分类算法之K最近邻算法(KNN)的Python实现
KNN的定义
所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
介绍
如下图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。
我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：
如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。
KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。
K 近邻算法使用的模型实际上对应于对特征空间的划分。K 值的选择，距离度量和分类决策是该算法的三个基本要素：
K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别。
距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。
在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离(其中x,y为2个样本，n为维度，x(k),y(k)为x，y第k个维度上的特征值。)：
算法描述
计算步骤：
- 算距离：给定测试对象，计算它与训练集中的每个对象的距离
- 找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻
- 做分类：根据这k个近邻归属的主要类别，来对测试对象分类
算法实现(python)
#coding:utf-8
import numpy
def classify(inX,dataSet,labels,k):
"""
:param inX: example
:param dataSet: dataSet 2D List
:param labels: 1D List
:param k the number of neighbor
:return: The label of the example as classify result.
"""
if len(dataSet) != len(labels):
raise ValueError("DataSet or labels was too less!"
"The length of DataSet is %s"
"But the length of labels is %s"%(len(dataSet),len(labels)))
dArrays = numpy.array(dataSet)
inArray = numpy.array(inX)
result = (((dArrays-inArray)**2).sum(axis=1))**0.5
index_list = result.argsort() #argsort函数返回的是数组值从小到大的索引值
classCount = dict()
for i in range(k):
label = labels[index_list[i]]
classCount[label] = classCount.get(label,0) + 1
return sorted(classCount,key=lambda x:classCount[x],reverse=True)[0]
案例演示
电影分类数据集：
| 电影名称 | 搞笑镜头 | kiss镜头 | 打斗镜头 | 标签 |
|---|---|---|---|---|
| 美人鱼 | 45 | 2 | 9 | 喜剧片 |
| 功夫熊猫3 | 39 | 0 | 31 | 喜剧片 |
| 谍影重重 | 5 | 2 | 57 | 动作片 |
| 叶问3 | 3 | 2 | 65 | 动作片 |
| 怦然心动 | 7 | 46 | 4 | 爱情片 |
| 泰坦尼克号 | 9 | 39 | 8 | 爱情片 |
-
我们构建一个已分好类的数据集
movie_data = {"美人鱼":[45,2,9,"喜剧片"], "功夫熊猫3":[39,0,1,"喜剧片"], "谍影重重":[5,2,57,"动作片"], "叶问3":[3,2,65,"动作片"], "怦然心动":[7,46,4,"爱情片"], "泰坦尼克号":[9,39,8,"爱情片"]} -
计算一个新样本与数据集中所有数据的距离
这里的新样本就是："唐人街探案": [23, 3, 17, "？"]。使用欧氏距离来计算。
x为："唐人街探案": [23, 3, 17, "？"]，y为："谍影重重": [5, 2, 57, "动作片"]，则两者之间的距离为：
d = ((23-5)**2+(3-2)**2+(17-57)**2)**0.5
代码实现：
x = [23, 3, 17] KNN = [] for k,v in movie_data.items(): d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2) KNN.append([k,round(d,2)]) #round为取精度，两位小数。 return KNN #output [["叶问3",52.01],["功夫熊猫3",22.83],["泰坦尼克号",39.66],["美人鱼",23.43],["谍影重重",43.87],["怦然心动",47.69]] -
按照距离大小进行递增排序
KNN.sort(key=lambda dis: dis[1]) #output [["功夫熊猫3",22.83],["美人鱼",23.43],["泰坦尼克号",39.66],["谍影重重",43.87],["怦然心动",47.69],["叶问3",52.01]] 选取距离最小的k个样本
KNN=KNN[:3] #取前3个，K=3
#output
[["功夫熊猫3",22.83],["美人鱼",23.43],["泰坦尼克号",39.66]]-
确定前k个样本所在类别出现的频率，并输出出现频率最高的类别
labels = {"喜剧片":0,"动作片":0,"爱情片":0} for s in KNN: label = movie_data[s[0]] labels[label[3]] += 1 labels =sorted(labels.items(),key=lambda l: l[1],reverse=True) return labels #output {"喜剧片":2,"爱情片":1,"动作片":0} 所以可以把"唐人街探案"这部电影打上喜剧片的标签
算法评估
- KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。
- 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
- 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
行业应用
字符识别、文本分类、图像识别
客户流失预测、欺诈侦测等（更适合于稀有事件的分类问题）
