所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
2.算法实例
有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。我们要做的是给绿色的小圆分类。
如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。
3.算法特点KNN 算法本身简单有效，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
4.算法流程首先计算出已知类别的数据集当中所有点与当前点的距离
然后按照距离的大小按递增次序排列
之后选取与当前点距离最小的n个点
确定出那n个点所在类别出现的频率
最后返回n个点出现频率最高的类别作为当前点的预测分类
书中的k-临近算法，classify()函数有四个输入参数：用于分类的输入向量inX，输入的训练样本集为dataSet，标签向量为labele，最后的参数k表示用于选择最近邻居的数目，其中标签向量的元素数目和矩阵dataSet的行数相同。代码使用欧式距离公式来计算两个向量点之间的距离，计算完成之后对数据按照从小到大的次序排列。然后确定前k个距离最小元素所在额主要分类，将classCount字典分解为元组列表，然后使用程序第二行导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行逆序排列，最后返回发生频率最高的标签。
#书中的knn算法
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] #取得样本的数量
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2 #求得不同维度上距离差值的平方
sqDistances = sqDiffMat.sum(axis=1) #将不同维度上的差值平方进行相加
distances = sqDistances**0.5 #将上一步的结果进行开平方得到距离
sortedDistIndicies = distances.argsort() #将距离的索引进行从小到大的排序
classCount={} #创建一个用于存储前k个点和对应类别的字典
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]] #依次取得前k个点对应的分类
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #使用get函数取得上一步中得到分类的已有得分数，若无则取0，并将结果+1保存至classCount字典内
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) #对结果进行排序
return sortedClassCount[0][0] #返回结果
书中的转换函数，创建一个1*1024的NumPy数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值储存在NumPy数据中，最后返回数组
#书中的测试函数
def img2vector(filename):
returnVect = zeros((1,1024)) #新建并初始化一个初值赋0的矩阵
fr = open(filename) #打开传入文件
for i in range(32):
lineStr = fr.readline() #读取文本文件
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j]) #将32*32的矩阵依次赋值给1*1024的矩阵
return returnVect #返回结果
书中给出的数字识别系统测试代码，错误率在1.2%。改变k的值或者修改函数handwriting-classTest随机选取训练样本或者改变训练样本的数目，都会使得k-临近算法的错误率产生变化。实际使用过程中算法的执行效率不高，原因是需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次。
#书中的测试代码
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) #将32*32转换为1*1024
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) #将32*32转换为1*1024
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) #将转化后的结果丢入kNN分类器
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 errors is: %d' %errorCount) #输入总错误数
print ('nthe total error rate is: %f' %(errorCount/float(mTest))) #输入错误率
上述的函数和代码用于实现手写数字识别，
所作的操作是首先将样本集依次读入，并依其所属的数字分类将他们进行格式转换。完成格式转换后再依次读入测试数据，然后使用kNN分类算法来得出预测值，并与真实值进行比较，最后将不符合的错误结果进行记录，从而得出最终的错误率。
k-临近算法是分类数据最简单有效的算法，是基于实例的学习，在使用算法时必须有接近实际数据的训练样本数据，k-临近算法必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间，此外必须最数据集中每个数据进行距离计算，可能会很耗时间。k-临近算法的另一个缺点是无法给出任何数据的基础结构信息，我们也就无法知晓平均实例样本和典型实例样本有什么特征了。
