python验证码识别6:kNN

Roy
编程技术

什么是kNN?kNN(k-Nearest Neighbors)是机器学习中处理分类问题的一种简单明了的算法。核心精髓就是老祖宗几百年前留下的言语"物以类聚，人以群居”。忘记从哪里看到的一个说法：“你身边最好的6个朋友的平均薪资，就是你的薪资水平。“这就是kNN算法的一个应用了吧，另外我觉得之前几篇给验证码降噪用的连通域算法，分割用的滴水算法，都有kNN的味道在里面。

首先，对于字符型验证码的识别都省不了之前说的那几步：

  1. 灰度
  2. 二值化
  3. 降噪
  4. 切割

如果图片有旋转、扭曲还要多一步操作进行复原。接下来想使用kNN算法，则需要将二值化后的图片转换成向量(个人觉得二值化后的数据已经可以满足使用了，但为了使用Numpy提高处理效率，所以还需要进行转换)，在计算距离，最后归类到某个已知类别中。

所以，如果想使用kNN算法来识别字符有一个前提条件，就是分割图片的宽、高像素必须一致，这样才能计算距离。这里以UCI提供好的手写数字为例，省去了自己下载验证码、降噪等步骤，但原理都是一样的。

二值化后的图片存储为txt文件，内容类似这样：

00000000000011111000000000000000
00000000011111111100000000000000
00000000111111111110000000000000
00000001111111111110000000000000
00000111111111111110000000000000
00000111111111111110000000000000
00000011111110001111100000000000
00000011110000000111100000000000
00000011110000000111100000000000
00000011100000000111100000000000
00000000000000000111100000000000
00000000000000000111100000000000
00000000000000000111000000000000
00000000000000000111100000000000
00000000000000000111100000000000
00000000000000000111100000000000
00000000000000001111000000000000
00000000000000011111000000000000
00000000000000111111000000000000
00000000000000111110000000000000
00000000000000111111000000000000
00000000000001111110000000000000
00000000000011111100000000000000
00000000001111111000000000000000
00000000111111110000000000000000
00000000111111111000011000000000
00000001111111111111111111100000
00000000111111111111111111110000
00000000011111111111111111110000
00000000111111111111111111110000
00000000011111111111110010000000
00000000000000010000000000000000

由上面可知，二值化后图片变成了一个32*32的矩阵，先把这个矩阵变成一个向量，人话就是"把这个32行的文件变成1行”。

import numpy as np

def img2vector(filename, w, h):
    returnVect = np.zeros((1, w * h))
    with open(filename, 'r') as f:
        for i in range(h):
            line = f.readline()
            for j in range(w):
                returnVect[0, w * i + j] = int(line[j])
    return returnVect

接下来建立数据集，把所有二值化后的文本文件都放到一个矩阵里：

from os import listdir
def create_dataset(dirname, w, h):
    labels = []
    file_list = listdir(dirname)
    m = len(file_list)
    trainingmat = np.zeros((m, w * h))
    for i in range(m):
        file_name = file_list[i]
        file_str = file_name.split('.')[0]
        labels.append(int(file_str.split('_')[0]))
        trainingmat[i, :] = img2vector('%s/%s' % (dirname, file_name), w, h)
    return trainingmat, labels

接下来，根据上篇文章介绍的欧式距离来进行分类：

import operator

def classify(target_data, data_set, labels, k):
    data_set_size = data_set.shape[0]  # 有多少行

    diff_mat = np.tile(target_data, (data_set_size, 1)) - data_set  # 将target_data扩维，使其和data_set行数一致，并求差

    sq_diff_mat = diff_mat**2  # 求平方

    sq_distances = sq_diff_mat.sum(axis=1)  # 求和，注意axis=1代表对行，默认对列求和

    distances = sq_distances**0.5  # 开平方

    sorted_distances = distances.argsort()  # 返回排序后的索引

    class_count = {}
    for i in range(k):
        vote_label = labels[sorted_distances[i]]  # 找到最近元素的标签

        class_count[vote_label] = class_count.get(vote_label, 0) + 1  # 计算相似数量

    sorted_classcount = sorted(
        class_count.items(),
        key=operator.itemgetter(1),
        reverse=True)
    return sorted_classcount[0][0]

然后就可以开始测试了：

if __name__ == '__main__':
    trainingmat, train_labels = create_dataset('./trainingDigits', 32, 32)
    testmat, test_labels = create_dataset('./testDigits', 32, 32)
    error = 0
    for i, one in enumerate(testmat):
        classifier_result = classify(one, trainingmat, train_labels, 3)
        print(
            "预测结果： %d 真实结果： %d" %
            (classifier_result, test_labels[i]))
        if classifier_result != test_labels[i]:
            error += 1
    print("错误数：%d" % error)
    print("错误率： %f" % float(error / len(test_labels)))

输出如下：

...
预测结果： 9 真实结果： 9
预测结果： 2 真实结果： 2
预测结果： 3 真实结果： 3
错误数：13
错误率： 0.013742

可以看出在这个示例中使用kNN预测的准确率可以达到99%，但这个算法也有缺陷，最明显的就是每一条测试数据都要和训练集所有的数据进行距离计算，所以现在基本很少用了。说到这里，现在深度学习这么流行，各种框架封装好了各种算法，我们还有必要学习这种“原始”的东西么？

个人看法是有必要，如果目的不是仅仅当一个“掉包侠”，那么切记：

勿在浮沙建高塔。