決策樹缺失值處理方法

缺失值場景

（1）在各列特征都有缺失值時，選擇哪列特征去目前劃分分支？

（2）標明劃分分支的特征後，如果某樣本在該特征上取值缺失，該把這個樣本劃分到哪個分支？

一些數學原理

特征 a a a的 V V V個取值 { a 1 , a 2 , . . . , a V } \{a^1, a^2, ..., a^V\} {a1,a2,...,aV}

樣本子集 D ~ \tilde{D} D~中，屬于第 k k k類 ( k = 1 , 2 , . . . , N ) (k=1,2,...,N) (k=1,2,...,N)的子集為 D ~ k \tilde{D}_k D~k​

=> D ~ = ⋃ k = 1 N D ~ k = ⋃ v = 1 V D ~ v \tilde{D}=\bigcup_{k=1}^N \tilde{D}_k=\bigcup_{v=1}^V \tilde{D}^v D~=⋃k=1N​D~k​=⋃v=1V​D~v

假定樣本 x x x的權重為 w x w_x wx​，則對特征 a a a有

無 缺 失 樣 本 占 比 ： ρ = ∑ x ∈ D ~ w x ∑ x ∈ D w w 無缺失樣本占比：\rho=\frac{\sum_{x\in\tilde{D}}w_x}{\sum_{x\in D}w_w} 無缺失樣本占比：ρ=∑x∈D​ww​∑x∈D~​wx​​

無 缺 失 樣 本 , 第 k 類 占 比 ： p ~ k = ∑ x ∈ D ~ k w x ∑ x ∈ D ~ w x ( 1 ≤ k ≤ N ) 無缺失樣本,第k類占比：\tilde{p}_k=\frac{\sum_{x\in\tilde{D}_k}w_x}{\sum_{x\in \tilde{D}}w_x}(1\leq k\leq N) 無缺失樣本,第k類占比：p~​k​=∑x∈D~​wx​∑x∈D~k​​wx​​(1≤k≤N)

無 缺 失 樣 本 , 特 征 a = a v 占 比 ： r ~ v = ∑ x ∈ D ~ v w x ∑ x ∈ D ~ w x ( 1 ≤ v ≤ V ) 無缺失樣本,特征a=a^v占比：\tilde{r}_v=\frac{\sum_{x\in\tilde{D}^v}w_x}{\sum_{x\in \tilde{D}}w_x}(1\leq v\leq V) 無缺失樣本,特征a=av占比：r~v​=∑x∈D~​wx​∑x∈D~v​wx​​(1≤v≤V)

相應的資訊增益為

G a i n ( D , a ) = ρ × ( E n t ( D ~ ) − ∑ v = 1 V r ~ v E n t ( D ~ v ) ) , E n t ( D ~ ) = − ∑ k = 1 N p ~ k l o g p ~ k Gain(D,a)=\rho\times\Big(Ent(\tilde{D})-\sum\limits_{v=1}^V\tilde{r}_vEnt(\tilde{D}_v)\Big),Ent(\tilde{D})=-\sum\limits_{k=1}^N\tilde{p}_k log\tilde{p}_k Gain(D,a)=ρ×(Ent(D~)−v=1∑V​r~v​Ent(D~v​)),Ent(D~)=−k=1∑N​p~​k​logp~​k​

分裂方法

訓練集 D D D，特征 a a a，在特征 a a a上有值(非缺失)的樣本子集 D ~ \tilde{D} D~

=> 則根據子集 D ~ \tilde{D} D~ 判定特征 a a a的優劣

在標明特征 a a a上缺失的樣本，劃分特征 a a a時

=> 把該樣本 同時劃入所有子節點，按特征 a a a的取值占比 計算樣本分裂到各分支的權重 r ~ v w x \tilde{r}_v w_x r~v​wx​