原理

決策樹是一種基本的分類與回歸方法讥邻，其模型就是用一棵樹來表示我們的整個決策過程夷野。這棵樹可以是二叉樹（比如CART 只能是二叉樹）蒿辙，也可以是多叉樹（比如 ID3拇泛、C4.5 可以是多叉樹或二叉樹）。根節(jié)點包含整個樣本集思灌，每個葉節(jié)都對應一個決策結果（注意俺叭，不同的葉節(jié)點可能對應同一個決策結果），每一個內(nèi)部節(jié)點都對應一次決策過程或者說是一次屬性測試泰偿。從根節(jié)點到每個葉節(jié)點的路徑對應一個判定測試序列熄守。

ID3、C4.5耗跛、CART

這三個是非常著名的決策樹算法裕照。簡單粗暴來說:

ID3 使用信息增益作為選擇特征的準則；

C4.5 使用信息增益比作為選擇特征的準則调塌；

CART 使用 Gini 指數(shù)作為選擇特征的準則晋南。

熵

在信息論與概率論中，熵用于表示隨機變量不確定性的度量羔砾。
設X是一個有限狀態(tài)的離散型隨機變量负间，其概率分布為:

image.png

則隨機變量X的熵定義為：

image.png

image.png

其中趾访，pi = P(X = xi)。
信息增益(information gain)
信息增益表示的是：得知特征X的信息而使得類Y的信息的不確定性減少的程度董虱。
特征A對訓練數(shù)據(jù)集D的信息增益g(D,A)定義為集合D的經(jīng)驗熵H(D)與特征A給定
條件下D的經(jīng)驗條件熵H(D|A)之差腹缩，即g(D,A)=H(D)-H(D|A)

ID3

熵表示的是數(shù)據(jù)中包含的信息量大小(混亂度)。熵越小空扎，數(shù)據(jù)的純度越高藏鹊，也就是
說數(shù)據(jù)越趨于一致，這是我們希望的劃分之后每個子節(jié)點的樣子转锈。
信息增益 = 劃分前熵 - 劃分后熵盘寡。信息增益越大，則意味著使用屬性a來進行劃
分所獲得的 “純度提升” 越大 撮慨。也就是說竿痰，用屬性a來劃分訓練集，得到的結果
中純度比較高砌溺。

ID3 僅僅適用于二分類問題影涉。ID3 僅僅能夠處理離散屬性。

C4.5

C4.5 克服了ID3僅僅能夠處理離散屬性的問題规伐，以及信息增益偏向選擇取值較多特征的問題蟹倾，使用信息增益比來選擇特征。信息增益比 = 信息增益 / 劃分前熵 選擇信息增益比最大的作為最優(yōu)特征猖闪。

image.png

C4.5 處理連續(xù)特征是先將特征取值排序鲜棠，以連續(xù)兩個值中間值作為劃分標準。嘗試每一種劃分培慌，并計算修正后的信息增益豁陆，選擇信息增益最大的分裂點作為該屬性的分裂點。

CART

CART 與 ID3吵护，C4.5 不同之處在于 CART 生成的樹必須是二叉樹盒音。也就是說，無論是回歸還是分類問題馅而，無論特征是離散的還是連續(xù)的祥诽，無論屬性取值有多個還是兩個，內(nèi)部節(jié)點只能根據(jù)屬性值進行二分用爪。

CART 的全稱是分類與回歸樹（classification and regression tree）原押。從這個名字中就應該知道，CART 既可以用于分類問題偎血，也可以用于回歸問題诸衔。

回歸樹

使用平方誤差最小化準則來選擇特征并進行劃分盯漂。每一個葉子節(jié)點給出的預測值，是劃分到該葉子節(jié)點的所有樣本目標值的均值笨农，這樣只是在給定劃分的情況下最小化了平方誤差就缆。

要確定最優(yōu)化分，還需要遍歷所有屬性谒亦，以及其所有的取值來分別嘗試劃分并計算在此種劃分情況下的最小平方誤差竭宰，選取最小的作為此次劃分的依據(jù)。由于回歸樹生成使用平方誤差最小化準則份招，所以又叫做最小二乘回歸樹切揭。

具體為，假設已將輸入空間劃分為 M 個單元R1,R2,...,Rm锁摔，即 M 個特征廓旬，并且在每個單元Rm上有一個固定的輸出值Cm，于是回歸樹可以表示為

image.png

信息增益 vs 信息增益比

信息增益的一個缺點,那就是：信息增益總是偏向于選擇取值較多的屬性谐腰。信息增益比在此基礎上增加了一個罰項孕豹，解決了這個問題。

Gini 指數(shù) vs 熵

既然這兩個都可以表示數(shù)據(jù)的不確定性十气，不純度励背。那么這兩個有什么區(qū)別那？

Gini 指數(shù)的計算不需要對數(shù)運算砸西，更加高效叶眉；

Gini 指數(shù)更偏向于連續(xù)屬性，熵更偏向于離散屬性籍胯。

決策樹的剪枝

決策樹算法很容易過擬合（overfitting）竟闪，剪枝算法就是用來防止決策樹過擬合，提高泛華性能的方法杖狼，剪枝分為預剪枝與后剪枝。

預剪枝

預剪枝是指在決策樹的生成過程中妖爷，設置一個閾值,對每個節(jié)點在劃分前先進行評估蝶涩，若當前的劃分不能帶來泛化性能的提升，則停止劃分絮识，并將當前節(jié)點標記為葉節(jié)點绿聘。

后剪枝

后剪枝是指先從訓練集生成一顆完整的決策樹，然后自底向上對非葉節(jié)點進行考察次舌，若將該節(jié)點對應的子樹替換為葉節(jié)點熄攘，能帶來泛化性能的提升，則將該子樹替換為葉節(jié)點彼念。

總結

決策樹算法主要包括三個部分：特征選擇挪圾、樹的生成浅萧、樹的剪枝。常用算法有 ID3哲思、C4.5洼畅、CART。

特征選擇棚赔。特征選擇的目的是選取能夠?qū)τ柧毤诸惖奶卣鞯鄞亍Ｌ卣鬟x擇的關鍵是準則：信息增益、信息增益比靠益、Gini 指數(shù)丧肴；

決策樹的生成。通常是利用信息增益最大胧后、信息增益比最大芋浮、Gini 指數(shù)最小作為特征選擇的準則。從根節(jié)點開始绩卤，遞歸的生成決策樹途样。相當于是不斷選取局部最優(yōu)特征，或?qū)⒂柧毤指顬榛灸軌蛘_分類的子集濒憋；

決策樹的剪枝何暇。決策樹的剪枝是為了防止樹的過擬合，增強其泛化能力凛驮。包括預剪枝和后剪枝裆站。

對比預剪枝與后剪枝生成的決策樹，可以看出黔夭，后剪枝通常比預剪枝保留更多的分支宏胯，其欠擬合風險很小，因此后剪枝的泛化性能往往大于預剪枝決策樹本姥。但后剪枝過程是從底往上裁剪肩袍，因此其訓練時間開銷比前剪枝要大。