K-邻近算法(KNN)_k近邻算法k的取值

1. KNN 算法原理

k-近邻算法（k-Nearest Neighbour algorithm）的工作原理：给定一个已知标签类别的训练数据集，输入没有标签的新数据后，在训练数据集中找到与新数据最邻近的 k 个实例，如果这 k 个实例的多数属于某个类别，那么新数据就属于这个类别。即由那些离新数据最近的 k 个实例来投票决定新数据归为哪一类。

最邻近分类算法是数据挖掘分类（classification）技术中最简单的算法之一，其指导思想是”近朱者赤，近墨者黑“，即由你的邻居来推断出你的类别。

比如，有红色三角形和蓝色方块两种类型，现在想要判断绿色的圆点属于那种类别：

若 k=3，绿色圆点属于红色三角类别（距离绿色圆点最近的是 2 个红色三角和 1 个蓝色方块，少数服从多数，继而判定绿色圆点属于红色三角）；若 k=5，由于蓝色四方形比例为3/5，因此绿色圆将被判定为属于蓝色四方形类。

由于KNN最邻近分类算法在分类决策时只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

2. kNN 算法的流程

1. 计算已知类别数据集中的点与当前点之间的距离；

2. 按照距离递增次序排序；

3. 选取与当前点距离最小的 k 个点；

4. 确定前 k 个点所在类别的出现频率；

5. 返回前 k 个点出现频率最高的类别作为当前点的预测类别。

3. kNN 的基本要素

由上述的流程可知，对于一个确定的训练集，只要确定了距离度量、k值和分类决策规则，就能对任何一个新的实例，确定它的分类。

3.1 距离度量

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

距离度量是描述特征空间中两个实例的距离，也是这两个实例的相似程度。

在 n 维实数向量空间中，我们主要使用的距离度量方式是欧式距离，但也可以使用更加一般的 Minkowski 距离。

关于距离的度量方法，常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）或其他。

3.1.1 欧氏距离

　Euclidean Distance 定义：

　　两个点或元组P1=（x1，y1）和P2=（x2，y2）的欧几里得距离是

   

3.1.2 曼哈顿距离

3.1.3 闵可夫斯基距离

若二个向量或二个点p 、and q，其座标分别为pi及qi，则两者之间的切比雪夫距离定义如下：D(p,q)=max(|pi-qi|)，这也等于以下Lp度量的极值：，因此切比雪夫距离也称为L∞度量。

3.2 k 值的选择

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

对于k值的选择，一般根据样本的分布，选择一个较小的值，然后通过交叉验证选择一个合适的k值。

• 选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测7结果起作用，与此同时带来的问题是泛化误差会增大。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。

• 选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误。换句话说，k值的增大就意味着整体的模型变得简单，容易发生欠拟合。

一个极端的例子是 k 等于样本数，则完全没有分类，那么无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。

K的取法：

 常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。

一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。

3.3 分类决策规则

k 近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

4. kNN 算法的 Python 实现

有人曾经统计过很多电影的打斗镜头和接吻镜头，下图显示了 6 部电影的打斗和接吻镜头数。假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？我们可以使用 kNN 来解决这个问题。

4.1 算法实现

4.1.1 构建已经分类好的原始数据集

import pandas as pd
import seaborn as sns
%matplotlib inline
 
data = {'电影名称':['California Man','He’s Not Really into Dudes','Beautiful Woman','Kevin Longblade','Robo Slayer 3000','Amped II','?'],
        '打斗镜头':[3,2,1,101,99,98,18],
        '接吻镜头':[104,100,81,10,5,2,90],
        '电影类型':['爱情片','爱情片','爱情片','动作片','动作片','动作片','未知']}
 
movie_data = pd.DataFrame(data)
 
movie_data

sns.lmplot('打斗镜头','接吻镜头',movie_data,hue='电影类型', fit_reg=False)

<seaborn.axisgrid.FacetGrid at 0x193aaee9fd0>

我们可以从散点图中大致推断，这个未知电影有可能是爱情片，因为看起来它距离已知的三个爱情片的点更近一点。那么，具体是如何来度量距离的呢？这个例子中我们使用欧氏距离来衡量。

4.1.2 计算已知类别数据集中的点与当前点之间的距离

new_data=list(movie_data.loc[6][1:3])
dist = list((((movie_data.iloc[:6,1:3]-new_data)**2).sum(1))**0.5)
# .iloc：根据标签的所在位置，从 0 开始计数，选取列
# loc：根据 DataFrame 的具体标签选取列
dist

[42.5440947723653,
 39.66106403010388,
 26.92582403567252,
 95.80187889597991,
 97.30878685915265,
 98.49365461794989]

4.1.3 将距离升序排列，然后选取距离最小的k个点

dist_l = pd.DataFrame({'dist':dist, 'labels':movie_data.iloc[:6,3]})
dr = dist_l.sort_values(by='dist')[:4]
dr

4.1.4 确定前k个点所在类别的出现频率

re = dr.loc[:,'labels'].value_counts()
re

爱情片    3
动作片    1
Name: labels, dtype: int64

4.1.5 选择频率最高的类别作为当前点的预测类别

result = []
result.append(re.index[0])
result

['爱情片']

4.2 封装函数

import pandas as pd
 
def classify0(inX, dataSet, k):
    result = []
    dist = list((((dataSet.iloc[:,1:3]-inX)**2).sum(1))**0.5)
    dist_l = pd.DataFrame({'dist':dist, 'labels':dataSet.iloc[:,3]})
    dr = dist_l.sort_values(by='dist')[:k]
    re = dr.loc[:,'labels'].value_counts()
    result.append(re.index[0])
    return result

classify0(new_data, movie_data[], 4)

['爱情片']

4.3 sklearn 实现

Scikit-learn 是专门面向机器学习的 Python 开源框架，它实现了各种成熟的算法，并且易于安装与使用。KNeighborsClassifier 在 scikit-learn 在 sklearn.neighbors 包之中。KNeighborsClassifier 使用很简单，三步：

1. 创建 KNeighborsClassifier 对象；

2. 调用 fit 函数；

3. 调用predict函数进行预测。

from sklearn.neighbors import KNeighborsClassifier
X = movie_data.iloc[:6,1:3]
y = movie_data.iloc[:6,3]
neigh=KNeighborsClassifier(n_neighbors=4)
neigh.fit(X,y)
print(neigh.predict([[18,90]]))

['爱情片']

5. 优缺点

• 优点：简单，易于理解，无需建模与训练，易于实现；适合对稀有事件进行分类；适合与多分类问题，例如根据基因特征来判断其功能分类，kNN 比 SVM 的表现要好。

• 缺点：惰性算法，内存开销大，对测试样本分类时计算量大，性能较低；可解释性差，无法给出决策树那样的规则。

Reference

• 《机器学习实战》第 2 章 k-近邻算法

• 《统计学习方法》第 3 章 k 近邻法

• K近邻算法（KNN）