决策树

数据挖掘 决策树

---

决策树是一种简单的机器学习方法。决策树经过训练之后，看起来像是以树状形式排列的一系列if-then语句。一旦我们有了决策树，只要沿着树的路径一直向下，正确回答每一个问题，最终就会得到答案。沿着最终的叶节点向上回溯，就会得到一个有关最终分类结果的推理过程。今天要总结的包括三种决策树算法：ID3，C45和CART，其中ID3和C45常用来解决分类问题，CART常用来解决回归问题。

---

ID3

ID3是最基础的一种决策树算法，其思想就是根据特征（feature）的值逐步把数据分类，直到所有的叶子节点属于同一个类型结束。那么这些特征及其值应该怎么来选呢，这里我们就要引入一个概念叫做熵，熵最早是由香农为了解决对系统信息量化度量的问题而提出的，它的计算公式如下：

$$Entropy(S) = -\sum_{i=1}^{k} p_ilog_{2}(p_i)$$
其中$k$表示类别的个数，$p_i$表示类别$i$的比例。数学上，熵反映了随机变量的随机程度，熵越大表示越随机也就是越无序，反之亦然。

在引入熵之后，接下来我们就可以解决上面的问题了。方法是根据某一个特征划分数据集，其划分前后信息熵会有变化，优先选择的特征是让给让信息熵变化最大或者信息熵增益比最大的特征。根据这样的准侧，我们就可以递归的生成决策树了。

---

C45

C45算法是在ID3算法上的改进，它与ID3算法最大区别在于其不是根据信息熵增益最大来选择特征，而是根据信息熵增益率来选择。这是因为信息增益存在的一个问题：假设某个属性存在大量的不同值，在划分时将每个值成为一个结点，这样决策树在选择属性时，将偏向于选择该属性，但这肯定是不正确（导致过拟合）的。因此有必要使用一种更好的方法，那就是C4.5中使用的信息增益率（Info Gain Ratio），其考虑了分支数量和尺寸的因素，使用称为内在信息（Intrinsic Information）的概念[1]。 信息熵增益率计算如下：
设样本集S按照离散属性$F$的$V$个不同取值划分为，$s_1,s_2...s_v$ $V$个不同的子集，定义$Split(S,F)$:

$$Split(S,F) = -\sum_{v \in V}\frac{|s_i|}{|S|}log_2(\frac{|s_i|}{|S|})$$
$$Gain(S,F) = -\sum_{i=1}^{k} p_{i}log_{2}(p_{i}) - \sum_{v \in V of F}p(v)Entropy(s_v)$$
信息增益率为：
$$GainRatio(S,F) = \frac{Gain(S,F)}{Split(S,F)}$$
除了选特征的策略不同，相比于ID3，C45还有一些其他的优点：

• 能够处理连续性属性。其方法是将连续型变量离散化：1) 找到特征的最大值(max)和最小值(min)； 2) 假设该属性有N个不同的取值，这样就将其分为N-1段，这样就有N-1个分割值，分割值的取值方法为排序后前后属性值两两前后连续元素的均值（另一种方法是进行等分）；3) 分别计算每一个分割点的划分，然后选取最大的信息熵增益率。
• 缺失值处理。常见的方法包括: 1) 替换为最常见的值； 2) 给每一个可能值赋予概率； 3) 丢弃样本

---

CART

CART（Classification and Regression Trees）分类回归树，它使用基尼不纯度（Gini Impurity）来决定划分，基尼不纯度的定义为：

$$Gini(S) = \sum_{i=1}^{k}p_{i}(1-p_{i}) = \sum_{i=1}^{k}p_{i} - \sum_{i=1}^{k} p_{i}^{2} = 1 - \sum_{i=1}^{k} p_{i}^{2}$$
基尼不纯度表达了一个事件变为其对立事件的概率，基尼不纯度越小表示越纯，所以CART选择特征的策略是选择划分后能使基尼不纯度最小的特征。
CART和C45基本上是类似的算法，主要区别：1）它的叶节点不是具体的分类，而是是一个函数f()，该函数定义了在该条件下的回归函数。2）CART是二叉树，而不是多叉树。
具体而言：
设t代表某个数的节点，t中的样本集合为：{(x1,y1),(x2,y2)...(xn,yn)}， N(t)表示节点t中样本的个数，节点t的应变量的均值为：
$$\overline{y} = \frac{1}{N(t)} \sum_{i=1,x_i \in t}^{N(t)} y_i$$

节点内的平方残差为：

$$SS(t) = \sum_{i=1,x_i \in t}^{N(t)}(y_i - \overline{y})^{2}$$
划分（属性）F将t划分为左右节点tL和tR，得到：
$$\Phi(S,F) = SS(t) - SS(tL) - SS(tR)$$
能最大化上式的就是最佳划分：
$$\Phi(S,F^*) = max(\Phi(S,F))$$

---

剪枝

这里只简单的介绍一下思想。之所以要剪枝，是因为当决策树分支太多或深度太深，就很有可能出现过拟合，因此需要剪枝。一种很naive的方法是预剪枝，就是当树的深度大于某个阈值时停止，但是我们很难去定义这个阈值；另外一种方法时当熵的增加小于某个阈值时停止，这种方法存在的问题是决策树的构建过程中，往往是在熵增加很小后然后熵才会较大的增加。因此，常用的剪枝方法是后剪枝。所谓后剪枝是指在树创建成功后再进行剪枝操作，其方法是，对具有相同节点的一组节点进行检查，判断如果将其合并，熵的增加小于某个阈值的话则进行合并（剪枝）。