决策树缺失值处理方法

缺失值场景

（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​