KNN 的英文叫 K-Nearest Neighbor，应该算是数据挖掘算法中最简单的一种。
1. KNN的工作原理
“近朱者赤，近墨者黑”可以说是 KNN 的工作原理。整个计算过程分为三步：
（1）计算待分类物体与其他物体之间的距离；
（2）统计距离最近的 K 个邻居；
（3）对于 K 个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。
2. K 值如何选择
K 值的选择还是很重要的，那么K 值选择多少是适合的呢？
（1）如果 K 值比较小，就相当于未分类物体与它的邻居非常接近才行。这样产生的一个问题就是，如果邻居点是个噪声点，那么未分类物体的分类也会产生误差，这样 KNN 分类就会产生过拟合。
（2）如果 K 值比较大，相当于距离过远的点也会对未知物体的分类产生影响，虽然这种情况的好处是鲁棒性强，但是不足也很明显，会产生欠拟合情况，也就是没有把未分类物体真正分类出来。
所以 K 值应该是个实践出来的结果，并不是事先而定的。在工程上，一般采用交叉验证的方式选取 K 值。
3. 距离
在 KNN 算法中，还有一个重要的计算就是关于距离的度量。两个样本点之间的距离代表了这两个样本之间的相似度。距离越大，差异性越大；距离越小，相似度越大。
距离的计算方式有下面五种方式：
（1）欧氏距离；
（2）曼哈顿距离；
（3）闵可夫斯基距离；
（4）切比雪夫距离；
（5）余弦距离。
其中前三种距离是 KNN 中最常用的距离。
4. KD 树
KNN 的计算过程是大量计算样本点之间的距离。为了减少计算距离次数，提升 KNN 的搜索效率，人们提出了 KD 树（K-Dimensional 的缩写）。
KD 树是对数据点在 K 维空间中划分的一种数据结构。在 KD 树的构造中，每个节点都是 k 维数值点的二叉树。
5 KNN 做回归
对于一个新点，找出k个最近邻居，将他们的属性加权平均赋给改点。
6 KNN分类
构造函数 KNeighborsClassifier(n_neighbors=5, weights=‘uniform’, algorithm=‘auto’, leaf_size=30)
（1）n_neighbors：即 KNN 中的 K 值，代表的是邻居的数量。K 值如果比较小，会造成过拟合。如果 K 值比较大，无法将未知物体分类出来。一般我们使用默认值 5。
(2) weights：是用来确定邻居的权重，有三种方式：
weights=uniform，代表所有邻居的权重相同；
weights=distance，代表权重是距离的倒数，即与距离成反比；
自定义函数，你可以自定义不同距离所对应的权重。大部分情况下不需要自己定义函数。
(3) algorithm：用来规定计算邻居的方法，它有四种方式：
algorithm=auto，根据数据的情况自动选择适合的算法，默认情况选择 auto；
algorithm=kd_tree，也叫作 KD 树，是多维空间的数据结构，方便对关键数据进行检索，不过 KD 树 适用于维度少的情况，一般维数不超过 20，如果维数大于 20 之后，效率反而会下降；
algorithm=ball_tree，也叫作球树，它和 KD 树一样都是多维空间的数据结果，不同于 KD树，球树更适用于维度大的情况；
algorithm=brute，也叫作暴力搜索，它和 KD 树不同的地方是在于采用的是线性扫描，而不
是通过构造树结构进行快速检索。当训练集大的时候，效率很低。
（4）leaf_size：代表构造 KD 树或球树时的叶子数，默认是 30，调整 leaf_size 会影响到树的构造和搜索速度。
代码： https://github.com/gzhold/DataAnalysis/tree/master/sklearn/knn
网友评论