决策树 Decision tree

决策树是一个类似于流程图的树结构：

• 每个内部结点表示在一个属性上的测试；
• 每个分支代表一个属性输出；
• 每个树叶结点代表类或类分布。

准备知识

熵

香农提出了信息熵（entropy）的概念，信息量的度量就等于不确定性的大小，不确定性越大，熵越大。

$$Ent(D)=-\sum_ip(x_i)\log_2{p(x_i)}$$

决策树算法

属性结点不同的顺序决定了算法不同的复杂度。因选定属性的度量方法不同，产生了不同的算法；

ID3

信息增益（Information Gain）最大的属性作为最先的结点，代表这个属性包含了最多的信息。每确定一个结点后，在这个结点各分类的数据中，重新计算下一个结点。

$$Gain(D,A) = Ent(D)-Ent_{A}(D) \\ =Ent(D)-\sum_{\nu=1}^V \frac{|D^\nu|}{|D|}Ent(D^\nu) \\ Ent(D)是不考虑任何属性，总数据标记的信息熵 \\ Ent_{A}(D)是以某一属性计算全概率的信息熵,A有V个可能的取值$$

C4.5

ID3算法存在一个问题，就是越细小的分割分类错误率越小，所以ID3会越分越细，形成过拟合。

$$即 \quad Ent(D^\nu) \to 1 , \quad 亦即\quad Ent_A(D) \to 1$$

C4.5对ID3进行了改进，优化项要除以分割太细的代价，这个比值叫做信息增益率，并以此作为选择属性结点顺序的标准。

$$Gain\_ratio(D,A)=\frac {Gain(D,A)}{IV(A)} \\ IV(A)=-\sum_{\nu=1}^V \frac{|D^\nu|}{|D|} \log_2 \frac{|D^\nu|}{|D|} \\ 属性A可能取值越多，IV(A)的值通常越大$$

CART（Classification and Regression Tree）

使用基尼指数来选择划分属性

$$Gini(D)=\sum_{k=1}^{|y|} \sum_{k' \neq k}p_{k'}p_k=1-\sum_{k=1}^{|y|}p_k^2$$

直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，其纯度越高。

属性A的基尼系数

$$Gini\_index(D,A) = \sum_{\nu=1}^V \frac{|D^\nu|}{|D|}Gini(D^\nu)$$

剪枝（pruning)

构建树可能需要剪枝，解决过拟合问题

• 预剪枝（prepruning）：在树生长过程中设定指标，达到指标就停止生长。容易产生”视界局限“，丢失有效信息。
• 后剪枝（post pruning）：树充分生长，再对相邻的叶结点进行合并。计算量代价大。

连续值处理

所有属性必须是离散值，如果是连续值通过设定阈值创建离散值。

决策树的优点

• 直观，便于理解；
• 小规模数据集有效。

决策树的缺点

• 处理连续变量不好设定阈值；
• 属性类别较多时，错误增加的比较快；
• 可规模性一般。