K近邻算法详解
摘要: K近邻（简称KNN）是一种基于统计的数据挖掘算法，它是在一组历史数据记录中寻找一个或者若干个与当前记录最相似的历史记录的特征值来预测当前记录的未知的特征值，因此具有直观、无需先验统计知识等特点，同时K近邻算法适用于分类和回归两种不同的应用场景，本文主要介绍K近邻算法在回归任务场景下的应用。
avatar
文章概览
K近邻概述
K近邻算法简单直观，下面举一个简单的例子帮助大家理解。在一个城市当，居住着许多不同民族的居民，相同民族的人们大多聚集在一起，形成一个小型的部落。现在你想知道其中一个部落是属于哪个民族的，并且你已经掌握很多关于部落和民族的信息，你会怎么做？其实我们可以通过观察这个部落的人们的生活习惯、节日风俗、衣着服饰等特点，在与我们掌握其他部落的特点进行对比，找出与该部落在这些方面最接近的几个部落（已知这几个部落分别属于哪个民族），如果这几个部落的多数属于哪个民族，那么在很大程度上我们可以猜测该部落可能也属于这个民族，从而得到我们想要的答案。
对于K近邻稍微正式一点的描述是：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最近邻的K个实例，这K个实例的多数属于某个类，就把该输入实例分为这个类。从这段描述中我们可以看出，K近邻算法的学习过程只是简单的存储已知的训练数据，当遇到新的查询实例时，再从存储器中取出一系列相似的实例，用来分类新的查询实例。我们把K近邻算法的这种分类特点称为消极学习方法,具有同样特点的学习算法还有局部加权回归，它的优点在于不是在整个实例空间上一次性的估计目标函数，而是针对每个待分类的新实例做出局部的和相异的估计。而与之对应的分类算法，我们称之为积极学习方法，例如：支持向量机、神经网络等等，它的特点是在新的查询实例到来之前，通过训练实例总结归纳出相似判断的目标函数。
K近邻同样可以应用于回归任务。K近邻做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。而K近邻做回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。由于两者区别不大，虽然本文主要是讲解K近邻的分类方法，但思想对K近邻的回归方法也适用。
K近邻三要素
距离度量
回到刚才那个例子，我们假设从生活习惯、节日风俗、衣着服饰、宗教信仰等多个方面来考察部落之间的相似程度。所谓的相似程度用另外一种说法来表达即差异，差异越小，相似程度越大。在机器学习中，我们使用距离来度量差异。一般情况下我们采用欧式距离来度量差异（其他的距离度量方式如曼哈顿距离等同样适用）。
欧式距离：
刚才说到我们将通过生活习惯、节日风俗、衣着服饰、宗教信仰等多个方面来考察部落之间的相似程度，但是现在我们需要考虑这样一种情况，我们观察发现这些部落虽然在有些方面存在很大的差异，但是这些差异却不能成为区分不同民族的依据，比如说，A和B两个部落都属于C民族，但是A部落信仰D教，B部落信仰E教。也就是说，应用k-近邻的一个实践问题是，实例间的距离是根据实例的所有属性计算的，但是这些属性当中存在着对分类无关的属性，这些无关的属性可能在实例空间中相距很远，这样一来近邻间的距离会被大量的不相关属性所支配。这种由于存在很多不相关属性所导致的难题，有时被称为维度灾难。解决该问题的一个方法是，当计算两个实例间的距离时对每个属性加权，从不断的测试中获得启发，给对分类影响大的属性赋予更高的权值。
K值选择
K值的选择会对K近邻法的结果产生巨大的影响。如果选择较小的K值，学习的近似误差会减小，只有与输入实例较近的训练实例才会对预测结果起作用，这样做存在的问题是预测结果对近邻点过于敏感，如果近邻点恰巧是噪声，预测结果就会出错。如果选择较大的K值，其优点是可以减少学习得估计误差，缺点是与输入实例较远的训练实例也会对预测起作用。K值选择的原则往往是经过大量独立测试数据、多个模型来验证最佳选择。
分类决策规则
K近邻中的分类决策往往是多数表决，即由输入实例的K个近邻的训练实例中的多数类决定输入实例的类。这样的决策规则存在一个问题，假设我们现在已知A、B两个部落属于同一个民族，C、D、E三个部落属于同一个民族。为了测试我们的模型，我们将A部落作为实例，输入到模型中进行测试，K值设为4。经过计算我们发现，得到的K个近邻实例分别为B、C、D、E，并且A、B部落之间的特征距离很小，而A与C、D、E三个部落之间的特征距离很大。但是由于分类决策规则是依据多数进行表决的，所以我们最终会将A判断为与C、D、E部落相同的民族。由此可以看出，多数表决的决策规则是不合理的。解决这一问题的方法是对距离进行加权，B部落与A部落的差异比较小，所以在K个实例当中B部落应该对最终的决策产生更大的影响，而距离越远影响力越小。
K近邻的实现
线性查找
K近邻的核心思想是寻找与输入实例距离最近的K个实例，那么一个最朴素的想法是计算输入实例和所有训练实例之间的距离，然后从中挑选出距离最近的K个实例，这就是线性查找的思想，具体实现如下（大家可以在我的github中找到本文所有的源代码）：
#!/usr/bin/env python
#_*_ coding:utf-8 _*_
#通过直接对k-近邻算法的描述来构建鸢尾花数据集的模型，并利用该模型对鸢尾花类型进行预测
import numpy as np
import random
import operator
from init_data import load_data
def data_split():
"""
data_split函数的主要作用是将原始数据分为训练数据和测试数据，其中训练数据和测试数据的比例为2：1
"""
x_data,y_data = load_data()
x_training = []
x_test= []
y_training = []
y_test = []
for i in range(len(x_data)):
if random.random() > 0.67:
x_training.append(x_data[i])
y_training.append(y_data[i])
else:
x_test.append(x_data[i])
y_test.append(y_data[i])
x_training = np.array(x_training)
y_training = np.array(y_training)
x_test = np.array(x_test)
y_test = np.array(y_test)
return (x_training,x_test,y_training,y_test)
def euclidean_distance(x_training,row):
"""
euclidean_distance函数的主要功能是计算每一条测试数据和训练数据集的欧式距离
:param x_training: 训练数据集
:param row: 一条测试数据
:return: 表示欧式距离的矩阵
"""
dis = np.sum((row - x_training)**2,axis=1)
dis = np.sqrt(dis)
return dis
def predict(dis,y_training,k):
"""
predict函数的主要作用是通过计算所得的欧式距离的集合，从中选取k个距离最小的数据点，统计这k个数据点中各个类别所出现的次数，出现次数最多的类别即为预测值
:param dis: 表示欧式距离的矩阵
:param y_training: 训练数据的类别
:param k: 选取k个距离最近的数据
:return: 预测值
"""
dis_sort = np.argsort(dis)#对欧式距离集合进行排序，返回的dis_sort表示的是排序（从小到大）后的数据在原数组中的索引
statistics = {}#定义字典，用于统计k个数据点中各个类别的鸢尾花出现的次数
for i in range(k):
rank = dis_sort[i]
if y_training[rank] in statistics:
statistics[y_training[rank]] = statistics[y_training[rank]] + 1
else:
statistics[y_training[rank]] = 1
sort_statis = sorted(statistics.items(), key=operator.itemgetter(1), reverse=True)#对statistics字典按照value进行排序（从大到小）
y_predict = sort_statis[0][0]
return y_predict
if __name__ == "__main__":
x_training, x_test, y_training, y_test = data_split()
num = 0
i = 0
for row in x_test:
dis = euclidean_distance(x_training,row)
y_predict = predict(dis,y_training,5)
if y_predict == y_test[i]:
num = num + 1
i = i + 1
print('The accuracy is {0:1f}%'.format(num/i))
空间分割
基于线性查找的思想，存在一个严重的问题是，如果训练集合很大，计算非常耗时，这种方法在实际中难以应用。为了提高K近邻的搜索效率，我们考虑将搜索空间进行分割，通过这种方法来提高搜索效率，减少计算距离的次数。具体的方法有很多，这里主要介绍kd树。
关于kd树的算法和结构定义大家可以参考[《统计学习方法》](https://github.com/yuanliangding/books/blob/master/%E8%AE%A1%E7%AE%97%E6%9C%BA%7C%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD%7C%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/%E7%BB%9F%E8%AE%A1%E5%AD%A6%E4%B9%A0%E6%96%B9%E6%B3%95(%E6%9D%8E%E8%88%AA)和这篇博文,
本文主要关注kd树python实现的一些细节问题。
kd树的生成
- 每次对子空间的划分时，怎样确定在哪个维度上进行划分：在《统计学习方法》中采用的是轮流的方式，即如果这次选择了在第i维上进行数据划分，那下一次就在第j(j≠i)维上进行划分，例如：j = (i mod k) + 1。但是这样忽略了不同属性数据之间的分散程度，有的属性值比较分散，有的属性值比较集中，如果我们以数据分布比较分散的属性作为数据分割的依据，可以更大程度的分割数据，这样更有利于提高搜索的效率。方差可以衡量数据集合的分散程度，所以一般情况下我们采用最大方差分割法对数据集合进行分割。
- 以下是kd树生成算法的python描述，代码标注了详细的解释，可以在我的github中找到完整的代码。
def splitdata(data):
"""
splitdata函数的作用是对输入数据集合进行分割，具体规则：求出方差值最大的那一维特征，然后将整个数据集合根据这一维特征进行排序，中位数为分割点
:param data: 数据集合
:return: 分割数据的属性，数据分割点，分割后两个部分的数据集合
"""
n,m = np.shape(data) #获取numpy矩阵维度
right_data = []
left_data = []
num = 0
row_mean = np.sum(data,axis=0) / n #求矩阵每一列的平均值
row_variance = np.sum((data - row_mean)**2,axis=0) #求矩阵每一列的方差
max_row_variance = np.where(row_variance == np.max(row_variance))[0][0] #方差值最大的那一列的索引
sort_data = np.argsort(data,axis=0) #data矩阵按照列排序，返回排序后的对应的索引
split_row = sort_data[:,max_row_variance] #方差值最大的那一列排序后的索引值
split_index = int(n/2) #中位数
for line in split_row: #将data中的数据分成两个部分，索引排在中位数之前的放进left_data,反之放进right_data
if num > split_index:
if right_data == []:
right_data = data[line,:]
right_data = np.array([right_data])
else: right_data = np.concatenate((right_data,[data[line,:]]),axis=0)
elif num < split_index:
if left_data == []:
left_data = data[line,:]
left_data = np.array([left_data])
else: left_data = np.concatenate((left_data,[data[line,:]]),axis=0)
num = num + 1 #用于计数
split_data = data[split_row[split_index]] #取对应原始数据中的分割点值
print("分割结点为：",split_data,"--------- 分割维度为：",max_row_variance)
return(max_row_variance,split_data,right_data,left_data) #返回值分别为分割数据的属性，数据分割点，分割后两个部分的数据
class KNode(object):
"""
定义节点类
"""
def __init__(self,row = None,point = None,right = None,left = None,parent = None):
self.row = row #分割数据集合的特征
self.point = point #数据分割点
self.right = right #右子树
self.left = left #左子树
def create_tree(dataset,knode):
"""
create_tree函数的主要作用是通过递归的方式来建立kd树
:param dataset: 数据集合
:param knode: 根结点
:return: 返回kd树
"""
length = len(dataset)
if length == 0:
return
row,point,right_data,left_data = splitdata(dataset)
knode = KNode(row,point)
knode.right = create_tree(right_data,knode.right)
knode.left = create_tree(left_data,knode.left)
return knode
kd树的搜索
- kd树的搜索分为两个过程，首先找出包含输入实例的叶子结点，然后在从叶子结点回溯寻找K个近邻实例。在寻找叶子结点的过程中，我们会建立三个列表，一个列表用于存储搜索路径，一个列表用于存储K个近邻点，另外一个列表用于存储K个近邻点所对应的与输入实例的距离，在搜索叶子结点的过程中就计算K近邻点有利于简化回溯过程的搜索。在该过程中，每到达一个结点，我们先将该结点加入搜索路径，然后计算该结点与输入实例之间的距离，如果K近邻点列表中不足K个结点，直接将该结点加入K近邻点列表，同时将计算的距离加入对应的距离列表；如果K近邻列表中已经有K个结点，则选择距离列表中距离最大值与该结点计算的距离进行比较。如果该结点的距离小，则删除最大距离对应的结点，加入该结点，反之无需改变。
- kd树的回溯过程稍微麻烦一点,大家可以参照我给出的代码注释进行理解。在看代码的时候一定要学会去调试，可以帮助我们理解。
def find_KNN(point,kdtree,k):
"""
k近邻查找
:param point: 测试数据点
:param kdtree: 建立好的kd树
:param k: k值
:return: k个近邻点
"""
current = kdtree #当前节点
nodelist = [] #搜索路径
nodek = [] #存储k个近邻点与测试数据点之间的距离
nodek_point = [] #存储k个近邻点对应的值
min_dis = euclidean_distance(point,kdtree.point)
print("---------------------------------------------------------------------------------------")
while current: #找到测试点所对应的叶子结点，同时将搜索路径中的结点进行k近邻判断
nodelist.append(current) #将当前结点加入搜索路径
dis = euclidean_distance(point,current.point)
if len(nodek) < k: #nodek中不足k个结点时，直接将当前结点加入nodek_point
nodek.append(dis)
nodek_point.append(current.point)
print(current.point,"加入k近邻列表")
else: #nodek中有k个结点时，删除距离最大的哪个结点，再将该结点加入nodek_point
max_dis = max(nodek)
if dis < max_dis:
index = nodek.index(max_dis)
print(current.point, "加入k近邻列表;",nodek_point[index],"离开k近邻列表")
del(nodek[index])
del(nodek_point[index])
nodek.append(dis)
nodek_point.append(current.point)
ind = current.row #该结点进行分割时的特征
if point[ind] >= current.point[ind]:
current = current.right
else:
current = current.left
while nodelist: #回溯寻找k近邻
back_point = nodelist.pop()
ind = back_point.row
max_dis = max(nodek)
if len(nodek) < k or abs(point[ind] - back_point.point[ind])<max_dis: #如果nodek_point中存储的节点数少于k个，或者测试数据点和当前结点在分割特征维度上的差值的绝对值小于k近邻中的最大距离
if point[ind] <= back_point.point[ind]: #注意理解这一段判断的代码，因为在之前寻找叶子结点的过程中，我们决定搜索路径的判断方法是大于即搜索右子树，小于即搜索左子树，这里的判断恰恰相反，是为了遍历之前没有搜索的结点
current = back_point.right
else:
current = back_point.left
if current:
nodelist.append(current)
dis = euclidean_distance(point,current.point)
if max_dis > dis and len(nodek) == k:
index = nodek.index((max_dis))
print(current.point, "加入k近邻列表;", nodek_point[index], "离开k近邻列表")
del(nodek[index])
del (nodek_point[index])
nodek.append(dis)
nodek_point.append(current.point)
elif len(nodek) < k:
nodek.append(dis)
nodek_point.append(current.point)
print(current.point, "加入k近邻列表")
return nodek_point
scikit_learn中的K近邻算法
scikit_learn中的K近邻算法的具体解释大家可以参照scikit_learn官网的文档，这里给出一段利用scikit_learn解决鸢尾花数据集的代码。这篇文章中给出的代码都是基于UCI鸢尾花数据集实现的，大家可以比较一下这三种实现方式的预测准确率。
#!/usr/bin/env python
#_*_ coding:utf-8 _*_
#通过sklearn库中所提供的关于k-近邻算法相关的包来实现对鸢尾花数据集的建模与预测
from init_data import load_data
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.cross_validation import train_test_split
x_data,y_data = load_data() #获取数据
x_training,x_test,y_training,y_test = train_test_split(x_data,y_data,random_state=10) #将数据分为训练集和测试集
estimotor = KNeighborsClassifier() #构造k-近邻分类器
estimotor.fit(x_training,y_training) #训练模型
y_predicted = estimotor.predict(x_test) #用训练的模型进行预测
accuracy = np.mean(y_test == y_predicted)*100 #计算预测结果的准确率
print('The accuracy is {0:1f}%'.format(accuracy))
总结
K近邻算法的优点在于
- 算法简单直观，易于实现
- K近邻在进行类别决策时只于少量的相邻样本有关，可以避免样本数量不平衡问题
- K近邻最直接的利用了样本之间的关系，减少了类别特征选择不当对分类结果造成的不利影响，可以最大程度减少分类过程中的误差项
同时K近邻算法存在的问题也很突出
- 当样本数量大、特征多的时候计算量非常大
- 样本不平衡的时候，对稀有类别的预测准确率降低
- 预测速度慢
花了两天的时间找资料、写代码，又花了一天的时间写文章，终于结束了！有一点不太满意的地方是对kd树的回溯没有进行详尽的描述，原因是真的找不出一种好的描述方法，文字描述看起来累，用图表的话工作量太大，大家可以看看我推荐的博文结合代码，理解起来也不会太难。好了，到这里结束了，好好加油，坚持！
