K近邻（KNN）算法，是学习《机器学习实战》的第一个算法，也是最简单的一个分类方法。它的工作原理：存在一个样本数据集合，也就是训练样本，并且样本集中的每个数据都存在已知的标签，即我们知道数据集中的每个数据与标签的对应关系。现在输入没有标签的新数据，将新数据的每个特征与数据集中的每个数据的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说我们只选择前K个最相似的数据，通常K不大于20，最后选择K个最相似数据中出现次数最多的分类，作为新数据的分类。
其算法的描述：
第一步，计算测试数据与各个训练数据之间的距离
第二步，按照距离的递增关系进行排序
第三步，选取距离最小的K个点
第四步，确定前K个点所在类别的出现频率
第五步，返回前K个点钟出现频率最高的类别作为测试数据的预测分类
下面通过一个图形来直观说明一下：
两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。
如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
k-近邻算法采用裁量不同特征值之间的距离的方法进行分类：
优点：精度高、对于异常不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型
K近邻算法的一般流程：
（1）收集数据：可以使用任何方法
（2）准备数据：距离计算所需要的数值，最好使用结构化的数据格式
============================================================================================================================
在处理不同取值范围的特征值时，通常采用将数值归一化，如将取值范围处理为0到1之间，
newValue=(oldValue-min)/(max-min)
============================================================================================================================
（3）分析数据
（4）训练算法：此步骤不适用于K-近邻算法
（5）测试算法：计算错误率
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于那个分类，最后应用对计算出的分类执行后续的处理。
下面与python实现：
#coding:utf-8 from numpy as np import operator ##给出训练数据以及对应的类别 def createDataSet(): group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]]) labels = ['A','A','B','B'] return group,labels ###通过KNN进行分类 def classify(input,dataSe t,label,k): dataSize = dataSet.shape[0]##说明一下shape给出的是矩阵的行列数，（m,n）[0]：行数 [1]:列数 ####计算欧式距离 diff = np.tile(input,(dataSize,1)) - dataSet###tile函数是复制矩阵，tile(a,n)：把矩阵复制N遍， tile(a,(1,2)):把矩阵a复制成一个一维两遍，即[[a,a]]，tile(a,(2,1)):把矩阵复制为二维的，即[[a],[a]] sqdiff = diff ** 2 squareDist = np.sum(sqdiff,axis = 1)###行向量分别相加，从而得到新的一个行向量 axis=0：列数不变, axis=1:行数不变 dist = squareDist ** 0.5 ##对距离进行排序 sortedDistIndex = np.argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标 classCount={} for i in range(k): voteLabel = label[sortedDistIndex[i]] ###对选取的K个样本所属的类别个数进行统计 classCount[voteLabel] = classCount.get(voteLabel,0) + 1 ###选取出现的类别次数最多的类别 maxCount = 0 for key,value in classCount.items(): if value > maxCount: maxCount = value classes = key return classes if __name__=="__main__": dateset,labels=createDataset() input=np.array([0,0.3]) k=3 output=classify(input,dataset,labels,k) print input print output 如何测试分类器：通过大量的测试数据，我们可以得到分类器的错误率-------分类器给出的错误结果的次数除以测试执行的总数。错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。
======================================================================================================================
