數(shù)據(jù)倉庫17(1).ppt_第1頁
數(shù)據(jù)倉庫17(1).ppt_第2頁
數(shù)據(jù)倉庫17(1).ppt_第3頁
數(shù)據(jù)倉庫17(1).ppt_第4頁
數(shù)據(jù)倉庫17(1).ppt_第5頁
已閱讀5頁,還剩36頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

2、 H(U),在進行了通信之后,信宿收到了信源發(fā)來的信息,這種先驗不確定性才會被消除或者被減少。 如果干擾很小,不會對傳遞的信息產(chǎn)生任何可察覺的影響,信源發(fā)出的信息能夠被信宿全部收到,在這種情況下,信宿的先驗不確定性就會被完全消除。,在一般情況下,干擾總會對信源發(fā)出的信息造成某種破壞,使信宿收到的信息不完全。 先驗不確定性不能全部被消除,只能部分地消除。 通信結(jié)束之后,信宿仍然具有一定程度的不確定性。這就是后驗不確定性,用條件熵表示H(U/V)。 后驗不確定性總要小于先驗不確定性: H(U/V) H(U),如果后驗不確定性的大小正好等于先驗不確定性的大小,這就表示信宿根本沒有收到信息。 如果后驗

3、不確定性的大小等于零,這就表示信宿收到了全部信息。 可見,信息是用來消除(隨機)不確定性的度量。信息量用互信息來表示,即: I(U,V)H(U) H(U/V),互信息的計算,1定義 (1)設(shè)S為訓(xùn)練集,有n個特征(屬性),表示為(A1,A2,.,An)。S表示例子總數(shù)。 (2)S中有U1,U2兩類。Ui表示Ui類例子數(shù)。 (3)特征Ak處有m個取值,分別為(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)消息(符號)Ui(i=1,2,.,q)的發(fā)生概率P(Ui)組成信源數(shù)學(xué)模型(樣本空間或概率空間),(3.5),(3)自信息:消息Ui發(fā)生后所含有的信息量。它反映了消息Ui發(fā)生前的不確定性(隨機性)。定義為: 以2為底,所得的信息量單位為bit。以e為底,所得的信息量單位為nat. (4)信息熵:自信息的數(shù)學(xué)期望。即信源輸出

5、后,每個消息所提供的信息量,也反映了信源輸出前的平均確定性。定義為:,(3.6),(3.7),例如:兩個信源,其概率空間分別為: 則信息熵分別為: 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)是信源輸出前的平均不確定性,也稱先驗熵。 H(U)的性質(zhì): (1)H(U)=0時,說明只存在著唯一的可能性,不存在不確定性。 (2)如果n種可能的發(fā)生都有相同的概率,即所有的Ui有P(Ui)=1/n,H(

6、U)達到最大值log n,系統(tǒng)的不確定性最大。 P(Ui)互相接近,H(U)就大。P(Ui)相差大,則H(U)就小。,7互信息 (1)后驗熵和條件熵 當(dāng)沒有接收到輸出符號V時,已知輸入符號U的概率分布為P(U),而當(dāng)接收到輸出符號V=Vj 后,輸入符號的概率分布發(fā)生了變化,變成后驗概率分布P(U|Vj)。其后驗熵為: 那么接收到輸出符號V=Vj后,關(guān)于U的平均不確定性為: 這是接收到輸出符號Vj后關(guān)于U的條件熵,這個條件熵稱為信道疑義度。它表示在輸出端收到全部輸出符號V后,對于輸入端的符號集U尚存在的不確定性(存在疑義)。 從上面分析可知:條件熵小于無條件熵,即 H(U|V)H(U)。 說明接

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

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

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

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

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

12、若子集僅含正例或反例,對應(yīng)分枝標上P或N,返回調(diào)用處。,實例計算,對于氣候分類問題進行具體計算有: 信息熵的計算 信息熵: 類別出現(xiàn)概率: |S|表示例子集S的總數(shù),|ui|表示類別ui的例子數(shù)。 對9個正例和5個反例有: P(u1)=9/14 P(u2)=5/14 H(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/14 P(v2)=4/14 P(v3

13、)=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/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, 互信息計算 對 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個例子中對天氣的3個取值進行分枝,3 個分枝對應(yīng)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類,因此對應(yīng)分枝標記為P,其余兩個子集既含有正例又含有反例,將遞歸調(diào)用建樹算法。, 遞歸建樹 分別對F1和F3子集利用ID3算法,在每個子集中對各特征(仍為四個特征)求互信息. (1)F1中的天氣全取晴值,則H(U)=H(U|V),有I(U|V)=0,在余下三個

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論