一种用于邮政分拣系统的邮政编码识别方法

技术领域

本发明属于邮政技术领域，特别涉及一种用于邮政分拣系统的邮政编码识别方法。

背景技术

邮政编码的识别是邮政自动分拣设备能准确分拣函件的核心。目前对于邮政编码识别的算法均基于传统的单个数字的识别，假设每类数字是均衡分布的，没有考虑在邮政编码中各类数字出现的频次。然而在邮政编码中，每类数字的分布不是均衡的，尤其是本口分拣中，由于处理的都是当地信函，邮政编码中的前几位有很大的重复性，数字类别分布的不均衡现象尤其明显，因此邮政编码的识别也是一种类别不均衡问题，需要适合的方法来降低类别分布不均衡带来的影响，提高自动信函分拣系统的性能。近年来，类别不均衡分布问题已经被意识到是机器学习和数据挖掘领域的一个非常重要的问题。人们已经对类别不平衡问题进行了大量的研究，但是一直没有成熟有效的解决方案。

发明内容

本发明目的是提供一种用于邮政分拣系统的邮政编码识别方法，以解决现有技术中邮政分拣系统的邮政编码识别难题。本发明的原理是基于研究表明，基于类别不平衡数据集的分类器学习和错识代价不相同或未知情况下分类器的学习可以用相似的方式来实现，而代价敏感学习是这类问题的一个很好的解决方案。

本发明的技术方案是，一种用于邮政分拣系统的邮政编码识别方法，包括以下步骤：

根据邮政分拣系统提供的名址库统计所在地域的邮政编码的数字字符的分布情况，具体统计所涵盖的所有邮政编码中每类数字的出现次数，统计表1如下所示，

表1

其中，N_i表示数字字符i，i ∈{0，...，9}出现的次数；

确定出现次数最少的数字字符c，满足N_c≤N_i，其中i，c ∈{0，...，9}；

设数字字符c的错分代价为1，即Cost[c]＝1，则其它9类数字字符的错分代价为$>\mathrm{Cost}\left[i\right]=\frac{N_i}{N_c}\times \mathrm{Cost}\left[c\right]=\frac{N_i}{N_c}---\left(1\right)$>

在邮政分拣系统中采集大数量的邮政编码组成邮政编码数字字符图像样本库，在该样本库中利用所述的错误代价矩阵采集训练样本集，对样本数的选取是，根据所述的错分代价，为错分代价最小的类别c选取训练样本M_c个，为其他9类数字选取训练样本个数为

M_i＝(1+log(Cost[i]/Cost[c])×M_c    (2)

训练样本集采集完成后，用该训练样本集对支持向量机分类器进行训练，该支持向量分类器是一个二类分类器，过程如下：

在学习阶段，设训练样本集为{(x₁，y₁)，...，(x_i，y_i)，...，(x_l，y_l)}，其中x_i为样本，y_i为类别，x_i ∈Rⁿ，y_i ∈{-1，1}，求最优解满足公式（3），公式（3）为

$>{\min }_{\alpha }\frac{1}{2}{\Sigma }_{i=1}^l{\Sigma }_{j=1}^l{y}_i{y}_j{\alpha }_i{\alpha }_{j}K(x_i,x_j)-{\Sigma }_{i=1}^l{\alpha }_i---\left(3\right)$>

其中$>{\Sigma }_{i=1}^l{y}_i{\alpha }_i=0,$>

然后选择α^*的正分量，计算由此构造出最优分类超平面，得出决策函数为：

$>f\left(x\right)=\mathrm{sgn}({\Sigma }_{i=1}^l{\alpha }_i^{*}{y}_i(x·x_i)+b^{*})---\left(4\right)$>

在识别阶段，对于待测样本x，输入如公式（4）的决策函数中，得出其二类的分类结果1或-1；

在所述的学习阶段的训练样本中，每两类作为一个二类分类，邮政编码的10个数字作为10类，则训练10×(10-1)/2=45个分类器，

在所述的识别阶段，用每个分类器来预测测试样本，得到45个预测结果，根据结果对邮政编码的10个类别进行投票，得票最多的类别为测试样本的邮政编码类别。

本发明公开一种适用本口分拣的邮政编码识别方法，以信函分拣系统所用地域的邮政编码中的数字字符分布为基础，首先统计邮政编码中十个数字的出现频率，根据统计数据确定代价敏感矩阵，然后利用代价敏感矩阵对训练样本进行加权采样，用加权采样的训练样本集对支持向量机（SVM）分类器进行代价敏感学习，实现利用代敏感分类器对邮政编码进行识别，从而克服邮政编码中数字字符分布不均衡带来的影响。本发明实际应用于信函分拣机的识别模块中，识别信封图像中的邮政编码，实现对信函的自动分拣。鉴于对邮政编码的统计为基础，该方法主要应用于信函的本口分拣中。

附图说明

图1现有的邮政编码识别方法流程图

图2本发明的邮政编码识别方法流程图

具体实施方式

以下结合附图对本发明的具体实施方式做详细说明。

传统的邮政编码识别方法，没有考虑邮政编码中数字的分布信息，只依赖于单个数字的识别算法，如附图1所示。本发明公开的邮政编码识别方法以邮政编码中数字字符的分布为基础，用代价敏感学习的方法对邮政编码中的字符进行识别，从而克服因字符类别分布不均衡而造成的影响，具体方法如附图2所示。

错分代价是指对于一个有C类样本的分类问题，Cost[i,c](i,c∈{0，...,C-1})表示第i类的样本被错分到第c类的代价（其中Cost[i,i]＝0），其代价矩阵可表示为：

用Cost[i](i∈{0,...,C-1}表示第i类的错识代价，它一般由Cost[i,c](i,c∈{0，...,C-1})导出。错分代价矩阵Cost表示了分类问题中的不同类别错分的代价差异性，因此又称为代价敏感矩阵。

中国的邮政编码有6位数字组成，共用到0-9十类数字。对于任何一个邮政编码来说，任何一个数字i，它被错识为任何其它9类数字都会导致邮政编码的识别错误，代价是相同的，即Cost[i,c]＝Cost[i,b](i,c,b∈{0，...,9},c≠b)，因此在本系统中我们设定Cost[i]＝Cost[i,c](i,c∈{0，...,9},i≠c)，则代价矩阵可表示为：

对于整个信函分拣系统来说，由于应用地域所涵盖的邮政编码中每类数字出现频次不同导致类别不平衡，从而每类数字的代价是不同的，出现次数多的类别错分代价较高，出现次数少的类别错分代价较低，因此我们根据对邮编的统计数据设定代价矩阵。首先统计该系统所要识别地域的邮政编码的数字字符的分布情况，具体统计所涵盖的所有邮编中每类数字的出现次数。以地域A为例，统计其所有邮编中每类数字的出现次数，N_i表示数字字符i(i ∈{0，...，9}出现的次数，则可得到如表1的统计结果。

表1地域A的邮编的统计结果

因为出现次数较少的数字字符，它的错识将导致较少的邮政编码被识错，而出现次数较多的数字字符，它的错识会导致较多的邮政编码被识错，因此我们为次数较少的数字字符设定较小的错分代价，为出现次数较多的数字字符设定较大的错分代价，具体如下：

1、确定出现次数最少的数字字符c，满足N_c≤N_i(i，c ∈{0，...，9})。

2、设数字字符c的错分代价为1，即Cost[c]＝1，则其它9类数字字符的错分代价为：

$>\mathrm{Cost}\left[i\right]=\frac{N_i}{N_c}\times \mathrm{Cost}\left[c\right]=\frac{N_i}{N_c}---\left(1\right)$>

确定错分代价后，用错分代价矩阵（即代价敏感矩阵）来对分类器的学习训练样本进行采样，得到训练样本集。具体实施中，统计目标地域的所涵盖的所有邮政编码，并统计这些邮政编码中10类数字的出现频次，得到适用于该目标地域的代价敏感矩阵，利用该代价敏感矩阵采集分类器的字符图像训练样本集。具体如下：

1、在邮政分拣系统中采集大数量的邮政编码组成邮政编码数字字符图像样本库。

2、根据上面介绍得到的错分代价，在样本库中为错分代价最小的类别c选取训练样本M_c个。

3、为其他9类数字选取训练样本，为了既估计错分代价的差异又考虑每类数字的识别准确率，用公式（2）为其他9类数字选取样本个数。

M_i＝(1+log(Cost[i]/Cost[c])×M_c    (2)

训练样本集采集结束后，用其对支持向量机分类器进行训练。

支持向量机是一种用来解决分类问题和回归问题的数据挖掘技术，它的特点是利用最大间隔思想降低分类器的VC维，实现结构风险的最小化。它利用核函数K(x_i，x_j)实现线性不可分的训练样本集映射到线性可分空间，在解决小样本、非线性和高维模式识别问题中有较大优势。它是一个二类分类器，基本原理为：

1、学习阶段：设训练集{(x₁，y₁)，...，(x_i，y_i)，...，(x_l，y_l)}，其中x_i为待分类样本，y_i表示类别，x_i ∈Rⁿ，y_i ∈{-1，1}。求最优解$>{\alpha }^{*}={({\alpha }_1^{*},{\alpha }_2^{*},...,{\alpha }_l^{*})}^T$>满足公式（3）

$>{\min }_{\alpha }\frac{1}{2}{\Sigma }_{i=1}^l{\Sigma }_{j=1}^l{y}_i{y}_j{\alpha }_i{\alpha }_{j}K(x_i,x_j)-{\Sigma }_{i=1}^l{\alpha }_i---\left(3\right)$>

其中然后选择α^*的正分量，计算$>b^{*}=y_i-{\Sigma }_{i=1}^l{y}_i{\alpha }_i^{*}K(x_i,x_j),$>由此可以构造出最优分类超平面，得出决策函数：

$>f\left(x\right)=\mathrm{sgn}({\Sigma }_{i=1}^l{\alpha }_i^{*}{y}_i(x·x_i)+b^{*})---\left(4\right)$>

2、识别阶段：对于待测样本x，输入如公式（4）的决策函数中，得出其二类的分类结果1或-1。

邮政编码中的数字识别是个多分类（10类）问题，因此我们需要将SVM推广到可以分多类样本。我们采用一对一的方法，在学习阶段训练样本中的每两类作为一个二类分类问题，10个数字有10类，则训练10×(10-1)/2=45个分类器。在识别阶段用每个分类器来预测测试样本，可得到45个预测结果，根据结果对10个类别进行投票，得票最多的类别为测试样本所属类型。

本发明以邮政编码中数字字符的分布为基础，利用代价敏感分类器克服数字字符分布不均衡对识别效果带来的影响，实现邮政编码的准确识别。

首先统计邮政编码中十个数字的出现频率，根据统计数据确定代价敏感矩阵，然后利用代价敏感矩阵对训练样本集进行加权采样，用加权采样后的训练样本集对分类器进行代价敏感学习，从而实现利用代敏感分类器对邮政编码进行识别。其中，选用支持向量机(SVM)作为字符识别的分类器，对其进行代价敏感学习，使其成为代价敏感分类器对邮政编码进行识别。