机器学习实战（一）—— k - 近邻算法

一、前言

当我们想看电影而又不知道看啥电影的时候，通常会选择一些分类标签，例如想看哪个国家的，想看什么类型的等等。因此，我们可以发现，电影是可以按照题材分类的。但具体又是怎么分类的呢？比如动作片的电影有哪些相似之处呢？与爱情片有什么区别呢？动作片中有打斗场景，但爱情片中也有打斗场景啊。但我们可以发现，动作片中的打斗场景明显多于爱情片的打斗场景。因此，我们可以通过电影中某一场景出现的次数来判断其类型。

本文将基于电影中的打斗次数、亲吻次数，使用 k-近邻算法构造分类器，自动划分电影的题材类型。

二、k-近邻算法概述

简单的说，k-近邻算法通过测量不同特征之间的距离并进行比较得到分类结果。

其工作原理如下：

对于一个给定的训练集，我们知道训练样本中的每组数据特征及其分类标签。然后输入没有标签的新数据，将新数据的每个特征与训练集中的每个特征进行比较，选取特征最相似（最近邻）的分类标签，一般来说，我们只选取前 k 个最相似的分类标签，这也是 k-近邻算法中 k 的由来，通常 k 不超过 20。最后，选择 k 个数据中出现次数最多的分类标签作为新数据的分类结果。

回到刚刚电影题材分类问题，使用 k-近邻算法进行题材分类的过程如下所示：

首先我们需要训练集以及题材未知的电影中出现的打斗和接吻次数，如图 2-1 所示：

2-1

下面，我们将计算未知电影与训练样本中其他电影的距离，我们暂时不关心如何计算这些距离，之后会学习。

得到的距离如 2-2 所示：

2-2

假定 k = 3，根据 k- 近邻算法的定义，该电影的题材将被判定为爱情片。这就是 k-近邻算法的大致过程。

三、实战环节 -- 使用 k-近邻算法改进约会网站配对效果

海伦一直在在线约会网站寻找合适的约会对象，尽管网站会推荐不同的人，但她并没有从中找到喜欢的人。海伦的所有约会对象，大概可以分为三类：

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

海伦希望我们的分类软件可以很好的帮助她将匹配对象划分到确切的分类中。经过一段时间的数据收集，她把数据放在了 datingTestSet.txt 中，每个样本数据占一行，共 1000 行，每个样本数据包含以下三种特征：

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

1. 加载数据集，把普通文本文件转化为 Python 矩阵并将分类标签数字化

import numpy as np
import matplotlib.pyplot as plt
import operator
'''
函数说明：加载数据集，将文本文件转换为矩阵
参数：filename -- 文件名
返回值：returnMat -- 数据特征
        classLabelVector - 数据标签
'''
def file2matrix(filename):
    fr = open(filename)
    arrayOlines = fr.readlines()
    numberOfLins = len(arrayOlines)
    # 初始化数据特征矩阵
    returnMat = np.zeros((numberOfLins,3))
    #初始化数据标签
    classLabelVector = []
    index = 0
    for line in arrayOlines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        if listFromLine[-1] == 'largeDoses':
            classLabel = 3
        elif listFromLine[-1] == 'smallDoses':
            classLabel = 2
        elif listFromLine[-1] == 'didntLike':
            classLabel = 1
        classLabelVector.append(classLabel)
        index += 1
    return returnMat,classLabelVector
returnMat,classLabelVector = file2matrix('D:/py_work/data/chapter2-knn/dating/datingTestSet.txt')
# print(returnMat)
# print(classLabelVector[0:20])

执行结果为：

加载数据集

我们已经从文本文件中导入了数据，但这种方式不是特别的直观，接着让我们用图形化的方式展示数据。

2. 可视化数据集

'''
函数说明:可视化数据集
参数：dataMat -- 只含特征的数据集
      datingLabels -- 数据集标签
返回值：无
'''
def showData(dataMat,datingLabels):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    #展示第二列、第三列特征,并通过颜色区别展示不同标签的数据
    # ax.scatter(dataMat[:,1],dataMat[:,2],15.0*np.array(datingLabels),15.0*np.array(datingLabels))
    ax.scatter(dataMat[:,0],dataMat[:,1],15.0*np.array(datingLabels),15.0*np.array(datingLabels))
    plt.title('datingDataSet')
    plt.xlabel('flight miles')
    plt.ylabel('play games')
    plt.show()

# showData(returnMat,classLabelVector)

执行结果为：

可视化数据集

以上展示了样本类别与每周玩游戏百分比以及每周消耗的冰淇淋公斤数之间的关系，同样的，我们还可以展示样本类别与每周玩游戏的百分比以及每年获得的飞行里程数之间的关系。由于代码类似，所以此处直接展示结果。

可视化数据集2

3. 数据归一化

表2-3

表 2-3 给出了四组样本数据，如果我们想计算样本 3 和样本 4 之间的距离，则有：

样本3 与样本 4 的距离

我们可以发现，上述式子的结果受数值大的特征的影响最大，这么一来这三个特征就会有不一样的权重，但海伦认为这三个特征是同等重要的，因此，我们需要采用数值归一化，如将数值取值范围处理为 0 到 1 或 -1 到 1。下面的公式可以将任意数值的特征值转化为 0 到 1 之间的数值。

数值归一化

'''
函数说明：数值归一化
参数： dataSet --  待归一化的数据集
返回值：normDataSet -- 归一化的数据集
        ranges -- 最大值喝最小值之间的差值
        minVals -- 最小值
'''
def autoNorm(dataSet):
    # 返回值最小的一列数值
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    # 初始化放归一化数据的数组
    normDataSet = np.zeros(np.shape(dataSet))
    #获取待归一化数据集的行数
    m = dataSet.shape[0]
    # 根据归一化公式将数据集中的每个数据都减去最小值
    normDataSet = dataSet - np.tile(minVals,(m,1))
    normDataSet = normDataSet / np.tile(ranges,(m,1))
    return normDataSet,ranges,minVals

normDataSet,ranges,minVals = autoNorm(returnMat)
# print(normDataSet)
# print(ranges)
# print(minVals)

数据归一化结果：

数据归一化结果

4. k-近邻算法

'''
函数说明：k-近邻算法
参数：inX -- 待分类的向量
      dataSet -- 用于训练的数据集
      labels -- 用于训练的数据集标签
      k -- 表示选择最近邻数据的数目
返回值：sortedClassCount[0][0] -- 出现频率最高的数据标签
'''
def classify0(inX,dataSet,labels,k):
    #数据集行数
    dataSetSize = dataSet.shape[0]
    #计算样本件的距离
    diffMat = np.tile(inX,(dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    # 将每行数据的距离求和得到样本间的距离
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    # 将得到的距离从小到大排序，排序的结果为索引
    sortedDistIndicies = distances.argsort()
    # print(sortedDistIndicies)
    #字典统计分类标签出现的次数,index为类别标签，vlaue为出现的次数
    classCount = {}
    for i in range(k):
        # 得到距离最小的数据对应类别标签
        voteIlabel = labels[sortedDistIndicies[i]]
        # 判断 voteIlabel 这个类别是否存在，若存在，则加 1，否则为 0
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    # print(classCount)
    # 根据统计得到的标签出现次数按从大到小的顺序进行排列
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    # print(sortedClassCount)
    # 返回出现次数最多的分类标签
    return sortedClassCount[0][0]

inX = returnMat[0:1]
# print(returnMat[1:])
predClass = classify0(inX,returnMat[1:],classLabelVector,3)
# print('预测分类：',predClass)

执行结果：

k-近邻算法执行结果

5. 代码整合 -- 作为完整程序验证分类器

'''
函数说明：作为完整程序验证分类器
参数：无
返回值：无
'''
def datingClassTest():
    #用于训练的数据比例
    hoRatio = 0.10
    returnMat,classLabelVector = file2matrix('D:/py_work/data/chapter2-knn/dating/datingTestSet.txt')
    normDataSet,ranges,minVals = autoNorm(returnMat)
    m = normDataSet.shape[0]
    numTestVecs = int(m * hoRatio)
    #初始化错误率
    errorCount = 0.0
    for i in range(numTestVecs):
        calssifierResult = classify0(normDataSet[i,:],normDataSet[numTestVecs:m,:],classLabelVector[numTestVecs:m],4)
        print("the classfier came back with:",calssifierResult,"the real answer is:",classLabelVector[i])
        # print("the real answer is:",classLabelVector[i])
        if(classLabelVector[i] != calssifierResult):
            errorCount += 1.0
    # print("the total error rate is：",(errorCount / float(numTestVecs)))


# datingClassTest()

执行结果：

约会数据分类结果

测试时，发现当 k = 3 时，错误率为 5%，而当 k = 4 时，错误率为 3%。因此不同的取值会有不同的结果，没有人知道 k 取什么值时预测结果最好只有不断地尝试才能找到最佳取值。

6. 约会网站预测函数

讲了这么多，我们最终的目的是帮助海伦通过自行输入样本特征信息预测出样本是哪一类？不喜欢的人？魅力值一般的人？还是极具魅力的人？

'''
函数说明：根据用户自行输入的样本特征预测样本类别
参数：无
返回值：无
'''
def classifyPerson():
    resultList = ['not at all','in small doses','in large doses']
    percnetTats = float(input("percentage of time spent playing vedio games?"))
    # 用户自行输入待分类的样本特征
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of iceCream consumes per year?"))
    datingDataMat,datingLabels = file2matrix('D:/py_work/chapter2-knn/data/dating/datingTestSet.txt')
    normMat,ranges,minVals = autoNorm(datingDataMat)
    inArr = np.array([ffMiles,percnetTats,iceCream])
    calssifierResult = classify0((inArr - minVals)/ranges,normMat,datingLabels,3)
    print("You will probably like this person:",resultList[calssifierResult - 1])

# classifyPerson()

运行后，程序会提醒你输入相关数据，输入数据后得到的结果如下：

自输入预测类别

至此，使用 k-近邻算法改进在线约会网站配对效果的任务就完成啦~

四、实战环节 -- 使用 k-近邻算法实现手写识别系统

本小节我们将使用 k-近邻算法构造手写识别分类器。为了简单起见，这里的识别系统只能识别数字 0 到 9。需要识别的数字已经使用图形处理软件，处理成具有相同色彩和大小：即 32 x 32 px 的黑白图像。尽管采用文本形式存储图像不能有效的利用存储空间，但为了方便理解，我们还是将图像转换为文本格式。

1. 数据准备：将图像转换为测试向量

实际图像分别存储在 testDigits 和 trainingDigits内，其中训练集包含了大约 2000 个例子，每个数字大概有 200 个样本；测试集中大约包含 900 个测试数据。

为了使用之前例子的分类器，我们需要将图像转换为一个向量，即将 32 x 32 的图像矩阵转换为 1 x 1024 的向量。

from numpy import *
import numpy as np
import pandas as pd
import dating_match
#从os中导入listfdir 函数，用于列出指定目录的文件名
from os import listdir

'''
函数说明：将32x32的矩阵转换为1x1024的向量
参数：filename -- 待转换数据的文件名
返回值：returnVec -- 转换后的1x1024向量
'''
def image2vector(filename):
    returnVec = np.zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        linestr = fr.readline()
        for j in range(32):
            returnVec[0,32*i+j] = int(linestr[j])
    return returnVec
trainVec = image2vector("D:/py_work/data/chapter2-knn/digits/trainingDigits/0_0.txt")
# print("trainVec[0,0:31]:",trainVec[0,0:31])

矩阵到向量转换结果为：

矩阵到向量转化结果

2. 使用 k-近邻算法识别手写数字

'''
函数说明：使用k-近邻算法识别手写数字
参数：无
返回值：无
'''
def handwritingClassTest():
    # 用于存储数字类别
    hwlabels = []
    #listdir函数用于列出指定目录的文件名
    trainingFileList = listdir('D:/py_work/data/chapter2-knn/digits/trainingDigits')
    m = len(trainingFileList)
    traingingMat = zeros((m,1024))
    for i in range(m):
        # 提取文件名
        fileNameStr = trainingFileList[i]
        fileStr = trainingFileList[i].split(".")[0]
        # 提取文件所描述的数字
        fileClassNum = int(fileStr.split("_")[0])
        hwlabels.append(fileClassNum)
        # 成功将训练数据有32X32数组转换为1024矩阵
        traingingMat[i,:] = image2vector('D:/py_work/data/chapter2-knn/digits/trainingDigits/%s'%fileNameStr)
    testFileList = listdir('D:/py_work/data/chapter2-knn/digits/testDigits')
    errorCount = 0.0
    mTset = len(testFileList)
    for i in range(mTset):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split(".")[0]
        fileClassNum = int(fileStr.split("_")[0])
        vectorUnderTest = image2vector("D:/py_work/data/chapter2-knn/digits/testDigits/%s"%fileNameStr)
        classifierResult = dating_match.classify0(vectorUnderTest,traingingMat,hwlabels,3)
        print("the classifierResult is",classifierResult,"the real answer is",fileClassNum)
        if(classifierResult != fileClassNum):
            errorCount += 1.0
    print("the total errorCount is:",errorCount)
    print("the total errorRate:",errorCount / float(mTset))
    
handwritingClassTest()

执行结果为：

识别手写数字结果

可以看到，使用 k-近邻算法识别手写数字，错误率为 1.2%。但在实际使用这个算法时，其执行效率并不高，因为每判断一个数字，就要进行 2000 次距离计算，而且每个距离计算还包括了 1024 个维度浮点运算，总计要执行 900 次。此外，我们还要为测试向量准备 2MB 的空间。k 决策树就是 k-近邻算法的优化版，可节省大量计算开销。

五、 结语

k-近邻算法是分类数据最简单最有效的算法。但与此同时它也有自己的缺陷：

• 因为 k-近邻算法必须保存所有数据，所以当数据集较大时，必须使用大量的存储空间。
• 因为 k-近邻算法需要对数据集中的每个数据计算距离值，所以在实际使用时可能非常耗时。
• 除了以上两个缺点外，k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，它只能得到待测样本与训练集样本之间的距离。因此我们无法得知平均实例样本和典型实例样本具有什么特征。

之后我们将会学习使用概率测量方法处理分类问题，该方法可以解决 k-近邻算法的第三个缺陷。