本文核心算法根据[美]Peter Harrington著《Machine Learning in Action(中文版译作“机器学习实战”)》整理。
理论作为铺垫，实战更激动人心。
看书和教程过了一周，终于愿意尝试一下真正的算法实现了，不得不说，这个过程非常愉快。
直接进入正题：k-近邻算法。
一、工作原理
存在一个样本数据集合，也称作训练样本集(Training DataSet)，并且样本集中每个数据都存在标签(Label)，即我们知道样本集中每一数据与所属分类的对应关系。/*回顾监督学习的定义：提供一组“正确答案的数据”。很明显这个算法是监督学习的一种/*
输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，/*后面我们会注意到，这种比较的过程恰恰是整个算法中最耗时的过程/* 然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个相似数据中出现次数最多的分类，作为新数据的分类。
简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。
开发机器学习应用的通用步骤：
收集数据->准备数据(结构化的数据格式，例如矩阵)->分析数据（通常可以使用图表使数据的展示更清晰）->训练算法（将得到的知识存储为计算机可以使用的格式）->测试算法（计算错误率）->使用算法
将k-近邻算法对应到以上通用步骤中，其实只有训练算法这一步是可以省略的，后面我们会讲到原因。
二、实现过程
相关环境
操作系统：macOS Sierra 10.12.3
python版本：Python 2.7.10
扩展包：Numpy Matplotlib
IDE：PyCharm CE
1.导入数据
首先建立工程文件夹，并创建名为kNN.py的文件。之后输入以下代码
# coding=utf-8
from numpy import *
import operator
'''-------------------------创建第一个训练用数据集------------------------------'''
def createDataSet():
group = array([[1.0,1.1],[1.0,1.0],[0.0,0.0],[0,0.1]])
labels = ['A','A','B','B']
return group,labels
'''------------------------测试----------------------------------------------'''
group,labels = createDataSet()
print group
print labels
如果能正常输出结果，则这一步ok。
这一步创建了这样一个训练集合：二维空间中有四个点，坐标分别是(1.0,1.1),(1.0,1.0),(0.0,0.0),(0,0.1)，我们把前两个点标识为A类点，后两个点标识为B类点。
这时我们给出一个未标识的点，如何判定它应该(更可能)是哪类点呢？
2.实施kNN算法
将工作原理中的描述转换成算法。
对未知类别属性的数据集中的每个点一次执行以下操作：
（1）计算已知类别数据中的点雨当前点的距离；
（2）按照距离递增次序排序；
（3）选取与当前点距离最小的k个点；
（4）确定前k个点所在类别的出现频率；
（5）返回前k个点出现频率最高的类别作为当前点的预测分类
'''-------------------------训练算法--------------------------------------------'''
def classify0(inX,dataSet,labels,k):
#inX是未标识的输入向量，dataSet是已知数据集，labels是数据集对应的标识，k即是k-近邻算法中定义的k
dataSetSize = dataSet.shape[0] #shape[0]：读取矩阵第一维的长度，即训练实例的个数
diffMat = tile(inX,(dataSetSize,1)) - dataSet
#tile(A,reps):reps的数字从后往前分别对应A的第N个维度的重复次数
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1) #矩阵第一行元素值求和
distances = sqDistances**0.5
sortedDistIndices = distances.argsort() #返回数组元素值从小到大排序的索引值
classCount={} #数据字典
for i in range(k): #选择距离最小的k个点
voteIlabel = labels[sortedDistIndices[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
group,labels = createDataSet()
a = classify0([0,0.2],group,labels,3)
print a
仔细理解这个算法之后，k-近邻的核心思想就掌握了。
在测试算法时我们输入了一个坐标为(0,0.2)的未标识点，显然它应该属于B类点(肉眼目测)。
若执行后发现输出确实如此，则证明这个分类器算法在原理上没有差错。
三、应用：手写数字识别系统
我们先考虑一个问题：一张数字图像包含的信息是十分庞杂的，如何进行结构化？
首先将每个手写数字图像转化成一个32*32的图像(确保每个数字的大小近似以取得较好的效果)，再将图像中笔画经过的像素点记作1，笔画未经过的像素点记作0，保存为一个32行、32列的文本文件，这便可以作为训练集合来输入了。
图书的作者已经在官网上提供了相关训练用例和源码(https://www.manning.com/books/machine-learning-in-action)，这里为了方便我放置了训练集合和测试用例的文本文件的链接(链接: https://pan.baidu.com/s/1jIdVUlw 密码: 5erd)。
把解压得到的两个文件夹放在工程目录下。
在kNN.py的基础上，加入以下代码。（注意在文件头部额外加入from os import listdir）
关于代码里的listdir和split细节可以查看相关函数的用法。
def img2vector(filename): #文本转换为单行矩阵
returnVect = zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
'''测试转换效果，可手动打开文件观察是否一致
testVector = img2vector('testDigits/0_13.txt')
print testVector[0,0:32] #第一行1-32位
'''
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits') #训练列表
m = len(trainingFileList)
trainingMat = zeros((m,1024)) #有多少个文件，就给矩阵多少行
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0]) #获取该训练样本的标签
hwLabels.append(classNumStr) #加入标签
trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr) #将格式化的文本文件加入矩阵
#训练矩阵构造完毕，接下来构造测试矩阵
testFileList = listdir('testDigits')
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
#将测试用矩阵、训练矩阵、标签矩阵和k的设置值传给训练算法
print "the classifier came back with: %d, the real answer is %d" %(classifierResult, classNumStr)
#输出分析值和实际值，并计算学习后的算法错误率
if (classifierResult != classNumStr): errorCount +=1.0
print "\nthe total number of error is: %d" % errorCount
print "\nthe total error rate is: %f" %(errorCount/float(mTest))
handwritingClassTest()
这样，第一个小应用程序就设计好了，希望大家可以看到实现的效果～
测试中一些有趣的现象：
数字1容易被算法识别为7；
数字8被认错的概率最高，5其次；
数字0、4被识别的准确率极高。
另外很明显的一点：k-近邻算法不存在”训练算法”这一步骤，因此它的运行效率很低(每一次运行都需要把测试用例和所有的训练样本全部计算)，用上文应用的例子来说：每个距离计算包括1024个维度的浮点计算，总共执行900次。还需要为所有的训练样本留下大约2.1MB的存储空间，导致k-近邻算法的时间和空间复杂度都很高。 希望在后面的学习中能够找到更优的算法来解决图像处理问题（肯定会有的）。
End.