第2章 k-近邻算法

    一句话总结：近朱者赤近墨者黑！

    k 近邻算法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k 近邻算法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻算法不具有显式的学习过程。

    k 近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。

    电影可以按照题材分类，那么如何区分 动作片 和 爱情片 呢？

    1. 动作片：打斗次数更多
    2. 爱情片：亲吻次数更多

    基于电影中的亲吻、打斗出现的次数，使用 k-近邻算法构造程序，就可以自动划分电影的题材类型。

    1. 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
    2. 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
      1. 计算新数据与样本数据集中每条数据的距离。
      2. 对求得的所有距离进行排序（从小到大，越小表示越相似）。
      3. 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
    3. 求 k 个数据中出现次数最多的分类标签作为新数据的分类。

    KNN 通俗理解

    给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 k 个实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。

    KNN 开发流程

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

    KNN 算法特点

    1. 优点：精度高、对异常值不敏感、无数据输入假定
    2. 缺点：计算复杂度高、空间复杂度高
    3. 适用数据范围：数值型和标称型

    : https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/2.KNN/kNN.py

    项目概述

    海伦使用约会网站寻找约会对象。经过一段时间之后，她发现曾交往过三种类型的人:

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

    她希望：

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

    现在她收集到了一些约会网站未曾记录的数据信息，这更有助于匹配对象的归类。

    开发流程

    1. 收集数据：提供文本文件
    2. 准备数据：使用 Python 解析文本文件
    3. 分析数据：使用 Matplotlib 画二维散点图
    4. 训练算法：此步骤不适用于 k-近邻算法
    5. 测试算法：使用海伦提供的部分数据作为测试样本。
    6.         测试样本和非测试样本的区别在于：
    7.             测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
    8. 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

    收集数据：提供文本文件

    海伦把这些约会对象的数据存放在文本文件 中，总共有 1000 行。海伦约会的对象主要包含以下 3 种特征：

    • 每年获得的飞行常客里程数
    • 玩视频游戏所耗时间百分比
    • 每周消费的冰淇淋公升数
    1. 40920    8.326976    0.953952    3
    2. 14488    7.153469    1.673904    2
    3. 26052    1.441871    0.805124    1
    4. 75136    13.147394    0.428964    1
    5. 38344    1.669788    0.134296    1

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

    1. def file2matrix(filename):
    2.     """
    3.     Desc:
    4.         导入训练数据
    5.     parameters:
    6.         filename: 数据文件路径
    7.     return: 
    8.         数据矩阵 returnMat 和对应的类别 classLabelVector
    9.     """
    10.     fr = open(filename)
    11.     # 获得文件中的数据行的行数
    12.     numberOfLines = len(fr.readlines())
    13.     # 生成对应的空矩阵
    14.     # 例如：zeros(2，3)就是生成一个 2*3的矩阵，各个位置上全是 0 
    15.     returnMat = zeros((numberOfLines, 3))  # prepare matrix to return
    16.     classLabelVector = []  # prepare labels return
    17.     fr = open(filename)
    18.     index = 0
    19.     for line in fr.readlines():
    20.         # str.strip([chars]) --返回已移除字符串头尾指定字符所生成的新字符串
    21.         line = line.strip()
    22.         # 以 '\t' 切割字符串
    23.         listFromLine = line.split('\t')
    24.         # 每列的属性数据
    25.         returnMat[index, :] = listFromLine[0:3]
    26.         # 每列的类别数据，就是 label 标签数据
    27.         index += 1
    28.     # 返回数据矩阵returnMat和对应的类别classLabelVector
    29.     return returnMat, classLabelVector

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

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

    Matplotlib 散点图

    样本3和样本4的距离：
    \sqrt{(0-67)^2 + (20000-32000)^2 + (1.1-0.1)^2 }

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

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

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

    1. y=(x-MinValue)/(MaxValue-MinValue)　　
    3. 说明：x、y分别为转换前、后的值，MaxValue、MinValue分别为样本的最大值和最小值。　　

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

    1. y=log10(x)　　
    3. 说明：以10为底的对数函数转换。
    7. ![对数函数图像](../images/2.KNN/knn_1.png)

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

    1. y=arctan(x)*2/PI　
    3. 如图：
    5. ![反余切函数图像](../images/2.KNN/arctan_arccot.gif)

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

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

    1. def autoNorm(dataSet):
    2.     """
    3.     Desc:
    4.         归一化特征值，消除特征之间量级不同导致的影响
    5.     parameter:
    6.         dataSet: 数据集
    7.     return:
    8.         归一化后的数据集 normDataSet. ranges和minVals即最小值与范围，并没有用到
    10.     归一化公式：
    11.         Y = (X-Xmin)/(Xmax-Xmin)
    12.         其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。
    13.     """
    14.     # 计算每种属性的最大值、最小值、范围
    15.     minVals = dataSet.min(0)
    16.     maxVals = dataSet.max(0)
    17.     # 极差
    18.     ranges = maxVals - minVals
    19.     normDataSet = zeros(shape(dataSet))
    20.     m = dataSet.shape[0]
    21.     # 生成与最小值之差组成的矩阵
    22.     normDataSet = dataSet - tile(minVals, (m, 1))
    23.     # 将最小值之差除以范围组成矩阵
    24.     normDataSet = normDataSet / tile(ranges, (m, 1))  # element wise divide
    25.     return normDataSet, ranges, minVals

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

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

    kNN 算法伪代码：

    1. 对于每一个在数据集中的数据点：
    2.     计算目标的数据点（需要分类的数据点）与该数据点的距离
    3.     将距离排序：从小到大
    4.     选取前K个最短距离
    5.     选取这K个中最多的分类类别
    6.     返回该类别来作为目标数据点的预测值

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

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

    1. def datingClassTest():
    2.     """
    3.     Desc:
    4.         对约会网站的测试方法
    5.     parameters:
    6.         none
    7.     return:
    8.         错误数
    9.     """
    10.     # 设置测试数据的的一个比例（训练数据集比例=1-hoRatio）
    11.     hoRatio = 0.1  # 测试范围,一部分测试一部分作为样本
    12.     # 从文件中加载数据
    13.     datingDataMat, datingLabels = file2matrix('input/2.KNN/datingTestSet2.txt')  # load data setfrom file
    14.     # 归一化数据
    15.     normMat, ranges, minVals = autoNorm(datingDataMat)
    16.     # m 表示数据的行数，即矩阵的第一维
    17.     m = normMat.shape[0]
    18.     # 设置测试的样本数量， numTestVecs:m表示训练样本的数量
    19.     numTestVecs = int(m * hoRatio)
    20.     print 'numTestVecs=', numTestVecs
    21.     errorCount = 0.0
    22.     for i in range(numTestVecs):
    23.         # 对数据测试
    24.         classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
    25.         print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
    27.     print errorCount

    约会网站预测函数

    1. def classifyPerson():
    2.     resultList = ['not at all', 'in small doses', 'in large doses']
    3.     percentTats = float(raw_input("percentage of time spent playing video games ?"))
    4.     ffMiles = float(raw_input("frequent filer miles earned per year?"))
    5.     iceCream = float(raw_input("liters of ice cream consumed per year?"))
    6.     datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    7.     normMat, ranges, minVals = autoNorm(datingDataMat)
    8.     inArr = array([ffMiles, percentTats, iceCream])
    9.     classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels, 3)
    10.     print "You will probably like this person: ", resultList[classifierResult - 1]

    实际运行效果如下: 

    1. >>> classifyPerson()
    2. percentage of time spent playing video games?10
    3. frequent flier miles earned per year?10000
    4. liters of ice cream consumed per year?0.5
    5. You will probably like this person: in small doses

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

    : https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/2.KNN/kNN.py

    项目概述

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

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

    开发流程

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

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

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

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

    1. def img2vector(filename):
    2.     returnVect = zeros((1,1024))
    3.     fr = open(filename)
    4.     for i in range(32):
    5.         lineStr = fr.readline()
    6.         for j in range(32):
    7.             returnVect[0,32*i+j] = int(lineStr[j])
    8.     return returnVect

    分析数据：在 Python 命令提示符中检查数据，确保它符合要求

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

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

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

    测试算法：编写函数使用提供的部分数据集作为测试样本，如果预测分类与实际类别不同，则标记为一个错误

    1. def handwritingClassTest():
    2.     # 1. 导入训练数据
    3.     hwLabels = []
    4.     trainingFileList = listdir('input/2.KNN/trainingDigits')  # load the training set
    5.     m = len(trainingFileList)
    6.     trainingMat = zeros((m, 1024))
    7.     # hwLabels存储0～9对应的index位置， trainingMat存放的每个位置对应的图片向量
    8.     for i in range(m):
    9.         fileNameStr = trainingFileList[i]
    10.         fileStr = fileNameStr.split('.')[0]  # take off .txt
    11.         classNumStr = int(fileStr.split('_')[0])
    12.         hwLabels.append(classNumStr)
    13.         # 将 32*32的矩阵->1*1024的矩阵
    14.         trainingMat[i, :] = img2vector('input/2.KNN/trainingDigits/%s' % fileNameStr)
    16.     # 2. 导入测试数据
    17.     testFileList = listdir('input/2.KNN/testDigits')  # iterate through the test set
    18.     errorCount = 0.0
    19.     mTest = len(testFileList)
    20.     for i in range(mTest):
    21.         fileNameStr = testFileList[i]
    22.         fileStr = fileNameStr.split('.')[0]  # take off .txt
    23.         classNumStr = int(fileStr.split('_')[0])
    24.         vectorUnderTest = img2vector('input/2.KNN/testDigits/%s' % fileNameStr)
    25.         classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
    26.         print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
    27.         if (classifierResult != classNumStr): errorCount += 1.0
    28.     print "\nthe total number of errors is: %d" % errorCount
    29.     print "\nthe total error rate is: %f" % (errorCount / float(mTest))

    经过上面的介绍我们可以知道， k 近邻算法有 三个基本的要素：

    • k 值的选择

      • k 值的选择会对 k 近邻算法的结果产生重大的影响。
      • 如果选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。
      • 如果选择较大的 k 值，就相当于用较大的邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。
      • 近似误差和估计误差，请看这里：
        • 近似误差越小，对本数据集的预测效果就越好，但是不保证其他数据集的预测效果
        • 估计误差越小，对世界上所有相类似的数据集总体预测效果越好，对本数据集的预测效果不一定越好
      • 特征空间中两个实例点的距离是两个实例点相似程度的反映。
      • k 近邻模型的特征空间一般是 n 维实数向量空间 向量空间 。使用的距离是欧氏距离，但也可以是其他距离，如更一般的 距离，或者 Minkowski 距离。

    • 分类决策规则

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