一、KNN算法原理

1、原理概述

KNN 的英文叫 K-Nearest Neighbo，应该算是数据挖掘算法中最简单的一种，也是相对最简单的一种分类方法，属于监督学习范畴。所谓K最近邻，就是K个最近的邻居的意思，每个样本都可以用它最接近的K个邻居来代表。与其他机器学习算法不一样的是：KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。

KNN思路大致为：一个训练数据集事先对每个训练样本标记好对应的标签。当来了一个新的测试样本预测分类时，K近邻的方法就是找到测试样本到原先的训练数据集中寻找每一个样本的相似度，然后根据相似度大小对训练数据集中样本排序，取前K个最相近的样本的标签的众数作为测试样本的标签（即前K个样本投票决定）。测试样本到原先训练数据集中每个训练样本的距离度量，一般用的是欧氏距离，也可以使用p范数（欧氏距离是2范数）。

工作原理总结：

1、计算待分类样本与其他样本之间的距离；

2、统计距离最近的K个邻居；

3、对于K个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。K 值如何选择。

2、K值的取值

K：临近数，即在预测目标点时取几个临近的点来预测。

K值得选取非常重要，因为如果 K 值比较小，就相当于未分类物体与它的邻居非常接近才行。这样产生的一个问题就是，如果邻居点是个噪声点，那么未分类物体的分类也会产生误差，这样 KNN 分类就会产生过拟合。

如果 K 值比较大，相当于距离过远的点也会对未知物体的分类产生影响，虽然这种情况的好处是鲁棒性强，但是不足也很明显，会产生欠拟合情况，也就是没有把未分类物体真正分类出来。

所以 K 值应该是个实践出来的结果，并不是我们事先而定的。在工程上，我们一般采用交叉验证的方式选取 K 值。交叉验证的思路就是，把样本集中的大部分样本作为训练集，剩余的小部分样本用于预测，来验证分类模型的准确性。所以在 KNN 算法中，我们一般会把 K 值选取在较小的范围内，同时在验证集上准确率最高的那一个最终确定作为 K 值。

3、距离的选取

距离就是平面上两个点的直线距离

关于距离的度量方法，常用的有：欧氏距离、曼哈顿距离、闵可夫斯基距离、切比雪夫距离、余弦值、相关度或其他。

1）欧氏距离

欧氏距离是我们最常用的距离公式，也叫做欧几里得距离。在二维空间中，两点的欧式距离就是：

图片

同理，我们也可以求得两点在 n 维空间中的距离：

图片

2）曼哈顿距离

曼哈顿距离在几何空间中用的比较多，等于两个点在坐标系上绝对轴距总和。用公式表示就是：

图片

3）闵可夫斯基距离

闵可夫斯基距离不是一个距离，而是一组距离的定义。对于 n 维空间中的两个点 x(x1,x2,…,xn) 和 y(y1,y2,…,yn) ， x 和 y 两点之间的闵可夫斯基距离为：

图片

其中 p 代表空间的维数，当 p=1 时，就是曼哈顿距离；当 p=2 时，就是欧氏距离；当 p→∞时，就是切比雪夫距离。

二、sklearn库函数调用

1、预测案例

1）案例代码

这个案例是我目前学习课程中的案例--使用 KNN 对手写数字进行识别分类。手写数字数据集是个很有名的用于图像识别的数据集。数字识别的过程就是将这些图片与分类结果 0-9 一一对应起来。完整的手写数字数据集 MNIST 里面包括了 60000 个训练样本，以及 10000 个测试样本。我使用的是 sklearn 自带的手写数字数据集做 KNN 分类，这个数据集可理解为一个简版的 MNIST 数据集。

# 导入依赖包
import numpy as np
import matplotlib 
import matplotlib.pyplot as plt
 
# 用来做数据集的分割，把数据分成训练集和测试集，这样做的目的是为了评估模型
from sklearn.model_selection import train_test_split
# 导入了KNN的模块，是sklearn提供的现成的算法
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
# 导入数据集
digits=datasets.load_digits()
# X存储的是数据的特征，y存储的每一个样本的标签或者分类
X=digits.data
y=digits.target
# 查看数据结构
X.shape
y.shape
digits.keys()
digits.target_names
X[:10]
# 数据探索
some_digit=X[666]
some_digit_image=some_digit.reshape(8,8)
plt.imshow(some_digit_image,cmap=matplotlib.cm.binary)
plt.show()

图片

# 分割数据，将20%的数据作为测试集，其余作为训练集（
X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.2,random_state=666) #设置随机种子random_st
# 调用库函数里的KNN，选择K值
# 定义了一个KNN object，带有参数叫做n_neighbors=3， 即K值是3
knn_clf=KNeighborsClassifier(n_neighbors=3)
knn_clf.fit(X_train,y_train)
# 预测以及计算准确率
y_predict=knn_clf.predict(X_test)
accuracy_score(y_test,y_predict)
correct=accuracy_score(y_test,y_predict)
print("正确率:",correct)

运行结果：
正确率: 0.988888888888888

案例代码构造一个 KNN 分类器 knn_clf，把训练集的数据传入构造好的 knn_clf，并通过测试集进行结果预测，与测试集的结果进行对比，得到 KNN 分类器准确率为0.9889

2）参数概述

KNN分类器的常用构造参数有：

1、n_neighbors 代表邻居的数量。

2、weights：代表所有邻居的权重，其中 uniform 代表所有邻居权重相同， distance 代表权重是距离的倒数。还可以自定义。

3、algorithm: 计算邻居的方法，auto代表根据数据的情况自动选择，kd_tree 是kd树，适用于维数不超过20的情况。ball_tree是球树，可以用于维度更大的情况。brute 是暴力搜索。

4、leaf_size:是kd树或者球树的叶子数量，默认是20.

2、KNN超参数

在KNN里，通过交叉验证，我们即可以得出最合适的K值。它的核心思想无非就是把一些可能的K逐个去尝试一遍，然后选出效果最好的K值。

1）手写超参数

# 寻找最好的k
best_method=""
best_score=0.0
best_k=-1
# 循环每一个K值
for method in["uniform","distance"]:
    for k in range(1,11):
        knn_clf=KNeighborsClassifier(n_neighbors=k,weights=method)
        knn_clf.fit(X_train,y_train)
        score=knn_clf.score(X_test,y_test)
        if score>best_score:
            best_k=k
            best_score=score
            best_method=method
        
print("best_k=:",best_k)
print("best_score=:",best_score)
print("best_method=:",best_method)

运行结果：
best_k=: 1

best_score=: 0.9888888888888889

best_method=: uniform

2）使用sklearn获取最优k值

# 通过网格方式来获取参数 Grid Search
from sklearn.model_selection import GridSearchCV
param_grid=[
    {
        'weights':['uniform'],
        'n_neighbors':[i for i in range(1,11)]
    },
    {
        'weights':['distance'],
        'n_neighbors':[i for i in range(1,11)],
        'p':[i for i in range(1,6)]
    }
]
# 通过GridSearchCV来搜索最好的K值
knn_clf_best=KNeighborsClassifier()
grid_Search=GridSearchCV(knn_clf_best,param_grid)
grid_Search.fit(X_train,y_train)
grid_Search.best_estimator_
grid_Search.best_score_
best_score=grid_Search.best_score_
# 输出最好的参数以及对应的准确率
best_score=grid_Search.best_score_
print("最优准确率:",best_score)

运行结果：
最优准确率****: ****0.988****16****9****7****9****81****9****0675

通过网格方式寻找最优k值方法计算出来的准确率为0.9882，对比上面实验结构，准确率有细微的下降，但这并不代表通过网格方式来获取参数的方法有问题，这两者的差异只是因为模型评判标准不一致形成的。

三、总结

1、 KNN算法是最简单有效的分类算法，简单且容易实现。当训练数据集很大时，需要大量的存储空间，而且需要计算待测样本和训练数据集中所有样本的距离，所以非常耗时。

2、 KNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。

3、KNN对于样本不均衡的数据效果不好，需要进行改进。改进的方法时对k个近邻数据赋予权重，比如距离测试样本越近，权重越大。

【机器学习算法系列】KNN算法的世界