（計算機軟件與理論專業(yè)論文）數(shù)據挖掘中基于貝葉斯技術的分類問題的研究.pdf

臺肥工業(yè)大學碩士論文摘要 摘要 基于貝葉斯技術的分類是當前數(shù)據挖掘領域的一個研究熱點。本文從兩個 方面對貝葉斯分類模型進行了深入的研究：半樸素貝葉斯分類與增量貝葉斯分 類。 半樸素貝葉斯分類模型對樸素貝葉斯分類模型的結構進行了擴展，其目的 是為了突破樸素貝葉斯分類模型特征屬性間獨立性假設限制，提高分類性能。 目前半樸素貝葉斯分類模型學習的關鍵是如何有效組合特征屬性。針對已有的 學習算法中存在的效率不高及部分組合意義不大的問題，本文提出了條件互信 息度量半樸素貝葉斯分類學習算法( c m i b s n b c ) 。運用實驗數(shù)據進行了比較實 驗，實驗取得了大量的數(shù)據。在分析結果的基礎上得出了相應的結論，證明了 模型的有效性。 增量貝葉斯分類模型的關鍵是測試實例的選擇策略，本文研究的重點是如 何充分利用訓練集的先驗知識并使其在學習過程中向前傳遞，提出了新的模型。 新模型的基本思想是基于o 1 分類損失用訓練集對候選測試實例進行檢驗，這 保證了與訓練集相容性較好的測試實例被優(yōu)先選擇。 關鍵字：數(shù)據挖掘、貝葉斯理論、分類規(guī)則、信息熵、屬性組合、主動學 習策略。 臺肥工業(yè)大學碩士論文 a b s n a 吐 a b s t r a c t c l a s s i f y i n gb a s e do nb a y e st e c h n o l o g yh a sg o tm o r ea n dm o r ei n t e r e s t si nt h ef i e l d o fd a t am i n i n g t h i st h e s i sm a k e sas t u d yo ft w ob a y e s i a nc l a s s i f y i n gm o d e l sw h i c ha r e s e m i - n a i v eb a y e s i a nc l a s s i f i e ra n di n c r e a s i n gb a y e s i a nc l a s s i f i e r s e m i - n a i v eb a y e s i a nc l a s s i f i e re x t e n d st h es t r u c t u r eo fn a f v eb a y e s i a nc l a s s i f i e ri n o r d e rt og e tr i do f t h el i m i to f t h e a s s u m p t i o no f i n d e p e n d e n c eb e t w e e n f e a t u r ea t t r i b u t e so f n a i v eb a y e s i a nc l a s s i f i e ra n di m p r o v et h ep e r f o r m a n c eo fc l a s s i f i c a t i o n t h ek e yo fm o d e l l e a r n i n go f s e m i - n a i v eb a y e s i a nc l a s s i f i e ri sh o wt oc o m b i n ef e a t u r ea t t r i b u t e se f f e c t i v e l y s i n c em o s ta l g o r i t h m sa r en o te f f e c t i v ea n dn o tv e r ym e a n i n g f u li nc o m b i n i n g ，t h i st h e s i s p r o p o s e s a n a l g o r i t h mb a s e do n ak i n do fs e m i - n a i v e b a y e s i a nc l a s s i f i e r w h i c hi s m e a s u r e db yc o n d i t i o n a lm u t u a li n f o r m a f i o n ( c m i - b s n b c ) t h i st h e s i s i m p l e m e n t st h e c m i - b s n b cm o d e la n du s e si tt o c a r r y o u ts e r i e so fc o m p a r i n g e x p e r i m e n t s o n e x p e r i m e n t a ld a t a ，w i t hp l e n t yo f r e s u l t a n td a t ab e e no b t a i n e d a f t e r s y n t h e t i c a l l ya n a l y z i n g t h ee x p e r i m e n t a lr e s u l tw em a k es o m ec o n c l u s i o nw h i c hs h o wt h ee f f e c t i v e n e s so ft h e m o d e l t h e k e y o f i n c r e a s i n gb a y e s i a nc l a s s i f i e ri st h ep o l i c yo f h o wt oc h o o s et e s ts a m p l e s t h i st h e s i ss t u d i e sh o w t om a k ef u l lu s eo f p r i o r k n o w l e d g e a n dt r a n s m i ti t t h en e wm o d e l i sp r e s e n t e dw h i c hi sb a s e do nt h e0 - 1l o s so fc l a s s i f i c a t i o na n du s e s t r a i n i n gs e tt ov e i l f y t h et e s ts a m p l e s ，w h i c ha s s u r e st h a tt h et e s ts a m p l em o r e c o m p a t i b l ew i t ht h et r a i n i n gs e tb e e h o s e nf i r s t l y k e yw o r d s ：d a t am i n i n g ，b a y e st h e o r y , c l a s s i f i c a t i o n r u l e ，i n f o r m a t i o n e n t r o p y , a t t r i b u t e c o m b i n i n g ，p o l i c y o fi n i t i a t i v el e a r n i n g i i 獨創(chuàng)性聲明 本人聲明所呈交的學位論文是本人在導師指導f 進行的研究工作及取得的研究成果。據我所 知，除了文中特別加以標注和致澈的地方終，論文中不包含其他人已經發(fā)表或撰寫過的研究成暴， 也不包含為獲得壘膽王些太堂或其他教育機構的學位或證書而使用過的材料。與我一 囝王攆熊嗣恚對本研究聯(lián)髏匏任雋貢獻均已在論文孛侔了明確的說明著表示謝意。 學位論文作 簽字日期：沙丫年b 月2 ，瞄 學位論文版權使用授權書 岑學位論文作者競金了解壘e 墨王業(yè)盔堂有關保留、使用學位論文的規(guī)定，有權保留并向 國家有關部門或機構送交論文的復印件和磁盤，允許論文被奩閱和儲閱。本人授權合肥工業(yè)大學 可以將學位論文的全部或部分內容編入霄燕數(shù)據庫進行檢索，可以漿用影印、縮印或掃描等復制 手段保存、匯編學位論文。 ( 保密的學位論文擻解密后適用本授權書) 學誼論 簽字舀 學位論文作者畢業(yè)后去向 工豫單位： 通訊地址： 導師簽名 z 毫 簽字日期：吁年廠月2 翻 電話： 郵編： 臺肥工業(yè)太學碩士論文 致謝 致謝 論文是在我的導師王浩教授的悉心指導下完成的。感謝王老師三年來對我無微不 至的關懷與孜孜不倦的教誨! 王老師嚴謹?shù)闹螌W態(tài)度、淵博的專業(yè)知識、敏銳的學術 洞察力將對我以后的工作、學習產生深遠的影響。論文的字里行間無不浸透了王老師 的心血。王老師在學術上帶給我啟迪，拓寬了我的思路，引導了我的學術思維。王老 師不僅僅是我三年的指導老師，更是我終生的榜樣。 在此我要真誠地感謝胡學鋼教授! 胡老師在學術上對我們要求嚴格，生活中是我 們的良師益友。 我還要感謝我的師兄姚宏亮博士，另外還有我們k d d 課題組的方寶富師兄、于 磊、王騁、楊靜等。我與他們在學習上互相幫助，生活上情同手足。 最后，感謝所有關心過我，幫助過我的老師和同學。 i i i 作者姜卵生 2 0 0 4 年5 月2 0 日 臺瑟王魏太攀蠖士論文 燕一章縫論 1 。1 數(shù)援攘握技術凝遴 第一章緒論 本研究課題的學術背景是數(shù)據挖掘( d a t am i n i n g ，簡稱為d m ) 。下面簡單 介紹數(shù)據挖掘的產生背景，數(shù)據挖掘基本概念、種類及其研究現(xiàn)狀和發(fā)展趨勢。 1 1 1 鼗辯挖掘產生靜鶩景 我們融經處于數(shù)字時代。半個多世紀蛆米。計算機按術的高速發(fā)展使得信 患技術已經滲透至l 人類活動靜各個領域。數(shù)攥蓐，數(shù)據會簿戳及i n t e n e t 技術懿 應嗣普及使得我稍可以獲得和需袋處理靜數(shù)強規(guī)模越來越巨大i l l 。這艨數(shù)據都 是非常寶貴的資源。 然而，在擁有海爨數(shù)據的同時，我們對數(shù)據知識的提取很大程度上依舊停 整在過去囊讒、筵擎穩(wěn)索靛袁乎羔。羨惑熬裁蔣是數(shù)據，毽是數(shù)據零蹙不等于 信息。激增的數(shù)據矮灝蘊涵著大激的“寶藏”一一事先未知而潛在有髑的信息， 這就導致了所謂的“數(shù)據爆炸但知識貧乏”現(xiàn)象。比如，公司的經理如何從數(shù) 據中發(fā)現(xiàn)顧客的偏好，以便有針對性地開發(fā)耨產品? 醫(yī)學研究人員采用錚么方 法方鏈觚大量病歷串羧窩意菜靜瘸豹病人靜焚弱病癥， 美餒采取蘩藏增船預薅 和治愈機會? 這些問題從傳統(tǒng)的數(shù)據庫中無法找出答案。傳統(tǒng)的數(shù)據陣不適合 于處理分析性問題。 總鮑米說，當餒爨在人類生潘中逐澎扮演越來越重黌熱色顯數(shù)據瓷滾充足 的時候，久稍希望能從繁雜的數(shù)據中挖掘出有瘸的信怠，發(fā)現(xiàn)其中存在的關系 和規(guī)則。這正是數(shù)據挖掘產生并發(fā)展的現(xiàn)實凝礎。 從技術角度來看，數(shù)據挖掘也是很有必要的。僅憑人去理解一個大的數(shù)據 集合是綴豳難載或者滋是攝本不搿施戇。數(shù)攢豹轡翔一黢海囂令瑟瑟：領域魏 數(shù)目和案例數(shù)。人類的分析和抽象能力不適宜于高維和海麓數(shù)據，處理高維數(shù) 據的一個標準方法是把數(shù)據投影到一個維數(shù)較低的子空間，然后在這個簡化的 空間中進行分析和建模。隨著維數(shù)黲不斷增加，降維度可能組合的今數(shù)呈爆炸 性遁長；愛辮，囪低縫孑空閹授影囂，可能怒本來穗對器易識別靜潤趣轉化為 一個難以識別的問題。而某些挖掘算法，能利用反轉技術有目的地增加維數(shù)， 使得模式變得更加簡單。此外，數(shù)據集合的增長速度也迸遠超過了傳統(tǒng)的手工 分撬技術所能處理鮑程疫。如巢我羹想及黠媳禚臻由數(shù)攢疆筷涎信患，螽i | 簧統(tǒng) 酶分析蔽術方法是不可能達到目的的。 臺胖工業(yè)大學碩士論文 第一章緒論 1 1 2 數(shù)攥挖疆豹蒸零概念 一提起數(shù)據撼握太鈣就會懋起基予數(shù)據霹鰓熟談發(fā)瑗( k d d ：k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ) 。k d d 與數(shù)據挖掘是兩個息息相關的概念。由于現(xiàn)在的 工作大部分是基予數(shù)據艨鰓，掰以在實際磷究與應耀過程中提越受多熬跫 k d d 。下筒介紹兩者各自的概念及相互關系，這有利予理解聰續(xù)內容。 人們從不同的層面提出了不同的k d d 定義，一張大家蟄遍接受的定義形 式怒皿】：k d d 是一種從數(shù)據中發(fā)現(xiàn)真實、新穎、有潛在應用價值而鼠最終可以 被理解的模式的j # 平凡過程。它包括從數(shù)據庫中對數(shù)據的選取和采櫸，清理辯 頸楚疆，轉換稻必要靜籬純，孤數(shù)據中挖掘產生模式，直到對得到的模式進行 解釋和評估等過程。這里所說的模式是對一個數(shù)據子集的狹義描述，不同于模 鍪。提取鶼知識表示為穰念、藏翔、蕊镎、模筑、約祭幫可視純等形式。 數(shù)據挖掘【3 3 怒從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用 數(shù)攘中，掇取隱含在其孛熬、太粕事瓷不餐遴熬、毽又是潛瓷育瘸瀚倍惑巔蠲 識的過程。 姨穰念可鞋餐漤，數(shù)爨挖撼鶼范匿魄k d d 廣泛，k d d 怒燕窩數(shù)據癢熬， 而數(shù)據挖掘面向的數(shù)據形式可以有多種多樣，它可以魁數(shù)據庫，還可以是圖像， 聲鬻等媒體數(shù)據。從過糕e 看，數(shù)據挖掘又可以被看修是從數(shù)據庫中提取霉用 信怠這一過程的同義詞，它是k d d 的一個步驟“。 本文的主要內容是數(shù)據挖掘中的分炭問題。本文中的分類是恧向數(shù)據霹救 分炎，掰瀲嚴格魏說它耩予k d d 范酶。有些分類是稀向文本，頁磷等其它媒 體形式的，它們屬于一般意義上的數(shù)據挖掘的范疇。 1 1 3 數(shù)據挖掘的種類 根據被挖掘知識的種類，數(shù)據挖掘可分類以下幾種類型p 【5 】： ( 1 ) 概化規(guī)則( s u m m a r i z a t i o n ) 挖掘窀主要傲的是從用戶指定的數(shù)據庫中挖掭 密( 雙不同的角度袋在不間的層次上的) 平均最小最大慎、總和、百分執(zhí)等等。挖 掘結果用交叉表，特征規(guī)則，統(tǒng)計的曲線圈表等表示。 犯關聯(lián)褒鬃( a s s o c i a t i o n ) 挖掘它要骰豹蕊馭數(shù)攥渾中挖掘密滿足一定祭件 的依賴關系或相關關系。 ( 3 分類( c l a s s i f i c a t i o n ) 援翳挖掘憲鵝恁務楚在已鰨調練數(shù)鋸翡特征幫分類結 果的前提下，為每一個分類找到一個合理的描述或模型。然后再用這些分類的描述威 模燮對類別未知鼴凝夔數(shù)據避露分類。分類是數(shù)據挖握中一令分重要懿漾蘧，誨多 數(shù)據挖掘間題本質上都可以等價或轉化為分裟問題。例如語音識別( s p e e c h i d e n t i f i c a t i o n ) 、圖像識另q ( i m a g ei d e n t i f i c a t i o n ) 等閥題。這些趣題實豁上是為菜一語音 或翻像數(shù)據找到合璦的特征描述。如果把特征集合巍成類別集合，那上述識別問題就 2 臺肥工業(yè)大學碩士論文 第一章緒論 純粹是一分類問題了。本文的研究工作即是圍繞數(shù)據挖掘中的分類問題展開的。 f 4 )聚類( c l u s t e r i n g ) 規(guī)則挖掘它也是一種特殊的分類過程，有時稱之為無監(jiān)督 分類，其宗旨在于按被處理對象的內在特征分類，有相同特征的數(shù)據被歸為一類。它 與分類規(guī)則挖掘的區(qū)別在于分類是基于訓練數(shù)據的，而聚類則直接對數(shù)據進行處理。 ( 5 )預測( p r e d i c t i o n ) 分析 當分類的工作偏向于處理漏掉的數(shù)據、預測數(shù)據的分 類或發(fā)展趨勢時，這時的工作就屬于預測分析的范疇。 f 6 1趨勢( t r e n d ) 分析又稱時間序列分析，它是從一時間段的發(fā)展過程中發(fā)現(xiàn) 數(shù)據的時序特性，以利于決策分析。 f 7 1 偏差( d e v i a t i o n ) 分析又稱比較分析，它將找出一系列判別式的規(guī)則，以區(qū) 別用戶設定的兩個不同類。 i 1 4 數(shù)據挖掘的研究現(xiàn)狀和發(fā)展趨勢 目前，對數(shù)據挖掘的研究主要體現(xiàn)在以下幾個方面：對知識發(fā)現(xiàn)方法的研 究進一步發(fā)展，如近年來注重對b a y e s ( 貝葉斯) 方法以及b o o s t i n g 方法的研究 和提高【6 l ：傳統(tǒng)的統(tǒng)計學回歸法在d m 中的應用【3 】；d m 與數(shù)據庫的結合越來 越緊密。在應用方面：k d d 商業(yè)軟件工具不斷產生和完善，注重建立解決問題 的整體系統(tǒng)，而不是孤立的過程。用戶主要集中在大型銀行、保險公司、電信 公司和銷售業(yè)。國外很多計算機公司非常重視d m 系統(tǒng)的開發(fā)應用，i b m 與微 軟都成立了相應的研究中心進行這方面的工作。許多著名的計算機公司開始嘗 試著k d d 軟件的開發(fā)，比較典型的有s a s 公司的e n t e r p r i s em i n e r ，i b m 公司 的i n t e l l i g e n tm i n e r ，s g i 公司的s e t m i n e r ，s p s s 公司的c l e m e n t i n e 等。w e b 數(shù) 據挖掘產品有n e tp e r c e r p t i o n s ，a c c r u e i n s i g h t 和a c c r u e h i tl i s t ， c o m m e r c e t r e n d s 等。 與國外相比，國內對d m 的研究稍晚，目前進行的大多數(shù)研究項目是由政 府資助進行的，如國家自然科學基金、8 6 3 計劃、“九五”、“十五”計劃等。1 9 9 3 年國家自然科學基金開始對數(shù)據挖掘研究進行支持。國內從事數(shù)據挖掘研究的 人員主要集中在大學，也有部分在研究所或公司。所涉及的研究領域很多，一 般集中于學習算法的研究、數(shù)據挖掘的實際應用以及有關數(shù)據挖掘理論方面的 研究【5j 。如北京系統(tǒng)工程研究所對模糊方法在數(shù)據挖掘中的應用研究、北京大 學對數(shù)據立方體的研究、華中理工大學、復旦大學、浙江大學等對關聯(lián)規(guī)則的 研究等。但是到目前為止，國內還沒有比較成熟的數(shù)據挖掘產品。 數(shù)據挖掘研究的趨勢體現(xiàn)在以下幾個方面： ( 1 )研究專門用于知識發(fā)現(xiàn)的數(shù)據挖掘語言，也許會像s q l 語言一樣走向形式 化和標準化： ( 2 )尋求數(shù)據挖掘中的可視化方法，使得知識發(fā)現(xiàn)的過程能夠被用戶理解，也 便于在知識發(fā)現(xiàn)過程中的人機交互： 叁i ! 三望查璺鱉蘭笙奎 簍二蘭! ! 壘 ( 3 )研究在網絡環(huán)境下的數(shù)據挖掘技術，特別是在i n t e m e t 上建立d m s e r v e r ， 與數(shù)攢艨服務器配合，實現(xiàn)數(shù)據挖掘； ( 4 )黧強對各靜菲結梅純數(shù)爨豹挖撼，懿文本數(shù)據、閣形墨象數(shù)籀、多媒蔣數(shù) 據； ( 5 )與未來的網格技術相結食，研究基于網格的數(shù)據挖掘技術。其研究需要將 隨著瓣摻技零熬發(fā)袋露困臻緊遺。 1 2 數(shù)據挖掘中的分摸問題 分類在數(shù)據挖掇中是一個j 常重要的諜邂，譬蘸在麓監(jiān)上應靂凝多。分類 戇飪務怒撬密一個黌鬟戇概念攢述( 逶霞稱之為分類器) ，它筏表了這類數(shù)搖的 整體信息，即該類的內涵描述，一般用規(guī)則濺決策樹模式表示。該模式能夠把 數(shù)據庫中的元組映射到給定類別集中的某一個。例如：可以建立一個疾病診斷 分類器，耀予攫擺癔疲特廷集鑫凌劌羝該瘸痰蹶對應的痰痣，驤零甓蒺生診瑟e 一個類的內涵撼述分為：特征描述和辨剮性描述1 7 j 。 特攝描述是對類中對象的共同特征的描述：辨別性描述是對兩個或多個類 之間的隧別性描述。特征描述允毒午不同類中嶷意共同特鑷；麗辨別性描述對不 兩類不黢騫掇交豹戇鍰。分類藏楚尋我會逶翁辨筠往疆逡翡過程。 我們可以將分類模型都抽象成用分類函數(shù)的形式來液示。這樣來可以用 如下規(guī)灝化的形式來定義分類： 分類要學習的分炎器裁褶當予一個蘧數(shù)f ( x ) ，它繪麓要分類躲實鑲x 賦予 類標簽c ，c ( j = 1 , 2 ，確，實惻x 由一組屬設值a ，a ：，群。籀述，e 憝類變量集 合取肖限值。本文所涉及的分擻模型就建立在上述定義之上。 1 2 。i 數(shù)援分類的過攆 分炎包括兩個過程；分類模烈的建立以及運用模型讖行新實例分炎： l 。2 1 。l 醣類模型靛建轟 通過分析由屬憾描述的數(shù)據庫元組來構造模型。假定每個元素屬于一個預 定的類，由一個類標撼屬性( c l a s sl a b e l a t t r i b u t e ) 表示。對于分類，數(shù)據元組也 稱為樣本、實惻或對漿。為建立分類模型露被分撰弱數(shù)據元經枚成謝緣數(shù)據集。 誦練數(shù)搭集孛酶單個元組稱為詡練樣本。由予預先知道每個訓練樣本的類別屬 性值，遮個建立模型的學習過程屬于有監(jiān)督的學習，與溉監(jiān)督學習相對。無監(jiān) 督學習的分類就是所謂的聚類。聚類過程中每個訓練樣本的類標簽攀先是未知 豹，要學習懿類羼毽霹愛取篷及可髓取蓬熬個數(shù)事先氌哥縫不知遂，箕瑟懿愛 將“距離”相近或“個性”相似韻元組放在一起，構成一類。 毒 臺肥工業(yè)大學碩士論文 第一章緒論 通常，通過第一步的學習建立的模型用分類規(guī)則、決策樹或數(shù)學公式的形 式表示。例如：給定一個顧客信用信息的數(shù)據庫，通過分類算法學習得出分類 規(guī)則，根據這些規(guī)則，可以判斷顧客信譽的好壞( 如圖1 1 ) 。這樣的規(guī)則就是一 種分類模型。以后就可以利用這個模型為其它顧客的數(shù)據進行分類。 顧客i d年齡收入水平信譽度 n o 1 4 0 由 一般 n 0 4 4 0中 一般 n o 53 1 4 0高優(yōu)良 i f 年齡= 3 1 4 0 a n d 收入水平= ”高。h e n 信 譽度= ”優(yōu)良4 圖i - 1 分類模型的學習，在訓練數(shù)據上用分類算法學習，學習模型用分類規(guī)則的形式表示 1 2 1 2 模型的運用 首先要評估模型的預測準確率。常用的評估手段是保持【8 ( h o l d o u t 、方法。 該方法使用類標簽測試樣本集，這些樣本隨機選取，并與前面使用過的訓練集 相獨立，即測試樣本集完全不同于訓練樣本集。模型在測試樣本集上的準確率 是指正確被模型分類的測試樣本的百分比。對于每個測試樣本，將分類模型學 習得出的預測類與已知的類標簽相比較，如果相同，則表示分類成功。評估過 程中之所以使用與訓練集相獨立的測試集，是為了避免出現(xiàn)過分擬合的現(xiàn)象。 如果通過測試認為模型是可以接受的，那么就可以利用這個模型對類標簽 未知的數(shù)據實例或對象進行分類。例如：在通過分析現(xiàn)有顧客數(shù)據的基礎上學 習得到的分類規(guī)則可以用于預測新的顧客的信譽度f 如圖1 2 1 。 壘i ! 三望鑾黧堡主笙奎 i 堡至! ! 蘭 夕爿 d 收入( n o 2 0 1 ，3 1 4 0 ，高) 度= 優(yōu)信譽度? 毒 往良( 羲溺結果) 睫1 - 2 分類模型的運用 努炎其騫廣泛豹疫瘸，憊努傣譽顴定、激療診瑟、羧麓頸測穩(wěn)選擇麴物等。 1 2 2 數(shù)據的預處理 淹了疆褰分類斡壤磺蠖、騫散靛釋霉 棗縫魏，囂要霹勢黌掰建豹數(shù)攢逡牙必要瓣 預處理。 1 2 2 1 數(shù)據轉換 為了便于分類，需要對原始數(shù)據進行必溪的轉換。例如將連續(xù)濺的數(shù)據離 散化、將屬性值數(shù)字化、對數(shù)據進行概念抽象等。 1 2 2 。2 數(shù)據清理 數(shù)據清理的目的怒清除或減少噪聲數(shù)據以及處理空缺數(shù)據。可采用平滑技術消除 或減少噪聲數(shù)據：對予空缺值，可用該屬性最常出現(xiàn)的值，或根據統(tǒng)計，閣最可能的 篷代替。盡管夫部分鶼分類算法罄湊籠理臻聲數(shù)據稻窒漆餐翁輟裁，毽經 蔓清理戇數(shù) 據將更有助于提高學習的執(zhí)行效率。 1 2 2 3 捆關性分析 數(shù)據中的許多屬性可能與分必任務不相獲。例如：記錄銀行貸款申請日期 的數(shù)據w 能與客戶的信譽度不相關。此外，還可能有些屬性是冗余的，如果包 含這些冗余屬性將減慢或誤導學習步驟。因此，可以進行握關性分掇，刪除學 習過搖巾不穩(wěn)關靜竣冗余豹屬戳。在祝器學習中，這一過程稱之灸褥縫選擇。 在理想情況下，用在相關性分析上的時間，加上從壓縮了的屬性集上學習 的時間，應當少于在原來屬性集上學習所用的時問。這種分析就可以幫助提高 分類糖浚及分類效率。 6 合挺工監(jiān)丈學硬士避文 第一章堵論 1 2 3 分類方法的比較和評估 分類方法可戳較鑲下秀舔猿漣行定較耪浮績 奪 頸測準確度預測準確度魑用得最廣泛的一種比較尺度，特別是對于預測型 分類任務。常見的方法是n 交叉驗證法( c v - n ) 。 奪 計葵復雜度計算復雜度依賴于算法的實現(xiàn)鰓節(jié)與磺傳強境。在d m 中，由 于操作辯蒙是大型數(shù)耀薄，并且在實際應薅中數(shù)據靚模越來越大。因此空瀾和時間的 復雜度問題將是一個非常重要的環(huán)節(jié)。 奪 讎壯性這涉及對于數(shù)據集中噪聲數(shù)據或空缺數(shù)據的處理，它反成程有噪聲 數(shù)據或空缺數(shù)據戇媾撬下模銎是否蠢正確分類熬戇力。 奪w 伸縮性大部分的分類冀法是內存駐甜算法，通常假定數(shù)據量搬小。算法 的可伸縮性意味著對于海量數(shù)據而裔是否具有有數(shù)的構造模型的能力。這點在硬件 性能提高照數(shù)據規(guī)模不斷擴大的情況下顯褥很熏裂。 電 模鶩匏籬活發(fā)筆蜀理矮彀對予疆述墼的分類程務，模整描述越麓潔且越容 易理解就越受歡迎。例如，采用規(guī)則表示的分類囂比較簡明好用，而用神經網絡構造 產生的分類器則比較難以理解。 1 2 4 幾種烹要的分類方法 數(shù)據挖掘領域中分類的方法綴多，本節(jié)奔纓壓靜常霓豹分類愚慧。 1 2 4 1 線性判別函數(shù)分類方法 我 f j 知遭，如果實際闞題數(shù)次策蘧是線瞧的( 妻線躲竣老超平囂的) ，詩箕 秘穆造邋程裁穩(wěn)當箍攀。困魏幫經遇垂贅凌繁瑟不是線程躺，我們也寧可柩毪 錯誤率最小這個最優(yōu)原則，努力構造成線性函數(shù)。 線性分類法1 2 】的目標就是尋找一條直線：g ( x ) = w 1 * x + w o ，這條點線能夠能 夠盡可黢媳姆囂類樣本分瑟。f i s h e r 線性翔剃溪數(shù)是一令經典麴裂裂方法。它 的核心惑想是進行坐標變換，尋找能將樣本盡珂能分開的方向?？紤]搬n 維空 間的樣本投影到一條殿線上，形成一維空間。為了避免投影后不同樣本混雜在 一起不易區(qū)分，可以將直線轉渤，尋找一個方向使樣本的投影盡量分開。也 羲是滋，搜褥類潤差器盡蠆裁大，類肉差異器哥縫棗。 1 ，2 4 2 決策樹分類方法 決策耱5 是較暈應矮子數(shù)據摭攘分類麓熬熬秘方法。在數(shù)據繭較丈辯， 決策樹方法能較快地構造出分類器；其樹型結構可以很方便地轉化為s q l 語言 7 臺0 9 3 - 業(yè)大學碩士論文 第一章緒論 形式，以便用來更有效地訪問數(shù)據庫；且i f - t h e n 規(guī)則可以很容易地從這種結 構轉化中得到，因此這種方法引起了研究者的廣泛興趣。 絕大多數(shù)決策樹分類方法分兩步構造分類器：樹的生成與樹的剪枝。在樹 的生成階段，決策樹是通過反復地分拆訓練集而成。在每一次分拆時，都是利 用某種分拆準則選擇一個屬性。由所選屬性值不同將訓練集分成多個子集。然 后在每個子集上重復同樣的分拆過程，直到每個分拆后的訓練集的子集樣本均 屬于同一類別為止。 對樹的剪枝操作是為了避免出現(xiàn)模型的過分擬合現(xiàn)象。因為如果完全按訓 練集中的樣本生成決策樹，那么當樣本數(shù)據存在噪聲時，就會出現(xiàn)過分擬合的 現(xiàn)象，即把噪聲數(shù)據當作正確的樣本而同樣要求決策樹擬合。這實際會導致決 策樹泛化能力的下降，甚至可能會使生成的決策樹幾乎不可用。因此必須對過 分擬合的分支進行修剪。通常的修剪方法有兩種：一是利用測試集，選擇使得 對測試集分類的誤差最小的子樹；另外的一種方法是借助于m d l ( 最小描述長 度) 原理進行剪枝，它是從概率描述的層面來驗證決策樹的結構。上述兩種方法 的基本思想和目的是一致的，都是為了弱化噪聲數(shù)據的消極影響，提高分類模 型的表達能力。 這種分類方法的關鍵是在樹的生成階段找出合適的分拆準則。目前用得最 多的是q u i n l a n t ”于1 9 8 3 年提出來的i d 3 準則和c a r t ( 分類與回歸樹) 準則。 1 2 4 3 粗糙集分類方法 粗糙集理論1 9 1 是z p a w l a k 于1 9 8 2 年提出來的。這一理論從新的角度對知 識進行了定義，把知識看作是對論域的劃分，認為知識是有粒度的。引入代數(shù) 學中的等價關系來討論知識。該理論近年來主要被用于知識約簡、知識的相關 性分析及分類挖掘。 粗糙集的基本理論是：在數(shù)據庫中將行元素看成對象，列元素當成屬性f 分 為條件屬性與決策屬性) 。等價關系r 定義為不同的對象在某個( 或幾個) 屬性上 取值相同，這些滿足等價關系的對象的集合稱之為等價關系r 的等價類。條件 屬性上的等價類e 與決策屬性上的等價類y 之間的關系分如下三種情形：( 1 ) 下近似：y 包含e ：( 2 ) 上近似：y 與e 的交集非空；( 3 ) 無關：y 與e 的交集為 空。對下近似建立確定性規(guī)則，對上近似建立不確定性規(guī)則( 含可信度1 ，對無 關情況不存在規(guī)則。 1 2 4 4 概念格方法 概念格 1 0 1 是基于二元關系構造的，它描述了對象和特征之間的聯(lián)系，表明 r 概念之間的泛化和例化關系，其相應的哈斯圖實現(xiàn)了對數(shù)據的可視化。作為 臺肥工業(yè)大學碩士論文 第一章緒論 知識的一種表示形式，它有助于挖掘概念間的各種規(guī)則。概念是把所感知的事 物的共同本質特點抽象出來，并加以概括。概念都具有內涵和外延，基于對概 念的這種理解，r w i l l e | 】在1 9 8 2 年首先提出根據二元關系來構造相應概念格 ( 或g a l o i s 格) 的思想，也稱為形式概念分析。其基本內容是以概念格中的每 個節(jié)點表示一個形式概念，其中概念的外延代表相應的一組對象，內涵則表示 這組對象所具有的公共特征( 屬性) 。概念格所對應的哈斯圖形象地揭示了概念 間的泛化和例化關系，反映出一種概念層次結構( c o n c e p t h i e r a r c h y ) ，實現(xiàn)了 對數(shù)據的可視化。上述這些特性使得概念格成為數(shù)據挖掘領域一種頗受青睞的 分類工具。 1 2 4 5 神經網絡分類方法 在數(shù)據挖掘領域，神經網絡方法由于其結構復雜，且學習過程中的非線性 優(yōu)化存在局部極小值等問題而研究得較少。最早正式將神經網絡理論引入分類 領域的是h l u 、r s e t i o n o 及h l i u l l “。神經網絡模仿生物神經元對信息的傳遞 特性構建分層網絡模型?？梢杂脠D形的方式說明其分類思想。圖l 3 是一個三 層神經網絡模型。數(shù)據屬性從其中的輸入層進入網絡，輸出層反應了對其分類 的預測信息。其中的每個點就是神經網絡中的“神經元”。 一輸出層 一隱含層 一- - 輸入層 圖1 - 3 神經網絡分類模型圖示 1 2 4 6 距離函數(shù)法和最近鄰判別法 模式分類中最簡單直觀的方法就是基于距離函數(shù)的分類法。它的核心思想 是使用一類的重心來代表這個類，計算待分類樣本到各類重心的距離，歸入距 離最近的類。在判別分析中常采用馬氏距離，因為馬氏距離既考慮了類的均值， 又包含了類內方差的信息，對訓練樣本中蘊涵的信息利用得比較充分。采用馬 氏距離的基本假設是各類均服從正態(tài)分布。 如果允許類中全部樣本點都可有資格作為類的代表的話，這就是最近鄰法。 最近鄰法不是僅僅比較與各類均值的距離，而是計算和所有樣本點之間的距離， 選擇距離最近的將新實例歸入所屬類。 9 合肥工業(yè)大學碩士論文 第一章緒論 為了克服最近鄰法錯判率較高的缺陷，k 一近鄰法不是僅邈取一個最近鄰進 行分類，而是選取k 個近鄰，然后檢查它們的類別，歸入比黧最大的那一類。 上述分類稱為“聚類”，氌啕檄無藏餐分類。 1 2 4 7 支摻爨量娥分類方法 支持向量機【”1 是上世紀九十年代中期提出寒的一辨分類方法。它脫離傳統(tǒng) 方法中降維的定式，利麗反轉搔術有目的增加問題空悶的維數(shù)，使得分類問題 變樗相對容易。對某些簡單的問題來說，統(tǒng)計的方法可以較精確地將那些需要 考纛靜因素區(qū)分離來，戮便成功逡進 亍學習。褥在實黼應用中，不褥不使霜阮 較笈雜的算法和模型，比如神經網絡等。支持向量機具有兩者的優(yōu)點。它能構 造穗當復雜戇模登，其中毽含大霪懿神經瘸絡，r b f 瓣絡幫稼為將鏞豹多璦式 分類器。但是它的基本思想又是相當簡漿的，闌為它對應于離維空間中的線形 方法。 1 2 。4 。8 基予貝i 咔斯技術的努類方法 貝葉斯學派【1 4 】【l 5 】f 1 6 l f l7 】【】8 】形成于上世紀五六十年代，關于貝葉期技術的研 究久盛不褒。，卡年找，愛時蘩闕終或秘途痰爝予專家系統(tǒng)。九+ 年代鞋采， 貝葉斯學習一直魑機器學習研究的重要方向。旗于這種技術的分類方法是本文 分綏瓣重點內容，它以完善懿煲跨簸理論必基醛，這耱分類方法毒較強靜挨霆 表示、學習和推理能力。本文后面的章節(jié)都圍繞這一主題展開。、 在本節(jié)余紹上述各耪不同分類思想的曩的是巍了蘩助理解數(shù)攢分類懿蠢 涵。這些怒本文所選課躐的研究背景。 1 。3 漂囂來派和本文懿維織 課題采源： 本文受安徽省自然科學基金：基于貝時斯湖技術的智能a g e n t s 自組織和學 習的研究( 0 3 0 4 2 3 0 5 ) 的資助。 本文的組織： 本文系統(tǒng)介紹基于貝葉斯技術的分炎模型，在介紹一般理論的基礎上 乍了 逡一步的搽索，掇出了自己弱覓解。本文豹其體安耨鱺下： 第一章緒言：介紹數(shù)據挖掘的相關概念，并引入本文的研究主蹶：分必。 套終分類懿基本愚想、j 妻程鼓及死耱分類方法。 第二章貝葉斯理論與貝葉斯分類器：比較系統(tǒng)地介紹了貝葉斯熬本理論、 簍n + 顴分類模型躲分類思想鞋及獒它耀美理論，魏售憋凄量毽逡、寵驗分布豹 選取等。 l o 合肥工業(yè)大學碗士論文 第一章緒論 第三章半樸素貝葉新分類橫疆：介紹半樸索貝竹斯分類模型的基本思想。 在此深入研究了借助于條件互信息的半樸素貝葉斯分類算法。 第西章灌量援時薪分類器：介紹了增量委時薪分炎器靜蒺本理論，并就 其中基于樸索貝葉斯分類愿想的增量分類過程進行了深入探討。 第五章蒽續(xù)與震望：震望這一領蠛激居熬發(fā)震趨勢。奔紹濤來袋完成鶼 工作。 舍耗王盈大學頸諗文 譽= 肇愛肆菇瑾論與裁奸辯分類器 第二章貝葉斯理論與貝葉斯分類器 2 。1 炎麓凝努類羲戇一簸囂建 貝葉斯分類器建立在經典的貝葉斯概率理論【1 4 1 與貝葉斯網絡技術的基礎 上，下磷分別予以介紹： 2 1 1 炙種斯定理 定義2 1 ：一個隨機試驗所裔可能的“揍本結果”6 1 梅成的集合稱為該隨 秘蘧驗熬基本空溺，察羆集合q 一 c o 表示，蒸本空閨又褡為棒本空鬻，箕元素 m 稱為樣本點。 例如：對于任意擲一枚硬幣的隨機實驗，其樣本空間q = 正，反) 。 定義2 2 ：繪定了基本空聞q ，一個隧極棗俸就是q 的一個子袋，也裁是 麥菜些蘩本結采組成靜集合。驄稅事釋表示麓筑試驗懿禁締結采。魏輥事釋可 以簡稱為事件。 例如：投擲兩顆骰子，“其和為4 點”這事件可用集合的形式表示為 a = ( i ，3 ) ，( 2 ，2 ) ，( 3 ，1 ) e 定義2 3 ：給定臻本空間q 中釃兩個事件a 與b ，狠艇然a q ，b 仨q ，如 果a n b = 西，則稱a 與b 互為不相容事件。 定義2 4 ：若給定一個事件a ，則“a 不發(fā)生”這個零件稱為a 的對立事 終。矮予集a 奩q 審熬毒 集轟一q a 表示。 從定義中容易看出不相容事件與對立事件兩個概念之間的區(qū)別，這兩個概 念在實際問題中容易混淆。 定義2 + 5 ：在概率論中為了像涯德臺撥寇性質蛇的攀饞壤率存在，著不總 是逐一討論基本空瀚q 中的一切予集。實際上當q 為不對數(shù)無窮集時，事件鼗 也有無窮個。因此，為了研究事件間的各種關系，記全體察件構成的熊類為貿， 要求婀?jié)M足： 1 ) 靛； ( 2 ) 蓿a 貿，則a 虢； ( 3 ) 糟a l ，爿2 ，a “倪，則u 蠢，鼴。 下甏繪出襁率豹定義： 定義2 6 ：如果p 是吼上的一個實值酗數(shù)，即對每個a 孵，脊個實函 1 2 臺肥工業(yè)大學碩士論文 第二章貝葉蜥理論與貝葉斯分類器 數(shù)p ( a ) 與之對應，并且滿足以下三點： 非負- 陵對v a e9 1 ，p ( 4 ) 0 ； 規(guī)范瞧p f 嗷) = l ； 可列可加性 若a 。，a ：，以，是鐘中兩兩不相容的事件，則 7 p ( u 4 ) = p ( 4 )( 2 1 ) f = lf l 黧稱p 是( q ，數(shù)) 上豹一令攢率( 溺浚) ，e ( a ) 稱為事籜a 豹凝率，三元綴 ( q ，锨，p ) 稱為概率空間。 條臀壤率反應了事勢之聞黲擐率關系； 定義2 7 ：設( q ，鞏，p ) 為一概率空間，a ，b 9 1 ，且p ( a ) 0 ，則 即協(xié)a 鬻， ( 2 _ 2 ) 稱為己知a 發(fā)生時b 豹條律概率。 下述三個公式是貝葉斯技術的直接理論依據： 乘法公式： p ( a b ) = p ( a ) p ( bi 一)( 尸( 4 ) o ) ； p ( a b ) = 尹( b ) p ( a | 彩( p ( 器) ； 更一般的情形是：設i i 彳2 ，a 。毗，h 2 ，p ( a i ，爿2 ，a 。) o n p ( 磊，a 2 ，鐫) = p ( a 1 ) p ( a 2la t ) p ( 鐫la i ，a 2 ) p ( a 。l 璉，a ：，。，蠢) 縐，3 ) 全概率公式： 設a 1 ，蠢2 ，t z ，a 。爨，磁兩不楣容，p ( a ；) o ，i = i 2 ，籜，雖u 曼= 鼗，粼對經 何事件b 婀，有： “ 尹( 彩= p ( b i 毒) 琰蔫) ( 2 ，) 貝葉斯公式： 若a ，如，a 。一辨，兩兩不相容，p ( a ，o ，i = 1 , 2 ，n ；則對于任何滿足 尸( 曰) 0 的b ，bg 锨，有： p ( a ，ib ) ：_ p ( b ia j ) p ( a 。) ( 2 5 ) p ( b 4 ，) _ p ( 一；) 貝葉斯分類技術正是旗于上述理論的。在具體討論分類技術之前，先給出 下述豢壽一般牲意義戇結諗： 2 1 2 最大履驗假設姆最大似然假設 在觀察到數(shù)據之前，根據背景知識或經驗確定某個假設空間h 中的假設h 臺肥工業(yè)大學硪士論文第= 章貝葉斯理論與貝葉斯分類器 成立的概率為p ( h ) ，稱之為假設h 的先毅概率。令d 怒一個訓練數(shù)據集合，在 沒露關于哪個假設成立的知識而觀察到的d 的概率，稱為d 的先駿概率，用 p ( 渤表示。在假設h 成立的條 串下，觀察到d 的概率記為p ( d h ) 。在觀察到硼 練數(shù)據據d 的條件下，假設h 成立的概率p ( h l d ) 稱為h 的后駿概率。后驗概率 反浚t 詡練數(shù)蠢辯稷設殘立概率豹影璃，它是依賴于數(shù)據d 靜。已知p ( h ) 、p ( d h ) 和p ( d ) ，貝葉新定理提供了一個計算假設h 的后驗概率的方法，因而成為貝 時欺理論豹基石 6 1 ： 帕i d ) = 掣鏟 通常，學習的任務是：對于繪定的觀察數(shù)據d ，在h 中發(fā)現(xiàn)最可能的假設 h h 。任何這櫸艙具鴦最大可能的假設稱炎最大囂驗假設( m a p , m a x i m u m a p o s t e r i o r i ) ，記為 m ： 盎。= a r g m a x p ( h id ) = a r g m a x p ( d l 矗秘p p ) = a r g m a xp ( di 妒姊)( 2 6 ) 如采h 表示對數(shù)據分類靜假渡i “上述( 2 6 ) 式就是一個原始的分類模型。貝 葉斯分類就是根據上述m a p 假設找出新實例煅可能的分類。所有對貝葉斯分 類囂的拆鴦礪窕王俸幫楚黻魏霰浚為 ；謄撬。 在沒有任何背景知識的情況下，可以假定h 中所有的假設有相闖的先驗。 這瓣2 國式中弱p ( d | 矗) 戴雋繪定h 薅數(shù)攥d 靜叛然。任露鎂p 國l 磊) 最大靜稷 設稱為最大似然( m l m a x i m u ml i k e l i h o o d ) 假設： h m l = a r g m a x p ( d | h ( 2 + 7 ) 在分類過程孛，( 2 7 ) 式往往被用采在窟發(fā)式搜索鰱進行橫整檢測。 2 1 。3 貝葉斯網絡與貝葉斯分類器 貝葉斯網絡【1 9 】1 2 0 】【2 】f 2 2 】【2 3 l 【2 4 1 是用來表示變擻間連按概率的圖形模式，它提 供了一耱是然懿表示困果德怠懿方法，蠲來發(fā)瑗數(shù)據瓣瓣灌褻聯(lián)系。在這個耀 絡中，用節(jié)點表示變量，有向邊表示變擻間的依賴關系。當我們在貝葉斯網絡 中搬其中代表類別變量蛉節(jié)點作為根節(jié)點，其余鼴有變爨邦鋒淹它的予節(jié)點眩， 貝葉斯網絡就變成了分類器。 設某領域中類別變量為c = b ，c 2 ，q ，特鍛變量為衛(wèi)= 墨，x ：，x 。) ，每 個特征的氆域為確，置) ，i 【l m 】，特鑷的取德用小寫字母一( i 【l m 】) 表示。 對每一個實例x = ( 一，x 2 ，x 。) 來說，分類的目的就是通過學習一定的訓練樣本 集d ，來獲褥它的類翔稼簽e 。裰據最大后驗假設原纛，貝時斯分類器采用下 面的表達式珥a k p ( o 。i x ) 來決定它的類別。其中： 臺肥工業(yè)大學碩士論文 第二章貝葉斯理論與貝葉斯分類囂 p 以) 丌p k lc ；硝k ) ) p b l x = l ，f 一 ( 2 + 8 p t x ， 這里療x ， 表示節(jié)點爿，除類別節(jié)點c 之外的所有父節(jié)點。x 。表示實例) ( 第 i 個特征靜款值。掰黻學習員野辯分類摟嫠靜任務是馭調練樣本集d 中學習概 率分布函數(shù)：p ( c ，) ，p ( x ，ic ，：石b ，) ) ，i 【l f 1 ，j 【l m 1 。 學習勢逶矮哭時薪分炎器畦氛括兩令遴程，一是霹予每一特征節(jié)杰我裂狳 根節(jié)點之外的所有父節(jié)點，也就燃學習貝葉斯網絡結構；二是在已知結構的然 醚上獲褥上述參數(shù)戇售計，露聯(lián)淫鮑參數(shù)學習弱懲。麩數(shù)據孛學霹嬲絡戇結構 和分布參數(shù)正在成為貝葉斯學習理論的研究熱點之一。與純貝葉斯網鉻學習：j 過 程不同的是，貝時鞭分類器所采鼷靛往鍍是滿足一定黢鍘條終熬夔健揀結穩(wěn)形 式。這是為了取得算法實踐上的可行性。太部分研究工作都集中在如何使分類 器在限制框架內取得最優(yōu)竣次優(yōu)的分類蛇分類效果。 2 1 4 信息度量理論 美國數(shù)學家s h a n n o n 2 s 于1 9 4 8 年提出了熵的概念。熵是一種信息度量正 具，它反映了不確定性問題款平均不確定程度。其在信息論、人工智黢農數(shù)攢 挖掘領域中有著廣泛的應用。 ，設隨機變量在一個離敝事件集合中進行取傻，稱為離散信源。離散事件集 合a = 口l 一，療。 稱為信源褥號表。如果事件之閶褶互獨立，這樣的離散信源稱 為離散無記憶信源，熵概率空間