分類決策樹_ID3算法

1、決策樹決策樹 決策樹基本概念決策樹基本概念 決策樹算法決策樹算法 主要內(nèi)容主要內(nèi)容 決策樹基本概念決策樹基本概念 決策樹算法決策樹算法 決策樹基本概念決策樹基本概念 關(guān)于分類問題關(guān)于分類問題 分類（Classification）任務(wù)就是通過學(xué)習(xí)獲得一個目標(biāo)函數(shù) （Target Function）f, 將每個屬性集x映射到一個預(yù)先定義好的類 標(biāo)號y。 分類任務(wù)的輸入數(shù)據(jù)是紀(jì)錄的集合，每條記錄也稱為實例 或者樣例。用元組(X,y)表示，其中，X 是屬性集合，y是一個 特殊的屬性，指出樣例的類標(biāo)號（也稱為分類屬性或者目標(biāo)屬性） 決策樹基本概念決策樹基本概念 關(guān)于分類問題關(guān)于分類問題 名稱體溫表皮覆

2、蓋 胎生水生動 物 飛行動 物 有腿冬眠類標(biāo)號 人類恒溫毛發(fā)是否否是否哺乳動 物 海龜冷血鱗片否半否是否爬行類 鴿子恒溫羽毛否否是是否鳥類 鯨恒溫毛發(fā)是是否否否哺乳類 X y 分類與回歸分類與回歸 分類目標(biāo)屬性分類目標(biāo)屬性y是離散的，回歸目標(biāo)屬性是離散的，回歸目標(biāo)屬性y是連續(xù)的是連續(xù)的 決策樹基本概念決策樹基本概念 解決分類問題的一般方法解決分類問題的一般方法 分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。 分類技術(shù)一般是用一種學(xué)習(xí)算法確定分類模型，該模型可以很好 地擬合輸入數(shù)據(jù)中類標(biāo)號和屬性集之間的聯(lián)系。學(xué)習(xí)算法得到的 模型不僅要很好擬合輸入數(shù)據(jù)，還要能夠正確地預(yù)測未知樣本的 類標(biāo)號。

3、因此，訓(xùn)練算法的主要目標(biāo)就是要建立具有很好的泛化 能力模型，即建立能夠準(zhǔn)確地預(yù)測未知樣本類標(biāo)號的模型。 分類方法的實例包括：決策樹分類法、基于規(guī)則的分類法、 神經(jīng)網(wǎng)絡(luò)、支持向量級、樸素貝葉斯分類方法等。 決策樹基本概念決策樹基本概念 解決分類問題的一般方法解決分類問題的一般方法 通過以上對分類問題一般方法的描述，可以看出分類問題 一般包括兩個步驟： 1、模型構(gòu)建（歸納） 通過對訓(xùn)練集合的歸納，建立分類模型。 2、預(yù)測應(yīng)用（推論） 根據(jù)建立的分類模型，對測試集合進(jìn)行測試。 決策樹基本概念決策樹基本概念 解決分類問題的一般方法解決分類問題的一般方法 TIDA1A2A3類 1Y100LN 2N125

4、SN 3Y400LY 4N415MN 學(xué)習(xí)算法 學(xué)習(xí)模型 模型模型 應(yīng)用模型 TIDA1A2A3類 1Y100L？ 2N125S？ 3Y400L？ 4N415M？ 訓(xùn)練集（類標(biāo)號已知）訓(xùn)練集（類標(biāo)號已知） 檢驗集（類標(biāo)號未知）檢驗集（類標(biāo)號未知） 歸納 推論 決策樹基本概念決策樹基本概念 決策樹決策樹 決策樹是一種典型的分類方法，首先對數(shù)據(jù)進(jìn)行處理，利用 歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數(shù)據(jù)進(jìn)行 分析。本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程。 決策樹基本概念決策樹基本概念 決策樹的優(yōu)點決策樹的優(yōu)點 1、推理過程容易理解，決策推理過程可以表示成If Then形式； 2、

5、推理過程完全依賴于屬性變量的取值特點； 3、可自動忽略目標(biāo)變量沒有貢獻(xiàn)的屬性變量，也為判 斷屬性 變量的重要性，減少變量的數(shù)目提供參考。 主要內(nèi)容主要內(nèi)容 決策樹基本概念決策樹基本概念 決策樹算法決策樹算法 決策樹算法決策樹算法 與決策樹相關(guān)的重要算法與決策樹相關(guān)的重要算法 1、Hunt,Marin和Stone 于1966年研制的CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個概 念。 2、1979年, J.R. Quinlan 給出ID3算法，并在1983年和1986年對ID3 進(jìn)行 了總結(jié)和簡化，使其成為決策樹學(xué)習(xí)算法的典型。 3、Schlimmer和Fisher于1986年對ID3進(jìn)行改造，在每個可能的決策

6、樹 節(jié)點創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到ID4算法。 4、1988年，Utgoff 在ID4基礎(chǔ)上提出了ID5學(xué)習(xí)算法，進(jìn)一步提高了效 率。 1993年，Quinlan 進(jìn)一步發(fā)展了ID3算法，改進(jìn)成C4.5算法。 5、另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二 元邏輯問題生成，每個樹節(jié)點只有兩個分枝，分別包括學(xué)習(xí)實例的正 例與反例。 CLS, ID3，C4.5，CART 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中

7、低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 假定公司收集了左表數(shù)據(jù)，那么對假定公司收集了左表數(shù)據(jù)，那么對 于任意給定的客人（測試樣例），于任意給定的客人（測試樣例）， 你能幫助公司將這位客人歸類嗎？你能幫助公司將這位客人歸類嗎？ 即：你能預(yù)測這位客人是屬于即：你能預(yù)測這位客人是屬于“買買” 計算機(jī)的那一類，還是屬于計算機(jī)的那一類，還是屬于“不買不買” 計算機(jī)的那一類？計算機(jī)的那一類？ 又：你需要多少有關(guān)這位客人的信又：你需要多少有關(guān)這位客人的信 息才能回答這個問題？息才能回答這個問題？ 決策樹

8、的用途決策樹的用途 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 誰在買計算機(jī)？誰在買計算機(jī)？ 年齡？ 學(xué)生？信譽(yù)？買 青 中 老 否是 優(yōu)良 不買買買 不買 決策樹的用途決策樹的用途 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買歸類：買 計算機(jī)？計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否

9、良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 誰在買計算機(jī)？誰在買計算機(jī)？ 年齡？ 學(xué)生？信譽(yù)？買 青 中 老 否是 優(yōu)良 不買買買 不買 決策樹的用途決策樹的用途 決策樹算法決策樹算法 決策樹算法決策樹算法 決策樹的表示決策樹的表示 決策樹的基本組成部分：決策結(jié)點、分支和葉子。決策樹的基本組成部分：決策結(jié)點、分支和葉子。 年齡？ 學(xué)生？信譽(yù)？買 青 中 老 否是 優(yōu)良 不買買買 不買 決策樹中最上面的結(jié)點稱為根結(jié)點。 是整個決策樹的開始。每個分支是

10、一 個新的決策結(jié)點，或者是樹的葉子。 每個決策結(jié)點代表一個問題或者決策. 通常對應(yīng)待分類對象的屬性。 每個葉結(jié)點代表一種可能的分類結(jié)果 在沿著決策樹從上到下的遍歷過程中，在每個結(jié)點都有一個 測試。對每個結(jié)點上問題的不同測試輸出導(dǎo)致不同的分枝，最后 會達(dá)到一個葉子結(jié)點。這一過程就是利用決策樹進(jìn)行分類的過程， 利用若干個變量來判斷屬性的類別 ID3 決策樹算法決策樹算法 ID3算法主要針對屬性選擇問題。是決策樹學(xué)習(xí)方法中最 具影響和最為典型的算法。 該方法使用信息增益度選擇測試屬性。該方法使用信息增益度選擇測試屬性。 當(dāng)獲取信息時，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信 息伴著不確定性。 從直覺上講

11、，小概率事件比大概率事件包含的信息量大。 如果某件事情是“百年一見”則肯定比“習(xí)以為?！钡氖录?含的信息量大。 如何度量信息量的大??？ ID3 信息量大小的度量信息量大小的度量 決策樹算法決策樹算法 Shannon1948年提出的信息論理論。事件ai的信息量I（ ai ）可 如下度量： 其中p(ai)表示事件ai發(fā)生的概率。 假設(shè)有n個互不相容的事件a1,a2,a3,.,an,它們中有且僅有一個 發(fā)生，則其平均的信息量可如下度量： n i i i n i in ap apaIaaaI 1 2 1 21 )( 1 log)()(),.,( )( 1 log)()( 2 i ii ap apaI

12、 ID3 信息量大小的度量信息量大小的度量 決策樹算法決策樹算法 n i i i n i in ap apaIaaaI 1 2 1 21 )( 1 log)()(),.,( 上式，對數(shù)底數(shù)可以為任何數(shù)，不同的取值對應(yīng)了熵的不同單位。 通常取2，并規(guī)定當(dāng)p(ai)=0時 =0 )( 1 log)()( 2 i ii ap apaI v信息增益信息增益 用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力，用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力， ID3算法在生成算法在生成 樹的每一步使用樹的每一步使用信息增益信息增益從候選屬性中選從候選屬性中選 擇屬性擇屬性 v用熵度量樣例的均一性用熵度量樣例的均一性 v信息增益

13、信息增益 v用熵度量樣例的均一性用熵度量樣例的均一性 熵刻畫了任意樣例集合熵刻畫了任意樣例集合 S 的純度的純度 給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集S， 那么那么 S 相對這個布爾型分類（函數(shù)）的熵為相對這個布爾型分類（函數(shù)）的熵為 信息論中對熵的一種解釋：信息論中對熵的一種解釋：熵熵確定了確定了要編碼集合要編碼集合S 中任意成員的分類所需要的最少二進(jìn)制位數(shù)；熵值中任意成員的分類所需要的最少二進(jìn)制位數(shù)；熵值 越大，需要的位數(shù)越多越大，需要的位數(shù)越多。 更一般地，如果目標(biāo)屬性具有更一般地，如果目標(biāo)屬性具有c個不同的值，那么個不同的值，那么 S 相

14、對于相對于c個狀態(tài)的分類的熵定義為個狀態(tài)的分類的熵定義為 v用信息增益度量熵的降低程度熵的降低程度 屬性A 的信息增益，使用屬性A分割樣例集合S 而導(dǎo)致的熵的降低程度 Gain (S, A)是 在知道屬性在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)的值后可以節(jié)省的二進(jìn)制位數(shù) 例子，注意是對當(dāng)前樣例集合計算上式 () ( ,)( )() v v v Values A S Gain S AEntropy SEntropy S S v1、信息熵是用來衡量一個隨機(jī)變量出現(xiàn)的期望值，一個變量的信 息熵越大，那么它出現(xiàn)的各種情況也就越多，也就是包含的內(nèi)容多， 我們要描述它就需要付出更多的表達(dá)才可以，也就是需要更

15、多的信 息才能確定這個變量。 v2、信息熵是隨機(jī)變量的期望。度量信息的不確定程度。信息的熵 越大，信息就越不容易搞清楚（雜亂）。 v3、一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂， 信息熵就越高。信息熵也可以說是系統(tǒng)有序化程度的一個度量。 v4、信息熵用以表示一個事物的非確定性，如果該事物的非確定性 越高，你的好奇心越重，該事物的信息熵就越高。 v5、熵是整個系統(tǒng)的平均消息量。 信息熵是信息論中用于度量信息 量的一個概念。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系 統(tǒng)越是混亂，信息熵就越高。 v6、處理信息就是為了把信息搞清楚，實質(zhì)上就是要想辦法讓信息 熵變小。 熵：表示隨機(jī)變量

16、的不確定性。 條件熵：在一個條件下，隨機(jī)變量的不確定性。 信息增益：熵 - 條件熵。表示在一個條件下，信息 不確定性減少的程度。 v例如： 假設(shè)X(明天下雨)的信息熵為2（不確定明天是否下 雨），Y(如果是陰天則下雨）的條件熵為0.01（因 為如果是陰天就下雨的概率很大，信息就少了） 信息增益=2-0.01=1.99。信息增益很大。說明在獲 得陰天這個信息后，明天是否下雨的信息不確定性 減少了1.99，是很多的，所以信息增益大。也就是 說陰天這個信息對下雨來說是很重要的。 ID3 信息量大小的度量信息量大小的度量 決策樹算法決策樹算法 Gain（S，A）是屬性）是屬性A在集合在集合S上的信息增

17、益上的信息增益 Gain（S，A）= Entropy（S） -Entropy（S，A） Gain（S，A）越大，說明選擇測試屬性對分類提供的信息越多）越大，說明選擇測試屬性對分類提供的信息越多 計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買

18、 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第1步計算決策屬性的熵步計算決策屬性的熵 決策屬性“買計算機(jī)？”。該屬性分 兩類：買/不買 S1(買)=641 S2（不買）= 383 S=S1+S2=1024 P1=641/1024=0.6260 P2=383/1024=0.3740 I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2

19、) =0.9537 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第2步計算條件屬性的熵步計算條件屬性的熵 條件屬性共有4個。分別是年齡、 收入、學(xué)生、信譽(yù)。 分別計算不同屬性的信息增益。 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 1

20、28中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第2-1步計算年齡的熵步計算年齡的熵 年齡共分三個組： 青年、中年、老年 青年買與不買比例為128/256 S1(買)=128 S2（不買）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183 決策樹算法決策樹算法

21、 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第2-2步計算年齡的熵步計算年齡的熵 年齡共分三個組： 青年、中年、老年 中年買與不買比例為256/0 S1(買)=256 S2（不買）= 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2

22、 =-(P1Log2P1+P2Log2P2) =0 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第2-3步計算年齡的熵步計算年齡的熵 年齡共分三個組： 青年、中年、老年 老年買與不買比例為257/127 S1(買)=257 S2（不買）=127 S=S1+S2=384 P1=257 /384 P2=127

23、/384 I(S1,S2)=I(257，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第2-4步計算年齡的熵步計算年齡的熵 年齡共分三個組： 青年、中年、老年 所占比例 青年組 384/1025=0

24、.375 中年組 256/1024=0.25 老年組 384/1024=0.375 計算年齡的平均信息期望 E（年齡）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877 G（年齡信息增益） =0.9537-0.6877 =0.2660 （1） 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買

25、1 老中否優(yōu)買 第第3步計算收入的熵步計算收入的熵 收入共分三個組： 高、中、低 E（收入）=0.9361 收入信息增益=0.9537-0.9361 =0.0176 (2) 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第4步計算學(xué)生的熵步計算學(xué)生的熵 學(xué)生共分二個組： 學(xué)生、非學(xué)生 E（學(xué)生）=0.781

26、1 年齡信息增益=0.9537-0.7811 =0.1726 （3） 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第5步計算信譽(yù)的熵步計算信譽(yù)的熵 信譽(yù)分二個組： 良好，優(yōu)秀 E（信譽(yù)）= 0.9048 信譽(yù)信息增益=0.9537-0.9048 =0.0453 （4） 決策樹算法決策樹算法 計 數(shù) 年齡收

27、入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 第第6步計算選擇節(jié)點步計算選擇節(jié)點 年齡信息增益=0.9537-0.6877 =0.2660 （1） 收入信息增益=0.9537-0.9361 =0.0176 （2） 年齡信息增益=0.9537-0.7811 =0.1726 （3） 信譽(yù)信息增益=0.9537-0.9048 =0.0453 （4）

28、決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128青中否良不買 64青低是良買 64青中是優(yōu)買 年齡年齡 青年 中年 老年 買/ 不買 買 買/ 不買 葉子 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128青中否良不買 64青低是良買 64青中是優(yōu)買 青年買與不買比例為128/256 S1(買)=128 S2（不買）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P1Log2

29、P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183 決策樹算法決策樹算法 計 數(shù) 年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？歸類：買計算機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128青中否良不買 64青低是良買 64青中是優(yōu)買 如果選擇收入作為節(jié)點 分高、中、低 平均信息期望（加權(quán)總和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591 I(0,128)=0 比例: 128/384=0.3333 I(6

30、4,128)=0.9183 比例: 192/384=0.5 I(64,0)=0 比例: 64/384=0.1667 注意 決策樹算法決策樹算法 計 數(shù) 年 齡 收入學(xué)生信譽(yù)歸類：買計算歸類：買計算 機(jī)？機(jī)？ 64青高否良不買 64青高否優(yōu)不買 128中高否良買 60老中否良買 64老低是良買 64老低是優(yōu)不買 64中低是優(yōu)買 128青中否良不買 64青低是良買 132老中是良買 64青中是優(yōu)買 32中中否優(yōu)買 32中高是良買 63老中否優(yōu)不買 1 老中否優(yōu)買 年齡年齡 青年 中年 老年 學(xué)生 買 信譽(yù) 葉子 否否是是優(yōu)優(yōu)良良 買 不買 買/ 不買 買 葉子 葉子葉子 決策樹算法決策樹算法 ID

31、3 決策樹建立算法決策樹建立算法 1 決定分類屬性； 2 對目前的數(shù)據(jù)表，建立一個節(jié)點N 3 如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個類，N就是樹葉，在樹葉上 標(biāo)出所屬的類 4 如果數(shù)據(jù)表中沒有其他屬性可以考慮，則N也是樹葉，按照少 數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別 5 否則，根據(jù)平均信息期望值E或GAIN值選出一個最佳屬性作 為節(jié)點N的測試屬性 6 節(jié)點屬性選定后，對于該屬性中的每個值： 從N生成一個分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形 成分支節(jié)點的數(shù)據(jù)表，在表中刪除節(jié)點屬性那一欄 如果分支數(shù)據(jù)表非空，則運(yùn)用以上算法從該節(jié)點建立子樹。 決策樹算法決策樹算法 決策樹的數(shù)據(jù)準(zhǔn)備決策樹的數(shù)據(jù)準(zhǔn)備

32、姓名姓名年齡年齡收入收入學(xué)生學(xué)生信譽(yù)信譽(yù)電話電話地址地址郵編郵編買計算機(jī)買計算機(jī) 張三張三234000是是良良281-322-03282714 Ave. M77388買買 李四李四342800否否優(yōu)優(yōu)713-239-78305606 Holly Cr78766買買 王二王二701900否否優(yōu)優(yōu)281-242-32222000 Bell Blvd.70244不買不買 趙五趙五18900是是良良281-550-0544100 Main Street 70244買買 劉蘭劉蘭342500否否優(yōu)優(yōu)713-239-7430606 Holly Ct78566買買 楊俊楊俊278900否否優(yōu)優(yōu)281-355

33、-7990233 Rice Blvd.70388不買不買 張毅張毅389500否否優(yōu)優(yōu)281-556-0544399 Sugar Rd.78244買買 。 。 。 原始表原始表 決策樹算法決策樹算法 計數(shù)年 齡 收 入 學(xué) 生 信譽(yù)歸類：歸類： 買計算買計算 機(jī)？機(jī)？ 64青 高否良不買 64青 高否優(yōu)不買 128中 高否良買 60老 中否良買 64老 低是良買 64老 低是優(yōu)不買 64中 低是優(yōu)買 128青 中否良不買 64青 低是良買 。 整理后的數(shù)據(jù)表整理后的數(shù)據(jù)表 決策樹的數(shù)據(jù)準(zhǔn)備決策樹的數(shù)據(jù)準(zhǔn)備 vData cleaning 刪除刪除/減少減少noise， 補(bǔ)填補(bǔ)填missing v

34、alues vData transformation 數(shù)據(jù)標(biāo)準(zhǔn)化（數(shù)據(jù)標(biāo)準(zhǔn)化（data normalization） 數(shù)據(jù)歸納（數(shù)據(jù)歸納（generalize data to higher-level concepts using concept hierarchies） 例如：年齡歸納為老、中、青三類例如：年齡歸納為老、中、青三類 控制每個屬性的可能值不超過七種控制每個屬性的可能值不超過七種 （最好不超過五種）（最好不超過五種） vRelevance analysis 對于與問題無關(guān)的屬性：刪對于與問題無關(guān)的屬性：刪 對于屬性的可能值大于七種對于屬性的可能值大于七種 又不能歸納的屬性：刪又不

35、能歸納的屬性：刪 決策樹算法決策樹算法 決策樹的數(shù)據(jù)準(zhǔn)備決策樹的數(shù)據(jù)準(zhǔn)備 決策樹算法決策樹算法 處理連續(xù)屬性值 決策樹算法比較適合處理離散數(shù)值的屬性。實際應(yīng)用中 屬性是連續(xù)的或者離散的情況都比較常見。 在應(yīng)用連續(xù)屬性值時，在一個樹結(jié)點可以將屬性Ai的值 劃分為幾個區(qū)間。然后信息增益的計算就可以采用和離散值 處理一樣的方法。原則上可以將Ai的屬性劃分為任意數(shù)目的 空間。C4.5中采用的是二元分割（Binary Split）。需要找出 一個合適的分割閾值。 參考C4.5算法 Top 10 algorithms in data mining Knowledge Information System

36、2008 14:137 決策樹算法決策樹算法 ID3算法小結(jié)算法小結(jié) ID3算法是一種經(jīng)典的決策樹學(xué)習(xí)算法，由Quinlan于1979年 提出。ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié) 點的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值 變?yōu)樽钚〉膶傩?，以?gòu)造一顆熵值下降最快的決策樹，到葉子節(jié) 點處的熵值為0。此時，每個葉子節(jié)點對應(yīng)的實例集中的實例屬于 同一類。 決策樹算法決策樹算法 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（1） 通過ID3算法來實現(xiàn)客戶流失的預(yù)警分析，找出客戶流失的 特征，以幫助電信公司有針對性地改善客戶關(guān)系，避免客戶流失 利

37、用決策樹方法進(jìn)行數(shù)據(jù)挖掘，一般有如下步驟：數(shù)據(jù)預(yù)處 理、決策樹挖掘操作，模式評估和應(yīng)用。 電信運(yùn)營商的客戶流失有三方面的含義：一是指客戶從一個 電信運(yùn)營商轉(zhuǎn)網(wǎng)到其他電信運(yùn)營商，這是流失分析的重點。二是 指客戶月平均消費(fèi)量降低，從高價值客戶成為低價值客戶。三、 指客戶自然流失和被動流失。 在客戶流失分析中有兩個核心變量：財務(wù)原因非財務(wù)原因、 主動流失被動流失。 客戶流失可以相應(yīng)分為四種類型：其中非財務(wù)原因主動流失 的客戶往往是高價值的客戶。他們會正常支付服務(wù)費(fèi)用，并容易 對市場活動有所響應(yīng)。這種客戶是電信企業(yè)真正需要保住的客戶。 決策樹算法決策樹算法 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)

38、用實例（在電信行業(yè)應(yīng)用實例（2） 數(shù)據(jù)預(yù)處理 數(shù)據(jù)挖掘的處理對象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲在數(shù) 據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲在其CRM中），是長期積累的 結(jié)果。但往往不適合直接挖掘，需要做數(shù)據(jù)的預(yù)處理工作，一般 包括數(shù)據(jù)的選擇(選擇相關(guān)的數(shù)據(jù))、凈化(消除冗余數(shù)據(jù))、轉(zhuǎn)換、 歸約等。數(shù)據(jù)預(yù)處理工作準(zhǔn)備是否充分，對于挖掘算法的效率乃 至正確性都有關(guān)鍵性的影響。 該公司經(jīng)過多年的電腦化管理，已有大量的客戶個人基本信息 (文中簡稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名 用戶號碼、用戶標(biāo)識、用戶身份證號碼(轉(zhuǎn)化為年齡)、在網(wǎng)時間 （竣工時間）、地址、職業(yè)、用戶類別、客戶流失（用戶狀態(tài)

39、） 等等，數(shù)據(jù)準(zhǔn)備時必須除掉表中一些不必要的屬性，一般可采用面 向?qū)傩缘臍w納等方法去掉不相關(guān)或弱相關(guān)屬性。 決策樹算法決策樹算法 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（3） 屬性刪除：將有大量不同取值且無概化操作符的屬性或者可用其 它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表 中的用戶標(biāo)識、身份證號碼等，它們的取值太多且無法在該取值 域內(nèi)找到概化操作符，應(yīng)將其刪除，得到表1。 表1 客戶信息表 年齡學(xué)歷職業(yè)繳費(fèi)方式在網(wǎng)時長費(fèi)用變化率客戶流失 58大學(xué)公務(wù)員托收1310%NO 47高中工人營業(yè)廳繳費(fèi)942%NO 26研究生公務(wù)員充值卡263%YES

40、28大學(xué)公務(wù)員營業(yè)廳繳費(fèi)52.91%NO 32初中工人營業(yè)廳繳費(fèi)32.3%NO 42高中無業(yè)人員充值卡2100%YES 68初中無業(yè)人員營業(yè)廳繳費(fèi)92.3%NO 決策樹算法決策樹算法 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（4） 屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆 進(jìn)行概化。文化程度分為3類：W1初中以下(含初中)，W2高中(含 中專)，W3大學(xué)(專科、本科及以上)；職業(yè)類別：按工作性質(zhì)來分 共分3類：Z1一Z3； 繳費(fèi)方式：托收：T1,營業(yè)廳繳費(fèi)：T2,充值卡：T3。 連續(xù)型屬性概化為區(qū)間值：表中年齡、費(fèi)用變化率和在網(wǎng)時間為 連續(xù)型數(shù)據(jù)，

41、由于建立決策樹時，用離散型數(shù)據(jù)進(jìn)行處理速度最 快，因此對連續(xù)型數(shù)據(jù)進(jìn)行離散化處理，根據(jù)專家經(jīng)驗和實際計 算信息增益，在“在網(wǎng)時長”屬性中，通過檢測每個劃分，得到在 閾值為5年時信息增益最大，從而確定最好的劃分是在5年處，則 這個屬性的范圍就變?yōu)?：H1,H2。而在“年齡”屬性中， 信息增益有兩個鋒值，分別在40和50處，因而該屬性的范圍變?yōu)?40-50即變?yōu)榍嗄辏心辏夏辏篘1,N2,N3；費(fèi) 用變化率：指（當(dāng)月話費(fèi)近3個月的平均話費(fèi)）/近3個月的平 均話費(fèi)）0，F(xiàn)1:30%，F(xiàn)2：30%-99%, F3:100%變?yōu)?F1,F2,F3。 表2 轉(zhuǎn)化后的客戶信息表 年齡學(xué)歷職業(yè)繳費(fèi)方式開戶時

42、間費(fèi)用變化率客戶流失 N3W3Z1T1H2F1NO N2W2Z2T2H2F2NO N1W3Z1T3H1F2YES N1W3Z1T2H1F1NO N1W1Z2T2H1F1NO N2W2Z3T3H1F3YES N3W1Z3T1H2F1NO 決策樹算法決策樹算法 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（5） YESNO 年 齡 職 業(yè) YES 繳費(fèi)方式 YES YES NO YSES NO NO 在網(wǎng)時長 NO F1 F2 F3 N1 N2 N3 T1T2 T3 Z1 Z2 Z3 H1 H2 費(fèi)用變化率 決策樹算法決策樹算法 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（6） 在圖中，NO表示客戶不流失，YES表示客戶流失。從圖可以看出，客戶費(fèi)用變化率 為100%的客戶肯定已經(jīng)流失；而費(fèi)用變化率低于30%的客戶；即每月資費(fèi)相對穩(wěn)定的客 戶一般不會流失，費(fèi)用變化率在30%99%的客戶有可能流失，其中年齡在4050歲之間