數(shù)據(jù)倉庫17(1).ppt

1、第7章 信息論方法（一）,7.1 信息論原理 7.2 決策樹方法,7.1 信息論原理 信息論是C.E.Shannon為解決信息傳遞（通信）過程問題而建立的理論，也稱為統(tǒng)計(jì)通信理論。 1. 信道模型 一個(gè)傳遞信息的系統(tǒng)是由發(fā)送端（信源）和接收端（信宿）以及連接兩者的通道（信道）三者組成。,信道,u1,u2.ur,信源 U,v1,v2.vr,P(V|U),信宿 V,在進(jìn)行實(shí)際的通信之前，收信者（信宿）不可能確切了解信源究竟會(huì)發(fā)出什么樣的具體信息，不可能判斷信源會(huì)處于什么樣的狀態(tài)。 這種情形就稱為信宿對(duì)于信源狀態(tài)具有不確定性。而且這種不確定性是存在于通信之前的。因而又叫做先驗(yàn)不確定性，表示成 信息熵

2、 H（U）,在進(jìn)行了通信之后，信宿收到了信源發(fā)來的信息，這種先驗(yàn)不確定性才會(huì)被消除或者被減少。 如果干擾很小，不會(huì)對(duì)傳遞的信息產(chǎn)生任何可察覺的影響，信源發(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)不確定性的大小，這就表示信宿根本沒有收到信息。 如果后驗(yàn)

3、不確定性的大小等于零，這就表示信宿收到了全部信息。 可見，信息是用來消除（隨機(jī)）不確定性的度量。信息量用互信息來表示，即： I（U，V）H（U） H（U/V）,互信息的計(jì)算,1定義 （1）設(shè)S為訓(xùn)練集，有n個(gè)特征（屬性），表示為（A1，A2，.，An）。S表示例子總數(shù)。 （2）S中有U1，U2兩類。Ui表示Ui類例子數(shù)。 （3）特征Ak處有m個(gè)取值，分別為（V1，V2，.，Vm）。 2Ui類出現(xiàn)概率為: P（Ui）=Ui/S（3.1） 自然有,3Ui類中在特征Ak處取值Vj的例子集合Vij的條件概率為: P（VjUi）=Vij/Ui（3.2） 自然有 4在特征Ak處，取Vj值的例子集合的概率為

4、: P（Vj）=Vj/S （3.3） 自然有,5在特征Ak處取Vj值的例子，屬于Ui類的例子集合Uij的條件概率為: P（UiVj）=Uij/Vj（3.4） 自然有,6信息熵 （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é)期望。即信源輸出

5、后，每個(gè)消息所提供的信息量，也反映了信源輸出前的平均確定性。定義為:,（3.6）,（3.7）,例如:兩個(gè)信源，其概率空間分別為: 則信息熵分別為: H（X）= - 0.99 log0.99 - 0.01 log0.01 = 0.08 bit H（Y）= - 0.5 log0.5 - 0.5 log0.5 = 1bit 可見 H（Y）H（X） 故信源Y比信源X的平均不確定性要大。,信息熵H（U）是信源輸出前的平均不確定性，也稱先驗(yàn)熵。 H（U）的性質(zhì): （1）H（U）=0時(shí)，說明只存在著唯一的可能性，不存在不確定性。 （2）如果n種可能的發(fā)生都有相同的概率，即所有的Ui有P（Ui）=1/n，H（

6、U）達(dá)到最大值log n，系統(tǒng)的不確定性最大。 P（Ui）互相接近，H（U）就大。P（Ui）相差大，則H（U）就小。,7互信息 (1)后驗(yàn)熵和條件熵 當(dāng)沒有接收到輸出符號(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è)條件熵稱為信道疑義度。它表示在輸出端收到全部輸出符號(hào)V后，對(duì)于輸入端的符號(hào)集U尚存在的不確定性（存在疑義）。 從上面分析可知：條件熵小于無條件熵，即 H（U|V）H（U）。 說明接

7、收到符號(hào)集V的所有符號(hào)后，關(guān)于輸入符號(hào)U的平均不確定性減少了。即總能消除一些關(guān)于輸入端X的不確定性，從而獲得了一些信息。,（2）平均互信息 定義: I（U,V） = H（U） H（U|V） （3.10） I（U,V）稱為U和V之間的平均互信息.它代表接收到符號(hào)集V后獲得的關(guān)于U的信息量。 可見，熵（H（U）、H（U|V）只是平均不確定性的描述。熵差（H（U） H（U|V）是不確定性的消除，即互信息才是接收端所獲得的信息量。 對(duì)輸入端U只有U1，U2兩類，互信息的計(jì)算公式為:,7.2 決策樹方法,7.2.1決策樹概念 決策樹是用樣本的屬性作為結(jié)點(diǎn)，用屬性的取值作為分支的樹結(jié)構(gòu)。 決策樹的根結(jié)點(diǎn)是

8、所有樣本中信息量最大的屬性。樹的中間結(jié)點(diǎn)是該結(jié)點(diǎn)為根的子樹所包含的樣本子集中信息量最大的屬性。決策樹的葉結(jié)點(diǎn)是樣本的類別值。,決策樹是一種知識(shí)表示形式，它是對(duì)所有樣本數(shù)據(jù)的高度概括。 決策樹能準(zhǔn)確地識(shí)別所有樣本的類別，也能有效地識(shí)別新樣本的類別。,7.2.2 ID3方法基本思想,當(dāng)前國際上最有影響的示例學(xué)習(xí)方法首推J.R.Quinlan的ID3（Interative Dic熱miser versions3）. 原理： 首先找出最有判別力的特征，把數(shù)據(jù)分成多個(gè)子集，每個(gè)子集又選擇最有判別力的特征進(jìn)行劃分，一直進(jìn)行到所有子集僅包含同一類型的數(shù)據(jù)為止。最后得到一棵決策樹。 J.R.Quinlan的工

9、作主要是引進(jìn)了信息論中的互信息，他將其稱為信息增益（information gain），作為特征判別能力的度量，并且將建樹的方法嵌在一個(gè)迭代的外殼之中。,一、ID3基本思想 例如：關(guān)于氣候的類型，特征為: 天氣 取值為： 晴，多云，雨 氣溫 取值為： 冷 ，適中，熱 濕度 取值為： 高 ，正常 風(fēng) 取值為： 有風(fēng)， 無風(fēng),每個(gè)實(shí)體在世界中屬于不同的類別，為簡單起見，假定僅有兩個(gè)類別，分別為P，N。在這種兩個(gè)類別的歸納任務(wù)中，P類和N類的實(shí)體分別稱為概念的正例和反例。將一些已知的正例和反例放在一起便得到訓(xùn)練集。 表3.1給出一個(gè)訓(xùn)練集。由ID3算法得出一棵正確分類訓(xùn)練集中每個(gè)實(shí)體的決策樹，見下圖

10、。,ID3決策樹,決策樹葉子為類別名，即P 或者N。其它結(jié)點(diǎn)由實(shí)體的特征組成，每個(gè)特征的不同取值對(duì)應(yīng)一分枝。 若要對(duì)一實(shí)體分類，從樹根開始進(jìn)行測試，按特征的取值分枝向下進(jìn)入下層結(jié)點(diǎn)，對(duì)該結(jié)點(diǎn)進(jìn)行測試，過程一直進(jìn)行到葉結(jié)點(diǎn)，實(shí)體被判為屬于該葉結(jié)點(diǎn)所標(biāo)記的類別。,現(xiàn)用圖來判一個(gè)具體例子， 某天早晨氣候描述為: 天氣：多云 氣溫：冷 濕度：正常 風(fēng)： 無風(fēng) 它屬于哪類氣候呢? 從圖中可判別該實(shí)體的類別為P類。,ID3就是要從表的訓(xùn)練集構(gòu)造圖這樣的決策樹。 實(shí)際上，能正確分類訓(xùn)練集的決策樹不止一棵。 Quinlan的ID3算法能得出結(jié)點(diǎn)最少的決策樹。,二、ID3算法 （一）主算法 從訓(xùn)練集中隨機(jī)選擇一

11、個(gè)既含正例又含反例的子集（稱為窗口）； 用“建樹算法”對(duì)當(dāng)前窗口形成一棵決策樹； 對(duì)訓(xùn)練集（窗口除外）中例子用所得決策樹進(jìn)行類別判定，找出錯(cuò)判的例子； 若存在錯(cuò)判的例子，把它們插入窗口，轉(zhuǎn)2，否則結(jié)束。,主算法流程用下圖表示。其中PE、NE分別表示正例集和反例集，它們共同組成訓(xùn)練集。PE，PE和NE，NE分別表示正例集和反例集的子集。 主算法中每迭代循環(huán)一次，生成的決策樹將會(huì)不相同。,ID3主算法流程,（二）建樹算法 對(duì)當(dāng)前例子集合，計(jì)算各特征的互信息； 選擇互信息最大的特征Ak； 把在Ak處取值相同的例子歸于同一子集，Ak取幾個(gè)值就得幾個(gè)子集； 對(duì)既含正例又含反例的子集，遞歸調(diào)用建樹算法；

12、若子集僅含正例或反例，對(duì)應(yīng)分枝標(biāo)上P或N，返回調(diào)用處。,實(shí)例計(jì)算,對(duì)于氣候分類問題進(jìn)行具體計(jì)算有： 信息熵的計(jì)算 信息熵： 類別出現(xiàn)概率： |S|表示例子集S的總數(shù)，|ui|表示類別ui的例子數(shù)。 對(duì)9個(gè)正例和5個(gè)反例有： P（u1）=9/14 P（u2）=5/14 H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit, 條件熵計(jì)算 條件熵： 屬性A1取值vj時(shí)，類別ui的條件概率： A1=天氣 取值 v1=晴，v2=多云，v3=雨 在A1處取值晴的例子5個(gè)，取值多云的例子4 個(gè)，取值雨的例子5 個(gè)，故： P（v1）=5/14 P（v2）=4/14 P（v3

13、）=5/14 取值為晴的5 個(gè)例子中有2 個(gè)正例、3個(gè)反例，故： P（u1/v1）=2/5， P（u2/v1）=3/5 同理有：P（u1/v2）=4/4， P（u2/v2）=0 P（u1/v3）=2/5， P（u2/v3）=3/5 H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4) +0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3) = 0.694bit, 互信息計(jì)算 對(duì) A1=天氣 處有： I（天氣）=H（U）- H（U|V）= 0.94 - 0.694 = 0.246 bit 類似可得： I（氣溫

14、）=0.029 bit I（濕度）=0.151 bit I（風(fēng)）=0.048 bit 建決策樹的樹根和分枝 ID3算法將選擇互信息最大的特征天氣作為樹根，在14個(gè)例子中對(duì)天氣的3個(gè)取值進(jìn)行分枝，3 個(gè)分枝對(duì)應(yīng)3 個(gè)子集，分別是: F1=1，2，8，9，11，F(xiàn)2=3，7，12，13，F(xiàn)3=4，5，6，10，14 其中F2中的例子全屬于P類，因此對(duì)應(yīng)分枝標(biāo)記為P，其余兩個(gè)子集既含有正例又含有反例，將遞歸調(diào)用建樹算法。, 遞歸建樹 分別對(duì)F1和F3子集利用ID3算法，在每個(gè)子集中對(duì)各特征（仍為四個(gè)特征）求互信息. （1）F1中的天氣全取晴值，則H（U）=H（U|V），有I（U|V）=0，在余下三個(gè)

15、特征中求出濕度互信息最大，以它為該分枝的根結(jié)點(diǎn)，再向下分枝。濕度取高的例子全為N類，該分枝標(biāo)記N。取值正常的例子全為P類，該分枝標(biāo)記P。 （2）在F3中，對(duì)四個(gè)特征求互信息，得到風(fēng)特征互信息最大，則以它為該分枝根結(jié)點(diǎn)。再向下分枝，風(fēng)取有風(fēng)時(shí)全為N類，該分枝標(biāo)記N。取無風(fēng)時(shí)全為P類，該分枝標(biāo)記P。 這樣就得到圖8.5的決策樹,對(duì)ID3的討論, 優(yōu)點(diǎn) ID3在選擇重要特征時(shí)利用了互信息的概念，算法的基礎(chǔ)理論清晰，使得算法較簡單，是一個(gè)很有實(shí)用價(jià)值的示例學(xué)習(xí)算法。 該算法的計(jì)算時(shí)間是例子個(gè)數(shù)、特征個(gè)數(shù)、結(jié)點(diǎn)個(gè)數(shù)之積的線性函數(shù)。我們曾用4761個(gè)關(guān)于苯的質(zhì)譜例子作了試驗(yàn)。其中正例2361個(gè)，反例240

16、0個(gè)，每個(gè)例子由500個(gè)特征描述，每個(gè)特征取值數(shù)目為6，得到一棵1514個(gè)結(jié)點(diǎn)的決策樹。對(duì)正、反例各100個(gè)測試?yán)髁藴y試，正例判對(duì)82個(gè)，反例判對(duì)80個(gè)，總預(yù)測正確率81%，效果是令人滿意的。, 缺點(diǎn) （1）互信息的計(jì)算依賴于特征取值的數(shù)目較多的特征，這樣不太合理。一種簡單的辦法是對(duì)特征進(jìn)行分解，如上節(jié)例中，特征取值數(shù)目不一樣，可以把它們統(tǒng)統(tǒng)化為二值特征，如天氣取值晴，多云，雨，可以分解為三個(gè)特征；天氣晴，天氣多云，天氣雨。取值都為“是”或“否”，對(duì)氣溫也可做類似的工作。這樣就不存在偏向問題了。,（2）用互信息作為特征選擇量存在一個(gè)假設(shè)，即訓(xùn)練例子集中的正，反例的比例應(yīng)與實(shí)際問題領(lǐng)域里正、反例比例相同。一般情況不能保證相同，這樣計(jì)算訓(xùn)練集的互信息就有偏差。 （3）ID3在建樹時(shí)，每個(gè)節(jié)點(diǎn)僅含一個(gè)特征，是一種單變元的算法，特征間的相關(guān)性強(qiáng)調(diào)不夠。雖然它將多個(gè)特征用一棵樹連在一起，但聯(lián)系還是松