公开/公告号CN101334843A
专利类型发明专利
公开/公告日2008-12-31
原文格式PDF
申请/专利权人 中国科学院自动化研究所;
申请/专利号CN200710118156.X
申请日2007-06-29
分类号G06K9/46;
代理机构北京中博世达专利商标代理有限公司;
代理人申健
地址 100080 北京市海淀区中关村东路95号
入库时间 2023-12-17 21:15:08
法律状态公告日
法律状态信息
法律状态
2018-07-20
未缴年费专利权终止 IPC(主分类):G06K9/46 授权公告日:20100825 终止日期:20170629 申请日:20070629
专利权的终止
2010-08-25
授权
授权
2009-02-25
实质审查的生效
实质审查的生效
2008-12-31
公开
公开
技术领域
本发明涉及模式识别领域,特别涉及模式识别中的特征提取方法及装置。
背景技术
模式是通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息;把模式所属的类别或同一类中模式的总体称为模式类(或简称为类)。而“模式识别”则是在某些一定量度或观测基础上把待识模式划分到各自的模式类中去。
模式识别的研究主要集中在两方面,即研究生物体(包括人)是如何感知对象的,以及在给定的任务下,如何用计算机实现模式识别。
一个计算机模式识别系统基本上由三个相互关联而又有明显区别的过程组成,即数据生成、模式分析和模式分类。数据生成是将输入模式的原始信息进行量化处理,转换为向量,成为计算机易于处理的形式。模式分析是对数据进行加工,包括特征选择、特征提取、数据维数压缩和决定可能存在的类别等。模式分类则是利用模式分析所获得的信息,对计算机进行训练,从而制定判别标准,以期对待识模式进行分类。
其中模式分析中的特征提取对于高效的模式分类是非常重要。模式分类涉及到各个领域,如图像分类、语音识别、生物技术、医学等。分类的效率始终是模式分类研究的重要内容,在很多实际问题中,可进行模式分类研究的特征变量非常多,如果将所有可供参考的特征变量都考虑进去进行分类,那么效率将非常低,在实际中无法使用。因此,需要对特征变量进行提取,将经特征提取得到的特征子集作为客观分类器的输入,经过对客观分类器训练,利用特征子集进行分类,从而提高分类的效率。
特征提取是基于搜索一个使信息损失量最小的特征子空间,信息量是通过特征子空间和类变量之间的互信息来度量,特征提取方法不但考虑特征变量与类变量之间的相关性,而且考虑特征变量之间的相关性。
特征提取可应用在中医学中。辨证论治是中医的核心,辨证是利用中医理论来理解和诊断疾病的一种方法,证候是未知病因的症状复合体,是机体发生异常的表征。广义的症状不但包括四诊信息,还包括性别、体质、情绪、压力、饮食、生活习惯等众多因素。在辨证过程中,因为有太多的症状体征,医生很难将所有观察到的症状都考虑进去。不同的症状体征在辨证过程中起不同的作用,如何找出包含信息量最大的症状体征集合作为某种证候的辨证标准是中医界非常重要的问题。
特征提取同样可应用于数字图像的模式识别。数字图像的模式识别是根据图像的像素灰度值进行模式分类的,一幅图像的像素量很多,如常用的1280×960像素、640×480像素、320×240像素、160×120像素等,如果在模式分类中将所有的像素作为模式分类器的输入,那样的效率将非常低。因此特征提取对于图像的模式分类也是非常重要的研究内容。在图像的特征提取中,将每个像素看作是一个特征变量,选取出对于模式分类最有用的像素作为客观分类器的输入。
关于特征变量提取的方法。相关分析是选择信息量大的特征集合的基础,特征变量可以根据它们与类变量的相关度值进行选择。
目前有多种分析相关的统计方法,最简单的方法是相关系数法,但该方法只适用于分析线性相关问题,而许多实际中的问题都是非线性关系。通常使用的非线性统计分析方法是逻辑(logistic)回归法,该方法需要特征变量之间是相互独立的,而实际的很多问题难以满足这个条件。更重要的是logistic回归方法的回归系数不能够直接反映特征变量与类变量之间的相关度值,要用胜算比(odds ratio,OR)值来确定,并且OR值没有实际的物理意义。主成分分析方法和因子分析方法也可用于相关性分析,这两种方法也只能分析变量之间的线性关系,不能度量变量之间任意的相关性。
基于熵的互信息方法则不但可以分析数值变量(离散变量和连续变量)之间的相关性,而且可以度量变量之间的任意相关性。互信息是熵理论中的核心概念之一,是非线性复杂系统自适应性的重要测度,其实质是事物之间的信息传递,随机变量之间的统计相关性,已被应用到很多领域,特别是模式识别领域。
与传统方法相比,基于熵的互信息主要有以下优点:
1)它既可以度量变量之间线性相关性又可度量变量之间的非线性相关性;
2)与logistic回归非线性分析方法相比,基于熵的互信息方法对分析的变量没有互相独立的条件限制;
3)基于熵的互信息方法不但可以分析数值变量(离散变量和连续变量)之间的相关性,而且可以度量分级变量、符号变量之间的相关性。
最优的特征选择方法,是将所有的特征组合都评估一遍,这通常会产生组合爆炸问题,因此研究有效的特征提取方法是非常重要的问题。目前,已经有很多学者从事这方面的研究,几种有效的特征提取方法已被提出,用来解决组合问题。但在这些方法中,选择的特征个数通常被预先人为指定,这样势必引入个人的主观性,因此,不是一个好的截尾准则。
发明内容
本发明的目的之一在于提一种模式识别中的特征提取方法,能够有效避免预先指定选择的特征个数的主观性。
为达到上述目的,本发明采用的技术方案为:
该模式识别中的特征提取方法,包括步骤:
根据样本的模式原始信息确定离散的特征变量与类变量,并对该特征变量与类变量进行预处理;
设定联合贡献度阈值;
确定特征变量的组合与类变量的联合贡献度;
获取所述联合贡献度大于或等于所设定联合贡献度阈值的特征变量的组合。
在现有的特征提取方法中,选择的特征个数通常被预先人为指定,这样势必引入个人的主观性。基于这个问题,本发明提出了一种新的基于互信息的贡献度定义形式,用指定联合贡献度的阈值代替指定特征个数作为特征提取的截尾准则。根据所指定的联合贡献度的阈值,提取联合贡献度大于或等于所设定联合贡献度阈值的特征变量的组合,从而获得一个使信息损失量最小的特征子空间,这样能有效避免以往特征提取中的主观性。
本发明的另一目的在于提一种模式识别中的特征提取装置,能够有效避免预先指定选择的特征个数的主观性。
为达到该目的,所采用的技术方案为:
该模式识别中的特征提取装置,包括:
数值预处理模块,用于根据样本的模式原始信息确定离散的特征变量与类变量,并对该特征变量与类变量进行预处理;确定每个特征变量可能的取值,确定类变量可能的取值,设定特征子集,并把该特征子集初始化为空集;
阈值设定模块,用于设定联合贡献度阈值;
联合贡献度确定模块,用于确定特征子集与类变量的联合贡献度;
特征提取模块,用于根据该联合贡献度,获取联合贡献度大于或等于所设定联合贡献度阈值的特征子集。
在现有的特征提取中,选择的特征个数通常被预先人为指定,这样势必引入个人的主观性。基于这个问题,本发明提出了一种新的基于互信息的贡献度定义形式,用设定模块所预先设定的联合贡献度的阈值代替指定特征个数作为特征提取的截尾准则。通过联合贡献度确定模块来确定特征子集与类变量的联合贡献度,根据设定模块所预先设定的联合贡献度的阈值,由特征提取模块提取联合贡献度大于或等于所设定联合贡献度阈值的特征子集,从而获得一个使信息损失量最小的特征子空间,这样能有效避免以往特征提取中的主观性。
附图说明
图1为本发明模式识别方法的流程图;
图2为本发明模式识别装置的系统框图;
图3为本发明实施例中每个症状与证候之间的互信息示意图;
图4为本发明实施例中每个症状的贡献度示意图;
图5为本发明实施例中选择症状的联合贡献度示意图。
具体实施方式
为了更好地理解本发明,下面结合附图和具体实施方式对本发明作详细说明。
特征提取是要选择最重要的特征组合,使其信息损失量达到最小,从实用的角度出发,可以节省大量的分类处理时间。
本发明提出了一种基于新的截尾准则的特征提取方法和装置,这主要是针对离散变量的特征提取。在该特征提取方法和装置中,定义了一种新的基于互信息的联合贡献度形式,用指定联合贡献度的阈值代替指定特征个数作为特征提取的截尾准则,提取联合贡献度大于或等于所设定联合贡献度阈值的特征变量的组合,从而获得一个使信息损失量最小的特征子空间,这样能有效避免以往特征提取中的主观性,同时,本发明提出的基于样本量的计算联合互信息的方法,能大大降低计算量。
一种新的基于互信息的贡献度定义如下:
定义:设I(Xi;Y),i=1,2,…,n表示每个特征变量与类变量之间的互信息,I(X;Y)表示总的联合互信息,每个特征变量的基于互信息的贡献度定义为:
ri=I(Xi;Y)/I(X;Y),i=1,2,…,n
特征变量集X的子集S与类变量Y之间的联合贡献度为:
rs=I(S;Y)/I(X;Y)
说明:根据基于香农熵互信息的性质,特征变量越多,与类变量之间的互信息越大,因此,贡献度与联合贡献度的取值范围在[0,1]之间。
基于联合贡献度的特征提取具体操作方法介绍如下:
给定一个已选择的特征子集S,该算法从特征集合X中选择下一个特征变量要满足该特征变量加入到S中生成的新的特征子集S←{S,Xi}与类变量之间的互信息最大。一个特征变量要被选择,那么该特征变量所提供的信息不应该在已选的特征子集S中包含。例如,如果两个特征变量Xi和Xj是高度相关的,那么I(Xi;Xj)的值就很大,当其中一个变量被选中,则另一个变量被选中的机会将大大降低。
本发明模式识别中的特征提取方法,包括步骤:根据样本的模式原始信息确定离散的特征变量与类变量,并对该特征变量与类变量进行预处理;设定联合贡献度阈值;确定特征变量的组合与类变量的联合贡献度;获取所述联合贡献度大于或等于所设定联合贡献度阈值的特征变量的组合。
参考图1所示,结合中医的辨证论治问题,本发明模式识别中的特征提取方法,用于对从人体观测到的中间症状信息进行处理,包括如下具体步骤:
步骤一、根据样本的模式原始信息确定离散的特征变量与类变量,并对该特征变量与类变量进行预处理;将所有特征变量组合为特征变量集,并确定每个特征变量可能的取值;确定类变量可能的取值;设定特征子集,并把该特征子集初始化为空集。
分析1022份血瘀证临床数据。在这些数据里记载了71个人体症状,这些症状所对应的取值也就是模式原始信息,所有症状都用离散的特征变量表示,其中,一些症状(特征变量)有两个值,用取值0,1表示,一些症状(特征变量)有四个值,用取值0,1,2,3表示;中医的证候用类变量表示,该类变量有五个值,分别代表中医的五个证候:气虚血瘀、气滞血瘀、阳虚血瘀、痰瘀互阻、瘀血阻络。
步骤二、设定联合贡献度阈值。
该阈值的取值范围为[0,1].具体的取值通常根据实际需求进行确定,阈值越大,提取的症状数越多,根据经验,该阈值的取值范围一般为[0.9,0.98]。本实施例中的联合贡献度的阈值指定为0.95。
步骤三、确定症状的组合与症候之间的联合贡献度,具体包括如下步骤:
S300、确定每个症状与症候之间的互信息;
S301、确定使症状与证候之间的互信息最大的症状,将该症状从症状集合中去除,并加入到特征子集中;
S302、确定该特征子集与证候的联合贡献度。
其中,在步骤S300中,每个症状与证候的互信息是通过公式:
每个症状与证候的互信息公式是这样的得来的:
设n个特征变量用集合X={X1;X2;…;Xn}表示,其概率密度函数分别为p(x1),p(x2),…,p(xn)。
类变量Y的Shannon熵可表示为:
特征变量Xi和类变量Y之间的联合熵可表示为:
其中Xi可用特征变量集X的一个子集来代替,即联合熵可推广到n个特征变量的情况。类变量Y与特征变量Xi之间的互信息可表示成:
其中Xi可用特征变量集X的一个子集来代替。
特征变量、类变量和它们的联合概率分布是通过统计的方法获得的,具体为:
令n个特征变量用集合X={X1,X2,…,Xn}表示,变量Xi有mi个值,即
这时,特征变量、类变量和它们的联合概率分布就可以通过统计的方法获得,即
通过计算每个症状与证候之间的互信息如图3所示。
在步骤S300与步骤S301之间还有步骤:从症状集合中除去与证候的互信息小于预定值的症状。
通过上述互信息计算公式得的到每个症状与症候的互信息后,一些症状的互信息非常小,因此这些症状可以被忽略,对保留下来的症状集合进行特征提取,而且这不会对正确分类产生太大的影响,这样可大大节省特征提取的时间。
在步骤S302中,特征子集与证候的联合贡献度是通过公式:
rs=I(S;Y)/I(X;Y)来确定的。
其中,rs表示联合贡献度;
I(S;Y)表示联合互信息,通过公式:
I(X;Y)表示总的联合互信息。
下面介绍关于总的联合互信息的确定方法。
根据贡献度的定义,需要计算症状集合与证候之间总的联合互信息,当用常规的互信息计算方法进行计算时,它的计算量非常大,并且当症状很多时会产生组合爆炸。例如,有30个症状,每个症状有4个取值,它们被映射到2类,那么它需要计算大约1.15×1018个组合值,这在实际运算中是很难完成的。通过统计可以发现,在样本有限的情况下,很多组合的概率为0,因此可通过样本而不考虑具体的症状组合来计算总的联合互信息,下面将介绍该计算方法。
B=(B1,B2,…,BN)T是一个频次向量,表示特征变量(症状)的值都相等的样本数,它的计算过程将在下面描述。D=(Dij),i=1,2,…,N;j=1,2,…,k是一个频次矩阵,表示特征变量(症状)值都相等,同时类变量(证候)的值也相等的样本数,E=(E1,E2,…,Ek)T是一个频次向量,表示类变量(证候)的值相等的样本数。该算法可通过下面的步骤来实现:
步骤S3031:设训练样本T已知,初始化参数:令向量B的所有元素值为1,令矩阵D和向量E的所有元素值都为0。
步骤S3032:下面的程序用来获得计算概率时用到的频次。
设i=1,2,…,N,j=i+1,i+2,…,N
如果Bi=0,那么执行下一个循环;
否则
如果yi=cl,那么El=El+1,l=1,2,…,k;
如果xi=xj,那么Bi=Bi+1,Bj=0;
如果xi=xj和yi=cl,那么Dil=Dil+1,l=1,2,…,k。
步骤S3033:计算总的联合互信息
说明:当Dij×Bi×Ej等于0时,log(Dij/BiEj)=0。
利用该算法,很容易计算总的联合互信息I(X;Y),当样本量不是很大的情况下,计算量可大大的降低。例如,当N=2000,n=30,k=2时,仅需要
通过计算本实施例中71个症状与证候之间总的联合互信息为1.7342。
根据每个特征变量的基于互信息的贡献度的定义,很容易计算每个症状的贡献度,所有症状的单独贡献度如图4所示。
步骤四:获取所述联合贡献度大于或等于所设定联合贡献度阈值的症状的组合,具体包括步骤:
将所确定的联合贡献度与所设定的联合贡献度阈值进行比较,
若所确定的联合贡献度大于或等于所设定的联合贡献度阈值,则获取该特征子集;
若所确定的联合贡献度小于所设定的联合贡献度阈值,则对于症状集合的每个症状分别与特征子集的组合,确定使该组合与证候的互信息最大的症状,将该症状从症状集合中去除,并加入到特征子集中;然后回到步骤三往下执行。
通过特征提取,9个症状被选择,他们的联合贡献度为0.9711,结果如图5所示。选择的循序依次为急噪易怒,偏身麻木,胸闷,失眠,疲乏无力,职业,舌脉曲张,舌质紫暗,面色黑,这意味这着这9个症状的联合贡献度最大,在诊断这五个症候时包含的信息量最多。
为证明所选择的症状组合信息量最大,有效的方法是用这些症状来辨证,这里选用多类支持向量机进行分类,支持向量机的设置为:惩罚参数C=20,核函数选为径向基函数,宽度设为σ2=0.1。863个样本作为训练样本,余下的159个样本作为测试样本,当所有症状作为支持向量机的输入,通过训练,107个样本可以被正确分类,分类正确率为0.6729。当经过特征提取的症状组合作为支持向量机的输入,123个样本可以被正确分类,分类正确率为0.7736。它的正确率高于所有症状作为输入时的正确率是因为在整个症状集合中存在噪音,经过特征提取,噪音可以被降低,因此经过特征提取的症状组合是信息量最大的组合。
在该特征提取实例中如果用常规的互信息计算方法进行计算,会发生组合爆炸,实际中无法实现,而根据这里提出的离散变量互信息的快速算法,本特征提取在2个小时左右就可完成。
本发明另一实例为利用本发明对实时集成电路IC卡数字字符进行识别。
该实例是要实现对生产的IC卡上面打印的卡号进行快速识别,以检验打印的卡号与输入的卡号是否符合。每张卡上打印32个数字,这些打印的数字是由阿拉伯数字0-9组合而成的。
首先通过图像采集卡对IC卡上打印的数字进行采集,生成数字图像,其次通过图像处理方法将打印的数字分割为32个数字区域,每个数字区域的大小为8×10个像素,然后对每个数字区域进行识别,确定其所对应的数字。每秒钟需要处理6张这样的IC卡。
应用本发明模式识别中的特征提取方法,对每个数字区域进行特征提取,包括如下步骤:
S01、根据样本的模式原始信息确定离散的特征变量与类变量,并对该特征变量与类变量进行预处理;将所有特征变量组合为特征变量集,并确定每个特征变量可能的取值;确定类变量可能的取值;设定特征子集,并把该特征子集初始化为空集。
在这里,模式原始信息为IC卡上数字图像中像素点的灰度值,特征变量为数字图像的像素点,类变量为数字值。每一个特征变量(像素点)有2个灰度值0和1,特征变量集合为80个像素点。数字区域可分成10类,即数字0-9。
S02、设定联合贡献度阈值。
本实施例中的联合贡献度的阈值指定为0.95
S03,确定像素点的组合与数字之间的联合贡献度,具体包括如下步骤:
S031、确定每个像素点与数字之间的互信息;
S032、确定使与数字互信息最大的像素点,将该像素点从像素点集合中去除,并加入到特征子集中;
S033、确定该特征子集与数字之间的联合贡献度。
其中,在步骤S031中,每个像素点与数字之间的互信息是通过上述公式:
在步骤S031与步骤S032之间还有一步:从像素点集合中除去与数字的互信息小于预定值的像素点。
通过上述互信息计算公式得的到每个像素点与数字的互信息后,一些像素点的互信息非常小,因此这些像素点可以被忽略,对保留下来的像素点集合进行特征提取,而且这不会对正确分类产生太大的影响,这样可大大节省特征提取的时间。
在步骤S033中,特征子集与数字之间的联合贡献度是通过公式:
rs=I(S;Y)/I(X;Y)来确定的。
其中,rs表示联合贡献度;
I(S;Y)表示联合互信息;
I(X;Y)表示总的联合互信息。
S04,获取所述联合贡献度大于或等于所设定联合贡献度阈值的像素点的组合,具体包括步骤:
将所确定的联合贡献度与所设定的联合贡献度阈值进行比较,
若所确定的联合贡献度大于或等于所设定的联合贡献度阈值,则获取该特征子集;
若所确定的联合贡献度小于所设定的联合贡献度阈值,则对于像素点集合的每个像素点分别与特征子集的组合,确定使该组合与数字之间的互信息最大的像素点,将该像素点从像素点集合中去除,并加入到特征子集中,然后回到步骤S033往下执行。
通过该特征提取方法,只有21个像素点就可以达到预期的识别效果,大大提高了IC卡上所打印卡号的识别效率。
如图2所示,本发明还提供一种模式识别中的特征提取装置,包括:
数值预处理模块10,根据样本的模式原始信息确定离散的特征变量与类变量,并对该特征变量与类变量进行预处理;
阈值设定模块20,用于设定联合贡献度阈值;
联合贡献度确定模块30,用于确定数值预处理模块所设定的特征子集与类变量的联合贡献度;
特征提取模块40,用于根据该联合贡献度,获取联合贡献度大于或等于所设定联合贡献度阈值的特征子集。
其中,所述联合贡献度确定模块30包括:
互信息确定单元301,用于确定每个特征变量与类变量之间的互信息;
最大值确定单元303,用于根据所述互信息,确定使特征变量与类变量之间的互信息最大的特征变量,将该特征变量从特征变量集中去除,并加入到特征变量集的子集中;对于特征变量集的每个特征变量分别与特征子集的组合,确定使该组合与类变量的互信息最大的特征变量,将该特征变量从特征变量集中去除,并加入到特征子集中;
联合贡献度确定单元304,用于确定特征子集与类变量的联合贡献度。
为了节省特征提取的时间,在所述互信息确定单元与最大值确定单元之间还有一过滤单元302,用于从特征变量集中除去与类变量的互信息小于预定值的特征变量。这样,通过上述互信息计算公式得的到每个症状与症候的互信息后,一些症状的互信息非常小,因此这些症状可以被忽略,对保留下来的症状集合进行特征提取,而且这不会对正确分类产生太大的影响,这样可大大节省特征提取的时间。
所述特征提取模块40包括:
比较单元401,用于将所确定的联合贡献度与所设定的联合贡献度阈值进行比较;
提取单元402,用于提取联合贡献度大于或等于所设定的联合贡献度阈值的特征子集。
若比较单元401所确定的联合贡献度大于或等于所设定的联合贡献度阈值,则提取单元402将该特征子集;若比较单元401所确定的联合贡献度小于所设定的联合贡献度阈值,则由互信息确定单元301确定特征变量集的每个特征变量分别与特征子集的组合与类变量的互信息,由最大值确定单元303从中确定使该组合与类变量的互信息最大的特征变量,将该特征变量从特征变量集中去除,并加入到特征子集中;然后由联合贡献度确定单元304确定该特征子集联合贡献度。
所述阈值设定模块所设定的联合贡献度阈值的取值范围一般为[0.9,0.98]。
本发明模式识别中的特征提取方法与装置,主要是针对离散变量的特征提取。在该特征提取方法和装置中,定义了一种新的联合贡献度形式,这种基于联合贡献度的特征提取方法可有效避免以往特征提取方法预先指定选择的特征个数的主观性,并且可以提高提取的速度,能够广泛应用于离散的数字图像信息、指纹信息、脸纹信息、语音信息或手写/印刷字符信息的等的特征提取。
机译: 从用于模式识别的信号中确定特征向量的方法和装置以及用于模式识别的方法和装置以及计算机可读存储介质
机译: 模式识别中的特征选择装置
机译: 模式识别中的特征选择装置