機(jī)器學(xué)習(xí)day9-決策樹

決策樹

決策樹自上而下，對樣本數(shù)據(jù)進(jìn)行樹形分類的過程。決策樹由結(jié)點(diǎn)和有向邊組成。結(jié)點(diǎn)又分內(nèi)部結(jié)點(diǎn)和葉結(jié)點(diǎn)。每個(gè)內(nèi)部結(jié)點(diǎn)表示一個(gè)特征或?qū)傩裕~子結(jié)點(diǎn)表示類別。
從頂部開始，所有樣本聚在一起，經(jīng)過根結(jié)點(diǎn)的劃分，樣本分入不同的子結(jié)點(diǎn)，再根據(jù)子結(jié)點(diǎn)的特征進(jìn)一步劃分，直到所有的樣本被歸入到一個(gè)類別。
決策樹是最基礎(chǔ)且常見的監(jiān)督學(xué)習(xí)模型，可以用于處理分類問題和回歸問題。
決策樹的生成包括：特征選擇，樹的構(gòu)造，樹的剪枝三個(gè)過程。

決策樹常用的啟發(fā)函數(shù)

常用的決策樹算法有：ID3，C4.5和CART，那么它們的啟發(fā)式函數(shù)是什么？

ID3-最大信息增益

對于樣本集合D，類別數(shù)為K，數(shù)據(jù)集D的經(jīng)驗(yàn)熵表示：
H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}
其中，C_k是樣本集合D中屬于第k類的樣本子集，|C_k|表示該子集的元素個(gè)數(shù)，|D|表示樣本集合的樣本個(gè)數(shù)。
然后計(jì)算某特征A對于數(shù)據(jù)集D的經(jīng)驗(yàn)條件熵H(D|A)：
H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=\sum_{i=1}^n\frac{|D_i|}{|D|}(-\sum_{k=1}^{k}\frac{|D_{ik}|}{|D_i|})log_2\frac{|D_{ik}|}{|D_i|}
其中，D_i表示D中特征A取第i個(gè)值得樣本子集，D_{ik}表示D_i中屬于dik類的樣本子集。
因此，信息增益g(D,A)可以表示為二者之差，
g(D,A)=H(D)-H(D|A)
信息增益最大，一般是最后具體劃分類別的結(jié)點(diǎn)。

C4.5-最大信息增益比

特征A對于數(shù)據(jù)集D的信息增益比定義：
g_{R}(D,A)=\frac{g(D,A)}{H_A(D)}
其中
H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}
H_A(D)稱為數(shù)據(jù)集D關(guān)于A的取值熵。

CART-最大基尼指數(shù)(Gini)

Gini描述的是數(shù)據(jù)的純度，與信息熵含義類似
Gini(D)=1-\sum_{k=1}^{n}(\frac{|C_k|}{|D|})^2
CART每次迭代時(shí)選擇基尼指數(shù)最小的特征及其對應(yīng)的切分點(diǎn)進(jìn)行分類。CART是二叉樹，每一步數(shù)據(jù)按照特征A的取值切成兩份，分別進(jìn)入左右子樹。特征A的Gini指數(shù)定義：
Gini(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)

三種啟發(fā)函數(shù)

ID3使用信息增益作為評價(jià)標(biāo)準(zhǔn)。C4.5基于ID3進(jìn)行了優(yōu)化，引入了信息增益比，對取值較多的特征進(jìn)行懲罰，避免了一定程度的過擬合。提高決策樹的泛化能力。
ID3應(yīng)用于離散變量，C4.5和CART都可以用于連續(xù)變量。
ID3和C4.5用于分類任務(wù)，CART，Classification and Regression Tree，分類回歸樹用于回歸和分類問題。
最后，ID3對于樣本特征缺失值比較敏感，CART和C4.5會自己處理，C4.5通過剪枝，CART則是直接利用全部數(shù)據(jù)發(fā)現(xiàn)所有可能的樹結(jié)構(gòu)進(jìn)行對比。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容