k-近邻算法

Posted on | In | Visitors:

学习机器学习实战一书，记录一下。书上原代码都是以Python2版本编写，这边我是用Python3版本，所以会与书上代码有少许不同。

k-近邻算法

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

优缺点

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

工作原理

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

一般流程

  • 收集数据：可使用任何方法
  • 准备数据：数据格式结构化处理
  • 分析数据：任意选择方法
  • 训练算法：此步骤不适用于k-近邻算法
  • 测试算法：计算错误率
  • 使用算法：首先输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理

导入数据

新建Python文件kNN.py，添加数据导入函数：

1
2
3
4
def createDataSet():
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

当然该函数中的四组数据及其标签均是人为假定的，后期可通过读取txt、csv等文件来获取数据。

实现kNN算法

这边采用的是欧氏距离公式来计算两个向量点之间的距离，公式为：
$$
d (x_a, x_b) = \sqrt{\sum_{p} \left( x^p_a - x^p_b \right)^2}
$$
算法的伪代码实现：
对未知类别属性的数据集（测试集）中的每个点依次执行以下操作

  • 计算已知类别数据集（训练集）中的点与当前点之间的距离；
  • 按照距离递增次序排序；
  • 选取与当前点距离最小的k个点；
  • 确定前k个点所在类别的出现频率；
  • 返回前k个点出现频率最高的类别作为当前点的预测分类。

Python代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 分类器实现，参数：输入测试数据、训练集、训练标签、k值
def classify(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]                      # 数据集大小，即训练样本数量
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet  # 计算两矩阵元素级别上的差
    sqDiffMat = diffMat ** 2                            # 所有元素求平方
    sqDistances = sqDiffMat.sum(axis=1)                 # 横轴上所有元素求和   [ 2.21  2.    0.    0.01]
    distances = sqDistances ** 0.5                      # 开根号  [ 1.48660687  1.41421356  0.          0.1       ]
    sortedDistIndicies = distances.argsort()            # 从小到大排序后返回其索引 [2 3 1 0]
    classCount = {}                                     # 空字典，存储前k个数据的标签及其计数
    for i in range(k):                                  # 遍历距离最小的前k个，统计它们的标签数量
        votelabel = labels[sortedDistIndicies[i]]       # 依次获取该数据的标签
        classCount[votelabel] = classCount.get(votelabel, 0) + 1  # 若字典中存在该标签，则在该值上直接加1；若不存在，则先初始化为0，再加1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]                       # 返回降序排序后数量最多的标签的值

注：

  1. dataSet.shape返回的是一个tuple，里面有两个元素，简单来说就是数据集数组的行和列数，也就是数据集的样本数量和单个样本的特征数。
  2. np.tile函数（import numpy as np）：输入按照函数参数右侧的数值或元祖来进行复制扩充自己。
    因此这边代码中np.tile(inX, (dataSetSize, 1))，实际上就是将inX整个数据在纵轴方向上复制扩充了dataSetSize倍，横轴方向上保持1倍，即不变。
    这样使得原数据inX可以与数据集dataSet中每个样本进行相减求差值。
  3. sqDiffMat.sum(axis=1)：对sqDiffMat做求和操作，axis=1表示对列进行操作，但是是以横轴为方向（其实就是行上所有数求和）。所以这边做的是对测试样本与每个训练样本的差值的求和。若axis=0则表示对行进行操作，但是是以列为方向（列方向上所有数求和）。
  4. sortedDistIndicies = distances.argsort()：将distances中的元素从小到大排列，提取其对应的index(索引)，然后输出到sortedDistIndicies。
  5. sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)：classCount.items()返回的是一个列表，其中包含了由键值组成的元祖；operator.itemgetter(1)表示定义一个函数，获取第1个域；reverse=True表示逆序。所以整个sorted()函数做的是对classCount.items()这元祖列表做排序（逆序）操作，这排序的规则是按key来进行的，也就是根据列表中元祖的第1个域（即第2个值）来排序（其实就是根据各个标签的统计数量来降序排序）。

测试分类器

错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。分类器的错误率：分类器给出的错误结果的次数除以测试执行的总数。完美分类器的错误率为0，最差分类器的错误率为1.0。

简单地调用运行：

1
2
3
4
5
6
import kNN
if __name__ == '__main__':
    group, labels = kNN.createDataSet()
    label = kNN.classify([0, 0], group, labels, 3)
    print(label)

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

准备数据

数据文件：datingTestSet2.txt，每个样本（文件中每一行）中主要包含每一个对象的3种特征：每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰激凌公升数，最后一列是标签值：1、2、3，表示喜欢的程度。

在kNN.py文件中添加file2matrix函数，输入为文件名字符串，输出为训练样本矩阵和类标签向量。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def file2matrix(filename):
    with open(filename, 'r') as file:                        # 打开文件
        arrayLines = file.readlines()                        # 读取文件中所有行数据
        numberOfLines = len(arrayLines)                      # 文件行数
        returnMat = np.zeros((numberOfLines, 3))             # 创建返回的矩阵，初始化为0
        classLabelVector = []
        index = 0
        for line in arrayLines:                              # 遍历行
            line = line.strip()                              # 去除回车字符
            listFromLine = line.split('\t')                  # 根据\t划分为列表
            returnMat[index, :] = listFromLine[0:3]          # 获取该行的前3个数据
            classLabelVector.append(int(listFromLine[-1]))   # 获取该样本数据的标签值
            index += 1
    return returnMat, classLabelVector                       # 返回样本数据数组和标签

调用函数，并打印数据：

1
2
3
dataArray, dataLabels = kNN.file2matrix("datingTestSet2.txt")
print(dataArray)
print(dataLabels[:10])

数据打印显示为：

1
2
3
4
5
6
7
8
[[  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]
 ...
 [  2.65750000e+04   1.06501020e+01   8.66627000e-01]
 [  4.81110000e+04   9.13452800e+00   7.28045000e-01]
 [  4.37570000e+04   7.88260100e+00   1.33244600e+00]]
[3, 2, 1, 1, 1, 1, 3, 3, 1, 3]

注：

  1. np.zeros((a, b))创建a行b列的数组，其值全为0
  2. line.split('\t')对字符串按\t做划分操作，得到由多个子字符串组成的列表

归一化处理

因为特征属性飞行常客里程数的数值较大，直接使用欧氏距离的话该属性值会严重影响计算结果。

因此，在处理这种不同取值范围的特征值时，通常采用的方法是将数值归一化，如将取值范围处理为0~1或者-1~1之间。下面公式将任意取值范围的特征值转化为0~1区间内的值：

1
newValue = (oldValue - min) / (max - min)

其中min和max分别是数据集中的最小特征值和最大特征值。

在kNN.py中添加新函数autoNorm()，该函数自动将数字特征值转化为0~1的区间：

1
2
3
4
5
6
7
8
9
def autoNorm(dataSet):
    minValues = dataSet.min(0)                          # 返回数据集中每列上的最小值
    maxValues = dataSet.max(0)                          # 每列上的最大值
    ranges = maxValues - minValues                      # 求差，得数据的范围
    normDataSet = np.zeros(shape=np.shape(dataSet))     # 根据shape创建数组，全为0
    m = dataSet.shape[0]                                # 样本数量
    normDataSet = dataSet - np.tile(minValues, (m, 1))  # 公式
    normDataSet = normDataSet / np.tile(ranges, (m, 1))
    return normDataSet, ranges, minValues

测试算法

在kNN.py中添加测试代码，作为完整程序来验证分类器：

1
2
3
4
5
6
7
8
9
10
11
12
13
def dataClassTest():
    testRatio = 0.20                                          # 定义数据集中为测试样本的比例
    dataSet, dataLabels = file2matrix("datingTestSet2.txt")   # 读取数据
    normMat, ranges, minValues = autoNorm(dataSet)            # 归一化处理
    m = normMat.shape[0]                                      # 样本数量
    numTestVecs = int(m * testRatio)                          # 确定测试样本的数量
    errorCount = 0.0                                          # 错误数量统计
    for i in range(numTestVecs):
        classifierResult = classify(normMat[i, :], normMat[numTestVecs:m, :], dataLabels[numTestVecs:m], 3)  # 传入测试数据、训练集、训练标签、k值
        print("classify: %d, read answer: %d" % (classifierResult, dataLabels[i]))
        if classifierResult != dataLabels[i]:                # 如果预测不正确，则统计加1
            errorCount += 1
    print("total error rate is: %f" % (errorCount / float(numTestVecs)))  # 打印错误率

执行结果显示：

1
2
3
4
5
6
7
8
classify: 3, read answer: 3
classify: 2, read answer: 2
...
...
classify: 2, read answer: 2
classify: 3, read answer: 3
classify: 2, read answer: 2
total error rate is: 0.080000

构建完整系统

1
2
3
4
5
6
7
8
9
10
11
def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']              # 定义三种喜欢程度，对应数据集中标签 1,2,3
    ffMiles = float(input("frequent flier miles earned per year?"))              # 输入每年飞行里程数
    percentTats = float(input("percentage of time spent playing video games?"))  # 输入玩游戏所耗时间百分比
    iceCream = float(input("liters of ice cream consumed per week?"))            # 输入每周消费冰激凌公升数
    dataArray, dataLabels = file2matrix("datingTestSet2.txt")                    # 从txt中获取训练数据
    normMat, ranges, minVals = autoNorm(dataArray)                               # 归一化处理
    inArray = np.array([ffMiles, percentTats, iceCream])                         # 对测试数据处理，整合成数组
    normInArray = (inArray - minVals) / ranges                                   # 对数据做归一化处理
    classifyResult = classify(normInArray, normMat, dataLabels, 3)               # 分类，k=3
    print("you will probably like this person: ", resultList[classifyResult - 1])

只要输入对应特征的值，就可以获得系统的结果判定，运行结果显示：

1
2
3
4
percentage of time spent playing video games?12
frequent flier miles earned per year?30000
liters of ice cream consumed per year?0.5
you will probably like this person:  in large doses

示例：手写识别系统

准备数据

数字图像均已存储为txt形式，里面是由32行32列的0和1数字组成

首先把32x32的二进制图像转换为1x1024的向量，这样就可以用之前的分类器来处理这些数字图像信息了。

1
2
3
4
5
6
7
8
9
# 将图像转为向量
def img2vector(filename):
    returnVector = np.zeros((1, 1024))                       # 初始化0数组，1行1024列
    with open(filename, 'r') as file:                        # 读取文件
        for i in range(32):                                  # 遍历行
            lineStr = file.readline()                        # 读取行
            for j in range(32):                              # 遍历列
                returnVector[0, 32 * i + j] = int(lineStr[j])# 将该行上第j个数据存进数组第i行第j列中
    return returnVector                                      # 返回数组

测试算法

上边我们已将数据处理为分类器可以识别的格式，现在我们将这些数据输入到分类器中，检测分类器的执行效果。

kNN.py中需添加from os import listdir，用于列出给定目录的文件名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def handwritingClassTest():
    hwLabels = []                                        # 列表，存放训练数据集标签
    trainingFileList = listdir("digits/trainingDigits")  # 列出给定目录中的文件名
    m = len(trainingFileList)                            # 训练样本数
    trainingMat = np.zeros((m, 1024))                    # 初始化全0矩阵 m行1024列
    for i in range(m):                                   # 遍历训练数据
        fileNameStr = trainingFileList[i]                # 获取文件名全称，如 3_107.txt
        fileStr = fileNameStr.split('.')[0]              # 根据 . 划分，获取文件名 如 3_107
        classNum = int(fileStr.split('_')[0])            # 根据 _ 划分，获取该文件表示的真实数字 如 3
        hwLabels.append(classNum)                        # 将该数字标签放入训练集标签列表中
        trainingMat[i, :] = img2vector('digits/trainingDigits/%s' % fileNameStr)  # 调用函数，将第i个文件内的内容转化为数组，并存储
    testFileList = listdir("digits/testDigits")     # 列出测试集目录中的文件名
    errorCount = 0.0                                # 错误统计
    mTest = len(testFileList)                       # 测试集大小
    for i in range(mTest):                          # 遍历测试集
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNum = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector("digits/testDigits/%s" % fileNameStr)
        classifyResult = classify(vectorUnderTest, trainingMat, hwLabels, 3)  # 调用函数，预测数字
        print("the classifier: %d, the real value: %d" % (classifyResult, classNum))
        if classifyResult != classNum:
            errorCount += 1.0
    print("total number of errors: %d" % errorCount)
    print("total error rate: %f" % (errorCount / float(mTest)))   # 错误率

调用运行：

1
kNN.handwritingClassTest()

结果显示：

1
2
3
4
5
6
7
8
the classifier: 0, the real value: 0
the classifier: 0, the real value: 0
...
the classifier: 9, the real value: 9
the classifier: 9, the real value: 9
the classifier: 9, the real value: 9
total number of errors: 10
total error rate: 0.010571

小结

本篇主要就是学习k-近邻算法，以及该算法的两个简单实际应用。k-近邻算法必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间。由于必须对数据集中的每个数据计算距离值，实际使用时非常耗时。

代码链接：https://github.com/asdfv1929/MachineLearningInAction_Python3/tree/master/Chapter02_kNN

------------- 本 文 结 束 感 谢 您 的 阅 读 -------------
坚持原创技术分享，您的支持将鼓励我继续创作！
0%