分類模型算法決策樹

1、八斗大數(shù)據(jù)培訓分類算法-決策樹決策樹 八 斗 大 數(shù) 據(jù)， 盜 版 決策樹簡介ID3算法C4.5、CART算法【實踐】決策樹 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹O u t L i n e 樹形結(jié)構(gòu)決策規(guī)則 分類問題，對樣本： 從根節(jié)點出發(fā) 根據(jù)節(jié)點規(guī)則決定走哪個子節(jié)點 一直走到葉子節(jié)點 根據(jù)葉子節(jié)點的輸出規(guī)則輸出 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 例子：評估 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 - 例 子八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 - 例 子 如何做到？計數(shù)收入學生信譽是否64青高

2、否良否64青高否優(yōu)否128中高否良買60老中否良買64老低是良買64老低是優(yōu)否64中低是優(yōu)買128青中否良否64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買64 八老 斗 大 數(shù)據(jù)中否， 盜 版 否作為根節(jié)點 青年，否，買 中年，買 老年，否，買 “中年”停止分解，“青年”、“老年”繼續(xù)分解 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 - 例 子 對“青年”分解 經(jīng)分析，高收入和低收入，只對應(yīng)一個簽作為葉子節(jié)點，停止，直接將該標 八 斗 大 數(shù) 據(jù)， 盜 版 計數(shù)收入學生信譽是否64青高否良否64青高否優(yōu)否128青中否良否64青低是良買64青

3、中是優(yōu)買八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 - 例 子 對“中收入人群”繼續(xù)分解 經(jīng)分析，學生特征可以完全區(qū)分，停止 八 斗 大 數(shù) 據(jù)， 盜 版 計數(shù)收入學生信譽是否128青中否良否64青中是優(yōu)買八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 - 例 子 于是生成“青年”側(cè)的決策樹 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 - 例 子 對最終的結(jié)果進行概率計算 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹決 策 樹 - 例 子 提前將各個特征值離散化：0（青年）,1（中年）,2（老年） 收入：0（高收入），1（中收入），2（低收入） 學生：0（是

4、），1（否） 信譽：0（優(yōu)），1（良） 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹特 征 離 散 化 不確定性函數(shù)I稱為的信息量，U發(fā)生概率p的單調(diào)遞減函數(shù)：1=𝑙𝑜𝑔𝐼𝑈= 𝑙𝑜𝑔𝑝𝑝 信息熵：一個信源中，不能僅考慮單一發(fā)生的不確定性，需要考慮所有可能情況的平均不確定性，為𝑙𝑜𝑔 𝑝 的統(tǒng)計平均值E𝐻𝑈= 𝐸

5、;𝑙𝑜𝑔𝑝 𝑢𝑖= 𝑝 𝑢𝑖𝑖𝑙𝑜𝑔𝑝 𝑢𝑖 信息熵是事物不確定性的度量標準 決策樹中，不僅可用來度量類別不確定性，也可以度量包含不同特征的數(shù)據(jù)樣本與類別的不確定性。 熵越大，不確定性越大，即度越大 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 熵 ， 香 農(nóng) 定 理 學習算法 給定訓練數(shù)據(jù)，決定樹的結(jié)構(gòu) 節(jié)點規(guī)則 葉子

6、結(jié)點輸出規(guī)則 著名算法 ID3 C4.5 連續(xù)變量、缺省值、剪枝等 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹學 習 算 法 簡 介決策樹簡介ID3算法C4.5、CART算法【實踐】決策樹 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹O u t L i n e ID3 輸入：離散值（屬性） 使用信息增益來學習 信息熵（Entropy） S是樣例集合規(guī)則𝐻𝑆= 𝑝𝑖𝑢𝑖𝑙𝑜𝑔𝑝𝑢w

7、894; p(ui)表示S中第i類樣例的比例 信息增益： 用規(guī)則r將樣例集合S分為k個子集S1、Sk | · |表示集合元素個數(shù) 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹I D 3 學 習 算 法 節(jié)點規(guī)則： 按屬性：k種可能的屬性值->k個子集 學習問題：挑那種屬性？ ID3算法：信息增益最大的！ 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹I D 3 學 習 算 法 設(shè)S是s個數(shù)據(jù)樣本的集合，假定類別具有m個不同值，定義m個不同類𝐶𝑖𝑖 = 1,2, , 𝑚 ，設(shè)Ү

8、78;𝑖是𝐶𝑖的樣本數(shù)，對于一個給定的樣本分類所需要的信息熵由下式給出：𝐼𝑠1, 𝑠2, , 𝑠𝑚= 𝑝𝑖𝑙𝑜𝑔𝑖𝑝𝑖𝑠𝑖 𝑝 是任意樣本屬于𝐶 的概率，并用𝑝=估計𝑖𝑖𝑖𝑆 八 斗 大 數(shù) 據(jù)， 盜

9、 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 如 何 計 算 ？ 用信息熵來度量每種特征不同取值的不確定性 設(shè)A具有v個不同的值𝑎1, 𝑎2, 𝑎𝑣 某一特征A將S劃分為v個不同的子集𝑆1, 𝑆2, 𝑆𝑣， 其中𝑆𝑗包含S中這樣一些樣本：他們在A上具有值𝑎𝑗，若選A作測試特征，即最優(yōu)劃分特征，那么這些子集就是S節(jié)點中生長出來的決策樹分支。設(shè)𝑠𝑖𝑗是子集

10、𝑆𝑗中類𝐶𝑖的樣本數(shù)。 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 如 何 計 算 ？ 由A劃分成子集的熵或期望信息由下式給出：𝑣𝑠1𝑗+ 𝑠2𝑗 + + 𝑠m𝑗𝐸𝐴= 𝑗=1𝐼𝑠1𝑗, 𝑠2𝑗, , 𝑠m𝑗𝑠

11、19904;+𝑠+𝑠 其中，是第j個子集的權(quán)，并且等于子集（即A值為𝑎 ）中的樣本個數(shù)1𝑗2𝑗m𝑗𝑗𝑠除以S中的樣本總數(shù)，其信息熵值越小，子集劃分的純度越高𝑚= 𝑝𝑖𝑗𝑙𝑜𝑔𝑖=1 其中，𝑠𝑖𝑗𝑝𝑖𝑗=𝐼𝑠1

12、9895;, 𝑠2𝑗, , 𝑠m𝑗𝑝𝑖𝑗𝑠𝑗 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 如 何 計 算 ？ 最后，實用信息增益確定決策樹分支的劃分依據(jù)Gain(A) = 𝐼- E(A)𝑠1, 𝑠2, , 𝑠𝑚 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 如 何 計 算 ？ 接前面例子： 類別S劃分為兩類：買或

13、不買𝑆1(買) =640𝑆1(不買) =384 總體S=S1+S2=1024384640𝑝= 0.375𝑝= 0.6252110241024 根據(jù)公式：𝑚𝐼𝑠1, 𝑠2= 0.9544𝐼𝑠 , 𝑠, , 𝑠= 𝑝 𝑙𝑜𝑔𝑝12m𝑖𝑖𝑖=1 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)

14、培訓分類算法-決策樹信 息 增 益 計 算 舉 例 接下來計算每個特征的信息熵 1、先計算“”特征的熵，共分3組，青年（0），中年（1），老年（2） 其中青年占總樣本的概率為p(0)=384/1024=0.375 青年中的買/不買=128/256 所以：S1(買)=128，p1=128/384S2(不買)=256，p2=256/384S=S1+S2=384𝑚= 𝑝𝑖𝑙𝑜𝑔𝐼𝑠1, 𝑠2= 0.9183 根據(jù)公式𝐼𝑠1,

15、𝑠2, , 𝑠m𝑝𝑖 八 斗 大 數(shù) 據(jù)𝑖， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 計 算 舉 例 其中中年占總樣本的概率為p(1)=256/1024=0.25 中年中的買/不買=256/0 所以：S1(買)=256，p1=1S2(不買)=0，p2=0S=S1+S2=256 根據(jù)公式𝑚= 𝑝𝑖𝑙𝑜𝑔𝑖=1𝐼𝑠1, 𝑠2= 0𝐼

16、𝑠1, 𝑠2, , 𝑠m𝑝𝑖 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 計 算 舉 例 其中老年占總樣本的概率為p(1)=384/1024=0.375 老年中的買/不買=256/128 所以：S1(買)=256，p1=256/384S2(不買)=128，p2=128/384S=S1+S2=384 根據(jù)公式𝑚= 𝑝𝑖𝑙𝑜𝑔𝑖=1𝐼𝑠1, &#

17、119904;2= 0.9157𝐼𝑠1, 𝑠2, , 𝑠m𝑝𝑖 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 計 算 舉 例 所以匯總 “ E( G(”的平均信息期望：)=0.375*0.9183+0.25*0+ 0.375*0.9157=0.6877)=0.9544-0.6877=0.2667從所有特征中選擇信息增益最大的作 同理： E(學生)=0.7811 E(收入)=0.9361 E(信譽)=0.9048為根節(jié)點或者內(nèi)部節(jié)點，根據(jù)計算，G(學生)=0.1733G(

18、收入)=0.0183 G(信譽)=0.0496首次選取“”來劃分 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 計 算 舉 例 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 計 算 舉 例 ID3(Dataset, attrList)終止條件1、創(chuàng)建根節(jié)點R2、如果當前Dataset中數(shù)據(jù)是“純”的：將R的節(jié)點類型標記為當前類型3、如果當attrList為空：將R的節(jié)點類型標記為當前Dataset中，樣例個數(shù)最多的類型4、其余情況：1) 從attrList中選擇屬性A2) 按照屬性A所有的不同值𝑉𝑖 ，

19、將Dataset分為不同的子集𝐷𝑖，對于每個𝐷𝑖a) 創(chuàng)建節(jié)點Cb) 如果𝐷𝑖為空：節(jié)點C標記為Dataset中，樣例個數(shù)最多的類型c) 𝐷𝑖不為空：節(jié)點C=ID3(𝐷𝑖，attrList-A)d) 將節(jié)點C添加為R的子節(jié)點5、返回R 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹I D 3 學 習 算 法 ID3(Dataset, attrList)終止條件1、創(chuàng)建根節(jié)點R2、如果當前Dataset中數(shù)據(jù)是“純”的：將R

20、的節(jié)點類型標記為當前類型3、如果當attrList為空：將R的節(jié)點類型標記為當前Dataset中，樣例個數(shù)最多的類型4、其余情況：1) 從attrList中選擇屬性A2) 按照屬性A所有的不同值𝑉𝑖 ，將Dataset分為不同的子集𝐷𝑖，對于每個𝐷𝑖a) 創(chuàng)建節(jié)點Cb) 如果𝐷𝑖為空：節(jié)點C標記為Dataset中，樣例個數(shù)最多的類型c) 𝐷𝑖不為空：節(jié)點C=ID3(𝐷𝑖，attrList-A)d) 將節(jié)點

21、C添加為R的子節(jié)點5、返回R遞歸條件 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹I D 3 學 習 算 法 ID3(Dataset, attrList)1、創(chuàng)建根節(jié)點R2、如果當前Dataset中數(shù)據(jù)是“純”的：將R的節(jié)點類型標記為當前類型3、如果當attrList為空：將R的節(jié)點類型標記為當前Dataset中，樣例個數(shù)最多的類型4、其余情況：1) 從attrList中選擇屬性A2) 按照屬性A所有的不同值𝑉𝑖 ，將Dataset分為不同的子集𝐷𝑖，對于每個𝐷𝑖a) 創(chuàng)建節(jié)點Cb)

22、 如果𝐷𝑖為空：節(jié)點C標記為Dataset中，樣例個數(shù)最多的類型c) 𝐷𝑖不為空：節(jié)點C=ID3(𝐷𝑖，attrList-A)d) 將節(jié)點C添加為R的子節(jié)點5、返回R 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹I D 3 學 習 算 法 缺點？ 傾向于挑選屬性值較多的屬性，有些情況可能 貪婪性提供太多有價值的信息剃刀原理：盡量用較少的東西做的事 不適用于連續(xù)變量 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹I D 3 算 法決策樹簡介ID3算法C4.5、CART算法

23、【實踐】決策樹 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹O u t L i n e 相對于ID3： 克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足 支持連續(xù)變量 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹C 4 . 5 算 法 信息增益率：𝑚= 𝑝 𝑢𝑖𝑙𝑜𝑔i=1𝐻𝑆𝑝𝑢𝑖𝑆𝑣𝐺𝑎𝑖

24、;𝑛𝑆, 𝐴= 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝑆) 𝑣𝑉𝑎𝑙𝑢𝑒(𝐴)𝐸𝑛𝑡𝑟𝑜𝑝𝑦𝑆𝑣𝑆𝐺𝑎𝑖𝑛(&

25、#119860;)𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜 𝐴=𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝐴)屬性A的分布情況，度越大，ratio越小，越純凈，ratio越大 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹信 息 增 益 率 C4.5(Dataset, attrList)1、創(chuàng)建根節(jié)點R2、如果當前Dataset中數(shù)據(jù)是“純”的

26、或其他終止條件：將R的節(jié)點類型標記為當前類型3、如果當attrList為空：將R的節(jié)點類型標記為當前Dataset中，樣例個數(shù)最多的類型4、其余情況：1) 從attrList中選擇gainratio最大的屬性A2) 按照屬性A所有的不同值𝑉𝑖 ，將Dataset分為不同的子集𝐷𝑖，對于每個𝐷𝑖a) 創(chuàng)建節(jié)點Cb) 如果𝐷𝑖為空：節(jié)點C標記為Dataset中，屬性值個數(shù)最多的類型c) 𝐷𝑖不為空：節(jié)點C=C4.5(𝐷

27、19894;，attrList-A)d) 將節(jié)點C添加為R的子節(jié)點5、返回R 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹C 4 . 5 算 法 信息增益（比例）增長低于閾值，則停止 閾值需要調(diào)校 將數(shù)據(jù)分為訓練集和測試集 測試集上錯誤率增長，則停止 沒有用全部樣本訓練 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹停 止 條 件 先較為充分地生長過擬合 剪枝： 相鄰的葉子節(jié)點，如果合并后不純度增加在 測試集錯誤率下降，則合并 等等其他條件 反復(fù)嘗試，較耗時間范圍內(nèi)，則合并 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹剪 枝 葉子節(jié)點輸出大多數(shù)樣例

28、所屬的類別 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓分類算法-決策樹葉 子 輸 出 規(guī) 則 CART： 二叉回歸樹 Gini系數(shù)|𝑦|𝑦|= 𝑝𝑘𝑝𝑘 = 1 𝑝𝑘2𝐺𝑖𝑛𝑖𝐷𝑘=1 𝑘𝑘𝑘=1𝑉= 𝑣=1𝐷𝑣𝐷𝑣𝐺𝑖𝑛𝑖_𝐼