【正文】 ID3的改進 ? 改進 1：用 信息增益率 代替 信息增益 來選擇 屬性 ? 改進 2：能夠完成對 連續(xù)值屬性 的 離散化處理 ? 改進 3：能處理 屬性值缺失 的情況 ? 改進 4：在決策樹構(gòu)造完成之后進行 剪枝 十大數(shù)據(jù)挖掘算法 kMeans SVM Apriori EM PageRank AdaBoost kNN Na239。 按屬性 A對 D劃分后，數(shù)據(jù)集的信息熵 : 1( ) * ( )vjAjjDInfo D Info DD?????????? ???????其中， 充當?shù)? j 個劃分的權重。 因此 熵可以作為數(shù)據(jù)純凈度或混亂度的衡量指標 。 H(D) = * * = （ 3） D中包含有 100%的正例和 0%的負例。 因此 ， 當每支球隊奪冠的可能性 (概率 )不等時 ， 這條信息的信息量比 5比特少 ? 香農(nóng)指出 ， 它的準確信息量應該是 )l o g...l o gl o g( 32322211 ppppppH ????????p1,p2,...,p32分別是這 32支球隊奪冠概率，香農(nóng)把它稱作 信息熵，單位為比特 ； 可以算出，當 32支球隊奪冠概率相同時，對應的信息熵為 5比特。 這個過程實際上是一個從數(shù)據(jù)中獲取知識 ， 進行機器學習的過程 ? 第 2步：利用生成完畢的 決策樹 對輸入數(shù)據(jù)進行 分類 。 它表示了一個 關心電子產(chǎn)品的用戶是否會購買 PC（ buys_puter） 的知識 ， 用它可以 預測某條記錄 （ 某個人 ） 的購買意向 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”。一般時候采用二元分裂，因為二元分裂在窮舉搜索中更加靈活。決策樹主要有二元分支（ binary split）樹和多分支（ multiway split）樹。 ? 下例是為了解決這個問題而建立的一棵 決策樹 ， 從中可以看到?jīng)Q策樹的基本組成部分： 決策結(jié)點 、 分支 和 葉結(jié)點 決策樹 ? 下圖給出了一個 商業(yè)上使用的決策樹 的例子 。 使用決策樹進行分類 ? 第 1步：利用訓練集 建立并精化一棵決策樹 ， 建立 決策樹模型 。 這樣只要 5次 ， 我就能知道哪支球隊是冠軍 當然 ， 香農(nóng)不是用錢 ， 而是用比特 (bit)來度量信息量 ， 在上例中 ， 這條消息的信息量是 5比特 信息量的比特數(shù)和所有可能 情況的對數(shù)有關，例如本例 中，信息量 = log (球隊數(shù) )， 即 5 = log (32) 信息熵 (Entropy) ? 實際上可能不需要 5次就能猜出誰是冠軍 ， 因為一些強隊得冠的可能性更高 ， 因此第一次猜測時可以把少數(shù)幾支強隊分成一組 ， 其它球隊分成另一組 ， 然后猜冠軍球隊是否在那幾支強隊中 ? 這樣 ， 也許三次或四次就能猜出結(jié)果 。 H(D) = * * = 1 （ 2） D中包含有 20%的正例和 80%的負例。 當 D 中 所有數(shù)據(jù)都只屬于一個類時，熵得到最小值 。 如果 A 是 離散值 ，可依屬性 A 將 D 劃分為 v 個子集 { D1, D2, ..., Dj , ..., Dv } 其中， Dj為 D中的樣本子集，它們在 A上具有屬性值 aj 這些劃分將對應于從該節(jié)點 A出來的分支。 決策樹技術發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是采用 遞歸分割的貪婪算法 。 信息增益度量 偏向于對 取值較多 的 屬性 進行測試，即它傾向于選擇 v較大 的 屬性 A 舉個極端的例子：考慮充當唯一標識的屬性 PID。 假設一連續(xù)值屬性共有 N個不同的屬性值，則可找到 N1個可能的 分裂點 。 由于訓練樣本缺乏代表性的樣本 ， 在沒有多少訓練記錄的情況下 ， 學習算法仍然繼續(xù)細化模型就會導致過度擬合 改進 4： 缺乏代表性樣本所導致的過度擬合 名稱 體溫 胎生 4條腿 冬眠 哺乳動物 蠑螈 冷血 N Y Y N 虹鳉 冷血 Y N N N 鷹 恒溫 N N N N 弱夜鷹 恒溫 N N Y N 鴨嘴獸 恒溫 Y Y Y Y 哺乳動物分類的訓練樣例 名稱 體溫 胎生 4條腿 冬眠 哺乳動物 人 恒溫 Y N N Y 大象 恒溫 Y Y N Y 鴿子 恒溫 N N N N 體溫 恒溫 冷血 冬眠 N Y N N 4條腿 Y N N Y 按照訓練模型。 哺乳動物分類的測試樣例 改進 4：決策樹剪枝 How? 預剪枝(prepruning) 后剪枝(postpruning) 在完全正確分類訓練集之前就停止樹的生長。 1. 自底向上的遍歷每一個非葉節(jié)點 (除了根節(jié)點 )，將當前的非葉節(jié)點從樹中減去，其下所有的葉節(jié)點合并成一個節(jié)點，代替原來被剪掉的節(jié)點。 回歸樹（ Regression Tree） R e g r e s s i o n T r e eR M 6 . 9N O X . 6 6N O X . 6 716R M 6 . 5 14N O X . 5 122 N O X . 6 3272719R M 7 . 44633因變量 continuous ， 葉子為 因變量 的預測值。 選擇具有最小 Gini指標 (或最大 ?Gini)的屬性作為 分裂屬性 )()()( DG i n iDG i n iAG i n i A???處理離散值屬性 以收入為例，對收入屬性的所有可能子集： {低，中，高 }， {低，中 }， {低，高 }， {中，高 }， {低 }， {中 }， {高 } 考慮所有可能的二元劃分，并計算劃分前后的 Gini指標， 選擇能產(chǎn)生最小 Gini指標的子集作為分裂子集 收入 ∈ {中，高 } ... ... 是 否 回歸樹的生成 ◇ 數(shù)據(jù)： N個觀測， p個自變量， 1個因變量 (連續(xù)型 ) ◇ 目標：自動地選擇分裂變量及其分裂點 假設有一個分裂把自變量空間分成 M個區(qū)域 : 在每個區(qū)域，我們用一個常數(shù)來擬合因變量： 12, ,..., MR R R1( ) ( )Mmmmf x c I x R???? 優(yōu)化目標：誤差平方和最小 上最優(yōu)的擬合解為 2m in ( ( ))iiiy f x??MR? ( | )m i i mc avey x R??從根節(jié)點開始 ， 考慮一個分裂變量 j和分裂點 s， 得到 2個區(qū)域： 最優(yōu)的變量 j和分裂點 s， 要滿足 對于給定的 j和 s， 最里層的優(yōu)化問題的解為 而對于給定的 j,分裂點 s很快能找到 . 這樣 ， 遍歷所有的自變量 ， 就能找到最佳的一對 j和 s. 遞歸分割 greedy algorithm 12(,) { | }, and (,) { | }jjRjs XX s Rjs XX s? ? ? ?12122212,( , ) ( , )min min ( ) min ( )iiiijs c cx R js x R jsy c y c????? ? ???????1 1 2 2? ?(| (,)), and (| (,))ii iicaveyxRjs caveyxRjs? ? ? ?剪枝 ? 最大的決策樹能對訓練集的準確率達到 100%， 最大的分類樹的結(jié)果會導致過擬合 （ 對信號和噪聲都適應 ） 。 這里介紹 costplexity pruning。ve Bayes CART 高伸縮性決策樹算法 ? SLIQ、 SPRINT、 BOAT 決策樹基本概念 決策樹的優(yōu)點 推理過程容易理解，決策推理過程可以表示成 If Then形式； 推理過程完全依賴于屬性變量的取值特點； 可自動忽略目標變量沒有貢獻的屬性變量，也為判斷屬性 變量的重要性，減少變量的數(shù)目提供參考。 歸納推理試圖從對象的一部分或整體的特定的觀察中獲得 一個完備且正確的描述。 決策樹基本概念 關于歸納學習 (2) 歸納學習的過程就是尋找一般化描述的過程。該假定是歸納學習的有效性的前提條件。將描述逐步一般化。每個例子都是一個 對偶（序偶）（ x, f(x)），對每個輸入的 x，都有確定的輸出 f(x)。例如， y=ax+b。 一般方法如定義為使訓練值與假設值 預測出的值之間的誤差平方 和 E最小為最佳。多數(shù)情況下，為了高效地搜索，可以 利用假設空間中一種自然形成的結(jié)構(gòu)，即一般到特殊的偏序關系。 H中每個假設 h表 示 X上定義的布爾函數(shù)。 （ Function Approximation）。 1979年 , . Quinlan 給出 ID3算法 ， 并在 1983年和 1986年對 ID3 進行了總結(jié)和簡化 ， 使其成為決策樹學習算法的典型 。 另一類決策樹算法為 CART， 與 ， CART的決策樹由二元邏輯問題生成 ， 每個樹節(jié)點只有兩個分枝 ， 分別包括學習實例的正例與反例 。 ? 從根節(jié)點到葉節(jié)點的每一條路經(jīng)都對應著一條合理的規(guī)則 ，規(guī)則間各個部分 （ 各個層的條件 ） 的關系是合取關系 。 如果在應用中發(fā)現(xiàn)不符合規(guī)則的實例 ， 程序會詢問用戶該實例的正確分類 ，從而生成新的分枝和葉子 ， 并添加到樹中 。 ? 決策樹是描述分類過程的一種數(shù)據(jù)結(jié)構(gòu) ， 從上端的根節(jié)點開始 ， 各種分類原則被引用進來 ， 并依這些分類原則將根節(jié)點的數(shù)據(jù)集劃分為子集 ， 這一劃分過程直到某種約束條件滿足而結(jié)束 。 可以通過對結(jié)構(gòu)進行廣度優(yōu)先搜索 ， 并在每個節(jié)點生成 “ IF… THEN”規(guī)則來實現(xiàn) 。 ? 設計分類停止條件 ， 實際應用中數(shù)據(jù)的屬性很多 ， 真正有分類意義的屬性往往是有限幾個 ， 因此在必要的時候應該停止數(shù)據(jù)集分裂： ? 該節(jié)點包含的數(shù)據(jù)太少不足以分裂， ? 繼續(xù)分裂數(shù)據(jù)集對樹生成的目標 (例如 ID3中的熵下降準則 )沒有貢獻， ? 樹的深度過大不宜再分。 決策樹的基本原理 決策樹應用 它經(jīng)常作為很多熟悉模型（如回歸模型）的輔助工具。 對數(shù)據(jù)的要求 ? 進行分析時 ， 決策樹對變量的量綱的差異 、 離群值的存在以及有偏分布不太敏感 ， 也就是說對數(shù)據(jù)準備要求不高 。 ? 而回歸模型的回歸系數(shù)具有可解釋性 ， 在流行病學研究中 ， 對致病因素的效應 ， 常用一些危險度指標來衡量因素與發(fā)病 （ 或死亡 ） 的聯(lián)系程度或?qū)θ巳喊l(fā)病的致病作用的大小均可通過擬合該模型得出 。 謝謝！ 演講完畢，謝謝觀看！