（农业机械化工程专业论文）基于信息论的特征选择和分类算法研究.pdf

硅南农业大学硕士学位论文 捅墨 摘要 随着计算机科学与技术的发展，人们越来越认识到信息的价值。在信息爆炸的今天，人们迫切 需要一种方法从大量的数据信息中提取并找到有用的信息，数据挖掘就是在这种情况下诞生的。近 十年，数据挖掘的研究工作取得了很大的进展各种数据挖掘软件的应用极大地推动了人们掌握、 处理信息的能力，并为人们带来了很好的经济效益。数据挖掘就是从大量的、不完全的、有噪声的、 模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。 特征选择和数据分类是数据挖掘的两个重要的课题。特征选择就是从一个原始的特征集合中选 择一个最优特征子集的过程，这个特征子集应当保留原始特征集合的全部或大部分类别信息。数据 分类的任务是找出一个类别的概念描述( 通常称之为分类器) ，它代表了这类数据的整体信息，即该 类的内涵描述，一般用规则或决策树模式表示，该模式能够把数据库中的元组映射到给定类别集中 的某一个。 本文在特征选择算法和数据分类算法两个方面做出了一些比较深入的研究。在特征选择算法方 面，研究了信息度量中的互信息在衡量特征与类别之间和各个特征之间的关系时所起到的作用；主 要针对特征选择过程中的冗余特征消除问题作出了具体而深入的研究。在数据分类算法方面，研究 了在分类过程中条件互信息在评价特征重要性方面的作用；利用条件互信息建立互信息网络 井通 过互信息网络简化分类规则。并通过实验对这两方蔼的研究成果作出了较为科学的评价。 本文在第4 章通过讨论特征选择的过程，分析和论证了在特征选择过程中消除冗余特征的重要 性，提出了在特征选择过程中消除冗余特征的一种算法_ i 丘似的马尔可夫毯过滤法。共在此基础 上提出了一个基于信息论的特征选择算法- e c b f 算法。该算法以信息论量度为基本工具结合 了在特征子集评估中的特征冗余分析，利用单个特征评估在计算上的优势，将特征冗余性分析引入 到单个特征评估方法中，实现对高维度数据集的高效的特征选择。 在文中我们选取了基于信息论的关联量度r m i ，该量度通过互信息和信息熵构造而成，从总体 上反映了各个特征之间以及特征与类别之间的关联程度。通过运用关联度量l t m i 计算各个特征与类 别之间的关联度，可以将特征集中的与类别不相关的特征全部过滤出去，产生与类别相关的相关特 征集。但在相关特征集中通常存在着冗余的特征消除冗余特征将使得后续的数据分类模型的建立 更加有效。 特征冗余通常以特征关联来确定。普遍认为如果两个特征的数值完全地相互关联，则它们彼此 是冗余的。事实上，当一个特征与一组特征部分地相互关联的时候，不可能直接决定该特征是冗余 的。马尔可夫毯是进行特征冗余性分析的一种强有力的工具，它描述了一个冗余特征在特征集中的 主要表现，通过冗余特征与特征集的统计关系可以判定特征的冗余性，并由此产生了判定冗余特征 的马尔可夫毯过滤法。 由于马尔可夫毯过滤法在计算上的要求过高，在高维度的数据集中，应用马尔可夫毯过滤法分 析和判定冗余特征必然会使特征选择算法的效率降低，因而这种方法是不适合商维度的特征选择 的- 在马尔可夫毯过滤法中，我们通过抽取该方法的基本特性，分析该方法的主要组成部分并结合 关联量度r m i ，推论并构造了一个近似的马尔可夫毯过滤法，并以此方法在相关特征集中进行冗余 特征分析。 在近似的马尔可夫毯过滤法中，特征与类别之闻的关联称为c 关联，两个特征之问的关联称为 f 关联，没有任何的近似的马尔可夫毯的特征称为优越的特征。近似的马尔可夫毯的基本工作原理 是：如果特征x 的c - 关联大于特征y 的c 一关联且特征之间的f 关联大于特征y 的c 关联，则 特征y 是冗余的。 由近似的马尔可夫毯的基本工作原理可知其基本性质：具有晟大c - 关联值的特征不存在近似的 马尔可夫毯，该特征是优越的特征。利用该性质，在对相关特征的c 。关联值进行排序后，可以从具 有最大c 关联值的特征开始，逐步消除所有的冗余特征，而保留优越的特征，最后形成的特征集由 所有优越的特征组成。 利用近似的马尔可夫毯过滤法进行相关性和冗余性分析，就是通过选择所有的优越特征并且除 去剩余特征的方法。它使用c 关联和f - 关联来确定特征冗余，而且结合前向序列选择和除去冗余 特征因此，它不但围绕所有的特征对进行f - 关联分析。而且比纯粹的前向序列选择或后向消除法 取得更高的效率。 本文第5 章提出了一个建立在相关特征集上的数据分类方法m n 算法。该算法以信息论 量度为基本工具通过条件互信息评估各个相关特征在分类过程中的等级次序，产生简洁的分类规 则，并评估分类规则在分类过程中的重要程度。 互信息网络( l u t u a l i n f o r m a t i o nn e t w o r k ( m i n ) ) 是一种信息论方法，在拓朴结构上类似于神 经网络，在预测方式上类似于决策树。建立互信息网络的原理是：在一个已知结点的条件下，如果 一个特征与类别特征之间的条件互信息值最大，则该特征是此结点下最重要的特征，并由此分裂产 生新的结点。 在互信息网络构建过程中，对于任何给定的结点z ，找出不属于结点z 分支的所有特征，并计 算这些特征与类别之问的条件互信息取得使条件互信息值最大的特征，则该特征是在结点z 的条 件下对分类最重要的特征，将该特征按其特征值进行结点分裂。如果没有特征使得条件互信息显著 增加，则该结点为最终结点，将该结点与类别结点进行连接，并计算结点与类别结点之间的权重， 形成一条分类规则。 通过条件互信息建立的互信息网络分类模型具有如下优点：在分类预测准确率上比其它分类学 习算法有所提高；由它产生的规则形式简单；模型描述简洁。 本文第6 章对特征选择算法e c b f 和分类学习算法m i t n 进行了实验分析评估。论证了e c b f 算法在特征选择过程中的运行效率和算法有效性。 评估并指出了e c b f 算法在应用于低维度的数据集时，其运行效率和算法的有效性与其它特征 选择算法不相上下；但在应用于高维度的数据集时。e c b f 算法表现出一定的优势。在众多的包含 n 西南农业大学硕士学位论文摘要 有大量不相关特征和冗余特征的领域中。对于有指导学习的特征选择，e c b f 算法是有效率和效力 的。 对建立在e c b f 算法之上的分类学习算法m 1 t n 的有效性和效率进行了评估，证实了m e n 算 法在预测准确率方面的优势，也证实了m i t n 算法在运行效率上还存在一定的不足。 关键词：数据挖掘特征选择分类信息论马尔可夫毯 i i l a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n d t e c h n o l o g y ，p e o p l ec o m e t or e a l i z et h ei m p o r t a n c e o fi n f o r m a t i o n i nt h ep r e s e n tt i m e s o f k n o w l e d g ee x p l o s i o n ，p e o p l en e e du r g e n t l yam e t h o dt ol o c a t et h e u s e f u li n f o r m a t i o ni nt h ev a s ta m o u n to fd a t ap r o v i d e db y c o m p u t e r a n dt h u sd a t am i n i n gc o m e s i ni t s w a y i ns u c has i t u a t i o n o v e rt h ep a s tt e ny e a r s ，g r e a tp r o g r e s sh a sb e e nm a d ei nt h er e s e a r c ho fd a t a m i n i n g t h eu t i l i z a t i o no fv a r i o u sd a t am i n i n gs o f t w a r eh a sg r e a t l yp r o m o t e dt h ep e o p l e sa b i l i t yt o g r a s p a n dd i s p o s eo ft h ec o m p u t e ri n f o r m a t i o na n dt h u sh a s b r o u g h t a b o u tag o o db e n e f i t d a t am i n i n gi sa na n a l y t i cp r o c e s sd e s i g n e dt o e x p l o r ed a t a ( u s u a l l yl a r g ea m o u n t so fd a t a t y p i c a l l yb u s i n e s s o rm a r k e tr e l a t e d ) i ns e a r c ho fc o n s i s t e n t p a t t e r n sa n ds y s t e m a t i cr e l a t i o n s h i p s b e t w e e nv a r i a b l e s ，a n dt h e nt ov a l i d a t et h ef i n d i n g sb ya p p l y i n gt h ed e t e c t e dp a t t e r n st on e ws u b s e t so f d a t a f e a t u r es e l e c t i o na n dc l a s s i f i c a t i o na r et w oi m p o r t a n ta s p e c t so fd a t am i n i n g t h ep r o c e s so f f e a t u r es e l e c t i o ni st os e l e c tab e s ts u b s e to ff e a t u r e sf r o map r i m i t i v es e t , t h eb e s ts u b s e ts h o u l dh o l da u o ram a j o r i t yo fc l a s si n f o r m a t i o ne x i s t i n gi np f i m i d v es e t t h em i s s i o no ft h ed a t ac l a s s i f i c a t i o ni st o f i n do u tt h ec o n c e p t d e s c r i p t i o no f ac a t e g o r y ，a n di tr e p r e s e n t e dt h ew h o l ei n f o r m a t i o no ft h e s ed a t a i nt h i sp a p e r ，w ed os o m er e s e a r c h e si na l g o r i t h mo ff e a t u r es e l e c t i o na n dd a t ac l a s s i f i c a t i o n i nt h e a s p e c to f f e a t u r es e l e c t i o na l g o r i t h m ，f i r s t l yw e s t u d yt h ea c t i o no fm u t u a li n f o r m a t i o ni nw c i g h t i n gt h e r e l a t i o na m o n gf e a t u r e sa n dt h er e l a t i o nb e t w e e nf e a t u r ea n dc l a s s b a s e do nm u t u a li n f o r m a t i o n ，s o m e c o n c r e t ea n d i n d e p t hr e s e a r c h e sa i m i n ga tt h ep r o b l e m o fe l i m i n a t i n gr e d u n d a n tf e a t u r e si nt h ep r o c e s s o ff e a t u r es e l e c t i o nh a v eb e e na c h i e v e d i nt h ea s p e c to fc l a s s i f i c a t i o na l g o r i t h m ，w ei n v e s t i g a t et h e e f f e c to fc o n d i t i o n a lm u t u a li n f o r m a t i o nw h e na p p l y i n gi ne v a l u a t i n gt h ei m p o r t a n c eo ff e a t u r e si nt h e p r o c e s so fc l a s s i f i c a t i o n ，e s t a b l i s ht h em u t u a l i n f o r m a t i o nn e t w o r k w i t hc o n d i t i o n a lm u t u a li n f o r m a t i o n ， a n dm a k et h ec l a s s i f i c a t i o nr u l e sb ec o n c i s e f i n a l l y ，w ee v a l u a t et h er e s u l t so ft h et w oa s p e c t sc o r r e c t l y b ys o m ee m p i r i c a ls t u d i e s i nc h a p t e r4o ft h i sp a p e r , w ea n a l y z ea n dd e m o n s t r a t et h ei m p o r t a n c eo fr e m o v i n gr e d u n d a n t f e a t u r e si nt h ep r o c e s so ff e a t u r es e l e c t i o n ，a n dt h e np r o v i d ea na l g o r i t h mo fr e m o v i n gr e d u n d a n t f e a t u r e si nt h ep r o c e s so ff e a t u r es e l e c t i o nc a l l e da p p r o x i m a t em a r k o v - b l a n k c tf i l t e r m o r e o v e r ，b a s e d o nt h ea p p r o x i m a t em a r k o v b l a n k e tf i l t e r ，w ep u tf o r w a r daf e a t u r es e l e c t i o na l g o r i t h mb a s e do i l i n f o r m a t i o nt h e o r i e sc a l l e de c b fa l g o r i t h m u s i n g i n f o r m a t i o n t h e o r ym e a s u r e s ，c o m b i n i n g t h e r e d u n d a n tf e a t u r e a n a l y s i s i ns u b s e te v a l u a t i o na n dm a k i n gu s eo ft h ea d v a n t a g ei nc a l c u l a t i o no f i n d i v i d u a le v a l u a t i o n ，t h ee c b f a l g o r i t h ma c h i e v e se f f i c i e n tf e a t u r es e l e c t i o ni nh i g h - d i m e n s i o n a ld a t a b ya p p l y i n gr e d u n d a n tf e a t u r ea n a l y s i st oi n d i v i d u a le v a l u a t i o n i nt h i sp a p e rw es e l e c tc o r r e l a t i o nm e a s l l r e s ( r m i ) b a s e do ni n f o r m a t i o n - t h e o r yt om e a s u r et h e 西南农业大学硕士学位论文a b s t r a c t c o r r e l a t i o n a m o n g f e a t u r e sa n db e t w e e naf e a t u r ea n dc l a s s t h er m ii sc o n s t r u c t e d b y i n f o r m a t i o n - e n t r o p ya n dm u t u a li n f o r m a t i o n b yc a l c u l a t i n gt h ec o r r e l a t i o nb e t w e e nf e a t u r ea n dc l a s s ， w ec a l lr e m o v et h ei r r e l e v a n tf e a t u r e sf r o mt h ep r i m i t i v es e t ，a n df o r mar e l e v a n tf e a t u r es e t b u tu s u a l l y t h e r ea r es o m er e d u n d a n tf e a t u r e si nr e l e v a n ts e t ，e l i m i n a t i n gr e d u n d a n tf e a t u r e sw i l ll e a dt oam o r e e f f i c i e n tp r o c e s so f e s t a b l i s h i n gc l a s s i f i c a t i o nm o d e l t h ef e a t u r er e d u n d a n c yi s u s u a l l yi d e n t i f i e db yt h ec o r r e l a t i o nm e a s u r ea m o n gf e a t u r e s i t i s c o m p r e h e n s i v et o t h i n kt h a t ：i ft h ev a l u e so ft w of e a t u r e si s c o m p l e t e l yc o r r e l a t e d ，t h e nt h e y a r e r e d u n d a n te a c ho t h e r i nf a c t ，w h e naf e a t u r ei sp a r t l yc o r r e l a t e dw i t has e to ff e a t u r e s ，w ec a nn o td e c i d e d i r e c t l yt h a tt h ef e a t u r e i sr e d u n d a n t m a r k o v - b l a n k e ti sap o w e r f u lm e t h o di na n a l y z i n gr e d u n d a n tf e a t u r e s i th a sd e s c r i b e dt h em a i n p e r f o r m a n c eo far e d u n d a n tf e a t u r e w ec a ni d e n t i f yt h er e d u n d a n tf e a t u r eb yt h es t a t i s t i c a lm e a s u r e b e t w e e naf e a t u r ea n das u b s e to ff e a t u r e s a n dt h i sf o r m sm a r k o v b l a n k e tf u t c r h o w e v e r ，b e c a u s eo f a l a r g e o fc a l c u l a t i o no fm a r k o v b l a n k e t f i l t e r , a p p l y i n g i tt oe l i m i n a t er e d u n d a n tf e a t u r e si n h i g h d i m e n s i o n a ld a t a s e tw i l ld e p r e s st h ee f f i c i e n c yo ff e a t u r es e l e c t i o na l g o r i t h mb ya l lm e a n s s ot h i s m e t h o di su n s u i t a b l ei nh i 曲- d i m e n s i o n a ld a t as e t s b yp i c k i n gu pt h eb a s i cp r o p e r t yi n t h em a r k o v - b l a n k e th l t e r , a n a l y z i n gi t sm a i ns t r u c t u r e ， c o m b i n i n gt h ec o r r e l a t i o nm e a s u r e 眦d e d u c ea n dc o n s t r u c ta na p p r o x m a t em a r k o v - b l a n k e th l t e r , a n du s e di tt oa n a l y z er e d u n d a n tf e a t u r e si nr e l e v a n tf e a t u r e ss u b s e t i no u ra p p r o x i m a t em a r k o v - b l a n k e tf i l t e r ，w ed e f i n et h ec o r r e l a t i o nb e t w e e nf e a t u r ea n dc l a s sa s c - c o r r e l a t i o n ，t h e c o r r e l a t i o n a m o n gf e a m m s a s f - c o r r e l a t i o n ，a n d ar e l e v a n tf e a t u r ew i t hn o a p p r o x i m a t e m a r k o v - b l a n k e ta sp r e d o m i n a n tf e a t u r e t h e p r i m a r yp r i n c i p l eo fa p p r o x i m a t em a r k e r - b l a n k e ti s ：i ft h ec - c o r r e l a t i o no ft h ef e a t u r ex i s l a r g e rt h a nt h ec - c o r r e l a t i o no ft h ef e a t u r ey ，a n dt h ef - c o r r e l a t i o no ft h e t w of e a t u r e si sl a r g e rt h a nt h e c - c o r r e l a t i o no ff e a t u r ey t h e nt h ef e a t u r eyi sar e d u n d a n c y 。f r o mt h ep r i m a r yp r i n c i p l ew e c a l lt a k ea c o n c l u s i o n ：t h ef e a t u r et h a th a st h e l a r g e s t c - c o r r e l a t i o nv a l u ed on o th a v e a n ya p p r o x i m a t e m a r k o v b l a n k e t a n dt h ef e a t u r ei sap r e d o m i n a n tf e a t u r e m a k i n gu s eo ft h ea b o v ec o n c l u s i o n ，a f t e r s o r t i n gt h ec - c o r r e l a t i o n ，w ec a ne l i m i n a t e a l lr e d u n d a n tf e a t u r e sa n dr e m a i nt h ep r e d o m i n a n tf e a t u r e s o u rm e t h o d a p p r o x i m a t e sr e l e v a n c ea n dr e d u n d a n c ya n a l y s i sb ys e l e c t i n ga l lp r e d o m i n a n t f e a t u r e s a n dr e m o v i n gt h er e s tf e a t u r e s i tr i s e sb o t hc - a n df - c o r r e l a t i o n st od e t e r m i n ef e a t u r er e d u n d a n c ya n d c o m b i n e ss e q u e n t i a lf o r w a r ds e l e c t i o nw i t he l i m i n a t i o ns ot h a ti tn o to n l yc i r c u m v e n t sf u l lp a i r - - w i s e f - c o r r e l a t i o na n a l y s i sb u ta l s oa c h i e v e sh i g h e re f f i c i e n c yt h a np u r es e q u e n t i a lf o r w a r ds e l e c t i o n o r b a c k w a r de l i m i n a t i o n i nc h a p t e r5o ft h i s p a p e r ，w eb r i n gac l a s s i f i c a t i o na l g o r i t h mc a l l e dm i t n w h i c hb a s e do nt h e r e l e v a n tf e a t u r es u b s e tb r o u g h tb ye c b f a l g o r i t h m u s i n gi n f o r m a t i o n t h e o r ym e a s u r e si nt h ep r o c e s s v 西南农业犬学硕士学位论文 a b s t r a c t o f c l a s s i f i c a t i o n ，t h i sa l g o r i t h me v a l u a t e st h ei m p o r t a n c eo fe v e r yf e a t u r eb yc a l c u l a t i n gt h e i rc o n d i t i o n a l m u t u a li n f o r m a t i o n ，f o r m sc o m p a c tc l a s s i f i c a t i o nr u l e s ，a n de s t i m a t e st h e s i g n i f i c a n c eo fe a c hr u l e m u t u a l i n f o r m a t i o n n e t w o r k ( m 踯i s a l l i n f o r m a t i o n - t h e o r e t i cm e t h o d i tr e s e m b l e st h e t o p o l o g i c a ls t r u c t u r eo fn e u r a ln e t w o r k s a n di t i ss i m i l a rt od e c i s i o n t r e ei np r e d i c t i v em e t h o d t h e p r i n c i p l eo fe s t a b l i s h i n gt h em u t u a l - i n f o r m a t i o nn e t w o r ki s ：g i v e nan o d e ，i ft h ec o n d i t i o n a lm u t u a l i n f o r m a t i o nv a l u ei st h el a r g e s to fa l l ，t h e nt h ef e a t u r ei st h em o s ti m p o r t a n tf e a t u r ea n dt h en o d es h o u l d b e s p l i t i nt h ec o n s t r u c tp r o c e s so fm u t u a l i n f o r m a t i o nn e t w o r k ，g i v e na n yn o d eo ft h en e t w o r k ，w cc a n c a l c u l a t et h ec o n d i t i o n a lm u t u a li n f o r m a t i o nv a l u e sb e t w e e na l lo t h e rf e a t u r e sa n dc l a s s ，a n df i n dt h e l a r g e s to ft h e m t h e nt h ef e a t u r ew i t hl a r g e s tv a l u e i st h em o s t i m p o r t a n tf e a t u r ei nc l a s s i f i c a t i o n a l lt h e v a l u e so ft h ef e a t u r ew i l lb e c o m et h en e x tn o d e s ht h e r ei sn o ta n yf e a t u r et om a k et h ec o n d i t i o n a l m u t u a li n f o r m a t i o ni n c r e a s e d ，t h e nt h eg i y e nn u d ei saf i n a ln o d e w ec o n n e c tt h en o d ew i t ha l lt h e t a r g e t n u d e sa n dc a l c u l a t et h ew e i g h tb e t w e e nt h e s en o d e sa n dt h ef i n a ln o d e t h u si tf o r m sa c l a s s i f i c a t i o nr u l e t h ec l a s s i f i c a t i o nm o d e lc o n s t r u c t e db yc o n d i t i o n a lm u t u a li n f o r m a t i o nh a ss o m ea d v a n t a g e s ：i t h a sm o r e p r e d i c t i v ea c c u r a c yt h a no t h e r c l a s s i f i c a t i o na l g o r i t h ma n dt h er u l e sa l es i m p l e i nc h a p t e r6o ft h i sp a p e r ，w ea n a l y z ea n de v a l u a t et h ef e a t u r es e l e c t i o na l g o r i t h ma n dc l a s s i f i c a t i o n a l g o r i t h mb y s o m e e m p i r i c a l e v a l u a t i o n s w ec o n f i r mt h a tt h ee c b f a l g o r i t h mi se f f i c i e n ta n de f f e c t i v ei nt h ep r o c e s so ff e a t u r es e l e c t i o n a n dw ep o i n to u tt h a tt h ee f f i c i e n c ya n de f f e c t i v e n e s so fe c b fa l g o r i t h mi sc o m p a r a t i v ew i t ho t h e r f e a t u r es e l e c t i o na l g o r i t h mw h e nt h e ya r ea p p l i e dt ol o w e rd i m e n s i o n a ld a t as e t b u te c b fa l g o r i t h m h a sm o r ea d v a n t a g e sw h e nt h eg i v e nd a t as e th a sh i g h e rd i m e n s i o n i tc o m e st ot h ec l a s s i f i c a t i o na l g o r i t h mb a s e do ne c b f w ea p p r o v et h a tm 1 t na l g o r i t h mh a s s o m e a d v a n t a g e s o n p r e d i c t i v ea c c u r a c ya l t h o u g h i th a ss o m el i m i t a t i o no ni t se f f i c i e n c y k e yw o r d s ：d a t am i n i n g f e a t u r es e l e c t i o nc l a s s i f i c a t i o ni n f o r m a t i o nt h e o r y m a r k o vb l a n k e t v l 西南农业大学硕士学位论文 第1 章文献综述 第1 章文献综述 1 1 数据挖掘 本研究的学术背景是数据挖掘( d a t am i n i n g ，简称为d m ) 。下面简单介绍数据挖掘的产生背 景，数据挖掘基本概念、种类及其研究现状和发展趋势。 1 1 1 数据挖掘产生的背景 随着数据库技术的不断发展及数据库管理系统的广泛应用，大型数据库系统己经在各行各业 普及，数据库中存储的数据量急剧增大。在大量的数据背后隐藏着许多重要信息，而这些重要信 息可以很好地支持人们的决策。可是目前用于对这些数据进行分析处理的工具却很少。目前人们 用到的主要是数据库的存储功能，而隐藏在这些数据之后的更重要的信息则没有充分利用。这些 信息是关于数据的整体特征的描述及对发展趋势的预测在决策生成的过程中具有重要的参考价 值。数据库技术的日益成熟和数据仓库的发展为数据挖掘提供了发挥的平台【1 8 。 在数据库技术飞速发展的同时，人工智能领域的一个分支机器学习的研究也取得很大进 展。自5 0 年代开始机器学习的研究以来，先后经历了神经模型和决镱理论、概念符号获取及知识 加强和论域专用学习三个阶段，根据人类学习的不同模式人们提出了很多机器学习方法，如：实 例学习、观察和发现学习、神经网络和遗传算法等等睁“。其中某些常用且较成熟的算法己被人 们运用于实际的应用系统及智能计算机的设计和实现中。数据挖掘中的许多方法就来自于机器学 习。 由于数据存储技术的日渐成熟，数据库和联机事务处理( ( 0 p ) 已经被广泛应用于金融、证券、 保险、销售以及天气预报、工业生产、分子生物学、基因工程研究等各行各业。因而积累了大量 数据洱。人们已经不满足于简单的统计分析，而需要发现更深层次的规律，提供更有效的决策 支持。而传统专家系统靠人工获取知识这一“瓶颈”在日益膨胀的“数据山”面前显得更加无力。 数据挖掘的对象是某一专业领域中积累的数据：挖掘过程是一个人机交互、多次反复的过程：挖 掘的结果要应用于该专业。因此数据挖掘的整个过程都离不开应用领域的专业知识。目前数据挖 掘技术在货篮数据( b a s k e td a t a ) 分析、金融风险预测、产品产量、质量分析、分子生物学、基因工 程研究、i n t e r n e t 站点访问模式发现以及信息搜索和分类等许多领域得到了成功的应用【1 2 - 1 4 。 因此，数据挖掘是应用需求推动下跨学科发展的产物，而且在近几年里迅速发展起来【1 7 i 。这 个领域的实质是智能技术与数据库技术的结合，不但为决策者提供知识和策略，而且为投资者带 来经济效益。这就是数据挖掘( d a t am i n i n g ) 技术产生的背景。 1 1 2 数据挖掘的基本概念 数据挖掘p a t am i n i n g ) 中文又译作数据采掘，1 9 9 5 年在加拿大召开了第一届知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t 曲。一k d d ) 和数据挖掘( d a t am i n i n g d m ) 国际学术会议以后t 数据挖掘开始流行，它是“知识发现”概念的深化。k d d 一词是在1 9 8 9 年8 月于美国底特律市 召开的第一届k d d 国际学术会议上正式形成的。 数据挖掘就是通过分析已经存在在数据库中的数据解决问题。数据挖掘被定义成发现数据模 式的过程 4 l 【7 l 。这个过程必须是自动化的或者( 通常) 是半自动化的。被挖掘出来的规则应该意味着 某些方面的优势一一特别是经济方面的优势。 另一种比较公认的定义是：数据挖掘就是从大型数据库中的数据中提取人们感兴趣的知识。 这些知识是隐含的、事先未知的潜在的有用的信息提取的知识表示为概念( c o n c e p t s ) 、规则皿u l e ) 、 规律( r e g u l a r i t i e s ) 、模式但a n e m s ) 等形式【3 | 【”】。 这种定义把数据挖掘的对象定义为数据库，更广义的说法是：数据挖掘意味着在一些事实或 观察数据的集合中寻找模式的决策支持过程。 现在普遍接受的定义是：数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程1 1 1 1 2 。 从概念可以看出，数据挖掘的范围比k d d 广泛，k d d 是面向数据库的，而数据挖掘面向的 数据形式可以有多种多样，它可以是数据库，还可以是图像，声音等媒体数据。从过程上看，数 据挖掘又可以被看作是从数据库中提取有用信息这一过程的同义词，它是k d d 的一个步骤。 本文的主要内容是数据挖掘中的分类问题。本文中的分类是面向数据库的分类，所以严格地 说它属于k d d 范畴。有些分类是面向文本，页面等其它媒体形式的。它们属于一般意义上的数 据挖掘的范畴。 1 1 3 数据挖掘的种类