（管理科学与工程专业论文）马田系统在模式识别中的研究与应用.pdf

摘要 特征提取选择是模式识别领域的至关重要的研究课题。它本质上是一个多 因素优化问题，本论文试图应用试验设计的理论方法来解决这一问题。， 马田系统是最早应用正交表试验设计来解决模式识别中的特征选择问题的 方法。它以基于马氏距离的信嗓比为优化目标，应用二水平正交表进行有效特 征的选择。在国外，尤其是日本，早已展开m t s 的应用工作，而对其理论基础 研究很少，应用m t s 的动力更多地是来自田口试验设计方法以往在工程领域的 巨大成功的鼓舞。在国内，应用和研究则都还刚起步。因此，本文试图探求的 m t s 理论基础，为它建立一个合适的数学模型，并以此为指导下，更深入地进 行应用方面的研究。惧体内容如下： 第二章主要介绍了试验设计的基本理论模型和试验设计与多因素优化问题 的联系，为第三章m t s 的数学模型建立提供理论准备。 本章着重介绍正交表的 各种统计最优性和它在多因素优化问题中的应用。讨论了除正交表设计之外的 其它筛选因素试验的设计方法，丰富了m 姆的设计方法。本章还探讨m 稻中 主要使用的二水平正交表的交互作用散布性质，为m t s 中交互作用的处理提供 了理论依据。最后，本章提出几种因素显著性检验方法的特点和应用背景，为 肘硒特征显著性检验提供方法库。 第三章主要为m t s 建立数学模型。在可分性判据指标( 响应指标) 为样本 一阶和二阶矩的函数的假设下，我们指出基于二水平正交表设计的肘四可以建 立在线性统计模型基础之上，当样本量足够大时，还可视为近似等方差模型。 这样就使得m t s 能应用第二章讨论正交表设计的许多优良性质。我们假设的可 分性判据指标的函数形式是相当普遍的，因此，我们为m 塔建立的模型也具有 相当的适用性。本章最后讨论了可分性判据指标值估计的精确度、交互作用以 及显著性检验方法对m t s 的影响。这些问题在实际中经常遇到。y 第四章着重探讨最优特征( 维数) 问题。奉章提出优化特征的几个层次： 基于最高识别l f 确率的最优特征基十最优可分性判据指标值的最优特征和约 摘要 2 0 0 1 年3 月 束条件下的最优特征，文中我们证明了基于最优可分性判据指标值的最优特征 和贝叶斯线性分类器和最小距离分类器下的最优特征。在第二节，利用第一节 讨论结果来指导我们对o r l 人脸图象的有效鉴别特征进行再优化。应用m 搿 我们找到了人脸图象的有效鉴别特征的最优特征。第二节的例子表明m 嬲可以 还可用于特征提取后的特征的验证、评价和再优化。 第五章讨论正交表在多分类器组合中的应用。( 仿照前几章用正交表进行有 效特征选择的做法，本章也应用正交表试验设计进行分类器筛选，我们用筛选 出的有效分类器进行组合获得了多分类器组合的最佳识别率。本章还讨论了 彳弼在多级分类( 串联形式) 的多分类器组合中的特征选择中的应用，通过m 商 的特征选择，串联系统识别率得到显著的改善。此外，后验概率的估计在多分 类器组合中占有重要地位，本章引进了两种估计法，作者证明了它们是极大似 然估计，讨论了其渐进性并将它们应用在多级分类中，取得良好效果。矿 第六章讨论m t s 的具体应用问题。；主要从可分信息的角度来探讨可分性判 据指标对m t s 特征选择的影响，讨论了非参数方法的可分性判据指标和具有可 分信息互补的多个可分性判据指标对m t s 特征选择的改进作用。本节还应用聚 类的方法，用它来帮助m 峦进行特征选择。这些都取得相当好的效果。1 t 关键词：马田系统，试验设计，正交表，模式识别，可分性判据，特征提取7 尬： 择，多分类器组合 堕圭兰焦堕奎 呈里墨堕垄堡塞望型! 竺塑窒兰窒旦 一坠 a b s t r a c t f e a t u r ee x t r a c t i o n s e l e c t i o ni sav e r yi m p o r t a n tr e s e a r c hs u b j e c ti nt h ea r e a o f c o m p u t e rp a t t e r nr e c o g n i t i o ni ti se s s e n t i a l l yaq u e s t i o no f m u l t i v a r i a n to p t i m i z a t i o n w e t r yt os o l v et h i sp r o b l e mb y t h em e a n so f t h et h e o r yo f e x p e r i m e n t a ld e s i g n m t s ( m a h a l a n o b i st a g u c h is y s t e m ) i st h ef i r s tm e t h o do fa p p l y i n ge x p e r i m e n t a l d e s i g ni nf e a t u r es e l e c t i o n i tt a k es n r ( s i g n a l n o i s er a t i o ) b a s e do nm a h a l a n o b i s d i s t a n c e 髂o p t i m i z a t i o no b j e c t i v ea n da p p l y i n go n h o g o n a lt a b l et o s e l e c tf e a t u r e s w h i c ha r ee f f e c t i v ei nr e c o g n i t i o n i no t h e rc o u n t r i e s ，e s p e c i a l l yi nj a p a n , m r sh a s b e e nw i d e l yu s e di nm a n yf i e l d s h o w e v e rt h es t u d yo fm t s st h e o r yi sn o tw e l l d o n e t h em o t i v a t i o no fm t s sa p p l i c a t i o ni sm o r es t i m u l a t e db yt h es u c c e s so f t a g u c h im e t h o d i no u rc o u n t r y , a l lo fw o r ki sj u s ts t a r t e ds ow e t r yt oa s c e r t a i n t h eb a s eo fm t sa n db u i l dam a t h e m a t i c a lm o d e ls ot h a tw ec a nt a k ei ti n t op r a c t i s e m o r e j u s t l y t h em a i n w o r ko f t h i s p a p e r i so u t l i n e da sf o l l o w s i nt h ef i r s tc h a p t e r , t h eb a s i cc o n c e p to f p a t t e r nr e c o g n i t i o n ，e x p e r i m e n t a ld e s i g n a n dm t si si n t r o d u c e d i nt h es e c o n dc h a p t e r , t h eb a s i ct h e o r e t i c a lm o d e lo f e x p e r i m e n t a ld e s i g na n di t s r e l a t i o n s h i pw i t hm u l t i v a r i a n to p t i m i z a t i o na r ei n t r o d u c e dt om a k ep r e p a r a t i o nf o r t h em t s sm a t h e m a t i c a lm o d e lw h i c hw i l lb ed i s c u s s e di nc h a p t e r3 w es t r e s st h e s t a t i s t i c a l o p t i m a lp r o p e r t yo fo r t h o g o n a lt a b l ea n di t sc o n t a c t sw i t hm u l t i - v a r i a n t o p t i m i z a t i o n w ea l s od i s c u s s e do t h e rd e s i g nm e t h o d so fs e l e c t i n gf a c t o r se x c e p tf o r o r t h o g o n a lt a b l ed e s i g n t h ep r o p e r t yo f d i s t r i b u t i o no ff a c t o r s i n t e r a c t i o ni nt w o l e v e lo r t h o g o n a lt a b l ei sa l s os t u d i e dw h i c h p r o v i d ef o u n d a t i o nf o rm t s i nd e a l i n g w i t hf a c t o r s i n t e r a c t i o n a t l a s t ，s o m eu s e f u lm e t h o d so fs i g n i f i c a n c et e s t a r e i n t r o d u c e dw h i c hw i l lb eu s e di no t h e r c h a p t e r s ， m t s sm a t h e m a t i c a lm o d e li sb u i l ti nc h a p t e r3 s t a r t i n go nt h ea s s u m p t i o nt h a t t h ed i s c r i m i n a n tc r i t e r i o ni st h ef u n c t i o no f f i r s ta n ds e c o n d o r d e r m o m e n t & s a m p l e s w ei n d i c a t et h a tm t sb a s e do nt w o l e v e lo r t h o g o n a lt a b l ec a nb ef o u n d e do nl i n e a r s t a t i s t i c a lm o d e l w h e nt h es a m p l es i z ei sv e r yl a r g e , t h em o d e l a p p r o x i m a t e l y c a nb e ! ! 垒! 塑! ! j 坐型旦 r e 迎a r d e da sv a r i a n c em o d e l s ow ec a ns a f e l ym a k eu s eo f t h eo p t i m a lp r o p e r t yo f o r t h o g o n a lt a b l ei nm t s t h ef o r mo fd i s c r i m i n a n tc r i t e r i o ni ss ou n i v e r s a lt h a tt h e c a nb ew i d e l yu s e d ，a tt h el a s tp a r to f c h a p t e r3 , t h ei n f l u e n c eo n m r si sa n a l y z e do f t h ed r e c i s i o no fe s t i m a t eo fd i s c r i m i n a n tc r i t e r i o n ，i n t e r a c t i o n a n dt h em e t h o do f s i g n i f i c a n c et e s t o p t i m a lf e a t u r e i sd i s c u s s e di nc h a p t e r4t h i sp r o b l e mi sp u tf o r w a r di nt h r e e a s p e c ta c c o r d i n gt oo p t i m i z a t i o no b j e c t i v ew h i c h h a st h r e ek i n d s ：t h em i n i m a le r r o r r a t e ，o p t i m a ld i s c r i m i n a n tc r i t e r i o na n do p t i m a ld i s c r i m i n a n tc r i t e r i o nw i t hr e s t r a i n t c o n d i t i o n i nt h ef i r s ts e c t i o no ft h i s c h a p t e r , t h eo p t i m a lf e a t u r e sa r cg i v e nw h i c h o p t i m i z eg e n e r a ld i s c r i m i n a n tc r i t e r i o na n dm i n i m i z et h ee r r o r r a t eo fb a y s i a nl i n e a r c l a s s i f i e ra n dm i n i m u md i s t a n c ec l a s s i f i e r i nt h es e c o n ds e c t i o n ，u n d e rt h eg u i d a n c e o ft h er e s u l to ft h ef i r s ts e c t i o n ，w ea p p l ym t st os e l e c te f f e c t i v ef e a t u r e so fo r l f a c ed a t a b a s ei nt h i sc a s e ，m t si sp r o v e dt oh a v et h ea b i l i t yt ov a l i d a t e ，e v a l u a t ea n d r e o p t i m i z et h ee x t r a c t e df e a t u r e s i nc h a p t e r5 , w ed i s c u s st h ea p p l i c a t i o no fm t si nt h ec o m b i n a t i o no fm u l t i - c l a s s i f i e r st w o l e v e lo r t h o g o n a lt a b l ea r ea g a i nu s e dt of i n dt h ec l a s s i f i e r st h a tm a k e t h ee r r o r - r a t eo fc o m b i n a t i o ns y s t e mm i n i m u mt h eu s eo fm t si nt h es y s t e mo f m u l t i c l a s s i f i e r sw h i c ha r ec o m b i n e di ns e r i e si sa l s od i s c u s s e d t o i m p l e m e n t c o m b i n a t i o no fm u l t i - c l a s s i f i e r s ，t w ok i n d so fm e t h o d o fe s t i m a t eo f p o s t e r i o r p r o b a b i l i t ya r ed i s c u s s e d ，i n c l u d i n gt h e i ra p p r o x i m a t ep r o p e r t i e s t h e ya r ea l s ou s e d i ns e r i a lc o m b i n a t i o ns y s t e m i n c h a p t e r6 ，s o m ep r a c t i c a lp r o b l e m o fa p p l i c a t i o no fm t si s d i s c u s s e d ， i n c l u d i n g t h eu s eo fd i s c r i m i n a n tc r i t e r i o nc o n t a i n i n gc l a s ss e p a r a b l ei n f o r m a t i o n ，a n d c o m p l e m e n t a r y d i s c r i m i n a n tc r i t e r i o nac l u s t e rm e t h o di si n t r o d u c e dt oh e l pm r st o s e l e c te f f e c t i v ef e a t u r e s k e yw o r d s ：m t s ( m a h a l a n o b i st a g u c h i t a b l e ，p a t t e r nr e c o g n i t i o n ，d i s c r i m i n a n t c o m b i n a t i o no fm u l t i - c l a s s i f i e r s s y s t e m ) e x p e r i m e n t a ld e s i g n o r t h o g o n a l c r i t e r i o n ，f e a t u r ee x t r a c t i o n s e l e c t i o n ， 堕主堂焦堡兰 呈里墨堕垄堡塞塑型竺堑壅兰窒旦上 1 绪论 1 1 模式识别概述 模式识别是6 0 年代迅速发展起来的一门学科，7 0 年代随着大规模集成电路 技术以及计算机性价比的迅速提高，无论理论还是应用上，模式识别技术都有 了显著的发展。目前，模式识别己形成完整的理论体系，在国民经济和国防科 学的诸领域发挥着越来越重要的重用 1 1 1 2 】。 模式是取自世界有限部分的单一样本的被测量值的综合；模式识别就是试图 确定一个样本的类别属性。客观世界里存在这样些物体和事件，它们在物理 上可以测量，能够用足够多的函数来描述，它们的可测数据的集合称为物理上 可觉察到的世界。显然，这些可测数据，或者说这个世界的维数是无限多的。 在物理上可觉察到的世界里，适当地选择某些物体和事件，称为样本，对它们 分别进行观测，每个样本的观测数据的综合都构成模式，所有的样本观测数据 构成模式空间。显然，模式空间的维数与所选择的样本和测量方法有关，也与 特定的应用有关，一般说来是很大的。由物理上可觉察到的世界到模式空间所 经历的过程称为模式采集。模式空间的维数虽然有限，但还是很多，其中有些 并不能有效揭示样本类别区分的本质。因此在判别之前要对模式空间的各坐标 进行综合分析，获取最能区分样本类别的观测量作为主要特征，这些主要特征 就构成特征空间。显然，特征空间的维数大大压缩了。相对应地，称模式空间 的各坐标元素为原始特征。由模式空间到特征空间所需要的综合分析，包含适 当的变换和选择，称为特征提取和特征选择。根据某些知识和经验确定分类准 则，称之为判决规则。由判决规则，把特征空间里的样本区分为不同类型，从 而实现特征空间到类型空间的转换。一般把类型空间的元素定义与类型数目相 等，类型空间里的点的数目是有限的。由特征空间到类型空间所需的操作称为 分类判决。 综上所述，模式识别过程可用图1 1 表示【l 】。 ! 堕笙一三塑上塑 嚣巨巨咽 图1 1 模式识别的过程 简单地说，模式识别主要任务是模式采集、特征提取、选择和分类。分类的 算法大致可分为：统计方法【3 】【4 】、句法方法 5 】- 【9 、神经网络方法【1 0 卜 1 2 】、 模糊理论方法 1 3 】- 【1 5 】和多分类器组合方法 1 0 2 一 1 1 2 。前两类方法在六、七十 年代就已发展成熟；近十几年发展较为活跃的是后三类方法。本论文主要探讨 特征提取选择的具体方法，不讨论分类判决算法，只应用一些成熟的算法如统 计方法、神经网络方法和多分类器组合方法。 在进行模式采集时，总是尽可能多地采集测量数据，致使样本在模式空间 里的维数很大。这就带来处理上的困难，处理时间的消耗和费用都会很大，有 时无法直接分类，即所谓“维数灾难”。其次，在原始特征里，有些提供的信 息对分类贡献不大，有必要对原始数据进行变换得到最能反映分类本质的特 征。显然，特征选择是很重要的，它强烈地影响分类器的设计及性能。假使对 不同类别这些特征的差别很大，那就较容易设计出具有良好性能的分类器。因 此特征选择是模式识别中的关键，甚至有人认为是模式识别中的全部问题所 在。由于许多实际问题常不易找到那些最重要的特征，或受条件限制不能对它 们直接测量，这就使特征提取，选择的任务复杂化而成为模式识别系统最困难的 任务。特征提取选择的任务就是如何从众多特征中找出那些最有效的特征。目 前，这个问题受到极大重视，尤其在特征提取方面积累了很多卓有成效的方法， 但特征选择的方法并不多，效果不好，效率也不高基本上还不能摆脱穷举 法的阴影。 本论文提出的马田系统大大丰富了特征选择的方法库。它第一次将模式识 别中的特征选择问题用试验设计的方法来解决。它通过科学设计安排试验，使 得我们不必穷举仅要几次极具代表性的试验数据就能得到最有效的特征，其效 果和效率都是其它许多特征选择方法所不能比拟的。马田系统方法的新颖性、 操作易行性和结论的有效性应当引起广泛的重视。 博士学位论文马田系统在模式识别中的研究1 曼生塑 1 2 试验设计 1 2 1 试验设计的含义 试验设计是研究如何正确地安排试验的一门统计学科。它以数理统计、线 性代数、数论和组合数学为理论基础，科学地安排试验方案，正确地分析试验 结果，尽快获得优化方案的一种数学方法。大多数数理统计方法主要用于分析 已经得到的数据，而试验设计还决定数据如何收集。试验设计是统计数学的一 个重要分支。 试验设计的方法可以是多种多样的，广义地说，为获得一定的信息，用任 何方式进行试验都可称为试验设计的方法。当然，不同方法进行试验获得的信 息多少、效率和数据分析的容易程度是不同的。这就涉及到最优试验设计问题 【1 6 。针对不同的设计准则，人们提出了正交表设计 4 5 】、均匀表设计【1 8 、d 一 最优 1 9 、a 最优 1 6 】、e - 最优【1 6 】、g - 最优设计 1 6 】【1 9 】等许多试验设计方案。 在多种设计方案中，又以正交表试验设计应用最为广泛，a c t s 就主要应用二水 平正交表为设计方案。 试验设计的目的是为了获得试验条件与试验结果之间规律性的认识。它能 从影响试验结果( 响应指标) 的多种因素中，判断那些因素显著，那些因素不 显著；能确定最佳因素水平组合的预测数学模型( 即所谓经验公式) ；能对响 应指标达到的最优值及其波动范围给以定量地估计。因此试验设计适合解决多 因素，甚至多响应指标的优化问题。 试验设计是否科学，分析是否合理，结果是否正确并非按部就班就能得到。 它不仅要求试验者熟悉试验设计自身的理论、方法、技巧，还必须具有较深的 专业理论知识和丰富的实践经验。因此m i s 要应用得成功，除了要遵循试验设 计的基本理论方法外，还要具体结合模式识别中特征选择的实际。只有把试验 设计理论、专业知识和实践经验三者紧密结合才能取得良好的效果。 !堕笙型盟 1 2 2 试验设计的发展历史 试验设计的基本思想和方法是英国统计学家于本世纪2 0 年代创立。它的最 初应用思想是减少偶然( 随机) 因素的影响，使试验数据有一个合适的数学模 型，改传统的逐一因素依次试验的方法，对不同因素的每一水平组合进行试 验，最后用方差分析的方法对数据进行统计分析。1 9 3 5 年，r a f i s h e r 出版试 验设计，从此开创了一门新的应用数学的学科领域。f i s h e r 也被誉为试验设计 的奠基者和创始人。 4 0 年代，d 劳尼提出多因素试验的部分实施方法，奠定了现代试验设计 理论和方法基础。4 0 年代末、5 0 年代初，日本电讯研究所以田口玄一为首的 一批研究人员在研究电话通讯设备系统时发现，自f i s h e r 以来创造的试验设计 方法，不论全因素试验法，或是随机取组法、拉丁方格法在应用中均受到限制。 于是，他们改进了英国人创立的试验设计技术，开发了用正交表安排试验、分 析试验结果的正交表试验优化技术方法 1 7 】。1 9 5 2 年，田口玄一在日本东海电 报公司应用正交表进行项目的优化试验获得成功。之后，正交表试验设计法在 日本，继而在国际上得到迅速推广。 与此同时，从5 0 年代初，在综合回归分析与试验设计最新研究应用成果的 基础上，创立了回归试验设计技术。这也是应用数学的一个新发展。它将试验 的方案设计、数据处理与回归方程统一起来进行优化，己成为现代通用的一种 试验设计技术。回归试验设计主要从正交性、旋转性等优良性出发，利用正交 表、正交多项式回归、中心组合设计、单纯形以及计算机编制试验方案等，直 接建立各种回归方程。由于它具有设计表格化，公式规范化，分析程序化等特 点，为此项技术的实际应用提供了方便条件。 1 9 5 7 年，田口玄一提出了信噪比试验设计法 2 0 1 ，以解决产品设计问题中 的功能波动问题。它为试验设计拓展了新的内容，也为正交表试验设计法开辟 了新的应用领域。7 0 年代中期，田口玄一提出了三次设计的思想和方法，是对 传统试验设计技术方法的完善和重要发展，为企业研究产品质量与成本的最佳 配合及其试验设计技术提供了系统方法。该方法灵活运用信噪比设计法，充分 壁主兰堡堡苎 兰里墨堕垄堡塞望型! 塑堑窒量皇旦 一三 利用产品或系统存在的非线性效应，利用专业技术、生产实践提供的信息资料， 同正交表试验技术相结合，取得高质量、低费用的十分显著的技术经济效果。 从试验设计发展的历程来看，如果说f i s h e r 创立早期、传统的试验设计是第一 个里程碑，正交表的开发和正交表试验设计法的广泛应用是第二个里程碑，那 么，田口玄的信噪比试验设计的开发和三次设计的创立是第三个里程碑。田 口博士在以往工作基础上，于8 0 年代提出走质量工程学道路，编著质量工 程学丛书，将质量管理，质量控制及试验设计科学的发展，提高到一个新水 平【2 l 】。 我国从5 0 年代开始，开展对试验设计这门学科的研究，并逐步应用到工农 业生产中去。6 0 年代末，在正交试验设计的理论和方法上都有新的创见，并编 制一套较为适用的正交表，简化了试验程序和试验结果的分析方法，自7 0 年 代以来，大力推广，同时，在正交表试验设计理论上也有新的突破。自8 0 年 代开始，我国学者方开泰等又创立了均匀试验设计法【1 8 】，在我国工业、国防 中取得了初步效果。 从以上发展历史可以看出，试验设计是与实践结合十分紧密的。其内容是 随实践发展不断丰富、完善的，其应用领域也不断扩大。近几年又出现马田系 统这样一种新的应用方法。 1 3 马田系统概述 近几年来， n i c h it a 蝴i 2 2 - 【2 4 提出了马田系统，运用到多维系统的降 维上。它实际上就是田口信噪比试验设计在特征选择上的应用。在日本，马田 系统己广泛应用在：模式识别、大学入学测试系统、借贷信用的审核系统、农 业应用、产品检验系统、医疗诊断和疾病预测系统、手写体识别系统、制造过 程诊断系统、自动预防事故系统等。每年都有大量这方面的案例发表 2 5 】 3 3 】 证明它是一个行之有效的工具。田口也将它作为自己方法体系未来发展的方 向。 特征提取选择本质上是个优化问题，而试验设计也是解决优化问题的重要 !竺丝j 坚竺旦 工具，此二者的交汇就产生了马田系统。马田系统与众多特征提取选择方法相 比，最引人之处就是它引进了正交表，这是它的一个创举。尽管正交表试验设 计方法早已用于具有复杂工程背景的多因素优化问题，但借助试验设计的一套 理论方法来评价和筛选特征在模式识别研究的历史上还是第一次 3 4 。马田系 统是将试验设计( 主要是田口信噪比试验设计) 的一套思想方法运用到模式识别 的特征选择上。对于待选的原始特征集，仍以信噪比为指标，但此时是作为衡 量特征对于类别的可分性程度的度量而出现。采用二水平的正交表安排有代表 性的试验，通过对试验结果进行显著性分析得出显著特征。以显著特征为基础 确定判别标准( 阈值) 进行分类。 1 3 1m t s 和特征选择问题 从文献资料和发表的一些案例来看，m 弼主要贡献在于利用正交表进行特 征选择。特征选择f e a t u r e ss e l e c t i o n ) 是从原特征集 r n 如，) 中按某个准则 选出有效特征组成特征子集( x i ，勘，x ，。) ；而特征提取( 力a t u r e se x t r a c t i o n ) 则 是将原特征集b ，h ) 通过某种变换v 而产生新的特征协，j _ ) ，一般地 m n 。特征选择可视为特征提取的特例，但严格地说，m t s 只涉及特征选择， 它不提供任何新的特征变换方法，但可对变换后的特征进行有效性评价，具体 例子我们可在第四章见到。 运用正交表筛选有效特征是脚s 的一个创举。就特征选择而言，我们可以 通过穷举法即将原有，1 个特征中分成若干组，每组m 个特征，对于给定的可分 性判据“) ，比较各组特征的优劣，从中挑选出最优的一组特征。此法直观而 且能得到最优的组特征，但计算量太大，从n 个特征中挑选m 个特征需比较 ，、 打 _ = 点个组合的以) 值。为此，出现了一些可得到次优结果的选择算 k m ) 7 ! t n m l 法，称为次优算法。 1 】中介绍一些算法如逐个特征比较法，顺序前进法s f s ( 包 括广义s f s 法) ，顺序后退法s b s ( 包括广义s b s 法) ，增“法。次优算法简 单易行，计算量小，但经常地所得结果与最优结果相差太大，不能得到满意得 博士学位论文 马田系统在模式识别中的研究与应用 特征子集。为此提出分枝定界搜索法 1 】，它是穷举法的一种快速算法。 为实施分枝定界搜索法，可分性判据j ( ) 必须具有单调性：即若 x xz m 一， m 3 ，则必有j ( x ，) j ( x ：) j ( x k 。) j ( x t ) 。分 枝定界法实际上也难得到最优结果，因为j ( ) 值用样本估计往往是有偏的( 第三 章32 节我们将看到这一点) ，且估计值，( ) 是随机变量还要受波动的干扰，因 此单调性在使用中往往不成立。而m r s 的模型中考虑了以) 真值受误差的扰 动，并以“) 为目标进行了优化。此外，分枝定界法的计算量还是很大的。根 据文 3 5 ( p p 5 0 1 ) 的例子，n = 2 4 ，m = 1 2 分枝定界法需要列举7 7 1 个节点( 即需计 算7 7 1 次j ( ) 值) ，改进的分枝定界法需计算1 8 8 次，如果采用马田系统的话， 只要计算2 8 次j ( ) 值即可( 采用上：。( 2 2 7 ) 正交表) 。非穷举的特征选择方法不多 且大多效率不高，马田系统的提出大大丰富了特征选择方法库。 1 3 2 马田系统与基于正交表的多因素最优化方法 m t s 应用正交表来进行特征优选是建立在试验设计的一整套理论基础之上 的，第二章我们将为m t s 建立数学模型。应用试验设计的方法进行多因素优化 在工程领域早已被广泛应用并取得巨大的成效，这一点可从田口参数设计中得 到印证。与其它用正交表进行多因素优化的实际工程应用相比，m 嬲有自己的 一些特点： m t s 因素个数众多但类型简单无复杂的工程背景。交互作用项较为单纯， 只有在要筛选特征之间存在交互效应。而且，如果合适选取响应指标，更有可 能只存在一阶的交互作用甚至没有交互作用。m t s 试验为可计算性项目，实施 较为容易。 在m t s 中，交互作用往往是作为外因出现的，交互作用的影响一般是处于 从属地位。若特征a 和b 的联合对分类有利，那么各类别必在4 或b 之中存在 较大差别，而且该差别一般地是主要的。这就使得我们可以在正交表中多安排 特征而少考虑或不考虑它们之间的交互作用，正交表的规模从而试验的次数可 ! 竺笙 一型旦王王旦 得到控制。 二水平正交表一阶交互作用在各列的分布有一定规律，借助于此，我们可 以采用一些交互作用分布较均匀的二水平正交表，从而可避开交互作用对m t s 特征选择的影响。另外还存在一些适合于筛选因素的试验设计方法，也能有助 于克服交互作用的影响。 以上这些特点使得m r s 用正交表处理优化问题有很大的优势。 当然，m t s 作为新兴的技术不可避免还存在不足 3 4 1 ，m t s 的完善和深入 应用就成为本论文的主要任务。 1 4 本文主要工作和内容安排 马田系统是用试验设计的方法来解决模式识别中的特征选择问题。它既要 考虑试验设计的基本思想方法和应用条件，又要结合模式识别特征选择领域的 具体环境特点。在国外，尤其是日本，早已展开肘嬲的应用工作，而对其理论 基础研究很少，应用m t s 的动力更多地是来自田口试验设计方法以往在工程领 域的巨大成功的鼓舞。在国内，应用和研究则都还刚起步。因此，本文试图探 求的m t s 理论基础，为它建立一个合适的数学模型，并以此为指导下，更深入 地进行应用方面的研究。全文共分六章，具体内容如下： 第二章主要介绍了试验设计的基本理论模型和试验设计与多因素优化问题 的联系，为第三章m t s 的数学模型建立提供理论准备。本章着重讨论正交表的 各种统计最优性和它在多因素优化问题中的应用。讨论了除正交表设计之外的 其它筛选因素试验的设计方法，丰富了m t s 的设计方法。本章还探讨m t s 中 着重使用的二水平正交表的交互作用散布性质，为m t s 中交互作用的处理提供 了理论依据。最后，本章提出几种因素显著性检验方法的特点和应用背景，为 m 弼特征显著性检验提供方法库。 第三章主要为m t s 建立数学模型。在可分性判据指标( 响应指标) 为样本 一阶和二阶矩的函数假设下，我们指出基于二水平正交表设计的m t s 可以建立 在线性统计模型基础之上，当样本量足够大时，还可视为近似等方差模型。这 堕主堂堡垒奎兰里墨竺垄堡塞望型! 盟里壅兰窒旦 生 样就使得m t s 能应用第二章讨论正交表设计的许多优良性质。我们假设的可分 性判据指标的函数形式是相当普遍的，因此，我们为m t s 建立的模型也具有相 当广泛性。本章最后讨论了可分性判据指标值估计的精确度、交互作用以及显 著性检验方法对m 弼的影响。这些问题在实际中经常遇到。 第四章着重探讨最优特征( 维数) 问题。本章提出优化特征的几个层次： 基于最低识别正确率的最优特征、基于最优可分性判据指标值的最优特征和约 束条件下的最优特征，文中我们证明了基于最优可分性判据指标值的最优特征 和贝叶斯线性分类器和最小距离分类器下的最优特征。在第二节，利用第一节 讨论结果来指导我们对d 魁人脸图象的有效鉴别特征进行再优化。应用m 弼 我们找到了人脸图象的有效鉴别特征的最优特征。第二节的例子表明m t s 可以 还可用于特征提取后的特征的评价。 第五章讨论m t s 在多分类器组合中的应用。本章主要应用正交表试验设计 的方法进行分类器筛选，我们用有效分类器进行组合获得了多分类器组合的最 佳识别率。本章还讨论了m t s 在多级分类( 串联形式) 的多分类器组合中的特 征选择中的应用，通过m 嬲的特征选择，串联系统识别率得到显著的改善。此 外，为实施多级分类，本章还引进两种后验概率估计法，作者证明了它们是极 大似然估计，并讨论了其渐进性质，还将它们应用在多级分类中取得了较好的 效果。 第六章讨论m t s 的其它一些应用问题。主要从可分信息的角度来探讨可分 性判据指标对m t s 特征选择的影响，讨论了非参数方法的可分性判据指标和具 有可分信息互补的可分性判据指标对m t s 特征选择的改进作用。本节还应用聚 类的方法，用它来帮助m 7 一进行特征选择。这些都取得相当好的效果， 1 0 试验设计与多因素优化 2 试验设计与多因素优化 试验设计涉及的内容很多近来又有很大发展，本文仅讨论与马田系统密 切相关的部分。 2 1 线性统计模型 在讨论试验设计方法时，总是针对某一( 统计) 模型的。在应用统计领域 线性统计模型占重要地位。在第三章，我们将看到马田系统可以归结为线性统 计模型来研究。因此，本文讨论的所有试验设计方法都是针对线性统计模型来 说的。 整个试验可视为一个输入输出系统。我们称输出为响应指标( 试验指标) ， 输入系统的一般是影响响应指标的取值的量，称为因素。从纯数学观点来看， 因素相当自变量，用弘瓴，z ：，磊j 表示肌个因素；响应指标相当因变量，用 n 表示响应指标的理论真值。一般地，指标与因素之间存在函数关系n = f ( 刁。 为研究这种函数关系，通常根据专业知识，假定属于某种函数类型，但带有一 组未知参数b = ( b ，口：，b 。) 。也即n = 曩z ，b ) 。由于试验过程受随机因 素干扰，所得观察值y 并非指标r l 值，而是 y = f ( z ，t 3 ) + ( 21 ) 式中e 称为误差，( 21 ) 也称为数据结构模型。 在实际应用中，为统计理论研究和计算方便，假定可用一组己知函数： 由l ( z ) ，由2 ( z ) ，巾；g 力 ( 2 2 ) 近似展开为 尺z ，b ) 一口，中。( z ) + b2 中2 ( 幼+ f 3 ：中，( 2 ) ( 2 3 ) 上式称为线性数学模型，( 2 2 ) 称为因子项。这里所谓线性是对模型中的系数 b = ( 6 ，b 。，b ，) 来说的，对因素变量一般不是线性的。在马田系统中，适 当地选择可分性判据指标，可以得到形如( 21 ) 的数据结构模型，即真值项与误 差项是线性可分的。 堕主兰壁兰塞 呈里墨丝垄堡塞塑型主塑里塞兰室旦生 改变因素的取值，( z - ，z2 ，2 n ) ：1 1z 1 2 z l “ z 2 lz 2 2z 2 n ( 2 4 ) 进行试验( 或观察) ，得到门个观察值净( y l ：，j 0 。由( 23 ) 可得方程 y l = 。西l ( z 1 ) + 2 m 2 ( 矗) + + ，中。0 i ) + 自 y ：= 巾，0 ：) + 2 中：0 ：) + + ，弧0 2 ) 十占2 ( 2 5 ) j h = 1 面l ( z n ) + 2 m 2 ( z 一) + + p ，s ( z 一) + s 。 称( 2 5 ) 为线性统计模型。b 为待估参数，误差e = ( e ，：，e 。) 为随机变量， 我们可对e 作出各种统计假设，其中最经典的应当是正态等方差假定e ， n ( o ，o2 ) ，f l ，2 ，胛。若用矩阵表示各因子项在各观察点上的值： 函- ( 矗) 中2 ( z 0就( z 1 ) 中l ( z 2 )中2 0 2 ) 4 b ( z 2 ) 西l ( z 一)中z ( 厶)，( 厶) = z( 2 6 ) 则( 25 ) 可表示为 y ：一i b + s( 2 7 ) 通常把x 称为模型设计阵。若x 是由实数值组成的满秩阵，则模型称为回 归模型；若z 是由0 ，l 两个值组成的矩阵( 通常不满秩) ，则模型称为方差模 型。以上两种模型均假定v a t ( e ) = o2 ( 不必假定为正态分布) ，_ ，为单位阵。32 节中，对于某类范围很广的可分性判据指标，马田系统近似地有v a r ( e ，) 一 v a t ( e ，) ，产l 一2 s 成立。本文所讨论的都为方差模型。 在线性统计模型的理论中，矩阵石扮演重要角色，试验设计就是研究z 的 取值，也即是讨论如何在试验区域“最有效”地选择若干点，在这些点上进行 试验得到函数观察值，而后通过这些观察值去了解函数和它的变化特性。 试验设计的好坏，归根到底，是看它能否用较少的试验提供关于月z ) 的充 分信息。最优试验设计问题，就是在一定的模型假设下，如何在试验前适当地 ! ! 堕堕堡生兰圭里壅垡垡竺旦曼三旦 选择自变量( 因素) 值来确定设计阵x 的值，使得在统计推断中能具有某种统 计优良性质。针对不同的设计准则，人们提出了许多试验设计方案 3 6 】一 4 1 1 ： 如正交表设计、均匀表设计、d 最优、爿最优、e - j i i 优、g - 最优设计等。在多 种设计方案中。以正交表试验设计应用最为广泛。 2 2 正交表试验设计与多因素优化 2 2 1