決策樹既可以用來(lái)做分類【分類樹】，又可以做回歸【回歸樹】。
決策樹由三個(gè)部分構(gòu)成：
根節(jié)點(diǎn)：第一個(gè)選擇點(diǎn)
非葉子節(jié)點(diǎn)和分支：中間過(guò)程
葉子節(jié)點(diǎn)：最終的決策結(jié)果
過(guò)程：利用給定的訓(xùn)練集構(gòu)造一棵樹，根據(jù)構(gòu)造的樹，把測(cè)試集從上到下走一遍
所以關(guān)鍵是如何選擇特征來(lái)構(gòu)造決策樹
三種方法：ID3【按照信息增益計(jì)算】窟蓝、C4.5【按照信息增益比計(jì)算】、CART【按照CINI系數(shù)計(jì)算】
分類樹
例子：
1）ID3
衡量標(biāo)準(zhǔn)：熵【表示隨機(jī)變量不確定性的指標(biāo)】饱普，熵值越大运挫，不確定性越高
當(dāng)時(shí)，
等于0 套耕，達(dá)到最小谁帕，完全沒(méi)有不確定性；
當(dāng)時(shí)冯袍，
等于1匈挖，達(dá)到最大，不確定性最大颠猴。
另外選擇節(jié)點(diǎn)的最終標(biāo)準(zhǔn)是信息增益【表示特征X使得類Y的不確定性減少的程度【熵的下降程度】】关划，將信息增益最大的特征作為根節(jié)點(diǎn)，以此類推翘瓮。
第一輪：
原始數(shù)據(jù)的熵值：
yes：9個(gè)贮折，no：5個(gè)
如果按outlook分類：
sunny：yes有2個(gè)，no有3個(gè)资盅，即取得sunny的概率為5/14
sunny類的熵值：
overcast：yes有4個(gè)调榄，no有0個(gè)，即取得overcast的概率為4/14
overcast類的熵值：0
rainy：yes有3個(gè)呵扛，no有2個(gè)每庆，即取得rainy的概率為5/14
rainy類的熵值：
綜上，按outlook分類的熵值為【此處計(jì)算的實(shí)際是條件熵】
信息增益為0.940-0.693=0.247
同理
如果按temperature分類:
hot類：取hot的概率是4/14
熵值為：
mild類：取mild的概率是6/14
熵值為：
cool類：取cool的概率是4/14
熵值為：
綜上今穿，按temperature分類的熵值為
信息增益為0.940-0.911=0.029
按humidity分類：
normal類：取normal的概率是7/14
熵值為：
high類：取high的概率是7/14
熵值為：
綜上缤灵，按humidity分類的熵值為
信息增益為0.940-0.7885=0.1515
按windy分類：
True類：取True的概率是6/14
熵值為：
False類：取False的概率是8/14
熵值為：
綜上，按windy分類的熵值為
信息增益為0.940-0.892=0.048
根據(jù)信息增益比最大的原則蓝晒，選擇特征outlook為根節(jié)點(diǎn)腮出。
現(xiàn)在的決策樹長(zhǎng)這樣：
由上圖可知，當(dāng)outlook等于overcast芝薇，可以得出肯定會(huì)去打球的結(jié)論胚嘲，不需要再切分，下面對(duì)sunny和rainy繼續(xù)切分
第二輪：
sunny類：當(dāng)前樣本的熵值等于
按temperature分類：熵為0.4洛二，信息增益0.571
按humidity分類：熵為0馋劈，信息增益0.971
按windy分類：熵為0.811攻锰，信息增益0.16
選擇特征humidity為節(jié)點(diǎn)
rainy類：當(dāng)前樣本的熵值等于當(dāng)前樣本的熵值等于
按temperature分類：熵為0.9508，信息增益0.0202
按humidity分類：熵為0.9508妓雾，信息增益0.0202
按windy分類：熵為0娶吞，信息增益0.971
選擇特征windy為節(jié)點(diǎn)
現(xiàn)在的決策樹長(zhǎng)這樣：
最終生成5個(gè)葉子節(jié)點(diǎn)
但是ID3算法會(huì)偏向于取值較多的特征：當(dāng)特征取值較多時(shí)，分類結(jié)果的純度較高君珠，不確定性越低寝志，熵值越低，信息增益比越大策添。
2）C4.5【信息增益比】
為了解決這個(gè)問(wèn)題，引入了信息增益比指標(biāo)
信息增益比等于信息增益除以自身的熵值毫缆，相當(dāng)于乘了一個(gè)懲罰項(xiàng)唯竹，當(dāng)該特征取值較多時(shí)，不確定性較高苦丁，熵值較大浸颓，它的倒數(shù)較小，信息增益比較小旺拉，被選擇為節(jié)點(diǎn)的可能性降低产上。
但是，反之蛾狗，當(dāng)特征取值較少時(shí)晋涣，不確定性較低，熵值較低沉桌，它的倒數(shù)較高谢鹊，信息增益比較大，被選擇的可能性較高留凭，因此C4.5偏向于選擇特征取值較少的為節(jié)點(diǎn)佃扼。
上述例子如果用C4.5作為衡量標(biāo)準(zhǔn)，結(jié)果如下：
第一輪：
按outlook分類：信息增益比為
按temperature分類：信息增益比為
按humidity分類：信息增益比為
按windy分類：信息增益比為
按照薪資增益比最大原則蔼夜，選擇特征windy為根節(jié)點(diǎn)【果然選了取值較少的那個(gè)】
第二輪：
windy為true的分支：
按outlook分類的信息增益比為0.423兼耀，temperature的為0.143，humidity的為0.082求冷，所以選擇outlook為節(jié)點(diǎn)
windy為false的分支：
按outlook分類的信息增益比為0.299瘤运，temperature的為0.078，humidity的為0.311遵倦，
所以選擇humidity為節(jié)點(diǎn)
此時(shí)的決策樹為【但愿沒(méi)算錯(cuò)】
最左邊和最右邊的節(jié)點(diǎn)可以同理繼續(xù)切分
3）CART【GINI系數(shù)】
以outlook和temperature為例
計(jì)算得出outlook的最佳切分點(diǎn)為{{rainy}尽超，{sunny，overcast}}梧躺，GINI系數(shù)為0.457似谁；
temperature的最佳切分點(diǎn)為{{mild}傲绣，{hot，cool}}巩踏，GINI系數(shù)為0.458
我所理解的應(yīng)該是根據(jù)每個(gè)特征的最佳切分點(diǎn)對(duì)應(yīng)的GINI系數(shù)秃诵，選擇系數(shù)最小的作為節(jié)點(diǎn)以及切分點(diǎn)。
回歸樹
這一塊在學(xué)習(xí)的時(shí)候是我覺(jué)得不太容易理解的塞琼，這里參考了https://blog.csdn.net/weixin_36586536/article/details/80468426和https://blog.csdn.net/Albert201605/article/details/81865261博主的內(nèi)容
這個(gè)類似于CART算法菠净，
首先遍歷所有特征，對(duì)每一個(gè)特征的每個(gè)切分點(diǎn)彪杉，得到兩個(gè)分支各自的標(biāo)簽值毅往，計(jì)算兩個(gè)分支各自的離差平方和，將這兩塊離差平方和之和作為這個(gè)切分點(diǎn)的離差平方和派近，將最小的離差平方和所對(duì)應(yīng)的切分點(diǎn)為該特征的最佳切分點(diǎn)攀唯，以此類推，得到第一層的根節(jié)點(diǎn)渴丸，然后對(duì)每個(gè)分支重復(fù)執(zhí)行上述步驟侯嘀，直至得到最終的決策樹，葉子節(jié)點(diǎn)輸出的是該分支標(biāo)簽值的平均值谱轨，當(dāng)有新的特征輸入時(shí)戒幔，從上到下走一遍決策樹，輸出相應(yīng)葉子節(jié)點(diǎn)的標(biāo)簽值土童。
