吴裕雄--天生自然python机器学习实战：K-NN算法约会网站好友喜好预测以及手写数字预测分类实验

实验设备与软件环境

硬件环境：内存ddr3 4G及以上的x86架构主机一部

系统环境：windows

软件环境：Anaconda2(64位)，python3.5，jupyter

内核版本：window10.0

实验内容和原理

（1）实验内容：

使用k近邻算法改进约会网站的配对效果。海伦使用约会网址寻找适合自己的约会对象，约会网站会推荐不同的人选。她将曾经交往过的的人总结为三种类型：不喜欢的人、魅力一般的人、极具魅力的人。尽管发现了这些规律，但依然无法将约会网站提供的人归入恰当的分类。使用KNN算法，更好地帮助她将匹配对象划分到确切的分类中。

使用k近邻算法构造使用k-近邻分类器的手写识别系统。需要识别的数字已经使用图形处理软件，处理具有相同的色彩和大小：宽高是32像素*32像素的黑白图像。使用这个手写识别系统，可以更加方便人们手写输入，并且进一步提高手写识别系统识别率。让用户获得更好的手写输入体验。在实验过程中，尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。

（2）实验原理：

kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。

算法步骤：

1. 准备数据，对数据进行预处理

2. 选用合适的数据结构存储训练数据和测试元组

3. 设定参数，如k

4.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列

5. 遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L 与优先级队列中的最大距离Lmax

6. 进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L < Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列。

7. 遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别。

8. 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k 值。

算法优点：

1.简单，易于理解，易于实现，无需估计参数，无需训练；

2. 适合对稀有事件进行分类；

3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。

算法缺点：

该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。

该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

可理解性差，无法给出像决策树那样的规则。

改进策略：

kNN算法因其提出时间较早，随着其他技术的不断更新和完善，kNN算法的诸多不足之处也逐渐显露，因此许多kNN算法的改进算法也应运而生。

针对以上算法的不足，算法的改进方向主要分成了分类效率和分类效果两方面。

分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。

实验过程与结果（可贴图）

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

（1）数据源说明

实验给出的数据源为datingTestSet.txt，共有4列，每一列的属性分别为：① percentage of time spenting playing vedio games；② frequent flied miles earned per year；③ liters of ice cream consumed per year；④ your attitude towars this people。通过分析数据源中的数据，得到规律，从而判断一个人的前三项属性来得出划分海伦对他的态度。

（2）KNN算法原理

对未知属性的某数据集中的每个点一次执行以下操作

计算已知类别数据集中的每一个点和当前点的距离

按照距离递增依次排序

选取与当前点距离最小的k个点

确定k个点所在类别的出现频率

返回k个点出现频率最高的点作为当前点的分类

（3）分析数据

首先使用Mapplotlib制作原始数据的散点图，在jupyter notebook命令行环境中，输入下列命令：

输入效果图如下：下面散点图使用datingDataMat矩阵的第二、第三列数据，分别表示特征值“玩视频游戏所耗时间百分比”和“每周所消费的冰淇淋公升数”。

由于没有使用样本分类的特征值，所以很难从上图中看到有用的数据模式信息。一般来说，会采用彩色或其他的记号来标记不同样本分类，以便更好地理解数据信息。Matplotlib库提供的scatter函数支持个性化标记散点图上的点。重新输入上面的代码如下：

上述代码利用变量datingLabels存储的类标志属性，在散点图上绘制了色彩不等、尺寸不同的点。可以看到与上图类似的散点图。但从上图中，我们很难看出有用的信息，然而由于下图利用颜色及尺寸标识了数据点的属性类别，因而我们基本上可以从下图中看到三个样本分类的局域轮廓：

以上我们使用datingDataMat矩阵的第二和第三列属性来展示数据，虽然也可以区别，但是在下面的图中，采用的是矩阵第一和第二列属性却可以得到更好的展示效果，下面图中清晰地标识了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同。代码及效果图如下：

（4）KNN算法实现
① 利用python实现构造分类器
首先计算欧式距离然后选取距离最小的K个点
代码如下：
def classify0(inMat,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    #KNN的算法核心就是欧式距离的计算，一下三行是计算待分类的点和训练集中的任一点的欧式距离
    diffMat=tile(inMat,(dataSetSize,1))-dataSet
    sqDiffMat=diffMat**2
    distance=sqDiffMat.sum(axis=1)**0.5
    #接下来是一些统计工作
    sortedDistIndicies=distance.argsort()
    classCount={}
    for i in range(k):
        labelName=labels[sortedDistIndicies[i]]
        classCount[labelName]=classCount.get(labelName,0)+1;
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

② 解析数据
输入文件名，将文件中的数据转化为样本矩阵，方便处理
代码如下：
def file2matrix(testFileName,parammterNumber):
    fr=open(testFileName)
    lines=fr.readlines()
    lineNums=len(lines)
    resultMat=zeros((lineNums,parammterNumber))
classLabelVector = []
    index = 0
    for line in arrayOLine:
        line = line.strip()#strip，默认删除空白符（包括'\n', '\r',  '\t',  ' ')
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0: 3]  #选取前3个元素存储到特征矩阵
        classLabelVector.append(int(listFromLine[-1])) #-1表示最后一列元素，如果不用int(),将当做字符串处理
        index += 1
    return returnMat, classLabelVector
返回值为前三列属性被写入到resultMat二维数组中，第四列属性作为标签写入到classLableVector中

③ 归一化数据
不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影 响到数据分析的结果，为了消除指标之间的量纲影响，需要进行 数据标准化处理，使各指标处于同一数量级。
处理过程如下：
def autoNorm(dataSet):
    minVals = dataSet.min(0)  #存放每一列的最小值，min(0)参数0可以从列中选取最小值，而不是当前行最小值
    maxVals = dataSet.max(0)  #存放每一列的最大值
    ranges = maxVals - minVals #1 * 3 矩阵
    normDataSet = zeros(shape(dataSet))   #列
    m = dataSet.shape[0]      #行
    normDataSet = dataSet - tile(minVals, (m, 1))  #tile(A, (row, col))
    normDataSet = normDataSet/tile(ranges, (m, 1))
    return normDataSet, ranges, minVals

④ 测试数据
在利用KNN算法预测之前，通常只提供已有数据的90%作为训练样本，使用其余的10%数据去测试分类器。注意10%测试数据是随机选择的，采用错误率来检测分类器的性能。错误率太高说明数据源出现问题，此时需要重新考虑数据源的合理性。
def datingClassTest(trainigSetFileName,testFileName):
    trianingMat,classLabel=file2Mat(trainigSetFileName,3)
    trianingMat,minVals,ranges=autoNorm(trianingMat)
    testMat,testLabel=file2Mat(testFileName,3)
    testSize=testMat.shape[0]
    errorCount=0.0
    for i in range(testSize):
        result=classify((testMat[i]-minVals)/ranges,trianingMat,classLabel,3)
        if(result!=testLabel[i]):
            errorCount+=1.0
    errorRate=errorCount/(float)(len(testLabel))
    return errorRate;

⑤ 使用KNN算法进行预测
如果第四步中的错误率在课接受范围内，表示可以利用此数据源进行预测。输入前三项属性之后较为准确的预测了分类。
代码如下：
def classifyPerson()
resultList = [‘not at all’,’in small doses’,’in large doses’]
percentTats = float(raw_input(”percentage of time spent playing video games?”))   #玩游戏占用了多少时间
ffMiles = float(raw_input(“frequent flier miles earned video games?”))   #玩游戏赚了多少飞行里程
iceCream = float(raw_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-近邻算构建手写识别系统
实现图像存储在目录trainingDigits中包含了大约2000个例子，每个例子的内容都是一些数字，每个数字大约有200个样本；目录testDigits中包含大约900个测试数据。使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果。这两组的数据是没有重叠的。
为了使用前面两个分类器，现在必须将图像格式化处理为一个向量。将把一个32*32的二进制图像矩阵转换为1*1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。
具体算法的实现如下：
手写识别系统KNN算法实现
① 利用python实现构造分类器
首先计算欧式距离然后选取距离最小的K个点
代码如下：
def classify0(inMat,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    #KNN的算法核心就是欧式距离的计算，一下三行是计算待分类的点和训练集中的任一点的欧式距离
    diffMat=tile(inMat,(dataSetSize,1))-dataSet
    sqDiffMat=diffMat**2
    distance=sqDiffMat.sum(axis=1)**0.5
    #接下来是一些统计工作
    sortedDistIndicies=distance.argsort()
    classCount={}
    for i in range(k):
        labelName=labels[sortedDistIndicies[i]]
        classCount[labelName]=classCount.get(labelName,0)+1;
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

② 解析数据

编写一段函数img2vector，将图像转换为向量：该函数创建1*1024的NumPy数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。具体代码如下：

在jupyter notebook中输入下列命令测试上面的img2vector函数，然后与文本编辑器打开的文件进行比较。具体代码及其输出如下：

输入效果如下：

③ 归一化数据

不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影 响到数据分析的结果，为了消除指标之间的量纲影响，需要进行 数据标准化处理，使各指标处于同一数量级。

但在这个手写识别系统中，每一个图像数据都是二元的数字，所以不需要再另将数据进行归一化处理。

④ 测试数据

在前面现实：改进约会网站的配对效果这一实验时，已经将数据处理成分类器可以识别的格式，现在我们将这些数据输入到分类器，检测分类器的执行效果。下面的代码主要是：自包含函数handwritingClassTest()是测试分类器。但在写入这些代码之前，必须确保将from os import listdir写入到文件的起始部分，这段代码的主要功能是从os模块中导入函数listdir，它可以列出给定目录的文件名。

具体代码如下：

在上面的程序清单中，将trainingDigits目录中的文件内容存储在列表trainingFileList中，然后可以得到目录中有多少文件，并将其存储在变量m中，接着，代码创建一个m行1024列的训练矩阵，该矩阵的行数据存储一个图像。我们可以从文件名中解系分类数字（第一个for循环的作用）。该目录下的文件按照规则命名，如文件9_45.txt的分类是9，它是数字9的第45个实例。然后我们可以将类代码存储在hwLabels向量中，使用前面讨论的img2vector函数载入图像。在下一步中，我们对testDigits目录中的文件执行相似的操作，不同之处是我们并不将这个目录下的文件载入矩阵中，而是使用classify0()函数测试该目录下的每一个文件。由于文件中的值已经在0和1之间，所以不需要上面使用的autoNorm()函数。

在jupyter notebook中输入handwritingClassTest()，测试该函数的输出结果。依赖于机器速度，加载数据集可能需要花费很长的时间，然后函数开始依次测试每个文件。具体的操作情况，如下图所示：

..........................................（篇幅有限）

从上面的输出可以看出：K-邻近算法识别手写数字数据集，错误率为1.2%。改变变量k的值、修改函数handwritingClassTest随机选取训练样本、改变训练样本的数目，都会对k-近邻算法的错误率产生影响。

⑤ 使用KNN算法进行预测

如果第四步中的错误率在课接受范围内，表示可以利用此数据源进行预测。读取一份手写数字二元数据集，使用前面的算法进行预测。

使用的预测文件数据截图如下：

文件8_179.txt具体数据截图如下：

代码如下：

算法输出的结果是：

可以看到：这个预测是数字8，和实际的输入相对应，所以这个手写预测结果是正确的。

操作异常问题与解决方案

1. KNN算法中的K值的大小对分类的影响？

答：K值选取的太小，模型太复杂。K值选取的太大，导致分类模糊。例如：k=1，则表示取距离测试数据距离最近的那一个样本数据的类作为预测数据的类。k=n，表示这个样本数据集中的n个样本数据，那个数据的类别多，那么被预测的数据就那个类别最多的类。

解决方案：

A、可以用Cross Validation。

B、可以用贝叶斯

C、可以用bootstrap

2. 如何理解KNN算法，其是否存在不足？

答：（1）理解：kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

（2）不足：

A、该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。

B、该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

C、可理解性差，无法给出像决策树那样的规则。

实验总结

通过本实验，我主要学习和掌握了： K-NN算法分类的原理及其具体的实现

骤。主要内容包括以下几个方面：

1、更加深入地学习和了解了KNN近邻算法的原理

2、对于python的相关语法和函数的理解和使用更加的透彻和熟练了

3、对于KNN近邻算法的大体的操作步骤，我现在也能够很熟悉地运用了

4、但在实验过程，由于python的版本的不兼容性，在一些函数库及函数的使用方面花费了一定的时间，但最后通过努力，还是将所遇到的问题都很好地解决了

5、通过k-近邻算法改进约会网站的配对效果和构建手写识别系统，在于积累代码编写，系统逻辑思维能力，抽象思维能力等方面，也有所提升。

6、希望通过后期的努力，更进一步地提升自己在机器学习代码编写，算法理解等方面的能力。

最后很感谢老师的指导和他的支持......