行业知识
K最临近算法(KNN)
���录
一、介绍
二、距离的计算
2.1 闵式距离
2.2 余弦距离
三、K值的选取
四、KNN代码实现（Python）
一、介绍
在机器学习中，KNN是很简单、很常用的分类算法。
当我们已经一些分类好的数据时，如果这时新增了一个没有分类的数据该怎么办呢？
我们可以使用knn为这个数据分类，所谓knn就是K个最临近邻居（k-nearest neighbor）。也就是说我们通过判断这个数据与其他数据的距离来给他分类。
为了方便解释，我们设新增的数据为F，假设原本的数据为：
| 数据 | 标签 |
| A | 1 |
| B | 1 |
| C | 0 |
| D | 1 |
| E | 0 |
F与原有数据的距离为：
| 数据 | 距离 |
| A | 10 |
| B | 24 |
| C | 45 |
| D | 34 |
| E | 25 |
我们可以通过距离给原有的数据按升序排序：A、B、E、D、C。
对于k值我们取3，那么F与前3个最近的数据就是A、B、E了，它们对应的标签分别是1、1、0。
那么对于F分配的标签就是1。
想必到此你也明白了knn的大概思路了。简单来说是当一个样本点标签未知时，我们可以去寻找离它最近的k个样本点，并统计它们的标签，最后取出现次数最多的标签作为这个样本的标签。
当然，到此你已经对KNN有所了解。你可能还存有疑问，比如这些距离是如何计算得到的、K的取值该如何确定。接下来，我们将解决这个问题。
二、距离的计算
在特征空间中，两个样本点之间的距离大小可以认为是反映这两个样本的相似程度。
我们可以用闵式距离（闵可夫斯基距离 Minkowski Distance）和余弦距离（Cosine Distance）
2.1 闵式距离
闵式距离并不是一个距离，而是一组距离。
对于A(x11, x12, ..., x1n)和B(x21, x22, ..., x2n)，我们可以用闵式距离的公式计算。
当p=1时，为曼哈顿距离。
当p=2时，为欧几里得距离。
当p=时，为切比雪夫距离。
2.2 余弦距离
余弦距离也可以称为余弦相似度，余弦值的大小可以反应两个样本点在特征空间的夹角。
余弦值越大，夹角越小，两个样本点的向量夹角越小，其相似程度越高。
三、K值的选取
当K值取1时，即为最临近算法。新增的未标注的样本点会被归到离它最近的样本所在的类中。这可能会出现问题，比如原数据存在问题的话。还是应该多参考其他邻居的情况。
当K值过大时，这时可能会把较远的邻居考虑进去，这并不是我们希望的，就会导致欠拟合。
当K值取偶数时，就可能出现两个类出现次数一样的情况，这时又该选哪一类？所以我们一般将K值设置为奇数。
K值的选取我们可以通过交叉验证，让K从一个很小的值开始，比如从1开始慢慢增大，选取误差最小的K值。（为什么要从1开始呢？因为在某些情况下，K值取1的效果会更加好些，具体取值还得根据具体的实际情况决定）
还有一种方法就是通过过往的经验判断。
四、KNN代码实现（Python）
这里笔者使用欧几里得距离。
def knn(x, y, labels, k): #计算距离 dist = ((x-y)**2).sum(1) dist = np.sqrt(dist) #排序 indx = dist.argsort() #统计前k个邻居中每类出现的次数 cnt = {} for i in range(k): if cnt.get(labels[indx[i]]) is None: cnt[labels[indx[i]]] = 1 else: cnt[labels[indx[i]]] += 1 c = sorted(cnt.items(), key=operator.itemgetter(1), reverse=True) #返回出现次数最多的类 return c[0][0] 完整代码：
import operatorimport matplotlib.pyplot as pltimport numpy as npcolor = ['b', 'c', 'g', 'k', 'm', 'r', 'y', 'orange', 'tan', 'teal', 'darkblue', 'darkred', 'gold']def knn(x, y, labels, k): dist = ((x-y)**2).sum(1) dist = np.sqrt(dist) indx = dist.argsort() cnt = {} for i in range(k): if cnt.get(labels[indx[i]]) is None: cnt[labels[indx[i]]] = 1 else: cnt[labels[indx[i]]] += 1 c = sorted(cnt.items(), key=operator.itemgetter(1), reverse=True) print(cnt) return c[0][0]x, y = np.random.random(2)*100, np.random.random([10, 2])*100labels = [1, 0, 1, 2, 2, 1, 2, 1 ,0, 1]pred = knn(x, y, labels, 3)print(f'{x} 的类别是 {pred} {color[pred]}')cls = {}for i, label in enumerate(labels): if cls.get(label) is None: cls[label] = [y[i]] else: cls[label].append(y[i])for c in cls: plt.plot([i[0] for i in cls[c]], [i[1] for i in cls[c]], 'o', color=color[c], label=str(c)+f' {color[c]}') plt.legend()plt.plot(x[0], x[1], 'o', color='darkred', label=str(pred)+f' {color[pred]}')plt.legend()plt.show() 分类结果（k值为3）：
红色点为新增的样本点，其他颜色为原有的样本点。
我们可以看到离新增的样本最近的样本为：
两个1（蓝色），一个0（绿色），所以新增的样本点（红色）标签为1
