1、K-近邻算法（KNN）概述
K-近邻算法采用测量不同特征值之间的距离方法进行分类。
工作原理：存在一个样本数据集合（也称作训练样本集），并且样本集中每个数据都存在标签（即我们知道样本集中每一数据与所属分类的对应关系）。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
例如：电影分类，用K-近邻算法分类爱情片和动作片，假如有一部未看过的电影，如何确定它是爱情片还是动作片？
表1 每部电影的打斗镜头数、接吻镜头数以及电影评估类型
| 电影名称 | 打斗镜头 | 接吻镜头 | 电影类型 |
| California Man | 3 | 104 | 爱情片 |
| He's Not Really into Dudes | 2 | 100 | 爱情片 |
| Beautiful Woman | 1 | 81 | 爱情片 |
| Kevin Longblade | 101 | 10 | 动作片 |
| Robo Slayer 3000 | 99 | 5 | 动作片 |
| Amped II | 98 | 2 | 动作片 |
| ? | 18 | 90 | 未知 |
首先计算未知电影与样本集中其他电影的距离（先忽略如何计算得到这些距离值），如表2
表2 已知电影与未知电影的距离
| 电影名称 | 与未知电影的距离 |
| California Man | 20.5 |
| He's Not Really into Dudes | 18.7 |
| Beautiful Woman | 19.2 |
| Kevin Longblade | 115.3 |
| Robo Slayer 3000 | 117.4 |
| Amped II | 118.9 |
现在按照距离递增排序，可以找到K个距离最近的电影。假定K=3，则三个最靠近的电影依次是He's Not Really into Dudes、Beautiful Woman、California Man。K-近邻算法按照距离最近的三部电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。
2、K-近邻算法的一般流程
（1）收集数据：可以使用任何方法
（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式
（3）分析数据：可以使用任何方法
（4）训练算法：此步骤不适合用于K-近邻算法
（5）测试算法：计算错误率
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K-近邻算法判定输入数据分别属于那个类别，最后应用对计算出的分类执行后续的处理。
3、用python实现kNN算法
首先创建名为kNN.py模块
在kNN.py文件中增加下面代码：
# -*- coding: utf-8 -*-
from numpy import * #引入科学计算包numpyimport operator #经典python函数库，运算符模块。#创建数据集def createDataSet(): group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels=['A','A','B','B'] return group,labels#k-近邻算法核心#inX：用户分类的输入向量，即将对其进行分类#dataSet:训练样本集#labels：标签向量def classifyO(inX,dataSet,labels,k): #距离计算 dataSetSize=dataSet.shape[0] #得到数组的行数，即知道有几个训练数据，这里为4 diffMat=tile(inX,(dataSetSize,1))-dataSet #tile是numpy中的函数，tile将一个数组，扩充成了4个一样的数组；diffMat得到目标与训练数值之间的差值 sqDiffMat=diffMat**2 #各个差值分别平方 sqDistances=sqDiffMat.sum(axis=1) #对平方后的数据求和，sum(axis=1)表示求矩阵的行的和 distances=sqDistances**0.5 #开方，得到距离 sortedDistIndicies=distances.argsort() #对距离进行升序排列 #选择距离最小的k个点 classCount={} for i in range(k): voteIlabel=labels[sortedDistIndicies[i]] #获得前k个距离对应的类标签 classCount[voteIlabel]=classCount.get(voteIlabel,0)+1 #对这些类标签进行统计，求出对应的数量，形成的列表有两列，一列为类标签，一列为数量 #排序 sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) #对上面前k个类标签数量进行排序 return sortedClassCount[0][0] #取最小的距离对应的类标签 在centos中运行（kNN.py在desktop/algorithm/）
#cd algorithm#python>>>import kNN>>>group,labels=kNN.createDataSet()>>>grouparray([[1. , 1.1], [1. , 1. ], [0. , 0. ], [0. , 0.1] ])>>>labels['A','A','B','B']>>>kNN.classifyO([0,0],group,labels,3) #输入[0,0]测试值，测试运行结果'B'
4、kNN算法的优缺点
优点：精度高，对异常数据不敏感（你的类别是由邻居中的大多数决定的，一个异常邻居并不能影响太大），无数据输入假定；
缺点：计算发杂度高（需要计算新的数据点与样本集中每个数据的“距离”，以判断是否是前k个邻居），空间复杂度高（巨大的矩阵）；无法给出任何数据的基础结构信息，无法知晓平均实例样本和典型实例样本具有什么特征。
适用数据范围：数值型（目标变量可以从无限的数值集合中取值）和标称型（目标变量只有在有限目标集中取值）。