【正文】 ? 什么是決策樹 ? ID3算法 ? 算法改進(jìn) ? CART算法 ID3的改進(jìn) ? 改進(jìn) 1：用 信息增益率 代替 信息增益 來選擇 屬性 ? 改進(jìn) 2：能夠完成對 連續(xù)值屬性 的 離散化處理 ? 改進(jìn) 3：能處理 屬性值缺失 的情況 ? 改進(jìn) 4：在決策樹構(gòu)造完成之后進(jìn)行 剪枝 十大數(shù)據(jù)挖掘算法 kMeans SVM Apriori EM PageRank AdaBoost kNN Na239。 本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程 。 按屬性 A對 D劃分后，數(shù)據(jù)集的信息熵 : 1( ) * ( )vjAjjDInfo D Info DD?????????? ???????其中， 充當(dāng)?shù)? j 個劃分的權(quán)重。 數(shù)據(jù)集的信息熵 假設(shè)按屬性 A 劃分 D 中的樣本，且屬性 A 根據(jù)訓(xùn)練數(shù)據(jù)的觀測具有 v 個不同取值 { a1, a2, ..., aj , ..., av }。 因此 熵可以作為數(shù)據(jù)純凈度或混亂度的衡量指標(biāo) 。 當(dāng) D中 正反例所占比例相同時，熵取最大值 。 H(D) = * * = （ 3） D中包含有 100%的正例和 0%的負(fù)例。 （ 1） D中包含有 50%的正例和 50%的負(fù)例。 因此 ， 當(dāng)每支球隊(duì)奪冠的可能性 (概率 )不等時 ， 這條信息的信息量比 5比特少 ? 香農(nóng)指出 ， 它的準(zhǔn)確信息量應(yīng)該是 )l o g...l o gl o g( 32322211 ppppppH ????????p1,p2,...,p32分別是這 32支球隊(duì)奪冠概率，香農(nóng)把它稱作 信息熵，單位為比特 ； 可以算出，當(dāng) 32支球隊(duì)奪冠概率相同時，對應(yīng)的信息熵為 5比特。 相反 ， 如果我們對某件事已經(jīng)有了較多了解 ， 那么不需要太多信息就能把它搞清楚 ? 從這個角度看 ， 信息量 就等于 不確定性的多少 ? 如何量化信息的度量呢 ？ 信息熵 (Entropy) ? 假如我錯過了一個有 32支球隊(duì)參加的足球賽 ， 賽后我問一個知道比賽結(jié)果的觀眾 “ 哪支球隊(duì)是冠軍 ” ？ 他不愿意直接告訴我 ， 而讓我猜 ， 每猜一次 ， 他要收一元錢才肯告訴我是否猜對 ， 那我需要付多少錢才能知道誰是冠軍呢 ？ 我可以把球隊(duì)編號 ， 從 1到 32， 然后問 “ 冠軍球隊(duì)在 116號中嗎 ？ ” ， 假如他告訴我猜對了 ， 我就接著問 “ 冠軍在18號中嗎 ？ ” ， 假如他說猜錯了 ， 那我就知道冠軍在 916號中 。 這個過程實(shí)際上是一個從數(shù)據(jù)中獲取知識 ， 進(jìn)行機(jī)器學(xué)習(xí)的過程 ? 第 2步：利用生成完畢的 決策樹 對輸入數(shù)據(jù)進(jìn)行 分類 。 每個葉結(jié)點(diǎn) (橢圓框 )代表一個類 : buys_puters=yes 或者 buys_puters=no ? 在這個例子中 ， 特征向量為： (age, student, credit_rating, buys_puters) ? 被決策數(shù)據(jù)的格式為 : (age, student, credit_rating) ? 輸入新的被決策的記錄 ， 可以預(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 決策樹 ? 這棵決策樹對銷售記錄進(jìn)行分類 ， 指出一個電子產(chǎn)品消費(fèi)者是否會購買一臺計(jì)算機(jī) “ buys_puter”。 其中的每個 內(nèi)部結(jié)點(diǎn) （ internal node） 代表對某個屬性的一次 測試 ， 每條 邊 代表一個 測試結(jié)果 ， 葉結(jié)點(diǎn) （ leaf） 代表某個 類 （ class） 或者 類的分布 （ class distribution） ， 最上面的結(jié)點(diǎn)是 根結(jié)點(diǎn) ? 決策樹 提供了一種展示 在什么條件下 會得到 什么類別 這類規(guī)則 的方法 。一般時候采用二元分裂，因?yàn)槎至言诟F舉搜索中更加靈活。決策樹分類 王成（副教授） 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 主要內(nèi)容 ? 什么是決策樹 ? ID3算法 ? 算法改進(jìn) ? CART算法 Decision Tree Modeling 決策樹是一種簡單且應(yīng)用廣泛的 預(yù)測 方法 決策樹 圖 常見的決策樹形式 決策樹主要有二元分支（ binary split）樹和多分支（ multiway split）樹。 決策樹形式 決策樹 ? 決策樹 （ Decision Tree） 又稱為 判定樹 ， 是運(yùn)用于分類的一種 樹結(jié)構(gòu) 。 ? 下例是為了解決這個問題而建立的一棵 決策樹 ， 從中可以看到?jīng)Q策樹的基本組成部分： 決策結(jié)點(diǎn) 、 分支 和 葉結(jié)點(diǎn) 決策樹 ? 下圖給出了一個 商業(yè)上使用的決策樹 的例子 。 每個內(nèi)部結(jié)點(diǎn) (方形框 )代表對某個屬性的一次檢測 。 使用決策樹進(jìn)行分類 ? 第 1步：利用訓(xùn)練集 建立并精化一棵決策樹 ， 建立 決策樹模型 。 對輸入的記錄 ， 從 根結(jié)點(diǎn) 依次測試記錄的 屬性值 ， 直到到達(dá)某個 葉結(jié)點(diǎn) ， 從而找到該記錄所在的 類 主要內(nèi)容 ? 什么是決策樹 ? ID3算法 ? 算法改進(jìn) ? 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é)點(diǎn)選取方式 哪種更好？ ID3算法 ? ID3算法主要針對屬性選擇問題 ? 使用信息增益度選擇測試屬性 ID3決策樹建立算法 1 決定分類屬性集合； 2 對目前的數(shù)據(jù)表，建立一個節(jié)點(diǎn) N 3 如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個類， N就是樹葉，在樹葉上 標(biāo)出所屬的類 (純的類別 ) 4 如果數(shù)據(jù)表中沒有其他屬性可以考慮，則 N也是樹葉，按照少 數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別 (不純的類別 ) 5 否則， 根據(jù)平均信息期望值 E或 GAIN值選出一個最佳屬性作 為節(jié)點(diǎn) N的測試屬性 6 節(jié)點(diǎn)屬性選定后，對于該屬性中的每個值： 從 N生成一個分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形 成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄 7如果分支數(shù)據(jù)表屬性非空，則轉(zhuǎn) 1，運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹 信息熵 (Entropy) ? 我們常說信息很多 ， 或信息很少 ， 但卻很難說清楚信息到底有多少 ? 比如一本 50多萬字的 《 史記 》 有多少信息量 ？ 或一套莎士比亞全集有多少信息量 ？ ? 這個問題幾千年來都沒有人給出很好的解答 ， 直到 1948年 ，香農(nóng) (Claude Shannon)在他著名的論文 “ 通信的數(shù)學(xué)原理 ”中提出了 信息熵 的概念 ， 才解決了 信息的度量問題 ， 并且量化出信息的作用 信息熵 (Entropy) ? 一條 信息的信息量 和它的 不確定性 有著直接的關(guān)系 ? 比如 ， 要搞清楚一件非常不確定的事 ， 或是我們一無所知的事情 ， 就需要了解大量信息 。 這樣只要 5次 ， 我就能知道哪支球隊(duì)是冠軍 當(dāng)然 ， 香農(nóng)不是用錢 ， 而是用比特 (bit)來度量信息量 ， 在上例中 ， 這條消息的信息量是 5比特 信息量的比特?cái)?shù)和所有可能 情況的對數(shù)有關(guān)，例如本例 中，信息量 = log (球隊(duì)數(shù) )， 即 5 = log (32) 信息熵 (Entropy) ? 實(shí)際上可能不需要 5次就能猜出誰是冠軍 ， 因?yàn)橐恍?qiáng)隊(duì)得冠的可能性更高 ， 因此第一次猜測時可以把少數(shù)幾支強(qiáng)隊(duì)分成一組 ， 其它球隊(duì)分成另一組 ， 然后猜冠軍球隊(duì)是否在那幾支強(qiáng)隊(duì)中 ? 這樣 ， 也許三次或四次就能猜出結(jié)果 。 信息熵 (Entropy) 對于任意一個隨機(jī)變量 X(比如奪冠球隊(duì) )，它的熵定義為 ????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的概率，用 估計(jì) |||| ,DC Di數(shù)據(jù)集 D的信息熵 : 例 : 計(jì)算對下列數(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，其