机器学习：（1）k-近邻算法及手写数字识别系统_编程实现k-近邻算法并用于手写数字识别 按照距离递增次序排序; 选取与当

（一）kNN算法概述

1.k邻近算法基于距离的测量，选取距离最近的特征值，即为预测的结果。该算法属于监督学习中的分类算法，基于大量数据的基础上，做出相应的预测，一般运用于手写数字识别，约会网站的大量数据匹配等等。

2.其优点是：精度高，对异常值不敏感，无数据输入假定.

3.其缺点是：计算复杂度高，空间复杂度高。

4.适用数据范围是：数值型和标称型。

（二）原理

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

（三）代码

1. 使用Python导入数据

from numpy import  *  #导入numpy的库函数，调用函数时前面无需加上numpy.
import  operator      #导入运算符模块

def createDataSet():
    group=array([[3,104],[2,100],[101,10],[99,5]])  #导入四部电影[打斗镜头次数，接吻镜头]
    labels=['A','A','B','B']    #labels分类标签，A为爱情片，B为接吻镜头
    return group,labels
1
2
3
4
5
6
7
'
运行
运行

导入两个模块，一个是科学计算包NumPy，还一个是运算符模块。定义createDataSet函数，使用该函数创建数据集和标签。
这里有4组数据，每组数据有两个我们已知的属性或特征值，向量labels包含了每个数据点的标签信息，labels包含的元素个数等于group矩阵行数。

2. 实施kNN分类算法

2.1 伪代码：对未知类别属性的数据集中的每个点依次执行以下操作：

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

2.2 程序实现

#inX用于分类的输入向量，dataSet输入的训练样本集，labels标签向量，k用于选择最近邻居的数目。其中标签向量的元素数目和矩阵dataSet的行数相同
def classify0(intX,dataSet,labels,k): 
    #计算dataSet行数，获得数据集的行数，x.shape函数可以输出一个元组（m,n），其中元组的第一个数m表示矩阵的行数，元组的第二个数n为矩阵的列数,shape[0]只输出行数，shape[1]只输出列数
    dataSetSize=dataSet.shape[0] 
    #numpy.tile函数用于扩展数组，对intX按(4,1)进行复制，4代表复制4行，1代表列不变,求未知类别与各个点的差值，再求到原点的距离得知与各点的距离大小
    #复制待分类数据方便矩阵计算，一个样本对应一个输入数据，多个样本和同一个输入数据的距离可以通过矩阵同时计算
    #矩阵减法，输入数据的特征减去样本数据的对应特征
    diffMat=tile(intX,(dataSetSize,1))-dataSet 
    #矩阵平方即特征差值的平方
    sqDiffMat=diffMat**2  
    #按行求和得到平方和，二维情况下，sum(axis=0)按列求和，sum(axis=1)按行求和
    sqDistances=sqDiffMat.sum(axis=1) 
    #开方得欧式距离，计算两个点间的距离
    distances=sqDistances**0.5
    #argsort()按升序排序后取索引值，argsort返回数值从小到大的索引值（数组索引0,1,2,3）
    sortedDistIndicies=distances.argsort()

    #定义字典
    classCount={} 
    #选择距离最小的k个点,i从0到k-1
    for i in range(k):   
        #取出样本对应的标签
        voteIlabel=labels[sortedDistIndicies[i]]
        #前半部分添加字典key值，后半部分为对应value值，get函数若有对应voteIlabel则返回该值，若无则为0，根据排序结果的索引值返回靠近的前k个标签，统计类别出现的次数{'A': 1, 'B': 2}
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    #用字典做类别计数器，类别为键，数量为值，将无序的字典迭代为有序的元组后，operator模块中的itemgetter函数，itemgetter(1)取出元组第一个域进行比较（有第0个域），reverse=True为按降序排序
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    
    return sortedClassCount[0][0] 
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
'
运行
运行

classify0 ()函数有4个输入参数：用于分类的输入向量是inX，dataSet输入的训练样本集，labels标签向量，k用于选择最近邻居的数目。其中标签向量的元素数目和矩阵dataSet的行数相同。程序所使用的欧氏距离公式，计算两个向量点xA和xB之间的距离：

$$d=\sqrt{(x{A}_0-x{B}_0{)}^2+(x{A}_1-x{B}_1{)}^2}$$

计算完所有点之间的距离后，可以对数据按照从小到大的次序排序。然后，确定前k个距离最小元素所在的主要分类，输入k总是正整数；最后，将classCount字典分解为元组列表，然后使用程序第二行导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行排序。此处的排序是逆序，即按照从最大到最小次序排序，最后返回发生频率最高的元素标签。

3.预测数据所在分类

group,labels = createDataSet()
print(classify0([18,90],group,labels,3))
1
2

预测结果为A：爱情片。

A
1

4.分析

若是训练数据集过大，每次都需要计算数据的距离值，实际耗时会过大，不仅时间开销大，存储空间的消耗也巨大。

（四）手写数字识别系统实验

1. 实验概述

构造一个能识别数字0到9的基于kNN分类器的手写数字识别系统。
需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素✖32像素的黑白图像。

2. 实验内容

（1） 使用K-NN算法识别数字0-9，实现最基本的KNN算法，使用trainingDigits文件夹下的数据，对testDigits中的数据进行预测。
（2）改变K的值，并观察对正确率的影响。

3. 代码

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

将32✖32的二进制图像矩阵转换为1✖1024的向量：

#将图像转换为测试向量
def img2vector(filename):
    #将32*32的二进制图像矩阵转化为1*1024的向量,用法：zeros(shape, dtype=float, order=’C’),返回：返回来一个给定形状和类型的用0填充的数组；
    return_vector = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        #readline() 方法用于从文件读取整行，包括 “\n” 字符。如果指定了一个非负数的参数，则返回指定大小的字节数，包括 “\n” 字符。
        lineStr = fr.readline()
        for j in range(32):
            # 将每行的头32个字符值存储在Numpy数组中
            return_vector[0, 32 * i + j] = int(lineStr[j])
    #返回数组
    return return_vector
1
2
3
4
5
6
7
8
9
10
11
12
13
'
运行
运行

函数img2vector创建1×1024的NumPy数组，然后打开给定的文件，循环读取文件前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。

3.2 测试kNN算法

将trainingDigits目录中的文件内容存储在列表中，然后可以得到目录中有多少文件，并将其存储在变量m中。接着，创建一个m×1024的训练矩阵trainingMat，每行数据存储一个图像。然后从文件名解析分类数字，并存储在hwLabels向量中，使用img2vector函数载入图像。接着队testDigits目录中的文件执行相识的操作，但不载入矩阵中，而是使用classify0()函数测试该目录下的每个文件。

 
# 手写数字识别
def handwritingClassTest():
    #定义字典
    hwLabels = []
    #listdir（）函数的参数是一个路径名，函数返回值是一个列表，存放该路径下所有的文件名and目录名。
    trainingFileList = listdir('D:/study/机器学习/py code/kNN/trainingDigits')
    #len函数返回参数对象（例如字符或字符串、元组、列表和字典等）的项目个数（长度）。这里是返回列表长度
    m = len(trainingFileList)
 
    #创建一个m*1024的训练矩阵
    trainingMat = zeros((m,1024))
    #从文件名中解析出分类数字，该目录下的文件按照规则命名，如文件9_45.txt的分类是9，它是数字9的第45个实例
    for i in range(m):
        #9_45.txt
        fileNameStr = trainingFileList[i]
        #9_45
        #split通过指定分隔符对字符串进行切片，并返回分割后的字符串列表（list）
        #语法：str.split(str="",num=string.count(str))[n]
        #str:表示为分隔符，默认为空格，但是不能为空('')。若字符串中没有分隔符，则把整个字符串作为列表的一个元素
        #例如：s.split('')是不合法的表达
        #num:表示分割次数。如果存在参数num，则仅分隔成 num+1 个子字符串，并且每一个子字符串可以赋给新的变量
        #[n]:表示选取第n个分片
        fileStr = fileNameStr.split('.')[0]
        #9
        classNumStr = int(fileStr.split('_')[0])
        #将类代码存储在hwLabels向量中,在列表hwLabels末尾添加classNumStr
        hwLabels.append(classNumStr)
        #载入图像,m*1024的训练矩阵
        trainingMat[i,:] = img2vector('D:/study/机器学习/py code/kNN/trainingDigits/%s' % fileNameStr)

    #测试集
    testFileList = listdir('D:/study/机器学习/py code/kNN/testDigits')  
    errorCount = 0.0
    mTest = len(testFileList)    
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        #1*1024的列表
        vectorUnderTest = img2vector('D:/study/机器学习/py code/kNN/testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)
        print("预测值： ",classifierResult)
        print("真实值： ",classNumStr)
        if(classifierResult!=classNumStr):
            errorCount += 1.0
    print("总共错误的数量为： ",errorCount)
    print("错误率为： ",(errorCount)/float(mTest))
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
'
运行
运行

预测结果为：

...
预测值：  9
真实值：  9
预测值：  9
真实值：  9
总共错误的数量为：  10.0
错误率为：  0.010570824524312896
1
2
3
4
5
6
7

（五）总结

1.课本中函数classify0()排序时用到了函数iteritems()，由于版本问题无法使用，则改成了items()函数返回classCount。

二者区别在于：
items()返回一个列表，以二元组的形式展示了字典中所有的元素，是比较耗内存的，尤其是在元素数量巨大时。但是在获取元素时有巨大的优势。
iteritems()作为生成器，保存的是算法，因此对空间不敏感，但是如果生成算法复杂，相比于items()需要更多的时间来获取下一个元素。这也就是经典的时间换空间。

2.kNN算法确实是分类数据最简单有效的算法，但是如果训练数据集很大，存储空间就必须够大，并且算法的执行效率不高。正如手写数字识别系统这个案例，维度高、样本多，计算过程就十分繁琐，不太适合。

3.kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

！！！4.N个训练样本，样本维度为M，k=1时，时间复杂度：
训练时，O(1)，因为不需要训练；
测试时，O(NM)，N个样本都需要计算距离。

！！！5.kNN算法要求：

• 近邻点特征相同/相近。
• 特征维度一致，不一致则归一化，newValue = (oldValue - min) / (max - min)。

• ！！！6.
  优点：
  （1）可处理分类问题，简单易懂。
  （2）可以免去训练过程。
  （3）还可以处理回归问题即预测（股票啥的，根据以前的走势预测下一个点的位置）
  缺点：
  （1）效率低，每一次分类都要对训练数据进行计算，计算距离。
  （2）对训练数据依赖大，过拟合、欠拟合难以权衡。
  （3）维度灾难。

  ！！！7.k过小，过拟合。k过大，欠拟合。

  ！！！8.better的方法：最近邻搜索也叫KD树（类比折半查找）