使用k-近邻算法改进约会网站的配对效果--学习笔记（python3版本）
使用k-近邻算法改进约会网站的配对效果--学习笔记（python3版本）
本文取自《机器学习实战》第二章，原始为python2实现，现将代码移植到python3，且原始代码非常整洁，所以这本书的代码很值得学习一下。
k-近邻算法概述
工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
k-近邻算法的一般流程
1.收集数据：可以使用任何方法
2.准备数据：距离计算所需要的数值，最好是结构化的数据格式
3.分析数据：可以使用任何方法
4.训练算法：此步骤不适于k-近邻算法
5.测试算法：计算错误率
6.使用算法：首先输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后的处理
实现条件
我是在win7操作系统下实现的，使用pycharm。python3.6是用Anaconda。安装包是numpy，Matplotlib。
算法过程
程序1--k-近邻算法
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] #dataSet的行数
diffMat = tile(inX, (dataSetSize,1)) - dataSet #tile（）在行上重复dataSetSize次，列上1次
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(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
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]函数classify0有四个输入，inX代表用于待分类的输入向量，dataSet代表训练样本集，labels代表标签向量，k代表k-近邻的值，一般k值选择小于20.本文采用的是欧式距离，计算完待分类的向量和所有的点之间距离后，对数据排序，然后返回数据标签最大的值。
程序2--将文本记录转换为Numpy的解析程序
def file2matrix(filename):
fr = open(filename)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines)
returnMat = zeros((numberOfLines, 3))
classLabelVector = []
index = 0
for line in arrayOLines:
line = line.strip()
listFromLine = line.split('\t')
returnMat[index, :] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector打开文本文件观察，一共四列。最后一列为标签，如下图：
40920 | 8.326976 | 0.953952 | 3 |
|---|---|---|---|
14488 | 7.153469 | 0.953952 | 2 |
这属于第二步准备数据。函数需要传入一个参数，就是数据文本名字。首先打开，然后一次读取所有的行。计算出数据总共有多少行，构造一个和样本数据行数相同，列为3的矩阵。构造标签列表。然后逐行处理数据，并存入矩阵。这里处理数据是先去掉空格，然后以\t分隔开。
分析数据
>>> import matplotlib
>>> import matplotlib.pyplot as plt
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> ax.scatter(group[:,0], group[:,1], 15*array(labels), array(labels))
>>> plt.show()
如图：
这里采用列1和列2的属性值得到的图，一般来说都是一次一次的试。这里省略前面试的过程，直接采用最佳属性成图。
程序3--归一化特征值
def autoNorm(dataSet):
minVals = dataSet.min(0)#每列最小值
maxVals = dataSet.max(0)#每列最大值
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1))
normDataSet = normDataSet / tile(ranges, (m,1))
return normDataSet, ranges, minVals在函数autoNorm中，将每列的最小值放入minVals中，最大值放入maxVals中，
归一化公式：
newValue = (oldValue - min) / (max - min)
这里采用的是线性函数归一化，将原始数据归一化到[0,1]之间。这样消除特征值之间的量纲的差距。比如在此文中，航程一般都是几千，而消耗的冰淇淋之类一般也就是10以下，如果不归一化处理，航程对分类结果的影响会非常的大，而归一化之后，大家占的比重都差不多。采用线性函数归一化跟选择的距离有关。这里是欧式距离。还有0均值标准化归一。采用不同的距离测量方法在具体考虑不同的归一化方法。
程序4--分类器针对约会网站的测试代码
def datingClassTest():
hoRatio = 0.10
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m * hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m,:],\
datingLabels[numTestVecs:m],3)
print("the classifier came back with: %d,the real anser is: %d"\
% (classifierResult, datingLabels[i]))
if (classifierResult != datingLabels[i]):
errorCount += 1.0
print('the total error rate is : %f ' % (errorCount/float(numTestVecs)))这里其实是步骤5，测试算法。也叫交叉验证，一般用来评判分类器的性能。
函数datingClassTest()函数，先定义用于交叉验证的数据比率。然后读取数据样本，再用autoNorm将数据样本归一化。在取得数据样本的行数。在将具体要作为交叉验证的数据样本值存入numTestVecs中，这里将数据样本的前numTestVecs个样本逐一读取，然后运用k-近邻算法得到算法判定的标签，再跟真实标签做比较。
一般来说交叉验证的数据都是随机取，若人为干预太多则会对分类器的性能判断失误。这里还可以取最后的一段数据来判定。
程序5--约会网站预测函数
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
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?"))
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = array([ffMiles, percentTats, iceCream])
classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
print("you will probably like this person: ", resultList[classifierResult - 1])这段程序主要用来预测，做k-近邻分类器不可能只是对已有的数据进行分类，最主要的就是用来预测没有得到标签的样本数据。而预测结果的真实性，则由刚才的交叉验证的结果来评估。如果刚才交叉验证得到分类器的性能特别的差，那么就需要调整分类算法，或者观察训练样本数据的特征。
预测实验结果如下图：
总结
k-近邻算是比较简单好用的分类算法了，也是这本书的第一个算法。它具有
优点：精度高，对异常值不敏感，无数据输入假定
缺点：计算复杂度高，空间复杂度高其实我们是否可以尝试牺牲一定的精度来降低k-近邻的计算复杂度。就比如说，此文章里面，分成了三类。我将已有的数据样本分别计算三类标签的中心值，预测新的数据标签时，我就计算新进来的数据与三个样本中心值距离，就将数据划分到离它最近的那个中心值那一组。这样就变成了1-近邻分类，这样计算将会降低很多。如果需要提高精度，则将k值取大，但是k值取大之后计算量增加了无数倍。
k-近邻算法必须先对数据分类，然后才能预测。不像其他分类算法，是先训练样本。k-近邻学习起来简单易懂。