KNN 算法（K Near Neighbor）

一、简介

​ 就是说每个样本都可以根据与它最接近的K个邻居来代表，是一种基于监督学习方式的分类算法。简单来表达：近朱者赤近墨者黑。具体可以表示为下图：

alt

​ 图中绿色的点可以根据距离K内的其他邻居来判断是三角还是方块。

二、距离

​ 我们一般选用曼哈顿距离或者是欧氏距离，具体表述公式如下：

曼哈顿距离:d1,2=∑i=1k∣x1i−x2i∣欧氏距离:d1,2=∑i=1k∣x1i−x2i∣2\text{曼哈顿距离:} d_{1,2} = \sum_{i=1}^k|x_{1i}-x_{2i}| \\\text{欧氏距离:} d_{1,2} =\sqrt{\sum_{i=1}^k{|x_{1i}-x_{2i}|}^2}

三、K值的选取

​ K值的选取对于算法的影响很大，K = 0的时候没有邻居，K = N(邻居个数)的时候输出邻居中数量最多的。所以为了选取一个合适的K值也很重要。

交叉验证法

​ 我们使用交叉验证发来搜索K值，具体例子如下；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import numpy as np
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import KFold  #主要用于K折交叉验证

# 导入iris数据集
iris=datasets.load_iris()
X=iris.data
y=iris.target
print(X.shape,y.shape)
# 定义我们想要搜索的K值（候选集），这里定义8个不同的值
ks=[1,3,5,7,9,11,13,15]

# 例：进行5折交叉验证，KFold返回的是每一折中训练数据和验证数据的index
# 假设数据样本为:[1,3,5,6,11,12,43,12,44,2],总共10个样本
# 则返回的kf的格式为（前面的是训练数据，后面的是验证数据）：
# [0,1,3,5,6,7,8,9],[2,4]
# [0,1,2,4,6,7,8,9],[3,5]
# [1,2,3,4,5,6,7,8],[0,9]
# [0,1,2,3,4,5,7,9],[6,8]
# [0,2,3,4,5,6,8,9],[1,7]
kf =KFold(n_splits=5, random_state=2001, shuffle=True)

# 保存当前最好的K值和对应的准确值
best_k = ks[0]
best_score = 0

# 循环每一个K值
for k in ks:
    curr_score=0
    for train_index, valid_index in kf.split(X):
        #每一折的训练以及计算准确率
        clf = KNeighborsClassifier(n_neighbors=k)
        clf.fit(X[train_index], y[train_index])
        curr_score = curr_score + clf.score(X[valid_index], y[valid_index])
    #求5折的平均准确率
    avg_score = curr_score/5
    if avg_score > best_score:
        best_k = k
        best_score = avg_score
    print("现在的最佳准确率：%.2f"%best_score, "现在的最佳K值 %d"%best_k)

print("最终最佳准确率：%.2f"%best_score, "最终的最佳K值 %d"%best_k)

四、算法流程

  • 计算当前点与所有点之间的距离
  • 距离按照升序排列
  • 选取距离最近的K个点
  • 统计这K个点所在类别出现的频率
  • 这K个点中出现频率最高的类别作为预测的分类

五、适用场景

  • 多分类问题
  • 稀有事件分类问题
  • 文本分类问题
  • 模式识别
  • 聚类分析