k近邻算法是机器学习中原理最简单的算法之一，其思想为：给定测试样本，计算出距离其最近的k个训练样本，将这k个样本中出现类别最多的标记作为该测试样本的预测标记。
k近邻算法虽然原理简单，但是其泛华错误率却不超过贝叶斯最有分类器错误率的两倍。所以实际应用中，k近邻算法是一个“性价比”很高的分类工具。
基于欧式距离，用Python3.5实现kNN算法：
主程序：
from numpy import*import operatordef myED(testdata,traindata):""" 计算欧式距离，要求测试样本和训练样本以array([ [],[],...[] ])的形式组织，每行表示一个样本，一列表示一个属性"""size_train=traindata.shape[0] # 训练样本量大小size_test=testdata.shape[0] # 测试样本大小XX=traindata**2sumXX=XX.sum(axis=1) # 行平方和YY=testdata**2sumYY=YY.sum(axis=1) # 行平方和Xpw2_plus_Ypw2=tile(mat(sumXX).T,[1,size_test])+\tile(mat(sumYY),[size_train,1])EDsq=Xpw2_plus_Ypw2-2*(mat(traindata)*mat(testdata).T) # 欧式距离平方distances=array(EDsq)**0.5 #欧式距离return distancesdef mykNN(testdata,traindata,labels,k):""" kNN算法主函数，labels组织成列表形式 """size_test=testdata.shape[0]D=myED(testdata,traindata)Dsortindex=D.argsort(axis=0) # 距离排序，提取序号nearest_k=Dsortindex[0:k,:] # 提取最近k个距离的样本序号label_nearest_k=array(labels)[nearest_k] # 提取最近k个距离样本的标签 label_test=[]if k==1:label_test=label_nearest_kelse:for smp in range(size_test):classcount={}labelset=set(label_nearest_k[:,smp]) # k个近邻样本的标签集合for label in labelset:classcount[label]=list(label_nearest_k[:,smp]).count(label)# 遍历k个近邻样本的标签，并计数，并以字典保存标签和计数结果sortedclasscount=sorted(classcount.items(),\key=operator.itemgetter(1),reverse=True) # 按照计数结果排序label_test.append(sortedclasscount[0][0]) # 提取出现最多的标签return label_test,D
示例：
# 以下示例数据摘自周志华《机器学习》P202表9.1labels=[1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0]traindata=array([[0.6970,0.4600],[0.7740,0.3760],[0.6340,0.2640],\[0.6080,0.3180],[0.5560,0.2150],[0.4030,0.2370],[0.4810,0.1490],\[0.4370,0.2110],[0.6660,0.0910],[0.2430,0.2670],[0.2450,0.0570],\[0.3430,0.0990],[0.6390,0.1610],[0.6570,0.1980],[0.3600,0.3700],\[0.5930,0.0420],[0.7190,0.1030]])testdata=array([[0.3590,0.1880],[0.3390,0.2410],[0.2820,0.2570],\[0.7480,0.2320],[0.7140,0.3460],[0.4830,0.3120],[0.4780,0.4370],\[0.5250,0.3690],[0.7510,0.4890],[0.5320,0.4720],[0.4730,0.3760],\[0.7250,0.4450],[0.4460,0.4590]])k=5label_test,distances=mykNN(testdata,traindata,labels,k)print('\n')print(label_test)
示例结果：
>>[1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
