机器学习实践之K-近邻算法实践学习

本文根据最近学习机器学习书籍 网络文章的情况,特将一些学习思路做了归纳整理,详情如下.如有不当之处,请各位大拿多多指点,在此谢过.

一、k-近邻算法(k-Nearest Neighbor，KNN)概述

1、简言之，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

2、工作原理

存在一个样本数据集合，也称为训练样本集，且样本集中每个数据都存在标签，也就是众所周知样本集中每一数据与所属分类的对应关系。输入没有标签的新数据以后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般情况下，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最终，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

3、k-近邻算法的一般流程

（1） 收集数据：可以使用任何方法。
（2） 准备数据： 距离计算所需要的数值，最好是结构化数据格式。
（3） 分析数据： 可以使用任何方法。
（4） 训练算法： 此步骤不适用K-近邻算法。
（5） 测试算法： 计算错误率。
（6） 使用算法： 首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

4、相关特性

（1）优点： 精度高，对异常值不敏感、无输入假定。

（2）缺点： 计算复杂度高、空间复杂度高。

（3）适用数据范围： 数值型和标称型。

kNN是non-parametric分类器（不做分布形式的假设，直接从数据估计概率密度），是memory-based learning，不适用于高维数据（curse of dimension)，算法复杂度高（可用KD树优化）。另外，k越小越容易过拟合，但是k很大会将分类精度（设想极限情况：k=1和k=N（样本数））。

二、k-近邻场景

我们知道，电影可以按题材分类，但题材本身是如何定义的？由谁来判定某部电影属于哪个题材？即同一题材的电影会具有哪些公共特征？这些都是在做电影分类时一定要搞清楚的问题。这里以动作片和爱情片为例做简要说明。动作片具有哪些公共特征，使得动作片之间非常相似，却明显有别于爱情片？动作片中也可能有接吻镜头，爱情片中也可能存在打斗镜头，所以，不能简单地依靠是否存在打斗或者接吻来判断一部电影的类型。但很明显的是，动作片中的打斗镜头更多、爱情片中的接吻次数更频繁，基于此类场景在一部电影中出现的次数可用来进行电影分类。

有人曾经统计过很多电影的打斗镜头和接吻镜头， 下方图1-1 给出了6部电影的打斗和接吻镜头。假如现在有一部从未看过的电影，你如何判断它属于动作片还是爱情片呢？

图1-1

首先，我们弄清楚这部未知电影中存在多少打斗镜头、多少接吻镜头，图1-1中问号位置是该未知电影出现的镜头数图示，具体见下方表1-1。

表1-1每部电影的打斗镜头数、接吻镜头数及电影评估类型

由图1-1和表1-1，可用将未知电影在图1-1的具体位置标出，利用欧式距离公式，计算出未知电影与样本集中其他电影之间的距离，相见下方表2-2所示。

表2-2 已知电影与未知电影之间的距离

由表2-2所示，显然，如果样本集中所有电影与未知电影之间的距离按照递增排序的话，可以得到k个距离最近的电影，这里假设k=2的话，则未知电影与电影He’s Not Really into Dudes，Beautiful Woman影片类型最为相似，判定未知电影属于爱情片。

三、示例：使用kNN算法优化约会网站的配对效果

特别提醒：有些教材或博客，在代码实现过程中，由于python2.x和python3.x的不同，在实际执行过程中出现语法错误，这里特做提醒，print语句将输出内容一律加上();另外，python3.0版本后用input替换了raw_input，请读者注意。

1、项目概述

海伦在使用约会网站寻找自己的约会对象。总结经验之后，她发现曾交往过的人分三种类型:

• 不喜欢的人
• 魅力一般的人
• 极具魅力的人

她期待：

• 工作日与魅力一般的人约会
• 周末与极具魅力的人约会
• 不喜欢的人则直接排除掉

2、  k-近邻算法开发实现流程

• 收集数据：提供文本文件

•  准备数据：使用 Python 解析文本文件

•  分析数据：使用 Matplotlib 画二维散点图

•  训练算法：此步骤不适用于 k-近邻算法

•  测试算法：使用海伦提供的部分数据作为测试样本。         测试样本和非测试样本的区别在于：             测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。

•  使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。 

3、   准备数据:从文本文件中解析数据

目前,海伦搜集来一些约会对象的数据,并把这些数据存放在文本文件 datingTestSet2.txt中，每个样本数据占据一行,总共有 1000 行。这些样本数据主要包含以下 3 种特征：

• 每年获得的飞行常客里程数
• 玩视频游戏所耗时间百分比
• 每周消费的冰淇淋公升数

而文本文件datingTestSet2.txt的数据格式如下：


40999    9.161978      1.110180      3

15823    0.991725      0.730979      2

35432    7.398380      0.684218      3

53711    12.149747     1.389088      3

64371    9.149678      0.874905      1

9289    9.666576       1.370330      2

准备数据：使用 Python 解析文本文件

将文本记录转换为 NumPy 的解析程序

    def file2matrix(filename):

       """

       Desc:

           导入训练数据

       parameters:

           filename: 数据文件路径

       return:

           数据矩阵 returnMat 和对应的类别 classLabelVector

       """

       fr = open(filename)  

       numberOfLines = len(fr.readlines())  

       returnMat = zeros((numberOfLines, 3))  # prepare matrix to return

       classLabelVector = []  # prepare labels return

       fr = open(filename)

       index = 0

       for line in fr.readlines():  

           line = line.strip()  

           listFromLine = line.split('\t')  

           returnMat[index, :] = listFromLine[0:3]  

           classLabelVector.append(int(listFromLine[-1]))

           index += 1  

       return returnMat, classLabelVector

    datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')

    datingDataMat

array([[  4.09200000e+04,   8.32697600e+00,   9.53952000e-01],

       [  1.44880000e+04,   7.15346900e+00,   1.67390400e+00],

       [  2.60520000e+04,   1.44187100e+00,   8.05124000e-01],

       ...,

       [  6.88460000e+04,   9.97471500e+00,   6.69787000e-01],

       [  2.65750000e+04,   1.06501020e+01,   8.66627000e-01],

       [  4.81110000e+04,   9.13452800e+00,   7.28045000e-01]])

[3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3]

执行如下代码  

    import matplotlib

    import matplotlib.pyplot as plt

    fig = plt.figure()

    ax = fig.add_subplot(111)

    ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels), 15.0*array(datingLabels))

    plt.show()

而下图中采用矩阵的第一和第三列属性得到很好的展示效果，清晰地标识了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同。

5、     准备数据:归一化数值

归一化数据 （归一化是一个让权重变为统一的过程)

样本3和样本4的距离：

归一化特征值，消除特征之间量级不同导致的影响

归一化定义： 我是这样认为的，归一化就是要把你需要处理的数据经过处理后（通过某种算法）限制在你需要的一定范围内。首先归一化是为了后面数据处理的方便，其次是保正程序运行时收敛加快。 方法有如下：

• 线性函数转换，表达式如下：

  y=(x-MinValue)/(MaxValue-MinValue)

  说明：x、y分别为转换前、后的值，MaxValue、MinValue分别为样本的最大值和最小值。

• 对数函数转换，表达式如下：

  y=log10(x)

  说明：以10为底的对数函数转换。

  如图：

• 反余切函数转换，表达式如下：

  y=atan(x)*2/PI

  如图：

• 式(1)将输入值换算为[-1,1]区间的值，在输出层用式(2)换算回初始值，其中和分别表示训练样本集中负荷的最大值和最小值。

在统计学中，归一化的具体作用是归纳统一样本的统计分布性。归一化在0-1之间是统计的概率分布，归一化在-1--+1之间是统计的坐标分布。

    def autoNorm(dataSet):

        """

        Desc:

            归一化特征值，消除特征之间量级不同导致的影响

        parameter:

            dataSet: 数据集

        return:

            归一化后的数据集 normDataSet. ranges和minVals即最小值与范围，并没有用到 

        归一化公式：

            Y = (X-Xmin)/(Xmax-Xmin)

            其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。

        """  

        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))  # element wise divide

        return normDataSet, ranges, minVals

6 、   测试算法

作为完整程序验证分类器

使用海伦提供的部分数据作为测试样本。如果预测分类与实际类别不同，则标记为一个错误。

kNN 分类器针对约会网站的测试代码

    def datingClassTest():

        """

        Desc:

            对约会网站的测试方法

        parameters:

            none

        return:

            错误数

        """  

        hoRatio = 0.1  # 测试范围,一部分测试一部分作为样本  

        datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')  # load data setfrom file  

        normMat, ranges, minVals = autoNorm(datingDataMat)  

        m = normMat.shape[0]  

        numTestVecs = int(m * hoRatio)

        print 'numTestVecs=', numTestVecs

        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 answer is: %d" % (classifierResult, datingLabels[i]))

            if (classifierResult != datingLabels[i]): errorCount += 1.0

        print ("the total error rate is: %f" % (errorCount / float(numTestVecs)))

        print (errorCount)

上面已经在数据上对分类器进行了测试,现在则可以使用这个分类器帮助海伦对于约会对象进行分类,即海伦在网站上找到某人并输入他的信息,该程序会给出她对对方喜欢程度的预测值.

    def clasdifyPerson():

        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 filer miles earned per year?"))

        iceCream = float(raw_input("liters of ice cream consumed per year?"))

        datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')

        normMat, ranges, minVals = autoNorm(datingDataMat)

        inArr = array([ffMils, percentTats, iceCream])

        classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels, 3)

        print ("You will probably like this person: ", resultList[classifierResult - 1])

>>> kNN.classifyPerson()

percentage of time spent playing video games?10

frequent flier miles earned per year?10000

liters of ice cream consumed per year?0.5

You will probably like this person: in small doses

四、   项目案例2: 手写数字识别系统

1、   项目概述

构造一个能识别数字 0 到 9 的基于 KNN 分类器的手写数字识别系统。

需要识别的数字是存储在文本文件中的具有相同的色彩和大小：宽高是 32 像素 * 32 像素的黑白图像。

2、   开发流程

收集数据：提供文本文件。 准备数据：编写函数 img2vector(), 将图像格式转换为分类器使用的向量格式 分析数据：在 Python 命令提示符中检查数据，确保它符合要求 训练算法：此步骤不适用于 KNN 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的          区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，          则标记为一个错误 使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提取          数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统 

收集数据: 提供文本文件

目录  trainingDigits中包含了大约 2000 个例子，每个例子内容如下图所示，每个数字大约有 200 个样本；目录 testDigits中包含了大约 900 个测试数据。

准备数据: 编写函数 img2vector(), 将图像文本数据转换为分类器使用的向量

将图像文本数据转换为向量

    def img2vector(filename):

        returnVect = 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

在 Python 命令行中输入下列命令测试 img2vector 函数，然后与文本编辑器打开的文件进行比较:

>>> testVector = kNN.img2vector('testDigits/0_13.txt')

>>> testVector[0,0:31]

array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])

>>> testVector[0,31:63]

array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])

训练算法：此步骤不适用于 KNN

因为测试数据每一次都要与全量的训练数据进行比较，所以这个过程是没有必要的。

def handwritingClassTest():  

    hwLabels = []

    trainingFileList = listdir('trainingDigits')  # load the training set

    m = len(trainingFileList)

    trainingMat = zeros((m, 1024))  

    for i in range(m):

        fileNameStr = trainingFileList[i]

        fileStr = fileNameStr.split('.')[0]  # take off .txt

        classNumStr = int(fileStr.split('_')[0])

        hwLabels.append(classNumStr)

        # 将 32*32的矩阵->1*1024的矩阵

        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)  

    testFileList = listdir('testDigits')  # iterate through the test set

    errorCount = 0.0

    mTest = len(testFileList)

    for i in range(mTest):

        fileNameStr = testFileList[i]

        fileStr = fileNameStr.split('.')[0]  # take off .txt

        classNumStr = int(fileStr.split('_')[0])

        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)

        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)

        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)))

五、   K-近邻算法小结

截至目前,我们做一总结,k-近邻算法必须保存全部数据集,如果训练数据集很大,必须使用大量的存储空间.由于必须对数据集中的每个数据计算距离值,实际使用时可能非常耗时.此外,k-近邻还有以缺陷是它没办法给出任何数据的基础结构信息,也就无法得知平均实例样本和典型实例样本有哪些特征.而要解决这个问题,需要使用概率测量方法来处理.

k 近邻算法有 三个基本的要素：

• k 值的选择

  • k 值的选择会对 k 近邻算法的结果产生重大的影响。
  • 如果选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。
  • 如果选择较大的 k 值，就相当于用较大的邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。
  • 近似误差和估计误差，请看这里：https://www.zhihu.com/question/60793482

• 距离度量

  • 特征空间中两个实例点的距离是两个实例点相似程度的反映。
  • k 近邻模型的特征空间一般是 n 维实数向量空间 。使用的距离是欧氏距离，但也可以是其他距离，如更一般的 距离，或者 Minkowski 距离。

• 分类决策规则

  • k 近邻算法中的分类决策规则往往是多数表决，即由输入实例的 k 个邻近的训练实例中的多数类决定输入实例的类。