1.簡介
根據損失函式最小化原則建立決策樹模型
損失函式一般是正則化的極大似然函式
本質上為從訓練資料集中歸納出的一組分類規則
每一個子結點對應一個特征取值，葉節點即一個類
步驟
特征選擇、決策樹生成、決策樹修剪4
2.特征選擇
2.1 熵
使用熵度量隨機變數不確定性
P
(
X
=
x
i
)
=
p
i
P(X=x_i) = p_i
P(X=xi?)=pi?
則熵定義為
H
(
X
)
=
H
(
p
)
=
?
s
u
m
(
p
i
l
o
g
p
i
)
H(X)=H(p)=-sum(p_ilogp_i)
H(X)=H(p)=?sum(pi?logpi?)
對于條件概率分布
P
(
X
=
x
i
,
Y
=
y
i
)
=
p
i
j
P(X=x_i,Y=y_i)=p_{ij}
P(X=xi?,Y=yi?)=pij?
條件熵
H
(
Y
∣
X
)
=
s
u
m
(
p
i
H
(
Y
∣
X
=
x
i
)
)
H(Y|X)=sum(p_iH(Y|X=x_i))
H(Y∣X)=sum(pi?H(Y∣X=xi?))
通過極大似然估計獲得經驗熵
2.2資訊增益
資訊增益：特征A對訓練資料集D的資訊增益g(D,A),定義為集合D的經驗熵H(D)與特征A給定條件下D的經驗條件熵H(D|A)之差，即：
g
(
D
,
A
)
=
H
(
D
)
?
H
(
D
∣
A
)
g(D,A)= H(D)-H(D|A)
g(D,A)=H(D)?H(D∣A)
等價于訓練資料集中類與特征的互資訊
即由于特征A使得分類不確定性減少的程度
2.3資訊增益比
單純使用資訊增益可能存在偏向于選擇取值較多的特征的問題
特征A對訓練資料集D的資訊增益比定義為其資訊增益與訓練資料集D關于特征A的值的熵之比
g
R
(
D
,
A
)
=
g
(
D
,
A
)
H
A
(
D
)
g_R(D,A)=\frac{g(D,A)}{H_A(D)}
gR?(D,A)=HA?(D)g(D,A)?
H
A
(
D
)
=
?
∑
n
1
(
D
i
D
l
o
g
2
D
i
D
)
H_A(D)=-\sum{^n}{_1}(\frac{D_i}{D}log_2\frac{D_i}{D})
HA?(D)=?∑n1?(DDi??log2?DDi??)
n
為
特
征
A
取
值
數
量
，
D
i
為
特
征
A
取
值
i
時
樣
本
數
n為特征A取值數量，D_i為特征A取值i時樣本數
n為特征A取值數量，Di?為特征A取值i時樣本數
理解：避免了資訊增益時偏向于取值較多（n較大）的特征；取值數量n越大，分母越大，可以認為該項是一項懲罰項
3.決策樹的生成
3.1 ID3演算法
即在決策樹各個結點上應用資訊增益選擇特征，遞回地構建決策樹
步驟：從根結點開始，對結點計算所有可能的特征，選擇資訊增益最大的特征作為節點的特征，由特征的不同取值建立子結點，遞回構建直到所有資訊增益都很小（無用特征拋棄）或者所有特征都選完
- a.若類只有一個或特征取值為空，則回傳T單結點樹，節點標記為類
- b.計算資訊增益，獲得當前最大資訊增益特征，與閾值比較，小于則直接回傳，該節點標記為類，否則按照特征取值將訓練集劃分，將實體數最大的類作為標記，構建子結點
- c.對子結點，以劃分后訓練集為訓練集，以剩下特征為特征集，遞回呼叫
- 缺點：該演算法只有樹的生成，容易導致過擬合現象
3.2 C4.5演算法
在ID3的基礎上，使用資訊增益比選擇特征
4.決策樹的剪枝
提高模型的泛化能力（對預測資料的擬合）
一般通過使得損失函式最小決定剪枝
4.1 剪枝損失函式公式
C
α
(
T
)
=
s
u
m
(
N
t
H
t
(
T
)
+
α
(
T
)
)
C_α(T)=sum(N_tH_t(T) +α(T))
Cα?(T)=sum(Nt?Ht?(T)+α(T))
- T為樹
- t為葉節點
- Nt為樣本點
- Ntk為分類為k的樣本點個數
- 右邊代表復雜度
- 理解：即累計所有葉節點，分類熵作為損失函式（如果所有樣本點分類正確，則H（T）=0
4.2 剪枝演算法 - 計算每個結點的經驗熵
- 從葉結點往上，比較損失函式大小（剪枝前后），根據大小關系決定是否剪枝，遞回直到損失函式最小，回傳此時子數
5.CART演算法
即在給定輸入隨機變數X條件下輸出隨機變數Y的條件概率分布
5.1 最小二乘回歸生成
遞回地構建二叉決策樹，對回歸樹用平方誤差最小化準則，對分類樹用基尼系數最小化準則，進行特征選擇，生成最小樹
f
(
x
)
=
s
u
m
(
c
m
I
(
x
∈
R
m
)
f(x)=sum(c_mI(x∈R_m)
f(x)=sum(cm?I(x∈Rm?)
即隨機選擇一個輸入變數
x
j
=
s
x^j=s
xj=s將訓練集切分為兩塊
R
1
(
j
,
s
)
=
{
x
∣
x
j
<
=
s
}
R_1(j,s)=\{x|x^j<=s\}
R1?(j,s)={x∣xj<=s}
R
1
(
j
,
s
)
=
{
x
∣
x
j
>
s
}
R_1(j,s)=\{x|x^j>s\}
R1?(j,s)={x∣xj>s}
通過損失函式尋找最優切分變數j與切分點s
l
o
s
s
=
s
u
m
(
y
i
?
f
(
x
i
)
)
2
loss = sum(y_i-f(x_i))^2
loss=sum(yi??f(xi?))2
m
i
n
[
m
i
n
(
l
o
s
s
1
)
+
m
i
n
(
l
o
s
s
2
)
]
min[min(loss1)+min(loss2)]
min[min(loss1)+min(loss2)]
對于固定輸入變數j，最優切分點可以通過求均值找出
c
i
=
a
v
e
(
y
i
∣
x
i
∈
R
i
(
j
,
s
)
)
c_i=ave(y_i|x_i∈R_i(j,s))
ci?=ave(yi?∣xi?∈Ri?(j,s))
繼續對子區域劃分，最后得到回歸樹即最小二乘回歸樹
5.2分類樹生成
基尼指數:用于選擇最優特征
G
i
n
i
(
p
)
=
s
u
m
(
p
k
(
1
?
p
k
)
)
=
s
u
m
k
(
p
k
?
p
k
2
)
=
1
?
s
u
m
k
(
k
2
)
Gini(p)=sum(p_k(1-p_k))=sum^k(p_k-p_k^2)=1-sum^k(k^2)
Gini(p)=sum(pk?(1?pk?))=sumk(pk??pk2?)=1?sumk(k2)
- K為類個數
- 樣本點屬于K類概率即pk
在特征A的情況下,依照A是否取值a分為D1，D2資料集
G
i
n
i
(
D
,
A
)
=
∣
D
1
∣
∣
D
∣
G
i
n
i
(
D
1
)
+
∣
D
2
∣
∣
D
∣
G
i
n
i
D
2
Gini(D,A) =\frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini{D_2}
Gini(D,A)=∣D∣∣D1?∣?Gini(D1?)+∣D∣∣D2?∣?GiniD2?
理解：表示經過特征A切割（按照A取值分割資料集）后，集合的不確定性
5.3 CART生成演算法
- 對每種特征的每一種可能性，計算其基尼系數（依照是否取值劃分資料集）
- 選擇基尼指數最小的特征及其對應的切分點作為最優特征和最優切分點，生成兩個子結點，依照特征將訓練集劃分進去
- 對兩個子結點繼續遞回（篩選剩下特征）直到結點中樣本個數小于閾值
5.4 CART剪枝
C
α
(
T
)
=
C
(
T
)
+
α
∣
T
∣
C_α(T)=C(T)+α|T|
Cα?(T)=C(T)+α∣T∣
C(T)為預測誤差，|T|為子數的葉結點個數（復雜度）
使用α衡量復雜度的影響
- 從整體樹 T 0 T_0 T0?開始剪枝，對于任意內部結點t，以t為單節點樹的損失函式為
- C α ( t ) = C ( t ) + α C_α(t)=C(t) +α Cα?(t)=C(t)+α
- 以t為根節點的樹損失函式為
- C α ( T t ) = C ( T t ) + α ∣ T t ∣ C_α(T_t)=C(T_t)+α|T_t| Cα?(Tt?)=C(Tt?)+α∣Tt?∣
- 即對每一內部結點計算
- g ( t ) = C ( t ) ? C ( T t ) ∣ T t ∣ ? 1 g(t)=\frac{C(t)-C(T_t)}{|T_t|-1} g(t)=∣Tt?∣?1C(t)?C(Tt?)?衡量剪枝后整體損失函式減少的程度，分母即剪去的結點，g（t)為α取值
- 在 T i T_i Ti?中剪去g（t）最小的 T t T_t Tt?將得到的子數作為 T i + 1 T_{i+1} Ti+1?并將最小的g(t)設為α1，即區間[α1,α2)的最優子樹，重復剪枝直到根結點
- 交叉驗證：驗證所有子樹的損失函式，選擇最小損失函式對應的子樹 T i T_i Ti?與其對應的α
5.5CART剪枝演算法
- 設k=0, T = T 0 T=T_0 T=T0?
- 設 α = + ∞ α=+\infty α=+∞
- 自下而上計算各結點t的g(t)及 α = m i n ( α , g ( t ) ) α=min(α,g(t)) α=min(α,g(t))
- 對g(t)最小的結點剪枝，并以數量最多類作為該葉結點類，得到樹T
- 設k=k+1, α k = α , T k = T α_k=α,T_k=T αk?=α,Tk?=T
- 如果 T k T_k Tk?不是由根結點及兩個葉結點構成的樹，則令 α = + ∞ α=+\infty α=+∞繼續重復，否則 T k = T n T_k=T_n Tk?=Tn?
- 交叉驗證子樹，選擇最優
理解：由于α不固定，因此我們需要獲得各種α取值情況下的最優子樹，則在剪枝程序中，α也逐漸增大，最終得到n棵子樹，通過比較損失函式確定最優情況
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259405.html
標籤：AI
下一篇：為何你進不了大廠？