最近在学习机器学习实战这本书，学的第一个算法就是K-近邻算法，话不多说，直接步入正题。
一、K-近邻算法概述
简单地说，K-近邻算法采用测量不同特征值之间的距离方法分类。
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型。
二、K-近邻算法的工作原理
官方解释：存在一个样本数据集，也称作训练样本集，并且样本中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数，最后，选择k个最相似的数据中出现次数最多的分类，作为新数据的分类。
我的理解：k-近邻算法就是根据“新数据的分类取决于它的邻居”进行的，比如邻居中大多数都是退伍军人，那么这个人也极有可能是退伍军人。而算法的目的就是先找出它的邻居，然后分析这几位邻居大多数的分类，极有可能就是它本省的分类。
三、K-近邻算法的一般流程
（1）收集数据：可以使用任何方法
（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式
（3）分析数据：可以使用任何方法
（4）训练算法：此步骤不适用于K-近邻算法
（5）测试算法：计算错误率
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理
四、简单的操作实例
1、准备：使用python导入数据
创建KNN.py的python模块，并在python模块中添加以下代码
from numpy import * import operator #导入运算符的包 def creatDataSet(): group = array([[1.0 , 1.1], [1.0 , 1.0], [0 , 0], [0 , 0.1]]) labels = ['A', 'A', 'B', 'B'] return group , labels我们可以简单的测试以下这段代码
>>> group array([[1. , 1.1], [1. , 1. ], [0. , 0. ], [0. , 0.1]]) >>> labels ['A', 'A', 'B', 'B']以上是有四组数据每组数据有两个我们已知的属性或者特征值。上面的 group 矩阵每行包含一个不同的数据，我们可以把它想象为某个日志文件中不同的测量点或者入口。由于人类大脑的限制，我们通常只能可视化处理三维以下的事务。因此为了简单地实现数据可视化，对于每个数据点我们通常只使用两个特征。向量 labels 包含了每个数据点的标签信息， labels 包含的元素个数等于 group 矩阵行数。这里我们将数据点(1, 1.1)定义为类A，数据点(0, 0.1)定义为类B。带有4个数据点的简单例子如下图所示：
2、实施kNN算法
对未知类别属性的数据集中的每个点依次执行以下操作：
（1）计算已知类别数据集中点与当前点之间的距离
（2）按照距离递增次序排序
（3）选取与当前点距离最小的k个点
（4）确定前k个点所在类别出现的频率
（5）返回前k个点出现频率最高的类别作为当前点的预测分类
相关的实现代码如下（仍然填写在kNN.py的python模块中）
def classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape[0] #表示第二维的长度，即行数 diffMat = tile(inX, (dataSetSize, 1)) - dataSet #tile表示铺成与训练集相同的维度 sqDiffMat = diffMat ** 2 sqDistances = sqDiffMat.sum(axis = 1) #sum(axis)指将矩阵的每一行相加 distances = sqDistances ** 0.5 sortedDistIndicies = distances.argsort() #将distances矩阵中的元素排序并返回相应的索引值 classCount = {} #创建一个字典来存储计数 for i in range(k): #K值是自己设置的 voteIlabel = labels[sortedDistIndicies[i]] #把按值大小顺序排列的欧氏距离索引list前k个对应的labels遍历出来 classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #计算前 k个出现的最多的次数 sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True) print(sortedClassCount) return sortedClassCount[0][0] #classCount.items()将classCount字典分解为元组列表 #operator.itemgetter(1)按照第二个元素次序对元组进行排序 #reverse = True是逆序，即按照从大到小的顺序进行排列 import kNN group, labels = kNN.creatDataSet() ank = kNN.classify0([0, 0], group, labels, 3) print('[0 , 0]所对应的类别为：', ank)运行上述代码可得以下结果：
[('B', 2), ('A', 1)] [0 , 0]所对应的类别为： B从运行的结果可以看出[0 , 0]所对应的类别为‘B’类，大家可以改变[0 , 0]为其他值测试输出的结果
3、代码解析
（1）diffMat = tile(inX, (dataSetSize, 1)) - dataSet
tile表示铺成与训练集相同的维度，举个栗子
>>> A = array([1, 2, 3, 4]) >>> A array([1, 2, 3, 4]) >>> tile(A, (2, 1)) array([[1, 2, 3, 4], [1, 2, 3, 4]])（2）sqDistances = sqDiffMat.sum(axis = 1)
sum(axis = 1)指将矩阵的每一行相加，举个栗子
>>> A = array([[1, 2, 3, 4], [0, 2, 4, 1]]) >>> A array([[1, 2, 3, 4], [0, 2, 4, 1]]) >>> A.sum(axis = 1) array([10, 7])（3）sortedDistIndicies = distances.argsort()
将distances矩阵中的元素排序并返回相应的索引值，举个栗子
>>> A = array([-1, 4, 0, 1, 2]) >>> A.argsort() array([0, 2, 3, 4, 1], dtype=int64)（4）sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)
classCount.items()将classCount字典分解为元组列表 operator.itemgetter(1)按照第二个元素次序对元组进行排序 reverse = True是逆序，即按照从大到小的顺序进行排列 举个栗子
>>> import operator >>> dict={} >>> dict['A']=2 >>> dict['B']=1 >>> dict['C']=3 >>> print dict {'A': 2, 'C': 3, 'B': 1} #创建了一个字典，名字为dict >>>Countlabels_max=sorted(dict.iteritems(),key=operator.itemgetter(1),reverse=True)#运行代码 >>> print Countlabels_max [('C', 3), ('A', 2), ('B', 1)] >>> Countlabels_max[0][0]#返回第0个tuple的第0个参数，也就是我最终的结果总结：kNN算法是个相对来说比较简单的算法，我也是初学者，如果有什么理解不到位的地方还请指点改正
