（計算機軟件與理論專業(yè)論文）決策樹分類方法及其在鐵路客票營銷分析中的應(yīng)用.pdf

摘要 隨著計算機科學的不斷發(fā)展，大量的原始數(shù)據(jù)被不斷收集并存儲到計算機 中，面數(shù)援處理能力的低下，造成了盡囂信息豐富，知識貧乏的現(xiàn)狀。數(shù)據(jù)挖援 用非平凡的方法從大量數(shù)據(jù)中發(fā)現(xiàn)商用的知識，正是應(yīng)此要求而迅速發(fā)展起 來的一門科學。數(shù)據(jù)挖掘包含眾多任務(wù)，分類是其中一項被廣泛應(yīng)用艙技術(shù)。分 類經(jīng)過長麓的發(fā)最已產(chǎn)生了眾多算法，德其串大部分幫是內(nèi)存駐留算法，通常假 定數(shù)據(jù)量很小。隨著數(shù)據(jù)庫中數(shù)據(jù)量越來越大，建立高效的、適用于大型數(shù)據(jù)庫 系統(tǒng)款分炎葵i 翊置戲失數(shù)據(jù)挖攥懿一個瓣竣毪翔熬。 鐵路中的客票系統(tǒng)蘊含了豐富的數(shù)據(jù)信息，如何從這海掇的信息中挖掘出有 用的知識，是一會亟待研究解決豹閥題。本文將數(shù)據(jù)挖掘中能分類技術(shù)月于鐵鼴 客票營銷分析中的客票分類，形成了一種新的分類方法t td t c ( d e c i s i o nt r e e c l a s s i f i c a t i o nb a s e do l lt r a i nt i c k e t s ) , 該方法針對鐵路客票的實際特點，采用掰 的基于文件分割秘定量規(guī)則茲決燕樹分類冀法s fd t ( d e c i s i o nt r e e c 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 l ls p l i t t i n gf i l e s ) 對客票數(shù)據(jù)讖行分析，以達到依 攢窖票屬黢特征對客蔡發(fā)售及列車運營蓊提避行勢類及頸涎瓣鞫懿。該方法被瑙 予客票分析，得出了能夠指導列車營運的非平凡模式和決策信息，實現(xiàn)了分類技 術(shù)與大規(guī)?？推睌?shù)據(jù)庫系統(tǒng)捆縫合的一次嘗試。 t td t c 方法以鐵路客票數(shù)據(jù)為基礎(chǔ)，以鐵路客票營銷分析為目的，針對鐵 路客票信息數(shù)據(jù)量大、屬性復雜、域值廣等特點，實現(xiàn)了從數(shù)據(jù)預處理、決策樹 塞殘至l 燕潮提取、戔識產(chǎn)生等一系列遙穩(wěn)。該方法憲壘適應(yīng)鐵路窖票營銷分析豹 需要，能夠?qū)推睌?shù)據(jù)進行較為有效的分析和處理，得出指導鐵路營運的決策信 息。 s f _ d t 算法以決策樹分類算法i d 3 的基本思想為基礎(chǔ)，用基于文件分割的方 法代替原有的基于內(nèi)存的算法，提高了算法的可規(guī)模性，可以處理超大覯模的數(shù) 據(jù)。另外，算法還產(chǎn)童了帶有統(tǒng)計信息的定量規(guī)則，能夠清晰地提供主類的分布 情況，為數(shù)據(jù)分析提供了更為詳細的信息。 遙遘稀究，蔽鏹為分類技術(shù)懿發(fā)震翎建了薪熬波蠢鶩豢，為其進一步研究奠 定了應(yīng)用熬礎(chǔ)。另方面，也將數(shù)據(jù)挖掘的技術(shù)用于鐵路客漿營銷分析，為鐵路 客運豹臺璦安接及緞級管理提供了豐富豹決策信惠。 關(guān)鍵字：數(shù)據(jù)挖掘，分類，決策樹，客票營銷分析，定量規(guī)則，客運 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 e ，m o r ea n dm o r eo r i g i n a ld a t ai s c o l l e e t e da n ds t o r e di nc o m p u t e r s 。t 如p o o r a b m t yo f m a n a g i n g d a t am a k e sd a t ar i c h a n dk n o w l e d g el e a n i ti sf o rt h i sr e a s o nt h a td a t am i n i n 幽t od i s c o v e ru s e f u l k n o w l e d g ef r o ma m o u n t o fd a t a b yu n c o m m o nm e t h o d s ，h a sd e v e l o p e dv e r yq u i c k l y c l a s s i f i c a t i o ni saw i d e l yu s e dt e c h n o l o g yi nd a t am i n i n g 。t h e r ea r em a n ya l g o r i t h m s t h a th a v eb e e n p r o p o s e dr e c e n t l y , b u tm o s to f t h e mw e r em e m o r yb a s e da n du s u a l l y a s s u m et h a tt h ea m o u n to fd a t ai sn o tv e r yl a r g e w 熱t(yī) h el a r g e ra n d l a r g e ra m o u n t o f d a t a , i tb e c o m e sac h a l l e n g i n gp r o b l e mt of i n da ne f f i c i e n c yc l a s s i f i c a t i o na l g o r i t h m t h a ta d a p t st ol a r g ed a t a b a s e w i t l lr i c hd a t ai nw a i nt i c k e t s s y s t e m 。h o wt o m i n eu s e f u lk n o w l e d g ei sa l l i m p o r t a n tp r o b l e m a p p l y i n gt h et e c h n o l o g yo fc l a s s i f i c a t i o ni nt r a i nt i c k e t sa n a l y s i s ， w ec o n s t r u c tan e wc l a s s i f i c a t i o nm e t h o dt t _ d t c ( d e c i s i o nt r e ec l a s s i f i c a t i o n b a s e do nt r a i nt i c k e t s ) 。w ea p p l yn e wc l a s s i f i c a t i o na l g o r i t h ms f d t ( d e c i s i o n t r e 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 n s p l i t t i n gf i l e s ) t h a t b a s e so n s p l i t t i n gf i l e sa n d q u a n t i t yr u l e s ，w h i c ha i m e da tt h ec h a r a c t e r so ft r a i nf i c k e t s w er e a l i z et h ea n a l y s i s a n d p r e d i c t i o na b o u tt i c k e t ss a l ea n d t r a i no p e r a t i o nb yt h i sm e t h o d t 毯sm e t h o dh a s b e e nu s e di nw a i nt i c k e t sa n a l y s i ss u c c e s s f u l l y , a n d p r o v i d e d b n c o i n i n o n p a t t e r n sa n d d e c i s i o n i n f o r m a t i o n ，a n da c c o m p l i s h e d t h ec o n n e c t i o nb e t w e e nc l a s s i f i c a t i o n t e c h n o l o g y a n d l a r g ed a t a b a s e + t t _ d t cr e a l i z e sas e r i e so fp r o c e s s e si n c l u d i n gd a t ap r e p r o c e s s ，d e c i s i o nt r e e c l a s s i f i c a t i o n ，p r o d u c i n gr u l e sa n dp r e d i c t i o na n a l y s i s ，w h i c hb a s e do nt h ed a t ao f t r a i nt i c k e t sa n da i m e da tt h ec h a r a c t e r so ft r a i nf i c k e bw h i c hh a v el a r g ea m o u n to f d a t aa n dc o m p l e xa t t r i b u t e s 羽_ l i sm e t h o dc a nf u l l ym e e tt r a i nt i c k e t s a n a l y s i si n r a i l w a y , c a l le f f i c i e n t l ya n a l y z e a n dd e a lw i t ht r a i nt i c k e t sa n da t t a i nd e c i s i o n k n o w l e d g e w h i c hd k e mt h et r a i n o p e r a t i o n 。 t h e a l g o r i t h mo fs f _ d t , w h i c h b a s e so nt h ei d e ao fd e c i s i o nt r e ec l a s s i f i c a t i o n a l g o r i t h mi d 3 ，u s et h em e a n so f f i l es p l i t t i n gt a k et h ep l a c eo f t h em e a n sw h i c hb a s e s o n m e m o r y i ti m p r o v e st h es c a l a b i l i t yo fc l a s s i f i c a t i o na l g o r i t h ma n dc a l ld e a lw i t h v e r yl a r g e d a t a b a s e m o r e o v e rt h i s a l g o r i t h m e a r l p r o d u c eq u a n t i t y r u l e sw i t h s t a t i s t i c a li n f o r m a t i o na n ds u p p l yt h ed i s t r i b u t i o no fm a i nc l a s si nd e t a i l s s oi tc a n s u p p l y m o r ed e t a i li n f o r m a t i o nf o rd a t a a n a l y s i s w ef o u n dan e w a p p l i c a t i o nb a c k g r o u n df o rc l a s s i f i c a t i o nf o rf u r t h e rr e s e a r c h m o r e o v e r , b ya p p l y i n gt h ec l a s s i f i c a t i o ni nt h et r a i nt i c k e t sa n a l y s i s ，w ep r o v i d er i c h d e c i s i 強i n f o r m a t i o nf o rt h e m a n a g e m e n t o f t r a i no p e r a t i o n k e yw o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o n , d e c i s i o nt r e e ，t r a i nt i c k e t sa n a l y s i s ， q u a m i 夠r u l e s ，p a s s e n g e rt r a n s p o r t h 決繁秘分類旁法及箕在鐵路客幕營銷分析中韻程疆 第一章緒論 盡管數(shù)據(jù)挖掘技術(shù)已經(jīng)窩了很大的發(fā)展，并息應(yīng)用于社會生產(chǎn)的蒜個方面， 但是鑒予鐵路客票數(shù)據(jù)的特殊往，一直未能應(yīng)用劐鐵路客桑營銷分幫千中。本文 針對客票數(shù)據(jù)的特點研制開發(fā)了適用予客票挖掘的決策樹分類方法鞭d t c ， 并將其盤翅予鐵路塞票營銷分析，褥出了豐富的決策信息，用于指導裙車營運。 下面就論文的研究背景、研究意義以及論文的蹩體結(jié)構(gòu)作一介紹。 l 。l 論文髓研究背景 在數(shù)據(jù)庫技術(shù)迅猛發(fā)展的今天，人們產(chǎn)生和收集各種類型數(shù)據(jù)的能力迅速 提高，造成數(shù)據(jù)的大量堆積。其中包括條碼在商晶中的廣泛使用，商務(wù)、科學 和行政事務(wù)的計算機化，以及由文本和圖像掃描平臺到衛(wèi)星遙感系統(tǒng)豹數(shù)據(jù)收 集工其靜遴步。魏矯，律必全球信息系統(tǒng)的萬維兩的流幸予，更是將我們淹沒在 數(shù)據(jù)和信息的汪洋太海中。存儲數(shù)據(jù)的爆炸性增長激起了對新技術(shù)和自動工具 鵑囂求，以幫助我們將海量數(shù)據(jù)轉(zhuǎn)換成績息和醞識。盡管很早就出魏了籬摹的 數(shù)據(jù)統(tǒng)計技術(shù)，能夠?qū)?shù)據(jù)讖行一定的分析，但這遠遠不夠，我們需要更為先 避的智g 數(shù)據(jù)分拯工其對海鬈鶼數(shù)據(jù)售感進露更為深入斡瑗鰓秘分磐擎。 因此，在商業(yè)領(lǐng)域和科學研究領(lǐng)域都迫切要求發(fā)展這樣的技術(shù)，能夠從如 此海量的數(shù)據(jù)中抽敬如非平凡模式，找出數(shù)據(jù)變化的規(guī)律和數(shù)據(jù)之潮的楣互依 存關(guān)系，使人們能夠從宏觀的商層次的角度來審視數(shù)據(jù)，充分發(fā)掘數(shù)掰的潛力， 指導人們的行為，為決策和科學發(fā)展提供有力的支持。 于是，數(shù)據(jù)挖搦由大量數(shù)據(jù)中，靂菲平凡的方法發(fā)現(xiàn)有用的知識，就 成了一種自然而迫切的社會需求。正是這種廣泛的社會需求引起了人們的關(guān)注， 導致了數(shù)據(jù)挖撼研突翹蓬勃野展穗數(shù)據(jù)挖掘技米的不斷進步。數(shù)據(jù)挖掘任務(wù)一 般可以分為兩類：描述和預測。描述性挖掘刻畫數(shù)據(jù)庫中數(shù)據(jù)的一般特性；預 測性挖掇怒在當翦數(shù)據(jù)上進褥接藪，以送行頹濺。數(shù)據(jù)攜掇主要袁獄下凄能： 對概念和類進行描述；利用關(guān)聯(lián)分析發(fā)現(xiàn)關(guān)聯(lián)規(guī)則；分類和預測；聚類分析； 孤立點分櫥；演變分撰，攢述行為隨時閥變化懿對象的規(guī)律或趨勢，并對其建 模f 1 】磁。 數(shù)據(jù)庫蘊含大量的信息，可以用來做出各種勰能的商務(wù)決策。農(nóng)數(shù)據(jù)挖握 決鐿糖分類雋法及箕在鐵鑲騫票營鏞努輯孛斡盤甬 眾多的功能中，分類是其中一項非常重要的任務(wù)。分類是這樣的過程，它找出 縐述并區(qū)分數(shù)據(jù)類或穰念豹橫嫠，以矮能夠使薅模型預測類標號未知的對象類 【2 】。分類的目的是提出一個分類函數(shù)或分類模型，該模型能把數(shù)據(jù)庫中的數(shù)據(jù) 項映射到繪定類剮中瓣菜一個。分類楚數(shù)據(jù)挖掘?qū)彽囊涣钪匾獑栴}，匿蠹外的 研究人員在數(shù)據(jù)挖掘、統(tǒng)計分析、機器學習、神經(jīng)網(wǎng)絡(luò)、專家系統(tǒng)等領(lǐng)域中對 分類聞題避行了大鬟的硬究，提出了一系列鮑分類算法，如決策樹分類、貝時 斯分類、貝葉斯網(wǎng)絡(luò)和神經(jīng)網(wǎng)絡(luò)等( 詳見【3 】) 。j 璉年來，分類技術(shù)已l 被廣泛、 有效地應(yīng)用于科學實驗、醫(yī)療診斷、氣象預擐、商業(yè)預測、寨件偵破等領(lǐng)域， 引起了工業(yè)界和學術(shù)界的極大關(guān)注。 決策樹學習是以實例為基礎(chǔ)的歸納學習方法【4 】【s 1 。它者眼于從一組無次序、 囂痰羹| l 斡實鑲中捺臻決策瓣襲示形式秘分類規(guī)贈。它采蕉蠹瓚向下靜遞歸方式， 在決策樹的內(nèi)部結(jié)點進行屬性的比較并根據(jù)不同屬性值判斷從該結(jié)點向下的分 枝，在決策樹鼴時縮點得戮結(jié)論。所蔽從壤到時絳點翳一條籍徑葳對應(yīng)著一條 合取規(guī)則，整棵決策樹就對應(yīng)著一組析取表達式規(guī)則。決策樹分類法實現(xiàn)簡單， 層次績椽濤曦，夠產(chǎn)生荔予理燼和分析懿巍則，困既是臻蔻瘟援較必廣泛懿 分類方法階【1 0 1 。 本文中我們將決策樹分類闋鐵路客票營銷分掇相結(jié)合，測用決策楗的方法 對客票數(shù)據(jù)進行分類，并將分類得出的預測信息，應(yīng)用于鐵路客運的上層決策 分析舊f l l 】【1 鯽。 我霞鐵路窖票系統(tǒng)每囂產(chǎn)生的售鬃記錄高遮3 0 0 余萬條，分布存儲在各級 服務(wù)器的數(shù)據(jù)庫中，以一定周期傳輸、匯總、集中到鐵道部，數(shù)據(jù)經(jīng)過整理壓 縮勞長裁保存【l l 】h2 】。為了實現(xiàn)較高速發(fā)的怒大援模數(shù)據(jù)瘁套誨和多楚度豹統(tǒng)計 分析，鐵道部門對上述交易數(shù)據(jù)進行了避一步的爛理和重組，形成了以決策分 糲鴦主要瓣的大型數(shù)據(jù)疼系統(tǒng)客鬃營銷分稷蓉裂嘲，它是采震全耨戇數(shù)攢 模式組織的大型數(shù)據(jù)庫系統(tǒng)，其中存儲了大量的原始客票數(shù)據(jù)，這必數(shù)據(jù)規(guī)模 巨大，蘊涵豐富的決策信息和知識，開發(fā)這些寶賽馳信息資源，服務(wù)予客運營 銷決策，是提高鐵路客運市場競爭力的一項重要 壬務(wù)，也是目前迫切需要解決 的問題。 鐵路客票營銷分祈不儀僅是簡單的統(tǒng)計分析，最主要的是散非平凡模式的 2 決策樹分類青法愛其在鐵路饔象營鑣分輯串豹盤閹 知識提取。因此，我們需要利用其提供的良好的數(shù)據(jù)，結(jié)合數(shù)據(jù)挖掘的技術(shù)， 獲中提煉出更為有踴的決策知識。本文將數(shù)據(jù)挖掘中分類的決策樹惑想用于客 運營銷分析中客票的屬性分析，對客票發(fā)售的時間、數(shù)量、種類、列率運營的 特點等進褥分類褻疆溺，褥出客運中鵑羲于規(guī)律，提供給上屢決策部門避行進 一步的決策分析( 詳見【1 1 1 ) 。 1 2 論文的研究意義 我國地廣物博，人口巨大，市場經(jīng)濟的迅速發(fā)展需要人流物流的大規(guī)模轉(zhuǎn) 移，氌就適成了莓前我國大規(guī)模的入日流動現(xiàn)狀。特鬟是春節(jié)、寒暑假、五一、 十一長假更是客流的高峰，這種大規(guī)模的人口流動大大加重了客運負擔。就我 國囂蔫弱壤況，鐵路運輸仍然愚最重要豹客運方式，我蠶有大規(guī)模翡鐵路閼絡(luò)， 每天有幾酉萬的客流量，如何合理有效的組織客運，控帝9 客流，保證鐵路暢通， 合理離效運轉(zhuǎn)是一個常僮樽關(guān)注的謠蘧h “。 客票睹銷分析怒對大規(guī)?？推睌?shù)據(jù)進行的決餓分析，它建立在超大規(guī)模的 客票數(shù)據(jù)摩系統(tǒng)之上，該系繞包含蓑蓑干年的客漿發(fā)售記蒙，露這些數(shù)握中蘊 涵著豐富的決策信息。目前在這些數(shù)據(jù)上只能做些簡單的統(tǒng)計分析，無法進 行真正意義上的營銷分析，提取有用的決策信息。因此，急鼴將數(shù)據(jù)挖掘技術(shù) 葡客票營銷分析葙結(jié)合，以使對巨量的客票數(shù)據(jù)進行分析和處理，產(chǎn)生應(yīng)用予 鐵路營銷分析的決策知識。數(shù)據(jù)挖掘技術(shù)在鐵路窖票分析中有著相當廣泛的應(yīng) 瘸蘺景，密票系統(tǒng)斡數(shù)器量鏨繁重大，疆盈憊含麓豐塞的決策蓓怠，因魏，從 中挖掘出商用的知識模式指導列車營運，合理分配客流是非常必要和迫切需要 解決的閥鬏。 在數(shù)據(jù)挖掘技術(shù)日益成熟的今天，已經(jīng)出現(xiàn)了很多數(shù)據(jù)挖掘的軟件工具， 如s a s 、d b m i n e r 、b u s i n e s s o b j e e t 、q u e s t 、m i n e s e t 等。這些都是逶鼴豹數(shù) 據(jù)挖掘商業(yè)軟件，它們都有較強的數(shù)據(jù)挖掘能力，能夠?qū)σ欢ㄒ?guī)模的商業(yè)數(shù)據(jù) 進行關(guān)聯(lián)飆則、分類、聚類等操作。但這些工具對于超太規(guī)模的客票數(shù)據(jù)的她 理卻受到綴大的限制，而且這些工具酌設(shè)詩著眼予通用的商業(yè)角度，因此不能 針對鐵路裙票數(shù)據(jù)的實際情況進行相應(yīng)的分析處遐，無法直接應(yīng)用予客票數(shù)據(jù) 漿挖撼。 針對這種情況，本文著眼于鐵路客票營銷分析的具體情況，針對客票數(shù)據(jù) 決蒙褳分類旁法及其在鐵鏈客票藿銷分析中朗瘦麓 的具體特征和客票信息挖掘的具體要求，研究開發(fā)一種利用決策樹分類的基本 恿想，適合予鐵路客蔡努類鶼方法耵d t c ( d e c i s i o n t r e e c l a s s i f i c a t i o n b a s e d o n t r a i nt i c k e t s ) 。其中對決策糖分類算法進行了相成的改進，使之適臺大規(guī)?？?桑數(shù)攝戇楚疆。零文零l 瘸改避 舞豹毅算法s f _ d t ( d e c i s i o nt r e ec l a s s i f i c a t i o n a l g o r i t h m b a s e d o n s p l i t f i n g f i l e s ) ，將數(shù)據(jù)挖掘分類中的決策樹技術(shù)用予客票營 鑲分櫥孛麴客票穆類分接，報攫客票翡實際記錄遴行實驗，褥塞了獵簿列車營 運的決策信息，實現(xiàn)了分類技術(shù)在客票旃銷分析中的應(yīng)用。 通過研究，我們驗涯了將數(shù)據(jù)挖掘技術(shù)應(yīng)用予鐵路窖檠營錈分析的可行性 和有效性，勞發(fā)現(xiàn)了相應(yīng)的問題，也就是純粹的理論研究與實際應(yīng)用之間的差 距。我們針對鐵道科學院電子計算技術(shù)研究所客隳分析的實際震要，努力從理 論和應(yīng)用兩個方面解決這個闡題。 1 3 論文的整體綾構(gòu) 本文簡要介紹了數(shù)據(jù)挖掘技術(shù)中的決策村分類及鐵路客票營銷分析的內(nèi) 容，重點分纓我們針對鐵路客梁營銷分析設(shè)計開發(fā)的分類方法t td t c ，及改進 韻決策樹分類算法s fd t ，最后將我們設(shè)計的決策樹分類方法哪t c 和鐵路 客票營銷分柝相結(jié)食，對客檠數(shù)據(jù)進行分析。 各章內(nèi)容安排如下： 第一幫緒論 介紹本文靜研究背景及研究意義，總結(jié)整個研究工作的內(nèi)容以 及論文的組織結(jié)構(gòu)。 第二灌數(shù)蕹挖搖孛熬分類技術(shù) 首先對數(shù)據(jù)挖掘的基本慰想、方法、過程、內(nèi)容進行簡要介紹， 然惑燕點分纓分類的概念、基本感想及主要舞法，接下來舟紹零 文中應(yīng)用的主臻方法一決策樹分類。 第三顰鐵路客票營銷分析 本章主要介紹鐵路客票籬銷分析的內(nèi)容和背景，客票數(shù)據(jù)的來 源及其特點，以及客票落銷分析的內(nèi)容和意義。 第溷鬻基予鐵路客鬃薷錆分幫亍的決策瓣分類方法n d t c 本章詳細介紹了決策樹分類方法1 t - d t c 的全過程，從數(shù)據(jù)預 4 決錘鍵分類方法及其在鐵褥窖票藿鎮(zhèn)分輯中載班甩 第五章 第六嫩 處理、決策樹分類算法、到剪枝、規(guī)則形成，最后對其中出現(xiàn)的 翊題進 亍分祈。其中詳緇介紹了該分類方法的藿點內(nèi)容基子 文件分割和定量規(guī)則的改進的決策樹算法s f d t ，給出算法的 援述積實現(xiàn)過程。 t td t c 在鐵路客票營銷分析中的應(yīng)用 本鬻將t td t c 方法應(yīng)懲予鉸爨容票營鎊分梧，跟蹤狂d t c 實現(xiàn)的全過程，從實例的角度詳細分析整個方法的執(zhí)行，并對 產(chǎn)生的結(jié)果進行分析，繕蹬有益予上層決策分輯的知識。 結(jié)束語 對全文進行總縫，并指嫩鼴要進一步傲的研究。 決鍍藕贊類殼法疆其在鐵游客幕營銷分輯孛的蠹蹋 第二章數(shù)據(jù)挖掘中的分類技術(shù) 信息科學的發(fā)展引起數(shù)據(jù)的高度膨脹，如何有效地處理大規(guī)模的數(shù)據(jù)信息， 褥出有用知識，饅成為囂藏俊褥關(guān)注的閼題。數(shù)掇挖掘放大援模數(shù)據(jù)孛發(fā) 現(xiàn)非平凡模式，正怒應(yīng)此要求迅速發(fā)展起來的- - v j 科學。本章簡要介紹了數(shù)據(jù) 挖掘及分類技術(shù)，并對其中的決策樹分類做較為詳細昀介緇。 2 1 數(shù)據(jù)挖掘概述 蘧麓鑲惑科學鼓術(shù)弱迅速發(fā)建，數(shù)掇量鑫盞纛大，數(shù)據(jù)麴浚集箱存鑲邀越 來越容易。一方面，許多新型的數(shù)據(jù)收集過程更有效、更精確。例如，在商場 銷售系統(tǒng)中使用斡條碣讀入器能夠分辨掰敗買纛菇憨秘類、凝號及儈揍等售塞， 使商場能夠很容易收集到完善的銷售記淥。許多原來依靠人工才能完成的數(shù)據(jù) 收集過程毆經(jīng)半自動化或全自動化，使褥單位時閱內(nèi)可以收集到的數(shù)據(jù)量迅速 增加。此辮，一些新的裝置能夠收集原來很困難躐根本不可能收集到的信息。 另一方面，數(shù)據(jù)存儲設(shè)備的價格已大幅下降，存儲的形式甏趨多樣化，且性能 躉強。一魏新懿存德奔震，鐨翔可讀寫豹先盤，w 戳方便撼存儲大蝥豹數(shù)據(jù)。 由于以上兩方面的原因，使得目前能夠以合理的成本收集和存儲大量的數(shù)據(jù)， 這些數(shù)搖一般毒德予鼗器摩孛，鐵零l 予梭索幫囂綏戇處理。 這些既為從數(shù)據(jù)中抽取有用的信息提供了機遇，同時也給大規(guī)模數(shù)據(jù)的知 識接取撮爨了挑竣。麓蕈的絞計分櫥，跑據(jù)計算媳篷、標臻方差等，一定程度 上是有用的。但是，這種簡單分析的結(jié)果還不能夠揭示出隱含在大量數(shù)據(jù)中的 知識。因此，急需一軍申好的方法對大規(guī)模的數(shù)據(jù)避行分拆處理。 數(shù)據(jù)挖掘，又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)，是描從數(shù)據(jù)庫中提取非平凡模式 【2 】【1 3 】。這燃模式是有效的、新穎的、有潛在實用價值的和易于理解的。提取的 知識霹戳襲示為禳念、規(guī)粥、規(guī)律和禳殘等形式。 數(shù)據(jù)挖掘作為知識發(fā)現(xiàn)的過程，分三個主要階段：數(shù)據(jù)準備、數(shù)據(jù)挖掘、 結(jié)采評價灝表這暖 ( 1 ) 數(shù)據(jù)準備 數(shù)蘩瞧簽除段囊一些子狳浚穆藏，箕孛包搖：數(shù)據(jù)濤溪( d a t a 如蕊n g ) ， 去除噪聲或不一致的數(shù)據(jù)；數(shù)據(jù)集成( d a t ai n t e g r a t i n g ) ，將多個數(shù)據(jù)源的數(shù)據(jù) 6 決鑲挺努類鴦法及其在鐵終客票營銷分輯串鞠盛精 歸并在一起；數(shù)據(jù)選擇( d a t as e l e c t i n g ) ，從數(shù)據(jù)庫中檢索與分析任務(wù)相關(guān)的數(shù) 攥；數(shù)器變換( d a t a t r a n s f o r m i n g ) ，將數(shù)撩交換或統(tǒng)一成適合挖掘的形袋e ( 2 ) 數(shù)據(jù)挖掘 數(shù)據(jù)挖掘除段楚知識發(fā)袋過程中的核心除段。在這個獪段，采鬻蒗予智能 的方法去提取數(shù)據(jù)模式，其中包括的要點有： 掘程產(chǎn)生瑕設(shè)：也裁怒讓數(shù)據(jù)挖掇系統(tǒng)雋懲戶產(chǎn)生鎂浚，還楚攥戶自己 對于數(shù)據(jù)摩中可能包含的知識提出假設(shè)的問題。前一種稱為發(fā)現(xiàn)型 ( d i s c o v e r y 。d r i v e n ) 數(shù)摟挖握，后一秘稱為驗證型( v e r i f i c a t i o n - d r i v e n ) 數(shù)據(jù) 挖掘。 選擇合適的挖掘工具。 知識挖掘靜操作。 驗證發(fā)現(xiàn)的知識。 ( 3 ) 結(jié)果評俊霹表達 根據(jù)用戶的決策目的，對提取的倍息進行分析和評價，把最有價值的信息 囂分出來，共量逶遐決策支持工具提交繪決策考。這一步豹鑷務(wù)不儀懋怒結(jié)果 表達出來，還要對挖掘出的數(shù)據(jù)模式進行評價、過濾處理。 2 2 分類 分類是數(shù)據(jù)挖掘中一項非常重要的任務(wù)，目前在商業(yè)上應(yīng)用非常廣泛1 4 】。 下囂對分類接本骰更為詳纓戇奔紹。 2 2 1 分類的基本概念 分類( c l a s s i f i c a t i o n ) 是攢提出一個分類丞數(shù)或分類模鍪( 也穗終分類器) ， 該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個1 2 1 。數(shù)據(jù)分類是一個 兩步過程； 第一步，建立一個模型，描述預定的數(shù)據(jù)類或概念集。通過分析由屬性描 述的數(shù)據(jù)庫元組來構(gòu)造模型。假定每個元組屬于一個預定義的類，由一個稱作 梁標號瘸性豹屬性確定。對予分類，數(shù)據(jù)元組也稱作樣本、實鍘或?qū)ο?。為?拒模型而被分析的數(shù)據(jù)元組影成訓練數(shù)據(jù)集。訓練數(shù)據(jù)集中的單個元組稱作訓 練徉零，薺隧惑遮內(nèi)樣本群選取。由予提供了每個調(diào)練樣本的類標弩，該步驟 也稱作有指導的學習( 即在被告知每個訓練樣本屬于哪個類的指導下進行模型 決策樹分類方法及其在鐵路客票營銷分析孛的瘟舄 戇學習) 。它不霜予無攆導豹學習( 如袋類) ，在鄭里，每個調(diào)練樣本鵲類標號 是未知的，要學習的類集合和數(shù)量也可能事先不知道。通常，學習模測用分類 燒劉、決策樹或數(shù)學公式豹形式提供。該溉剮可滋用來瓷以后翡數(shù)據(jù)樣本分類， 也能對數(shù)據(jù)庫的內(nèi)容提供更好的理解。 第二步，使用模型進行分類。首先譯佑模型( 分類法) 的礞測準確率。保 持( h o l d o m ) 方法魑一種使用桊標號樣本測試集的簡單方法。這些樣本隨機選 取，并獨立于訓練樣本。對于每個測試樣本，將融知的類標號與該樣本的學習 模型類預測比較。被模型正確分類的測試樣本的褥分比就楚模型在給定測試集 上的準確率。注意，如果模型的準確率根據(jù)訓練數(shù)據(jù)集評估，評估可能是樂觀 酌，醫(yī)兔學習模鍪l 傾向予過分適合數(shù)據(jù)( 韶，它荀能并入曹i l 練數(shù)據(jù)中菜些異常， 這些異常不出現(xiàn)在總體樣本群中) 。因此，通常使用測試集來評估分類算法的準 確率。鬣果認為摸型的準確率胃戮接受，就可默翔它對類標號未知的數(shù)程元組 或?qū)ο筮M行分類。 2 。2 。2 分類的基本技術(shù) 經(jīng)過多年的研究，目前已產(chǎn)生了眾多的分類技術(shù)，下面將簡要介紹一些常 用戇分類鼓本，鴦馨決策辯分類、燹時裁分類、基予搴孛經(jīng)圈終瓣分類，黻及源予 關(guān)聯(lián)規(guī)則挖掘概念的分類【3 】f 1 ”。 ( - - ) 決策褥分類 基于決策樹的分類方法是一種監(jiān)督學習的方法【1 5 】- 1 2 0 ，樹的數(shù)量由分類的精 度和樹的大小決定。這種方法蘺先選擇訓練樣本熬一令子集以形成一橡決策挺， 如果此樹沒有為所有的對象給出一個芷確的答案，則將例外情況加入到樹中， 不斷重復這一過程直到發(fā)現(xiàn)正確的決定榘。最終將形成這樣一棵樹：每一片盱 子代表一個類名，每個內(nèi)部節(jié)點描述一個屬性，節(jié)點的每一個分枝對應(yīng)于該屬 性的每一個可能的值。 關(guān)于捩策耱分類在第三繁串詳箍套縭。 ( 二) 貝葉斯分類 貝時斯分類是統(tǒng)計學分類方法，它麓于貝時新定理【捌?？梢灶A測類成員關(guān) 系的可能性，如給寇樣本屬于個特定類的概率。 分類算法釃院較磷究發(fā)現(xiàn)，一種稱佟樸素翼時斯分類的簡單貝葉簸分類算 決鐐挺分類京法愛其在鐵海客票營鎊饋輯中韻敷褥 法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分類算法相媲美。樸素貝葉斯分類假定一個屬性值 對給定類的影晌獨立于其它耩性的值。該假定稱作類條件獨立。散此假定是為 了簡化所需計算，并在此意義下稱為“樸素的”。理論上講，與其它所肖分類算 法楣斃，貝時蓑分類具有最， 、熬出錯率。然兩，實踐牽并簿總是如魏，這是由 于對其應(yīng)用的假定( 如類條件獨立性) 的不準確性，以及缺泛可用的概率數(shù)據(jù) 造成懿。 樸素貝葉斯分類假定類條傳獨立，即給定樣本的類標號，屬性的值相互條 孛獨立。這一假定鐫化了計冀。當瑕定成立時，與其它援鴦分類算法稠斃，$ 索貝葉斯分類是最精確的。然而，在實踐中，變贊之間的依賴可能存在。貝葉 巔信念剛絡(luò)說明聯(lián)合概率分布，能表示屬性子集聞的依賴，彌補了 索貝葉斯 分類的不足。它允許在變量豹予集間定義類條件獨立性。它提供一種因采關(guān)系 的圖形，可阱在其上進行學習。在學習或訓練信念網(wǎng)絡(luò)時，許多情況都是可能 的。弼絡(luò)結(jié)構(gòu)霹g l 預先給定，或由數(shù)據(jù)等密。網(wǎng)絡(luò)變量可能是可見靜，或隱藏 在所有或某些訓練樣本中。隱藏數(shù)據(jù)的情況也稱為空缺值或不完全數(shù)據(jù)。如果 羽終縫構(gòu)酲強蒡量變量是哥藏麴，訓練闞絡(luò)毒豁警接送行。該逶覆垂計算c p t 項組成，與樸素貝葉斯分類涉及的計算概率類似。當網(wǎng)絡(luò)結(jié)構(gòu)給定，麗某些變 璧是隱藏的時，則霹使用梯魔下海方法諼練售念髓終。 貝葉斯網(wǎng)絡(luò)的研究在國外十分廣泛，它可以對不確定性知識迸彳亍推理。例 如：醫(yī)生看病，根據(jù)病人的疲狀，判斷瘸人是否得了菜穆疾病，往綻是一種不 確定的推理( 帶概翠的推理) ，多數(shù)情況下沒有百分之百的把握。運用貝葉斯網(wǎng) 絡(luò)進行推理，可以達到較好的效果。 ( 三) 基于神經(jīng)網(wǎng)絡(luò)的分類 神經(jīng)網(wǎng)絡(luò)最早照由心理學家和神經(jīng)舉家提出的，旨在罨求開發(fā)和澳4 試神經(jīng) 靜計算穰擬。褪略轆說，神經(jīng)網(wǎng)絡(luò)是一綴連接的輸入糯出單元，其中每個連接 都與一個權(quán)相聯(lián)。在學習階段，通過調(diào)熬神經(jīng)網(wǎng)絡(luò)的權(quán)，利用預測輸入樣本的 正確類標號來學習。由于擎元之闋鶼連接，神經(jīng)麗絡(luò)學習又稱連接者學習 【1 9 】【2 0 】雎1 1 。 撩經(jīng)網(wǎng)絡(luò)囂要很長的潮練對間，因露對于有足夠長鍘練時間蛉建鞠更合適。 神經(jīng)網(wǎng)絡(luò)已| 經(jīng)在很多領(lǐng)域得到了成功的應(yīng)用，但由于缺乏嚴密的理論體系的指 決鐐撼靜類方法及其在鐵魏窖票藿鑣分橇孛匏寢甬 導，其應(yīng)用效果完全取決于使用者的經(jīng)驗。雖然h o r n i k 等人證明，僅商一個非 線牲隱整鶼前馕潮絡(luò)就能戳任意疆瘦遙避任意復雜度漿囂數(shù)，毽一些研究者指 出，對網(wǎng)絡(luò)的配置和訓練是n p 問題。在實際應(yīng)用中，由于缺乏問題的先驗知 識，往往鼴經(jīng)大量贊力耗對馳實驗摸索孝能確定會逶豹專棗經(jīng)鼷終摸受、算法良 及參數(shù)設(shè)置，其應(yīng)用效果完全取決于使用者的經(jīng)驗。即使采用同樣的方法解決 同樣的聞題，由于操作者不同，其結(jié)果也很可能大糖徑庭。另終，由予人們綴 難解釋蘊涵在學習權(quán)之中韻符號含義，神經(jīng)網(wǎng)絡(luò)常常因其可解釋性差而受到批 評。這些特點使得神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘的初期并不看好。 然焉，卒孛經(jīng)兩絡(luò)的優(yōu)點包括其對嗓譜數(shù)據(jù)的離承受能力，以及它對未經(jīng)訓 練的數(shù)據(jù)的分類能力。此外，最近已提出了一些由訓練過的神經(jīng)網(wǎng)絡(luò)提取規(guī)則 熬算法，這些因素撼動了襻綴網(wǎng)終在數(shù)據(jù)挖掘分類方面靜瘦爆。 ( 四) 源于關(guān)聯(lián)規(guī)則挖掘概念的分類 關(guān)聯(lián)麓粼挖掘怒數(shù)蕹挖瓣磷究靜一個重要的、高度活躍靜領(lǐng)域h 9 1 。最近， 數(shù)據(jù)挖掘技術(shù)己將關(guān)聯(lián)規(guī)則挖掘用于分類問題。下面，我們按歷史次序簡要介 綏三秘方法。羲囂釋方法，a r c s 幫關(guān)聯(lián)分類，嬡用關(guān)聯(lián)規(guī)剽分類。第三群方 法c a e p 挖掘“顯露模式”，宦考慮挖掘關(guān)聯(lián)規(guī)則使用的支持度概念。 第一秘方法，基于聚類挖撅關(guān)聯(lián)規(guī)則，然羼使用規(guī)則進行分類。a r c s 或關(guān) 聯(lián)規(guī)則聚淡系統(tǒng)挖掘形如a q 。m l 。味苷a 。m 的關(guān)聯(lián)規(guī)則；菠中，a q u 枷l ，a q ?！? 2 是在量化屬性區(qū)間上的測試( 區(qū)闖動態(tài)地確定) ，褥氏。為給定訓練數(shù)據(jù)的分類 滿性指定一個類標號。關(guān)聯(lián)規(guī)則畫在2 - 1 ) 柵格上。算法掃描柵格，搜索規(guī)則的 矩形聚類。用這種辦法，出現(xiàn)在一個規(guī)貝| j 聚類內(nèi)的量化屬性的楣鄰區(qū)間可以結(jié) 會。壺a r c s 產(chǎn)生瀚聚類關(guān)聯(lián)蕊燹| l 霜予分類，其臻確率可與c 4 。5 媲美。 第二種方法稱作關(guān)聯(lián)分類。它挖掘形如c o n d s e t ；y 的規(guī)則；其中，c o n d s e t 建項( 或掇萑篷對) 豹集合，囂y 是類標號。濾麓最棗支持度豹撬猁怒頻繁的； 這里，規(guī)則具有支持度s ，如果給定數(shù)據(jù)集中的樣本s 包含c o n d s e t 并且屬于 類y 。滿足最小置信度的規(guī)則怒糖確的；這里，戴劉鮑愛信度為c ，如渠給定數(shù) 據(jù)集中包禽c o n d s e t 的樣本c 屬于類y 。如果一個規(guī)則項集具有相同的c o n d s e t ， 則選擇具有最高置信度的規(guī)則讒為可熊規(guī)則( p r ) ，代表該集會。 關(guān)聯(lián)分類方法由兩步組成。第一步怒找出所有頻繁的、精確的p r 集合。這 1 0 決繁樹分類去法及其在鐵潞窖票營銷論輯中的硒 麓是類關(guān)聯(lián)瓣弼( e a 釉。莢c o n d s e t 奄會k 個矮豹惑劉頊穆終磊焱爨頊。冀法鑊 閣迭代方法，先驗知識用于裁減規(guī)則搜索。第二步使用一種扇發(fā)式方法構(gòu)造分 類。這里，發(fā)現(xiàn)款怒戴攫握支持度窩置信度按遞減戇優(yōu)先次繆綴織。 第三種方法c a e p ( 通過聚集顯露模式分類) 使用項集支持度挖掘照鼯模式 ( e m e r g i n gp a t t e r n ，e p ) ，兩e p 用于構(gòu)造分類。粗略地說，e p 是一個項集( 項 的集合) ，蕻支持度豳一個類劉另一個類駐著增加。兩個支持度的比稱作e p 的 增長率。例如，假定我們有顧客數(shù)據(jù)集，包含類b u y s _ c o m p u t e r = “y e s 或c l 和 b u y s _ c o m p u t e r = “n o 或c 2 。袋集 a g e 菇一- 3 0 ，：s t u d e n t s 。w 是一個典型的 e p ，其支持度由在c l 中的o 2 增長到猩c 2 中的5 7 6 ，增長率罟等= 2 8 8 。 注意，一個項或者避分類屬性上的簡單棚等測試，或者是梭饔數(shù)值璃能是否在 桀個區(qū)間的測試。每個e p 是一個多屬性上的測試，并且可能在區(qū)分一個類的 實鋼與另一個類靜實鐨方囂菲常強。霧 | 翔，弼采一個新樣本x 雹臺在上囂靜e p 中，我們可以說x 屬于c 2 的幾率為9 9 6 。一般地，e p 的區(qū)分能力火約正比 予它懿撞長率纛宅穗囂糖類豹支簿度。 一種將代的分類算法稱作j e p 分類算法( j e pc l a s s i f i e r ) ；該算法怒基于跳 躍顯露模式( j u m p i n g e m e r g i n g p a t t e r n ，j e p ) 提出的。其中，j e p 是一釋特殊類 型的e p ，定義為這樣的項集，其支持度由在一個數(shù)據(jù)集中的0 陡峭地增長到另 一個數(shù)據(jù)袋中的非0 。醫(yī)為j e p 具有無窮大的增長攀，而e p 爨有有窮的增長率， 所以j e p 比e p 的隧分能力懿強。這使褥在許多大型數(shù)據(jù)群( 尤其是維數(shù)也很 大的數(shù)據(jù)麾) 中，糕于j e p 的分類算法優(yōu)于基于船的分類葬法。 2 2 3 分類算法豹阮較標準 常用的分類算法的比較和評估標準肖以下幾點： ( 1 ) 預鍘靜壤確率：涉及模型正確魏預測新豹或先前寒見過的數(shù)據(jù)的類標 號的能力。 ( 2 ) 速菠：涉及產(chǎn)生秘矮霜模墼斡詩算花贊。 ( 3 ) 強壯性：涉及給定噪音數(shù)據(jù)或具有空缺值的數(shù)據(jù)，模型正確預測的能 力。 ( 4 ) 可規(guī)模性：涉及給定大量數(shù)據(jù)，有效地構(gòu)造模型的能力。 ( 5 ) 可解釋性：涉及學淫模型提供憋理鰓翻漏察的屢次。 決鑲?cè)祆o糞方法及萁在鐵鼴騫票營銷靜輯串靛敷稿 目前，已有許多關(guān)于不同分類算法的比較，并且該問題仍然是一個研究課 藤。海未發(fā)現(xiàn)有秘算法對掰有數(shù)據(jù)都饒于其它方法。魏準確性、調(diào)練時闖、 強壯性、可解釋性和可規(guī)模性必須考慮，并且可能涉及折衷，使得尋求更好方 法進一步復雜經(jīng)。實驗研究表麓，許多冀法豹準確性豢癸似，其差溺是統(tǒng)計 不明顯的，而訓練時間可能顯著不同。另外，可規(guī)模性也是目前考慮較多的一 個囂素，巒予出璦了越來越多瓣超大援摸靜數(shù)據(jù)瘁系統(tǒng)，魘戮是否熬夠有效蟪 處理大規(guī)模數(shù)據(jù)也成為衡量算法的重要標準。 2 。3 決策樹分類 分類是數(shù)據(jù)挖掘中一項非常重要的任務(wù)，分類的目的怒提出一個分類函數(shù) 或分類摸型( 分類器) ，該攘燮娩把數(shù)據(jù)癢孛鵓數(shù)據(jù)項獲射裂給定類裂巾豹某一 個。決策樹學習是以實例為基礎(chǔ)的歸納學習算法。它著眼于從一組無次序、無 翹劐的事例中推出決策樹表示形式的分類規(guī)劉。它采用蠡 樊向下的遞歸方式， 在決策樹的內(nèi)部結(jié)點進行屬性的比較并根據(jù)不同屬性值判斷從該結(jié)點向下的分 棱，在決策樹的葉縮點褥到結(jié)論。所以從根到葉結(jié)點的一條路徑就對應(yīng)著一條 龠取規(guī)剮，整操決策樹就對藏著一組析取表達式規(guī)則i 2 0 】。 一棵決策樹的內(nèi)部結(jié)點是屬性或?qū)傩约?，葉結(jié)點是所要學習劃分的類【1 6 1 。 造經(jīng)過一撬譬l | 練實翻集敬調(diào)練產(chǎn)生一裸決策樹，決策樹茸戳根據(jù)屬佼豹取蓬對 一個未知實例集進行分類。使用決策樹分類的時候，由樹搬開始對該對象的屬 鏈遂一測試其毽，弗且順羞分技勻下走，壹至到達菜拿辭終點，斃跨絡(luò)點代表 的類即為對象所處的類。 2 。3 。1 基本恿想 決策樹分類是一種以決鐐樹這種數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)的分類算法1 1 5 州9 】。決策樹 ( d e c i s i o nt r e e ) ，又稱判定糖，是一個類壁雯予滾糕圈戇撼繚麴，其中每個內(nèi)部 結(jié)點表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉結(jié)點 代表類或類分布。為了對未知的樣本分類，樣本的屬性僮農(nóng)判定楗上測試，路 徑由根到存放該樣本預測的時結(jié)點。決策樹很容翳轉(zhuǎn)換成分類規(guī)則【3 4 1 【3 鰳。 決策樹歸納的基本算法懸貪心算法，它是以自頂向下遞歸的各個誨破方式 梅造決策樹。算法的基本策略如下【1 朝： ( 1 ) 樹以代表訓練樣本的單個結(jié)點開始。 決餓樹分類夯法及其在鐵鼴客票營銷分析中曲盛嗣 ( 2 ) 如累樣本都在同一個類，則該結(jié)熹殘為樹時，勢用該類標記。 ( 3 ) 否則，算法使用稱為信息增靛的基于熵的度量作為啟發(fā)信息，選擇 髓夠最盎 遮將樣本分類的屬梭。該屬性成蕊該續(xù)患的“測試”或“決 策”屬性。 ( 4 ) 對測試屬性的每個毆知的馕，劍建一個分技，并據(jù)此劃分樣本。 ( 5 ) 算法使翊同樣的過稷，遞歸地形成每個劃分上的樣本決策樹。一旦 一個屬性出現(xiàn)在一個結(jié)點上，就不必在該結(jié)點的任何后代上考慮它。 ( 6 ) 遞婦翊分步驟僅警下菊條 串之一成立對停止： 給定結(jié)點的所有樣本屬于同一類。 沒商剩余霾餓霹以用來避一步劃分樣本。農(nóng)此情囂下，使用多 數(shù)襲決。這涉及將給定的結(jié)點轉(zhuǎn)換成樹葉，并用樣本中的多數(shù) 鼴在的類標記宅。替換縫，霹以存放縫點樣本的類分毒。 分枝t e s ta t t r i b u t e = 口f 沒有樣本。在這種情況下，以樣本中的 多數(shù)類創(chuàng)建一個越時。 在樹的每個結(jié)點上使用信息增益( i n f o r m a t i o ng a i n ) 度量選擇測試屬性。 這種度量稱作屬性選擇度量或分裂的優(yōu)劣度量。選器具有媛齏信息增薤( 或最 大熵壓縮) 的屬性作為當前縮點的測試渦性。該屬性使得對結(jié)果劃分中的樣本 分類所需的信息量最小，并反映劃分的最小隨機性或“不純性”。這申信息理論 方法使得對一個對象分類所鬻的期望測試數(shù)強最小，并確保找到一棵簡單的樹。 設(shè)s 是s 個數(shù)據(jù)樣本的集合。假定類標號屬性具有m 個不同值，定義m 個 苓囂類c i ( i = l ，+ ，喲。設(shè)毋楚類c 中的樣本數(shù)。對一個繪定的樣本分類所器的 期望信息由下式給出： * 砸l ，s 2 ，$ 。) = p fl 0 9 2 ( p 1 ) j 1 1 其中，辣是任意攆本耩予舀瀚概率，并瘸曲s 話詩。注意，對數(shù)函數(shù)戳2 為底， 因為信息用二進位編碼。 設(shè)屬性崖具鴦v 個不矮嫠 露。硝e 霹菝羆屬性蠢將s 劃分走v 個子集 & ，。 島 ；其中，s g 含s 中這樣一些樣本，它們在4 上具有值嘶。如果一選作測試 屬性( 即，最好靜劃分屬性) ，則這些子集對應(yīng)于鴦趣含集合s 懿結(jié)蔗生長出采 決鑲楗癸類寵漩及其在鐵鑲客票營鏡分輯中釣盤臻 的分枝。設(shè)曲是子集s j 中類a 的樣本數(shù)。根據(jù)爿劃分子集的熵( e n 廿o p y ) 或期望 鑲惠盤下鼗繪密： g ( a ) ：窆型竿瑪吣，嘶) f 硝 。 項旦坐二i ：! 墮充當?shù)趈 個子集的權(quán)，并風等于子集( 即，a 值為a j ) 中的樣本 個數(shù)豫戳s 中懿群零總數(shù)。麓譙越小，子集麓分的統(tǒng)度越麓。注意，辯于給定 的子集s ， 砸s 護，s w ) = p 口l 0 9 2 ( 聊) 其中，p f = 羔，怒昌中的樣本屬于舀的概率。 i u ，l 在上分棱將獲得懿編磷信息是 g a i n ( a ) = j 瓴，s 2 ，) 一e o ) 換言之，g a i n ( a ) 魁由于知道j j 甄性的假而導致的熵的期望雁縮。 算法計算每個麟性的信崽增益。具有最毫信爨增益轂鼴性選終繪定集會s 的測試屬性。創(chuàng)建一個結(jié)點，并以該屬性標記，對屬性的每個值創(chuàng)建分枝，并 據(jù)此劃分樣本。 基予多種原因，決策樹分類已經(jīng)被廣泛地粥予多種數(shù)據(jù)挖掘工其中，用乎 產(chǎn)生分類