基于混淆矩阵和Fisher准则构造层次化分类器?
张 静+, 宋 锐, 郁文贤, 夏胜平, 胡卫东 (国防科学技术大学 ATR重点实验室,湖南 长沙 410073)
?
Construction of Hierarchical Classifiers Based on the Confusion Matrix and Fisher’s Principle
ZHANG Jing+, SONG Rui, YU Wen-Xian, XIA Sheng-Ping, HU Wei-Dong
(State Laboratory of Automatic Target Recognition, National University of Defense Technology, Changsha 410073, China) + Corresponding author: Phn: +86-10-66356573, Fax: +86-10-64836117, E-mail: ben_bbzj@126.com
Received 2004-03-31; Accepted 2004-10-09
Zhang J, Song R, Yu WX, Xia SP, Hu WD. Construction of hierarchical classifiers based on the confusion matrix and Fisher’s principle. Journal of Software, 2005,16(9):1560?1567. DOI: 10.1360/jos161560
Abstract: Determination of the hierarchical relationship and the objective patterns of sub-classifiers is a primary problem in the construction of a hierarchical classifier. In this paper, a method focusing on the similarities between patterns is proposed to generate a hierarchical structure automatically. Firstly, a similarity measurement utilizing the confusion matrix is advanced to avoid the drawbacks of the traditional measurements, such as high computation costs and invalidity of preliminary conditions. Then abiding by Fisher’s Principle, a Patterns’ Similarity Relationship Analyzing Machine (PSRAM), which is integrated with the supervised and unsupervised pattern recombination methods, is designed to adaptively construct the structure of a hierarchical classifier. Various tests are testified that the proposed method is effective and practical, and it can prominently improve the performance and robustness of the hierarchical classifier. Key words:
hierarchical classifier; similarity measurement; patterns’ similarity relationship analysis machine; Fisher’s principle; adaptive pattern combination
摘 要: 构造层次化分类器的首要环节是确定各个子分类器的层属关系及其内部组成.从模式间的相似关系入手,实现了一种自动产生层次化分类器结构的方法.为了描述模式间的相似关系,首先提出利用混淆矩阵度量相似性的思路与方法,避免了现有常用度量方法计算量大、假设条件难以成立的不足.进而遵循Fisher准则,设计并实现了模式相似关系分析机(patterns’ similarity relationship analyzing machine,简称PSRAM),将有师指派和无师自组两种常用的模式重组方法有机结合起来,自适应地产生层次化分类器结构.大量测试证实,该方法有效、实用,可以显著地提高分类器的识别性能和稳健性. 关键词: 层次化分类器;相似性度量;模式相似关系分析机;Fisher准则;自适应模式组合 中图法分类号: TP18 文献标识码: A
层次化分类器由一系列子分类器按照一定的组织结构和层属关系共同构成.它将复杂的多模式识别问题分解成多个不同层次上、相对简单的针对较少模式的识别问题,从而达到降低分类难度、分而治之的目的[1?3].设计层次化分类器,首先需要解决多模式的重新组合问题,确定各个子分类器的层属关系及其内部组成[1,2].目前常用的方法可分为两种思路:有师指派,即领域专家根据背景知识确定模式重组方案;无师自组,即通过不同的聚类算法产生模式组合关系.然而,前者常存在结构单调、主观性强等缺陷,而后者则存在不可控因素多、性能不稳定等不足,需要将两种思想有机地结合起来,建立合理的层次化分类器结构
[1,2]
.
? 作者简介: 张静(1977－),女,河北唐山人,博士,助理研究员,主要研究领域为机器学习,雷达目标识别,建模与仿真,武器装备论证;宋锐(1975－),男,
博士,讲师,主要研究领域为雷达目标识别,系统集成;郁文贤(1964－),男,博士,教授,博士生导师,主要研究领域为智能信号处理,目标识别,信息融合;夏胜平(1969－),男,博士,副教授,主要研究领域为雷达目标识别,机器学习,智能信号处理;胡卫东(1967－),男,博士,教授,主要研究领域为信息融合,目标识别,智能信号处理,系统集成.
Fisher准则指出,当模式样本具有最小类内距离和最大类间距离时,将具有最佳的分类效果.着眼于设计合理的层次化分
[4]
类器结构,提高重聚类后的类内一致性和类间可分性,本文提出并实现了一种基于模式间相似关系(similarity relationship,简称SR)自适应地构造分类器层次结构的方法,以模式在判决域中表现出的相似性为切入点,基于Fisher准则产生模式组合的依据和准则.该方法有效地综合了有师和无师方法,具有原理简单、可实施性强、稳定性高的优点.
本文第1节首先分析了多种常用的模式间相似性度量方法及其不足,然后设计了一种利用混淆矩阵对相似性进行度量的方法.第2节在对有师和无师两类模式重组方法的优缺点进行分析的基础上,基于上述度量,采用模块化思想设计了模式相似关系分析机PSRAM(patterns’ similarity relationship analyzing machine),自适应建立层次化分类器的组织结构.第3节通过多个雷达目标识别场景中的大量实测数据,对本文提出的方法与常规层次化方法进行了综合测试和比较分析,验证了本文所提出方法的有效性、实用性和稳定性.第4节对本文工作进行了总结说明.
1 模式间相似性的度量
1.1 常用的模式间相似性度量方法
在模式识别中,各个类型之间通常具有不同程度的相似性,这决定了识别问题的难度和判决结果的质量.当相似的模式种类少且相似程度低时,模式之间的可分性较好,有利于识别问题的完成;而当相似的模式种类多且相似程度高时,模式之间的可分性差,进行识别的难度就高.因此,需要建立对模式间相似性进行度量的方法和准则,掌握具体问题背景下各个模式之间的相似程度,从而指导分类器的构造过程.
相似性属于抽象概念,难以直接定量求取.现有的方法主要从下面3个角度?1SB,SB方法,如离差矩阵SW,SB,ST及其变换TrSW[1,2,4]
??对其进行描述:基于特征空间几何距离的
SW等;基于模式概率分布的方法,如Bhattacharyya判据JB、Chernoff
判据JC、散度判据JD等,以及基于后验概率的方法,如Shannon熵可分性判据JH和计算更为简便的广义熵判据等.上述各种判据能够从不同角度描述模式之间的相似性,在理论分析与实际应用中发挥了一定作用.
但是在实际应用中,度量模式间相似性的方法应同时达到前提条件的可满足性和计算方法的可实施性这两个要求,而上述方法却不具备这样的性质[5].例如,当样本数量多、特征空间维数高时,基于特征空间距离测度的判据运算代价相当大,且难以完全避免特征相关所造成的影响;基于模式概率分布的判据要求模式概率分布已知,这一前提条件在实际问题中往往难以满足,通常只能建立在假设条件基础上;基于后验概率的判据,遵循熵的基本原则,更适合于刻画整个聚类问题的不确定性,而并非两两模式之间的相似性.针对上述问题,本文利用混淆矩阵,设计了一种简捷、实用的度量模式间相似性的方法. 1.2 基于混淆矩阵度量模式间相似性 1.2.1 混淆矩阵
混淆矩阵是模式识别领域中一种常用的表达形式.它描绘样本数据的真实属性与识别结果类型之间的关系,是评价分类器
性能的一种常用方法.假设对于N类模式的分类任务,识别数据集D包括T0个样本,每类模式分别含有Ti个数据(i?1,...,N).采用某种识别算法构造分类器C,cmij表示第i类模式被分类器C判断成第j类模式的数据占第i类模式样本总数的百分率,则可得到N?N维混淆矩阵CM(C,D):
?cm11??cm21?CM(C,D)???cmi1???cm?N1cm22cm22...cmi2...cmN2...cmii...cm1i...cm2i...cm1N??...cm2N??...?
...cmiN??...?...cmNN?? (1)
...cmNi混淆矩阵中元素的行下标对应目标的真实属性,列下标对应分类器产生的识别属性.对角线元素表示各模式能够被分类器
C正确识别的百分率,而非对角线元素则表示发生错误判断的百分率.
通过混淆矩阵,可以获得分类器的正确识别率和错误识别率: 各模式正确识别率:
平均正确识别率:
各模式错误识别率:
Ri?cmii,i?1,...,N
N(2)
RA???cmii?Ti?T0
i?1(3)
平均错误识别率:
Wi?j?1,j?i?cmij?1?cmii?1?Ri ??cmij?Ti?NN(4)
WA??NT0?1?RA
(5)
i?1j?1,j?i1.2.2 基于混淆矩阵的模式间相似性度量
利用混淆矩阵,除了可以获得分类器正确/错误识别率等指标以外,还可以发现那些容易发生错误判断的模式类型.然而,由式(2)~式(5)可知,错误识别率均可以通过正确识别率得到.这意味着,人们通常仅利用了混淆矩阵中的N个对角线元素,却忽视了N(N?1)个非对角线元素,损失了其中所蕴含的反映模式之间相似性的丰富信息.
在模式识别过程中,如果某两种模式之间比较相似,那么它们的样本就容易被判定为对方类型.假设模式i与模式j的相似性强,而与模式k的相似性弱,那么相对于cik和cki而言,cij和cji的取值将会较大,而cik和cki则较小甚至为0.由此,可以推出下面的结论:
结论. 混淆矩阵行向量Ci(i?1,...,N)代表了模式i的对象在进行分类时对各模式的倾向性.
进而,分析行向量Ci与Cj之间的关系,能够发现模式i和模式j在判决倾向性上所表现出来的一致性及相悖性.这从本质上看,是模式i和j之间相似性的表现和延伸.因此,可以从混淆矩阵入手,建立某种度量,描述不同模式间相似性的强弱.Ci和Cj之间的距离测度和矢量夹角,分别表示了它们之间的空间距离和相关性[6],均可被用来度量模式之间的相似性.若二者相距
近,则相似性强;若相距远则表明相似性弱.若二者的夹角小,也意味着相似性强;若夹角大则说明相似性弱.本文以L2范数为例来说明如何基于混淆矩阵进行度量.
由L2测度的定义[6],可以得到混淆矩阵CM(C,D)的L2测度矩阵LM2.LM2为N?N方阵,其元素lmij与cmij,i,j?1,...,N具有如下关系:
i?j?0,?Nlmij??
(Ci?Cj)2??(cmik?cmjk)2,i?j?k?1?(6)
可见,LM2矩阵为一个对角线元素为0的对称矩阵.因此,为了便于计算,只需分析其上三角部分的元素,而将其下三角元素置为0,则得到相似性度量矩阵(similarity measurement matrix,简称SMM),记为TM2.lmij取值越小,说明模式i与模式j的相似性越强,识别过程中这两类模式之间也就越容易发生错误判断;反之,lmij取值越大,模式i与模式j的相似性就越弱,也就越不容易产生错误判断.
2 模式相似关系分析机PSRAM
确定各层子分类器的层属关系及其内部组成,是层次化分类器设计的重点和难点.只有合理的层次化结构,才能提高模式重新聚类后的类内一致性和类间可分性,有效达到分而治之的目的,降低分类器构造和维护中的风险与代价. 2.1 常用层次化结构确定方法的不足
确定层次化分类器的组织结构,即对多种模式类型进行重新组合和聚类,既可以按照有师指派方式产生,也可以根据无师自组的方式进行[2].有师指派是指领域专家根据相关背景知识,将多个类型分别组合成不同的群体[3],比如在舰船目标识别中可以根据吨位(大/中/小型)将模式进行重组.无师自组则采用无师聚类的思想设计分类器,由一定量的实验样本数据自动产生组合方案[5].可见,有师指派是一种针对问题应用领域进行分析的方法,而无师自组则主要是一种着眼于模式特征域的手段,在实际中这两种方式都具有广泛的应用.
通常,模式识别是基于特征空间进行的[2].如果仅根据其应用领域的情况,主观地指定聚类/组合方案,而不考虑模式的特征分布,往往是不够合理的.有师指派产生层次化分类结构就存在这种主观性强、结构单一的问题.而无师自组的方式,由于其运算处理过程自动完成,存在一定的不可控性和较强的不稳定性.为此,需要将两种方法结合起来,使层次化分类器的结构既包含先验信息的指导,也能反映出不同模式在特征空间中的分布情况.
鉴于此,我们设计了一个模式相似关系分析机PSRAM,自适应地确定层次化分类器的结构. 2.2 模式相似关系分析机PSRAM
图1为PSRAM的原理框图.图中实线框表示分析机中各个组成模块,虚线框表示各个处理环节所产生的输出结果.
相似程度描述器D也称为预分类器,它是一个计算快捷、易于实现的单分类器,如基本Bayes分类器等.预分类器对样本数据进行识别,产生分类的混淆矩阵,从中获取模式相似性指标(如平均正确率RA、错误率WA等)以及相似性度量矩阵SMM.预分类器
Sample data Describer D (pre-classifier) Indices of SR SMM Analyzer A Nearest neighbor Graphic theory Rule-Based method … Adaptive combination scheme P Trigger 并不需要达到很高的正确识别率.这是因为,一方面,它只需刻画模式间的基本相似性而无须完成最终的识别任务;另一方面,若达到较高的识别性能,通常需要较多数量的样本和较为复杂的算法,这将增加运算的代价.
Fig.1 Block diagram of PSRAM 图1 模式相似关系分析机原理框图
模式相似性指标用于控制是否启动相似性分析器A.若该指标,如RA,超过一定门限,则表明简单的分类器即可达到较高的正确率,故不必建立层次化的分类结构;如果RA不足某个标准,则表明当前的预分类器和样本数据可能尚不足以描述模式之间的相似性,需要对预分类器进行调整或者增加样本数量.在这两种情况下,均不应启动分析器A.只有当RA处于特定范围时,才通过触发开关开启分析器A,将相似性度量矩阵传递给它.
在相似性分析器A中,可以采用多种方法对SMM进行处理.由第1.2.2节可知,SMM中的各个元素将不同模式在判决域中所具有的多维分类倾向性之间的关系映射成一维距离量.因此,许多基本的模式识别方法可以直接用来对这个简单的一维物理量进行分析.例如,基于最近邻的方法[4]根据lmij的不同取值采用基本k均值法即可将距离近的类型组合在一起;基于图论的方法[7]将各个模式类型定义为图中的节点,lmij定义为各个节点间的连接长度,从连接图中获得相应的分割;基于规则的方法[8]制定若干准则,判断模式之间是否相似,从而形成组合方案P.本文以基于规则的分析方法为例进行讨论. 2.3 模式组合规则
首先,按照式(7)对相似性度量矩阵TM2进行归一化处理,得到矩阵TMU.
tmU,ij?lmijtmax,其中,tmax?maxi,j(lmi,j)
(7)
然后,设定相似门限?和相异门限?,这通常由实际样本情况和经验共同决定. 进而,按照如下规则对模式进行自适应重组:
规则1. 若tmU,ij??,则模式i与模式j相似,将二者进行组合,记为可组合模式集Gm?{Ci,Cj}. ??{Ci,Cj}. 规则2. 若tmU,ij??,则模式i与模式j相异,不易发生混淆,记为不可组合模式集Gn规则3. 对于两个可组合模式集Gm1,Gm2,若Gm1?Gm2??,则将二者合并.
规则4. 对于??tmU,ij??的模式i,j,由于二者较为相似,需要根据已有可组合模式集G和不可组合模式集G?,确定它们的“归属”.
规则4.1. 若??tmU,ij??,且同时存在一个可组合模式集G?{Ci,Ck}和一个不可组合模式集G??{Cj,Ck},则模式j不可添加进可组合模式集G中.
规则4.2. 若??tmU,ij,tmU,ik??,且同时存在可组合模式集G1?{Cj,Ck},G2?{Ci,Ch},只有当tmU,hj, tmU,hk均小于?时方可进行组合.
至此,经过PSRAM的处理,产生了基于相似性的自适应模式重组聚类方案.根据这种组合关系,可对各个聚类分别设计子分类器,建立起层次化的分类结构.由于子分类器的任务相对简化,计算代价有所降低,故可以采用算法相对复杂但准确性更高的方法,如大规模神经网络[9]、支撑向量机SVM[10]、遗传算法[5]等.
3 实验分析
3.1 实验数据说明
本文采用从某现役对海警戒雷达上实际测量得到的8类舰船目标的视频回波序列作为实验数据.不同类型的舰船目标由于吨位、结构、材质不同,其雷达回波具有一定的规律性[11,12].但由于受到目标位置、姿态、运动状态、气象及海面状况等多种因素的影响,同一类型目标的雷达回波常表现出较大的差异性,而不同类型目标的回波也可能具有很强的相似性[12].对于这种复杂的多类目标雷达回波,采用单一结构的分类器很难达到良好的分类性能和稳健的泛化能力,必须采用层次化识别方法,将复杂问题分解为多个简单子问题[5,11].
