CN100338621C - 有限字符样本集上特征值误差补偿及参数分布修正方法 - Google Patents

Abstract

一种有限字符样本集上特征值误差补偿及参数分布修正方法。以最小的主特征值替换次特征值，并采用非对称模型描述特征矢量在优势主向量上的分布，分别用于减小次主向量空间和优势主向量空间导致的总体距离偏差来实现误差补偿及参数分布修正。本发明计算简单，识别时不需要任何额外的计算开销，能够更精确地刻画实际样本的分布情况，能显著地提高识别的精度。

Description

有限字符样本集上特征值误差补偿及参数分布修正方法

技术领域

本发明涉及的是一种用于统计模式识别技术领域的方法，具体地说，是一种有限字符样本集上特征值误差补偿及参数分布修正方法。

背景技术

马氏距离是模式识别中一个有效的相似性测度，可以采用从主向量分析(PCA)中得到的特征值-特征向量表达。PCA对描述数据的原坐标系进行正交变换，是从可能的高维数据中提取结构的有效技术。PCA可以通过解特征值问题或采用估计主向量的迭代算法实施，描述数据的新坐标值被称为主向量，通常采用主向量表达数据的结构比原坐标系要有效得多。然而，当可以利用的样本数量有限时，PCA计算的特征值通常包含误差。传统的马氏距离是在多变量正态分布概率密度函数的假设下推导出来的，因此，如果样本的分布服从多变量正态分布，马氏距离被认为是一个合适的测度指标。然而，研究发现样本的分布与正态分布有较大的差异，其中包括类内样本分布的非对称特性。因此需要采用改进的马氏距离来计算未知模式的特征矢量与某类的均值矢量之间的距离。

经对现有技术文献的检索发现，N.Kato，M.Suzuki，S.Omachi，H.Aso and Y.Nemoto在“采用方向元素特征和非对称马氏距离的手写字符识别系统”(电子电器工程师协会模式分析与机器智能学报，1999，21(3)：258-262.)一文中，采用对特征值加上偏移量的方法对所有的特征值进行误差补偿，并采用非对称模型描述所有主向量上的参数分布。其不足之处是，马氏距离在次主向量(对应于较小的特征值)上的偏差远大于在优势主向量上的偏差，对主特征值进行误差补偿可能同时增加类间的相似度；同时次特征值通常很小而且存在较大误差，因此无法精确地在相应的次主向量上对参数进行非对称分布描述。

发明内容

本发明的目的在于克服现有技术中的不足和缺陷，提供一种有限字符样本集上特征值误差补偿及参数分布修正方法，采用非对称分布对多变量正态分布假设进行修正，可以更精确地刻画实际样本的分布情况，能够显著地提高手写体数字字符的识别精度。

本发明是通过以下技术方案实现的，本发明以最小的主特征值替换次特征值，并采用非对称模型描述特征矢量在优势主向量上的分布，分别用于减小次主向量空间和优势主向量空间导致的总体距离偏差来实现误差补偿及参数分布修正。。

本发明的具体步骤如下：

(1)计算各类样本的均值特征矢量和协方差矩阵。这两个参数描述样本在特征矢量空间的分布状况，是本发明进行特征值误差补偿及参数分布修正的基础。其中，某类的均值特征矢量表示该类的质心，协方差矩阵表示该类样本分布的离散程度；

(2)对协方差矩阵进行对角化。通过PCA对描述数据的原坐标系进行正交变换，得到特征向量矩阵和特征值矩阵，有效地提取这些数据的结构。特征向量矩阵表示描述数据的新坐标系，描述数据的新坐标值被称为主向量，特征值则表示相应主向量上参数分布的离散程度。采用主向量表达数据的结构比原坐标系要有效得多，本发明的误差补偿及参数分布修正是在主向量空间进行的。

(3)根据设定的阈值分别选择每类的主特征值，其余为次特征值，通过采用最小的主特征值替换所有的次特征值对次特征值进行误差补偿；对应于主特征值的特征向量为优势主向量，对应于次特征值的特征向量为次主向量。对由于有限样本导致的次特征误差进行补偿，可以显著减少马氏距离在次主向量空间的误差。

(4)根据非对称假设计算优势特征向量上的准方差，准方差表示参数在均值特征矢量两侧分布的离散程度，并描述了参数在均值特征矢量两侧分布的非对称性。可以降低由于多变量正态分布假设导致的马氏距离在优势主向量空间的误差。

(5)采用上述计算得到的准方差和修正后的特征值替换传统马氏距离计算中的相应的特征值项，完成对马氏距离计算的修正。此处同时考虑了次特征值误差和优势主向量上非对称分布的影响，可以显著降低马氏距离的计算误差，从而显著地提高识别的精度。

本发明的有益效果是：本发明计算简单，针对性和通用性好，识别时不需要任何额外的计算开销，能够更精确地刻画实际样本的分布情况，能显著地提高识别的精度，满足手写体数字字符识别速度快，精度高的要求。

具体实施方式

为了更好地理解本发明的技术方案，该部分将做进一步详细描述，并在最后给出一个实施例。

1)有限样本集上的主向量分解

①根据某类的M个训练样本x_k，k＝1，…，M，其中x_k∈R^N，计算均值矢量 μ和协方差矩阵Σ_X：

$\stackrel{\‾}{\mathrm{\μ}}=\frac{1}{M}{\mathrm{\Σ}}_{k=1}^M{x}_k$

${\mathrm{\Σ}}_X=\frac{1}{M}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}(x_j-\stackrel{\‾}{\mathrm{\μ}}){(x_j-\stackrel{\‾}{\mathrm{\μ}})}^T$

②协方差矩阵对角化。将协方差矩阵Σ_X被分解为特征值矩阵与特征向量矩阵的乘积：

∑_X＝UDU^T

其中，U是特征向量矩阵，且U^TU＝I，D是由特征值构成的对角矩阵。λ_j和φ_j分别是协方差矩阵的第j个特征值和特征向量。

③以U为变换矩阵，将N维矢量X线性变换为N维矢量Y：

Y＝U^TX

变换后的协方差矩阵为：∑_Y＝U^T∑_XU＝D

④对Y进行D^-1/2变换，将协方差矩阵变换为单位矩阵I。

Y＝D^-1/2U^TX＝(UD^-1/2)^TX

∑_Y＝D^-1/2U^T∑_XUD^-1/2＝D^-1/2DD^-1/2＝I

变换矩阵UD^-1/2称为白化变换。变换矩阵D^-1/2的目的是以

为比例因子改变主向量的尺度，该变换意味着在主向量上对样本参数进行规范化。

⑤计算白化变换后的距离测度：

$d\left(x\right)=\left|\right|{\left({\mathrm{UD}}^{-1/2}\right)}^T(x-\stackrel{\‾}{\mathrm{\μ}})\left|\right|={\left({\left({\mathrm{UD}}^{-1/2}\right)}^T(x-\stackrel{\‾}{\mathrm{\μ}})\right)}^T\left({\left({\mathrm{UD}}^{-1/2}\right)}^T(x-\stackrel{\‾}{\mathrm{\μ}})\right)$

$={(x-\stackrel{\‾}{\mathrm{\μ}})}^T{\mathrm{UD}}^{-1/2}{D}^{-1/2}{U}^T(x-\stackrel{\‾}{\mathrm{\μ}})={(x-\stackrel{\‾}{\mathrm{\μ}})}^T{\mathrm{UD}}^{-1}{U}^T(x-\stackrel{\‾}{\mathrm{\μ}})$

$={(x-\stackrel{\‾}{\mathrm{\μ}})}^T{\mathrm{\Σ}}_X^{-1}(x-\stackrel{\‾}{\mathrm{\μ}})$

上式表明，白化变换空间的距离实际上就是未知模式的特征矢量x与某类的均值矢量 μ之间的马氏距离，可以采用特征值-特征向量的方式表达如下：

$d\left(x\right)=\underset{j=1}{\overset{N}{\mathrm{\Σ}}}\frac{1}{{\mathrm{\λ}}_j}{(x-\stackrel{\‾}{\mathrm{\μ}},{\mathrm{\φ}}_j)}^2$

有时，某些类的协方差矩阵是奇异矩阵，因此，计算马氏距离时，首先需要计算该协方差矩阵的伪逆矩阵。本质上，采用上式计算马氏距离将不可避免地遇到(x- μ，φ_j)²/(λ_j)＝0/0的情况。

2)本发明的次特征值的误差补偿

欲完成次特征值的误差补偿，需进行下列计算：

①选择主特征值。根据下式选择主特征值的个数：

k＝{n|(λ₁+λ₂+…+λ_n-1)/(λ₁+λ₂+…+λ_N)＜thr，

      (λ₁+λ₂+…+λ_n)/(λ₁+λ₂+…+λ_N)≥thr)

其中，0＜thr≤1.0为主特征值选择阈值。

②采用最小的主特征值λ_k替换其余N-k个次特征值λ_k+1，λ_k+2，…，λ_N，即，

${\stackrel{\‾}{\mathrm{\λ}}}_i=\left\{\begin{array}{cc}{\mathrm{\λ}}_i,& \mathrm{if\; i}\≤k\\ {\mathrm{\λ}}_k,& \mathrm{if\; i}>k\end{array}\right.$

③计算修改后的协方差矩阵：

∑_X＝U DU^T

其中， D是修改后的特征值矩阵：

$\stackrel{\‾}{D}=\mathrm{diag}\{{\stackrel{\‾}{\mathrm{\λ}}}_1,{\stackrel{\‾}{\mathrm{\λ}}}_2,\·\·\·,{\stackrel{\‾}{\mathrm{\λ}}}_N\}$

显然 ∑_X必定是非奇异矩阵。

④计算改进的距离测度：

$\stackrel{\‾}{d}\left(x\right)={(x-\stackrel{\‾}{\mathrm{\μ}})}^T{\stackrel{\‾}{\mathrm{\Σ}}}_X^{-1}(x-\stackrel{\‾}{\mathrm{\μ}})$

也可以采用下列的特征值-特征向量表达方式：

$\stackrel{\‾}{d}\left(x\right)=\underset{j=1}{\overset{N}{\mathrm{\Σ}}}\frac{1}{{\stackrel{\‾}{\mathrm{\λ}}}_j}{(x-\stackrel{\‾}{\mathrm{\μ}},{\mathrm{\φ}}_j)}^2$

上式从本质上避免了计算时出现(x- μ，φ_j)²/( λ_j)＝0/0的情况。

3)本发明的非对称分布

为了描述非对称分布，需进行下列计算：

①定义矢量集合S_j ⁺和S_j ^-：

$S_j^{+}=\left\{{{\stackrel{\‾}{u}}^i}_j\right|{{\stackrel{\‾}{u}}^i}_j\≥0\}$

$S_j^{-}=\left\{{{\stackrel{\&OverBar;}{u}}^i}_j\right|{{\stackrel{\&OverBar;}{u}}^i}_j<0\}$

其中 ${\stackrel{\&OverBar;}{u}}_j^i=(x_i-\stackrel{\&OverBar;}{\mathrm{\&mu;}},{\mathrm{\&phi;}}_j)$ 表示x_i- μ(i＝1，2，…，M)在特征向量φ_j(j＝1，2，…，k)上的投影。

②计算准方差(σ_j ⁺)²和(σ_j ^-)²：

${\left({\mathrm{\&sigma;}}_j^{+}\right)}^2=\frac{1}{\left|S_j^{+}\right|}\underset{u\&Element;S_j^{+}}{\mathrm{\&Sigma;}}{u}^2$

${\left({\mathrm{\&sigma;}}_j^{-}\right)}^2=\frac{1}{\left|S_j^{-}\right|}\underset{u\&Element;S_j^{-}}{\mathrm{\&Sigma;}}{u}^2$

③采用非对称模型刻画选定的优势主向量上的参数分布，采用特征值-特征向量表达方式计算改进后的马氏距离：

$\stackrel{\stackrel{\&OverBar;}{\&OverBar;}}{d}\left(x\right)=\underset{j=1}{\overset{N}{\mathrm{\&Sigma;}}}\frac{1}{{\mathrm{\&sigma;}}_j}{(x-\stackrel{\&OverBar;}{\mathrm{\&mu;}},{\mathrm{\&phi;}}_j)}^2$

其中，

以下进一步提供本发明马氏距离计算的实施例：

本发明在UCI手写体数字字符集(C.Blake，E.Keogh and C.J.Merz.UCI机器学习数据库.Irvine，CA：加州大学信息与计算机科学系.1998)上进行了实验。该数据库共包含5620个字符样本，将其中训练集中的3823个样本用于训练，测试集中的其余1797个样本用于测试。为减小图像的尺寸，共计算8×8＝64个像素，其中每个像素值等于原图像中4×4块中各像素值之和。基于训练集样本计算10类(0-9)字符的次特征值补偿值及优势主向量的非对称分布参数(准方差)。计算每一个测试样本到所有类别均值矢量的改进马氏距离，用最小距离分类器进行分类决策。本发明的方法在不同的thr值下进行识别率测试，结果参见表1。表2出了不同thr取值条件下各类的k值(优势主向量的数量)。而且，本发明的方法与现有的一些其它方法进行了识别性能比较，包括马氏距离，采用欧氏距离为测度指标的K-NN算法。比较实验的结果列于表3中。

表1中的识别率数据表明，本发明算法的识别性能随补偿阈值thr的变化而变化，当thr＝0.97时，识别率达到最大值，98.39％。显然，对应于thr＝1.00的识别率等于采用马氏距离的识别率。从表2容易看出，各类的优势主向量的个数随thr变化，类别3，6，8的原始协方差矩阵是奇异矩阵，因为它们非0特征值的个数小于特征矢量的维数，因此，在计算输入特征矢量到上述三类的马氏距离时，需要采用它们各自协方差矩阵的伪逆矩阵。从表3可以看出，本发明改进的马氏距离的分类性能明显优于马氏距离，而且超过采用欧氏距离为测度指标的K-NN算法。最后应该指出，在识别阶段本发明的算法与其它方法相比，不需要额外的计算开销。

表1

不同thr条件下的识别率结果(％)

thr(％)

96

96.5

97

97.5

98

99

100

识别率

98.16

98.16

98.39

98.16

98.16

97.94

94.71

表2

不同thr取值条件下各类的k值

表3

不同算法的识别率比较(％)

马氏距离	改进的马氏距离		K-NN(采用欧氏距离测度)
						thr＝0.97	thr＝0.98	K＝1	K＝2	K＝3
	94.71	98.39	98.16	98.00	97.38						97.83

Claims (7)

1、一种有限字符样本集上特征值误差补偿及参数分布修正方法，其特征在于，根据设定的阈值分别选择每类的主特征值，其余为次特征值，对应于主特征值的特征向量为优势主向量，对应于次特征值的特征向量为次主向量，以最小的主特征值替换次特征值，并采用非对称模型描述特征矢量在优势主向量上的分布，分别用于减小次主向量空间和优势主向量空间导致的总体距离偏差来实现误差补偿及参数分布修正。

2、根据权利要求1所述的有限字符样本集上特征值误差补偿及参数分布修正方法，其特征是，具体步骤如下：

(1)计算各类样本的均值特征矢量和协方差矩阵；

(2)对协方差矩阵进行对角化；

(3)根据设定的阈值分别选择每类的主特征值，其余为次特征值，通过采用最小的主特征值替换所有的次特征值对次特征值进行误差补偿；对应于主特征值的特征向量为优势主向量，对应于次特征值的特征向量为次主向量；

(4)根据非对称假设计算优势特征向量上的准方差，准方差表示参数在均值特征矢量两侧分布的离散程度，并描述了参数在均值特征矢量两侧分布的非对称性；

(5)采用上述计算得到的准方差和修正后的特征值替换传统马氏距离计算中的相应的特征值项，完成对马氏距离计算的修正。

3、根据权利要求2所述的有限字符样本集上特征值误差补偿及参数分布修正方法，其特征是，所述的步骤(1)中的均值特征矢量和协方差矩阵，这两个参数描述样本在特征矢量空间的分布状况，是本发明进行特征值误差补偿及参数分布修正的基础。

4、根据权利要求2或者3所述的有限字符样本集上特征值误差补偿及参数分布修正方法，其特征是，所述的步骤(1)中的均值特征矢量和协方差矩阵，均值特征矢量表示该类的质心，协方差矩阵表示该类样本分布的离散程度。

5、根据权利要求2所述的有限字符样本集上特征值误差补偿及参数分布修正方法，其特征是，所述的步骤(2)，通过PCA对描述数据的原坐标系进行正交变换，得到特征向量矩阵和特征值矩阵，有效地提取这些数据的结构。

6、根据权利要求5所述的有限字符样本集上特征值误差补偿及参数分布修正方法，其特征是，所述的特征向量矩阵表示描述数据的新坐标系，描述数据的新坐标值被称为主向量，特征值则表示相应主向量上参数分布的离散程度，误差补偿及参数分布修正是在主向量空间进行的。

7、根据权利要求2所述的有限字符样本集上特征值误差补偿及参数分布修正方法，其特征是，所述的步骤(3)中的次特征值，对由于有限样本导致的次特征值误差进行补偿，可以显著减少马氏距离在次主向量空间的误差。