简单起见，这里构造的系统只能识别数字0到9

解决思路与代码

（1）收集数据
　　目录trainingDigits中包好了2000左右个例子（用这些实例训练分类器），部分例子如下图所示。[注释：需要识别的数字已经经过图形处理软件，处理成具有相同色彩和大小(32×32像素的黑白图像)，每个数字大约200个样本。为了方便理解，我们把图像转换为文本格式]
　　手写
　　目录testDigits中包好了大约900个测试数据（用这些实例测试分类器的效果），两个目录的数据没有重复。
（2）准备数据
　　编写函数img2vector，将一个32×32的二进制图像转换成1×1024的numpy数组（即每个图像有1024个特征）
　　如何转换？打开文件→循环读出每一行→将每行的元素存储在numpy数组中

1
2
3
4
5
6
7
8
def img2vector(filename):
    x_vec = np.zeros((1,1024))       #初始化图像向量，全为0
    fr = open(filename)       #打开文件
    for i in range(32):
        frline = fr.readline()       #每次执行到这，就读取一行（一共32行）
        for j in range(32):       #遍历该行中每列的元素（一共32个元素）
            x_vec[0,32*i+j] = int(frline[j])       #一个元素一个元素地赋值
    return x_vec

1
2
3
4
5
>> x_vec = imgvector('testDigits/0_13.txt')
>> x_vec[0,:30]
array([ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  1.,  1.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  0.,  0.,  0.])

（5）评估模型
　　[模型介绍等详细内容见“改进约会网站的配对效果”]
　　先编写函数featurelabel()，用来构造数据集的特征矩阵、标签向量
　　再编写函数classtest()，将测试数据输入到分类器，评估分类器的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
from os import listdir
def featurelabel(filename):
    fr_list = listdir(filename)        #列出给定目录的文件名
    fr_num = len(fr_list)        #文件数量，即样本个数
    X = np.zeros((fr_num, 1024))        #初始化训练集特征矩阵
    y = []        #初始化标签向量

    for i in range(fr_num):         #遍历每一个样本
        fr_name = fr_list[i]          #样本文件的名字，比如0_0.txt
        y_str = fr_name.split('.')[0].split('_')[0]          #提取每个样本对应的标签
        y = y.append(int(y_str))
        X[i,:] = img2vector('%s/%s' % (filename, fr_name) )         #每一行的特征
    return X, y

　　代码问题：a=a.append(b)是错误写法。因为append方法没有返回值，即a=a.append(b)会执行成功，并将a赋值为None；第二次调用就会报错 → ‘NoneType’ object has no attribute ‘append’，因为None是不能调.append方法的。只写a.append(b)就可以了，不要接返回值

1
2
3
4
5
6
7
8
9
10
11
12
def classtest():
    X_train, y_train = featurelabel('trainingDigits')
    X_test, y_test = featurelabel('testDigits')
    error_count = 0.0
    m = len(X_test)
    for i in range(m):
        y_result = knnFunc(X_test[i], X_train, y_train, 3)
        if(y_result != y_test[i]):
            error_count += 1
    error_rate = error_count / m
    print('total number of errors is: %d' % error_count)
    print('error rate is: %f ' % error_rate)

1
2
3
>> classtest()
total number of errors is: 10
error rate is: 0.010571

　　knn算法是一种时间复杂度、空间复杂度很大的算法。比如这个例子的执行效率就很慢，因为它要经过以下运算：一共大约900个测试样本，对每个测试样本做2000次距离计算，每个距离计算包括了1024个维度浮点运算。另外，我们还需要为测试向量准备2MB的存储空间。
　　总结：k近邻算法是基于实例的学习，如果训练集很大,则必须使用大量的存储空间，而且必须对每个样本数据点计算距离，实际使用时非常耗时。它的另一个缺点是：无法给出数据的基础结构信息，不知道与测试数据相近的训练数据有什么特征（可以用决策树解决）