机器学习之KNN算法实现原理及Kd-tree的构建

K近邻（K-nearest neighbors,KNN）是一种基本的机器学习算法，所谓K近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻居来代表。KNN在做回归和分类额主要区别在于最后做预测的时候的决策方式不同，KNN在分类预测时，一般采用多数表决法；而在做回归预测时，一般采用平均值法。



首先输入样本进行分类，然后输入需要判断的物体根据KNN原则将其归类
KNN三要素
K值的选择对于K值的选择，一般根据样本分布选择一个较小的值，然后通过交叉验证来选择一个比较合适的最终值；当选择比较小的K值的时候，表示使用较小邻域中的样本进行预测，训练误差会减小，但是会导致模型变得复杂，容易过拟合；当选择较大的K值的时候，表示使用较大邻域中的样本进行预测，训练误差会增大，同时会使模型变得简单，容易导致欠拟合；
距离的度量一般使用欧式距离（欧几里得距离）；
决策规划在分类模型中，主要使用多数表决法或者加权多数表决法；在回归模型中，主要使用平均值法或者加权平均值法。
KD tree是KNN算法中用于计算最近邻的快速，便捷构建方式。当样本数量少的时候，我们可以使用brute这种暴力的方式进行求解最近邻，即计算到所有样本的距离。担当样本量比较大的时候u，直接计算所有样本的距离，工作量有点大，所以在这种情况下，我们可以使用kd-tree来快速计算。例如：样本中x2维度是方差最大的，那么计算m个样本中所有的x2的值，取中位数，小于该中位数的划分到左边，大于该中位数的划分到右边，分完后再分别取左子树和右子树中寻找方差最大的维度，依次递归直到树节点里只有一个样本。
方差最大的维度，证明波动的范围最大，即左右子树的样本的差异性最大。如果数量是偶数个，则选取中间两个数中较大的作为中位数进行划分。
划分流程如下：