數據倉庫與數據挖掘課件1 (9)

第7章

信息論方法

（1）信息論原理是數據挖掘的理論基礎之一。一般用于分類問題。原理:找出確定類別的關鍵的條件屬性。求關鍵屬性的方法，就是利用信息論原理中的公式,計算各條件屬性的信息量，從中選出信息量最大的屬性.獲取的分類知識表示形式為：（1）決策樹，如ID3、C4.5方法，是把信息量最大的屬性作為樹或子樹的根結點，屬性的取值作為分枝。（2）決策規(guī)則樹，如IBLE方法，是把信息量大的多個屬性作為樹或子樹的結點，多個屬性的權值和與閾值比較大小來產生分枝。7.1信息論原理7.2決策樹方法7.1信息論原理信息論是C.E.Shannon為解決信息傳遞（通信）過程問題而建立的理論，也稱為統(tǒng)計通信理論。1.信道模型一個傳遞信息的系統(tǒng)是由發(fā)送端（信源）和接收端（信宿）以及連接兩者的通道（信道）三者組成。信道u1,u2….ur信源Uv1,v2….vrP(V|U)信宿V在進行實際的通信之前，收信者（信宿）不可能確切了解信源究竟會發(fā)出什么樣的具體信息，不可能判斷信源會處于什么樣的狀態(tài)。這種情形就稱為信宿對于信源狀態(tài)具有不確定性。而且這種不確定性是存在于通信之前的。因而又叫做先驗不確定性，表示成信息熵H（U）在進行了通信之后，信宿收到了信源發(fā)來的信息，這種先驗不確定性才會被消除或者被減少。如果干擾很小，不會對傳遞的信息產生任何可察覺的影響，信源發(fā)出的信息能夠被信宿全部收到，在這種情況下，信宿的先驗不確定性就會被完全消除。在一般情況下，干擾總會對信源發(fā)出的信息造成某種破壞，使信宿收到的信息不完全。先驗不確定性不能全部被消除，只能部分地消除。通信結束之后，信宿仍然具有一定程度的不確定性。這就是后驗不確定性，用條件熵表示H（U/V）。后驗不確定性總要小于先驗不確定性:H（U/V）<H（U）如果后驗不確定性的大小正好等于先驗不確定性的大小，這就表示信宿根本沒有收到信息。如果后驗不確定性的大小等于零，這就表示信宿收到了全部信息?？梢?，信息是用來消除（隨機）不確定性的度量。信息量用互信息來表示，即：I（U，V）＝H（U）－H（U/V）互信息的計算1．定義（1）設S為訓練集，有n個特征（屬性），表示為（A1，A2，...，，An）。｜S｜表示例子總數。（2）S中有U1，U2兩類。｜Ui｜表示Ui類例子數。（3）特征Ak處有m個取值，分別為（V1，V2，...，，Vm）。2．Ui類出現(xiàn)概率為:

P（Ui）=｜Ui｜/｜S｜

（3.1）

自然有

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

P（Vj｜Ui）=｜Vij｜/｜Ui｜

（3.2）

自然有

4．在特征Ak處，取Vj值的例子集合的概率為:

P（Vj）=｜Vj｜/｜S｜

（3.3）

自然有

5．在特征Ak處取Vj值的例子，屬于Ui類的例子集合Uij的條件概率為:

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

（3.4）

自然有

6．信息熵（1）消息傳遞系統(tǒng)由消息的發(fā)送端（信源）和接收端（信宿）以及連接兩者的通道（信道）三者組成。（2）消息（符號）Ui（i=1，2，...，q）的發(fā)生概率P（Ui）組成信源數學模型（樣本空間或概率空間）

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

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

可見

H（Y）>H（X）

故信源Y比信源X的平均不確定性要大。

信息熵H（U）是信源輸出前的平均不確定性，也稱先驗熵。

H（U）的性質:

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

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

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

7．互信息(1)后驗熵和條件熵當沒有接收到輸出符號V時，已知輸入符號U的概率分布為P（U），而當接收到輸出符號V=Vj

后，輸入符號的概率分布發(fā)生了變化,變成后驗概率分布P（U|Vj）。其后驗熵為：那么接收到輸出符號V=Vj后，關于U的平均不確定性為：這是接收到輸出符號Vj后關于U的條件熵這個條件熵稱為信道疑義度。它表示在輸出端收到全部輸出符號V后，對于輸入端的符號集U尚存在的不確定性（存在疑義）。

從上面分析可知：條件熵小于無條件熵，即H（U|V）<H（U）。說明接收到符號集V的所有符號后，關于輸入符號U的平均不確定性減少了。即總能消除一些關于輸入端X的不確定性，從而獲得了一些信息。（2）平均互信息定義:

I（U,V）

=H（U）

H（U|V）

（3.10）

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

H（U|V））是不確定性的消除，即互信息才是接收端所獲得的信息量。對輸入端U只有U1，U2兩類，互信息的計算公式為: 7.2決策樹方法7.2.1決策樹概念決策樹是用樣本的屬性作為結點，用屬性的取值作為分支的樹結構。決策樹的根結點是所有樣本中信息量最大的屬性。樹的中間結點是該結點為根的子樹所包含的樣本子集中信息量最大的屬性。決策樹的葉結點是樣本的類別值。決策樹是一種知識表示形式，它是對所有樣本數據的高度概括。決策樹能準確地識別所有樣本的類別，也能有效地識別新樣本的類別。7.2.2ID3方法基本思想當前國際上最有影響的示例學習方法首推J.R.Quinlan的ID3（Interative

Dic熱miserversions3）.

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

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

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

濕度取值為：高，正常

風取值為：有風，無風

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

氣濕度風晴雨多云高正常有風無風PNNPPID3決策樹決策樹葉子為類別名，即P或者N。其它結點由實體的特征組成，每個特征的不同取值對應一分枝。若要對一實體分類，從樹根開始進行測試，按特征的取值分枝向下進入下層結點，對該結點進行測試，過程一直進行到葉結點，實體被判為屬于該葉結點所標記的類別?，F(xiàn)用圖來判一個具體例子，某天早晨氣候描述為:

天氣：多云

氣溫：冷

濕度：正常

風：無風它屬于哪類氣候呢?從圖中可判別該實體的類別為P類。ID3就是要從表的訓練集構造圖這樣的決策樹。實際上，能正確分類訓練集的決策樹不止一棵。Quinlan的ID3算法能得出結點最少的決策樹。二、ID3算法（一）主算法⒈

從訓練集中隨機選擇一個既含正例又含反例的子集（稱為"窗口"）；⒉

用“建樹算法”對當前窗口形成一棵決策樹；⒊

對訓練集（窗口除外）中例子用所得決策樹進行類別判定，找出錯判的例子；⒋

若存在錯判的例子，把它們插入窗口，轉2，否則結束。主算法流程用下圖表示。其中PE、NE分別表示正例集和反例集，它們共同組成訓練集。PE‘，PE’‘和NE’，NE‘’分別表示正例集和反例集的子集。主算法中每迭代循環(huán)一次，生成的決策樹將會不相同。訓練集PE、NE取子集建窗口窗口PE`、NE`生成決策樹測試PE、NE擴展窗口PE`=PE`+PE``NE`=NE`+NE``此決策樹為最后結果存在錯判的PE``，NE``嗎是否ID3主算法流程（二）建樹算法⒈

對當前例子集合，計算各特征的互信息；⒉

選擇互信息最大的特征Ak；⒊

把在Ak處取值相同的例子歸于同一子集，Ak取幾個值就得幾個子集；⒋

對既含正例又含反例的子集，遞歸調用建樹算法；⒌

若子集僅含正例或反例，對應分枝標上P或N，返回調用處。實例計算對于氣候分類問題進行具體計算有：⒈信息熵的計算信息熵：類別出現(xiàn)概率：|S|表示例子集S的總數，|ui|表示類別ui的例子數。

對9個正例和5個反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit⒉

條件熵計算條件熵：屬性A1取值vj時，類別ui的條件概率：A1=天氣

取值

v1=晴，v2=多云，v3=雨在A1處取值晴的例子5個，取值多云的例子4個，取值雨的例子5個，故：

P（v1）=5/14P（v2）=4/14P（v3）=5/14取值為晴的5個例子中有2個正例、3個反例，故：

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/5H(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⒊互信息計算對A1=天氣處有：

I（天氣）=H（U）-H（U|V）=0.94-0.694=0.246bit

類似可得：

I（氣溫）=0.029bitI（濕度）=0.151bitI（風）=0.048bit⒋建決策樹的樹根和分枝

ID3算法將選擇互信息最大的特征天氣作為樹根，在14個例子中對天氣的3個取值進行分枝，3個分枝對應3個子集，分別是:

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類，因此對應分枝標記為P，其余兩個子集既含有正例又含有反例，將遞歸調用建樹算法。⒌遞歸建樹分別對F1和F3子集利用ID3算法，在每個子集中對各特征（仍為四個特征）求互信息.

（1）F1中的天氣全取晴值，則H（U）=H（U|V），有I（U|V）=0，在余下三個特征中求出濕度互信息最大，以它為該分枝的根結點，再向下分枝。濕度取高的例子全為N類，該分枝標記N。取值正常的例子全為P類，該分枝標記P。

（2）在F3中，對四個特征求互信息，得到風特征互信息最大，則以它為該分枝根結點。再向下分枝，風取有風時全為N類，該分枝標記N。取無風時全為P類，該分枝標記P。

這樣就得到圖8.5的決策樹對ID3的討論⒈優(yōu)點

ID3在選擇重要特征時利用了互信息的概念，算法的基礎理論清晰，使得算法較簡單，是一個很有實用價值的示例學習算法。該算法的計算時間是例子個數、特征個數、結點個數之積的線性函數。我們曾用4761個關于苯的質譜例子作了試驗。