決策樹

0. Motivation?

Can you draw single division line for these?classes???

We need two lines one for threshold of x and threshold for?y? .

Decision Tree Classifier, repetitively divides the working area(plot) into sub part by identifying lines.

1. 基本流程

遞歸返回：

（1）當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別，無(wú)需劃分

（2）當(dāng)前屬性集為空，或是所有樣本在所有屬性上的取值相同，無(wú)法劃分帆啃。把當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)邢享，類別為該節(jié)點(diǎn)所含樣本最多的類別侨赡。

（3）當(dāng)前結(jié)點(diǎn)包含的樣本集合為空摇庙，不能劃分胆剧。把當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)絮姆，類別設(shè)定為其父結(jié)點(diǎn)所含樣本最多的類別。

2. 劃分選擇

2.1 信息增益

假定當(dāng)前樣本集合D中第k類樣本所占的比例為 $p_k(k=1,2,...,|y|)$

信息熵：度量樣本集合純度

$Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2 p_k$

信息熵越小秩霍，樣本集合的純度越高

假定離散屬性a有V個(gè)可能的取值 $\{a^1,a^2,...,a^V\}$ 滚朵， $D^v$ ：D中所有在屬性a上取值為 $a^v$ 的樣本

$\frac{|D^v|}{|D|}$ ：根據(jù)不同分支結(jié)點(diǎn)所包含的樣本數(shù)，給分支結(jié)點(diǎn)賦予權(quán)重前域，樣本數(shù)越多的分支結(jié)點(diǎn)影響越大

信息增益： $Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|} Ent(D^v)$

信息增益越大辕近，意味著使用屬性a來(lái)進(jìn)行劃分所獲得的“純度”提升越大

ID3以信息增益為準(zhǔn)則選擇劃分屬性，即在圖4.2第八行選擇屬性 $a_*=\arg \max_{a\in A}Gain(D,a)$

判別是否是好瓜： $|y|=2$ 匿垄，正例 $p_1=\frac{8}{17}$ ,反例 $p_1=\frac{9}{17}$

（1）計(jì)算根結(jié)點(diǎn)信息熵： $Ent(D)=-\sum_{k=1}^{2}p_k\log_2 p_k =0.998$

（2）計(jì)算當(dāng)前屬性集合{色澤移宅，根蒂，敲聲椿疗，紋理漏峰，臍部，觸感}中每個(gè)屬性的信息增益届榄。

“色澤”={青綠浅乔，烏黑，淺白}

$D^1$ (色澤=青綠)={1铝条，4靖苇，6，10班缰，13贤壁，17}，正例 $p_1=\frac{3}{6}$ 埠忘，反例 $p_2=\frac{3}{6}$ 脾拆， $Ent(D^1)=1.000$

$D^2$ (色澤=烏黑)={2，3莹妒，7名船，8，9旨怠，15}渠驼，正例 $p_1=\frac{4}{6}$ ，反例 $p_2=\frac{2}{6}$ 运吓， $Ent(D^2)=0.918$

$D^3$ (色澤=淺白)={5渴邦，11疯趟，12拘哨，14谋梭，16}，正例 $p_1=\frac{1}{5}$ 倦青，反例 $p_2=\frac{4}{5}$ 瓮床， $Ent(D^3)=0.722$

$Gain(D,色澤)=Ent(D)-\sum_{v=1}^{3}\frac{|D^v|}{|D|}Ent(D^v)=0.109$

同理

$Gain(D,根蒂)=0.143，Gain(D,敲聲)=0.141产镐，Gain(D,紋理)=0.381$

$Gain(D,臍部)=0.289隘庄，Gain(D,觸感)=0.006$

選擇“紋理”作為劃分屬性：

基于“紋理”屬性對(duì)根節(jié)點(diǎn)進(jìn)行劃分

針對(duì)“紋理=清晰”的分支結(jié)點(diǎn)，基于 $D^1$ 計(jì)算出各屬性的信息增益：

$Gain(D^1,根蒂)=0.458癣亚，Gain(D^1,敲聲)=0.331$

$Gain(D,色澤)=0.043丑掺，Gain(D,臍部)=0.458，Gain(D,觸感)=0.458$

不斷對(duì)每個(gè)分支結(jié)點(diǎn)進(jìn)行上述操作述雾，最終得到

信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的屬性有所偏好街州。

C4.5使用“增益率”來(lái)選擇最優(yōu)劃分屬性。

2.2 增益率

增益率： $Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

屬性a的固有值： $IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2 \frac{|D^v|}{|D|}$

屬性a的可取值數(shù)目越多（V越大）玻孟，則IV(a）通常會(huì)越大

增益率準(zhǔn)則對(duì)可取值數(shù)目較少的屬性有所偏好唆缴。

因此，C4.5算法沒(méi)有直接選擇增益率最大的候選劃分屬性黍翎，而是先從候選劃分屬性中找出信息增益高于平均水平的屬性面徽，再?gòu)闹羞x擇增益率最高的。

2.3 基尼指數(shù)

CART決策樹是用“基尼指數(shù)”來(lái)選擇劃分屬性匣掸。

基尼值： $Gini(D)=\sum_{k=1}^{|y|}\sum_{k^{\prime}\neq k}p_kp_{k^{\prime}}=1-\sum_{k=1}^{|y|}p^2_k$ 趟紊，反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率碰酝。

Gini值越小织阳，數(shù)據(jù)集D的純度越高。

屬性a的基尼指數(shù)： $Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$

在侯選屬性集合A中砰粹，選擇那個(gè)使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性唧躲，即 $a_*=\arg \min_{a\in A}Gini_index(D,a)$

3. 剪枝處理

預(yù)剪枝：在決策樹的生成過(guò)程中，對(duì)每個(gè)結(jié)點(diǎn)在劃分前先進(jìn)行估計(jì)碱璃，若當(dāng)前結(jié)點(diǎn)的劃分不能帶來(lái)決策樹泛化性能提升弄痹，則停止劃分并將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)。

后剪枝：先從訓(xùn)練集生成一顆完整的決策樹，然后自底向上地對(duì)非葉節(jié)點(diǎn)進(jìn)行考察，若將該結(jié)點(diǎn)對(duì)應(yīng)的子樹替換為葉節(jié)點(diǎn)能帶來(lái)決策樹泛化性能提升挂捅，則將該子樹替換為葉節(jié)點(diǎn)沮翔。

劃分訓(xùn)練集和驗(yàn)證集

采用信息增益準(zhǔn)則生成決策樹

3.1 預(yù)剪枝

（1）若根結(jié)點(diǎn)“臍部”不進(jìn)行劃分猜极，被標(biāo)記為葉結(jié)點(diǎn)鹿寻，其類別標(biāo)記為訓(xùn)練樣例數(shù)最多的類別屉更，假設(shè)標(biāo)記為“好瓜”抖苦。用驗(yàn)證集進(jìn)行評(píng)估历极，編號(hào){4,5,8}被正確分類窄瘟，{9,11,12,13}被錯(cuò)誤分類，精度為42.9%趟卸。用屬性“臍部”劃分后蹄葱，{4,5,8,11,12}被正確分類，驗(yàn)證集精度為71.4%锄列。因此图云，用“臍部”劃分得以確定。

（2）對(duì)②進(jìn)行劃分邻邮，基于信息增益準(zhǔn)則挑選出”色澤“竣况，{5}會(huì)被錯(cuò)分，劃分后驗(yàn)證集精度下降筒严，于是將禁止結(jié)點(diǎn)②被劃分丹泉。

（3）對(duì)③，最優(yōu)劃分屬性為”根蒂“萝风，劃分前后精度一樣嘀掸，禁止劃分。

（4）對(duì)④规惰，其所含訓(xùn)練樣例已屬于同一類睬塌，不再進(jìn)行劃分。

優(yōu)點(diǎn)：降低過(guò)擬合風(fēng)險(xiǎn)歇万，顯著減少了訓(xùn)練和測(cè)試的時(shí)間開銷

缺點(diǎn)：基于”貪心“揩晴，有欠擬合風(fēng)險(xiǎn)。有些分支當(dāng)前劃分雖然不能提升泛化性能贪磺，但在其基礎(chǔ)上進(jìn)行后續(xù)劃分卻有可能導(dǎo)致性能顯著提高硫兰。

3.2 后剪枝

先從訓(xùn)練集生成一顆完整的決策樹。圖4.5中決策樹的驗(yàn)證集精度為42.9%寒锚。

（1) 首先考慮結(jié)點(diǎn)⑥劫映，剪枝后的葉結(jié)點(diǎn)包含編號(hào){7,15}的訓(xùn)練樣本，于是刹前，該葉結(jié)點(diǎn)的類別標(biāo)記為”好瓜“泳赋，此時(shí)驗(yàn)證集精度提高至57.1%。因此決定剪枝喇喉。

（2）考察結(jié)點(diǎn)⑤祖今，替換后的葉結(jié)點(diǎn)包含{6,7,15}，標(biāo)記為”好瓜“，驗(yàn)證集精度仍為57.1%千诬，可以不進(jìn)行剪枝耍目。

（3）對(duì)結(jié)點(diǎn)②，替換后的葉結(jié)點(diǎn)包括{1,2,3,14}徐绑，標(biāo)記為”好瓜”邪驮，此時(shí)驗(yàn)證集精度提高至71.4%，于是泵三，決定剪枝耕捞。

（4）對(duì)結(jié)點(diǎn)③和①衔掸，替換后精度均未得到提高烫幕，于是得以保留。

后剪枝決策樹通常比預(yù)剪枝決策樹保留更多的分支敞映。一般情況下较曼，后剪枝決策樹欠擬合風(fēng)險(xiǎn)很小，但其訓(xùn)練時(shí)間開銷較大振愿。

4. 連續(xù)與缺失值

4.1 連續(xù)值處理

二分法：給定樣本集D和連續(xù)屬性a捷犹，假定a在D上出現(xiàn)了n個(gè)不同的取值，撿這些值從小到大進(jìn)行排序冕末，記為 $\{a^1,a^2,...,a^n \}$ 基于劃分點(diǎn)t可將D分為子集 $D^-_t$ 和 $D^+_t$ 萍歉，其中 $D^-_t$ 包含那些在屬性a上取值不大于t的樣本，而 $D^+_t$ 則包含那些在屬性a上大于t的樣本档桃。

$Gain(D,a)=\max_{t \in T_a}Ent(D)-\sum_{\lambda \in \{-,+\}}\frac{|D^v|}{|D|} Ent(D^\lambda)$

與離散屬性不同枪孩，若當(dāng)前結(jié)點(diǎn)劃分屬性為連續(xù)屬性，則該屬性還可作為其后代結(jié)點(diǎn)的劃分屬性藻肄。例如在父結(jié)點(diǎn)上使用了“密度<=0.381”蔑舞，不會(huì)禁止在子結(jié)點(diǎn)上使用“密度<=0.294”.

4.2 缺失值處理

問(wèn)題：（1）如何在屬性值缺失的情況下進(jìn)行劃分屬性選擇？

給定訓(xùn)練集D和屬性a嘹屯，令 $\tilde{D}$ 表示D中在屬性a上沒(méi)有缺失值的樣本子集攻询。假定屬性a有V個(gè)可取值 $\{a^1,a^2,...,a^V\}$ ，令 $\tilde{D}^v$ 表示 $\tilde{D}$ 中在屬性a上取值為 $a^v$ 的樣本子集州弟， $\tilde{D}_k$ 表示 $\tilde{D}$ 中屬于第k類的樣本子集钧栖，顯然有 $\tilde{D}= \bigcup_{k=1}^{{y}} \tilde{D}_k$ , $\tilde{D}= \bigcup_{v=1}^{{V}} \tilde{D}^v$ 。

假定我們?yōu)槊總€(gè)樣本x賦予一個(gè)權(quán)重 $w_x$ ,并定義

$\rho =\frac{\sum_{\tilde{D}} w_x}{\sum_{D} w_x}$ 婆翔，表示無(wú)缺失值樣本所占的比例

$\tilde{p_k} =\frac{\sum_{\tilde{D_k}} w_x}{\sum_{\tilde{D}} w_x}$ 拯杠，表示無(wú)缺失值樣本中第k類所占的比例， $\sum_{k=1}^{|y|} \tilde{p_k}=1$

$\tilde{r_v} =\frac{\sum_{\tilde{D^v}} w_x}{\sum_{\tilde{D}} w_x}$ 浙滤，表示無(wú)缺失值樣本中在屬性a上取值為 $a^v$ 的樣本所占的比例阴挣， $\sum_{v=1}^{V} \tilde{r_v}=1$

$Gain(D,a)=\rho \times Gain(\tilde{D},a)=\rho \times \Bigg(Ent(\tilde{D})-\sum_{v=1}^{V}{\tilde{r_v}} Ent(\tilde{D^v})\Bigg)$

以表4.4的數(shù)據(jù)為例生成一顆決策樹：

學(xué)習(xí)開始時(shí)，根節(jié)點(diǎn)包含樣本集D中全部17個(gè)樣例纺腊，各樣例的權(quán)值為1.

屬性“色澤”上無(wú)缺失值的樣例子集 $\tilde{D}=\{2,3,4,6,7,8,9,10,11,12,14,15,16,17\}$ 畔咧，共14個(gè)樣例茎芭。

信息熵 $Ent(\tilde{D})=-\sum_{k=1}^{2} \tilde{p_k}\log_2 \tilde{p_k}=-(\frac{6}{14}\log_2 {\frac{6}{14}} +\frac{8}{14}\log_2 {\frac{8}{14}} )=0.985$

令 $\tilde{D}^1,\tilde{D}^2,\tilde{D}^3$ 分別表示在屬性“色澤”上取值為“”青綠，“烏黑”誓沸，“淺白”的樣本子集梅桩。

$Ent(\tilde{D}^1)=-(\frac{2}{4}\log_2 {\frac{2}{4}} +\frac{2}{4}\log_2 {\frac{2}{4}} )=1.000$

$Ent(\tilde{D}^2)=-(\frac{4}{6}\log_2 {\frac{4}{6}} +\frac{2}{6}\log_2 {\frac{2}{6}} )=0.918$

$Ent(\tilde{D}^3)=-(\frac{0}{4}\log_2 {\frac{0}{4}} +\frac{4}{4}\log_2 {\frac{4}{4}} )=0.000$

樣本子集 $\tilde{D}$ 上屬性“色澤”的信息增益為

$Gain(\tilde{D},a)=Ent(\tilde{D})-\sum_{v=1}^{3}{\tilde{r_v}} Ent(\tilde{D^v})$

$=0.985-(\frac{4}{14} \times 1.000+\frac{6}{14}\times 0.918+\frac{4}{14}\times 0.918)=0.306$

于是，樣本集D上屬性“色澤”的信息增益為

$Gain(D,色澤)=\rho \times Gain(\tilde{D},色澤)=\frac{14}{17} \times 0.306=0.252$

類似地可計(jì)算出所有屬性在D上的信息增益

$Gain(D,根蒂)=0.171拜隧，Gain(D,敲聲)=0.145宿百，Gain(D,紋理)=0.424$

$Gain(D,臍部)=0.289，Gain(D,觸感)=0.006$

“紋理”取得最大的信息增益洪添，被用于對(duì)根節(jié)點(diǎn)進(jìn)行劃分垦页。

問(wèn)題：（2）給定劃分屬性，若樣本在該屬性上的值缺失干奢，如何對(duì)樣本進(jìn)行劃分痊焊？

若樣本x在劃分屬性a上的取值已知，則將x劃入與其取值對(duì)應(yīng)的子結(jié)點(diǎn)忿峻，且樣本權(quán)值在子結(jié)點(diǎn)中保持為 $w_x$ .

若樣本x在劃分屬性a上的取值未知薄啥，則將x劃入與所有的子結(jié)點(diǎn)，且樣本權(quán)值與屬性值 $a^v$ 對(duì)應(yīng)的子結(jié)點(diǎn)中調(diào)整為 $\tilde{r_v}\cdot w_x$ 逛尚。

就是讓同一個(gè)樣本以不同的概率劃入到不同的子結(jié)點(diǎn)中去垄惧。

{1,2,3,4,5,6,15}進(jìn)入“紋理=清晰”分支，{7,9,13,14,15}進(jìn)入“紋理=稍糊”分支绰寞，{11,12,16}進(jìn)入“紋理=模糊”分支到逊，且樣本在各子結(jié)點(diǎn)中權(quán)重保持1.

{8}在“紋理”上屬性缺失，將同時(shí)進(jìn)入三個(gè)分支中克握，但權(quán)重在三個(gè)子結(jié)點(diǎn)中分別調(diào)整為 $\frac{7}{15} 蕾管、\frac{5}{15} 、\frac{3}{15}$ 菩暗。{10}類似掰曾。

5 多變量決策樹

決策樹分類邊界的特點(diǎn)：軸平行，這是的學(xué)習(xí)結(jié)果有較好的可解釋性停团，每一段劃分都直接對(duì)應(yīng)某個(gè)屬性取值旷坦。

但在真實(shí)分類邊界比較復(fù)雜時(shí)，必須使用很多段劃分才能獲得較好的近似佑稠。

多變量決策樹：斜劃分秒梅，非葉結(jié)點(diǎn)對(duì)屬性的線性組合進(jìn)行測(cè)試，不再針對(duì)某個(gè)屬性舌胶。

最后編輯于：2019.03.04 10:31:18

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末捆蜀，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌辆它，老刑警劉巖誊薄，帶你破解...
沈念sama閱讀 218,204評(píng)論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異锰茉，居然都是意外死亡呢蔫，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,091評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門飒筑，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)片吊，“玉大人，你說(shuō)我怎么就攤上這事协屡∏渭梗” “怎么了？”我有些...
開封第一講書人閱讀 164,548評(píng)論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵著瓶，是天一觀的道長(zhǎng)联予。經(jīng)常有香客問(wèn)我啼县，道長(zhǎng)材原，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,657評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任季眷，我火速辦了婚禮余蟹，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘子刮。我一直安慰自己威酒，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,689評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布挺峡。她就那樣靜靜地躺著葵孤，像睡著了一般。火紅的嫁衣襯著肌膚如雪橱赠。梳的紋絲不亂的頭發(fā)上尤仍，一...
開封第一講書人閱讀 51,554評(píng)論 1贊 305
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音狭姨，去河邊找鬼宰啦。笑死，一個(gè)胖子當(dāng)著我的面吹牛饼拍，可吹牛的內(nèi)容都是我干的赡模。我是一名探鬼主播，決...
沈念sama閱讀 40,302評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼师抄，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼漓柑！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,216評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤辆布，失蹤者是張志新（化名）和其女友劉穎栋豫，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體谚殊，經(jīng)...
沈念sama閱讀 45,661評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡丧鸯，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,851評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了嫩絮。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片丛肢。...
茶點(diǎn)故事閱讀 39,977評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖剿干，靈堂內(nèi)的尸體忽然破棺而出蜂怎，到底是詐尸還是另有隱情，我是刑警寧澤置尔，帶...
沈念sama閱讀 35,697評(píng)論 5贊 347
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布杠步，位于F島的核電站，受9級(jí)特大地震影響榜轿，放射性物質(zhì)發(fā)生泄漏幽歼。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,306評(píng)論 3贊 330
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一谬盐、第九天我趴在偏房一處隱蔽的房頂上張望甸私。院中可真熱鬧，春花似錦飞傀、人聲如沸皇型。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,898評(píng)論 0贊 22
一樁弒父案砸烦，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)弃鸦。三九已至，卻和暖如春幢痘，著一層夾襖步出監(jiān)牢的瞬間唬格，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,019評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工雪隧，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留西轩，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,138評(píng)論 3贊 370
代替公主和親
正文我出身青樓脑沿，卻偏偏與公主長(zhǎng)得像藕畔，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子庄拇，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,927評(píng)論 2贊 355

決策樹