決策樹Decision Tree

決策樹

既可以應用于分類問題，也可以應用于回歸問題。

應用

優點

1. 非線性
2. 交叉效應
3. 稀疏性

缺點

1. 不穩定
2. 表現力較差
3. 精度不足

僞代碼

def TreeGenerate(D, A):
    生成節點node
    if D中樣本全屬于類别C:
        将node标記為C類葉節點
        return
    if A = ∅ or D中樣本在A上取值相同:
        将node标記為D中樣本數最多的類葉節點
        return       
    從A中選擇最優劃分屬性a
    for a_v in a:
        為node生成一個分支;令Dv表示D中在a上取值為a_v的樣本子集
        if Dv = ∅:
            将node标記為D中樣本數最多的類葉節點
        else:
            以TreeGenerate(Dv, A\{a})為分支節點
           

三種終止遞歸條件：

1. 目前節點包含樣本屬于同一類，無需劃分
2. 目前屬性集合為空，或所有樣本在所有屬性上取值相同，無法劃分
3. 目前節點包含的樣本集合為空，不能劃分

劃分選擇

資訊增益 Info Gain

p k p_k pk​ 是k類别在整體中所占比例。

資訊熵 E n t ( D ) = − ∑ k = 1 K p k l o g 2 ( p k ) Ent(D) = -\sum_{k=1}^K p_klog_2(p_k) Ent(D)=−∑k=1K​pk​log2​(pk​)

資訊熵的值越小，D的純度越高。假設離散屬性a有V個可能的取值， a 1 , a 2 , . . . , a V {a_1, a_2,..., a_V} a1​,a2​,...,aV​, 若使用a來對樣本D進行劃分，會産生V個分支節點。計算屬性a對樣本集D進行劃分得到的資訊增益。

G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V D v D E n t ( D v ) Gain(D, a) = Ent(D) - \sum_{v=1}^V \frac{D_v}{D} Ent(D_v) Gain(D,a)=Ent(D)−∑v=1V​DDv​​Ent(Dv​)

ID3決策樹算法就是用資訊增益為準則來選擇劃分屬性。但是這種算法對可取值數目較多的屬性有所偏好。

增益率 Gain Ratio

G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)​

其中 I V ( a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(a) = \sum_{v=1}^V \frac{|D_v|}{|D|}log_2\frac{|D_v|}{|D|} IV(a)=∑v=1V​∣D∣∣Dv​∣​log2​∣D∣∣Dv​∣​被稱為a的固有值。

C4.5決策樹算法利用增益率來選擇最優劃分屬性。

基尼指數 Gini Index

Gini(D)反映從資料集D中随機抽取兩樣本，其類别标記不一緻的機率。是以Gini(D)越小，資料集D的純度越高。

Gini impurity G i n i ( D ) = 1 − ∑ k = 1 K p k 2 Gini(D) = 1 - \sum_{k=1}^K p_{k}^2 Gini(D)=1−∑k=1K​pk2​

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

選擇使得劃分後基尼指數最小的屬性 a ∗ = a r g m i n a ∈ A G i n i _ i n d e x ( D , a ) a^* = arg min_{a \in A} Gini\_index(D, a) a∗=argmina∈A​Gini_index(D,a)

sklearn中使用的CART算法就是用Gini impurity做名額。

精度提升方法

剪枝處理是緩和過拟合的主要手段。基本政策有預剪枝和後剪枝。

預剪枝

在決策樹生成過程中，若目前節點的劃分不能帶來泛化性能提升，則停止劃分。預剪枝使得決策樹的很多分支都沒有展開，降低了過拟合風險，減少了訓練和測試時間。不過，有些分支的目前劃分雖不能提升泛化性能，但是在其基礎上進行的後續劃分卻有可能導緻性能顯著提高，帶來了欠拟合的風險。

後剪枝

訓練集生成的一棵完整決策樹自下而上對節點進行考察，如果該節點對應子樹替換為葉節點能帶來決策樹泛化性能提升，則将該子樹替換為葉節點。欠拟合風險很小，不過訓練時間要比不剪枝大得多。

連續值

連續屬性離散化。最簡單的政策就是采用二分法。給定樣本集D和連續屬性a，将該屬性所有值排序。基于劃分點t可将D分為 D t − D^-_t Dt−​和 D t + D^+_t Dt+​。之後我們可以計算資訊增益來确定合适的分割點。

需要注意的是，與離散屬性不同，若目前節點劃分屬性是連續屬性，該屬性還可作為其後代節點的劃分屬性。

缺失值處理

給定訓練集D和屬性a，用 D ~ \widetilde D D

表示D中在屬性a上沒有缺失值的樣本。為了解決在有屬性值缺失的情況下進行屬性劃分，可以給每一個樣本x賦予一個權重 w x w_x wx​。

ρ = ∑ x ∈ D ~ w x ∑ x ∈ D w x \rho = \frac{\sum_{x \in \widetilde D}w_x}{\sum_{x \in D}w_x} ρ=∑x∈D​wx​∑x∈D

​wx​​表示無缺失值樣本所占比例

p ~ k = ∑ x ∈ D ~ k w x ∑ x ∈ D ~ w x \widetilde p_k = \frac{\sum_{x \in \widetilde D_k}w_x}{\sum_{x \in \widetilde D}w_x} p

​k​=∑x∈D

​wx​∑x∈D

k​​wx​​表示無缺失值樣本中第k類所占比例

r ~ v = ∑ x ∈ D ~ v w x ∑ x ∈ D ~ w x \widetilde r_v = \frac{\sum_{x \in \widetilde D_v}w_x}{\sum_{x \in \widetilde D}w_x} r

v​=∑x∈D

​wx​∑x∈D

v​​wx​​表示無缺失值樣本中在屬性a上取值是 a v a_v av​的樣本所占比例

我們可以将資訊增益的計算式推廣成

G a i n ( D , a ) = ρ ∗ E n t ( D ~ ) − ρ ∗ ∑ v = 1 V r ~ v E n t ( D ~ v ) Gain(D, a) = \rho * Ent(\widetilde D) - \rho* \sum_{v=1}^V \widetilde r_v Ent(\widetilde D_v) Gain(D,a)=ρ∗Ent(D

)−ρ∗∑v=1V​r

v​Ent(D

v​)

為了解決特定樣本在該屬性上的值缺失時的樣本劃分問題，讓這個樣本以不同的機率劃入到不同的子節點中去。

多變量決策樹

可以對分類邊界進行不是沿着平行軸的方向進行劃分的或者進行其他複雜劃分的決策樹。

Reference

• 《美團機器學習實踐》by美團算法團隊，第三章
• 《機器學習》by周志華，第三、四章
• 白闆推導系列，shuhuai007