k-近邻算法(k-NearestNeighor Algorithm)是采用测量不同特征值之间的距离方法进行分类，简称kNN。
这里用到的距离计算是欧几里德距离。
工作原理：存在一个样本数据集合（,
,...,
,
）i
(0,n)，也称作训练样本集，并且样本集中每条数据都存在标签
，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后(
,
,...,
)，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。
距离计算如下：
然后把d按照从小到大排序，选择k个最相似数据中出现次数中最多的分类，作为新数据的分类。
kNN除了做分类任务，还可以做回归任务，在后面的章节中会讲到。
k-近邻算法的一般流程
(1)收集数据：方法不限
(2)准备数据：距离计算所需要的数值，最好是结构化的数据格式
(3)分析数据：方法不限
(4)训练算法：此步骤不适用于k-近邻算法（不需要训练，直接计算距离，找出距离最近的k个）
(5)测试算法：计算错误率
(6)使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理
所有代码实现都是在python集成的IDLE上完成，创建名为kNN.py的python模块，本节使用的代码都在这个文件中。
'''
KNN是一种最简单最有效的算法，但是KNN必须保留所有的数据集，
如果训练数据集很大，必须使用大量的存储空间，
此外，需要对每一个数据计算距离，非常耗时
另外，它无法给出任何数据的基础结构信息(无法给出一个模型)
'''
from numpy import *
import operator
import matplotlib
import matplotlib.pyplot as plt
from os import listdir
import numpy as np
import matplotlib as mpl
import matplotlib.lines as mlines
#使用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
#每次使用数据，调用该函数即可'''
伪代码
对未知类别属性的数据集中的每个点依此执行以下操作
1、计算已知类别数据集中的点与当前点之间的距离；
2、按照距离递增次序排序；
3、选取与当前点距离最小的k个点；
4、确定前k个点所在的类别的出现频率；
5、返回前k个点出现频率最高的类别作为当前点的预测分类。
'''
#实施kNN分类算法
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=0，是普通的相加，axis=1是将一个矩阵的每一行向量相加
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort()
#sort函数按照数组值从小到大排序
#argsort函数返回的是数组值从小到大的索引值
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
#get(key,k),当字典dic中不存在key时，返回默认值k;存在时返回key对应的值
sortedClassCount = sorted(classCount.items(),
key=operator.itemgetter(1),reverse=True)
#python2中用iteritems，python3中用items代替；operator.itemgetter(k),返回第k个域的值
return sortedClassCount[0][0]#测试KNN
#>>> import KNN
#>>> group,labels = KNN.createDataSet()
#>>> KNN.classify0([0,0],group,labels,3) # B
#>>> KNN.classify0([1.2,1.5],group,labels,3) # A
自行测试~
本节实现了比较简单的k-近邻算法，相信看完会加深对kNN的理解！
欢迎交流~