2021-09-23 88139e860b94cc8e241f92b9e138f7dd 99+ 11 m 1.7 k

决策树

1.概述

基本上决策树都是二叉树

两幅图意思一样

2.决策树 vs 逻辑回归

最大的差异上图就可以看出，左边为逻辑回归的决策面，右边为决策树的决策面

3.构建算法

常见方法的有ID3，C4.5，CART，总结如下

3.1 ID3

假设训练数据集为 $D$,∣$D∣$表示其大小。设有$K$个分类$ C_1,C_2,…,C_K$。设特征集为$\textbf{A}$,假设某个特征$ A$ 有$ n$ 个不同的取值 $\{a_1,a_2,…,a_n\}$,根据特征$A$的取值将 $D$ 划分成$n$个子集。记子集 $D_i$中属于类$ C_k$的样本集合为 $D_{ik}$。

数据集$D$的经验熵$H(D)$:

$H(D) = - \sum_{j=1}^K \frac {|C_j|}{|D|} \log \frac {|C_j|}{|D|}$

特征$A$对数据集$ D$的经验条件熵$H(D|A)$

$\begin{equation*} \begin{split} H(D|A) &= \sum_{i=1}^n \frac {|D_i|}{|D|} H(D_i) \\ & = - \sum_{i=1}^n \frac {|D_i|}{|D|}\sum_{j=1}^K \frac {|D_{ij}|}{|D_i|} \log \frac {|D_{ij}|}{|D_i|} \\ \end{split} \end{equation*}$

信息增益$g(D,A)$

$g(D,A)=H(D)-H(D|A)$

算法流程:

若$D$中所有实例都属于同一类 $C_k$,则 $T$ 为单节点树,并将类 $C_k$作为该节点的类标记,返回$T$.
若$\textbf{A}=\phi$,则$T$为单节点树,并将$D$中实例最大的类$C_k$作为该节点的类标记,返回$T$.
否则,按照信息增益的算法,计算每个特征对$D$的信息增益,取信息增益最大的特征 $A_g$.
如果$A_g< \varepsilon$,则置 $T$为单节点树,并将$D$中实例最大的类$C_k$作为该节点的类标记,返回$T$.
否则,对$A_g$的每一可能值 $a_i$,依$A_g=a_i$将$D$分成若干非空子集$D_i$
以$D_i$为训练集,以$\textbf{A}- A_g $为特征集,递归地调用步骤1到步骤5,得到子树 $T_i$,全部 $T_i$构成$T$,返回$T$.

3.2 C4.5

C4.5算法流程与ID3相类似，只不过将信息增益改为信息增益比，以解决偏向取值较多的属性的问题，另外它可以处理连续型属性。

分裂信息 $SplitInformation(D,A)$

$SplitInformation(D,A) = -\sum_{i=1}^n \frac {|D_i|}{|D|} \log \frac {|D_i|}{|D|}$

信息增益比 $GainRatio(D, A)$

$GainRatio(D, A) = \frac {g(D, A)} {SplitInformation(D, A)}$

3.3 CART

3.3.1 CART分类树

CART分类树算法使用基尼系数来代替信息增益（比），基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（比）相反。

对于样本$D$，个数为$|D|$，假设$K$个类别，第$k$个类别的数量为$|C_k|$，则样本$D$的基尼系数表达式：

$Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2$

对于样本$D$，个数为$|D|$，根据特征$A$的某个值$a$，把$D$分成$|D_1|$和$|D_2|$，则在特征$A=a$的条件下，样本$D$的基尼系数表达式为：

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

算法流程：算法输入训练集$D$，基尼系数的阈值，样本个数阈值。输出的是决策树$T$。

(1)、对于当前节点的数据集为$D$，如果样本个数小于阈值或没有特征，则当前节点停止递归，返回决策树。

(2)、计算样本集$D$的基尼系数，如果基尼系数小于阈值，则当前节点停止递归，返回决策树。

(3)、计算当前节点所有特征的各个特征值对数据集$D$的基尼系数

(4)、在计算出来的所有基尼系数中，选择基尼系数最小的特征$A$和对应的特征值$a$，并把数据集划分成两部分$D_1$和$D_2$，同时建立当前节点的左右节点，左节点的数据集$D$为$D_1$，右节点的数据集$D$为$D_2$。

(5)、对左右的子节点递归的调用1-4步，生成决策树。

3.3.2 CART回归树

对回归树用平方误差最小化准则

算法流程：输入为训练数据$D$，输出为回归树$f(x)$

(1) 选择最优的切分变量$j$和切分点$s$，遍历$j$，对固定的$j$遍历$s$，求解

$\min \limits_{j,s} \ [\min \limits_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min \limits_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$

(2) 用选定的$(j,s)$划分区域并决定输出值

$R_1(j,s)=\{x|x^{(j)}\le s\},R_2(j,s)=\{x|x^{(j)}> s\} \\\hat{c}_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i,m=1,2$

(3) 继续对两个子区域调用步骤（1）（2），直至满足停止条件

(4) 将输入空间划分成$M$个区域$R_1,R_2,…,R_M$，生成回归树

$f(x)=\sum_{m=1}^{M}\hat{c}_mI(x\in R_m)$

3.4 多变量决策树

无论ID3，C4.5，CART都是选择一个最优的特征做分类决策，但大多数，分类决策不是由某一个特征决定，而是一组特征。这样得到的决策树更加准确，这种决策树叫多变量决策树(multi-variate decision tree)。在选择最优特征的时，多变量决策树不是选择某一个最优特征，而是选择一个最优的特征线性组合做决策。

代表算法OC1。