（計(jì)算機(jī)軟件與理論專業(yè)論文）訓(xùn)練基于ep的分類器算法.pdf

摘要 數(shù)據(jù)挖掘又稱數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)，是從大量數(shù)據(jù)中用非平凡的方法發(fā)現(xiàn)有用 的知識(shí)。分類是數(shù)據(jù)挖掘中的一項(xiàng)非常重要的任務(wù)，在商業(yè)、金融、電訊、d n a 分析、科學(xué)研究等諸多領(lǐng)域具有廣泛的應(yīng)用。統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等領(lǐng) 域的研究者提出了很多分類方法，大部分算法是內(nèi)存駐留算法，適用于小型數(shù)據(jù) 集。隨著數(shù)據(jù)集的數(shù)據(jù)量和維數(shù)的增加，建立高效的、適用于大型數(shù)據(jù)集的分類 法已成為數(shù)據(jù)挖掘的一個(gè)挑戰(zhàn)性任務(wù)。 基于顯露模式( e m e 蟛n g p a t c e m ，e p ) 的分類方法是針對(duì)大型數(shù)據(jù)集的分類 提出的，e p 是gd o n g 和j “提出的一種新的知識(shí)模式，這些模式能夠捕獲目 標(biāo)類和非目標(biāo)類上多組屬性之間的不同，具有很好的分類性能。第一個(gè)基于e p 的分類算法是gd o n g 等提出的c a e p 算法，此后相繼提出了j e p c l a s s i f i e r 、 b c e p 和d e e p s 等一系列基于e p 的分類算法。相關(guān)研究表明，基于e p 的分類算 法的平均分類準(zhǔn)確率優(yōu)于決策樹等傳統(tǒng)算法，顯示了e p 在分類方面的優(yōu)越性。 本文提出了一種可調(diào)整權(quán)值的基于e p 的分類方法c e p a w 。c e p a w 使用基 本顯露模式( e e p ) 并聚合e e p 的區(qū)分能力建立分類器。在聚合e e p 的區(qū)分能 力時(shí)，e e p 的權(quán)值通過(guò)訓(xùn)練自適應(yīng)地選取。訓(xùn)練分為兩個(gè)階段：第一階段的主要 任務(wù)是挖掘e e p s ，構(gòu)造初始分類器。在e p 的選取以及評(píng)分函數(shù)方面。我們都采 用了不同于以往的基于e p 的分類算法的方法。第二階段是權(quán)值的自適應(yīng)調(diào)整。 丌始，所有e p 的權(quán)值相同。反復(fù)地使用初始分類器對(duì)訓(xùn)練樣本進(jìn)行分類，并通 過(guò)考察每個(gè)e p 對(duì)訓(xùn)練樣本的分類效果調(diào)整e p 的權(quán)值，直到分類器的分類準(zhǔn)確 率不能再提高。 為了測(cè)試算法的分類性能，使用了u c i 機(jī)器學(xué)習(xí)庫(kù)中的1 2 個(gè)數(shù)據(jù)集作為實(shí) 驗(yàn)數(shù)據(jù)集，并將實(shí)驗(yàn)結(jié)果與n b 、c 5 o 、c a e p 、l b 以及b c e p 算法進(jìn)行比較。 結(jié)果表明，c e p a w 具有更好的分類準(zhǔn)確率，自適應(yīng)地選取e p 的權(quán)值比以支持 度為權(quán)值的評(píng)分策略更加合理。當(dāng)數(shù)據(jù)分布發(fā)生輕微變化時(shí)，通過(guò)再訓(xùn)練，調(diào)整 e p 的權(quán)值，c e p a w 可以較好地適應(yīng)新的數(shù)據(jù)分布。 關(guān)鍵字：機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘，分類，顯露模式 a b s 8 c t a b s t r a c t d a t am i l l i n g ，a l s oh l o w n 鶴i ( i l o w l e d g ee 畦8 c o v e r yi nd a t a b a s e ，r e f b r st o m i n i n g k n o w l e d g e 丘d md a t a i nv e r yl a r g ed a t a b 嬲e si nn 0 枷v i a lm e m o d s c 1 a s s i f i 訓(xùn)o n ，a sa l li m p o n a f l tt l l e m ei nd a t a 嘶n i n 島h a sb e e nr 鼯e 盯c h e de d i 盯i n s t a t i s t i c s ，m a c h i n el e a r i l i n & n e u r a ln e t w o r k ，e x p e ns y s t e i t l s ，e t c b u tm o s ta 1 9 0 r i t l l m s a r ec o n 6 n e d m e m o r y ，t y p i c a l l y 鵲s u m i n gas m a l ld a t as i z c w i t h 也eg r o w t ho fd a t ai n v o l 啪ea i l dd i m e l l s i o m l i t y ，i ti ss m lac h a l l e l l g et ob u i l de f f t i v ec l a s s m e r sf o rl a r g e d a t a b a s e s m e t l l o d sf o rc l a s s i f i c a t i o nb ye m e f g i n gp a t t e m s ( e p s ) w e r ep m p o s e di no r d e rt o c l a s s 母l a r g ed a t a s e t s e p sa r en e wl 【i n do fl ( 1 l o w l e d g ep a t c 鋤p r e s e n 硼b ygd o n g a n dj “i n1 9 9 9 ，w h i c hc a nc 印m r cm ei n h 刪l td i s d n c t i o n sb c t w e e nd i f f 旨t c l a s s e so f d a t a s oe p sa r cu s e 如l 衙b u i l d i n ga c c u 墻t ec l a s s i f i e r s c a e ew 】i i c hw a s p m p o s e db yl i ， d o n ga 1 1 dr 鋤鋤o h 柚啪oi n l9 9 9 ，i st h ef i r s te p - b a s e d c l a s s m c a t i o na l g o r i l i n a f t e rt l l a t ，as 商e so fe p _ b a s c dd 髂s 湎e r sw e r ep m p o s e do n e a f t e ra i l o m e rs u c ha sb c e p ，j e p d a s s m d e e p s ，e t c i th a ss h o w nm a te p _ b a s e d c l a s s i 矗e ri sb e t t e rt l l a ns o m ec l a s s i cc l a s s i f i c a t i o nm e l o d ss u c ha sd e c i s i o nt r e e s t h i sd i s s e r t a t i o np r o p o s e san o v e le p - b 踮c dc l a s s i f i c a t i o nm e t h o d ， c a l l e d c l a s s 硪c a d o nb ye m e r g i n gp a t t e m s 麗t ha d j u s t a b l ew e i 曲t s ( c e p a w ) i nt h e 響n i n g p h a s e ，c e p a wu s e sas p e c i a lk i n do fe p s ，c a l l e de s s e n t i a l 鋤e r g i n gp a t t c i n s ( e e p s ) ， a n da g 爭(zhēng)e g a t e sd i 彘r e n t i a t i n gp o w e r so fe e p st oc o n s m 】c tc l a s s i f i e r s i no r d e rt o a g 掣g a t ed i 丘孤t i a t i n gp o w c r so fe e p s ，e a c he e pi sa s s o c i a t e dw i t ha na d j u s t a b l e w e i 曲tt h a ti sc h o s e nb y 仃a 岫i n 呂t r a i n i n gi sd i v i d e di n t o 伽op h a s e s i nt h ef i r s t p h a s c ，e e p sa r em i n e da n da ni n i t i a ld a s s m e ri sc o n s t m c t e d o l l ra 1 9 0 r i t l l mi s d i 丘旨e n tf b mt l l ep r e v i o u se p _ b a s e da l g o r i t h m s 、v i 出r e s p e c tt ot h ek i n do fe pa 1 1 dt h e s c o r i r 喀矗m c t i o n i nm es e c o n dp h a s e ，m ew e i g h t so fc e p sa r ca d j u s t a b l eb yt r a i n i n g f i r s t l y ，w e i g h t so f a l le e p sa r es e te q u a l ly b yu s i n gm ei n i t i a ld a s s m e rt oc l a s s i 毋l e t r a i n i n gs 鋤p l e si t e r a t i v e l y ，w ea d j u s tt h ew e i g h t so fe p sa c c o r d i n gt ot i l er e s u l t so f c l a s s i f 弭n g 吼t i lt h ea c c u r a c yr a t ec a nn o tb ei n c r e a s e d i no r d e rt oe s t i m a t e 廿l ea c c u 豫c yo fo u ra l g o t h m s ，o u re x p e m e n ts t u d yc 謝e d o n1 2b 髑曲m a 出d a l 夠e t 8 臺(tái)o m 乜弛u c 【m a c b i n ek ；蛐皿gr e p o s i t o r ys h o w st l l a t c e p a wp e r f o m l c 鼯c o m p a r a b l y 麗t l ld t l l 盯s t a t e - o f m e - a r td 鵲s i 丘c a t i o nm c l l l o d s s u c ha sn b ，c 5 o ，c b a ，c m a 咒c a e p 趾db c e pi nt e 肌so fo v e r a l lp r e d i c t i v e a c 咖c y - c o m p a r i n g 謝t l im c t l l o d s1 1 8 i n gs u p p o r t s 嬲w e i g h t s ，e x p 甜m e n t sh a v es h 嗍 t 1 1 a tc e p a wc a nc h o o s em o f er e 黯叩a b l ew e i 曲t st oa g 筍e g a l ed i 氆洲1 t i a t i n gp o w e 礙 o fe e p s w h e nt h ed a l ad i s m b u t i o nc h a i l g e ss l i 曲n y ，c e p a wc a i ia d a p tt ot l l en c w d a 協(xié)d i s m b u t i o nb yn 刪i l i n g k e y w o r d s ：m a c i l i n el e 秈i n g ，d a t am i n i g ，c i a s s m c a t i o n ，e m e 唔n gp a t t e h l 鄭重聲明 本學(xué)位論文是在導(dǎo)師指導(dǎo)下獨(dú)立撰寫并完成的。除文中 已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個(gè)人或集體已 經(jīng)發(fā)表或撰寫過(guò)的作品或成果。學(xué)位論文沒有剽竊、抄襲等 違反學(xué)術(shù)道德、學(xué)術(shù)規(guī)范的侵權(quán)行為，否則，本人愿意承擔(dān) 由此產(chǎn)生的一切責(zé)任和法律后果。特此鄭重聲明。 學(xué)位論文作者( 簽名) ：啦筆餒 口多年6 月年同 第一章緒論 第一章緒論 數(shù)據(jù)收集和數(shù)據(jù)存儲(chǔ)技術(shù)的快速進(jìn)步使得組織機(jī)構(gòu)可以積累海量數(shù)據(jù)。然而 海量數(shù)據(jù)遠(yuǎn)遠(yuǎn)超過(guò)了人的駕馭能力，人們面臨著“數(shù)據(jù)豐富，但信息貧乏”的尷 尬境地。因此，提取有用的信息成為巨大的挑戰(zhàn)。通常，由于數(shù)據(jù)量太大，無(wú)法 使用傳統(tǒng)的數(shù)據(jù)分析工具和技術(shù)處理它們。有時(shí)，即使數(shù)據(jù)集相對(duì)較小，由于數(shù) 據(jù)本身的非傳統(tǒng)特點(diǎn)，也不能使用傳統(tǒng)的方法。在其他情況下，需要回答的問(wèn)題 也不能使用已有的數(shù)據(jù)分析技術(shù)來(lái)解決。這樣，就需要開發(fā)新的方法。 數(shù)據(jù)挖掘是一種技術(shù)，它將傳統(tǒng)的數(shù)據(jù)分析方法與處理大量數(shù)據(jù)的復(fù)雜算法 相結(jié)合。數(shù)據(jù)挖掘也為探查和分析新的數(shù)據(jù)類型，為使用新的方法分析原有的數(shù) 據(jù)類型提供了機(jī)會(huì)。 1 1 什么是數(shù)據(jù)挖掘 數(shù)據(jù)挖掘是在大型數(shù)據(jù)存儲(chǔ)中，自動(dòng)地發(fā)現(xiàn)有用信息的過(guò)程。數(shù)據(jù)挖掘技術(shù) 用來(lái)探查大型數(shù)據(jù)庫(kù)，以發(fā)現(xiàn)先前未知的有用模式。數(shù)據(jù)挖掘還提供了一些機(jī)制， 用于預(yù)測(cè)未來(lái)的觀測(cè)結(jié)果。許多人把數(shù)據(jù)挖掘和數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn) ( k n o w l e d g ed i s c o v e r yi nd a t a b 8 s e s ，簡(jiǎn)稱k d d ) 看作是等價(jià)的概念a 在這種 觀點(diǎn)下，一種比較公認(rèn)的定義是wj f r a w l e y ，gp i a t e t s k y s h 印i r o 等人提出的， 其描述為： “數(shù)據(jù)挖掘，即數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)( k d d ) ，是一個(gè)在數(shù)據(jù)中提取模式的 過(guò)程，這些模式是有效的、新穎的、有潛在實(shí)用價(jià)值的和易于理解的?！?而另一些人把k d d 看作發(fā)現(xiàn)知識(shí)的完整過(guò)程，數(shù)據(jù)挖掘只是這個(gè)過(guò)程中關(guān) 鍵的一個(gè)部分。這種觀點(diǎn)對(duì)數(shù)據(jù)挖掘的定義是： “數(shù)據(jù)挖掘是數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)( k d d ) 過(guò)程中的一個(gè)步驟，這個(gè)步驟 由一些特定的數(shù)據(jù)挖掘算法組成，這些算法的任務(wù)是在滿足一定計(jì)算效率的約束 條件下，從數(shù)據(jù)中提取有效的模式?！?1 2 數(shù)據(jù)挖掘的任務(wù) 通常，數(shù)據(jù)挖掘任務(wù)分兩大類： 預(yù)測(cè)任務(wù)這些任務(wù)的目標(biāo)是根據(jù)其他屬性的值，預(yù)測(cè)特定屬性的值。被預(yù) 第一章緒論 測(cè)的屬性一般稱目標(biāo)( t a i 酣) 或依賴變量( d e p 姐d tv a r i 曲l e ) ，而用來(lái)做預(yù)測(cè) 的屬性稱解釋( e x p l a l l a t o r y ) 或獨(dú)立變量( i n d 印e i l d e n ta 州a b l e ) 。 搖述任務(wù)這里，目標(biāo)是導(dǎo)出概括數(shù)據(jù)中潛在聯(lián)系的模式( 相關(guān)、聚類、軌 道和異常) 。本質(zhì)上，描述性數(shù)據(jù)挖掘通常是探查，并且常常需要后處理技術(shù)驗(yàn) 證和解釋結(jié)果。 預(yù)測(cè)建模( p r 耐i c t i v em o d e 觸g ) 涉及用函數(shù)為目標(biāo)變量建立模型。有兩類 預(yù)測(cè)建模任務(wù)：分類( c l a s s 壤c a t i o n ) ，用于離散的目標(biāo)變量；回歸( r e 掣e s s i o n ) ， 用于連續(xù)的目標(biāo)變量。兩項(xiàng)任務(wù)目標(biāo)都是訓(xùn)練一個(gè)模型，它最小化目標(biāo)變量預(yù)測(cè) 值與實(shí)際值之間的誤差。預(yù)測(cè)建模可以用來(lái)確定顧客對(duì)產(chǎn)品促銷活動(dòng)的反應(yīng)，預(yù) 測(cè)地球生態(tài)系統(tǒng)的擾動(dòng)，或根據(jù)檢查結(jié)果判定病人是否患有某種特定的疾病。 關(guān)聯(lián)分析( a s s o c i a 廿蛆蚰a l y s i s ) 用來(lái)發(fā)現(xiàn)描述數(shù)據(jù)中強(qiáng)關(guān)聯(lián)特征的模式。 所發(fā)現(xiàn)的模式通常用蘊(yùn)涵規(guī)則或特征子集的形式表示。由于搜索空間是指數(shù)的， 關(guān)聯(lián)分析的目標(biāo)是以有效的方式提取最有趣的模式。關(guān)聯(lián)分析的應(yīng)用包括找出具 有相關(guān)功能的基因組，識(shí)別一起訪問(wèn)的w 曲頁(yè)面，理解地球氣候系統(tǒng)不同元素 之間的聯(lián)系。 聚類分析( d u s t 盯蚰a l y s i s ) 旨在發(fā)現(xiàn)緊密相關(guān)的觀測(cè)值組群，使得與屬于 不同簇的觀測(cè)值相比，屬于同一簇的觀測(cè)值相互之間盡可能類似。聚類用來(lái)對(duì)相 關(guān)的顧客分組，找出顯著影響地球氣候的海洋區(qū)域，壓縮數(shù)據(jù)。 異常檢測(cè)( a n o m a l yd e t e c d o n ) 的任務(wù)是識(shí)別其特征顯著不同于其他數(shù)據(jù)的 觀測(cè)值。這樣的觀測(cè)值稱為異常點(diǎn)( a n o m a l y ) 或離群點(diǎn)( o u t l i e r ) 。異常檢測(cè)算 法的目標(biāo)是發(fā)現(xiàn)真正的異常點(diǎn)，而避免錯(cuò)誤地將證常的對(duì)象標(biāo)注為異常點(diǎn)。換言 之，一個(gè)好的異常檢測(cè)器必須具有高檢測(cè)率和低誤報(bào)率。異常檢測(cè)的應(yīng)用包括欺 詐檢測(cè)、網(wǎng)絡(luò)攻擊、疾病的不尋常模式、生態(tài)系統(tǒng)擾動(dòng)。 1 3 數(shù)據(jù)挖掘算法的研究及應(yīng)用概況 近十幾年來(lái)，數(shù)據(jù)挖掘算法研究取得豐碩的成果，數(shù)據(jù)挖掘算法的主要研究 成果概要如下： 在關(guān)聯(lián)規(guī)則研究方面的主要成果有：尋找頻繁項(xiàng)集的a p r i o r i 算法、 f p g m w t l l 算法1 2 】針對(duì)不同情況設(shè)計(jì)的多維關(guān)聯(lián)規(guī)則挖掘方法哪】和多層關(guān)聯(lián)規(guī) 則挖掘方法【5 】等。 第一章緒論 在分類研究方面產(chǎn)生了多種分類方法和算法【6 】= 決策樹分類算法、源于關(guān)聯(lián) 規(guī)則的分類方法、貝葉斯分類方法、k 最i 臨近分類、基于案例的推理、遺傳算法、 粗糙集和模糊集方法等多種類型的分類方法。此外，還提出了以裝袋( b a g g i n g ) 和提升( b o o s t i i l g ) 為代表的可以有效提升某些算法分類準(zhǔn)確率的組合分類思想。 這些算法雖然來(lái)自不同領(lǐng)域并且具有各自不同的背景和特性，但是這些算法都在 一定的領(lǐng)域內(nèi)取得了很大的成功。盡管我們把算法分為上述幾個(gè)類型，但是這些 方法并不是孤立的，一個(gè)有效的分類算法可能是綜合上述多種思想設(shè)計(jì)完成的。 關(guān)于分類研究的問(wèn)題我們將在以后的章節(jié)做進(jìn)一步的論述。 在聚類研究方面也存在多種算法：基于劃分的聚類方法有k - m e a n s ， k m c d o i s 、和c i ，a r a 、c l a m n 等算法。層次聚類算法有a g n e s 算法、d i a n a 算法、b m t h 【”、c u r e 8 】、r o c k 9 1 、c h 柵d c o n 等算法?；诿芏鹊木垲愃?法有d b s c a 州1 ”、o p t i c s 、d e n c l u f l3 1 ?；诰W(wǎng)格的聚類方法有s t i n g 【1 4 】、 w a v e c l u s t 一15 1 、c l i o ue f l 6 等算法?；谀Ｐ偷木垲愃惴ㄓ薪y(tǒng)計(jì)學(xué)方法 c o b w e b 【17 1 、c l a s s i t 、a u t o c l a s s 和神經(jīng)網(wǎng)絡(luò)方法 2 0 0 ”。 其他研究方向也取得了豐碩的研究成果，如序列模式的挖掘有 g s p 吲( g e n c r a l i z c ds e q u e n t i a lp a t t e m s ) 算法和 p r c f i x s p a n 吲( p r e f i x p 刪e c t s e q u e n t i a lp a t t 鋤i i l i m n 曲算法。w e b 挖掘研究有尋找權(quán)威頁(yè)面的p a g c r a n k 【2 4 1 和 h i t s 2 5 1 算法( 目前g o o 掣e 搜索引擎使用該算法) 。總之，不同研究領(lǐng)域的研究 者都結(jié)合特定領(lǐng)域的應(yīng)用背景和需求，成功的丌發(fā)出了多種類型的數(shù)據(jù)挖掘算 法。 1 4 本文的內(nèi)容與組織 本文第一章簡(jiǎn)要介紹了數(shù)據(jù)挖掘的概貌。我們從數(shù)據(jù)挖掘概念的提出、研究 動(dòng)態(tài)、應(yīng)用概況，多個(gè)方面闡述了數(shù)據(jù)挖掘算法研究廣闊的前景和很高的應(yīng)用價(jià) 值，充分展示了本課題研究背景和意義。 本文的貢獻(xiàn)主要包括以下幾個(gè)方面：本文提出了種可調(diào)整權(quán)值的基于e p 的分類方法c e p a w ( c l a s s i f i c a t i o nb ye m e r g i n gp a t t e m sw i t h a d j u s t a b l ew e i 曲t s ) 。 c e p a w 使用基本顯露模式( e e p ) 并聚合e e p 的區(qū)分能力建立分類器。在聚合 e e p 的區(qū)分能力時(shí)，e e p 的權(quán)值通過(guò)訓(xùn)練自適應(yīng)地選取。與以支持度為權(quán)值的方 法相比，c e p a w 可以選取更合理的權(quán)值來(lái)聚合e e p 的區(qū)分能力。與現(xiàn)有的基于 第一章緒論 e p 的分類算法不同，本文所采用的初始分類器采用了增長(zhǎng)率與e p 權(quán)值相結(jié)合的 評(píng)分策略。實(shí)驗(yàn)表明c e p a w 算法具有很高的分類準(zhǔn)確率。 本文的其他部分將按如下結(jié)構(gòu)組織： 在本文的第二章，我們將詳細(xì)討論分類的基本概念、常見的分類方法、分類 模型的準(zhǔn)確性評(píng)估等問(wèn)題。在本章將定義和闡明分類問(wèn)題的最基本的概念以及分 類研究的一般過(guò)程，為我們下文深入探討分類問(wèn)題奠定基礎(chǔ)。 在本文的第三章，我們?cè)敿?xì)介紹顯露模式的概念以及現(xiàn)有基于e p 的分類算 法。通過(guò)本章的討論，我們首先闡明e p 的概念、性質(zhì)以及e p 的挖掘等問(wèn)題。 其次通過(guò)對(duì)現(xiàn)有基于e p 的分類算法的介紹，可以更清楚的表明c e p a w 算法與 現(xiàn)有的基于e p 的分類算法之間的聯(lián)系和區(qū)別。 在本文的第四章，我們介紹了一種可調(diào)整權(quán)值的基于e p 的分類方法 c e p a w 。在訓(xùn)練階段，c e p a w 使用e e p 建立分類器，并在聚合e p 的區(qū)分能力 時(shí)通過(guò)訓(xùn)練自適應(yīng)地確定e p 的權(quán)值。因?yàn)橛?xùn)練分類器分為兩個(gè)階段，我們分兩 部分詳細(xì)討論了c e p a w 算法。首先介紹了初始分類器的構(gòu)造，在e p 的選取以 及評(píng)分函數(shù)方面我們的初始分類器都不同于以往的基于e p 的分類算法。在訓(xùn)練 的第二部分，我們主要介紹了權(quán)值的自適應(yīng)選取策略。 在本文的五章，我們給出了c e p a w 算法在u c i 機(jī)器學(xué)習(xí)庫(kù)上的實(shí)驗(yàn)結(jié)果以 及與其他算法的對(duì)比分析。通過(guò)實(shí)驗(yàn)數(shù)據(jù)我們進(jìn)一步討論了c e p a w 算法的分類 特性，對(duì)算法進(jìn)行了更深入的探討。 第二章分類 第二章分類 數(shù)年來(lái)，分類問(wèn)題一直是機(jī)器學(xué)習(xí)、模式識(shí)別和統(tǒng)計(jì)學(xué)領(lǐng)域的一個(gè)重要研究 課題，目前也成為數(shù)據(jù)挖掘的一個(gè)重要任務(wù)，當(dāng)數(shù)據(jù)庫(kù)中包含的實(shí)例能夠作為將 來(lái)制定決策的基礎(chǔ)時(shí)，分類特別有用，比如用于評(píng)估信用風(fēng)險(xiǎn)、醫(yī)療診斷、科學(xué) 數(shù)據(jù)分析等等。 2 1 分類概念 能夠?qū)W習(xí)如何把一個(gè)對(duì)象劃分到預(yù)定義的類被認(rèn)為是智能的一個(gè)重要特征， 在人工智能、機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)等方面都有廣泛的應(yīng)用，這類任務(wù)被稱作分類。 分類是一種有指導(dǎo)的學(xué)習(xí)，即學(xué)習(xí)過(guò)程是在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的 “指導(dǎo)”下進(jìn)行的。 分類問(wèn)題可以描述為：數(shù)據(jù)是一張標(biāo)準(zhǔn)關(guān)系表，它包含個(gè)記錄，這些記 錄通常稱作元組( m p l e s ) 、實(shí)例( i n s t a l l c e ) 或樣本( e x 鋤p l e ) 。每一個(gè)實(shí)例用固定數(shù)目 的度量標(biāo)準(zhǔn)描述，這種度量標(biāo)準(zhǔn)稱作屬性( a t t r i b u t e ) 。每一個(gè)屬性都有一個(gè)合法的 取值范圍，稱作該屬性的域( d o m a i n ) 。如果屬性域是實(shí)數(shù)域，那么則稱該屬性為 數(shù)值屬性( n u m c r i c a la 州b 1 1 t e ) 或連續(xù)屬性( c o n t i n u o l l sa t 城b u t e ) 。如果屬性域是有限 的，那么則稱該屬性為分類屬性( c a t e g o r i c a la t t r i b u t e ) 或離散屬性( d i s c r e t e a t 塒b u t e ) 。這些屬性中有一個(gè)區(qū)別于其他的稱作類標(biāo)號(hào)( d a s sl a b e l ) ，類標(biāo)號(hào)指示 元組所屬的類。除了類標(biāo)號(hào)之外的其他屬性是預(yù)測(cè)未知樣本類型的依據(jù)，因此也 稱作預(yù)測(cè)屬性( p r e d i c t o ra t 讎b u t e s ) 。 在分類研究中，數(shù)據(jù)集通常被分成訓(xùn)練集和測(cè)試集。訓(xùn)練集用來(lái)構(gòu)造分類器， 測(cè)試集用來(lái)評(píng)估分類器的預(yù)測(cè)準(zhǔn)確度。因?yàn)閷W(xué)習(xí)算法可能對(duì)數(shù)據(jù)的過(guò)分特化，所 以使用訓(xùn)練數(shù)據(jù)構(gòu)造分類模型，然后用同樣的數(shù)據(jù)集評(píng)估分類模型可能導(dǎo)致過(guò)于 樂(lè)觀的估計(jì)。因此，通常采用測(cè)試集來(lái)評(píng)估分類模型。在分類研究中，通常采用 u c i 機(jī)器學(xué)習(xí)庫(kù)例( u c im a c h i n el e a r i l i n gr 印o s i t o 啪中的數(shù)據(jù)集評(píng)估不同的分類 模型。這些數(shù)據(jù)集來(lái)自廣泛的應(yīng)用領(lǐng)域，并且不同數(shù)據(jù)集的規(guī)模、目標(biāo)類的個(gè)數(shù) 和屬性個(gè)數(shù)變化很大，能夠比較全面的反映算法的分類性能。 分類過(guò)程可以描述為如下兩個(gè)步驟： 第一步是建立一個(gè)模型，描述預(yù)定的數(shù)據(jù)類或概念集。訓(xùn)練階段的目的是建 第二章分類 立分類器，即從訓(xùn)練數(shù)據(jù)集中獲取可以進(jìn)一步指導(dǎo)未知數(shù)據(jù)分類的專家知識(shí)。不 同的分類模型可能用不同的形式描述用于指導(dǎo)分類的知識(shí)，如分類規(guī)則、決策樹 或數(shù)學(xué)公式等。這些分類模型以不同的形式描述了某個(gè)類區(qū)別其他類的特征概念 集。從另一個(gè)角度來(lái)看，也可以認(rèn)為分類模型是以某種特定的形式描述了訓(xùn)練集 的數(shù)據(jù)分布特征。如果訓(xùn)練集能夠代表整體數(shù)據(jù)分布特征，那么由訓(xùn)練集獲得的 特征概念集就可以用來(lái)指導(dǎo)對(duì)未知數(shù)據(jù)的預(yù)測(cè)。 第二步，使用模型進(jìn)行分類。在使用分類模型對(duì)未知類標(biāo)號(hào)的實(shí)例或?qū)ο蠓?類之前，首先要使用測(cè)試集評(píng)估分類模型的分類準(zhǔn)確率。如果分類準(zhǔn)確率是可以 接受的，那么我們才可以真正把該模型用于指導(dǎo)未知元組的分類。有多種技術(shù)用 來(lái)評(píng)估分類模型的準(zhǔn)確性，關(guān)于模型的評(píng)估的問(wèn)題，本文在本章第3 節(jié)做進(jìn)一步 論述。 2 2 基本的分類技術(shù) 分類技術(shù)在不同領(lǐng)域有廣泛應(yīng)用，因此，統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等領(lǐng) 域的研究者提出了很多的分類方法。這些算法來(lái)自不同的領(lǐng)域、工作原理差別很 大，但是都在相應(yīng)的領(lǐng)域取得了成功。本節(jié)將簡(jiǎn)要介紹分類的基本技術(shù)?，F(xiàn)有的 分類技術(shù)主要有：基于決策樹的分類、貝葉斯分類、基于案例的推理、基于源自 關(guān)聯(lián)規(guī)則挖掘概念分類、神經(jīng)網(wǎng)絡(luò)、遺傳算法、模糊集和粗糙集方法等。 2 2 1 基于決策樹的分類 決策樹學(xué)習(xí)【2 7 0 8 1 是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它著眼于從組無(wú)次序、 無(wú)規(guī)則的實(shí)例中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方 式，首先選擇訓(xùn)練樣本的一個(gè)子集形成一顆決策樹，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬 性值的比較并根據(jù)不同的屬性值判斷該結(jié)點(diǎn)向下的分支，在決策樹的葉結(jié)點(diǎn)得到 結(jié)論。所以從根到葉子節(jié)點(diǎn)的一條路徑對(duì)應(yīng)著一條合取規(guī)則，整個(gè)樹就對(duì)應(yīng)著一 組析取表達(dá)式規(guī)則?；跊Q策樹學(xué)習(xí)算法的一個(gè)最大優(yōu)點(diǎn)是它在學(xué)習(xí)過(guò)程中不需 要使用者了解很多背景知識(shí)( 同時(shí)這也是它的最大缺點(diǎn)) ，只要訓(xùn)練例子能夠用 屬性一結(jié)論式的方式表達(dá)出來(lái)，就能使用該算法來(lái)學(xué)習(xí)?；跊Q策樹的分類方法 是一種監(jiān)督學(xué)習(xí)的方法，樹的數(shù)量決定于分類的精度和樹的大小，決策樹的構(gòu)造 過(guò)程也就是假設(shè)特化的過(guò)程?；跊Q策樹的分類算法很多，比較有影響的有i d 3 、 第二章分類 c 4 5 、c a r t 、s u o 、s p r t 、b o a t 和c ir 0 1 j d s 等算法和r 血l f 嘴t 框架。 i d 3 算法【2 冊(cè)是國(guó)際上最早、最有影響力的決策樹算法。該算法是j r d s s q 1 1 瑚蛆在1 9 8 6 年提出的。d 3 算法是基于信息熵、使用增量式學(xué)習(xí)技術(shù)的決策 樹分類算法，根據(jù)屬性集的取值選擇實(shí)例的類別。它采用自頂向下不可返回的策 略，搜索出全部空間的一部分，它確保決策樹的建立最簡(jiǎn)單、每次所做的測(cè)試數(shù) 據(jù)最少。l d 3 算法構(gòu)造的決策樹平均深度較小，分類速度較快。 但是i d 3 算法本身也存在些不足，如：m 3 算法偏向于選擇屬性值較多的 屬性，學(xué)習(xí)簡(jiǎn)單的邏輯表達(dá)能力較差等。由于i d 3 算法的廣泛應(yīng)用，研究人員圍 繞該算法做了大量富有成效的研究工作。1 9 9 6 年，j r o s sq u i n l a l l 對(duì)i d 3 算法進(jìn) 行了補(bǔ)充和改進(jìn)，提出了c 4 5 算法1 3 0 l 。c 4 5 算法不但解決了連續(xù)值數(shù)據(jù)的學(xué)習(xí) 問(wèn)題，而且能夠?qū)Q策樹轉(zhuǎn)化為等價(jià)的規(guī)則表示。但是c 4 5 算法同樣存在一些 不足之處，如：c 4 5 算法采用分而治之的策略所得到?jīng)Q策樹不一定是最優(yōu)的， 決策樹的結(jié)構(gòu)調(diào)整、性能改善較困難等。 大部分決策樹都限定訓(xùn)練樣本駐留內(nèi)存，這一限制制約了算法的可伸縮性。 在數(shù)據(jù)挖掘應(yīng)用中，包含數(shù)以百萬(wàn)記的訓(xùn)練樣本的非常大的訓(xùn)練集是很普通的。 因此，在這些算法用于非常大的、現(xiàn)實(shí)世界中的數(shù)據(jù)庫(kù)的挖掘時(shí)，算法的有效性 和可伸縮性成為值得關(guān)注的問(wèn)題。 對(duì)于大型數(shù)據(jù)庫(kù)構(gòu)造決策樹，研究者提出不同的解決方案。如：對(duì)連續(xù)屬性 離散化，在每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)選樣。但是這種方法仍然假定處理后的訓(xùn)練集可以放 在主存中。另外一種解決方案是：將樣本劃分成多個(gè)子集，使得每個(gè)子集可以放 在內(nèi)存中；然后，由每個(gè)子集構(gòu)造一棵決策樹；最后，輸出的分類法將出每個(gè)子 集得到的分類法組合在一起。盡管浚方法可以用于大數(shù)據(jù)集的分類，但是可能會(huì) 降低分類準(zhǔn)確性。 針對(duì)算法的可伸縮性，最近提出了適用于大的訓(xùn)練數(shù)據(jù)集進(jìn)行決策樹歸納的 算法。主要包括s l i o 、s p r i n t 和r a i l l f o r e s t 判定樹歸納框架。這些方法著重解 決當(dāng)訓(xùn)練數(shù)據(jù)量無(wú)法全部放入內(nèi)存時(shí)，如何高速準(zhǔn)確地生成決策樹。s l i o 和 s p r 礬t 都是用了預(yù)排序技術(shù)，同時(shí)定義了新的數(shù)據(jù)結(jié)構(gòu)，以利于決策樹的構(gòu)造。 s l i q 算法 3 1 】首先采用預(yù)排序技術(shù)，對(duì)非常大而不能放入內(nèi)存的駐留磁盤的 數(shù)據(jù)集進(jìn)行排序。同時(shí)s l i q 使用了若干個(gè)駐留磁盤的屬性表和單一的駐留內(nèi)存 第二章分類 的類表。類表的第n 項(xiàng)存放第n 條記錄的類標(biāo)號(hào)，所以類表的大小隨訓(xùn)練集中元 組數(shù)目成比例增長(zhǎng)。每個(gè)屬性則對(duì)應(yīng)一個(gè)屬性表，由記錄標(biāo)志號(hào)建立索引。每個(gè) 元組由一個(gè)從每個(gè)屬性表的一個(gè)表目到類表的一個(gè)表目的鏈接表示，而類表的每 一個(gè)表目都鏈接到它在決策樹中對(duì)應(yīng)的葉子節(jié)點(diǎn)。類表在決策樹構(gòu)造和剪枝過(guò)程 中需要頻繁訪問(wèn)，因此應(yīng)該駐留內(nèi)存。當(dāng)類表不能放在內(nèi)存時(shí)，算法性能會(huì)急劇 下降。 s p r i n t 算法舊也需要使用預(yù)排序技術(shù)，它利用屬性表存放類和記錄標(biāo)志符 信息。當(dāng)節(jié)點(diǎn)分裂時(shí)，屬性表被相應(yīng)劃分。s p r d 盯消除了所有內(nèi)存限制，但仍 然需要使用正比于訓(xùn)練集的散列樹。隨著訓(xùn)練集的增長(zhǎng)，這可能使代價(jià)變得昂貴。 s p r i n t 的設(shè)計(jì)易于并行化，這進(jìn)一步增強(qiáng)了算法的可伸縮性。 r 啦! f o r e s t 框架【3 ，l 是用于可伸縮的決策樹歸納的框架，它采用a v c 集 ( a t m b u t e 一u e c l 船sl a b d ，屬性一值和類標(biāo)號(hào)) 指示數(shù)據(jù)每個(gè)屬性類分布，能 夠使生成的決策樹的質(zhì)量?jī)H取決于具體的決策樹算法，而與本框架無(wú)關(guān)。它旨在 提高決策樹算法的伸縮性，陔框架可運(yùn)用于大多數(shù)決策樹算法( 例如s p 硎【n t 和 s l i q ) ，使算法獲得的結(jié)果與全部的數(shù)據(jù)放置于內(nèi)存所得到的結(jié)果一致，但是在 運(yùn)行時(shí)可以使用較少的內(nèi)存。 決策樹算法因?yàn)榫哂薪Y(jié)果容易被人理解、分類模式易于轉(zhuǎn)化成分類規(guī)則、輸 入?yún)?shù)少、能處理多種類型數(shù)據(jù)( 連續(xù)值和離散值) 、能夠設(shè)計(jì)出具有良好伸縮 性的算法等優(yōu)點(diǎn)，因此在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域具有廣泛的應(yīng)用。 決策樹歸納算法也可能面臨一些問(wèn)題，主要是碎片、重復(fù)和復(fù)制：碎片是指 通過(guò)重復(fù)劃分?jǐn)?shù)據(jù)集可能導(dǎo)致一些葉子包含的樣本數(shù)目太少而失去統(tǒng)計(jì)意義。這 些葉子對(duì)應(yīng)的是問(wèn)題空間中不具有一般意義的規(guī)則或是噪音數(shù)據(jù)引起的過(guò)適應(yīng)。 重復(fù)是一個(gè)屬性沿樹的一個(gè)給定分枝重復(fù)測(cè)試。復(fù)制是復(fù)制了決策樹中已經(jīng)存在 的子樹。這三個(gè)問(wèn)題不但使決策樹變得更龐大，同時(shí)影響決策樹的分類準(zhǔn)確度。 因此，為了防止過(guò)分適應(yīng)訓(xùn)練數(shù)據(jù)集、構(gòu)造具有更高分類準(zhǔn)確度的決策樹，需要 采用一些應(yīng)對(duì)策略，如剪枝、屬性構(gòu)造等。 2 2 2 貝葉斯方法 對(duì)于分類問(wèn)題，有些情況下，輸入特征向量唯一對(duì)應(yīng)著一個(gè)類別，這種問(wèn)題 稱為確定性的分類問(wèn)題；而更多的情況是，來(lái)自于不同類別的樣本在外觀特征是 一8 一 第一二章分類 具有極大的相似性的，我們必須為它選擇一個(gè)類別。貝葉斯方法能夠很好地處理 這類不確定性問(wèn)題，其特點(diǎn)是以概率表示所有形式的不確定性，學(xué)習(xí)或其他形式 的推理都用概率規(guī)則來(lái)實(shí)現(xiàn)。貝葉斯學(xué)習(xí)的結(jié)果表示為隨機(jī)變量的概率分布，其 解釋為我們對(duì)不同可能性的信任程度。 基于貝葉斯的分類過(guò)程可以這樣描述：假定有足個(gè)類c ，白c k ，給定未 知數(shù)據(jù)樣本z 可以用一個(gè)維向量描述為j = 缸l ，娩靠 ，分類器將預(yù)測(cè)未知 樣本工屬于在各屬性取值為工條件下的后驗(yàn)概率最高的類。即選擇能夠使p ( c f l 最大化的c ；作為未知樣本所屬的類 p ( a z ) p ( g i j ) ，1 ，k ，f 依據(jù)貝葉斯定理尸( gl x ) = ! 竺掣 其中，p ( 西對(duì)于所有的類都是常數(shù)，只需p 傭c i ) p ( c f ) 最大，而如果類的先 驗(yàn)概率未知，通常假定這些類是等概率的，即p 刊= 尸r j 列= = j d r c p 。類的先驗(yàn) 概率也可阻用尸( c p = 側(cè)“習(xí)，其中| s i | 是訓(xùn)練集中c f 類的樣本數(shù)，i s i 是訓(xùn)練集的樣本 總數(shù)。因此，如何獲得p f 硼c 砂成為基于貝葉斯的分類算法的關(guān)鍵問(wèn)題。 樸素貝葉斯分類算法( n a 如eb a y e s i a n ，n b ) 做了一個(gè)簡(jiǎn)單的假定：對(duì)于給定 的c f 類，所有屬性是相互獨(dú)立的。在屬性值相互條件獨(dú)立的前提下，尸( 圈c f ) 的 計(jì)算可以簡(jiǎn)化為：p ( 工jc f ) = 兀p ( 工，lc j ) 。概率坼“q ，p 阢i q 一，p 阢i 咧 j = l 可以通過(guò)訓(xùn)練集估算。 樸素貝葉斯分類法的假設(shè)是為了簡(jiǎn)化計(jì)算，但是這種假設(shè)在現(xiàn)實(shí)世界中不是 總成立的，因?yàn)楦鱾€(gè)屬性之間總存在著或多或少地相互依賴。貝葉斯信念網(wǎng)絡(luò) ( b a y e s i a l lb e l i e f n e 押o r k s ) 說(shuō)明聯(lián)合條件概率分布，它允許在變量的子集間定義 類條件獨(dú)立性。還能夠表示屬性子集問(wèn)的依賴。它提供一種因果關(guān)系的圖形，可 以在其上進(jìn)行學(xué)習(xí)。 貝葉斯網(wǎng)絡(luò)的知識(shí)表示為判別函數(shù)，與數(shù)據(jù)挖掘中的其他知識(shí)表示的方法如 規(guī)則表示、決策樹、人工神經(jīng)網(wǎng)絡(luò)等相比，貝葉斯網(wǎng)絡(luò)在知識(shí)表示方面具有以下 優(yōu)點(diǎn)：貝葉斯網(wǎng)絡(luò)能夠很方便地處理不完全數(shù)據(jù)。貝葉斯網(wǎng)絡(luò)能夠?qū)W習(xí)變量間的 因果關(guān)系。貝葉斯方法與其他模型相結(jié)合，通?？梢杂行У谋苊饬藬?shù)據(jù)的過(guò)分?jǐn)M 第二章分類 a 2 2 3 近鄰學(xué)習(xí)方法( a r e s t i g h b o r ) 最近鄰分類是基于類比的學(xué)習(xí)。訓(xùn)練樣本用n 維數(shù)值屬性描述，每個(gè)樣本代 表n 維空間的一個(gè)點(diǎn)。這樣，所有的訓(xùn)練樣本都存放在n 維模式空間中。給定一 個(gè)未知樣本，k 近鄰分類法搜索模式空間，找出最接近未知樣本的k 個(gè)訓(xùn)練樣 本。這k 個(gè)訓(xùn)練樣本是未知樣本的k 個(gè)“近鄰”?！芭R近性”有不同的定義方式， 最簡(jiǎn)單的就是歐幾罩德的距離定義，即根據(jù)兩個(gè)點(diǎn)之間的距離來(lái)確定二者的臨近 性。未知樣本被分配到k 個(gè)最臨近者中最公共的類，如果這些點(diǎn)屬于不同的類， 則可以通過(guò)某種判斷策略( 如多數(shù)表決方式) 來(lái)確定該未知樣本的最終歸屬。 近鄰分類是基于要求的或懶散的學(xué)習(xí)法，即它存放所有的訓(xùn)練樣本，并且直 到新的( 未標(biāo)記的) 樣本需要分類時(shí)才建立分類。而急切學(xué)習(xí)法( 如決策樹歸納 或后向傳播) 則在接受新的樣本之前構(gòu)造一個(gè)一般模型。懶散學(xué)習(xí)法的所有計(jì)算 都推遲到分類預(yù)測(cè)時(shí)進(jìn)行，因此如果訓(xùn)練集很大，可能的臨近者數(shù)量也很大，懶 散的學(xué)習(xí)法可能導(dǎo)致很高的計(jì)算開銷，使分類過(guò)程變得緩慢。 2 2 4 神經(jīng)網(wǎng)絡(luò)分類 神經(jīng)網(wǎng)絡(luò)f 州最早是出心理學(xué)家和神經(jīng)生物學(xué)家提出的，旨在尋求開發(fā)和測(cè) 試神經(jīng)的計(jì)算模擬。神經(jīng)網(wǎng)絡(luò)是一組相互連接的輸入輸出單元，每個(gè)連接都與 一個(gè)權(quán)值相連。在學(xué)習(xí)階段，通過(guò)調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使網(wǎng)絡(luò)能夠正確預(yù)測(cè)輸入 樣本的類標(biāo)號(hào)來(lái)學(xué)習(xí)。 神經(jīng)網(wǎng)絡(luò)需要很長(zhǎng)的訓(xùn)練時(shí)問(wèn)，而且需要大量的參數(shù)，這些參數(shù)主要靠經(jīng)驗(yàn) 確定，如網(wǎng)絡(luò)拓?fù)浠蚪Y(jié)構(gòu)。人們很難解釋蘊(yùn)涵在學(xué)習(xí)權(quán)之中的符號(hào)的含義，因此 神經(jīng)網(wǎng)絡(luò)很難被理解和解釋，神經(jīng)網(wǎng)絡(luò)的行為也像一個(gè)“黑盒子”。 神經(jīng)網(wǎng)絡(luò)也有一些其他算法所不具備的優(yōu)點(diǎn)，如對(duì)噪聲數(shù)據(jù)的高承受能力， 以及它對(duì)未經(jīng)訓(xùn)練的數(shù)據(jù)分類模式的優(yōu)秀表現(xiàn)。由于最近提出一些從訓(xùn)練過(guò)的神 經(jīng)網(wǎng)絡(luò)提取規(guī)則的算法。這些因素推動(dòng)了神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘分類方面的應(yīng)用。 2 2 5 粗糙集方法 現(xiàn)實(shí)生活中存在著許多不能簡(jiǎn)單地用真、假值來(lái)表示的含糊現(xiàn)象，如何表示 1 0 一 第二章分類 和處理這些現(xiàn)象就成為一個(gè)研究領(lǐng)域。 1 9 6 5 年z a d c i l 提出了模糊集，但遺憾的是模糊集是不可計(jì)算的，即沒有給 出數(shù)學(xué)公式描述這一含糊概念。直至2 0 世紀(jì)8 0 年代，波蘭的p a _ w l a k 提出了粗 糙集( r o u 曲s e t ) 。粗糙集理論可以用于分類，發(fā)現(xiàn)不準(zhǔn)確數(shù)據(jù)或者噪聲數(shù)據(jù)內(nèi) 在的結(jié)構(gòu)聯(lián)系，該理論基于給定訓(xùn)練數(shù)據(jù)內(nèi)部的等價(jià)類的建立。形成等價(jià)類的所 有數(shù)據(jù)樣本是不加區(qū)分的，即對(duì)于描述數(shù)據(jù)的屬性，這些樣本是等價(jià)的。給定現(xiàn) 實(shí)世界數(shù)據(jù)，通常有些類不能被可用的屬性區(qū)分。粗糙集可以用來(lái)近似或“粗略 地”定義這種類。給定類c 的粗糙集定義有兩個(gè)集合近似：c 的下近似和c 的 上近似。c 的下近似有一些這樣的樣本組成，根據(jù)關(guān)于屬性的知識(shí)，它們毫無(wú)疑 問(wèn)屬于c 。c 的上近似由所有這樣的樣本組成，根據(jù)關(guān)于屬性的知識(shí)，它們不可 能被認(rèn)為不屬于c 。 粗糙集方法的知識(shí)表示是產(chǎn)生式規(guī)則。例如，給定一個(gè)顧客信用信息的數(shù)據(jù) 庫(kù)，可以學(xué)習(xí)分類規(guī)則，根據(jù)他們的信譽(yù)度優(yōu)良或相當(dāng)好來(lái)識(shí)別顧客。這樣的規(guī) 則可以用來(lái)為以后的數(shù)據(jù)樣本分類，也能對(duì)數(shù)據(jù)庫(kù)的內(nèi)容提供更好的理解。 粗糙集理論的主要優(yōu)勢(shì)之一是它不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)的信 息，比如統(tǒng)計(jì)學(xué)中的概率分布、d e m p s t e 卜s h a f e r 理論中的基本概率賦值，或模糊 集理論中的隸屬度或概率值。當(dāng)然了，該理論也不是萬(wàn)能的，對(duì)建模而言，盡管 粗糙集論對(duì)知識(shí)不完全的處理是有效的，但是，由于這個(gè)理論沒有包含處理不精 確或不確定原始數(shù)據(jù)的機(jī)制。因此，單純地使用這個(gè)理論不一定能有效地描述不 精確或不準(zhǔn)確的實(shí)際問(wèn)題，這就意味著需要其他方法的補(bǔ)充( 如與證據(jù)理論和模 糊集理論的結(jié)合) 。 2 2 6 源于關(guān)聯(lián)規(guī)則的分類 關(guān)聯(lián)規(guī)則【”，3 6 1 挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要的、高度活躍的領(lǐng)域。最近， 數(shù)據(jù)挖掘技術(shù)業(yè)已將關(guān)聯(lián)規(guī)則挖掘用于分類問(wèn)題，我們將依次討論c b a 、c m a r 和c p a r 算法。 基于關(guān)聯(lián)規(guī)則的分類( c l a s s i f i c a t i o nb a s e do na s s o c i a t i o n ，c b a ) 算法采用和 a d r i o r i s 算法類似的候選項(xiàng)產(chǎn)生測(cè)試的方法挖掘所有滿足最小支持度和最小置信 度閩值的規(guī)則，然后使用數(shù)據(jù)覆蓋的概念來(lái)選擇一個(gè)規(guī)則集來(lái)建立分類器。c b a 使用形如j ，_ y 的關(guān)聯(lián)規(guī)則，其中z 是一個(gè)屬性值的集合而y 是類標(biāo)號(hào)這樣的 1 1 第二章分類 規(guī)則被稱作類規(guī)則( c l a 船a s c i 撕o nr u l 錙，c a r s ) 。由于產(chǎn)生的c a j 塔總數(shù)很大， 所以c b a 采用啟發(fā)式的剪枝策略，使用一個(gè)可以覆蓋所有元組的最有效的規(guī)則 集來(lái)構(gòu)造分類器。在預(yù)測(cè)未知元組的時(shí)，c b a 在規(guī)則集中從最有效規(guī)則開始的 按有效性順序搜索分類規(guī)則，并用第一個(gè)匹配的規(guī)則預(yù)測(cè)未知元組的類標(biāo)號(hào)。 c b a 在u c i 機(jī)器學(xué)習(xí)庫(kù)上的平均分類準(zhǔn)確性比c 4 5 高，并且分類器的構(gòu)造具有 線性可伸縮性。 c m a r 算法( c l a s s 語(yǔ)c a t i o nb a s e do nm 1 l l t i p l ea s s o c i a t i o nr u l e s ，c m a r ) 擴(kuò) 展了f p 骶e ，在每個(gè)節(jié)點(diǎn)上添加了類信息，并使用f p g r o w l 算法產(chǎn)生完整的 關(guān)聯(lián)規(guī)則集。并把這些規(guī)則存儲(chǔ)在一個(gè)稱作壓縮規(guī)則樹( c o m p r e s s e dr u l e 仃， c r 仃e e l 的數(shù)據(jù)結(jié)構(gòu)上，剪除置信度低的規(guī)則并依據(jù)關(guān)聯(lián)分析和數(shù)據(jù)覆蓋做進(jìn)一 步剪枝。預(yù)測(cè)未知元組的類標(biāo)號(hào)時(shí)，和c b a 僅使用一條規(guī)則做判斷的方法不同， c m a r 使用所有匹配的規(guī)則共同預(yù)測(cè)的預(yù)測(cè)未知元組所屬的類。為了解決不同 規(guī)則預(yù)測(cè)的類標(biāo)號(hào)不同而造成的沖突，c m a r 為每一個(gè)關(guān)聯(lián)規(guī)則給定一個(gè)權(quán)值。 u c i 機(jī)器學(xué)習(xí)庫(kù)測(cè)試表明，c m a r 算法的分類準(zhǔn)確度優(yōu)于c 4 5 和c b a ，并且 c m a r 比c b a 使用更少的內(nèi)存具有更好的可伸縮性。 c p a r 算、法f 3 8 1 是基于預(yù)測(cè)規(guī)則的分類算法( c l a s s m c a t i o nb 船e do np r e d i c t i v e a s s o c i a t i o nr u l e s ，c p a r ) ，它使用預(yù)測(cè)規(guī)則挖掘算法( p r e d i c t i v em l em i m n g ，p r m ) 產(chǎn)生預(yù)測(cè)規(guī)則。p r m 算法繼承了f o l l 算法的基本思想，c p a r 采用貪婪算法 從訓(xùn)練集直接產(chǎn)生預(yù)測(cè)規(guī)則，而不象傳統(tǒng)的基于關(guān)聯(lián)規(guī)則的分類算法那樣需要產(chǎn) 生大量候選規(guī)則。但是和傳統(tǒng)的基于規(guī)則的分類算法相比，c p a r 產(chǎn)生并測(cè)試更 多的規(guī)則。這是因?yàn)閜 r m 和f o l l 不同，它在發(fā)現(xiàn)一個(gè)實(shí)例被規(guī)則覆蓋之后并 不刪除它，而是降低它的權(quán)重。因此，p r m 算法產(chǎn)生更多規(guī)則并且每個(gè)實(shí)例通 常被多個(gè)規(guī)則覆蓋。并且不是僅僅選用最好的一條規(guī)則而是選擇所有接近最好的 規(guī)則的策略可以避免丟失重要的規(guī)則。c 隊(duì)r 在預(yù)測(cè)過(guò)程中用預(yù)期準(zhǔn)確度來(lái)度量 每一個(gè)規(guī)則的貢獻(xiàn)，使用最好的五個(gè)規(guī)則共同決定未知樣本的所屬類別。測(cè)試 結(jié)果顯示，c 隊(duì)r 取得了更好的分類精度和速度。 2 2 7 基于e p 的分類算法 1 9 9 9 年，d o n g 和l i 提出了一種新的知識(shí)模式，即顯露模式【3 9 1 4 0 】( e m e r