K近邻 Python实现 机器学习实战(Machine Learning in Action)
算法原理
K近邻是机器学习中常见的分类方法之间，也是相对最简单的一种分类方法，属于监督学习范畴。其实K近邻并没有显式的学习过程，它的学习过程就是测试过程。K近邻思想很简单：先给你一个训练数据集D，包括每个训练样本对应的标签。然后给你一个新的测试样本T，问你测试样本的标签预测是什么，K近邻的方法就是找到T到D中每一个样本的相似度，然后根据相似度大小对D中样本排序，取前K个最相似的样本的标签的众数作为测试样本T的标签（即前K个样本投票决定）。具体相似度怎么度量，是根据测试样本到D中每个训练样本的距离度量，一般用的最多的是欧氏距离，也可以更广泛的p范数（欧氏距离是2范数）。
例如：训练数据集D为二位数据，二维图如下图所示：
三种颜色分别代表三种比同类别的标签，现在给你一个新的测试样本T，只要放到图中取计算T到图中各点的距离，然后选取距离最近的K个点来投票决定测试样本属于哪一类（即是什么颜色）
K近邻算法实现
先给出算法实现，再详细解释各函数实现：
from numpy import * import operator
import matplotlibimport matplotlib.pyplot as plot
#########Python做数据处理常用的三个工具包，定义了一些矩阵运算，画图，操作符函数接口######def classify0(inX,dataSet,labels,k): dataSetSize=dataSet.shape[0] #1 diffMat=tile(inX,(dataSetSize,1))-dataSet #2 sqDiffMat=diffMat**2 #3 sqDistances=sqDiffMat.sum(axis=1) #4 distances=sqDistances**0.5 #5 sortedDistIndicies=distances.argsort() #6 classCount={} #7 for i in range(k): voteIlabel=labels[sortedDistIndicies[i]] #8 classCount[voteIlabel]=classCount.get(voteIlabel,0)+1 #9 sortedClasscount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) #10 return sortedClasscount[0][0] #11
--------------------------分割线----------------------------------------
参数注释：第一个参数表示要测试的样本(n维向量)；第二个参数表示训练数据集矩阵（每一行是一个训练样本(m)，每一列是一个坐标维度(n)）；第三个参数是训练数据的样本标签向量(m)；第四个参数K是设置的最近的前K个最近的样本
#1：获取训练样本矩阵的行数(即训练数据集中样本数量)，array.shape 或者shape(array)是numpy库中函数接口，用来读书矩阵的行数和列数(numpy中矩阵一般用多维数组实现)。array.shape[0]表示行，array.shape[1]表示列。
#2 ：tile函数是numpy中的一种类似于扩展函数，对于列表而言，如inX=[1，2，3]
则tile（inX，[2,3]）=[[1,2,3,1,2,3,1,2,3] ,2表示扩展两行，3表示扩展成3列。在这里inX扩展后为
[1,2,3,1,2,3,1,2,3]]
在这里inX扩展后为
,然后减去训练数据矩阵，得到该测试样本与各训练数据的各维度的差值
#3 各维度的差值平方，方便求欧式距离
#4 numpy.sum(axis)是矩阵求和函数，axis=0表示按行求和，axis=1表示按列求和，这里按列求和，得到测试样本点和训练数据样本点在各维度上的差值的平方和
#5得到的矢量每一列开方
#6对distances矢量排序。array.argsort()是numpy中的排序函数，返回的是按顺序的各值在原列表中的索引，如a=[3 5 6 1]
a.argsort()=[3 0 1 2],因为排完序后是[1 3 5 6],对应在原数组中的位置为[3 0 1 2],默认是按升序排序。此函数的具体其他用法请自己参考其它资料，网上很多。
#7字典，用来存储前K个距离最近的训练样本，其中的key存储K个样本的标签，value存储对应的距离。
#8从距离最小的训练样本点开始，把各点的标签存储进key
#9投票，当前训练样本如果是属于某一标签，就把该key值对应的value加1，如果之前还没出现过该标签，则创建该标签key，并设置默认value值为0
#10对字典内的各键值对按值排序，即按各类别的投票数排序，按降序排序，得到排序后的字典sortedClasscount
#11返回字典的第一个键值对的键值，即标签，作为检测样本的预测标签
--------------------------------分割线------------------------------------
机器学习实战中(Machine Learning in Action)的约会对象分类和手写识别源代码和data文件如有需要，可发邮件到[email protected]