數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(講稿4---決策樹學(xué)習(xí)技術(shù))

1、1 /221 / 22第四章 決策樹（decision tree）決策樹也是歸納學(xué)習(xí)中常用的一種知識(shí)表示形式，常用于分類。同時(shí)，也是發(fā) 現(xiàn)概念描述空間的一種有效方法。決策樹的主要優(yōu)點(diǎn)是描述簡(jiǎn)單，分類速度快，特 別適合大規(guī)模的數(shù)據(jù)處理。教學(xué)目的：掌握決策樹學(xué)習(xí)的概念重點(diǎn)掌握ID3ID3學(xué)習(xí)算法以及決策樹的構(gòu)造 了解目前常用的決策樹改進(jìn)方法4.14.1概念描述空間的歸納學(xué)習(xí)歸納學(xué)習(xí)旨在從大量的經(jīng)驗(yàn)數(shù)據(jù)中歸納抽取出一般的規(guī)則和模式，因而成為知識(shí)獲取的主要手段，在專家系統(tǒng)、模式識(shí)別、圖像處理、語音識(shí)別等領(lǐng)域都有重要 應(yīng)用。歸納學(xué)習(xí)是機(jī)器學(xué)習(xí)最核心、最成熟的分支。示例數(shù)字識(shí)別應(yīng)用：假設(shè)有三類數(shù)字，即0，

2、1, 2。每類有兩個(gè)例子，每個(gè)例子有四個(gè)屬性描述，即孔數(shù)（#hole）、端點(diǎn)數(shù)（#end）、交叉點(diǎn)數(shù)（#crosS）、右上 弧數(shù)（#right-arc）。如表所示。例子國(guó)CIDSIS廉1答肚ate類1O10012C120031020041033015202215212412可歸納產(chǎn)生三類數(shù)字的如下規(guī)則：0 類：#hole=1#cross=01類：#hole=0#right-arc=02類：#end=2#right-arc=1歸納學(xué)習(xí)是符號(hào)學(xué)習(xí)中研究得最為廣泛的一種方法。思想是：給定關(guān)于某個(gè)概念的一系列已知的正例和反例，從中歸納出一個(gè)通用的概念描述。歸納學(xué)習(xí)能夠獲得新的概念，創(chuàng)立新的規(guī)則，發(fā)現(xiàn)新

3、的理論 。它的一般操作是2/222 / 22泛化和特化。泛化用來擴(kuò)展某一假設(shè)的語義信息，使其能包含更多的正例，應(yīng)用于 更多的情況；特化是泛化的相反操作，用于限制概念描述的應(yīng)用范圍。示例假設(shè)我們被要求從一副撲克牌中選擇一張牌，如果選到好牌就可以獲獎(jiǎng)。已 知前面被抽出的牌有：梅花4、梅花7、黑桃2、紅桃5和黑桃J,其中前三 張都獲獎(jiǎng)，后兩張沒有獲獎(jiǎng)。試用歸納學(xué)習(xí)幫助選擇能獲獎(jiǎng)的好牌。解：取紙牌的一組屬性：y-花色（Suit）和階V2-（ Rank）,女口：梅花4顯然，紙牌的示例空間V V就是所有牌的集合。它是由屬性 Suit和Rank所定 義的，其中，屬性Vi,V2的可觀察值集合為：Vcl u b

4、s,s p a d,edsi a m o nhdesa rt-s-梅花、黑桃、方塊、紅桃V =1,2,3,4,5,6,7,8,9,10, J,Q,K每個(gè)示例就是單張牌。設(shè)X X是一組確定屬性決定的示例空間 （如，V1 V2）; H是定義在X上的假設(shè)空 間（如, H=梅花4、梅花7、黑桃2、紅桃5和黑桃J ），也就是用X的屬性按一 定的邏輯形式定義的一組概念。Q是定義在X上的目標(biāo)概念c的示例有限集，我們 定義Q的描述空間是由H中適合Q的全部示例的假設(shè)構(gòu)成的集合。如果示例空間是有限的，且目標(biāo)概念c是H的成員。當(dāng)新的示例添加到Q中時(shí), Q描述空間將收縮，最終直到僅包含目標(biāo)概念 c,這時(shí)稱描述空間被窮

5、盡。對(duì)描述空間可以用描述圖來表示，它是一個(gè)無回路的有向圖，其中各節(jié)點(diǎn)是描述 空間的元素。如果從節(jié)點(diǎn)p到q有一條弧，當(dāng)且僅當(dāng)下面兩條性質(zhì)成立：p比q特殊；不存在節(jié)點(diǎn)r，它比p普遍，比q特殊。取PE=梅花4、梅花7、黑桃2為正例；NE=紅桃5和黑桃J 為反例。這樣對(duì)，梅化4是冃疋示例，其描述圖為ba*ba*bnbnbjTbjT黒桃2怒加反例黑桃J於 后的矗述國(guó)加石的搐述國(guó)這里，c clubs; b-black; n-num; a-any-suit 或 any-rank。圖中從左至U右表示 suit從特殊到普遍，垂直方向從下到上表示Rank從特殊到普遍；ba表示的概念為梅花4鞫腹的椅述國(guó)C3 -*

6、baf .aa 43/222 / 22（suitblaOk （Ra nkan y r a n）k,即所有黑色的牌。這時(shí)增加新的示例，如梅花7,能修剪描述空間。刪除三個(gè)涉及階是 4的概念，因?yàn)?它們不能覆蓋該肯定示例，得到新的描述圖。同理，由否定示例紅桃5可修剪掉aa和an,因?yàn)檫@兩個(gè)概念覆蓋該否定示例；肯定示例黑桃 2剪掉梅花，最后由否定示 例黑桃J將描述空間縮小到單個(gè)概念bn,即黑色數(shù)字牌。4.24.2決策樹學(xué)習(xí)決策樹是用樣本的屬性作為結(jié)點(diǎn)，用屬性的取值作為分支的樹結(jié)構(gòu)。它是利用 信息論原理對(duì)大量樣本的屬性進(jìn)行分析和歸納而產(chǎn)生的。決策樹的根結(jié)點(diǎn)是所有樣 本信息中信息量最大的屬性。中間結(jié)點(diǎn)是以

7、該結(jié)點(diǎn)為根的子樹所包含的樣本子集中 信息量最大的屬性。決策樹的葉結(jié)點(diǎn)是樣本的類別值。決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它著眼于從一組無次序、無規(guī)則 的事例中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞推方式，在決策 樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分枝，在 決策樹的葉結(jié)點(diǎn)得到結(jié)論。所以，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取 規(guī)則，整棵決策樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則。決策樹的內(nèi)部結(jié)點(diǎn)是屬性或?qū)傩约?，稱為測(cè)試屬性；葉結(jié)點(diǎn)是所要學(xué)習(xí)劃分的 類。先用訓(xùn)練實(shí)例集產(chǎn)生決策樹，然后用其對(duì)未知實(shí)例集進(jìn)行分類。對(duì)實(shí)例進(jìn)行分類時(shí)，由樹根開始對(duì)該對(duì)象的屬性逐漸測(cè)試

8、其值，并且順著分支向下走，直至到達(dá)某個(gè)葉結(jié)點(diǎn)，此葉結(jié)點(diǎn)代表的類即為該對(duì)象所處的類。例如一棵基于表1中數(shù)據(jù)的用于檢測(cè)網(wǎng)絡(luò)入侵行為的決策樹。這個(gè)決策樹，用IP端口和系統(tǒng)名稱標(biāo)示內(nèi)部結(jié)點(diǎn)，用入侵和正常表示葉結(jié)點(diǎn)， 如下圖描述。表1入侵?jǐn)?shù)據(jù)例子System nameIP PoriSystem nameCategoiyApollo yf Arte inis004020ArtemisHoimal0D4020ApolloIntrusiohIF PortNormal002210ArtemisHortnal/002210ApolloIntrusiDii000010 004020000010ArtemisNomi

9、al/(J02000010ApolloNormalWoermal決策樹可轉(zhuǎn)換成如下的規(guī)則：(C+C+表示)If (System n ame=Artemis)4/222 / 22In trusi on=false;ElseIf (IP port=002210) In trusi on=true; else if (IP port=004020)In trusi on=true;Else if (IP port=000010) In trusio n=false;根據(jù)決策樹的各種不同屬性，有以下幾種不同的決策樹：決策樹的內(nèi)結(jié)點(diǎn)的測(cè)試屬性可能是單變量的，即每個(gè)內(nèi)結(jié)點(diǎn)只包含一個(gè)屬性，也可能是多變量的，

10、即存在包含多個(gè)屬性的內(nèi)結(jié)點(diǎn)；根據(jù)測(cè)試屬性的不同屬性值的個(gè)數(shù)，可能使每個(gè)內(nèi)結(jié)點(diǎn)有兩個(gè)或多個(gè)分支。如果每個(gè)內(nèi)結(jié)點(diǎn)只有兩個(gè)分支，則稱之為二叉樹決策樹；每個(gè)屬性可能是值類型，也可能是枚舉類型；分類結(jié)果既可能是兩類，也可能是多類。如果二叉決策樹的結(jié)果只能有兩類，則稱之為布爾決策樹。對(duì)布爾決策樹可很容易以析取范式的方式表示。如下圖為 （X3 X2） （X3 X4 一xj的析取范式另外，所有的決策樹學(xué)習(xí)都有一些等價(jià)的網(wǎng)絡(luò)表示形式。如上圖的人工神經(jīng)網(wǎng) 絡(luò)與決策樹表達(dá)了同一個(gè)析取概念（3 X2） （X3 X4 XJ，所執(zhí)行的功能相同。4.34.3 CLSCLS學(xué)習(xí)算法概念學(xué)習(xí)系統(tǒng)（CLS: Concept Le

11、arning System 是1966年由Hunt等人提出的, 是早期決策樹學(xué)習(xí)算法，后來的決策樹學(xué)習(xí)算法均可視為CLS算法的改進(jìn)和更新。CLSCLS算法的主要思想是：從一個(gè)空的決策樹出發(fā)，選擇某一屬性（分類屬性） 作為測(cè)試屬性，該測(cè)試屬性對(duì)應(yīng)決策樹中的決策結(jié)點(diǎn)，根據(jù)該屬性值的不同，可將 訓(xùn)練樣本分成相應(yīng)的子集。如果該子集為空，或該子集中的樣本屬于同一類，則該 Jt示AJC A-5/222 / 22子集為葉結(jié)點(diǎn)，否則該子集對(duì)應(yīng)于決策樹的內(nèi)部結(jié)點(diǎn)，即測(cè)試結(jié)點(diǎn)。需再選擇一個(gè) 新的分類屬性對(duì)該子集進(jìn)行劃分，直至所有的子集者為空或?qū)儆谕活悶橹?。例如，假設(shè)有一組人，眼睛和頭發(fā)的顏色及所屬的人種情況如下

12、表：人員服睛碩色頭垸靈色所屬人種1黑色黒色董種人2金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色全芭混血兒7灰色黑色溫血兒8藍(lán)色黒色混血兒假設(shè)首先選擇眼睛顏色作為測(cè)試屬性，貝以該結(jié)點(diǎn)引出三個(gè)分支圖：選擇眼睛顏色作為決策屬性這三個(gè)分支將樣本集分成三個(gè)子集1，6、2，4，8和3，5, 7。但這三個(gè)子集 中的元素都不屬于同一結(jié)果類，因此它們都不是葉結(jié)點(diǎn)，需要繼續(xù)劃分，即需要添 加新的測(cè)試結(jié)點(diǎn)。女口 頭發(fā)顏色，由于頭發(fā)顏色=黑色，金色，紅色，所以從子 集中可引出三個(gè)新的分支：通過增加結(jié)點(diǎn)逐步求精，直到生成一棵能正確分類訓(xùn)練樣本的決策樹。學(xué)習(xí)算法CLS算法的步驟可描述為：令決策樹T的初

13、始狀態(tài)只含有一個(gè)樹根（X，Q），其中X是全體訓(xùn)練實(shí)例 的集合，Q是全體測(cè)試屬性的集合；若T的所有葉結(jié)點(diǎn)（X,Q）都有如下狀態(tài)：或者第一個(gè)分量 X中的訓(xùn)練6/222 / 22信源 P(Y | X) X信宿Y其中,實(shí)例都屬于同一個(gè)類，或者第二個(gè)分量Q為空，則停止執(zhí)行學(xué)習(xí)算法，學(xué) 習(xí)的結(jié)果為T ；否則，選取一個(gè)不具有步驟所述狀態(tài)的葉結(jié)點(diǎn)（X,Q）；對(duì)于Q，按照一定規(guī)則選取測(cè)試屬性b,設(shè)X被b的不同取值分為m個(gè) 不相交的子集X；仁im，從（X,Q）伸出m個(gè)分叉，每個(gè)分叉代表b的 一個(gè)不同取值，從而形成 m個(gè)新的葉結(jié)點(diǎn)（X,Q-b） , H豈m ；轉(zhuǎn)步驟。從CLS的算法描述可以看出，決策樹的構(gòu)造過程也就

14、是假設(shè)特化的過程。 但CLS 算法并沒有規(guī)定采用何種測(cè)試屬性。然而，測(cè)試屬性集的組成以及測(cè)試屬性的先后 都對(duì)決策樹的學(xué)習(xí)有著舉足輕重的影響。此外，CLS算法所能處理的學(xué)習(xí)問題不能太大。4.44.4 ID3ID3 （IterativeIterative DichotomizerDichotomizer3 3）學(xué)習(xí)算法CLSCLS算法的思路是找出最有分辨能力的屬性，把數(shù)據(jù)庫(kù)劃分為許多子集（對(duì)應(yīng) 樹的一個(gè)分枝），構(gòu)成一個(gè)分枝過程，然后對(duì)每個(gè)子集遞歸調(diào)用分枝過程，直到所有 子集包含同一類型數(shù)據(jù)。最后得到的決策樹能對(duì)新的例子進(jìn)行分類，但CLS的不足是（1） 沒給出如何選取測(cè)試屬性b；（2） 它處理的學(xué)習(xí)

15、問題不能太大。為此，Quinlan提出了著名的以屬性為分類節(jié)點(diǎn) 的ID3學(xué)習(xí)算法，他是以信息熵 的下降速度作為選取測(cè)試屬性的標(biāo)準(zhǔn)，通過窗口來形成決策樹。信息熵的下降也就是信息不確定性的下降。1 1）信息論簡(jiǎn)介信息論是由C.E.Shannon （信息論的創(chuàng)始人）1948年為解決信息傳遞（通信）過 程問題而提出的以數(shù)學(xué)的方法來度量并研究信息 的理論，也稱為統(tǒng)計(jì)通信理論。他把一個(gè)傳遞信息的系統(tǒng) 視為，由發(fā)送端（信源）、接收端（信宿）和連接兩者的通道（信道）三者組成。P（Y |X）稱為信道的傳輸概率或轉(zhuǎn)移概率，它反映信道的輸入與輸出關(guān)系7/222 / 22用矩陣來表示，稱為轉(zhuǎn)移概率矩陣。P(Vi|Ui

16、) P(V2|uJP(Vq |Ui)P(Vi|U2) PW2IU2) P(Vq |U2)P(Y|X)=r qP(Vi |Ur) P(V2|Ur) P(Vq|U_q這里， P(Vj |uj =1, i =1,2, ,r。j 4從此通信模型可看出，在進(jìn)行實(shí)際的通信之前，收信者(信宿)不可能確切了 解信源究竟會(huì)發(fā)什么樣的具體信息，也不可能判斷信源會(huì)處于什么樣的狀態(tài)。這種 情形就稱為信宿對(duì)于信源狀態(tài)具有不確定性，而且這種不確定性是存在于通信之前 的，因此又叫做 先驗(yàn)不確定性。在進(jìn)行了通信之后，信宿收到了信源發(fā)來的信息，這種先驗(yàn)不確定性才會(huì)被消 除或者被減少。如果干擾很小，不會(huì)對(duì)傳遞的信息產(chǎn)生任何可察覺

17、影響，信源發(fā)出 的信息能夠被信宿全部收到，在這種情況下，信宿的先驗(yàn)不確定性就會(huì)被完全消除。 但是，在一般情況下，干擾總會(huì)對(duì)信源發(fā)出的信息造成某種破壞，使信宿收到的信 息不完全。因此，先驗(yàn)不確定性不能全部被消除，只能部分地消除。換句話說，通 信結(jié)束之后，信宿仍然具有一定程度的不確定性。這就是后驗(yàn)不確定性。顯然，后驗(yàn)不確定性總要小于先驗(yàn)不確定性，不可能大于先驗(yàn)不確定性。(1)如果后驗(yàn)不確定性的大小正好等于先驗(yàn)不確定性的大小，這就表示信宿 根本沒有收到信息。(2)如果后驗(yàn)不確定性的大小等于零，這就表示作宿收到了全部信息。可見，信息是用來消除(隨機(jī))不確定性的度量。信息量的大小，由所消除的不確定性的大

18、小來計(jì)量。下面介紹幾個(gè)概念：信息(符號(hào))Ui ( i =1,2,，r )的發(fā)生概率p(Ui)組成信源數(shù)學(xué)模型(樣本空間 或概率空間)：5u2 urX,P=12rILP(Ul) P(U2)P(Ur)自信息量：消息Ui發(fā)生后所含有的信息量。即在收到Ui事件之前，收信者對(duì) 8/222 / 22信源發(fā)出Ui的不確定性，定義為信號(hào)符號(hào)Ui的自信息量l(Ui)。即l(Ui) =log2log2 P(Ui)P(u其中，P(Ui)為信源發(fā)出Ui事件的概率； 信息熵：自信息的數(shù)學(xué)期望。因?yàn)樽孕畔⒘恐荒芊从撤?hào)收到前的不確定性， 而信息熵可以用來度量整個(gè)信源 X整體的不確定性，即信源發(fā)出信息前的平 均不確定性。定

19、義如下：rE(X)二 P(Ui)l(Ui) P(U2)l(U2)P(Ur)l(Ur)=7. P (Ui ) l 0 g P(U i )i 4其中，r為信源X所有可能的符號(hào)數(shù)Ui,U2/ ,Ur，即用信源每發(fā)一個(gè)符號(hào)所 提供的平均自信息量來定義信息熵。上式中， 對(duì)數(shù)底數(shù)b可為任何正數(shù)，不 同的取值對(duì)應(yīng)熵的不同單位 ，但通常取b=2 ;并規(guī)定：當(dāng)p(uj=o時(shí),P(Ui)log b P(uJ =0。當(dāng)對(duì)數(shù)的底為2時(shí)，l(u的單位為比特(bit)；當(dāng)對(duì)數(shù)的底為e時(shí)，l(uj的單位為奈特(nat);當(dāng)對(duì)數(shù)的底為10時(shí)，l(u)的單位為哈特(hart)；1奈特=1.44比特；1哈特=3.32比特。E(X

20、)的性質(zhì)如下：E(X) =0時(shí)，說明只存在著唯一的可能性，不存在不確定性；如果n種可能的發(fā)生都具有相同的概率，即對(duì)所有的ui，有P(Ui) =1/n，則E(X)達(dá)到最大值log2n，說明系統(tǒng)的不確定性最大；P(ui)互相越接近，E(X)就越大；P(Ui)相差大，則E(X)就小。如果信道中無干擾(噪聲)，信道輸出符號(hào)與輸入符號(hào)一一對(duì)應(yīng)，那么接收到傳 送過來的符號(hào)后，就消除了對(duì)發(fā)送符號(hào)的先驗(yàn)不確定性。后驗(yàn)熵一般信道中有干擾存在，信宿接收到符號(hào) V后，對(duì)信源發(fā)出的是什么符號(hào)仍有 不確定性。對(duì)此如何度量？當(dāng)沒有接收到輸出符號(hào)V時(shí)，已知發(fā)出符號(hào)U的概率分布P(U)，而接收到輸出 9/222 / 22符號(hào)

21、V二Vj后，輸入符號(hào)的概率分布發(fā)生了變化，變成了后驗(yàn)概率分布P(U |Vj)。10/222 / 22n=hil| lLCJX)如果a為X中取有限個(gè)不同值$42,，am的屬性，樣本集X劃分為m個(gè)不同的子E(X |C- C2IH C,n那么，接收到輸出符號(hào)V = Vj后，關(guān)于U的平均不確定性為:E(U |Vj)八 P(Ui |Vj)log-iP(Ui |Vj)這就是接收到輸出符號(hào)Vj后關(guān)于U的后驗(yàn)熵。即后驗(yàn)熵是當(dāng)信道接收到輸出符號(hào)Vj 后，關(guān)于輸入符號(hào)U的信息度量。條件熵后驗(yàn)熵在輸出符號(hào)集V的范圍內(nèi)是個(gè)隨機(jī)量，所以對(duì)于后驗(yàn)熵在輸出符號(hào)集V中求期望，得到條件熵：E(U |V)八 P(Vj)E(U |

22、Vj)j1八 P(Vj) P(Ui |Vj)log2-(*)j iP(Ui |Vj)這個(gè)條件熵稱為稱為信道 疑義度。它表示在輸出端收到全部輸出符號(hào) V后，對(duì)于輸 入端的符號(hào)集U尚存在的不確定性(存在疑義)。對(duì)U集尚存在的不確定性是由于 干擾(噪聲)引起的，如果是一一對(duì)應(yīng)，那么接收到符號(hào)集 V后，對(duì)U集的不確定 性完全消除，則信道疑義度E(U |V) =0。在決策分類中，假設(shè)X是訓(xùn)練樣本集，|X|是訓(xùn)練樣本數(shù)；樣本劃分為n個(gè)不同 的類C-,C2,Cn，則任意樣本X屬于類Ci的概率為所以，樣本X的平均信息熵為集X-,X2，Xm，則由式(* )知，由屬性a劃分的決策樹分類的平均條件熵為mE(X |a

23、) = p(Xj)E(Xj |a)j丘mn=-S p(Xj)遲 p(Ci |Xj)log p(Ci |Xj)j =1i =1若設(shè)|Xij |表示為子集Xj中類Ci的樣本數(shù)，貝U P(Ci|Xj)二1| x |11 / 2210 / 22 信息增益：一般E(X|a)=E(X)，樣本分類的熵值發(fā)生了變化，即屬性 a對(duì)于分類提供了信息，熵的變化量稱為屬性 a對(duì)于分類的信息增益Gain(a)，則Gai(a) =E(X)E(X|a) _0(證明略)從上式知，測(cè)試屬性將減少?zèng)Q策數(shù)分類的不確定程度。2 2)ID3ID3學(xué)習(xí)算法QuinlanQuinlan的ID3ID3算法就是選擇使Gain(a)最大的屬性作

24、為測(cè)試屬性，即選擇使 E(X|a)最小的屬性a a作為測(cè)試屬性。此外，ID3ID3中還引入了窗口方法進(jìn)行增量學(xué)習(xí) 來解決實(shí)例過大問題。具體算法為： 選出整個(gè)訓(xùn)練實(shí)例集X的規(guī)模為W的隨機(jī)子集Xi ；( W稱為窗口規(guī)模，子 集稱為窗口) 以使得式(* )的值最小為標(biāo)準(zhǔn)，選取每次的測(cè)試屬性，形成當(dāng)前窗口的 決策樹； 順序掃描所有訓(xùn)練實(shí)例，找出當(dāng)前的決策樹的例外，如果沒有例外，則 訓(xùn)練結(jié)束； 組合當(dāng)前窗口的一些訓(xùn)練實(shí)例與某些在中找到的例外，形成新的窗口，轉(zhuǎn)。示例表4.1給出了一個(gè)可能帶有噪聲的數(shù)據(jù)集合。它有4個(gè)屬性：Outlook,Temperature Humidity和windy。它被分為兩類：P

25、和N分別表示正例和反 例。試構(gòu)造決策樹將數(shù)據(jù)進(jìn)行分類。解：因?yàn)槌跏紩r(shí)刻屬于P類和N類的實(shí)例個(gè)數(shù)均為12個(gè)，所以初始時(shí)刻的熵值 為：H(X)12log12-12log12=124242424如果選取Outlook屬性作為測(cè)試屬性，則由式(* )有H (X | Outlook ) ( log _ _ log)_( log _ _ log )24999924_Z(_| o g_)= 0.5 5 2 82477H (X84444114477| Temp )(loglog )(loglog)248888241111111154411(l o gIo 曠)-0.673924555512 / 2211 /

26、22可以看出，H(XOutlook)最小，即有關(guān)Outlook的信息對(duì)于分類有最大的幫助，提 供最大的信息量，即I(X;Outlook)最大。所以選擇Outlook屬性作為測(cè)試屬性，就可 將訓(xùn)練實(shí)例集分為三個(gè)子集，生成三個(gè)葉結(jié)點(diǎn)，對(duì)每個(gè)葉點(diǎn)依次利用上面的過程, 則最終生成如下的決策樹:3 3)基于ID3ID3的信息增益的決策樹構(gòu)造算法ID3算法有著廣泛的應(yīng)用，其中較為著名的有C4.5、C5.0系統(tǒng)。C4.5的新功能是它能將決策樹轉(zhuǎn)換為等價(jià)的規(guī)則表示，并且 解決了連續(xù)取值的學(xué)習(xí)問題。12 (-4log 48812 -)+(448 8 log)=0.H (X | Humi )=24121212lo

27、g122412log1212 1284 ,455、 6 ,3333、-log)+ =( -lo-)H (X|Windy )24(-888log8246log66 6/ 5,5、+10( -55-log )=12410log101010表4.1樣本數(shù)據(jù)集屬性O(shè)utbokTemperatuieHumidityVftndy類1OicasiHotHighNotN2gicsstHotHighVeryN3mastHotHighMediumN4SunnyHotMghNatF5SunnyHotHighMediumP15RainMildH妙NotN1RjainMildHighNtdiumH8RainHotNbn

28、mlNotP9RixiCoolNoanalMediumN10RainHotNormalVeryN11SurmyCoolMorml.VeryP12SurmyGoodNomual.MediumF13Ove nc fistWdHighNotN14OwitastMildHighMediumN15ucastCoolNormalNotF16OitastCoolMcmnalMediumF17RainMildNomialNoti-I1SWdNormalMediumN19OVE ivastMildWomiAlMediumF206 icestMildNormlUetyP21SurmyMildHighVeiyP22

29、SunnyMildHighMediumP23SunnyHotNoiimalNotP24RainMildHighVeiyN918313 / 2212 / 22如果屬性A作為決策樹的根且A具有v個(gè)值，則A可將E分成v個(gè)子集ni個(gè)反例，那么Ei所需的期望信息是設(shè)樣本集E共有C類樣本，每類樣本數(shù)為以屬性A作為決策樹的根,A具有v個(gè)值可將E分成v個(gè)子集E-E2,Ev。假設(shè)Ei中含有j類樣本的個(gè)數(shù)為Pij ， j - 1,2, c 0則子集Ei的信息量為Ell簡(jiǎn)log 2 Pij(* )(1)(1) ID3ID3算法的基本原理設(shè)E=Fi F2Fn是n維有限向量空間，F(xiàn)j是有限離散符號(hào)集，E中的每 一元素e

30、 =(vV2,，vj稱為例子，Vj Fj, j =1,2，n。設(shè)PE和NE是E的兩個(gè)例 子集，分別稱為正例集和反例集。| PE |= p,| NE |二n，則ID3基于如下兩種假設(shè)： 在向量空間E上的一棵正確決策樹，對(duì)任意例子的分類概率同E中正例、反例的概率一致； 一棵決策樹對(duì)一例子做出正確分類判別所需的信息為i(p,n) p log2 p n p + n p + nEI,E2, ,Ev。假設(shè)Ei中含有Pi個(gè)正例和 1( Pi, nJ，以屬性A為根分類所需的期望熵為v p nE(A)日 I ( Pi, nJ y p + n則A根的信息增益為gai(A) =l(p,n) -E(A)ID3ID3的

31、思想是選擇gain(A)最大(即E(A)最小)的屬性A作為根結(jié)點(diǎn)。其方法 可推廣到多類情況。(上面只研究正、反兩類)cPi，i h,2, ,c，即 | E |八 pi。若i 二以A為根分類的信息熵為v | Ei |E(A): I(Ei)i | E |所以，選擇屬性A*使E(A)最小。(2)(2) 建樹的算法步驟 對(duì)于任意的選擇屬性A,假設(shè)A有v個(gè)屬性值，對(duì)應(yīng)的概率分別為p, p2,pv14 / 2213 / 22I（A10）151533log 2log 22020 2020202220-0.792815151515115log 2丄=3.11552 1l （中）-bog 21 - ？ log

32、2333送噸心681（優(yōu)）=0所以,153E（A320 丨（良）20 1 仲）1（優(yōu)）=2.5016220以屬性A擴(kuò)展，生成v個(gè)子結(jié)點(diǎn)EI，E2,，Ev , Ei是屬性A取i個(gè)值時(shí)，按照最小的信息熵原理選擇的A的后繼屬性，分別對(duì)應(yīng)的信息熵為I（EI）,I（E2）, ,l（Ev）； 根據(jù)公式（* ）計(jì)算E（A）； 選擇A*使E（A*）最小，將A*作為根屬性； 利用步驟的計(jì)算結(jié)果，建立結(jié)點(diǎn) A*的后繼結(jié)點(diǎn)EE2,EV; 對(duì)所有的Ei，若為葉結(jié)點(diǎn)，則停止擴(kuò)展此結(jié)點(diǎn)。否則遞歸執(zhí)行的過程。（3 3）應(yīng)用實(shí)例決策樹的構(gòu)造主要分為兩個(gè)階段：建樹階段和調(diào)整階段。例如下面以某課堂教學(xué)評(píng)估數(shù)據(jù)庫(kù)中的數(shù)據(jù)挖掘和知識(shí)

33、發(fā)現(xiàn)為例。該課堂教學(xué)評(píng)估指標(biāo)體系表共分為若干項(xiàng)，經(jīng)研究可歸納為：教學(xué)態(tài)度（A6 ）、教學(xué)內(nèi)容（A7 ）、教學(xué)方法（A8 ）、教學(xué)效果（A9 ）、評(píng)價(jià)（A.0）共五項(xiàng)，實(shí)際數(shù)據(jù) 見表1所示由于屬性初值為連續(xù)值，需進(jìn)行離散化處理。將屬性劃分為若干個(gè)區(qū)段，C1:95100 分、C2: 8094 分、C3: 7079 分、C4: 6069 分、C5: 60 分。見表 2 所示。解：去掉屬性A1。因?yàn)锳1對(duì)于結(jié)論屬性而言，無互信息，亦稱無信息增益，即gain （AJ = 0。計(jì)算測(cè)試集的全部信息量:然后計(jì)算各結(jié)點(diǎn)的信息量I （Ei），如A6gain（A6）=1（幾0）-E（A6）二1.7053415 /

34、 2214 / 22AAAAA血192.692 6913392 5592.6287.0586.27SOP85 0587.05390.4592.77S6.2E9 9SO 45438.396.9397.0397.1593.3591491 S384,9788 8591.1695.6556 13S5 3395 9595.65pF59.337.23342S3 1S9 3TS3.2580.67763SO392.S591.4EE 28992 851084.55S4-4779 3EQ 554 65u93393.3791.0790.393.312Pl 0591.7785.686.1591.051387 .S58

35、889.17 87 287 6 5149019590.9386.27 88 9590.951595.296.0739(5392 695 21691.38S.63S3 9E7S591317S7.15S7 534.17873587 151893.0590 486.63E7 1593 05197E.567.377.7573.52087.4P2.4779 132.7即4AAAAAAr1C2C2C2C22C2C2C2C2良C2C2C2C2良4ClClClCl憂5C2C2C2C2罠6ClClClCl憂702C2C3C3良s02C3C3C3中9C2C2C2C2良10C3C3C3C3中11C2C2C20212

36、C2C2C2C2良13C2C2C2C2艮.14C2C2C2C2良15ClClC2C2罠C2C2C2C217C2C2C2C2良12C2C2C2C2良19C3C3C3C3中20C2C2C3C3同理，可計(jì)算出ASA8,A信息熵:gai n( A7) =0.65876, gain( As)= 0.411, gain( A9) = 0.5 50 1故取A7為根屬性。同樣對(duì)Ci這一分支繼續(xù)使用ID3 方法進(jìn)一步劃分，可得到如圖所示的決策樹。該決策樹完全概括了教師教學(xué)評(píng)估的三個(gè)等級(jí)的 20個(gè)記錄。從圖中可以看出：教學(xué)A7是一重要指標(biāo)。表1或表2中隱藏的知識(shí)有如下幾種情況:規(guī)則1：IF(A7=C2) THEN

37、(良)規(guī)則2：IF(A7 =C3) THEN仲）規(guī)則3：IF(A7 = GA9 = C1)THEN(優(yōu))規(guī)則4：IF(A7 = G a A9 = C 2)THEN(良)即，如果教學(xué)內(nèi)容為良，則課堂教學(xué)質(zhì)量評(píng)價(jià)等級(jí)一定為良；如果教學(xué)內(nèi)容為中, 則課堂教學(xué)質(zhì)量評(píng)價(jià)等級(jí)一定為中；如果教學(xué)內(nèi)容和教學(xué)效果均為優(yōu)，則課堂教學(xué) 質(zhì)量評(píng)價(jià)等級(jí)一定為優(yōu)；如果教學(xué)內(nèi)容為優(yōu)而教學(xué)效果為良，則課堂教學(xué)質(zhì)量評(píng)價(jià) 等級(jí)為良。因此，從這些規(guī)則中，可以歸納出一條重要的知識(shí)，就是：教學(xué)內(nèi)容組 織好的老師，其課堂教學(xué)質(zhì)量的綜合評(píng)價(jià)成績(jī)較好。4.54.5 C4.5C4.5 方法表仝16 / 2215 / 22（1）類別Cj的發(fā)生概

38、率:心)旦j |T|freq(Cj,T)|T|（2）屬性V =Vj的發(fā)生概率:/、|T | P（Vi八帀P(5 |Vi|j，I Ti Ik=-j Wfreq(Cj ,T)log 2(freq(C,T)=inf o(T)ID3算法在數(shù)據(jù)挖掘中占有非常重要的地位。 但是在應(yīng)用中，ID3ID3算法存在不能 夠處理連續(xù)屬性、計(jì)算信息增益時(shí)偏向于選擇取值較多的屬性等不足。C4.5是在ID3 基礎(chǔ)上發(fā)展起來的決策樹生成算法， 由J.R.Quinlan在1993年提出。C4.5克服了 ID3 在應(yīng)用中存在的不足，主要體現(xiàn)在以下幾個(gè)方面：（1）用信息增益率來選擇屬性，它克服了信息增益選擇屬性時(shí)偏向于選擇取值較

39、多的屬性的不足；（2）在樹構(gòu)造過程中或者構(gòu)造完成之后，進(jìn)行剪枝；（3）能夠完成對(duì)連續(xù)屬性的離散化處理；（4）能夠?qū)τ诓煌暾麛?shù)據(jù)進(jìn)行處理；（5）C4.5采用的知識(shí)表示形式為決策樹，并最終可以形成產(chǎn)生式規(guī)則。4.5.14.5.1構(gòu)造決策樹設(shè)T為數(shù)據(jù)集，類別集合為G,C2,，Cd，選擇一個(gè)屬性V把T分為多個(gè)子集。設(shè)V有互不重合的n個(gè)值VV2，,vj，則T被分為n個(gè)子集衛(wèi),，Tn，這里中 的所有實(shí)例的取值均為Vi。令|T|為數(shù)據(jù)集T的例子數(shù)，|T |為V的例子數(shù)，|Cj卜freq（Cj,T）為Cj類的例子數(shù)，|CjV|為V =Vi例子中，具有Cj類別的例子數(shù)。則有：（3）屬性V二w的例子中，具有類別C

40、j的條件概率:Quinlan在ID3中使用信息論中的信息增益（Gain）來選擇屬性，而C4.5C4.5采用屬 性的信息增益率（GainGain RatioRatio）來選擇屬性。1 1、類別的信息熵H(C) p(Cj)log2(p(Cj) logC)jj |T |T |2 2、類別條件熵17 / 2216 / 22j |T|Ti|92|CjV|H(V)=二iP(vi)log2(p(vj)送號(hào)i二 |T |og(#)=spl _t nO(V)按照屬性V把集合T分割，分割后的類別條件熵為:H(C|V)p(Vj) p(Cj |vJlogp(Cj |vjjio(TJ = inf Ov(T)3 3、信息

41、增益，即互信息I (C,V)二H(C)-H(C|V )=in 0(T) - in 0V(T) = g a i(V)4 4、屬性V V的信息熵5 5、信息增益率gain _ratio = I (C,V) / H (V) = gain(V)/ split _inf o(V)C4.5對(duì)ID3改進(jìn)是用信息增益率來選擇屬性。理論和實(shí)驗(yàn)表明，采用“信息增益率” （C4.5）比采用“信息增益” （ID3）更好, 主要是克服了 ID3方法選擇偏向于取值多的屬性的不足。4.5.24.5.2連續(xù)屬性的處理在ID3中沒有處理連續(xù)屬性的功能。在 C4.5中，設(shè)在集合T中，連續(xù)屬性A的取值為w,v2,，vm，則任何在v

42、i和vi 1之間的任意取值都可以把實(shí)例集合分為兩部分T1 =t| A Zi和Tt | A vi可以看到，一共有m-1種分割情況。對(duì)屬性A的m-1種分割的任意一種情況，作為該屬性的兩個(gè)離散取值，重新構(gòu) 造該屬性的離散值，再按照上述公式計(jì)算每種分割所對(duì)應(yīng)的信息增益率 gai _ rati（vi），在m-1種分割中，選擇最大增益率的分割作為屬性A的分枝：T h r e s h W)d= vk其中，ga in _ ratio (vQ二max gai n_ ratio (vj，則連續(xù)屬性A可以分割為:18 / 2217 / 224.5.34.5.3決策樹剪枝由于噪聲和隨機(jī)因素的影響，決策樹一般會(huì)很復(fù)雜。

43、因此，需要進(jìn)行剪枝操作。1 1什么時(shí)候剪枝？剪枝操作有兩種策略：（1）在樹生成過程中判斷是否繼續(xù)擴(kuò)展決策樹。若停止擴(kuò)展，則相當(dāng)于剪去該結(jié)點(diǎn)以下的分枝；（2） 對(duì)于生成好的樹剪去某些結(jié)點(diǎn)和分枝。C 4 .5采用的是第二種方法。 剪枝之后的決策樹的葉結(jié)點(diǎn)不再只包含一類實(shí)例。結(jié)點(diǎn)有一個(gè)分布描述，即該葉結(jié)點(diǎn)屬于某類的概率。2 2、基于誤差的剪枝決策樹的剪枝通常是用葉結(jié)點(diǎn)替代一個(gè)或者多個(gè)子樹，然后選擇出現(xiàn)概率最高 的類作為該結(jié)點(diǎn)的類別。在 C4.5中，還允許用其中的樹枝來替代子樹。如果使用葉結(jié)點(diǎn)或者樹枝代替原來的子樹之后，誤差率若能夠下降，則就使用 此葉結(jié)點(diǎn)或者樹枝代替原來的子樹。3 3、 誤差率的判斷

44、設(shè)一個(gè)葉結(jié)點(diǎn)覆蓋N個(gè)實(shí)例，其中E個(gè)為錯(cuò)誤的。對(duì)于具有信任度 CF的實(shí)例, 計(jì)算一個(gè)2項(xiàng)分布，UCF（E,N），該2項(xiàng)分布，即實(shí)例的誤判概率，那么N個(gè)實(shí)例判 斷錯(cuò)誤的數(shù)目為N UCF（E,N）。子樹的錯(cuò)誤數(shù)目為所有葉結(jié)點(diǎn)的總和。如：注：（）中為覆蓋的實(shí)例數(shù)目設(shè)CF=0.25,貝U U該子數(shù)的實(shí)例判斷錯(cuò)誤數(shù)目為:19 / 2218 / 226 U 0.25 (0,6)9 U 0.25 (0,9)1 U 0.25 (0,1)=6 0.2069 0.143 1 0.750 二 3.273若以一個(gè)結(jié)點(diǎn)C1代替該子樹，則16個(gè)實(shí)例中有一個(gè)錯(cuò)誤（C3）,誤判實(shí)例數(shù)目為16xU0.25（1,16） =16 x

45、0.157=2.51 2由于判斷錯(cuò)誤數(shù)目小于上述子樹，則以該葉結(jié)點(diǎn)代替子樹。4.5.44.5.4從決策樹抽取規(guī)則在C4.5中，從決策樹抽取規(guī)則需要兩個(gè)步驟：獲得簡(jiǎn)單規(guī)則、精簡(jiǎn)規(guī)則屬性。1 1獲得簡(jiǎn)單規(guī)則對(duì)于已生成的決策樹，可以直接從中獲得規(guī)則。從根到葉的每一條路徑都可以是 一條規(guī)則。例如，下面的決策樹中可以得到規(guī)則決策樹：F =0J = 0: c I a SDsX = 0: c l a 0s J = 1K =1: cl a Ss* F =1G =1: cl aSsJ = 0: c l a S0sG=0K=0:clas）sJ =1*5 = 1: c l a1a規(guī)則：if F =1,G =0, J

46、 =1, K =1 the nclass2 2、精簡(jiǎn)規(guī)則屬性在上述獲得的簡(jiǎn)單規(guī)則中，可能包含了許多無關(guān)的屬性。在上面的規(guī)則中，條件 F和G的取值對(duì)于結(jié)論沒有任何影響。在不影響規(guī)則的預(yù)測(cè)效果的情況下，可以刪 除一些不必要的條件。設(shè)規(guī)則的形式為R：If A the n class C精簡(jiǎn)之后的規(guī)則為R:If A_ then class C其中，A是從A中刪除條件之后的形式 4.64.6決策樹的改進(jìn)算法20 / 2219 / 22E(X,a)l(X,a)V(X,a)|a 二 a)(1)(1) 二叉樹算法Kononenko等人認(rèn)為Quinlan的熵函數(shù)并不理想，有偏向于取值較多的屬性的毛 病。為了克服

47、這個(gè)毛病，Kononenko等人建議限制決策樹為二叉樹，使得取值多的 屬性與取值少的屬性有同等的機(jī)會(huì)。此法已在 ASSISTANT系統(tǒng)中實(shí)現(xiàn)。改進(jìn)思想和缺點(diǎn)見知識(shí)發(fā)現(xiàn)，史忠植著，清華大學(xué)出版社，2002P28-29(2)(2) 按信息比值進(jìn)行估計(jì)的方法由于每個(gè)實(shí)例關(guān)于屬性a的取值，需要做試驗(yàn)，計(jì)算等，這是需要付出一定代 價(jià)的。設(shè)屬性 a取值印，玄2,，它們擁有的實(shí)例個(gè)數(shù)分別為n?,m，且ka ni二n，其中n為訓(xùn)練實(shí)例屬于屬性a的總數(shù)。Qui nlan利用屬性a的熵值V(X,a)i 4來定義為了獲取實(shí)例關(guān)于屬性 a的取值所需要付出的代價(jià)：；niniV(X,a)-logy n n在屬性a提供相同

48、的信息量I(X,a)的同時(shí)，V(X,a)的取值越小越好。Qui nlan定義 了另一種測(cè)試屬性選取標(biāo)準(zhǔn)：即選取使得E(X,a)最大的屬性a作為測(cè)試屬性。優(yōu)點(diǎn)：能有效克服偏向取值多的屬性的毛病。缺點(diǎn)：更偏向于選擇對(duì)統(tǒng)一屬性值取值比較集中的屬性(即熵值最小的屬性)，而并不一定是對(duì)分類貢獻(xiàn)最大最重要的屬性。另外，當(dāng)屬性a只有一個(gè)取值時(shí)，V(X,a) =0，則 E(X,a)沒意義。(3)(3) 按分類信息估值Cendrowska根據(jù)屬性為實(shí)例分類提供了多少有用信息來選取測(cè)試屬性。將訓(xùn)練 實(shí)例分為l類G,C2, ,Cl。設(shè)屬性a的取值ag,ak，取其中所有|C |=0類，設(shè)有m個(gè)，定義:F(X,a)二C

49、endrowska認(rèn)為，應(yīng)選取使得F(X,a)最大的屬性a作為測(cè)試屬性。(4)(4) 按劃分距離估值的方法21 / 2220 / 22PC i j)logPC i 1 j)PG i)De Mantaras建議利用劃分距離的辦法來選擇測(cè)試屬性。設(shè)待分類屬性分別屬于I 個(gè)不同的類Ci,C2,C|，如果有一種劃分方法能夠把X 一下分為I個(gè)子集 Xi,X2，X|，其中每個(gè)Xi中的實(shí)例恰好屬于Ci類，這稱之為理想劃分。另一方面， 如果根據(jù)某個(gè)屬性的各個(gè)可能取值把 X分為子集，這也是一個(gè)劃分。如果能夠在兩 個(gè)劃分之間定義一種距離，則可以在由各個(gè)屬性定義的劃分當(dāng)中選擇離理想劃分最 近的那一個(gè)，將此屬性定為當(dāng)前的測(cè)試屬性。De Ma ntaras定義的距離也是以信息和熵為基礎(chǔ)的。將H（X,C）簡(jiǎn)記為H（C）。設(shè)：一、宀，:*表示X的某種劃分，貝U其信息熵 為mH（：）-八 p（： i）logo（： i）i=1設(shè)二】