【正文】 決策樹分類 王成（副教授） 計算機科學(xué)與技術(shù)學(xué)院 主要內(nèi)容 ? 什么是決策樹 ? ID3算法 ? 算法改進 ? CART算法 Decision Tree Modeling 決策樹是一種簡單且應(yīng)用廣泛的 預(yù)測 方法 決策樹 圖 常見的決策樹形式 決策樹主要有二元分支（ binary split）樹和多分支（ multiway split）樹。一般時候采用二元分裂，因為二元分裂在窮舉搜索中更加靈活。 決策樹形式 決策樹 ? 決策樹 （ Decision Tree） 又稱為 判定樹 ， 是運用于分類的一種 樹結(jié)構(gòu) 。 其中的每個 內(nèi)部結(jié)點 （ internal node） 代表對某個屬性的一次 測試 ， 每條 邊 代表一個 測試結(jié)果 ， 葉結(jié)點 （ leaf） 代表某個 類 （ class） 或者 類的分布 （ class distribution） ， 最上面的結(jié)點是 根結(jié)點 ? 決策樹 提供了一種展示 在什么條件下 會得到 什么類別 這類規(guī)則 的方法 。 ? 下例是為了解決這個問題而建立的一棵 決策樹 ， 從中可以看到?jīng)Q策樹的基本組成部分： 決策結(jié)點 、 分支 和 葉結(jié)點 決策樹 ? 下圖給出了一個 商業(yè)上使用的決策樹 的例子 。 它表示了一個 關(guān)心電子產(chǎn)品的用戶是否會購買 PC（ buys_puter） 的知識 ， 用它可以 預(yù)測某條記錄 （ 某個人 ） 的購買意向 A g e ? C r e d i t _ r a t i n g ? s t u d e n t ? y e s no y e s y e s no = 3 0 ? 4 0 30 … 40 y e s no f a i r e x c e l l e n t 決策樹 ? 這棵決策樹對銷售記錄進行分類 ， 指出一個電子產(chǎn)品消費者是否會購買一臺計算機 “ buys_puter”。 每個內(nèi)部結(jié)點 (方形框 )代表對某個屬性的一次檢測 。 每個葉結(jié)點 (橢圓框 )代表一個類 : buys_puters=yes 或者 buys_puters=no ? 在這個例子中 ， 特征向量為： (age, student, credit_rating, buys_puters) ? 被決策數(shù)據(jù)的格式為 : (age, student, credit_rating) ? 輸入新的被決策的記錄 ， 可以預(yù)測該記錄隸屬于哪個類 。 使用決策樹進行分類 ? 第 1步：利用訓(xùn)練集 建立并精化一棵決策樹 ， 建立 決策樹模型 。 這個過程實際上是一個從數(shù)據(jù)中獲取知識 ， 進行機器學(xué)習(xí)的過程 ? 第 2步：利用生成完畢的 決策樹 對輸入數(shù)據(jù)進行 分類 。 對輸入的記錄 ， 從 根結(jié)點 依次測試記錄的 屬性值 ， 直到到達某個 葉結(jié)點 ， 從而找到該記錄所在的 類 主要內(nèi)容 ? 什么是決策樹 ? ID3算法 ? 算法改進 ? CART算法 如何從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)決策樹 ? ID Age Hasjob Own_house Credit_rating Class 1 Young False False Fair No 2 Young False False Good No 3 Young True False Good Yes 4 Young True True Fair Yes 5 Young False False Fair No 6 Middle False False Fair No 7 Middle False False Good No 8 Middle True True Good Yes 9 Middle False True Excellent Yes 10 Middle False True Excellent Yes 11 Old False True Excellent Yes 12 Old False True Good Yes 13 Old True False Good Yes 14 Old True False Excellent Yes 15 Old False False fair no 貸款申請數(shù)據(jù)集 如何從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)決策樹 ? Age？ young middle old No:3 Yes:2 No:2 Yes:3 No:4 Yes:1 Own_house？ true false No:0 Yes:6 No:6 Yes:3 (a) (b) 兩種可能的根節(jié)點選取方式 哪種更好？ ID3算法 ? ID3算法主要針對屬性選擇問題 ? 使用信息增益度選擇測試屬性 ID3決策樹建立算法 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é)點屬性那一欄 7如果分支數(shù)據(jù)表屬性非空，則轉(zhuǎn) 1，運用以上算法從該節(jié)點建立子樹 信息熵 (Entropy) ? 我們常說信息很多 ， 或信息很少 ， 但卻很難說清楚信息到底有多少 ? 比如一本 50多萬字的 《 史記 》 有多少信息量 ？ 或一套莎士比亞全集有多少信息量 ？ ? 這個問題幾千年來都沒有人給出很好的解答 ， 直到 1948年 ，香農(nóng) (Claude Shannon)在他著名的論文 “ 通信的數(shù)學(xué)原理 ”中提出了 信息熵 的概念 ， 才解決了 信息的度量問題 ， 并且量化出信息的作用 信息熵 (Entropy) ? 一條 信息的信息量 和它的 不確定性 有著直接的關(guān)系 ? 比如 ， 要搞清楚一件非常不確定的事 ， 或是我們一無所知的事情 ， 就需要了解大量信息 。 相反 ， 如果我們對某件事已經(jīng)有了較多了解 ， 那么不需要太多信息就能把它搞清楚 ? 從這個角度看 ， 信息量 就等于 不確定性的多少 ? 如何量化信息的度量呢 ？ 信息熵 (Entropy) ? 假如我錯過了一個有 32支球隊參加的足球賽 ， 賽后我問一個知道比賽結(jié)果的觀眾 “ 哪支球隊是冠軍 ” ？ 他不愿意直接告訴我 ， 而讓我猜 ， 每猜一次 ， 他要收一元錢才肯告訴我是否猜對 ， 那我需要付多少錢才能知道誰是冠軍呢 ？ 我可以把球隊編號 ， 從 1到 32， 然后問 “ 冠軍球隊在 116號中嗎 ？ ” ， 假如他告訴我猜對了 ， 我就接著問 “ 冠軍在18號中嗎 ？ ” ， 假如他說猜錯了 ， 那我就知道冠軍在 916號中 。 這樣只要 5次 ， 我就能知道哪支球隊是冠軍 當(dāng)然 ， 香農(nóng)不是用錢 ， 而是用比特 (bit)來度量信息量 ， 在上例中 ， 這條消息的信息量是 5比特 信息量的比特數(shù)和所有可能 情況的對數(shù)有關(guān)，例如本例 中，信息量 = log (球隊數(shù) )， 即 5 = log (32) 信息熵 (Entropy) ? 實際上可能不需要 5次就能猜出誰是冠軍 ， 因為一些強隊得冠的可能性更高 ， 因此第一次猜測時可以把少數(shù)幾支強隊分成一組 ， 其它球隊分成另一組 ， 然后猜冠軍球隊是否在那幾支強隊中 ? 這樣 ， 也許三次或四次就能猜出結(jié)果 。 因此 ， 當(dāng)每支球隊奪冠的可能性 (概率 )不等時 ， 這條信息的信息量比 5比特少 ? 香農(nóng)指出 ， 它的準(zhǔn)確信息量應(yīng)該是 )l o g...l o gl o g( 32322211 ppppppH ????????p1,p2,...,p32分別是這 32支球隊奪冠概率，香農(nóng)把它稱作 信息熵，單位為比特 ； 可以算出，當(dāng) 32支球隊奪冠概率相同時，對應(yīng)的信息熵為 5比特。 信息熵 (Entropy) 對于任意一個隨機變量 X(比如奪冠球隊 )，它的熵定義為 ????XxxPxPXH )(l o g)()(變量的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大 數(shù)據(jù)集的信息熵 設(shè)數(shù)據(jù)集 D中有 m個不同的類 C1, C2, C3, ..., Cm 設(shè) Ci,D是數(shù)據(jù)集 D中 Ci類的樣本的集合 , |D|和 |Ci,D|分別是 D和 Ci,D中的樣本個數(shù) 21( ) lo gmiiiInfo D p p??? ?其中 pi是 數(shù)據(jù)集 D中任意樣本屬于類 Ci的概率，用 估計 |||| ,DC Di數(shù)據(jù)集 D的信息熵 : 例 : 計算對下列數(shù)據(jù)集分類所需的信息熵 年齡 收入 學(xué)生 信用 買了電腦 30 高 否 一般 否 30 高 否 好 否 3040 高 否 一般 是 40 中等 否 一般 是 40 低 是 一般 是 40 低 是 好 否 3040 低 是 好 是 30 中 否 一般 否 30 低 是 一般 是 40 中 是 一般 是 30 中 是 好 是 3040 中 否 好 是 3040 高 是 一般 是 40 中 否 好 否 22()5 5 9 9l o g l o g1 4 1 4 1 4 1 40 . 9 4 0In fo D? ? ??|D|=14 |C1,D|=5 |C2,D|=9 使用熵衡量數(shù)據(jù)純度 假設(shè)有一個數(shù)據(jù)集合 D，其中只有兩個類，一個是正例類，一個是負(fù)例類 計算 D中正例類和負(fù)例類在三種不同的組分下熵的變化情況。 （ 1） D中包含有 50%的正例和 50%的負(fù)例。 H(D) = * * = 1 （ 2） D中包含有 20%的正例和 80%的負(fù)例。 H(D) = * * = （ 3） D中包含有 100%的正例和 0%的負(fù)例。 H(D) = 1 * log21 0 * log20 =0 可以看到一個趨勢， 當(dāng)數(shù)據(jù)變得越來越 “ 純 ” 時，熵的值變得越來越小 。 當(dāng) D中 正反例所占比例相同時，熵取最大值 。 當(dāng) D 中 所有數(shù)據(jù)都只屬于一個類時，熵得到最小值 。 因此 熵可以作為數(shù)據(jù)純凈度或混亂度的衡量指標(biāo) 。這正是決策樹學(xué)習(xí)中 需要的。 數(shù)據(jù)集的信息熵 假設(shè)按屬性 A 劃分 D 中的樣本，且屬性 A 根據(jù)訓(xùn)練數(shù)據(jù)的觀測具有 v 個不同取值 { a1, a2, ..., aj , ..., av }。 如果 A 是 離散值 ，可依屬性 A 將 D 劃分為 v 個子集 { D1, D2, ..., Dj , ..., Dv } 其中， Dj為 D中的樣本子集，它們在 A上具有屬性值 aj 這些劃分將對應(yīng)于從該節(jié)點 A出來的分支。 按屬性 A對 D劃分后，數(shù)據(jù)集