决策树相关学习

决策树

信息熵: 随机变量的不确定性的度量.

H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i} H(X)=−i=1∑n​pi​logpi​

0 ≤ H ( X ) ≤ log ⁡ n 0 \leq H(X) \leq \log n 0≤H(X)≤logn

信息增益: 得知特征X的信息而使得类Y的信息的不确定性减少的程度.

g ( Y , X ) = H ( Y ) − H ( Y │ X ) g(Y,X)=H(Y)-H(Y│X) g(Y,X)=H(Y)−H(Y│X)

信息增益算法

输入:训练数据集D和特征A

输出:特征A对训练数据集D的信息增益g(D,A)

1. 计算数据集D的经验熵H(D)

2. 计算特征A对数据D的经验条件熵H(D|A)

   H ( D ) = − ∑ i = 1 n ∣ C k ∣ ∣ D ∣ log ⁡ 2 ∣ C k ∣ ∣ D ∣ H(D)=-\sum_{i=1}^{n} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|} H(D)=−i=1∑n​∣D∣∣Ck​∣​log2​∣D∣∣Ck​∣​

3. 计算信息增益

   g ( D , A ) = H ( D ) − H ( D │ A ) g(D,A)=H(D)-H(D│A) g(D,A)=H(D)−H(D│A)

ID3算法

思想: 在决策树各个节点上应用信息增益准则选择特征, 递归地构建决策树.

方法:从根节点出发, 对结点计算所有可能的特征的信息增益, 选择信息增益最大的特征作为节点的特征, 并递归构建决策树.

(ID3相当于用极大似然法进行概率模型的选择)

输入: 训练数据集D, 特征集A, 阈值ε

输出: 决策树T

1. 若D中所有实例属于同一类 C k C_k Ck​, 则T为单节点数, 并将类 C k C_k Ck​作为该节点的类标记,返回T.
2. 若A=∅, 则T为单节点树, 并将D中实例数最大的类 C k C_k Ck​作为该节点的类标记, 返回T.
3. 否则,安装信息增益算法, 计算A中各特征对D的信息增益, 选择信息增益最大的特征 A g A_g Ag​.
4. 若A_g的信息增益小于阈值ε,则设置T为单节点树, 并将D 中实例数最大的类C_k作为该节点的类标记, 返回T.
5. 否则,对 A g A_g Ag​的每一可能值 a i a_i ai​, 依 A g = a i A_g=a_i Ag​=ai​将D分割为若干非空子集 D i D_i Di​, 将 D i D_i Di​中实例数最大的类作为标记,构建子节点, 由结点及其子结点构成树T, 返回T.
6. 对第i个子结点, 以 D i D_i Di​为训练集, 以A- A g {A_g} Ag​为特征集, 递归调用(1)~(5), 得到子树 T i T_i Ti​, 返回 T i T_i Ti​

Cart 树

Cart树是二叉树,每次分裂产生两个子节点.

Cart 分类树

采用Gini指数选择最优特征, Gini指数反应样本集合的不确定性

Gini ⁡ ( p ) = ∑ i = 1 n p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 \operatorname{Gini}(p)=\sum_{i=1}^{n} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2} Gini(p)=i=1∑n​pk​(1−pk​)=1−k=1∑K​pk2​

其中假设有k个类, p k p_k pk​表样本点属于第k个类的概率.

在特征A的条件下,集合D的基尼指数定义为:

Gini ⁡ ( D , A ) = ∣ D 1 ∣ ∣ D ∣ Gini ⁡ ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ Gini ⁡ ( D 2 ) \operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right) Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)

选取Gini指数最小的特征作为划分特征

CART回归树

思想: 将输入空间划分为M个单元(R1, R2, …, R M R_M RM​), 并且在每个单元 R m R_m Rm​上有一个固定的输出值 c m c_m cm​

回归模型:

f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right) f(x)=m=1∑M​cm​I(x∈Rm​)

训练误差:

∑ x i ∈ R m ( y i − f ( x i ) ) 2 \sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2} xi​∈Rm​∑​(yi​−f(xi​))2

单元 R m R_m Rm​上的最优输出值 c m ∗ c_m^* cm∗​

c m ∗ = ave ⁡ ( y i ∣ x i ∈ R m ) c_{m}^{*}=\operatorname{ave}\left(y_{i} \mid x_{i} \in R_{m}\right) cm∗​=ave(yi​∣xi​∈Rm​)

空间划分

采用启发式,选择第j个变量 x j x^{j} xj和它取值s, 作为切分变量和切分点,并定义两个区域

R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } , R 2 ( j , s ) = { x ∣ x ( j ) ≥ s } R_{1}(j, s)=\left\{x \mid x^{(j)} \leq s\right\}, \quad R_{2}(j, s)=\left\{x \mid x^{(j)} \geq s\right\} R1​(j,s)={x∣x(j)≤s},R2​(j,s)={x∣x(j)≥s}

最优化切分点

min ⁡ j , s [ min ⁡ c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right] j,smin​⎣⎡​c1​min​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​xi​∈R2​(j,s)∑​(yi​−c2​)2⎦⎤​

附录

• 实例: Decision Trees