KNN算法

  跟着Udacity课程学完了无人驾驶第一个term，本来想深入研究一下机器视觉，但是视觉方向不能很好地与工作项目契合，所以决定先巩固一下传统机器学习算法。这个系列基于《机器学习实战》和《统计学系方法》展开，既有理论推导，又有代码实例，这样督促自己形成完备的知识体系。

简介

  KNN(k-nearest neighbour)，也成为k近邻算法，是一种最简单实用的机器学习分类算法。该算法本质是通过距离函数在向量间进行相似性检索，从而确定待分类点类别。之所以称之为最简单的分类算法，是因为k近邻算法没有显式的学习过程，其关键参数的含义较其他算法容易理解。

  KNN核心思想是“相近相似”，一般认为两个物体距离越近其关系越紧密，如果两个向量距离很近那么它们两个大概率属于同一类。有很多算法核心思想都是基于这个理论，比如反距离权重差值法等。

算法模型

语言描述

  给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

数学描述

• 输入

  训练数据集
$$T = \lbrace (x_{1},y_{1}),(x_{2},y_{2}),…,(x_{N},y_{N}) \rbrace \tag1$$
其中，$x_{i} \in X \subseteq R^{n}$为实例的特征向量，$ y_{i} \in Y =\lbrace c_{1},c_{2},…,c_{k}\rbrace $为实例类别，$i=1,2,…,N$

• 输出

  实例$x$所属的类$y$

1. 根据给定的距离度量，在训练集$T$中找出与$x$最邻近的$k$个点，涵盖这$k$个点的$x$邻域计作$N_{k}(x)$
2. 在$N_{k}(x)$中根据分类规则，一般为多数表决，来决定$x$的类别$y$：
   $$y=arg\mathop{max}\limits_{c_{j}}\sum_{x_{i} \in N_{k}(x)}I(y_{i}=c_{j}) , i=1,2,…,N, j=1,2,…,K \tag2 $$
   其中，$I$为指示函数，即当$y_{i} = c_{i}$时$I$为1，否则$I$为0。

关键参数

距离度量

  特征空间中两个实例点的距离是两个实例点相似程度的反映，k近邻模型特征空间一般采用$n$维实数向量空间$R^{n}$，使用的距离是欧式距离，除此之外还可以使用其他距离。

闵可夫斯基距离(MinKowski distance)

  闵可夫斯基距离也叫$L_{p}$距离，假设特征空间$X$是$n$维实数向量空间$R^{n}$，$x_{i},x_{j} \in X$，$x_{i} = (x^{1}_{i},x^{2}_{i},…,x^{n}_{i})^{T}$，$x_{j} = (x^{1}_{j},x^{2}_{j},…,x^{n}_{j})^{T}$，则$x_i$，$x_j$的$L_{p}$距离的定义为：
$$L_{p}(x_i,x_j)=(\sum_{l=1}^{n}|x^{(l)}_{i}-x^{(l)}_{j}|^p)^{\frac{1}{p}} \tag3$$

欧式距离

  当闵可夫斯基距离中的参数$p=2$时，称为欧式距离，即
$$L_{2}(x_i,x_j)=(\sum_{l=1}^{n}(x^{(l)}_{i}-x^{(l)}_{j})^2)^{\frac{1}{2}} \tag4$$

曼哈顿距离

  当闵可夫斯基距离中的参数$p=1$时，称为曼哈顿距离，即
$$L_{1}(x_i,x_j)=\sum_{l=1}^{n}|x^{(l)}_{i}-x^{(l)}_{j}|\tag5$$

当$p=\infty$时，是各个坐标距离的最大值，即
$$L_{\infty}(x_i,x_j)= \mathop{max}\limits_{l}|x^{(l)}_{i}-x^{(l)}_{j}|\tag6$$

  其实闵可夫斯基距离的定义与p-范数概念一致，向量的范数可以理解为向量的长度，或者是两个点之间的距离。

$k$值的选择

  k值的选择对k近邻的结果产生较大影响。

• $k=1$

  当$k=1$时，k近邻成为最近邻，只有与输入实例最近的点才会影响预测，即最近的实例点的类别就是输入实例的类别。

• 较小$k$值

  只有与输入实例较近的训练实例才会对结果起作用，预测结果会对临近的实例点非常敏感，如果一旦临近的实例点恰好是噪声，那么预测就会出错。这样做的好处是训练误差会减小，但是估计误差会增大，简而言之就是容易出现过拟合。

• 较大$k$值

  相当于选择较大邻域的训练实例进行预测，这时与输入实例较远的训练实例也会对预测起作用。这么做优点是可以减少估计误差，但是训练误差会增大。

• $k=N$

  当$k=N$时，即k与类别个数一致，那么无论输入实例是什么，都会把输入实例的类别判断为训练实例中类别最多的的类，这样是不对的。

  应用中，$k$值一般取一个比较小的值，通过交叉验证的方式选取最优的k值。

分类决策规则

  k近邻算法的分类决策规则一般采用多数表决，即由输入实例的k个临近的训练实例中的多数类决定输入实例的类别。

多数表决规则(majority voting rule)的数学描述

  如果分类的损失函数为0-1损失函数，分类函数为
$$f:{\bf{R}}^n\to\lbrace c_1,c_2,…,c_K\rbrace \tag7$$
那么误分类的概率是
$$P(Y\not=f(X)) = 1 - P(Y=f(X)) \tag8$$
对给定的实例$x \in X$，其最邻近的$k$个训练实例点构成集合$N_k(x)$，假设输入实例的类别是$c_j$，那么误分类率是：
$$\frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i \not = c_j)=1-\frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i = c_j) \tag9$$
要让误分类率最小，就让$\sum_{x_i \in N_k(x)}I(y_i = c_j)$最大，即$c_j$取个数最多的类别。

python代码示例

  示例为《机器学习实战》手写体的例子

#encoding:utf8
import numpy as np
import glob
import os

#knn算法主体
def knn_classifier(x_train,y_train,x_test,k):
	#计算向量拘留
	dis = distance(x_train,x_test)
	#根据距离排序
	sort_index = dis.argsort()
	classCount = {}
	#取前k个邻近的点
	for i in range(k):
		#获取第i个点的类别
		label = y_train[sort_index[i]]
		classCount[label] = classCount.get(label,0) + 1
	#进行多数表决投票
	classCount = sorted(classCount.items(),lambda x,y:cmp(x[1],y[1]),reverse=True)
	return classCount[0][0]


#欧式距离计算函数
def distance(x_train,x_test):
	datasize = x_train.shape[0]
	#tile可以把一个向量重复叠加为一个矩阵
	diff = np.tile(x_test,(datasize,1)) - x_train
	squareDiff = diff ** 2
	squareSum = squareDiff.sum(axis = 1)
	dis = np.sqrt(squareSum)
	return dis

#把手写体32*32的像素矩阵转化为1*2014的向量
def img2Vector(filename):
	returnVector = np.zeros((1,1024))
	file = open(filename)
	for i in range(32):
		lineString = file.readline()
		for j in range(32):
			returnVector[0,32 * i + j] = int(lineString[j])
	return returnVector


def load_train_data():
	train_data_file_path = glob.glob('./digits/trainingDigits/*.txt')
	train_label = []
	filenum = len(train_data_file_path)
	train_data = np.zeros((filenum,1024))
	for i in range(filenum):
		file_path = train_data_file_path[i]
		label = os.path.basename(file_path).split('_')[0]
		train_label.append(label)
		train_data[i:] = img2Vector(file_path)
	return train_data,train_label

def hand_writing_class_test():
	train_data,train_label = load_train_data()
	test_data_file_path = glob.glob('./digits/testDigits/*.txt')
	error = 0.0
	count = 0
	for file_path in test_data_file_path:
		file = open(file_path)
		test_label = os.path.basename(file.name).split('_')[0]
		test_data = img2Vector(file_path)
		predict_label = knn_classifier(train_data,train_label,test_data,3)
		count += 1
		if predict_label!=test_label:
			print "predict_label: ",predict_label,", test_label: ",test_label
			error += 1
	print 'error rate: ',error/count

def main():
	hand_writing_class_test()

if __name__=='__main__':
	main()

  输出为分类错误的示例类别及最终的分类错误率

predict_label:  1 , test_label:  8
predict_label:  3 , test_label:  8
predict_label:  7 , test_label:  9
predict_label:  9 , test_label:  3
predict_label:  1 , test_label:  8
predict_label:  1 , test_label:  9
predict_label:  1 , test_label:  8
predict_label:  9 , test_label:  3
predict_label:  7 , test_label:  1
predict_label:  6 , test_label:  5
predict_label:  3 , test_label:  5
predict_label:  6 , test_label:  8
error rate:  0.0126849894292
[Finished in 23.7s]

代码示例详见KNN代码示例

总结

  简单介绍了knn算法的基本思想和关键参数，并根据书中的例子进行了实践，过程并不复杂。但是，这个代码示例用穷举法一一计算输入实例与训练数据之间的距离，复杂度较高，缺点比较明显。针对这个问题，下篇文章将介绍kd树方法。

参考

• 统计学习方法，李航，清华大学出版社

• 机器学习实战，Peter Harrington，人民邮电出版社