分類模型算法決策樹

1、八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹決策樹 八 斗 大 數(shù) 據(jù)， 盜 版 決策樹簡(jiǎn)介ID3算法C4.5、CART算法【實(shí)踐】決策樹 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹O u t L i n e 樹形結(jié)構(gòu)決策規(guī)則 分類問(wèn)題，對(duì)樣本： 從根節(jié)點(diǎn)出發(fā) 根據(jù)節(jié)點(diǎn)規(guī)則決定走哪個(gè)子節(jié)點(diǎn) 一直走到葉子節(jié)點(diǎn) 根據(jù)葉子節(jié)點(diǎn)的輸出規(guī)則輸出 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹決 策 樹 例子：評(píng)估 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹決 策 樹 - 例 子八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹決 策 樹 - 例 子 如何做到？計(jì)數(shù)收入學(xué)生信譽(yù)是否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é)點(diǎn) 青年，否，買 中年，買 老年，否，買 “中年”停止分解，“青年”、“老年”繼續(xù)分解 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹決 策 樹 - 例 子 對(duì)“青年”分解 經(jīng)分析，高收入和低收入，只對(duì)應(yīng)一個(gè)簽作為葉子節(jié)點(diǎn)，停止，直接將該標(biāo) 八 斗 大 數(shù) 據(jù)， 盜 版 計(jì)數(shù)收入學(xué)生信譽(yù)是否64青高否良否64青高否優(yōu)否128青中否良否64青低是良買64青

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

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

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

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

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

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

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

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

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

12、9895;, 𝑠2𝑗, , 𝑠m𝑗𝑝𝑖𝑗𝑠𝑗 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹信 息 增 益 如 何 計(jì) 算 ？ 最后，實(shí)用信息增益確定決策樹分支的劃分依據(jù)Gain(A) = 𝐼- E(A)𝑠1, 𝑠2, , 𝑠𝑚 八 斗 大 數(shù) 據(jù)， 盜 版 八斗大數(shù)據(jù)培訓(xùn)分類算法-決策樹信 息 增 益 如 何 計(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、培訓(xùn)分類算法-決策樹信 息 增 益 計(jì) 算 舉 例 接下來(lái)計(jì)算每個(gè)特征的信息熵 1、先計(jì)算“”特征的熵，共分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ù)培訓(xùn)分類算法-決策樹信 息 增 益 計(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ù)培訓(xùn)分類算法-決策樹信 息 增 益 計(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ù)培訓(xùn)分類算法-決策樹信 息 增 益 計(jì) 算 舉 例 所以匯總 “ E( G(”的平均信息期望：)=0.375*0.9183+0.25*0+ 0.375*0.9157=0.6877)=0.9544-0.6877=0.2667從所有特征中選擇信息增益最大的作 同理： E(學(xué)生)=0.7811 E(收入)=0.9361 E(信譽(yù))=0.9048為根節(jié)點(diǎn)或者內(nèi)部節(jié)點(diǎn)，根據(jù)計(jì)算，G(學(xué)生)=0.1733G(

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

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

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

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

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

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

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

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

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

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

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