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

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