決策樹

決策樹是一種基本的分類與回歸方法。
學習時毁涉，利用訓練數(shù)據(jù)沉帮，根據(jù)損失函數(shù)最小化的原則建立決策樹模型。
決策樹學習通常包括3個步驟：特征選擇贫堰、決策樹的生成穆壕、決策樹的修剪。
相關算法實現(xiàn)有 ID3其屏，C4.5喇勋，CART。

一偎行、模型

用決策樹分類川背，從根節(jié)點開始，對實例的某一特征進行測試蛤袒，根據(jù)測試結果熄云，將實例分配到其子節(jié)點；這時妙真，每一個子結點對應著改特征的一個取值缴允。如此遞歸地對實例進行測試并分配，直至達到葉節(jié)點珍德。最后將實例分到葉節(jié)點的類中练般。

決策樹學習的損失函數(shù)通常是正則化的極大似然函數(shù)矗漾。

二、特征選擇

如果一個特征具有更好的分類能力薄料，使得各個子集在當前條件下有最好的分類敞贡，那么就應該選擇這個特征。信息增益 就能夠很好地表示這一直觀的準則都办。

信息增益

理解信息增益嫡锌，需要先理解熵與 條件熵 的定義。

熵（entropy）是表示變量不確定性的度量琳钉。

設 X 是一個取有限個值的離散隨機變量，其概率分布為
$P(X=x_i)=p_i蛛倦，i=1,2,...,n$
則隨機變量 X 的熵定義為
$H(X)=-\sum_{i=1}^np_ilogp_i$
上式中以 2 為底或以 e 為底歌懒，這時熵的單位分別稱作比特或納特。

熵越大溯壶，隨機變量的不確定性就越大及皂。

設有隨機變量（X,Y），其聯(lián)合概率分布為
$P(X=x_i,Y=y_j)=p_{ij}, i=1,2,...,n; j=1,2,...,m$
條件熵 H(Y|X) 表示在已知隨機變量 X 的條件下隨機變量 Y 的不確定性且改。 $H(Y|X)=\sum^n_{i=1}p_iH(Y|X=x_i)$
這里验烧， $p_i=P(X=x_i),i=1,2,...,n.$

信息增益 表示得知 特征X 的信息而使得類Y 的信息的不確定性減少的程度。

特征A 對訓練數(shù)據(jù)集 D 的信息增益 g(D,A), 定義為集合D的經驗熵 H(D) 與特征A給定條件下D的經驗條件熵 H(D|A) 之差又跛，即
$g(D,A)=H(D)-H(D|A)$

根據(jù)信息增益準則的特征選擇方法是：對訓練數(shù)據(jù)集（或子集）D碍拆，計算其每個特征的信息增益，并比較它們的大小慨蓝，選擇信息增益最大的特征感混。

信息增益的算法

設訓練數(shù)據(jù)集為 $D$ ， $|D|$ 表示其樣本容量礼烈。
設有 $K$ 個類 $C_k$ 弧满， $|C_k|$ 表示為屬于類 $C_k$ 的樣本個數(shù)， $k=1,2,...,K$ 此熬。
設特征 $A$ 有 $n$ 個不同的取值庭呜，根據(jù)特征 $A$ 的取值將 $D$ 分為 $n$ 個子集 $D_1,D_2,...,D_n$ ， $|D_i|$ 為 $D_i$ 的樣本個數(shù)犀忱。
子集 $D_i$ 中屬于 $C_k$ 的樣本的集合為 $D_{ik}$ 募谎， $|D_{ik}|$ 為 $D_{ik}$ 的樣本個數(shù)。

(1) 計算數(shù)據(jù)集 $D$ 的經驗熵 $H(D)$
$H(D)=-\sum^K_{k=1}\frac{|C_k|}{D}log_2\frac{|C_k|}{D}$

(2) 計算特征 $A$ 對數(shù)據(jù)集 $D$ 的經驗條件熵 $H(D|A)$
$H(D|A)=\sum^n_{i=1}\frac{D_i}{D}H(D_i)=-\sum^n_{i=1}\frac{D_i}{D}\sum^K_{k=1}\frac{D_{ik}}{D_i}log_2\frac{|D_{ik}|}{|D_i|}$
其中 $H(D_i)$ 為
$H(D_i)=-\sum^K_{k=1}\frac{D_{ik}}{D_i}log_2\frac{|D_{ik}|}{|D_i|}$

(3) 計算信息增益
$g(D,A)=H(D)-H(D|A)$

信息增益比

特征 A 對訓練數(shù)據(jù)集 D 的信息增益比 $g_R(D,A)$ 定義為其信息增益 $g(D,A)$ 與訓練數(shù)據(jù)集 D 的經驗熵 H(D) 之比：
$g_R(D,A)=\frac{g(D,A)}{H(D)}$

三峡碉、決策樹的生成

ID3 算法

ID3 算法的核心思想就是以信息增益來度量屬性的選擇近哟，選擇分裂后信息增益最大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策空間鲫寄。

ID3 算法只有樹的生成吉执，容易產生過擬合疯淫。

C4.5 算法

C4.5 算法對 ID3 算法做了改進，C4.5 在生成過程中戳玫，用信息增益比來選擇特征熙掺。

四、決策樹的剪枝

剪枝是決策樹算法對付過擬合的主要方法咕宿”壹ǎ基本策略有 預剪枝 和 后剪枝。

預剪枝

預剪枝是指在決策樹生成過程中府阀，對每個結點在劃分前先進行估計缆镣，若當前結點的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當前結點標記為葉結點试浙。
預剪枝降低了過擬合的風險董瞻，顯著減少了決策樹的訓練時間開銷和測試時間開銷，但可能帶來欠擬合的風險田巴。

后剪枝

后剪枝則是先從訓練集生成一棵完整的決策樹钠糊，然后自底向上地對非葉結點進行考察，若將該結點對應的子樹替換為葉結點能帶來決策樹泛化性能提升壹哺，則將該子樹替換為葉結點抄伍。
后剪枝決策樹的欠擬合風險很小，泛化性能往往優(yōu)于預剪枝決策樹.但其訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大得多管宵。

剪枝往往通過極小化決策樹整體的損失函數(shù)來實現(xiàn)截珍。

設樹 $T$ 的葉結點個數(shù)為 $|T|$ ， $t$ 是樹 $T$ 的葉節(jié)點啄糙，該結點有 $N_t$ 個樣本點笛臣，其中 $k$ 類的樣本點有 $N_tk$ 個， $k=1,2,...,K$ 隧饼， $H_t(T)$ 為葉結點 $t$ 上的經驗熵沈堡， $a \ge 0$ 為參數(shù)，則決策樹學習的損失函數(shù)可以定義為
$C_a(T)=\sum^{|T|}_{t=1}N_tH_t(T)+a|T|$
其中經驗熵為
$H_t(T)=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$
在算是函數(shù)中燕雁，令
$C(T)=-\sum^{|T|}_{t=1}\sum_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t}$
這時有
$C_a(T)=C(T)+a|T|$

上式中诞丽， $C(T)$ 表示模型對訓練數(shù)據(jù)的預測誤差，即模型與訓練數(shù)據(jù)的擬合程度拐格， $|T|$ 表示模型復雜度僧免。參數(shù) $a \ge 0$ 控制兩者之間的影響。較大的 $a$ 促使選擇較簡單的模型捏浊，較小的 $a$ 促使選擇較復雜的模型懂衩。 $a=0$ 意味著只考慮模型與訓練數(shù)據(jù)的擬合程度，不考慮模型復雜度。

樹的剪枝算法

(1) 計算每個結點的經驗熵浊洞。
(2) 遞歸的從樹的葉結點向上回縮牵敷。
設一組葉結點回縮到其父結點之前與之后的整體樹分別為 $T_B$ 與 $T_A$ ，其對應的損失函數(shù)值分別是 $C_a(T_B)$ 與 $C_a(T_A)$ 法希，如果
$C_a(T_A) \le C_a(T_B)$
則進行剪枝枷餐，即將父結點變?yōu)樾碌娜~結點。
(3) 返回 (2) 苫亦。直至不能繼續(xù)為止毛肋，得到損失函數(shù)最小的子樹 $T_a$ 。

五屋剑、CART 算法

CART 算法由以下兩步組成：
(1) 決策樹生成：基于訓練數(shù)據(jù)集生成決策樹润匙，生成的決策樹要盡量大。
(2) 決策樹剪枝：用于驗證數(shù)據(jù)集對已生成的數(shù)進行剪枝并選擇最優(yōu)子樹唉匾，這時用損失函數(shù)最小作為剪枝的標準趁桃。

分類樹的生成

分類樹用基尼指數(shù)選擇最優(yōu)特征，同時決定該特征的最優(yōu)二值切分點肄鸽。

基尼指數(shù)

分類問題中，假設有 $K$ 個類油啤，樣本點屬于第 $k$ 類的概率為 $p_k$ 典徘，則概率分布的基尼指數(shù)定義為
$Gini(p)=\sum^K_{k=1}p_k(1-p_k)=1-\sum^K_{k=1}p^2_k$

對于給定的樣本集合 $D$ ，其基尼指數(shù)為
$Gini(D)=1-\sum^K_{k=1}(\frac{|C_k|}{D})^2$
這里益咬， $C_k$ 是 $D$ 中屬于第 $k$ 類的樣本子集逮诲， $K$ 是類的個數(shù)。

如果樣本集合 D 根據(jù)特征 A 是否取某一可能值 a 被分割成 D_1 和 D_2 兩部分幽告，則在特征 A 的條件下梅鹦，集合 D 的基尼指數(shù)定義為
$Gini(D,A)=\frac{|D_1|}{D}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)$

基尼指數(shù) $Gini(D,A)$ 表示經 $A=a$ 分割后集合 $D$ 的不確定性∪咚基尼指數(shù)值越大齐唆，樣本集合的不確定性就越大。

CART 生成算法

(1) 設結點的訓練數(shù)據(jù)集為 $D$ 冻河，計算現(xiàn)有特征對該數(shù)據(jù)集的基尼指數(shù)箍邮。此時，對每一個特征 $A$ 叨叙，對其可能取的每個值 $a$ 锭弊，根據(jù)樣本點對 $A=a$ 的測試為“是”或“否”將 $D$ 分割成 $D_1$ 和 $D_2$ 兩部分，計算 $A=a$ 時的基尼指數(shù)擂错。
(2) 在所有可能的特征 $A$ 以及它們所有可能的切分點 $a$ 中味滞，選擇基尼指數(shù)最小的特征及其對應的切分點作為最優(yōu)特征與最優(yōu)切分點。依最優(yōu)特征與最優(yōu)切分點，從現(xiàn)結點生成兩個子結點剑鞍，將訓練數(shù)據(jù)集依特征分配到兩個子結點中去昨凡。
(3) 對兩個子結點遞歸地調用 (1)，(2)攒暇，直至滿足停止條件土匀。
(4) 生成 CART 決策樹。

CART 剪枝

(1) 設 $k=0$ 形用， $T=T_0$ 就轧。
(2) 設 $a=+\infty$ 。
(3) 自下而上地對各內部結點 $t$ 計算 $C(T_t)$ 田度， $|T_t|$ 以及
$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}\\ a=min(a,g(t))$
這里妒御， $T_t$ 表示以 $t$ 為根結點的子樹， $C(T_t)$ 是對訓練數(shù)據(jù)的預測誤差镇饺， $|T_t|$ 是 $T_t$ 的葉結點個數(shù)乎莉。
(4) 自上而下地訪問內部結點 $t$ ，如果有 $g(t)=a$ 奸笤，進行剪枝惋啃，并對葉結點 $t$ 以多數(shù)表決法決定其類，得到樹 $T$ 监右。
(5) 設 $k=k+1边灭，a_k=a，T_k=T$ 健盒。
(6) 如果 $T$ 不是由根結點單獨構成的樹绒瘦，則回到步驟(4)。
(7) 采用交叉驗證法在子樹序列 $T_0,T_1,...,T_n$ 中選取最優(yōu)子樹 $T_a$ 扣癣。

六惰帽、補充

連續(xù)值處理

對連續(xù)屬性的劃分，最簡單的策略是采用二分法對連續(xù)屬性進行處理父虑。

(1) 將連續(xù)屬性的 $n$ 個數(shù)值排序该酗。
(2) 取兩兩數(shù)的平均值為劃分點，共 $n-1$ 個频轿。
(3) 分別求每個劃分點下的經驗熵 $H(D_t^{-})$ 和 $H(D_t^+)$ 垂涯。
(4) 求每個劃分點的信息增益
$g(D,a,t) = H(D) - \sum_{\lambda\in (-,+)}\frac{|D^\lambda _t |}{|D|}H(D^\lambda _t )$
(5) 找出所有劃分點的最大信息增益，和其對應的劃分點航邢。

與離散屬性不同耕赘，若當前結點劃分屬性為連續(xù)屬性，該屬性還可作為其后代結點的劃分屬性膳殷。

缺失值處理

最后編輯于：2019.02.21 15:56:34

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末操骡，一起剝皮案震驚了整個濱河市九火，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌册招，老刑警劉巖岔激，帶你破解...
沈念sama閱讀 217,084評論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異是掰，居然都是意外死亡虑鼎，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,623評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門键痛，熙熙樓的掌柜王于貴愁眉苦臉地迎上來炫彩，“玉大人，你說我怎么就攤上這事絮短〗ぃ” “怎么了？”我有些...
開封第一講書人閱讀 163,450評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵丁频，是天一觀的道長杉允。經常有香客問我，道長席里，這世上最難降的妖魔是什么叔磷？我笑而不...
開封第一講書人閱讀 58,322評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮奖磁，結果婚禮上世澜，老公的妹妹穿的比我還像新娘。我一直安慰自己署穗，他們只是感情好，可當我...
茶點故事閱讀 67,370評論 6贊 390
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布嵌洼。她就那樣靜靜地躺著案疲，像睡著了一般。火紅的嫁衣襯著肌膚如雪麻养。梳的紋絲不亂的頭發(fā)上褐啡，一...
開封第一講書人閱讀 51,274評論 1贊 300
城市分裂傳說
那天，我揣著相機與錄音鳖昌，去河邊找鬼备畦。笑死，一個胖子當著我的面吹牛许昨，可吹牛的內容都是我干的懂盐。我是一名探鬼主播，決...
沈念sama閱讀 40,126評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼糕档，長吁一口氣：“原來是場噩夢啊……” “哼莉恼！你這毒婦竟也來了？” 一聲冷哼從身側響起，我...
開封第一講書人閱讀 38,980評論 0贊 275
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤俐银，失蹤者是張志新（化名）和其女友劉穎尿背，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體捶惜，經...
沈念sama閱讀 45,414評論 1贊 313
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡田藐，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 37,599評論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了吱七。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片汽久。...
茶點故事閱讀 39,773評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖陪捷，靈堂內的尸體忽然破棺而出回窘，到底是詐尸還是另有隱情，我是刑警寧澤市袖，帶...
沈念sama閱讀 35,470評論 5贊 344
?日本核電站爆炸內幕
正文年R本政府宣布啡直，位于F島的核電站，受9級特大地震影響苍碟，放射性物質發(fā)生泄漏酒觅。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,080評論 3贊 327
男人毒藥：我在死后第九天來索命
文/蒙蒙一微峰、第九天我趴在偏房一處隱蔽的房頂上張望舷丹。院中可真熱鬧，春花似錦蜓肆、人聲如沸颜凯。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,713評論 0贊 22
一樁弒父案仗扬，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽症概。三九已至，卻和暖如春早芭，著一層夾襖步出監(jiān)牢的瞬間彼城，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,852評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工退个，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留募壕，地道東北人。一個月前我還...
沈念sama閱讀 47,865評論 2贊 370
代替公主和親
正文我出身青樓语盈，卻偏偏與公主長得像舱馅，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子刀荒，可洞房花燭夜當晚...
茶點故事閱讀 44,689評論 2贊 354

決策樹