k近邻算法作为一个分类算法，他通过计算不同特征值之间的距离来进行分类，它的工作原理是存在一个样本集合作为训练样本集，且每个样本都存在一个标签，此时，输入一个新的样本不存在标签，我们通过计算这个新样本到这些训练样本集的距离，找出k个最靠近的样本，再对这些样本的标签进行统计，数量最多的则为新样本的标签。
这里的距离可以有很多，曼哈顿距离，欧式距离等等，后面的代码都使用欧氏距离，K-NN的伪代码如下：
（1）计算所有已知类别的数据集中的点到新的点的距离。
（2）按照距离进行排序。
（3）选取k个与新的点距离最小的k个点。
（4）计算k个点所在类别的频率。
（5）返回k个点出现频率最高的类别作为当前点的预测分类
下面进行实现：
def distance(target,dataset):length =dataset.shape[0]distances=[]for i in range(length):diff=0for j in range(dataset[i].shape[0]):diff += (dataset[i][j]-target[j])**2distance =diff**0.5distances.append(distance)return distances这里是计算了目标点target到数据集内所有点的距离，并保存在distances的列表中。
def sort_choose_k(distance,labels,k):index =distance.argsort()##选取从小到大排序的索引值class_count={}for i in range(k):vote =labels[index[i]]class_count[vote] =class_count.get(vote,0)+1##这里使用了get方法，利用键来获取值，然后get（）方法两个参数，第一个为键，第二个为初值sorted_class_count = sorted(class_count.items(),key=operator.itemgetter(1),reverse=True)return sorted_class_count[0][0]这里是对距离集进行排序，并选择出前k个。这里得argsort()函数作用于array类型，效果是将数组类型的数据进行升序排序后的索引值进行返回。这里的get()函数适用于dict类型，其中第一个参数为输入的键，后面那个参数为给键的初值。这里的itemgetter()方法是operator运算符模块自带的方法，这里是按照第二个元素的次序对元祖进行排序。
这样子就完成了K-NN算法建立，下面看一下例子。
这里例子是通过k临近算法来改进约会网站的配对效果。
（1）从文本文件中解析数据
这里是从txt文件转换成numpy类型
def turn_to_numpy(file):returnmat=[]labels=[]with open(file=file) as f:for line in f.readlines():line=line.strip()line=line.split('\t')returnmat.append(line[0:3])labels.append(line[-1])returnmat=np.array(returnmat)labels =np.array(labels)return returnmat,labels
returnmat=returnmat.astype('float')这里是通过readlines()方法读取每一行的数据，然后去除空格和左右两边的分隔符，存储在returnmat以及labels中。
这里我们观看数据会发现数据的差异很大，这里需要使用归一化来使数据大小变得统一。其公式为。有了公式就方便我们用代码所实现。
def guiyihua(dataset,target):min_set =dataset.min(axis=0)max_set=dataset.max(axis=0)diff = max_set-min_setnum = dataset.shape[0]diff_set =np.tile(diff,(num,1))min_num_set =np.tile(min_set,(num,1))norm_returnmat =(target-min_num_set)/diffreturn norm_returnmat,diff,min_num_set然后针对数据进行测试。
def datingclasstest():hoRadio=0.1datingDataMat,datingLabels =turn_to_numpy(file)datingDataMat =datingDataMat.astype('float')normmat,ranges,diff =guiyihua(datingDataMat,datingDataMat)m=normmat.shape[0]numtestvecs =int(m*hoRadio)errorCount=0.0for i in range(numtestvecs):classifierresult =sort_choose_k(np.array(distance(normmat[i,:],normmat[numtestvecs:m,:])),datingLabels[numtestvecs:m],3)print("the classifieer came back with {} ,the real answer is :{}".format(classifierresult,datingLabels[i]))if (classifierresult !=datingLabels[i]):errorCount+=1.0print("the total error rate is;{}".format(errorCount/float(numtestvecs)))
这里显示错误率为0.05，其实还不错，然后我们用手写数据再来测试一下。
数据的预处理
import numpy as np
def img2vector(filename):returnvect =np.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这一步将32×32的数据转换为1×1024，这样子就可以让分类器进行处理。
然后进行测试。
import os
import operator
def handwritingtest():hwlabels=[]trainingfilelist=os.listdir('trainingDigits')m=len(trainingfilelist)trainingmat=np.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(r'trainingDigits\{}'.format(filenamestr))testfilelist =os.listdir('testDigits')errorCount=0.0mtest=len(testfilelist)for i in range(mtest):filenamestr=testfilelist[i]filestr=filenamestr.split('.')[0]classnumstr =int(filestr.split('_')[0])vectorundertest=img2vector(r'testDigits\{}'.format(filenamestr))classifierresult=classify0(vectorundertest,trainingmat,hwlabels,3)print("the classifier came back with:{},the real answer is:{}".format(classifierresult,classnumstr))if(classifierresult!=classnumstr):errorCount+=1.0print("the total error rate is:{}".format(errorCount/float(mtest)))
这样子就完成了K近邻算法的手写以及测试
