（信号与信息处理专业论文）图象识别中的归纳学习方法研究.pdf

中国 科学 技术大学博士学 位论文 能 性 。 k 为 了 探 索 如 何 在 归 纳 学 习 及 其 应 用 研 究 方 面 容 入 新 的 思 路 ， 本 文 着 重 考 虑 了 悠 惑 i 0 g 艺 与决策树归纳学习之间的密切关系，并 试图用模式识别的理论和方法对归纳学习进行研究。 论文 的 研 究 工 作 包 括以 下7 个 方 面 : ( i )在绪论部分，论文分析了目 前机器学习领域的 研究动态、主要计算方法以及相关 领域的互动关系，阐述了 模式识别理论与决策树归纳学习的内 在联系，指出了 机器学习研 究中 提高判决精度的切入点。即，模式识别曾 对归纳学习的发展起到过重要作用和影响， 也是归纳学习最成功、最重要的应用领域之一。判决精度是模式识别和归纳学习的 共同问 题，在考虑提高归纳学习判决精度的时候应当充 分发挥模式识别中成熟理论的作用。 ( 2 )分析了 特征选择与决策树算法的一致性关系，从信号分析的角度出发，通过观察 窗口变化时信号能量的变化情况，提出了一种基于自相关函数的决策树归纳学习算法 a c d t 。与最适合离散数值学习的i d 3 算法相比，a c d t具有更高的判决精度。 ( 3 )模式类可分性度量准则是模式识别领域中的重要理论，然而它一直没有受到归纳 学习研究的足够的重视。将模式类可分性度量准则引入归纳学习是本文的创新之一。通过 对内类、内间距离准则进行分析并做局部修正，提出了一种基于类内、类间距离的 i c d 2 决策树算法。实验表明，i c d 2的判决精度高于连续数值学习算法 c 4 . 5并接近决策森林的 效果，而目 计算速度比c 4 . 5 更快。i c d 2 另一个特点是它可以对特征的有效性进行度量。 ( 4 ) 为了 避免 极多 模式学习时 所产生的o v e r # tt in g 问 题， 提出了 一 种 模式 递增学习 系 统m c m d 。该学习 系统可以 适应模式类别增加、 减少系统在模式类别 增加的 情况下的学习 量、保留已获得的知识，并能提高系统的判决精度。 ( 5 ) 通过对势函数训练的计算过程及 其算法的 研究， 提出了 一种新的 基于位势距离的 势函数算法。 它不仅可以 减少势函数法的计算迭代次数和判决函数的复杂度，它的 学习结 果还可以映射一组代表模式类边界样本的集合 该算法的提出主要用于 对模式识别和归纳 学习的重要理论v c - d i m e n s i o n 的研究，即典型样本问题。 ( 6 ) 作为一种探索， 论文研究了用典型样本、 神经网络和i c d 2 算法来构成学习系统。 目 前大部分的决策森林和多变决策树算法都是以可理解性和计算复杂性为代价来换取判决 精度的提高的。基于典型样本、神经网 络和 i c d 2的学习 系统在此方面有 所提高，它只是 以计算复杂性为代价来换取判决精度的提高的， 它的学习结果是 u d t而不是难以 理解的 f o r e s t 或 m d t 。 该学习系统得到的 结 果是神 经网 络的 判决精 度并具 有归 纳 学习 的 概念的可 理解性。 中国科学 技术大学博士学位论文 ( 7 ) 完成了一个基于归纳学习的 城市地形图 符识别系统。图 符识别系统是一种大型的 极多模式学习和识别系统。在该图符识别系统中，联系特征提取和归纳学习的纽带是模式 类可分性度量准则。 它既可以 对所提取的特征进行度量又是形成i c d 2 算法的基础。 m c m d 系统则起到了对极多模式类学习问题的分解与合成的作用，它不仅可以完成模式递增学习 的任务，还很大程度地提高了识别系统的判决精度。系统测试结果表明，由于特征提取方 法与学习算法的一致性， i c d 2 算法在判决精度方面显示出比c 4 . 5 算法和概率神经网络p n n 具有更高的性能。而i c d 2 与m c md的结合又在很大程度上改善了 极多 模式情况下的系统 性 能丫 “ 一，. . .曰 .口. 一一一一1 v + * 4 k 4 垫全 丝全 竺 竺 二 一 一 ab s t r a c t t h e m a i n p u r p o s e o f t h i s p a p e r i s t o s t u d y t h e m e t h o d o f g r a p h i c r e c o g n i t i o n u s i n g i n d u c t i v e l e a r n i n g . f o r g r a p h i c r e c o g n i t i o n , t h a t t e r r i b l y p a tt e rn c l a s s e s a n d b u t 琦r e c o g n i t i o n s y s t e m a r e t h e i m p o r t an t c h a r a c t e r i s t i c s i n o n e h and , and h o w t o p i l e n e w r e c o g n i z a b l e p a tt e rn t o t h e c o m p l e t e d s y s t e m i s ano t h e r p r o b l e m . i n d u c t i v e l e a r n i n g i s t h e m o s t m a t u r e b r an c h and t h e k e rn e l o f m a c h i n e l e a r n i n g , a n d t h e j o i n t b e t w e e n p a tt e rn r e c o g n i t i o n and a r t i f i c i a l i n t e l l i g e n c e . b a n d i n d u c t i v e l e a r n i n g t o g e t h e r w i t h p a tt e rn r e c o g n i t i o n t o s h a p e i n t e l l i g e n t r e c o g n i t i o n m e t h o d i s t h e k e y o f t h a t m a k i n g p a tt e rn r e c o g n i t i o n e v o l v e fr o m s t a t i s t i c a l a n d s t r u c t u r a l m e t h o d o l o g y t o i n t e l l i g e n t i z a t i o n - and c o n c e p t u a l i z a t i o n - b as e d m e t h o d , w h i c h f i g u r e s t h e m i l e s t o n e i n t h e c o u r s e o f a p p l i c a t i o n s o f i n d u c t i v e l e a r n i n g i t i s w e l l k n o w n , m o s t t e c h n i q u e s w e r e d e v e l o p e d an d s h o u l d b e i m p r o v e d i n p r a c t i c e . b a c k t o 1 9 9 0 s , t h a t a p p l y i n g i n d u c t i v e l e a r n i n g t o r e l a t e d a r e a w as s t a r t e d . j u s t i n t h i s t i m e , t h e d e f i c i e n c y o f c l a s s i c t h e o ry and a l g o r i t h m s o f i n d u c t i v e t e a m i n g w e r e d i s c o v e r e d t h a t t h e y h a d n o t p u t e n o u g h c o n s i d e r a t i o n t o t h e p r e d i c t e d a c c u r a c y w h e r e a s e m p h a s i z e t h e m e t h o d o f s u c c i n c t n e s s e x c e s s i v e l y . t h i s d i s c o v e r m a d e p e o p l e c l e a r - h e a d e d fr o m s i n k i n g i n o c c a m s a l g o r i t h m , a n d t h e n l o t s o f e x p e r i m e n t a l b a s e d m e t h o d , s u c h a s d e c i s i o n f o r e s t a n d m u l t i v a r i a n c e d e c i s i o n tr e e s w h i c h w e r e t i t l e d n o n - t h e o r e t i c a l m e t h o d 衍 s o m e f a m o u s s c i e n t i s t w h o p e r s i s t i n c l a s s i c i d e a , w e r e p r e s e n t e d i n s u c c e s s i o n . a c t u a l l y , t h e s e b e i n g d i s p u t e d m e t h o d s , w h i c h h a s n o w a y t o u n d e r s t and th e r e s u l t o f l e a rn i n g a l m o s t , c an m a k i n g p r o g r e s s i n i m p r o v i n g a c c u r a c y i n d e e d . b u t t h e r e i s a b a r r i e r i n t h e w a y o f i n d u c t i v e l e a r n i n g i t s e l f , b e c a u s e t h a t i f t h e r e s u l t o f l e a rn i n g l o s t t h e in t e l l i g i b i l i ty , o t h e r m e t h o d s o f a r t i f i c i a l i n t e l l i g e n c e s u c h a s d e d u c t i v e l e a rn i n g w i l l h a s n o b a s i s u n d e n i a b ly , p r e d i c t i v e a c c u r a c y i s t h e m a i n p u r p o s e o f l e a rn i n g n o w a d a y s . t h o u g h t h e s t a t u s o f r e s e a r c h i n d e c i s i o n - f o r e s t - m e t h o d a n d md t a l g o r i t h m s l e t u s h a v e a h o p e i n m i n d , t h e i m p r o v e d a c c u r a c y a t t h e c o s t o f i n t e l l i g i b i l i ty and h u g e c o m p l e x i ty i s n o t c o n s i d e r a b l e . t h e p r o b l e m t h a t t h e d e m a n d o f a c c u r a c y , c o m p l e x i ty a n d i n t e l l i g i b i l i ty a r e t h e v e ry d i ff i c u l t i s s u e h o w e v e r . a b o v e a l l , i n n o w a d a y s b a c k g r o u n d , s i m p l y c o m b i n e t h e c l a s s i c l e a r n i n g m e t h o d t o p a tt e rn r e c o g n i t i o n f o r c o n s t ru c t i n g a c l a s s i f i e r i s i m p o l i t i c , b e c a u s e t h e u l t i m a t e l y p u r p o s e o # r e c o g n i t i o n i s t o h a v e a h i g h e r p e r f o r m a n c e w i t h h i g h e r p r e d i c t i v e a c c u r a c y . n o t a l w a y s s e l e c t a d e c i s i o n f o r e s t m e t h o d o r a md t a lg o r i t h m a r b i tr a r i l y t o s e tt l e t h e p r a c t i c e p r o b l e m c an m a k e t h i n g s m o r e p e r f e c t . o n o n e h and , d e c i s i o n f o r e s t m e t h o d and m d t a l g o r i t h m s a r e n o t u n l i m i t e d a d a p t e d f o r i m p r o v i n g a c c ur a c y an y w h e r e . t h e l o c a l i z a t i o n o f t h e m a r e d i s c o v e r e d and d e m o n s tr a t e d a l r e a d y o n e o t h e r h and , e v e n i f t h e c o n d i t i o n s a r e s a t i s f i e d , t h e s e m e t h o d s a r e a l s o l i m i t e d i n m i n i a t ur e d a t a s e t s , b e c a u s e o f t h e h u g e c o m p u t i n g c o m p l e x i ty c o n f i n e d t h e m t h e a b i l i ty t o d i s p o s e t h e l v 中 a j + 鱼进主丝吐壑丝主一一一一 g i g an t i c r e a l i s t i c d a t a . a d d i t i o n a l l y , o n l y t h e c o n c e p t u a l l e a r n i n g c a n p r o v i d e t h e p r o b a b i l i ty o f c o m p r e h e n d i n g and i n t e rv e n i n g t o t h e s y s t e m i n o r d e r t o f i n d a w a y t h a t n e w i d e a s b e i n g a l l o w e d i n t o i n d u c t i v e l e a r n i n g a n d i t s a p p l i c a t i o n s , t h e a ff in i ty b e t w e e n p a tt e r n r e c o g n i t i o n and i n d u c t i v e l e a r n i n g w i t h d e c i s i o n tr e e i s e m p h a s i z e , and t h e t h e o ry and m e t h o d s o f p a tt e rn r e c o g n i t i o n a r e c o n s i d e r e d w h e n in d u c t i v e l e a r n i n g m e t h o d a r e s t u d i e d i n t h i s p a p e r . t h e r e s e a r c h w o r k i n m y t h e s i s i n c l u d e 7 a s p e c t a s f o l l o w s : ( l ) i n i n tr o d u c t i o n , t h e d e v e l o p m e n t s , m o s t l y m e t h o d s and m u t u a l r e l a t i o n b e t w e e n r e l a t e d a r e a s a r e ana l y z e d . b y e x p a t i a t i n g o n t h e i n h e r e n c e c o n t a c t b e t w e e n p a tt e rn r e c o g n i t i o n a n d d e c i s i o n - tr e e - m e t h o d s , t h e k e y p o i n t o f h o w t o i m p r o v e t h e a c c u r a c y i n m a c h i n e l e a r n i n g i s t u rn e d o u t : t h e t h e o ry o f p a tt e rn r e c o g n i t i o n h a s h a d p l a y i n g an i m p o rt ant r o l e a s t h e i n d u c t i v e l e a r n i n g t h e o r y and m e t h o d w e r e i n d e v e l o p m e n t . i t i s o n e o f t h e m o s t s u c c e e d e d a n d i m p o rt ant a p p l i e d d o m a i n o f i n d u c t i v e e a r n i n g . b e c a u s e o f t h a t t h e y h a v e t h e s a m e i s s u e a b o u t p r e d i c t i v e a c c u r a c y , w e s h o u l d e x e rt t h e m a t u r e t h e o ry o f p a tt e rn r e c o g n i t i o n s u ffic i e n t l y w h e n w e t h i n k o v e r h o w t o i m p r o v i n g t h e a c c u r a c y i n i n d u c t i v e l e a r n i n g . ( 2 ) b y ana l y z i n g t h e c o n s i s t e n c y b e t w e e n f e a t u r e - s e l e c t i o n - m e t h o d a n d d e c i s i o n - tr e e - m e t h o d , f r o m v i e w p o i n t o f s i g n a l ana l y s i s t h e o ry , a n d w i t h o b s e rv i n g t h e c h a n g i n g o f s i g n a l e n e r g y w h e n t h e d a t a - w i n d o w i s c h ang e d , w e p r o p o s e d a n e w m e t h o d o f s h a p i n g d e c i s i o n tr e e b a s e d o n a u t o - c o r r e l a t i o n f u n c t i o n n a m e d a c d t . c o m p a r in g w i t h i d 3 w h i c h i s f i tt e d f o r d i s p e r s i v e d a t a , a c d t a p p e a r s m o r e a c c u r a t e l y . ( 3 ) t h e s e p a r a b i l i ty - r u l e f o r p a tt e rn r e c o g n i t i o n i s a i m p o rt ant t h e o ry b u t n o t b e e n r e g a r d e d e n o u g h i n s t u 勿i n g o f i n d u c t i v e l e a r n i n g . t h a t i n tr o d u c i n g t h i s r u l e t o i n d u c t i v e l e a rn i n g i s o n e o f i n n o v a t i o n s i n t h e p a p e r . b y ana l y z i n g , p a r t ly m o d 近i n g , a n e w d e c i s i o n - tr e e - m e t h o d n a m e d i c d 2 w h i c h u s i n g i n n e r - c l a s s and i n t e r - c l a s s e s d i s t an c e a s l e a r n i n g s tr a t e g y i s t u rn e d o u t e x p e r i m e n t s s h o w t h a t t h e p r e d i c t i v e a c c u r a c y o f i c d 2 i s h i g h e r t h an c 4 . 5 and n e a r l y t o d e c i s i o n f o r e s t , and t h e c o m p u t i n g s p e e d i s f a s t e r t h an c 4 . 5 a s w e l l . s p e c i a l l y , i c d 2 c an m e a s u r e t h e v a l i d i ty o f t h e f e a t u r e . ( 4 ) f o r t h e i s s u e o f a v o i d i n g o v e r f i tt i n g p r o b l e m i n t e r r i b l y c l a s s e s c o n d i t i o n , w e p r o p o s e d a a l g o r i t h m n a m e d mc md f o r i n c r e m e n t a l - l e a r n i n g - d e m a n d . mc m d c a n a d a p t t h e c a s e o f a d d e d m o d e , r e d u c e b u r d e n o f l e a r n i n g w h e n t h e c l as s i n t h e r e c o g n i t i o n s y s t e m i s i n c r e a s e d , k e e p d o w n t h e a c h i e v e d k n o w l e d g e , and i m p r o v e t h e p r e d i c t i v e a c c u r a c y . ( 5 ) b y s t u d y i n g t h e p o t e n t i a l f u n c t i o n a l g o r i t h m a n d i t s c o m p u t i n g p r o c e s s , w e p r o p o s e d a n e w tr a in i n g m e t h o d b a s e d o n p o t e n t i a l d i s t a n c e . t h e p r o p o s e d m e t h o d n o t o n l y c an r e d u c e i t e r a t i v e t i m e s and c o m p l e x i ty o f d i s c r i m i n a t i o n , b u t a l s o c a n m a p a c o l l e c t i o n o f e x a m p l e s w h o 中国科学技术大学博士学位论文 a r e a t t h e b o u n d a r 3 v ( - d i me n s i o n . b e t w e e n c l a s s e s . t h i s a l g o r i t h m i s h e l p f u l f o r s t u d y i n g t h e ty p i c a l e x a m p l e s i n ( 6 ) a s a n e x p l o r a t i o n , m e t h o d o f c o m b i n i n g t h e c o n c e p t o f t y p i c a l e x a m p l e , n e u r a l n e t w o r k a n d i c d 2 a l g o r i t h m i s s t u d i e d . u n l i k e m o s t a l g o r i t h m s o f d e c i s i o n f o r e s t a n d m d t w e r e t o i m p r o v i n g p r e d i c t i v e a c c u r a c y a t t h e c o s t o f i n t e l l i g i b i l i ty and c o m p u t i n g c o m p l e x i ty , t h e p r o p o s e d m e t h o d i s t o c o n s tr u c t a u d t w h i c h i s e a s y t o u n d e r s t a n d a t t h e c o s t o f c o m p u t i n g c o m p l e x i ty , n o t a k i n d o f f o r e s t o r m d t a n d t h e a c c u r a t e m e a s u r e m e n t r e s u l t i s o f n e u r a l n e t w o r k w h e r e a s t h e i n t e l l i g i b i l i ty i s o f i n d u c t i v e l e a r n i n g ( 7 ) c o m p l e t i n g a c i ty - g r a p h - s y m b o l r e c o g n i t i o n s y s t e m u s i n g i n d u c t i v e l e a r n i n g m e t h o d c i ty - g r a p h - s y m b o l r e c o g n i t i o n s y s t e m i s a k i n d o f l a r g e i n t e r r i b ly e x c e s s i v e p a tt e r n s . i n t h e c o m p l e t e d s y s t e m , t h e l i g a m e n t b e t w e e n f e a t u r e e x tr a c t i o n and l e a r n i n g i s t h e s e p a r a b i l i ty - r u l e i n p a tt e rn r e c o g n i t i o n , w h i c h c an m e a s u r e f e a t u r e s a s w e l l a s f o r m i n g i c d 2 a l g o r i t h m . t h e a c t i o n o f m c m d i s f o r d e c o m p o s i t i o n an d s y n t h e s i s . i t c an a c h i e v e t h e g o a l o f i n c r e m e n t a l l e a r n i n g , an d c an i m p r o v e p r e d i c t i v e a c c u r a c y a s w e l l . t h e r e s u l t o f s y s t e m i c t e s t i n g t u r n o u t t h a t , b e c a u s e o f t h e r e i s c o h e r e n c e b e t w e e n f e a t u r e - e x tr a c t i o n - m e t h o d and l e a r n i n g - m e t h o d , t h e p e r f o r m a n c e o f i c d 2 i s h i g h e r t h an c 4 . 5 and p n n . f u r th e r m o r e , t h e c o m b i n a t i o n o f i c d 2 and mc md m a k e i t i m p r o v e d m u c h m o r e vl _ 生 q j + 迷士竺竺7一一一一 第一章 绪 论 1 . 1 引言 所谓模式识别就是经过分析、判断、归类以识别出事物与哪个供模仿的标本相同或近 似。其目的是对文字、声音、图象景物等模式信息加以处 理与识别，以解决计算机与外部 环境直接通信这一重要问题。图 象识别则是模式识别的一个子问题。 经典的模式识别理论是建立在概率论基础上的统计模式识别方法，以及从形式语言而 衍生出的结构模式识别方法【 1 。随着模糊子集理论、神经网 络和人工智能方法的出现及其 不断深入的研究，模糊模式识别、神经网络模式识别和人 工智能模式识别等新型的 模式识 别方法己广为人们所接受和采纳。毫无疑问，形式语言、模糊子集理论、神经网络和人工 智能都在很大程度上 推动了模式识别理论及其应用领域的发展。同时，统计模式识 别理论 一直都在对这些领域产生深远的影响。 模式识别理论中的一个重要环节是训练或学习，即通过对样本的学习来完成分类或聚 类任务。因此， 模式识别与人工智能、神经网络的熔合 在于 学习方法上的结合。众所周知， 机器学习是研究怎样用计算机模拟或实现人类学习活动的一门科学，是人工智能领域的一 个重要分支。由于知识获取问题已成为各类智能系统的瓶颈，机器学习和知识表示及推理 已 经渗透到了 人工智能的所有领域，因此机器学习己 经逐渐成为人工智能研究的主要方向 之一。人工智能的核心问 题是机器学习【 2 , 3 . 归纳学习旨 在从大量的经验数据中归纳抽取一般的判决规则和模式， 它是机器学习 最 核心、 最成熟的分支 2 , 3 。归纳学习由于依赖于经验数据，因此又叫经验学习 ( e m p i r i c a l l e a r n i n g ) ;由于归纳依赖于数据间的相似性， 所以它也叫做基于 相似性的学习 ( s i m i l a r i t y b a s e d l e a r n in g ) 。 归 纳学习 根据有无导师指导，又 分为 有导师 学习 ( s u p e rv i s e d l e a r n i n g ) 和无 导师学习 ( u n s u p e rv i s e d l e a r n i n g ) 。 有导 师学习 是 事先将训 练例子 ( 经验数 据) 分类， 因此通常叫示例学习 ( l e a rn i n g f r o m e x a m p l e s ) ;由于它产生规则，因而也叫概念学习 ( c o n c e p t l e a r n i n g ) 。 无导师学习事先不知道训 练例子的分类， 它包括概念聚类( c o n c e p t u a l c l u s t e r in g ) 和机器发 现 ( m a c h i n e d is c o v e ry ) 。 为了区 别 起见， 通常 将上 述各种学习 方法统 称为符号 学习( s y m b o l i c l e a r n i n g ) ， 而将同 属于示例学习范畴的神经网络( n e u r a l n e t w o r k ) 称为联结学习 ( c o n n e c ti o n is t l e a r n i n g ) . 本论文研究的是图象识别中的归纳学习方法。图象识别的特点是模式类别极多、识别 中国 科学技术大学博士学位论文 系 统庞大并且在实际 使用过程中经常需要增加可识别的模式类别。归 纳学习是人工智能和 机器学习理论的基础，也是模式识别理论与人 工智能相衔接的关键。 将模式识别与 人工智 能中的归纳学习结合起来形成智能模式识别方法是近年来 模式识别理论从基于概率论的统 计模式识别和基于形式语言的结构模式识别走向智能化、分类方法概念化的突破，也是归 纳学习 走向 实际应 用的 重要里 程碑。 例如【 3 1 , a q l l 4 ,5 已 经 应用于 1 5种大豆 病虫害的 诊 断，由 程序 产生的正 确诊断 率达到9 7 .6 %， 而人 类专家的正 确诊断 率只 有7 1 .8 % o a q 1 5 6 1 己经成功地应用到 3个医疗诊断问题 ( 淋巴造影、乳腺癌复发的预测、原发肿瘤位置的确 定) 并 取得了比 人类专家诊断正 确性更 好的效 果; 知识获 取系 统 p k a s 3 j 已 经成功地 应用 于大庆油田的录井工作，并且判决的正 确率远高于人类专家的判断。其它的 诸如印 刷体汉 字识别，o x报表自 动录入系统，打印机、复印机、电视机的色彩匹配等一系列重大技术 创新都融合了归纳学习的技术类容。 毫无疑问，任何一门技术学科都是在实践中产生并在实际应用的过程中得到不断地完 善和发展的。在 1 9 9 0 年代初期，归纳学习开始了面向实际应用的阶段。正是在这一时期， 人们发现了 经典的归纳学习理论和算法的严重不足，即经典的归纳学习的理论和算法忽视 的 判决 精度问 题， 而过分地强调了 学习 结果 在 概念 上的 简洁 性阴。 这 种 似乎是突 如其来的 问 题使人 们从 沉醉于o c c a m算法 8 中 清醒 过来， 于 是 各种基于实 验的、 被一 些持 经典的人 工智能思想的名家称为 “ 非理论方法”的决策森林 ( d e c i s i o n f o r e s t )算法和多变决策树 ( m u l t i v a ri a t e d e c i s i o n t r e e s )算法纷纷提出。诚然， 这些几乎不可能对学习 结果在概念上 进行理解的有争议的方法在提高分类器的判决精度方面确实取得了一定的进步，但对于归 纳学习 本身 而言却 仍然存在一个重大的 难 题 9 。因为 一旦学习的 结果 在概念上 难以 理 解甚 至失去了可理解性， 演绎学习 等人工智能的其它方法将失去基础。 尽管目 前决策森林和多 变 决策 树m d t l o 算法的研 究状况让人 们 看到了 提高 判决 精度的希 望， 然而它 们都是以 牺 牲概念的可 理解性 和巨大的计 算复杂性为代 价来换 取判决精 度的并 不十分 可 观的 提高 9 0 对判决精度、计算复杂性和概念的可理解性这三个方面的综合要求仍然是人们面临的非常 困难的问 题【 1 0 1 。 诚然， 如何提高 归纳学习 的判决 精度是目 前归纳学习 研究领 域的 重点论 题 7 , 9 1 . 综上所述， 在目 前的研究背景下简单地用经典的归纳学习 算法进行学习 来构成模式识 别用的分类器是不审 慎的，因为构成具有高判决精度的分类器是模式识别的 最终目 的;而 如果不加考虑地任意采用一种现成的决策森林算法或多变决策树算法来解决实际问 题也不 一定就能取得更理想的效果。一方面，以巨大的计算复杂性为代价的学习方法本身在提高 中 国 科 学 技 术 大 兰 4 兰垫竺主 判决精度方面并不是无条件的，因为人们己 经发现了 这类方法的局限性并在理论上进行了 论 证9 , 1 0 另 一 方 面， 即 使实 际 的 应 用 对 象满 足 这类 算 法的 前 提条 件， 它 们也 只 能 局限 于 在小规模数据集合上的实验。因为巨大的计算复杂性限制了它们处理庞大的实际应用数据 的能力，在概念上的难以理解性又限制了人们对所处理的 庞大的数据进行进一步的研究和 发掘 9 。 对决策森林和多 变决策树算法的 研究目 前还处于探索和发展阶段， 还有很多问题 需要探讨和深入分析。并且， 只有概念学习才有提供人们对识别系统的理解并以此对系统 的局部模块进行干预的可能性。 因此，研究图象识别中的归纳学习方法不仅需要根据图象识别的特点来研究如何有效 地将归纳学习方法应用于图象识别的训练过程，还需要充分考虑到目 前归纳学习研究领域 中的难题即如何有效地提高归纳学习的判决精度问题。由于判决精度问题是模式识别也是 目 前归纳学习的根本问 题，因此本论文拟在解决以 下问 题方面作一些探索: ( u 将模式识别理论与归纳学习方法结合，用模式识别的理论和观点来形成计算复杂 度较小、判决精度较高和概念可理解性较好的归纳学习算法。 ( 2 ) 模式识别面向实际的一个突出问题是在构成极多 模式类的分类器时， 很多 算法在 解决较少模式类的分类问题时具有较好的效果， 但处理极多 模式问题时却表现的不尽人意 为了避免极多模式类情况下归 纳学习的 “ 过确定” ( l 0 问 题 ( 它会降低识别系统的判决精 度) ， 我们需要研究一种能处理极多 模式的递增学习算法， 并希望它的学习结果是可理解的。 ( 3 )用所研究的归纳学习算法完成一个实用的图象识别系统。并将识别系统中的2 个 基本模块，即特征提取模块和归纳学习 模块有机地结合起来。 下面我们就一些模式识别和归纳学习的基本问 题和研究动态做一些扼要地总结。 1 . 2 统计图象识别概述 图象识别的主要训 练方法是有导师学习或称有监督分类。图 1 - 1 是统计 模式识别系统 的结构表示框图。可以 看出，图象识别系统是模式识别系 统的一个子集，只是图象识别系 统的处理对象不同，它的预处理方法和 特征提取方法也 就相应地发生了 变化。 图 象识别系统包括 3个主要部分，即特征提取方法、 特征选择方法和训练方法。在基 于统计模式识别理论的图 象识别系统中， 特征提取、 特征选择和训练分别是三个独立的计 算过程。 特征提取与选择的任务就是把模式空间里的n维特征压缩为特征空间里的k 个 特 征， 并且这 k个特征对于分类来说是最有效的。 从广义 上讲， 特征 提取是一种通过寻求