机器学习实战 | 第2章 k-临近算法

发表于   |   更新于 | 分类于 | | 阅读数
字数统计: 1.8k

==以下代码全部基于python3==

一、k-临近算法概述

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

  2. kNN算法伪代码：
    对未知类别属性的数据集中的每个点依次执行以下操作：
    （1）计算已知类别数据集中的点与当前点之间的距离；
    （2）按照距离递增次序排序；
    （3）选取与当前点距离最小的k个点；
    （4）确定前k个点所在类别的出现频率；
    （5）返回前k个点出现频率最高的类别作为当前点的预测分类。

  3. python3 下kNN算法实现：

    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
    26
    27
    28
    29
    30
    31
    32
    from numpy import *
    import operator 

    def createDataSet():
        group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        labels = ['A','A','B','B']
        return group,labels

    def classify_KNN(test_X, train_set, labels, K):
        rows = train_set.shape[0]
        diff = tile(test_X,(rows,1)) - train_set
        # 这一行利用tile函数将输入样本实例转化为与训练集同尺寸的矩阵
        # 便之后的矩阵减法运算

        # .tile若输入一个二元祖，第一个数表示复制的行数，第二个数表示对inx的重复的次数
        # .shape[0]代表行数，.shape[1]代表列数
       
        sqDistance = (diff ** 2).sum(axis=1)
        Distance = sqDistance ** 0.5
        sorted_Distance = Distance.argsort()
    	# 对每个训练样本与输入的测试样本求欧几里得距离，即点之间的范数
        # 随后按距离由小到大进行排序
        # 当axis为0时,是压缩行,即将每一列的元素相加,将矩阵压缩为一行
        # 当axis为1时,是压缩列,即将每一行的元素相加,将矩阵压缩为一列
        # 如果axis为整数元组（x，y），则是求出axis=x和axis=y情况下得到的和
        
        classCount = {}
        for i in range(K):
            vote_label = labels[sorted_Distance[i]]
            classCount[vote_label] = classCount.get(vote_label,0) +1
            sortedClassCount = sorted(classCount.items() , key = operator.itemgetter(1),reverse=True)
            return sortedClassCount[0][0]

运行：

1
2
3
4
>import kNN
>group,labels = kNN.createDataSet()
>kNN.classify_KNN([0,0],group,labels,3)
'B'
  1. 测试分类器最常用的方法：错误率——分类器给出错误结果的次数除以测试执行的总数。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def file_parse_matrix(filename):
    with open(filename) as fp:
        Arr_lines = fp.readlines()
        number = len(Arr_lines)
        # 初始化数据为m行3列（飞行里程，游戏时间，冰淇淋数）
        # 标签单独创建一个向量保存
        return_mat = zeros((number, 3))
        label_vec = []
        index = 0

        for line in Arr_lines:
            line = line.strip()
            listFromLine = line.split('\t')  # 按换行符分割数据
            # 将文本数据前三行存入数据矩阵，第四行存入标签向量
            return_mat[index, :] = listFromLine[0:3]
            label_vec.append(listFromLine[-1])
            index += 1
    return return_mat, label_vec

运行：

1
2
3
>datingDataMat,datingLabels=kNN.file_parse_matrix('datingTestSet.txt')
>datingDataMat
>>>datingLabels

2. 分析数据：使用 Matplotlib 创建散点图

1
2
3
4
5
6
>import matplotlib
>import matplotlib.pyplot as plt
>fig = plt.figure()
>ax = fig.add_subplot(111)
>ax.scatter(datingDataMat[:,1], datingDataMat[:,2])
>plt.show()

//这段代码运行的时候有一点问题，等待后续更正

3. 准备数据：归一化数值

数值归一化：处理不同取值范围的特征值，如将取值范围处理为0到1或者-1到1之间。
公式：newValue = (oldValue-min)/(max-min)
其中min和max分别是数据集中的最小特征值和最大特征值。
函数Norm_feature()，可以自动将数字特征值转化为0到1的区间：

1
2
3
4
5
6
7
8
9
10
11
def Norm_feature(data_set):
    minVal = data_set.min(0)
    maxVal = data_set.max(0)
    ranges = maxVal - minVal     # 计算极差
    # 下一步将初始化一个与原始数据矩阵同尺寸的矩阵
    # 利用tile函数实现扩充向量，并进行元素间的对位运算
    norm_set = zeros(shape(data_set))
    rows = data_set.shape[0]
    norm_set = (data_set - tile(minVal, (rows, 1))) / tile(ranges, (rows,1))
 
    return norm_set, ranges, minVal

运行：

1
>data_normed, ranges, minV = kNN.Norm_feature(datingDataMat)

4. 测试算法：作为完整程序验证分类器

书上的测试函数没有参数，是自适应函数
此处传入分割参数以及测试集，可以修改测试数值（使用书上的0.1作为分割率）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def Test_accuray(split_ratio, test_set, test_label):
    norm_test, ranges, Min = Norm_feature(test_set)
    rows = norm_test.shape[0]
    rows_test = int(rows * split_ratio)
    
    error  = 0
    
    for i in range(rows_test):
        Result = classify_KNN(norm_test[i,:], norm_test[rows_test:rows], \
                              test_label[rows_test:rows], 3)
        # 参数1表示从测试集（此处约会数据是随机的因此抽取前10%即可）中抽取一个实例
        # 参数2，3，4使用后90%作为训练数据，为输入的实例进行投票并分类，K=3
        
        print("the classifier came with: %s, the real answer is :%s " \
                 % (Result, test_label[i]))
        if(Result != test_label[i]) : error += 1
        # print(type(error)) #for test
        
    print("the accuracy is %f | the error_rate is %f " % \
          (1- (float(error) /float(rows_test)),(float(error) /float(rows_test))))

运行：

1
>kNN.Test_accuray(0.1,datingDataMat,datingLabels)

三、 示例：手写识别系统

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

实际图像存储在源代码的两个子目录内：目录trainingDigits中包含了大约2000个例子，每个数字大约有200个样本；目录testDigits中包含了大约900个测试数据。我们使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果。两组数据没有重叠。
为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。

1
2
3
4
5
6
7
8
9
10
11
12
from os import listdir #从os模块中导入函数listdir，它可以列出给定目录的文件名。
def img2vec(filename):
    '''this is to...将32X32的图像转化为1X1024的行向量'''
    returnvec = zeros((1, 1024))

    with open(filename) as fp:
        for i in range(32):
            line = fp.readline()
            for j in range(32):
                returnvec[0, 32 * i + j] = int(line[j])
    # returnVEC按32进位，j代表每位的32个元素
    return returnvec

运行：

1
2
3
>testVector = kNN.img2vec('digits/testDigits/0_13.txt')
>testVector[0,0:31]
>testVector[0,32:36]

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

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
26
27
28
29
30
31
def HandWritingTest(train_dir, test_dir):
    labels = []
    File_list = listdir(train_dir)
    # 将目录内的文件按名字放入列表，使用函数解析为数字
    m = len(File_list)
    train_mat = zeros((m, 1024))
    for i in range(m):
        fname = File_list[i]
        fstr = fname.split('.')[0]
        fnumber = int(fstr.split('_')[0])
        # 比如'digits/testDigits/0_13.txt'，被拆分为0,13,txt
        # 此处0即为标签数字
        labels.append(fnumber)
        train_mat[i, :] = img2vec('%s/%s' % (train_dir, fname))
    # labels is label_vec，同之前的KNN代码相同，存储标签

    test_File_list = listdir(test_dir)
    error = 0.0
    test_m = len(test_File_list)
    for i in range(test_m):
        fname = test_File_list[i]
        fstr = fname.split('.')[0]
        fnumber = int(fstr.split('_')[0])
        vec_test = img2vec('digits/testDigits/%s' % fname)
        Result = classify_KNN(vec_test, train_mat, labels, 3)
        print("the classifier came with: %d, the real answer is :%d " \
              % (Result, fnumber))
        if (Result != fnumber): error += 1
    # 这部分和Test模块相同，直接copy过来就好
    print("the accuracy is %f | the error_rate is %f " % \
          (1 - (float(error) / float(test_m)), (float(error) / float(test_m))))

运行：

1
>kNN.HandWritingTest('digits/trainingDigits', 'digits/testDigits/')
我们一起来让这个世界有趣一点……ヽ(✿ﾟ▽ﾟ)ノ