机器学习最简单算法——KNN算法（K-Nearest Neighbor）-白红宇

机器学习最简单算法——KNN算法（K-Nearest Neighbor）

阅读量：2240 次

发布时间：2019-05-09

本文共 7718 字，大约阅读时间需要 25 分钟。

机器学习最简单算法——KNN算法（K-Nearest Neighbor）

一、学习算法

二、KNN算法（k-Nearest Neighbor）

三、sklearn算法库(scikit-learn)

四、学习曲线

五、交叉验证

六、归一化

七、距离惩罚

八、KNN模型评价

九、模型的追求

一、学习算法

机器学习的方法是基于数据产生的"模型"（model）的算法，也称"学习算法"（learning algorithm）。包括有监督学习（supervised learning）、无监督学习（unsupervised learning）、半监督学习（semi-supervised learning）、强化学习（reinforcement learning）。

1、有监督学习

指对数据的若干特征与若干标签（类型）之间的关联性进行建模的过程；只要模型被确定，就可以应用到新的未知数据上。这类学习过程可以进一步分为「分类」（classification）任务和「回归」（regression）任务。在分类任务中，标签都是离散值；而在回归任务中，标签都是连续值。

2、无监督学习

指对不带任何标签的数据特征进行建模，通常被看成是一种“让数据自己介绍自己” 的过程。这类模型包括「聚类」（clustering）任务和「降维」（dimensionality reduction）任务。聚类算法可以讲数据分成不同的组别，而降维算法追求用更简洁的方式表现数据。

3、半监督学习

另外，还有一种半监督学习（semi-supervisedlearning）方法，介于有监督学习和无监督学习之间。通常可以在数据不完整时使用。

4、强化学习

强化学习不同于监督学习，它将学习看作是试探评价过程，以"试错" 的方式进行学习，并与环境进行交互已获得奖惩指导行为，以其作为评价。此时系统靠自身的状态和动作进行学习，从而改进行动方案以适应环境。

二、KNN算法（k-Nearest Neighbor）

1、算法原理

k-近邻算法，它的本质是通过距离判断两个样本是否相似，如果距离够近就认为他们足够相似属于同一类别。我们找到离其最近的k个样本，并将这些样本称之为「近邻」(nearest neighbor)。对这k个近邻，查看它们的都属于何种类别（这些类别我们称作「标签」(labels)）。然后根据“少数服从多数，一点算一票”原则进行判断，数量最多的的标签类别就是新样本的标签类别。其中涉及到的原理是“越相近越相似”，这也是KNN的基本假设。

2、算法模型

可以看到k-近邻算法就是通过距离来解决分类问题。这里我们解决的二分类问题，整个算法结构如下：

①算距离

给定测试对象𝐼𝑡𝑒𝑚，计算它与训练集中每个对象的距离。

依据公式计算𝐼𝑡𝑒𝑚 与𝐷1,𝐷2,……𝐷j之间的相似度，得到𝑆𝑖𝑚 (𝐼𝑡𝑒𝑚,𝐷1) , 𝑆𝑖𝑚 (𝐼𝑡𝑒𝑚,𝐷2) , 𝑆𝑖𝑚 (𝐼𝑡𝑒𝑚,𝐷j).

② 找邻居

圈定距离最近的k个训练对象，作为测试对象的近邻。

将𝑆𝑖𝑚 (𝐼𝑡𝑒𝑚,𝐷1) , 𝑆𝑖𝑚 (𝐼𝑡𝑒𝑚,𝐷2) , 𝑆𝑖𝑚 (𝐼𝑡𝑒𝑚,𝐷j) 排序，若是超过相似度阈值𝑡，则放入邻居集合𝑁𝑁.

③ 做分类

根据这k个近邻归属的主要类别，来对测试对象进行分类。

自邻居集合𝑁𝑁中取出前k名，查看它们的标签，对这k个点的标签求和，以多数决，得到𝐼𝑡𝑒𝑚可能类别。

三、sklearn算法库(scikit-learn)

自2007年发布以来，scikit-learn已经成为Python中重要的机器学习库了。scikit-learn，简称sklearn，支持了包括分类、回归、降维和聚类四大机器学习算法，以及特征提取、数据预处理和模型评估三大模块。sklearn是一个可以帮助我们高效实现算法应用的工具包。

在这里插入图片描述

# sklearn实现流程from sklearn.neighbors import KNeighborsClassifier # 导入KNN算法# 实例化,简单来说就是赋值clf=KNeighborsClassifier(n_neighbors=3)# 训练模型clf = clf.fit(X,y) # 预测输出，返回预测的标签result = clf.predict([[12.8,4.1]])  # predict,传入的数据必须是二维的数组result  # 查看结果# 模型的评估，接口score，返回预测的准确率,只针对分类问题离散型score = clf.score([[12.8,4.1]],[0]) # score,传入的数据必须是二维的数组score # 准确率的范围[0-1]# 返回预测的概率clf.predict_proba([[12.8,4.1]])

#skearn导入数据集，做KNN预测from sklearn.neighbors import KNeighborsClassifierfrom sklearn.datasets import load_breast_cancer   #数据集库 from sklearn.model_selection import train_test_split  #划分数据集库# 探索数据集data = load_breast_cancer()dataX= data.dataX.shapey= data.targety.shape#划分训练集和测试集Xtrain,Xtest,ytrain,ytest=train_test_split(X,y,test_size=0.2)Xtrain.shape# 建立模型&评估模型clf = KNeighborsClassifier(n_neighbors=7)  clf = clf.fit(Xtrain,ytrain)score = clf.score(Xtest,ytest)score# 找出一个数据点的最近邻（返回索引）clf.kneighbors(Xtest[[30,20],:],return_distance=True)

四、学习曲线

KNN中的k 是一个超参数，所谓"超参数"，就是需要人为输入，算法不能通过直接计算得出的参数。KNN中的k 代表的是距离需要分类的测试点x 最近的k 个样本点，如果不输入这个值，那么算法中重要部分“选出k 个最近邻”就无法实现。从KNN的原理中可见，是否能够确认合适的k 值对算法有极大的影响。学习曲线就是可以用来选择最优的K值。

参数学习曲线是一条以不同的参数取值为横坐标，不同参数取值下的模型结果为纵坐标的曲线，我们往往选择模型表现最佳点的参数取值作为这个参数的取值。

#学习曲线，选择最优Kkrange = range(1,21)    score=[]for i in krange:    clf=KNeighborsClassifier(n_neighbors=i)    clf=clf.fit(Xtrain,ytrain)    score.append(clf.score(Xtest,ytest))    plt.plot(krange,score)plt.show()score.index(max(score))+1  # score取值最大时对应的x轴的取值就是我们需要的超参数n_neighbors

五、交叉验证

我们追求的是模型在未知数据集上的效果，在陌生数据集上表现优秀的能力被称为泛化能力，即我们追求的是模型的泛化能力。如果模型在一套训练集和数据集上表现优秀，那说明不了问题，只有在众多不同的训练集和测试集上都表现优秀，模型才是一个稳定的模型，模型才具有真正意义上的泛化能力。为此，机器学习领域有着发挥神作用的技能：「交叉验证」。

最常用的交叉验证是k折交叉验证。我们知道训练集和测试集的划分会干扰模型的结果，因此用交叉验证n次的结果求出的均值，是对模型效果的一个更好的度量。

对于带交叉验证的学习曲线，我们需要观察的就不仅仅是最高的准确率了，而是准确率高，方差还相对较小的点，这样的点泛化能力才是最强的。在交叉验证+学习曲线的作用下，我们选出的超参数能够保证更好的泛化能力。

最标准，最严谨的交叉验证应该有三组数据：训练集、验证集和测试集。。当我们获取一组数据后，先将数据集分成整体的训练集和测试集，然后我们把训练集放入交叉验证中，从训练集中分割更小的训练集（k-1份）和验证集（1份），此时我们返回的交叉验证结果其实是验证集上的结果。我们使用验证集寻找最佳参数，确认一个我们认为泛化能力最佳的模型，然后我们将这个模型使用在测试集上，观察模型的表现。

在这里插入图片描述

注意：交叉验证的折数不可太大，因为折数越大抽出来的数据集越小，训练数据所带的信息量会越小，模型会越来越不稳定。如果你发现不使用交叉验证的时候模型表现很好，一使用交叉验证模型的效果就骤降，一定要查看你的标签是否有顺序，然后就是查看你的数据量是否太小，折数是否太高。

# 绘制带交叉验证的学习曲线，折数不能太大，即cv值不能过大，10万数据量以下分5折，10万以上可多点score = []var_ = []krange=range(1,21)for i in krange:    clf = KNeighborsClassifier(n_neighbors=i)    cvresult = CVS(clf,X,y,cv=5)    score.append(cvresult.mean())    var_.append(cvresult.var())    plt.plot(krange,score,color='k')plt.plot(krange,np.array(score)+np.array(var_)*2,c='red',linestyle='--')plt.plot(krange,np.array(score)-np.array(var_)*2,c='red',linestyle='--')# 确定最合适的K值score.index(max(score))+1

在这里插入图片描述

六、归一化

在实际分析情景当中，绝大多数数据集都会存在各特征值量纲不同的情况，此时若要使用KNN分类器，则需要先对数据集进行归一化处理，即是将所有的数据压缩都同一个范围内。

当数据（x）按照最小值中心化后，再按极差（最大值-最小值）缩放，数据移动了最小值个单位，并且会被收敛到[0，1]之间，而这个过程，就称作数据归一化（Normalization，又称Min-Max Scaling）。

x^*=\frac{x-min(x)}{max(x)-min(x)}

在sklearn 当中，我们使用preprocessing.MinMaxScaler 来实现这个功能。MinMaxScaler 有一个重要参数，

feature_range，控制我们希望把数据压缩到的范围，默认是[0，1]。

在现实业务中，我们只知道训练集的数据，不了解测试集究竟会长什么样，所以我们要利用训练集上的最小值和极差来归一化测试集。

from sklearn.preprocessing import MinMaxScaler as mmsX_ = mms().fit_transform(X)  # 归一化score = []var_ = []krange=range(1,20)for i in krange:    clf = KNeighborsClassifier(n_neighbors=i)    cvresult = CVS(clf,X_,y,cv=5)    score.append(cvresult.mean())    var_.append(cvresult.var())    plt.plot(krange,score,color='k')plt.plot(krange,np.array(score)+np.array(var_)*2,c='red',linestyle='--')plt.plot(krange,np.array(score)-np.array(var_)*2,c='red',linestyle='--')

在这里插入图片描述

七、距离惩罚

重要参数：weights

关于惩罚因子的选取有很多种方法，最常用的就是根据每个最近邻xj距离的不同对其作加权，加权方法为设置?j 权重，该权重计算公式为：

w_j=\frac{1}{d(x',x_j)}

这里需要注意的是，关于模型的优化方法只是在理论上而言进行优化会提升模型判别效力，但实际应用过程中最终能否发挥作用，本质上还是取决于优化方法和实际数据情况的契合程度，如果数据本身存在大量异常值点，则采用距离远近作为惩罚因子则会有较好的效果，反之则不然。因此在实际我们进行模型优化的过程当中，是否起到优化效果还是要以最终模型运行结果为准。

在sklearn中，我们可以通过参数weights来控制是否适用距离作为惩罚因子。weigehts有三个值，默认uniform，每个点权重相同，distance是权重点与其距离的倒数，callable是一个用户定义的函数，它接受一个距离数组，并返回相同形状的数组包含权重。

# 加上参数weightsscore = []var_ = []krange = range(1,20)for i in krange:    clf = KNeighborsClassifier(n_neighbors=i,weights='distance')    cvresult = CVS(clf,X_train,Ytrain,cv=5)    score.append(cvresult.mean())    var_.append(cvresult.var())plt.plot(krange,score,color='k')plt.plot(krange,np.array(score)+np.array(var_)*2,c='red',linestyle='--')plt.plot(krange,np.array(score)-np.array(var_)*2,c='red',linestyle='--')bestindex = krange[score.index(max(score))]-1print(bestindex)print(score[bestindex])返回 16和0.967032967，表示最优k是16，同时学习分数是0.967# 测试模型效果clf = KNeighborsClassifier(n_neighbors=3,weights='distance').fit(X_train,Ytrain)score =clf.score(X_test,Ytest)score返回0.92105263，表示加上参数weights，模型在测试集上的分数0.92105263

八、KNN模型评价

根据算法基本执行流程，我们可总结最近邻分类器的特点如下：

1、应用广泛：

最近邻分类属于一类更广泛的技术，这种技术称为基于实例的学习，它使用具体的训练实例进行预测，而不必维护源自数据的抽象（或模型）。基于实例的学习算法需要邻近性度量来确定实例间的相似性或距离，还需要分类函数根据测试实例与其他实例的邻近性返回测试实例的预测类标号。

2、计算效率低，耗费计算资源较大：

像最近邻分类器这样的消极学习方法不需要建立模型，所以，学习的开销很大，因为需要逐个计算测试样例和训练样例之间的相似度。相反，积极学习方法通常花费大量计算资源来建立模型，模型一旦建立，分类测试样例就会非常快。

3、抗噪性较弱，对噪声数据（异常值）较为敏感：

最近邻分类器基于局部信息进行预测，而决策树和基于规则的分类器则试图找到一个拟合整个输入空间的全局模型。正是因为这样的局部分类决策，最近邻分类器（k很小时）对噪声非常敏感。

4、模型不稳定，可重复性较弱：

最近邻分类器可以生成任意形状的决策边界，这样的决策边界与决策树和基于规则的分类器通常所局限的直线决策边界相比，能提供更加灵活的模型表示。最近邻分类器的决策边界还有很高的可变性，因为它们依赖于训练样例的组合。增加最近邻的数目可以降低这种可变性。

5、需要进行归一化处理：

除非采用适当的邻近性度量和数据预处理，否则最近邻分类器可能做出错误的预测。例如，我们想根据身高（以米为单位）和体重（以磅为单位）等属性来对一群人分类。属性高度的可变性很小，从1.5米到1.85米，而体重范围则可能是从90磅到250磅。如果不考虑属性值的单位，那么邻近性度量可能就会被人的体重差异所左右。