机器学习之K近邻法（KNN）

一、基本概念：

二、距离的计算方式：

三、k的选取:

四、特征归一化：

五、交叉验证：

一、基本概念：

k近邻算法是一种基本分类和回归方法。这里只讨论分类问题的k近邻法。

k近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分类到这个类中。

“近朱者赤，近墨者黑”可以说是 KNN 的工作原理。整个计算过程分为三步：

计算待分类物体与其他物体之间的距离；
统计距离最近的 K 个邻居；
对于 K 个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。下面我们根据k近邻的思想来给绿色圆点进行分类。

如果k=3，绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
如果k=5，绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

我们再通过代码看下 KNN 的功能：

'''
调用sklearn中的KNN模型
'''
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import numpy as npiris = datasets.load_iris()
x = iris.data
y = iris.target
print(x,y)x_train,x_test,y_train,y_test = train_test_split(x,y,random_state=20)clf = KNeighborsClassifier(n_neighbors=3)
clf.fit(x_train,y_train)correct = np.count_nonzero((clf.predict(x_test)==y_test)==True)
print("accuracy is:%.3f"%(correct/len(x_test)))

运行结果：

二、距离的计算方式：

（我们这里选择欧式距离）

（1）、欧氏距离:

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

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

（2）、曼哈顿距离

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

（3）、闵可夫斯基距离:

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

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

切比雪夫距离：

它是各个坐标距离的最大值，即 $d=max_{l}\left |x_{l}- y_{l}\right |$ .

（4）、余弦距离:

余弦距离实际上计算的是两个向量的夹角，是在方向上计算两者之间的差异，对绝对数值不敏感。在兴趣相关性比较上，角度关系比距离的绝对值更重要，因此余弦距离可以用于衡量用户对内容兴趣的区分度。比如我们用搜索引擎搜索某个关键词，它还会给你推荐其他的相关搜索，这些推荐的关键词就是采用余弦距离计算得出的。

手动实现 KNN：

from sklearn import datasets
from collections import Counter  # 为了做投票
from sklearn.model_selection import train_test_split
import numpy as np# 导入iris数据
iris = datasets.load_iris()
x = iris.data
y = iris.target
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=2003)def euc_dis(instance1, instance2):"""计算两个样本instance1和instance2之间的欧式距离instance1: 第一个样本， array型instance2: 第二个样本， array型"""dist = np.sqrt(np.sum((instance1 - instance2)**2 ))return distdef knn_classify(x, y, testInstance, k):"""给定一个测试数据testInstance, 通过KNN算法来预测它的标签。 x: 训练数据的特征y: 训练数据的标签testInstance: 测试数据，这里假定一个测试数据 array型k: 选择多少个neighbors?返回testInstance的预测标签 = {0,1,2}"""distances = [euc_dis(xones, testInstance) for xones in x]# 排序kneighbors = np.argsort(distances)[:k]# count是一个字典count = Counter(y[kneighbors])# count.most_common()[0][0])是票数最多的return count.most_common()[0][0]predictions = [knn_classify(x_train, y_train, data, 3) for data in x_test]
correct = np.count_nonzero((predictions == y_test) == True)
print("Accuracy is: %.3f" % (correct / len(x_test)))

运行结果：

三、k的选取:

一般而言，k 值的大小对分类结果有着重大的影响。

当选择的 k 值较小的情况下，就相当于用较小的邻域中的训练实例进行预测，只有当与输入实例较近的训练实例才会对预测结果起作用。但与此同时预测结果会对实例点非常敏感，分类器抗噪能力较差，因而容易产生过拟合，所以一般而言，k 值的选择不宜过小。

如图，其中有俩类，一个是黑色的圆点，一个是蓝色的长方形，现在我们的待分类点是红色的五边形。当 k 等于 1 时，待分类点将被误判为黑色的圆点。

但如果选择较大的 k 值，就相当于在用较大邻域中的训练实例进行预测，但相应的分类误差也会增大，模型整体变得简单，会产生一定程度的欠拟合。我们想，如果k=N（N为训练样本的个数）,那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型是不是非常简单，这相当于你压根就没有训练模型呀！直接拿训练数据统计了一下各个数据的类别，找最大的而已！

所以一般而言，我们需要采用交叉验证的方式来选择合适的 k 值。

大家可以从下面案例中体会下 K 值对模型的影响：

import matplotlib.pyplot as plt
import numpy as np
from itertools import product
from sklearn.neighbors import KNeighborsClassifier#生成一些随机样本
n_points=100
x1=np.random.multivariate_normal([1,50],[[1,0],[0,10]],n_points)
x2=np.random.multivariate_normal([2,50],[[1,0],[0,10]],n_points)
x=np.concatenate([x1,x2])
y=np.array([0]*n_points+[1]*n_points)
#print(x.shape,y.shape)# KNN 模型的训练过程
clfs = []
neighbors=[1,3,5,9,11,13,15,17,19]
for i in range(len(neighbors)):clfs.append(KNeighborsClassifier(n_neighbors=neighbors[i]).fit(x,y))#可视化结果
x_min,x_max=x[:,0].min()-1,x[:,0].max()+1
y_min,y_max=x[:,1].min()-1,x[:,1].max()+1
xx,yy=np.meshgrid(np.arange(x_min,x_max,0.1),np.arange(y_min,y_max,0.1))f,axarr=plt.subplots(3,3,sharex='col',sharey='row',figsize=(15,12))
for idx,clf,tt in zip(product([0,1,2],[0,1,2]),clfs,['KNN(k=%d)'%k for k in neighbors]):z=clf.predict(np.c_[xx.ravel(),yy.ravel()])z=z.reshape(xx.shape)axarr[idx[0],idx[1]].contourf(xx,yy,z,alpha=0.4)axarr[idx[0], idx[1]].scatter(x[:,0],x[:,1],c=y,s=20,edgecolor='k')axarr[idx[0], idx[1]].set_title(tt)
plt.show()

四、特征归一化：

可以说 KNN 是基于距离的度量的，为了避免各特征的范围不同导致在距离计算中所占权重不同的情况，需要进行特征归一化。

归一化方法----极差变换法：（也称为min-max方法），通过线性变换将数据映射到[0,1]之间，变换公式是：

其中min是样本中最小值，max是样本中最大值，x为每一个特征的值

标准化方法----z-score：将数据转换到均值为0，标准差为1的范围内，公式如下：

作用于每一列，其中mean为特征的平均值，σ为标准差

五、交叉验证：

交叉验证，顾名思义，就是重复的使用数据，把得到的样本数据进行切分，组合为不同的训练集和测试集，用训练集来训练模型，用测试集来评估模型预测的好坏。在此基础上可以得到多组不同的训练集和测试集，某次训练集中的某样本在下次可能成为测试集中的样本，即所谓“交叉”。

第一种：简单交叉验证，我们随机的将样本数据分为两部分（比如： 70%的训练集，30%的测试集），然后用训练集来训练模型，在测试集上验证模型及参数。接着，我们再把样本打乱，重新选择训练集和测试集，继续训练数据和检验模型。最后我们选择损失函数评估最优的模型和参数。

第二种：S折交叉验证（S-Folder Cross Validation）。和第一种方法不同，S折交叉验证会把样本数据随机的分成S份，每次随机的选择S-1份作为训练集，剩下的1份做测试集。当这一轮完成后，重新随机选择S-1份来训练数据。若干轮（小于S）之后，选择损失函数评估最优的模型和参数。

第三种：留一交叉验证（Leave-one-out Cross Validation），它是第二种情况的特例，此时S等于样本数N，这样对于N个样本，每次选择N-1个样本来训练数据，留一个样本来验证模型预测的好坏。此方法主要用于样本量非常少的情况，比如对于普通适中问题，N小于50时，一般采用留一交叉验证。

import numpy as npiris = datasets.load_iris()
x = iris.data
y = iris.target#定义我们想要搜索的 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=0for train_index,test_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[test_index],y[test_index])#求一下5折的平均准确率avg_score=curr_score/5if avg_score>best_score:best_k=kbest_score=avg_scoreprint("K值为 % d 时，品均准确率为 %.3f"%(k,avg_score))
print("the best_k is:%d"%best_k)

寻找最好的参数这一过程，可以直接用网格搜素实现：

#通过网格搜索来搜搜参数
from sklearn.model_selection import GridSearchCV
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifieriris = datasets.load_iris()
x = iris.data
y = iris.target#设置需要搜索的 K 值，注意：'n_neighbors'是 sklearn中 KNN 的参数，不能随便写
parameters={'n_neighbors':[1,3,5,7,9,11,13,15]}
knn=KNeighborsClassifier()#注意：这里不用指定参数clf=GridSearchCV(knn,parameters,cv=5)
clf.fit(x,y)print("最好的准确率为：%0.2f"%clf.best_score_,"最好的k值：",clf.best_params_)  #这里clf.best_params_是一个字典格式