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

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

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

3、的理論 。它的一般操作是2/222 / 22泛化和特化。泛化用來擴展某一假設(shè)的語義信息，使其能包含更多的正例，應用于 更多的情況；特化是泛化的相反操作，用于限制概念描述的應用范圍。示例假設(shè)我們被要求從一副撲克牌中選擇一張牌，如果選到好牌就可以獲獎。已 知前面被抽出的牌有：梅花4、梅花7、黑桃2、紅桃5和黑桃J,其中前三 張都獲獎，后兩張沒有獲獎。試用歸納學習幫助選擇能獲獎的好牌。解：取紙牌的一組屬性：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每個示例就是單張牌。設(shè)X X是一組確定屬性決定的示例空間 （如，V1 V2）; H是定義在X上的假設(shè)空 間（如, H=梅花4、梅花7、黑桃2、紅桃5和黑桃J ），也就是用X的屬性按一 定的邏輯形式定義的一組概念。Q是定義在X上的目標概念c的示例有限集，我們 定義Q的描述空間是由H中適合Q的全部示例的假設(shè)構(gòu)成的集合。如果示例空間是有限的，且目標概念c是H的成員。當新的示例添加到Q中時, Q描述空間將收縮，最終直到僅包含目標概念 c,這時稱描述空間被窮

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

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

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

8、其值，并且順著分支向下走，直至到達某個葉結(jié)點，此葉結(jié)點代表的類即為該對象所處的類。例如一棵基于表1中數(shù)據(jù)的用于檢測網(wǎng)絡(luò)入侵行為的決策樹。這個決策樹，用IP端口和系統(tǒng)名稱標示內(nèi)部結(jié)點，用入侵和正常表示葉結(jié)點， 如下圖描述。表1入侵數(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é)點的測試屬性可能是單變量的，即每個內(nèi)結(jié)點只包含一個屬性，也可能是多變量的，

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

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

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

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

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

15、問題不能太大。為此，Quinlan提出了著名的以屬性為分類節(jié)點 的ID3學習算法，他是以信息熵 的下降速度作為選取測試屬性的標準，通過窗口來形成決策樹。信息熵的下降也就是信息不確定性的下降。1 1）信息論簡介信息論是由C.E.Shannon （信息論的創(chuàng)始人）1948年為解決信息傳遞（通信）過 程問題而提出的以數(shù)學的方法來度量并研究信息 的理論，也稱為統(tǒng)計通信理論。他把一個傳遞信息的系統(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從此通信模型可看出，在進行實際的通信之前，收信者(信宿)不可能確切了 解信源究竟會發(fā)什么樣的具體信息，也不可能判斷信源會處于什么樣的狀態(tài)。這種 情形就稱為信宿對于信源狀態(tài)具有不確定性，而且這種不確定性是存在于通信之前 的，因此又叫做 先驗不確定性。在進行了通信之后，信宿收到了信源發(fā)來的信息，這種先驗不確定性才會被消 除或者被減少。如果干擾很小，不會對傳遞的信息產(chǎn)生任何可察覺

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

18、小來計量。下面介紹幾個概念：信息(符號)Ui ( i =1,2,，r )的發(fā)生概率p(Ui)組成信源數(shù)學模型(樣本空間 或概率空間)：5u2 urX,P=12rILP(Ul) P(U2)P(Ur)自信息量：消息Ui發(fā)生后所含有的信息量。即在收到Ui事件之前，收信者對 8/222 / 22信源發(fā)出Ui的不確定性，定義為信號符號Ui的自信息量l(Ui)。即l(Ui) =log2log2 P(Ui)P(u其中，P(Ui)為信源發(fā)出Ui事件的概率； 信息熵：自信息的數(shù)學期望。因為自信息量只能反映符號收到前的不確定性， 而信息熵可以用來度量整個信源 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所有可能的符號數(shù)Ui,U2/ ,Ur，即用信源每發(fā)一個符號所 提供的平均自信息量來定義信息熵。上式中， 對數(shù)底數(shù)b可為任何正數(shù)，不 同的取值對應熵的不同單位 ，但通常取b=2 ;并規(guī)定：當p(uj=o時,P(Ui)log b P(uJ =0。當對數(shù)的底為2時，l(u的單位為比特(bit)；當對數(shù)的底為e時，l(uj的單位為奈特(nat);當對數(shù)的底為10時，l(u)的單位為哈特(hart)；1奈特=1.44比特；1哈特=3.32比特。E(X

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

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

22、Vj)j1八 P(Vj) P(Ui |Vj)log2-(*)j iP(Ui |Vj)這個條件熵稱為稱為信道 疑義度。它表示在輸出端收到全部輸出符號 V后，對于輸 入端的符號集U尚存在的不確定性(存在疑義)。對U集尚存在的不確定性是由于 干擾(噪聲)引起的，如果是一一對應，那么接收到符號集 V后，對U集的不確定 性完全消除，則信道疑義度E(U |V) =0。在決策分類中，假設(shè)X是訓練樣本集，|X|是訓練樣本數(shù)；樣本劃分為n個不同 的類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對于分類提供了信息，熵的變化量稱為屬性 a對于分類的信息增益Gain(a)，則Gai(a) =E(X)E(X|a) _0(證明略)從上式知，測試屬性將減少決策數(shù)分類的不確定程度。2 2)ID3ID3學習算法QuinlanQuinlan的ID3ID3算法就是選擇使Gain(a)最大的屬性作

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

25、和N分別表示正例和反 例。試構(gòu)造決策樹將數(shù)據(jù)進行分類。解：因為初始時刻屬于P類和N類的實例個數(shù)均為12個，所以初始時刻的熵值 為：H(X)12log12-12log12=124242424如果選取Outlook屬性作為測試屬性，則由式(* )有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的信息對于分類有最大的幫助，提 供最大的信息量，即I(X;Outlook)最大。所以選擇Outlook屬性作為測試屬性，就可 將訓練實例集分為三個子集，生成三個葉結(jié)點，對每個葉點依次利用上面的過程, 則最終生成如下的決策樹:3 3)基于ID3ID3的信息增益的決策樹構(gòu)造算法ID3算法有著廣泛的應用，其中較為著名的有C4.5、C5.0系統(tǒng)。C4.5的新功能是它能將決策樹轉(zhuǎn)換為等價的規(guī)則表示，并且 解決了連續(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個值，則A可將E分成v個子集ni個反例，那么Ei所需的期望信息是設(shè)樣本集E共有C類樣本，每類樣本數(shù)為以屬性A作為決策樹的根,A具有v個值可將E分成v個子集E-E2,Ev。假設(shè)Ei中含有j類樣本的個數(shù)為Pij ， j - 1,2, c 0則子集Ei的信息量為Ell簡log 2 Pij(* )(1)(1) ID3ID3算法的基本原理設(shè)E=Fi F2Fn是n維有限向量空間，F(xiàn)j是有限離散符號集，E中的每 一元素e

30、 =(vV2,，vj稱為例子，Vj Fj, j =1,2，n。設(shè)PE和NE是E的兩個例 子集，分別稱為正例集和反例集。| PE |= p,| NE |二n，則ID3基于如下兩種假設(shè)： 在向量空間E上的一棵正確決策樹，對任意例子的分類概率同E中正例、反例的概率一致； 一棵決策樹對一例子做出正確分類判別所需的信息為i(p,n) p log2 p n p + n p + nEI,E2, ,Ev。假設(shè)Ei中含有Pi個正例和 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é)點。其方法 可推廣到多類情況。(上面只研究正、反兩類)cPi，i h,2, ,c，即 | E |八 pi。若i 二以A為根分類的信息熵為v | Ei |E(A): I(Ei)i | E |所以，選擇屬性A*使E(A)最小。(2)(2) 建樹的算法步驟 對于任意的選擇屬性A,假設(shè)A有v個屬性值，對應的概率分別為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擴展，生成v個子結(jié)點EI，E2,，Ev , Ei是屬性A取i個值時，按照最小的信息熵原理選擇的A的后繼屬性，分別對應的信息熵為I（EI）,I（E2）, ,l（Ev）； 根據(jù)公式（* ）計算E（A）； 選擇A*使E（A*）最小，將A*作為根屬性； 利用步驟的計算結(jié)果，建立結(jié)點 A*的后繼結(jié)點EE2,EV; 對所有的Ei，若為葉結(jié)點，則停止擴展此結(jié)點。否則遞歸執(zhí)行的過程。（3 3）應用實例決策樹的構(gòu)造主要分為兩個階段：建樹階段和調(diào)整階段。例如下面以某課堂教學評估數(shù)據(jù)庫中的數(shù)據(jù)挖掘和知識

33、發(fā)現(xiàn)為例。該課堂教學評估指標體系表共分為若干項，經(jīng)研究可歸納為：教學態(tài)度（A6 ）、教學內(nèi)容（A7 ）、教學方法（A8 ）、教學效果（A9 ）、評價（A.0）共五項，實際數(shù)據(jù) 見表1所示由于屬性初值為連續(xù)值，需進行離散化處理。將屬性劃分為若干個區(qū)段，C1:95100 分、C2: 8094 分、C3: 7079 分、C4: 6069 分、C5: 60 分。見表 2 所示。解：去掉屬性A1。因為A1對于結(jié)論屬性而言，無互信息，亦稱無信息增益，即gain （AJ = 0。計算測試集的全部信息量:然后計算各結(jié)點的信息量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同理，可計算出ASA8,A信息熵:gai n( A7) =0.65876, gain( As)= 0.411, gain( A9) = 0.5 50 1故取A7為根屬性。同樣對Ci這一分支繼續(xù)使用ID3 方法進一步劃分，可得到如圖所示的決策樹。該決策樹完全概括了教師教學評估的三個等級的 20個記錄。從圖中可以看出：教學A7是一重要指標。表1或表2中隱藏的知識有如下幾種情況:規(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(良)即，如果教學內(nèi)容為良，則課堂教學質(zhì)量評價等級一定為良；如果教學內(nèi)容為中, 則課堂教學質(zhì)量評價等級一定為中；如果教學內(nèi)容和教學效果均為優(yōu)，則課堂教學 質(zhì)量評價等級一定為優(yōu)；如果教學內(nèi)容為優(yōu)而教學效果為良，則課堂教學質(zhì)量評價 等級為良。因此，從這些規(guī)則中，可以歸納出一條重要的知識，就是：教學內(nèi)容組 織好的老師，其課堂教學質(zhì)量的綜合評價成績較好。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ù)挖掘中占有非常重要的地位。 但是在應用中，ID3ID3算法存在不能 夠處理連續(xù)屬性、計算信息增益時偏向于選擇取值較多的屬性等不足。C4.5是在ID3 基礎(chǔ)上發(fā)展起來的決策樹生成算法， 由J.R.Quinlan在1993年提出。C4.5克服了 ID3 在應用中存在的不足，主要體現(xiàn)在以下幾個方面：（1）用信息增益率來選擇屬性，它克服了信息增益選擇屬性時偏向于選擇取值較

39、多的屬性的不足；（2）在樹構(gòu)造過程中或者構(gòu)造完成之后，進行剪枝；（3）能夠完成對連續(xù)屬性的離散化處理；（4）能夠?qū)τ诓煌暾麛?shù)據(jù)進行處理；（5）C4.5采用的知識表示形式為決策樹，并最終可以形成產(chǎn)生式規(guī)則。4.5.14.5.1構(gòu)造決策樹設(shè)T為數(shù)據(jù)集，類別集合為G,C2,，Cd，選擇一個屬性V把T分為多個子集。設(shè)V有互不重合的n個值VV2，,vj，則T被分為n個子集衛(wèi),，Tn，這里中 的所有實例的取值均為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)送號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對ID3改進是用信息增益率來選擇屬性。理論和實驗表明，采用“信息增益率” （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之間的任意取值都可以把實例集合分為兩部分T1 =t| A Zi和Tt | A vi可以看到，一共有m-1種分割情況。對屬性A的m-1種分割的任意一種情況，作為該屬性的兩個離散取值，重新構(gòu) 造該屬性的離散值，再按照上述公式計算每種分割所對應的信息增益率 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決策樹剪枝由于噪聲和隨機因素的影響，決策樹一般會很復雜。

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

44、設(shè)一個葉結(jié)點覆蓋N個實例，其中E個為錯誤的。對于具有信任度 CF的實例, 計算一個2項分布，UCF（E,N），該2項分布，即實例的誤判概率，那么N個實例判 斷錯誤的數(shù)目為N UCF（E,N）。子樹的錯誤數(shù)目為所有葉結(jié)點的總和。如：注：（）中為覆蓋的實例數(shù)目設(shè)CF=0.25,貝U U該子數(shù)的實例判斷錯誤數(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若以一個結(jié)點C1代替該子樹，則16個實例中有一個錯誤（C3）,誤判實例數(shù)目為16xU0.25（1,16） =16 x

45、0.157=2.51 2由于判斷錯誤數(shù)目小于上述子樹，則以該葉結(jié)點代替子樹。4.5.44.5.4從決策樹抽取規(guī)則在C4.5中，從決策樹抽取規(guī)則需要兩個步驟：獲得簡單規(guī)則、精簡規(guī)則屬性。1 1獲得簡單規(guī)則對于已生成的決策樹，可以直接從中獲得規(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、精簡規(guī)則屬性在上述獲得的簡單規(guī)則中，可能包含了許多無關(guān)的屬性。在上面的規(guī)則中，條件 F和G的取值對于結(jié)論沒有任何影響。在不影響規(guī)則的預測效果的情況下，可以刪 除一些不必要的條件。設(shè)規(guī)則的形式為R：If A the n class C精簡之后的規(guī)則為R:If A_ then class C其中，A是從A中刪除條件之后的形式 4.64.6決策樹的改進算法20 / 2219 / 22E(X,a)l(X,a)V(X,a)|a 二 a)(1)(1) 二叉樹算法Kononenko等人認為Quinlan的熵函數(shù)并不理想，有偏向于取值較多的屬性的毛 病。為了克服

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

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

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