k-近邻算法（改进约会网站的配对效果）

示例背景：

我的朋友海伦一直使用在线约会网站寻找合适自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现曾交往过三种类型的人：

（1）不喜欢的人；

（2）魅力一般的人；

（3）极具魅力的人；

尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类，她觉得可以在周一到周五约会那些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。此外，海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更助于匹配对象的归类。

准备数据：从文本文件中解析数据

海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。海伦的样本主要包括以下3种特征：

1.每年获得的飞行常客里程数；

2.玩视频游戏所耗时间百分比；

3.每周消费的冰淇淋公升数；

在将上述特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式。在kNN.py中创建名为file2matrix的函数，以此来处理输入格式问题。该函数的输入为文本文件名字符串，输出为训练样本矩阵和类标签向量。

分析数据：使用Matplotlib创建散点图

import matplotlib as mpl
import matplotlib.pyplot as plt
import operatordef file2matrix(filename):  #获取数据f = open(filename)arrayOLines = f.readlines()numberOfLines = len(arrayOLines)returnMat = zeros((numberOfLines,3),dtype=float)#zeros(shape, dtype, order),创建一个shape大小的全为0矩阵，dtype是数据类型，默认为float，#order表示在内存中排列的方式（以C语言或Fortran语言方式排列），默认为C语言排列classLabelVector = []rowIndex = 0for line in arrayOLines:line = line.strip()listFormLine = line.split('\t')returnMat[rowIndex,:] = listFormLine[0:3]classLabelVector.append(int(listFormLine[-1]))rowIndex += 1return returnMat, classLabelVectorif __name__ == "__main__":datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')fig = plt.figure()  #图mpl.rcParams['font.sans-serif'] = ['KaiTi']mpl.rcParams['font.serif'] = ['KaiTi']plt.xlabel('玩视频游戏所耗时间百分比')plt.ylabel('每周消费的冰淇淋公升数')'''matplotlib.pyplot.ylabel(s, *args, **kwargs)override = {'fontsize'            : 'small','verticalalignment'   : 'center','horizontalalignment' : 'right','rotation'='vertical' : }'''ax = fig.add_subplot(111) #将图分成1行1列，当前坐标系位于第1块处（这里总共也就1块）ax.scatter(datingDataMat[: ,1], datingDataMat[: ,2],15.0*array(datingLabels), 15.0*array(datingLabels))#scatter是用来画散点图的# scatter（x,y,s=1,c="g",marker="s",linewidths=0）# s:散列点的大小,c:散列点的颜色，marker：形状，linewidths：边框宽度plt.show()

这是简单的创建了一下散点图，可以看到上面的图中还缺少了图例，所以下面的代码以另两列数据为例创建了带图例的散点图，代码大致还是一样的：

from numpy import *
import matplotlib as mpl
import matplotlib.pyplot as plt
import operatordef file2matrix(filename):  #获取数据f = open(filename)arrayOLines = f.readlines()numberOfLines = len(arrayOLines)returnMat = zeros((numberOfLines,3),dtype=float)#zeros(shape, dtype, order),创建一个shape大小的全为0矩阵，dtype是数据类型，默认为float，order表示在内存中排列的方式（以C语言或Fortran语言方式排列），默认为C语言排列classLabelVector = []rowIndex = 0for line in arrayOLines:line = line.strip()listFormLine = line.split('\t')returnMat[rowIndex,:] = listFormLine[0:3]classLabelVector.append(int(listFormLine[-1]))rowIndex += 1return returnMat, classLabelVectorif __name__ == "__main__":datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')fig = plt.figure()  #图plt.title('散点分析图')mpl.rcParams['font.sans-serif'] = ['KaiTi']mpl.rcParams['font.serif'] = ['KaiTi']plt.xlabel('每年获取的飞行常客里程数')plt.ylabel('玩视频游戏所耗时间百分比')'''matplotlib.pyplot.ylabel(s, *args, **kwargs)override = {'fontsize'            : 'small','verticalalignment'   : 'center','horizontalalignment' : 'right','rotation'='vertical' : }'''type1_x = []type1_y = []type2_x = []type2_y = []type3_x = []type3_y = []ax = fig.add_subplot(111) #将图分成1行1列，当前坐标系位于第1块处（这里总共也就1块）index = 0for label in datingLabels:if label == 1:type1_x.append(datingDataMat[index][0])type1_y.append(datingDataMat[index][1])elif label == 2:type2_x.append(datingDataMat[index][0])type2_y.append(datingDataMat[index][1])elif label == 3:type3_x.append(datingDataMat[index][0])type3_y.append(datingDataMat[index][1])index += 1type1 = ax.scatter(type1_x, type1_y, s=30, c='b')type2 = ax.scatter(type2_x, type2_y, s=40, c='r')type3 = ax.scatter(type3_x, type3_y, s=50, c='y', marker=(3,1))'''scatter是用来画散点图的matplotlib.pyplot.scatter(x, y, s=20, c='b', marker='o', cmap=None, norm=None, vmin=None, vmax=None, alpha=None, linewidths=None, verts=None, hold=None,**kwargs)其中，xy是点的坐标，s点的大小maker是形状可以maker=（5，1）5表示形状是5边型，1表示是星型（0表示多边形，2放射型，3圆形）alpha表示透明度；facecolor=‘none’表示不填充。'''ax.legend((type1, type2, type3), ('不喜欢', '魅力一般', '极具魅力'), loc=0)'''loc(设置图例显示的位置)'best'         : 0, (only implemented for axes legends)(自适应方式)'upper right'  : 1,'upper left'   : 2,'lower left'   : 3,'lower right'  : 4,'right'        : 5,'center left'  : 6,'center right' : 7,'lower center' : 8,'upper center' : 9,'center'       : 10,'''plt.show()

准备数据：归一化数值

当我们计算样本之间的欧几里得距离时，由于有些数值较大，所以它对结果整体的影响也就越大，那么小数据的可能就毫无影响了。在这个例子中飞行常客里程数很大，然而其余两列数据很小。为了解决这个问题，需要把数据相应的进行比例兑换，也就是这里需要做的归一化数值，将所有数值转化为[0,1]之间的值。

公式为：
newValue=(oldValue−min)/(max−min)newValue=(oldValue−min)/(max−min) （minmin和maxmax分别是数据集中的最小特征值和最大特征值）

def autoNorm(dataSet): #归一化数值minVals = dataSet.min(0)  #0表示每列的最小值，1表示每行的最小值，以一维矩阵形式返回maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = zeros(shape(dataSet))m = dataSet.shape[0]normDataSet = dataSet - tile(minVals, (m,1))normDataSet = normDataSet/tile(ranges, (m,1))return normDataSet, ranges, minVals

测试并构造完整算法

根据这1000个数据，将其中的100个作为测试数据，另900个作为训练集，看着100个数据集的正确率。

最后根据自己输入的测试数据来判断应该出现的结果是什么。

from numpy import *
import matplotlib as mpl
import matplotlib.pyplot as plt
import operatordef classify0(inX, dataSet, labels, k):dataSetSize = dataSet.shape[0]diffMat = tile(inX, (dataSetSize,1)) - dataSet  #统一矩阵，实现加减sqDiffMat = diffMat**2sqDistances = sqDiffMat.sum(axis=1)  #进行累加，axis=0是按列，axis=1是按行distances = sqDistances**0.5  #开根号sortedDistIndicies = distances.argsort()  #按升序进行排序，返回原下标classCount = {}for i in range(k):voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1  #get是字典中的方法，前面是要获得的值，后面是若该值不存在时的默认值sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)return sortedClassCount[0][0]def file2matrix(filename):  #获取数据f = open(filename)arrayOLines = f.readlines()numberOfLines = len(arrayOLines)returnMat = zeros((numberOfLines,3),dtype=float)#zeros(shape, dtype, order),创建一个shape大小的全为0矩阵，dtype是数据类型，默认为float，order表示在内存中排列的方式（以C语言或Fortran语言方式排列），默认为C语言排列classLabelVector = []rowIndex = 0for line in arrayOLines:line = line.strip()listFormLine = line.split('\t')returnMat[rowIndex,:] = listFormLine[0:3]classLabelVector.append(int(listFormLine[-1]))rowIndex += 1return returnMat, classLabelVectordef autoNorm(dataSet): #归一化数值minVals = dataSet.min(0)  #0表示每列的最小值，1表示每行的最小值，以一维矩阵形式返回maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = zeros(shape(dataSet))m = dataSet.shape[0]normDataSet = dataSet - tile(minVals, (m,1))normDataSet = normDataSet/tile(ranges, (m,1))return normDataSet, ranges, minValsdef datingClassTest(datingDataMat, datingLabels):  #测试正确率hoRatio = 0.1m = datingDataMat.shape[0]numTestVecs = int(hoRatio*m)numError = 0.0for i in range(numTestVecs):classifierResult = classify0(datingDataMat[i,:], datingDataMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)print('The classifier came back with: %d, the real answer is: %d.' %(classifierResult, datingLabels[i]))if (classifierResult != datingLabels[i]):numError += 1print('错误率为 %f' %(numError/float(numTestVecs)))def classifyPerson(datingDataMat, datingLabels, ranges, minVals):result = ['not at all', 'in small doses', 'in large doses']print('请输入相应信息：')percentTats = float(input('percentage of time spent playing video games?'))ffMiles = float(input('frequent flier miles earned per year?'))iceCream = float(input('liters of ice cream consumed per year?'))inArr = array([ffMiles, percentTats, iceCream])classifyResult = classify0((inArr-minVals)/ranges, datingDataMat, datingLabels, 3)print('You will probably like this person: ', result[classifyResult-1])if __name__ == "__main__":datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')datingDataMat, ranges, minVals = autoNorm(datingDataMat) #归一化数值datingClassTest(datingDataMat, datingLabels)classifyPerson(datingDataMat, datingLabels, ranges, minVals)fig = plt.figure()  #图plt.title('散点分析图')mpl.rcParams['font.sans-serif'] = ['KaiTi']mpl.rcParams['font.serif'] = ['KaiTi']plt.xlabel('每年获取的飞行常客里程数')plt.ylabel('玩视频游戏所耗时间百分比')'''matplotlib.pyplot.ylabel(s, *args, **kwargs)override = {'fontsize'            : 'small','verticalalignment'   : 'center','horizontalalignment' : 'right','rotation'='vertical' : }'''type1_x = []type1_y = []type2_x = []type2_y = []type3_x = []type3_y = []ax = fig.add_subplot(111) #将图分成1行1列，当前坐标系位于第1块处（这里总共也就1块）index = 0for label in datingLabels:if label == 1:type1_x.append(datingDataMat[index][0])type1_y.append(datingDataMat[index][1])elif label == 2:type2_x.append(datingDataMat[index][0])type2_y.append(datingDataMat[index][1])elif label == 3:type3_x.append(datingDataMat[index][0])type3_y.append(datingDataMat[index][1])index += 1type1 = ax.scatter(type1_x, type1_y, s=30, c='b')type2 = ax.scatter(type2_x, type2_y, s=40, c='r')type3 = ax.scatter(type3_x, type3_y, s=50, c='y', marker=(3,1))'''scatter是用来画散点图的matplotlib.pyplot.scatter(x, y, s=20, c='b', marker='o', cmap=None, norm=None, vmin=None, vmax=None, alpha=None, linewidths=None, verts=None, hold=None,**kwargs)其中，xy是点的坐标，s点的大小maker是形状可以maker=（5，1）5表示形状是5边型，1表示是星型（0表示多边形，2放射型，3圆形）alpha表示透明度；facecolor=‘none’表示不填充。'''ax.legend((type1, type2, type3), ('不喜欢', '魅力一般', '极具魅力'), loc=0)'''loc(设置图例显示的位置)'best'         : 0, (only implemented for axes legends)(自适应方式)'upper right'  : 1,'upper left'   : 2,'lower left'   : 3,'lower right'  : 4,'right'        : 5,'center left'  : 6,'center right' : 7,'lower center' : 8,'upper center' : 9,'center'       : 10,'''plt.show()

可以看到错误率为5%：