基于客观聚类的手写数字识别方法

王 娜，胡超芳

(1 a.天津工业大学电气工程与自动化学院自动化系；b.天津市电工电能新技术重点实验室，天津 300387；2 a.天津大学微光机电系统技术教育部重点实验室；b.电气自动化与信息工程学院自动化系，天津 300072)

0 引言

作为数据驱动工具之一，聚类是一种处理高维特征数据的有效手段，且基于划分的聚类算法已广泛应用于手写数字的识别[7]。但传统的划分聚类的初始聚类个数和聚类中心先验未知，需要经验或试凑确定，具有较多主观性；且聚类过程易受噪声或者数据分布影响，降低结果的准确性[8]。为此，引入一种新的基于客观聚类的手写数字识别方法——客观聚类分析方法[9]，它具有对数据中噪声和不规则形状的鲁棒性，可以确保上述聚类结果的准确性，且通过对模板数据集的一次聚类，获得代表性聚类个数和聚类中心，用来代替模板集识别分类，不仅避免了传统模板匹配法需要将待识别数据与模板数据集逐个比较的繁琐过程，而且约简了模板集、降低了计算量。通过对随机手写的数字在变形和添加噪声等情况下的识别，并与其他手写数字识别方法如Hopfield神经网络、支持向量机和粗糙集等，以及传统模板匹配法相比较，验证了本方法的有效性[5]。

1 手写数字识别问题描述

手写体数字识别一般包括图像预处理、特征提取、分类这3个步骤，其基本原理如图1所示。

如图1所示，其中预处理去除数字图像的噪声，并灰度化处理读入图像；采用降维方法提取数字图像的结构和统计特征，相比结构特征，统计特征对噪声不敏感，具有较好的稳定性，故可用于噪声较多的任意手写数字识别中。为此，本文采用一种统计特征法—5×5模板提取特征法[5]来对任意输入的手写体数字进行模板集的构造和输入数字特征向量的提取。其步骤如下：

1)找到每个手写样本的起始位置，在此附近搜索该样本的宽度和高度，将每个样本的长度和宽度5等分，构成5×5的均匀小区域，如图2所示。

2)对每一小区域内的黑像素个数进行统计，除以该小区域的面积总数，即得特征值，如图3所示。

图1 手写数字识别的基本步骤Fig.1 Basic steps of handwriting digital recognition

图2 对样本分成5×5区域Fig.2 Dividing the handwriting digital into a five times five area

图3 5×5模板特征值示意图Fig.3 Diagram of eigenvalue for the template of five times five

2 基于客观聚类的手写数字识别

采用模板匹配法进行数字识别时，首先，模板样本集中可能包含冗余的噪声数据，导致样本集整体数据的准确度下降，从而影响分类结果；其次，模板数据的维数较高且个数较多时，每个模板数据都要与待识别的样本进行一次距离测度的计算，计算量极其庞大，也带来识别效率的降低。为此，引入客观聚类分析方法来克服原始数据集中噪声数据的影响，提高分类精度，并选出代表性数据来约简模板数据集，降低计算量。

2.1 客观聚类分析

客观聚类分析方法分为两个阶段：偶极子划分和凝聚层次聚类。偶极子划分为后续的凝聚层次聚类提供初始聚类对象；此外原始数据集被偶极子划分为相似分布的子集，在子集上进行凝聚层次聚类，并将距离聚类中心远的数据，一般为噪声和边界点放置到最后聚类，从而能够有效降低其对最终聚类结果准确度的影响。凝聚层次聚类的聚类对象为偶极子划分的4个子集，并利用改进一致性准则来评判不同子集之间聚类结果的一致性，并选择一致性程度最高的聚类结果作为最终结果。

2.1.1 偶极子划分

偶极子划分过程分为初始子集生成、相似度排序、训练和测试子集生成[9]。

1)初始子集生成

2)相似度排序

对O中的元素，按照偶极子值由小到大依次排列，形成新的偶极子集On。

3)训练子集和测试子集生成

从On中取出前N/2个包含不重复样本的偶极子，将每个偶极子中距离数据集中点zr近的元素构成训练子集ZA={zA1,…,zAN/2}，其中每个元素按照距离远近排列。同理对每个偶极子中距离zr远的元素，得到训练子集ZB={zB1,…,zBN/2}。最后，从On中剩余的偶极子中再取出前N/2个包含不重复样本的偶极子，形成测试子集Zc和ZD。

由上述偶极子划分机制可知，其根据选定的参考聚类中心将原始数据集划分为不同的数据子集，在划分过程中按照偶极子对之间的相似性进行排序，使得在后续的凝聚层次聚类中，距离参考中心最远的偶极子对，大多为噪声数据点最后进行聚类中心的合并，而距离聚类中心最近的偶极子对最先进行聚类，从而有效降低了这些噪声点对聚类过程的影响，确保了聚类结果的准确性。

2.1.2 凝聚层次聚类

偶极子划分后，分别在子集A、B及C、D上进行凝聚层次聚类，选择相对不相似性测度作为每次聚类时聚类合并相似性程度的评判。相对不相似性测度定义为[10]

(1)

(2)

本文采用改进一致性准则克服噪声和分布的影响，提高聚类结果的鲁棒性，改进一致性准则定义为

(3)

最后，将指标BLnewAB和BLnewCD比较，由最低值确定最终聚类数和聚类中心，其中BLnewAB和BLnewCD分别由子集A、B和C、D按照式(3)得到。

由上述偶极子划分和凝聚层次聚类的步骤描述可知，偶极子分类初始划分了数据子集，并利用相似性排序法将噪声点和边界点对后续凝聚层次聚类的影响降低，从而为凝聚层次聚类提供了准确的初始聚类结果；而凝聚层次聚类利用改进一致性准则评判不同子集之间聚类结果的一致性，避免了单一聚类过程易受数据分布影响而导致聚类结果准确度下降的问题，提高了聚类结果选择的客观性，进而增强了聚类结果的精确性。

2.2 手写数字识别算法步骤描述

3 仿真研究

首先，获得数字0的模板库Z0，其表达式为130×25维矩阵：

(4)

图4 偶极子划分后的训练子集和测试子集the dipole partitioning

给定聚类数c∈{2,…,64}，利用相对不相似性测度进行聚类的合并，在聚类数为3时得到最小一致性准则值0.048，其对应聚类中心为

(5)

并取该聚类中心CenterAB0作为数字0模板样本集的代表，其由3个1×25维行向量组成，有效实现对训练子集A、B的约简。同理获得数字1,2,…,9的模板样本集聚类中心，分别为CenterAB1,…,CenterAB9：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

在手写数字输入软件的模板中在线输入数字0如下：

图5 数字0的手写在线输入示意图Fig.5 Online input diagram for the handwriting digital zero

图6 数字0变形后的手写在线输入示意图Fig.6 Online-input diagram for the distortion of handwriting digital zero

(15)

由式(15)可见，在线输入数字0与已知模板集中数字0的距离最近，为0.303，故应把其归为0类。

(16)

图7 数字0变形后的手写输入示意图Fig.7 Online-input diagram for the distortion of handwriting digital zero

(17)

(18)

表1 随机手写数字0输入下本方法与其他数据驱动方法比较

在手写数字分类软件模板[5]中随机输入29个数字0，本方法与其他数据驱动及模板匹配法比较如表1和表2所示。由表1和表2可见，对于任意输入的手写数字0，模板匹配法比其他数据驱动方法具有更高的识别精度。在其他数据驱动方法中，精度最低的是势函数法，为24.14%，最高的是Bayes匹配法，为69%。其他模板匹配法中精度最低的是基于类中心的欧几里德距离法，为72.41%；最高的是使用PCA的最近邻模板匹配法，为96.55%，而上述本方法识别精度为100%，说明本方法具有对变形及含噪声数据更强的鲁棒性，并且避免了支持向量机、Hopfiled神经网络等需要参数的初始设置和调节的过程，也避免了PCA最近邻模板匹配和夹角余弦距离法的PCA降维步骤，计算简单，易于实现，识别精度更高；另外本方法采用客观聚类分析对模板集聚类，利用聚类中心代表原始模板集，大大降低了计算量，提高了在线识别的效率。

同理依次随机输入9个手写数字1，图像如图8所示。

表2 随机手写数字0输入下本方法与其他模板匹配法比较

图8 按顺序1-9依次输入随机手写数字1示意图Fig.8 Diagram of inputting the random handwriting digital one in turn in the order of one to nine

本方法与其他方法比较如表3和表4所示[5]。由表3和表4可见，本方法与其他数据驱动和模板匹配法相比，仍具有更高的识别精度，简单易行。

表3 随机手写数字1输入下本方法与其他数据驱动方法比较

表4 随机手写数字1输入下本方法与其他模板匹配法比较

此外，通过每个数字均随机输入30个样本，对于其他手写输入数字2,3,…,9，本方法与其他方法的识别精度比较如表5所示。

表5 随机手写数字2-9输入下本方法与其他模板匹配法比较

由表5可见，本方法与其他模板匹配法相比，除对数字9的识别精度略低，为30%外，对其他数字2～8的识别精度均为最高，最高为100%，说明本方法具有较高的识别精度。并且，本方法采用模板集的聚类中心代表整个模板集，避免了传统的最近邻模板匹配法需要将待识别样本与模板集反复比较导致的繁琐计算量，提高了算法的计算效率。

4 结论

本文将客观聚类分析与模板匹配法相结合，提出了一种新的手写数字识别方法。该方法在无数据先验知识下，通过启发式自组织产生聚类，并利用聚类中心代替原始模板集，一方面具有对数据分布和噪声的较强鲁棒性，从而提高了识别精度；另一方面也约简了原始模板集，降低了计算的复杂性，提高了识别效率，对随机手写输入数字0-9在变形和加入噪声等情况下的识别结果验证了所提方法的有效性。