黑马程序员技术交流社区

标题: 【上海校区】k近邻算法（KNN） [打印本页]
作者: 梦缠绕的时候    时间: 2018-8-28 09:19
标题: 【上海校区】k近邻算法（KNN）

方法：<span class="MathJax" id="MathJax-Element-722-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk近邻法
适用问题：多类分类，回归
模型特点：特征空间，样本点
模型类型：判别模型

一、介绍

<span class="MathJax" id="MathJax-Element-808-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk近邻法是一种基本分类与回归方法。思想是给定一个训练数据集，其中样本类别给定，分类时，对新的样本，根据其<span class="MathJax" id="MathJax-Element-809-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk个最近邻的训练实例的类别，通过多数表决等方式进行预测。

引用百度来的一张图，直观理解下k近邻算法：

目标是判断中心绿色点的类别，当<span class="MathJax" id="MathJax-Element-810-Frame" tabindex="0" data-mathml="k=3" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">k=3k=3时，所形成的圆内红色三角形数量最多，则目标为红色类，当<span class="MathJax" id="MathJax-Element-811-Frame" tabindex="0" data-mathml="k=5" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">k=5k=5时，所形成的圆内蓝色正方形最多，则目标为蓝色类，这就是<span class="MathJax" id="MathJax-Element-812-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk近邻算法。

<span class="MathJax" id="MathJax-Element-813-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk近邻的三要素是：<span class="MathJax" id="MathJax-Element-814-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk值得选择、距离度量及分类决策规则。

本文介绍<span class="MathJax" id="MathJax-Element-815-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk近邻算法，三要素及代码实现，kd树和搜索kd树的算法将在另一片博文中介绍。

二、k近邻算法算法：

输入：训练数据集


T=(x1,y1),(x2,y2),⋯,(xN,yN)T=(x1,y1),(x2,y2),⋯,(xN,yN)


其中，xixi为实例的特征向量，yiyi为实例的类别，i=1,2,⋯,N.i=1,2,⋯,N.

输出：实例<span class="MathJax" id="MathJax-Element-1186-Frame" tabindex="0" data-mathml="x" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">xx所属的类<span class="MathJax" id="MathJax-Element-1187-Frame" tabindex="0" data-mathml="y." role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">y.y.

算法步骤：三、k近邻的三要素

下面我们介绍k近邻法的三个基本要素：距离度量、k值的选择和分类决策规则的确定。

3.1 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映，一般使用的是欧氏距离，也可以使其他距离，如<span class="MathJax" id="MathJax-Element-4851-Frame" tabindex="0" data-mathml="LP" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">LPLP距离和Minkowski距离。
下面是每个距离的定义：

设特征空间<span class="MathJax" id="MathJax-Element-4852-Frame" tabindex="0" data-mathml="X" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">XX是<span class="MathJax" id="MathJax-Element-4853-Frame" tabindex="0" data-mathml="n" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">nn维实数向量空间<span class="MathJax" id="MathJax-Element-4854-Frame" tabindex="0" data-mathml="Rn," role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">Rn,Rn, <span class="MathJax" id="MathJax-Element-4855-Frame" tabindex="0" data-mathml="xi" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">xixi,<span class="MathJax" id="MathJax-Element-4856-Frame" tabindex="0" data-mathml="xj∈X," role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">xj∈X,xj∈X, <span class="MathJax" id="MathJax-Element-4857-Frame" tabindex="0" data-mathml="xi=(xi(1),xi(2),⋯,xi(n))T" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">xi=(xi(1),xi(2),⋯,xi(n))Txi=(xi(1),xi(2),⋯,xi(n))T,<span class="MathJax" id="MathJax-Element-4858-Frame" tabindex="0" data-mathml="xj=(xj(1),xj(2),⋯,xj(n))T," role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">xj=(xj(1),xj(2),⋯,xj(n))T,xj=(xj(1),xj(2),⋯,xj(n))T, <span class="MathJax" id="MathJax-Element-4859-Frame" tabindex="0" data-mathml="xi,xj" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">xi,xjxi,xj的<span class="MathJax" id="MathJax-Element-4860-Frame" tabindex="0" data-mathml="Lp" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">LpLp距离为：


Lp(xi,xj)=(∑i=1n|xi(l)−xj(l)|p)1pLp(xi,xj)=(∑i=1n|xi(l)−xj(l)|p)1p


这里<span class="MathJax" id="MathJax-Element-4862-Frame" tabindex="0" data-mathml="p≥1" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">p≥1p≥1.当<span class="MathJax" id="MathJax-Element-4863-Frame" tabindex="0" data-mathml="p=2" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">p=2p=2时，称为欧氏距离，即


L2(xi,xj)=(∑i=1n|xi(l)−xj(l)|2)12L2(xi,xj)=(∑i=1n|xi(l)−xj(l)|2)12


当<span class="MathJax" id="MathJax-Element-4865-Frame" tabindex="0" data-mathml="p=1" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">p=1p=1时 ，称为曼哈顿距离，即


L1(xi,xj)=∑i=1n|xi(l)−xj(l)|L1(xi,xj)=∑i=1n|xi(l)−xj(l)|


当<span class="MathJax" id="MathJax-Element-4867-Frame" tabindex="0" data-mathml="p=∞" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">p=∞p=∞时，取各个坐标距离的最大值，即



L∞(xi,xj)=maxl|xi(l)−xj(l)|L∞(xi,xj)=maxl⁡|xi(l)−xj(l)|


3.2 kk值的选择

k值的选择会对结果产生直接的影响。

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，近似误差会减小，只有输入实例较近的训练实例才会对预测结果起作用，但确定是估计误差会增大，因为预测结果会对邻近的实例点非常敏感，如果邻近的实例点恰巧是噪声，预测结果就会出错。<span class="MathJax" id="MathJax-Element-5360-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk值的减小意味着模型变得复杂，容易产生过拟合（这句话可以理解为<span class="MathJax" id="MathJax-Element-5361-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk增大，邻域边界相对更平滑，<span class="MathJax" id="MathJax-Element-5362-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk减小，邻域边界更弯曲，更参差不平，更复杂，可以画图帮助理解）。

如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测，其优点是可以减少学习的估计误差，缺点是学习的近似误差会增大，这时与输入实例较远的训练实例也会起预测作用，使预测发生错误，<span class="MathJax" id="MathJax-Element-5363-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk值的增大就意味着整体的模型变得简单。

当<span class="MathJax" id="MathJax-Element-5364-Frame" tabindex="0" data-mathml="k=N" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">k=Nk=N是，无论输入什么，都将简单预测为最多实例点的类，是不可取得。

在应用中，<span class="MathJax" id="MathJax-Element-5365-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk值一般去一个比较小的数值，采用交叉验证选取最优<span class="MathJax" id="MathJax-Element-5366-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk值。

3.3 分类决策规则

<span class="MathJax" id="MathJax-Element-6302-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk近邻法中的分类决策规则一般采用多数表决，即由输入实例的<span class="MathJax" id="MathJax-Element-6303-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk个邻近的训练实例中的多数类决定。

多数表决规则等价于经验风险最小化，解释如下：如果分类的损失函数为0-1损失函数，分类函数为


f:Rn→{c1,c2,⋯,cK}f:Rn→{c1,c2,⋯,cK}


那么误分类的概率是

P(Y≠f(X))=1−P(Y=f(X))P(Y≠f(X))=1−P(Y=f(X))


对于给定实例xx，其最近邻的kk个训练实例点构成的集合Nk(x)Nk(x).如果涵盖Nk(x)Nk(x)的区域的类别是cjcj,那么误分类率是

1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)


要使误分类率最小即经验风险最小，就要使∑xi∈Nk(x)I(yi=cj)∑xi∈Nk(x)⁡I(yi=cj)最大，所以多数表决规则等价于经验风险最小化。
四、模型的优缺点

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值，如权值与距离成反比。

优点：

1.简单，易于理解，易于实现，无需估计参数，无需训练；
2. 适合对稀有事件进行分类；
3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。

缺点：

1.该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的<span class="MathJax" id="MathJax-Element-6319-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。

2.该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的<span class="MathJax" id="MathJax-Element-6320-Frame" tabindex="0" data-mathml="k" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 16px; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">kk个最近邻点。

3.可理解性差，无法给出像决策树那样的规。

五、代码实现

sklearn有现有的包可以调用，具体如下：

>>> X = [[0], [1], [2], [3]]>>> y = [0, 0, 1, 1]>>> from sklearn.neighbors import KNeighborsClassifier>>> neigh = KNeighborsClassifier(n_neighbors=3)>>> neigh.fit(X, y) KNeighborsClassifier(...)>>> print(neigh.predict([[1.1]]))[0]>>> print(neigh.predict_proba([[0.9]]))[[ 0.66666667  0.33333333]]

kd树和kd树的最近邻搜索将单独作为一篇文章介绍。


作者: 不二晨    时间: 2018-8-30 17:10
奈斯，加油加油



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2