K邻近算法
K邻近算法(KNN)(k-nearest neighbors) 非常简单且非常有效。KNN 的模型表示是整个训练数据集。简单吧？
通过搜索K个最相似的实例（邻居）的整个训练集并总结那些K个实例的输出变量，对新数据点进行预测。对于回归问题，这可能是平均输出变量，对于分类问题，这可能是模式（或最常见）类值。
诀窍在于如何确定数据实例之间的相似性。如果您的属性具有相同的比例（例如，以英寸为单位），则最简单的技术是使用欧几里德距离，您可以根据每个输入变量之间的差异直接计算该数字。
KNN可能需要大量内存或空间来存储所有数据，但仅在需要预测时才进行计算（或学习），及时。您还可以随着时间的推移更新和策划您的训练实例，以保持预测准确。
距离或接近度的概念可以在非常高的维度（许多输入变量）中分解，这会对算法在您的问题上的性能产生负面影响。这被称为维度的诅咒。它建议您仅使用与预测输出变量最相关的输入变量。
百度百科版本
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。
维基百科版本
在模式识别中，k-最近邻算法（k-NN）是用于分类和回归的非参数方法。在这两种情况下，输入都包含特征空间中最近的k个训练样例。输出取决于k-NN是用于分类还是回归：
- 在k-NN分类中，输出是类成员资格。对象通过其邻居的多个投票进行分类，其中对象被分配给其k个最近邻居中最常见的类（k是正整数，通常是小整数）。如果 k = 1，则简单地将对象分配给该单个最近邻居的类。
-在k-NN回归中，输出是对象的属性值。该值是其k个最近邻居的值的平均值。
k-NN是一种基于实例的学习或懒惰学习，其中函数仅在本地近似，并且所有计算都推迟到分类。该k-NN算法是最简单的所有中机器学习算法。
优缺点
优点:
- 理论成熟，思想简单，既可以用来做分类也可以用来做回归；
- 可用于非线性分类；
- 训练时间复杂度为O(n)；
- 对数据没有假设，准确度高，对outlier不敏感；
- KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练；
- KNN理论简单，容易实现；
缺点
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）效果差；
- 需要大量内存；
- 对于样本容量大的数据集计算量比较大（体现在距离计算上）；
- 样本不平衡时，预测偏差比较大。如：某一类的样本比较少，而其它类样本比较多；
- KNN每一次分类都会重新进行一次全局运算；
- k值大小的选择没有理论选择最优，往往是结合K-折交叉验证得到最优k值选择；
我的理解
在我看来，knn就是计算测试数据与每一个训练数据的距离，取出距离最近的K个训练数据的标签，以其中数量最多的作为测试数据的预测标签。
思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
算法流程
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类
K的取值
K：临近数，即在预测目标点时取几个临近的点来预测。
K值得选取非常重要，因为：
- 如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
- 如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了； - K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。
常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。
kdtree
kdtree 的意义在于使得 knn算法的搜索环节更快，提升整体运行速度。
k-d树是每个节点都为k维点的二叉树。所有 非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点，节点右边的子树代表在超平面右边的点。选择超平面的方法如下：每个节点都与k维中垂直于超平面的那一维有关。因此，如果选择按照x轴划分，所有x值小于指定值的节点都会出现在左子树，所有x值大于指定值的节点都会出现在右子树。这样，超平面可以用该x值来确定，其法线为x轴的单位向量。
简单来说，就是：
- 选择一个维度（x，y，z ......）；
- 选出这些点这个维度值的中位数；
- 将数据按中位数分为两部分；
- 对这两部分数据同样执行上述操作，直到数据点的数目为 1。
收官~ 👊
本文由 Chakhsu Lau 创作，采用 知识共享署名4.0 国际许可协议进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。