写在前面
最近几天忙完考试看了一个关于机器学习的基础算法——k近邻算法，简称为KNN。KNN是数据挖掘领域的十大经典算法之一，优点是简单，精度高，对异常值不敏感，无数据输入假定；缺点是计算的复杂度高，空间复杂度高。笔者由于刚刚机器学习入门，因此先从简单的算法开始，手动实现了一下KNN算法，并且基于KNN做了一个网页验证码图片识别的demo出来。当然现实中做验证码识别大多都不用KNN来做，开销太大而且太慢，但是目前水平有限嘛，就先用KNN来做着。
数据集获取
由于对母校西南交通大学的教务系统怀有深深执念，因此数据集就采自西南交大的教务登录系统，写一个小爬虫从教务系统的登录界面采集1000张验证码图片。
KNN核心算法编写
KNN是一种有监督学习方法，其核心思想非常简单，算法没有训练过程，当用户传入一个需要被分类的数据时，算法就会将该数据与数据集中的带标签数据进行对比，计算“距离”，并且根据与待分类数据距离的从小到大对数据集中的数据进行排序，最后根据用户传入的k值，选取前k个最接近待分类数据的数据的标签，则待分类数据的标签等于k个数据中出现次数最多的标签值。代码如下：
在这里，距离的衡量使用的是欧氏距离，用户也可以使用其他的距离来作为数据之间距离的衡量指标。
数据预处理
算法在对图片进行分类之前首先要对数据进行预处理。由于原始的图片是RGB图片，转化成矩阵有三个维度不太好处理，因此首先要将图片转化成灰度图，这样其矩阵就是二维的。同时为了增加对比度，和最大限度地去除验证码图片中随机线条对分类器的干扰，笔者设定一个阈值，将大于这个阈值的矩阵数值置为255，小于这个阈值的的数值置为0。这个阈值的选定需要针对不同的验证码做多次实验，来找到一个最优的值。
其次我们观察验证码图片可以发现，每张验证码图片的顶部和左端都有条黑色的实线，这是数据集中的噪音，需要去掉，算法将把图片在顶端和左端都切掉一个像素的宽度。
接下来我们需要对验证码图片进行切分，将验证码中的字母从原始图片中“切”出来，笔者认为这才是整个算法中比较有难度的一节。观察从网络上获取到的验证码图片，我们可以发现字母在图片中的位置分布并不是固定的，因此不能采用定长分割这种方案。必须要针对不同的图片动态分割，并且对分割后的图片进行规整化操作，以使每张图片都达到一样的大小便于后期向量化处理。在图片分割这个问题上，笔者以图片的每一列为考察单位，因为毕竟是要纵向分割图片。笔者基于这样的一个假设，若一列上不包含验证码字母，则该列上大部分应该是白色（一则因为图片上有一写随机干扰线无法完全去除，二则因为上一步将图片二值化后图片本底就变为白色），若一列上包含字母则该列上有相当一部分像素点的值应该不是白色，问题的关键依然在于选定一个阈值，若某一列白色阈值的比例大于这个值则判定该列上没有字母可以作为备选分割线，若小于这个阈值则该列上包含有字母，不能作为分割的备选线，笔者通过实验得出该阈值取0.9较为合适。那么，该算法第一步就能够得到一系列备选的图片分割线，第二步就是从这些备选分割线中选出真正的分割线，笔者在这里的设定是让分割线之间的距离最小，即两个字母之间若存在分割线则选择最中间的那条。分类效果如下图所示：
如上图所示，算法的切分效果还是不错的。
算法实现
到目前为止，笔者已经完成了图片的预处理和规整化。接下来只用将图片向量化并打上标签输入分类器就可以了。由于图片本身是一个二维矩阵，我们只用将二维转化成一维就行了，非常简单。接着，我们需要手动为每一个字母打上标签，效果如下图所示：
如上图所示，切分后的字母图片的名称第一个字母即为该图片的标签。
算法测试
笔者选取一百张验证码图片对分类器进行测试，测试代码如下：
最终测试结果表明该算法的错误率大约在0.2左右。
算法应用
笔者在该算法基础上由写了一个教务系统的登录程序，看能不能对学校的教务系统进行登录，代码如下：
运行结果如下：
如图所示，登录成功。
开源
https://github.com/yhswjtuILMARE/KNN-Identification-codes
2018年1月19日
