4. 決策樹

4.1. 基本流程

決策過程的最終結(jié)論是所希望判定的結(jié)果；
決策過程中提出的每個(gè)判定問題都是對(duì)某個(gè)屬性黨的“測(cè)試”；
每個(gè)測(cè)試的結(jié)果或是導(dǎo)出的最終結(jié)論，或是導(dǎo)出進(jìn)一步的判定問題，其考慮范圍是在上次決策結(jié)果的限定范圍之內(nèi)。

一般的，一棵決策樹包含一個(gè)根結(jié)點(diǎn)、若干個(gè)內(nèi)部節(jié)點(diǎn)和若干個(gè)葉結(jié)點(diǎn)；
葉結(jié)點(diǎn)對(duì)應(yīng)于決策結(jié)果，其他每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)屬性測(cè)試；
每個(gè)結(jié)點(diǎn)包含的樣本集合根據(jù)屬性測(cè)試的結(jié)果被劃分到子結(jié)點(diǎn)中；
根結(jié)點(diǎn)包含樣本全集。
從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑對(duì)應(yīng)了一個(gè)判定測(cè)試序列。
決策樹學(xué)習(xí)的目的是為了產(chǎn)生一棵泛化能力強(qiáng)的決策樹。

決策樹是一個(gè)遞歸過程。
導(dǎo)致遞歸的三種情況，

當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別，無需劃分;
當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分;
當(dāng)前結(jié)點(diǎn)包含的樣本集合為空，不能劃分.

劃分選擇

隨著劃分過程不斷進(jìn)行，希望決策樹的分支結(jié)點(diǎn)所包含的樣本盡可能屬于同一類別，即結(jié)點(diǎn)的純度越來越高。

信息增益

信息熵：度量樣本集合純度的指標(biāo)。
假定當(dāng)前樣本集合 $D$ 中第 $k$ 類樣本所占的比例為 $p_{k}(k=1,2,\dots,|\mathcal{Y }|)$ ，樣本集合 $D$ 的信息熵為：
$\operatorname{Ent}(D)=-\sum_{k=1}^{\mid \mathcal{Y |}} p_{k} \log _{2} p_{k}$
$\operatorname{Ent}(D)$ 的值越小，則純度越高。

考慮不同的分支結(jié)點(diǎn)所包含的樣本數(shù)不同，給分支結(jié)點(diǎn)賦予權(quán)重 $\left|D^{v}\right| /|D|$ ，即樣本數(shù)越多的分支結(jié)點(diǎn)的影響越大，
用屬性 $a$ 對(duì)樣本集 $D$ 進(jìn)行劃分所獲得的“信息增益”。
$\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)$
信息增益越大，即用屬性 $a$ 進(jìn)行劃分所獲得的純度提升越大。

用信息增益來進(jìn)行決策樹的劃分屬性選擇。
$a_{*}=\underset{a \in A}{\arg \max } \operatorname{Gain}(D, a)$

增益率

信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的屬性有所偏好。
一種方式，用增益率來選擇最優(yōu)劃分屬性。
$\operatorname{Gain} \operatorname{ratio}(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}$
其中， $IV$ 為屬性 $a$ 的固有值 intrinsic value.
$\operatorname{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|}$
增益率準(zhǔn)則對(duì)取值數(shù)目較少的屬性有所偏好。

基尼指數(shù)

數(shù)據(jù)集的純度可用基尼值來度量：
$\begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned}$
即，從數(shù)據(jù)集中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率。
數(shù)值越小，純度越高。
$ $a_{*}=\underset{a \in A}{\arg \min }$ Gini_index $(D, a)$

剪枝處理

剪枝處理，是決策樹應(yīng)對(duì)過擬合的主要手段。

預(yù)剪枝

預(yù)剪枝對(duì)劃分前后的泛化性能進(jìn)行估計(jì)。

預(yù)剪枝使得決策樹的很多分支沒有展開，降低了過擬合風(fēng)險(xiǎn)，且提高訓(xùn)練效率。

后剪枝

后剪枝決策樹的欠擬合風(fēng)險(xiǎn)很小，泛化性能往往優(yōu)于預(yù)剪枝決策樹. 但后剪枝過程是在生成完全決策樹之后進(jìn)行的，并且要自底向上地對(duì)樹中的所有非葉結(jié)點(diǎn)進(jìn)行逐一考察，因此其訓(xùn)練時(shí)間開銷比未剪枝決策樹和預(yù)剪枝決策樹都要大得多.

連續(xù)與缺失值

連續(xù)值處理

連續(xù)屬性的離散化
$T_{a}=\left\{\frac{a^{i}+a^{i+1}}{2} \mid 1 \leqslant i \leqslant n-1\right\}$
將中位點(diǎn)作為候選劃分點(diǎn)，像離散屬性值一樣來考察這些劃分點(diǎn)，選取最優(yōu)的劃分點(diǎn)進(jìn)行樣本集合的劃分.

需注意的是，與離散屬性不同，若當(dāng)前結(jié)點(diǎn)劃分屬性為連續(xù)屬性? 該屬性還可作為其后代結(jié)點(diǎn)的劃分屬性. 只是所使用的屬性數(shù)值不同。

缺失值處理

多變量決策樹

分類邊界的每一段都是與坐標(biāo)軸平行的，這樣的分類邊界使得學(xué)習(xí)結(jié)果有較好的可解釋性，因?yàn)?em>每一段劃分都直接對(duì)應(yīng)了某個(gè)屬性取值.

多變量決策樹" (multivariate decision tree) 就是能實(shí)現(xiàn)"斜劃分"甚至更復(fù)雜劃分的決策樹。

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

吃瓜教程_Task_3_西瓜書+南瓜書_Chapter4

吃瓜教程_Task_3_西瓜書+南瓜書_Chapter4

4. 決策樹

4.1. 基本流程

劃分選擇

信息增益