第七章-基于信息論的數(shù)據(jù)挖掘方法

第7章

信息論方法

7.1信息論原理7.2決策樹(shù)方法7.3C4.5算法7.1信息論原理信息論是C.E.Shannon為解決信息傳遞（通信）過(guò)程問(wèn)題而建立的理論，也稱(chēng)為統(tǒng)計(jì)通信理論。1.信道模型一個(gè)傳遞信息的系統(tǒng)是由發(fā)送端（信源）和接收端（信宿）以及連接兩者的通道（信道）三者組成。信道u1,u2….ur信源Uv1,v2….vrP(V|U)信宿V在進(jìn)行實(shí)際的通信之前，收信者（信宿）不可能確切了解信源究竟會(huì)發(fā)出什么樣的具體信息，不可能判斷信源會(huì)處于什么樣的狀態(tài)。這種情形就稱(chēng)為信宿對(duì)于信源狀態(tài)具有不確定性。而且這種不確定性是存在于通信之前的。因而又叫做先驗(yàn)不確定性，表示成信息熵H（U）在進(jìn)行了通信之后，信宿收到了信源發(fā)來(lái)的信息，這種先驗(yàn)不確定性才會(huì)被消除或者被減少。如果干擾很小，不會(huì)對(duì)傳遞的信息產(chǎn)生任何可察覺(jué)的影響，信源發(fā)出的信息能夠被信宿全部收到，在這種情況下，信宿的先驗(yàn)不確定性就會(huì)被完全消除。在一般情況下，干擾總會(huì)對(duì)信源發(fā)出的信息造成某種破壞，使信宿收到的信息不完全。先驗(yàn)不確定性不能全部被消除，只能部分地消除。通信結(jié)束之后，信宿仍然具有一定程度的不確定性。這就是后驗(yàn)不確定性，用條件熵表示H（U/V）。后驗(yàn)不確定性總要小于先驗(yàn)不確定性:H（U/V）<H（U）如果后驗(yàn)不確定性的大小正好等于先驗(yàn)不確定性的大小，這就表示信宿根本沒(méi)有收到信息。如果后驗(yàn)不確定性的大小等于零，這就表示信宿收到了全部信息。可見(jiàn)，信息是用來(lái)消除（隨機(jī)）不確定性的度量。信息量用互信息來(lái)表示，即：I（U，V）＝H（U）－H（U/V）2．信息熵（1）消息傳遞系統(tǒng)由消息的發(fā)送端（信源）和接收端（信宿）以及連接兩者的通道（信道）三者組成。（2）消息（符號(hào)）Ui（i=1，2，...，q）的發(fā)生概率P（Ui）組成信源數(shù)學(xué)模型（樣本空間或概率空間）

（3.5）（3）自信息:消息Ui發(fā)生后所含有的信息量。它反映了消息Ui發(fā)生前的不確定性（隨機(jī)性）。定義為：以2為底，所得的信息量單位為bit。以e為底，所得的信息量單位為nat.（4）信息熵:自信息的數(shù)學(xué)期望。即信源輸出后，每個(gè)消息所提供的信息量，也反映了信源輸出前的平均確定性。定義為:（3.6）（3.7）例如:兩個(gè)信源，其概率空間分別為:

則信息熵分別為:H（X）=-0.99log0.99-0.01log0.01=0.08bitH（Y）=-0.5log0.5-0.5log0.5=1bit

可見(jiàn) H（Y）>H（X）故信源Y比信源X的平均不確定性要大。

信息熵H（U）是信源輸出前的平均不確定性，也稱(chēng)先驗(yàn)熵。

H（U）的性質(zhì):

（1）H（U）=0時(shí)，說(shuō)明只存在著唯一的可能性，不存在不確定性。

（2）如果n種可能的發(fā)生都有相同的概率，即所有的Ui有P（Ui）=1/n，H（U）達(dá)到最大值logn，系統(tǒng)的不確定性最大。

P（Ui）互相接近，H（U）就大。P（Ui）相差大，則H（U）就小。

3．后驗(yàn)熵和條件熵當(dāng)沒(méi)有接收到輸出符號(hào)V時(shí)，已知輸入符號(hào)U的概率分布為P（U），而當(dāng)接收到輸出符號(hào)V=Vj

后，輸入符號(hào)的概率分布發(fā)生了變化,變成后驗(yàn)概率分布P（U|Vj）。其后驗(yàn)熵為：那么接收到輸出符號(hào)V=Vj后，關(guān)于U的平均不確定性為：這是接收到輸出符號(hào)Vj后關(guān)于U的條件熵

這個(gè)條件熵稱(chēng)為信道疑義度。它表示在輸出端收到全部輸出符號(hào)V后，對(duì)于輸入端的符號(hào)集U尚存在的不確定性（存在疑義）。從上面分析可知：條件熵小于無(wú)條件熵，即H（U|V）<H（U）。說(shuō)明接收到符號(hào)集V的所有符號(hào)后，關(guān)于輸入符號(hào)U的平均不確定性減少了。即總能消除一些關(guān)于輸入端X的不確定性，從而獲得了一些信息。4.互信息定義:

I（U,V）=H（U）

H（U|V）（3.10）

I（U,V）稱(chēng)為U和V之間的平均互信息.它代表接收到符號(hào)集V后獲得的關(guān)于U的信息量。可見(jiàn)，熵（H（U）、H（U|V））只是平均不確定性的描述。熵差（H（U）

H（U|V））是不確定性的消除，即互信息才是接收端所獲得的信息量。對(duì)輸入端U只有U1，U2兩類(lèi)，互信息的計(jì)算公式為: 互信息的計(jì)算1．定義（1）設(shè)S為訓(xùn)練集，有n個(gè)特征（屬性），表示為（A1，A2，...，，An）。｜S｜表示例子總數(shù)。（2）S中有U1，U2兩類(lèi)。｜Ui｜表示Ui類(lèi)例子數(shù)。（3）特征Ak處有m個(gè)取值，分別為（V1，V2，...，，Vm）。2．Ui類(lèi)出現(xiàn)概率為:

P（Ui）=｜Ui｜/｜S｜ （3.1）自然有

3．Ui類(lèi)中在特征Ak處取值Vj的例子集合Vij的條件概率為:

P（Vj｜Ui）=｜Vij｜/｜Ui｜ （3.2）自然有 4．在特征Ak處，取Vj值的例子集合的概率為:

P（Vj）=｜Vj｜/｜S｜ （3.3）自然有 5．在特征Ak處取Vj值的例子，屬于Ui類(lèi)的例子集合Uij的條件概率為:

P（Ui｜Vj）=｜Uij｜/｜Vj｜ （3.4）

自然有

7.2決策樹(shù)方法7.2.1決策樹(shù)概念決策樹(shù)是用樣本的屬性作為結(jié)點(diǎn)，用屬性的取值作為分支的樹(shù)結(jié)構(gòu)。決策樹(shù)的根結(jié)點(diǎn)是所有樣本中信息量最大的屬性。樹(shù)的中間結(jié)點(diǎn)是該結(jié)點(diǎn)為根的子樹(shù)所包含的樣本子集中信息量最大的屬性。決策樹(shù)的葉結(jié)點(diǎn)是樣本的類(lèi)別值。決策樹(shù)是一種知識(shí)表示形式，它是對(duì)所有樣本數(shù)據(jù)的高度概括。決策樹(shù)能準(zhǔn)確地識(shí)別所有樣本的類(lèi)別，也能有效地識(shí)別新樣本的類(lèi)別。7.2.2ID3方法基本思想當(dāng)前國(guó)際上最有影響的示例學(xué)習(xí)方法首推J.R.Quinlan的ID3（InterativeDic熱miserversions3）.

原理：首先找出最有判別力的特征，把數(shù)據(jù)分成多個(gè)子集，每個(gè)子集又選擇最有判別力的特征進(jìn)行劃分，一直進(jìn)行到所有子集僅包含同一類(lèi)型的數(shù)據(jù)為止。最后得到一棵決策樹(shù)。J.R.Quinlan的工作主要是引進(jìn)了信息論中的互信息，他將其稱(chēng)為信息增益（informationgain），作為特征判別能力的度量，并且將建樹(shù)的方法嵌在一個(gè)迭代的外殼之中。一、ID3基本思想例如：關(guān)于氣候的類(lèi)型，特征為:

天氣取值為：晴，多云，雨

氣溫取值為：冷，適中，熱

濕度取值為：高，正常

風(fēng)取值為：有風(fēng)，無(wú)風(fēng)

每個(gè)實(shí)體在世界中屬于不同的類(lèi)別，為簡(jiǎn)單起見(jiàn)，假定僅有兩個(gè)類(lèi)別，分別為P，N。在這種兩個(gè)類(lèi)別的歸納任務(wù)中，P類(lèi)和N類(lèi)的實(shí)體分別稱(chēng)為概念的正例和反例。將一些已知的正例和反例放在一起便得到訓(xùn)練集。表3.1給出一個(gè)訓(xùn)練集。由ID3算法得出一棵正確分類(lèi)訓(xùn)練集中每個(gè)實(shí)體的決策樹(shù)，見(jiàn)下圖。NO.屬性類(lèi)別天氣氣溫濕度風(fēng)1晴熱高無(wú)風(fēng)N2晴熱高有風(fēng)N3多云熱高無(wú)風(fēng)P4雨適中高無(wú)風(fēng)P5雨冷正常無(wú)風(fēng)P6雨冷正常有風(fēng)N7多云冷正常有風(fēng)P8晴適中高無(wú)風(fēng)N9晴冷正常無(wú)風(fēng)P10雨適中正常無(wú)風(fēng)P11晴適中正常有風(fēng)P12多云適中高有風(fēng)P13多云熱正常無(wú)風(fēng)P14雨適中高有風(fēng)N天

氣濕度風(fēng)晴雨多云高正常有風(fēng)無(wú)風(fēng)PNNPPID3決策樹(shù)決策樹(shù)葉子為類(lèi)別名，即P或者N。其它結(jié)點(diǎn)由實(shí)體的特征組成，每個(gè)特征的不同取值對(duì)應(yīng)一分枝。若要對(duì)一實(shí)體分類(lèi)，從樹(shù)根開(kāi)始進(jìn)行測(cè)試，按特征的取值分枝向下進(jìn)入下層結(jié)點(diǎn)，對(duì)該結(jié)點(diǎn)進(jìn)行測(cè)試，過(guò)程一直進(jìn)行到葉結(jié)點(diǎn)，實(shí)體被判為屬于該葉結(jié)點(diǎn)所標(biāo)記的類(lèi)別。現(xiàn)用圖來(lái)判一個(gè)具體例子，某天早晨氣候描述為:

天氣：多云

氣溫：冷

濕度：正常

風(fēng)：無(wú)風(fēng)它屬于哪類(lèi)氣候呢?從圖中可判別該實(shí)體的類(lèi)別為P類(lèi)。ID3就是要從表的訓(xùn)練集構(gòu)造圖這樣的決策樹(shù)。實(shí)際上，能正確分類(lèi)訓(xùn)練集的決策樹(shù)不止一棵。Quinlan的ID3算法能得出結(jié)點(diǎn)最少的決策樹(shù)。二、ID3算法（一）主算法⒈從訓(xùn)練集中隨機(jī)選擇一個(gè)既含正例又含反例的子集（稱(chēng)為"窗口"）；⒉用“建樹(shù)算法”對(duì)當(dāng)前窗口形成一棵決策樹(shù)；⒊對(duì)訓(xùn)練集（窗口除外）中例子用所得決策樹(shù)進(jìn)行類(lèi)別判定，找出錯(cuò)判的例子；⒋若存在錯(cuò)判的例子，把它們插入窗口，轉(zhuǎn)2，否則結(jié)束。主算法流程用下圖表示。其中PE、NE分別表示正例集和反例集，它們共同組成訓(xùn)練集。PE‘，PE’‘和NE’，NE‘’分別表示正例集和反例集的子集。主算法中每迭代循環(huán)一次，生成的決策樹(shù)將會(huì)不相同。訓(xùn)練集PE、NE取子集建窗口窗口PE`、NE`生成決策樹(shù)測(cè)試PE、NE擴(kuò)展窗口PE`=PE`+PE``NE`=NE`+NE``此決策樹(shù)為最后結(jié)果存在錯(cuò)判的PE``，NE``嗎是否ID3主算法流程（二）建樹(shù)算法⒈對(duì)當(dāng)前例子集合，計(jì)算各特征的互信息；⒉

選擇互信息最大的特征Ak；⒊把在Ak處取值相同的例子歸于同一子集，Ak取幾個(gè)值就得幾個(gè)子集；⒋對(duì)既含正例又含反例的子集，遞歸調(diào)用建樹(shù)算法；⒌若子集僅含正例或反例，對(duì)應(yīng)分枝標(biāo)上P或N，返回調(diào)用處。實(shí)例計(jì)算

對(duì)于氣候分類(lèi)問(wèn)題進(jìn)行具體計(jì)算有：⒈信息熵的計(jì)算信息熵：類(lèi)別出現(xiàn)概率：|S|表示例子集S的總數(shù)，|ui|表示類(lèi)別ui的例子數(shù)。對(duì)9個(gè)正例和5個(gè)反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit⒉條件熵計(jì)算條件熵：屬性A1取值vj時(shí)，類(lèi)別ui的條件概率：A1=天氣取值v1=晴，v2=多云，v3=雨在A1處取值晴的例子5個(gè)，取值多云的例子4個(gè)，取值雨的例子5個(gè)，故：

P（v1）=5/14P（v2）=4/14P（v3）=5/14取值為晴的5個(gè)例子中有2個(gè)正例、