Summary

简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。 它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。

适用数据范围：数值型和标称型。

详细介绍

下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

img

由此也说明了KNN算法的结果很大程度取决于K的选择。

在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离：

img

**接下来对KNN算法的思想总结一下：**就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点；

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

5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

常见问题

1. K值设定为多大？

K太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响） k值通常是采用交叉检验来确定（以k=1为基准） 经验规则：k一般低于训练样本数的平方根

2. 类别如何判定最合适？

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。

3. 如何选择合适的距离衡量？

高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。 变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

4. 训练样本是否要一视同仁？

在训练集中，有些样本可能是更值得依赖的。 可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。

5. 性能问题？

KNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。 懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。 已经有一些方法提高计算的效率，例如压缩训练样本量等。

6. 能否大幅减少训练样本量，同时又保持分类精度？

浓缩技术(condensing) 编辑技术(editing)

算法实例

如scikit-learn中的KNN算法使用:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#coding:utf-8
from sklearn import datasets #sk-learn 内置数据库
import numpy as np
'''KNN算法'''
iris = datasets.load_iris() #内置的鸢尾花卉数据集
#数据集包含150个数据集，分为3类，每类50个数据,
#可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个特征预测鸢尾花卉属于
#(Setosa，Versicolour，Virginica)三个种类中的哪一类
iris_X,iris_y = iris.data,iris.target #数据集及其对应的分类标签
# 将数据集随机分为训练数据集和测试数据集
np.random.seed(0)
indices = np.random.permutation(len(iris_X))
#用于训练模型
iris_X_train = iris_X[indices[:-10]]
iris_y_train = iris_y[indices[:-10]]
#用于测试模型
iris_X_test  = iris_X[indices[-10:]]
iris_y_test  = iris_y[indices[-10:]]
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier()
knn.fit(iris_X_train,iris_y_train)
prediction = knn.predict(iris_X_test)
score = knn.score(iris_X_test,iris_y_test)

print '真实分类标签:'+str(iris_y_test)
print '模型分类结果:'+str(prediction)+'\n算法准确度:'+str(score)

输出结果:

1
2
3

真实分类标签:[1 1 1 0 0 0 2 1 2 0]
模型分类结果:[1 2 1 0 0 0 2 1 2 0]
算法准确度:0.9