1.0 重識(shí)決策樹

????????決策樹是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成預(yù)測(cè)點(diǎn)，判斷其是否會(huì)發(fā)生的分析方法，是直觀運(yùn)用概率分析的一種圖解法。由于這種決策樹分支的圖形很像樹的枝干，故稱決策樹。

? ??????決策樹本質(zhì)上是基于經(jīng)驗(yàn)信息對(duì)目標(biāo)結(jié)論的判斷的總結(jié)，通過一句常用語來說：“歷史總是驚人的相似”，即由于某件事在過去某環(huán)境下有大概率發(fā)生，那么現(xiàn)在相同特征的環(huán)境下這件事也很可能會(huì)發(fā)生。

? ??????決策樹基于的假設(shè)較少，適用于大部分情況。但其缺點(diǎn)也很明顯：1）精度較低；2）每次只會(huì)根據(jù)單一特征劃分?jǐn)?shù)據(jù)，不會(huì)根據(jù)數(shù)據(jù)組合切分。但當(dāng)特征間存在關(guān)聯(lián)時(shí)，決策樹只會(huì)用多次切分?jǐn)M合這一情況。

2.0 決策樹的構(gòu)建過程

? ? ? ? 決策樹作為基于樹結(jié)構(gòu)的學(xué)習(xí)模型，也是由根節(jié)點(diǎn)，分叉，葉組成的，其生成過程也是按照“根節(jié)點(diǎn)-->分叉（內(nèi)節(jié)點(diǎn)）-->葉節(jié)點(diǎn)”的過程進(jìn)行。

????????決策樹生成的核心思想就是找出更加純凈的子集。理想情況下，每個(gè)子集里都是結(jié)論（標(biāo)簽）極其一致的數(shù)據(jù)。

????????判斷純度的方法不同決策樹的生成也不同，常用的判斷方法有：1）使用信息增益作純度判斷，稱為ID3樹；2）使用信息增益率作純度判斷，稱為C4.5樹；3）使用基尼系數(shù)作純度判斷，稱為CART樹。

? ? ? ? 總的來說，決策樹的生成步驟為

????????1）尋找最佳分割特征和分割點(diǎn)，把數(shù)據(jù)集分割成兩部分

????????2）判斷是否達(dá)到要求，若未達(dá)到，重復(fù)步驟1）繼續(xù)分割，直到達(dá)到要求停止，生成葉節(jié)點(diǎn)

????????3）判斷葉節(jié)點(diǎn)的標(biāo)簽

????????4）剪枝，防止過擬合

3.0 數(shù)據(jù)純度判斷方法

3.1 補(bǔ)充說明：信息熵、條件熵和經(jīng)驗(yàn)熵

? ? ? ?1）信息熵

????????信息熵，也稱香農(nóng)熵，是衡量系統(tǒng)數(shù)據(jù)混亂程度的一個(gè)指標(biāo)，熵值越大表示數(shù)據(jù)越混亂。決策樹使用信息熵來衡量劃分?jǐn)?shù)據(jù)后各子集的純凈程度，純凈程度越低說明劃分越合理。

????????假定目標(biāo)集合 $S$ 中有 $n$ 種標(biāo)簽（label）的樣本，第 $k$ 種標(biāo)簽所占比例為 $p_k$ ，則 $S$ 的信息熵Entrophy為：

$Ent(S)=\sum_{k=1}^n -p_k·log_2p_k$

????????注：1）取負(fù)號(hào)的原因： $p_k$ 作為比例取值范圍在0-1之間，取對(duì)數(shù)后將是一個(gè)負(fù)數(shù)，且概率越小，對(duì)數(shù)值也越小。但概率越小，表明標(biāo)簽可取值的種類越多，數(shù)據(jù)越雜亂，因此用負(fù)號(hào)取相反數(shù)，表明數(shù)據(jù)越雜亂熵值越大。2）log的底：log實(shí)際上是可以以任何大于1的正數(shù)為底，常見有2，e和10，雖然計(jì)算得到的數(shù)值有不同，但對(duì)數(shù)函數(shù)始終是單調(diào)曲線，并不會(huì)對(duì)信息純度的比較結(jié)果造成影響）

? ? ? ?2）條件熵

? ? ? ? 類似于條件概率，就是在給定條件下系統(tǒng)的信息熵。

????????假定目標(biāo)集合 $S$ 中有 $n$ 種（標(biāo)簽）樣本，現(xiàn)按照某一特征 $X$ 將 $S$ 劃分為若干子集 $D_m$ ，（將 $D_m$ 看成是一個(gè)獨(dú)立的系統(tǒng)）根據(jù) $D_m$ 所包含的標(biāo)簽的種類和概率，其信息熵為 $Ent(D_m|X=m)$ 。此時(shí)基于特征 $X$ 劃分下，系統(tǒng)的信息熵就是條件熵：

$Ent(S|X)=\sum_{m=1}^Mp(X=m)Ent(D_m|X=m)$

? ? ? ?3）經(jīng)驗(yàn)熵

? ? ? ? 經(jīng)驗(yàn)熵比較特別，是以某一特征作為樣本的標(biāo)簽，計(jì)算此時(shí)系統(tǒng)的信息熵。

? ??????假定目標(biāo)集合 $S$ 中有 $n$ 種（標(biāo)簽）樣本，現(xiàn)按照某一特征 $X$ 作為樣本標(biāo)簽，特性 $X$ 有 $i$ 種取值（臨時(shí)標(biāo)簽）， $p_x$ 為特征 $X$ 某一取值的概率，計(jì)算系統(tǒng)信息熵就是經(jīng)驗(yàn)熵：

$Ent_X(S)=\sum_{x=1}^i -p_x·log_2p_x$

3.3 信息增益和ID3樹

? ??????ID3樹使用信息增益來評(píng)價(jià)系統(tǒng)的數(shù)據(jù)混亂程度。假定目標(biāo)集合 $S$ 中有 $n$ 種（標(biāo)簽）樣本，此時(shí)系統(tǒng)的信息熵為 $Ent(S)$ 。現(xiàn)按照某一特征 $X$ 將 $S$ 劃分為若干子集，那么系統(tǒng)在劃分前后的信息熵變化就是信息增益：

$Gain(X)=Ent(S)-Ent(S|X)$

? ? ? ? 由于決策樹的目標(biāo)是提高信息純度，即降低系統(tǒng)的信息熵，因此信息增益越大，說明分類后的數(shù)據(jù)越純凈。

? ? ? ? 使用信息增益生成決策樹的步驟：

????????1）尋找最佳分割特征和分割點(diǎn)，對(duì)數(shù)據(jù)集進(jìn)行劃分：遍歷集合中所有可能的分割點(diǎn)（每個(gè)特征的每個(gè)取值），選擇信息增益最大的劃分特征和特征值作為最佳分割點(diǎn)

? ? ? ? 2）判斷是否達(dá)到停止要求，若未達(dá)到，重復(fù)步驟1）繼續(xù)分割，直到達(dá)到要求停止：節(jié)點(diǎn)中全部樣本的標(biāo)簽同屬于一個(gè)類別；如果分叉后的樣本數(shù)目小于給定的閥值，也停止進(jìn)行分叉

? ? ? ? 3）選擇葉節(jié)點(diǎn)里數(shù)量最多的標(biāo)簽作為葉節(jié)點(diǎn)的標(biāo)簽（投票法）

????????4）剪枝，防止過擬合

3.4 信息增益率和C4.5樹

? ? ? ? C4.5樹使用信息增益率來評(píng)價(jià)系統(tǒng)的數(shù)據(jù)混亂程度。信息增益體現(xiàn)了系統(tǒng)分割前后信息熵變化的絕對(duì)程度，信息增益率則是以百分比體現(xiàn)信息熵變化相對(duì)程度。

????????假定目標(biāo)集合 $S$ 中有 $n$ 種（標(biāo)簽）樣本?，F(xiàn)按照某一特征 $X$ 劃分為若干子集，在劃分前后的信息信息增益為 $Gain(X)$ ，經(jīng)驗(yàn)熵為 $Ent_X(S)$ ，則信息增益率為：

$Gain_r(X)=\frac{Gain(X)}{Ent_X(S)}$

? ? ? ? C4.5算法生成決策樹是以信息增益率最大作為最佳分割點(diǎn)的判斷標(biāo)準(zhǔn)。

3.5 基尼系數(shù)和CART樹

? ??????假定目標(biāo)集合 $S$ 中有 $n$ 種標(biāo)簽（label）的樣本，第 $k$ 種標(biāo)簽所占比例為 $p_k$ ，那么任抽兩次樣本，所得標(biāo)簽錯(cuò)誤的概率就是基尼值：

$Gini=\sum_{k=1}^n 1-p_k^2$

? ? ? ? 當(dāng)按照某一特征 $X$ 將 $S$ 劃分為若干子集 $D_m$ ，根據(jù)所包含的標(biāo)簽的種類 $i$ 和概率 $p_i$ ，此時(shí)系統(tǒng)的基尼值為：

$Gini-index(X)=\sum_{m=1}^MGini(D_m)=\sum_{m=1}^M(\sum_{i}1-p_i^2 )$

? ? ? ? CART樹在判斷分割停止條件上與ID3和C4.5樹不同，具體包含三點(diǎn)：1）決策樹到達(dá)最大深度；2）分叉節(jié)點(diǎn)的樣本數(shù)小于閥值；3）分叉的葉內(nèi)的樣本數(shù)小于閥值

4.0 過擬合處理方法

????????在決策樹生成過程中，隨著數(shù)據(jù)分割使得子集的樣本量越來越小，剩余待分割的數(shù)據(jù)越有可能是特殊情況，這就導(dǎo)致著決策樹分割總是向著過擬合的方向進(jìn)行。為了降低過擬合風(fēng)險(xiǎn)，需要主動(dòng)去除一些分類效果不明顯的分叉來防止過擬合，這一過程被稱為剪枝。剪枝主要有兩種方法：預(yù)剪枝和后剪枝

? ? ? ?預(yù)剪枝

????????預(yù)剪枝是在生成決策樹過程中，在節(jié)點(diǎn)劃分前進(jìn)性預(yù)評(píng)估，若節(jié)點(diǎn)分叉不能使決策樹得到泛化提升，則停止分叉生成葉。代表算法是悲觀錯(cuò)誤剪枝法PEP（Pesimistic-Error Pruning）。

? ?????后剪枝：

????????后剪枝是生成一棵完整的決策樹后，自下而上對(duì)每個(gè)葉節(jié)點(diǎn)和分叉點(diǎn)進(jìn)行評(píng)估，若減少分叉可以使決策樹得到泛化提升，則轉(zhuǎn)化分叉為一個(gè)葉。代表算法有錯(cuò)誤率降低剪枝REP（Reduced-Error Pruning），代價(jià)復(fù)雜度剪枝CCP（Cost-Complexity Pruning）。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

溫故知新——決策樹

溫故知新——決策樹

1.0 重識(shí)決策樹

2.0 決策樹的構(gòu)建過程

3.0 數(shù)據(jù)純度判斷方法