决策树专题

决策树的构建过程

构建步骤如下：

1. 将所有的特征看成一个一个的节点
2. 遍历每个特征的每一种分割方式，找到最好的分割点；将数据划分为不同的子节点，eg:N1，N2…；计算划分之后所有子节点的“纯度”信息；
3. 对第二步产生的分割，选择出最优的特征以及最优的划分方式；得出最终的子节点：N1，N2…Nm；
4. 对子节点N1、N2…Nm分别继续执行2-3步，直到每个最终的子节点都足够‘纯’。

决策树的原理

决策树是一类常见的机器学习方法，它是基于树的结构进行决策的，决策过程通常会进行一系列的判断或者子决策。

每次做决策时根据哪一个属性呢，即如何选择最优划分属性，一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一个类别，即节点的“纯度（purity）”越来越高。

决策树学习算法包含特征选择、决策树的生成与剪枝过程。决策树的学习算法通常是递归地选择最优特征，并用最优特征对数据集进行分割。开始时，构建根节点，选择最优特征，该特征有几种值就分割为几个子集，每个子集分别调用此方法，返回结点，返回的结点就是上一层的子结点。直到所有特征都已经用完，或者数据集只有一维特征为止。

信息熵

假设当前样本集合D中有n类样本${x_1,x_2,……,x_n}$，第i类样本在样本集合D中所占的比例为$p(x_i)$，则熵定义为信息的期望值，$x_i$的信息定义为：

$$l(x_i)= -\log_2p(x_i)$$

而样本集合D的信息熵定义为：

$$Ent(D) = -\sum_{i=1}^np(x_i)\log_2p(x_i)$$

$Ent(D)$的值越小，则D的纯度越高。

信息增益

假定离散属性a有k个可能的取值{a1,a2,……,ak}，若使用a来对样本集D进行划分，则会产生k个分支节点，其中第i个分支节点包含了D中所有在属性a上取值ai的样本，记为$D_i$，我们可根据公式求得第i个分支节点的信息熵记为$Ent(D_i)$，第i个分支节点样本集$D_i$占样本集合D总的样本比例记为$p(D_i) = D_i/D$，父节点的信息熵记为$Ent(D)$，则用属性a对样本D进行划分所获得的“信息增益”为：

$$Gain(D,a)= Ent(D)-\sum_{i=1}^kp(D_i)Ent(D_i)$$

一般而言，信息增益越大，表现使用属性a来进行划分所获得的“纯度提升”越大。

信息增益率

如果使用信息增益去对决策树进行划分，可能出现每个分支节点只包含一个样本，这些分支节点的纯度已经达到最大，但是，这样的决策树显然不具备泛化能力，无法对新样本进行有效的预测。

实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，因此提出了信息增益率的概念：

$$Gain\_ration(D,a) = Gain(D,a)/IV(a)\\ IV(a) = -\sum_{i =1}^kp(D_i)\log_2(D_i)$$

属性$a$的可能取值数目越多，则IV(a)的值通常会越大。

基尼指数

基尼指数定义：

$$Gini(D) = \sum_{k=1}^Kp_k(1-p_k)$$

基尼指数反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高，属性a的基尼指数定义为：

$$Gini_index(D,a) = \sum_{i=1}^kp(D_i)Gini(D_i)$$

于是在候选集合中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

常用的决策树算法

常用的决策树算法有ID3，C4.5和CART。

ID3：以信息增益为准则来选择划分属性，多叉树。

C4.5：使用信息增益率来进行属性的选择，多叉树。

CART：使用基尼指数来选择划分属性，二叉树。

C4.5对ID3做了哪些改进

ID3算法是采用信息增益作为评价标准进行分支的决策树算法。

ID3的缺点：

1. 对于具有很多值的属性它是非常敏感的，例如，如果我们数据集中的某个属性值对不同的样本基本上是不相同的，甚至更极端点，对于每个样本都是唯一的，如果我们用这个属性来划分数据集，它会得到很大的信息增益，但是，这样的结果并不是我们想要的。
2. ID3算法不能处理具有连续值的属性。
3. ID3算法不能处理属性具有缺失值的样本。
4. 由于按照该算法会生成很深的树，所以容易产生过拟合现象。

C4.5算法主要对ID3做出了以下方面的改进。

1. 用信息增益率来选择属性，克服了用信息增益来选择属性时偏向选择值多的属性的不足。
2. 可以处理连续数值型属性。
3. 缺失值处理：对于某些采样数据，可能会缺少属性值。在这种情况下，处理缺少属性值的通常做法是赋予该属性的常见值，或者属性均值。另外一种比较好的方法是为该属性的每个可能值赋予一个概率，即将该属性以概率形式赋值。这样处理的目的是计算信息增益，使得这种属性值缺失的样本也能处理。

C4.5的缺点：

1. 算法低效，在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
2. 内存受限，适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

C4.5算法处理连续数值型属性

对于连续分布的特征，其处理方法是：

先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的，如果有N条样本，那么我们有N-1种离散化的方法：$<=v_j$的分到左子树，$>v_j$的分到右子树。计算这N-1种情况下最大的信息增益率。另外，对于连续属性先进行排序（升序），只有在决策属性发生改变的地方（即分类发生了变化）才需要切开，这可以显著减少运算量。经证明，在决定连续特征的分界点时采用增益这个指标，而选择属性的时候才使用增益率这个指标能选择出最佳分类特征。

对连续属性的处理如下：

1. 对特征的取值进行升序排序；
2. 两个特征取值之间的中点作为可能的分裂点，将数据集分为两部分，计算每个可能的分裂点的信息增益。优化算法就是只计算分类属性发生改变的那些特征取值；
3. 选择修正后信息增益最大的分裂点作为该特征的最佳分裂点；
4. 计算最佳分裂点的信息增益率作为特征的信息增益率。注意，此处需对最佳分裂点的信息增益进行修正：减去$\log_2(N-1)/|D|$（N是连续特征的取值个数，D是训练数据数目，此修正的原因在于：当离散属性和连续属性并存时，C4.5算法倾向于选择连续特征做最佳树分裂点）

C4.5与CART的区别

两者都是决策树，但CART既可以做分类，又可以做回归，而C4.5只能用于分类。

C4.5是构造决策树来发现数据中蕴涵的分类规则，是一种通过划分特征空间逼近离散函数值的方法。C4.5是基于ID3的改进算法，使用信息增益率作为划分依据。分类规则是互斥且完备的，所谓互斥即每一条样本记录不会同时匹配上两条分类规则，所谓完备即每条样本记录都在决策树中都能匹配上一条规则。

CART本质是对特征空间进行二元划分（即CART生成的决策树是一棵二叉树），并能够对标量属性与连续属性进行分裂。在对标量进行划分时，分为等于该属性和不等于该属性；对连续进行划分时，分为大于和小于。并且在分类的时候是采用GINI作为衡量标准，而不是信息增益了；而在回归时，是使用均方误差作为评价。

CART对于特征的利用是可以重复的，而作为分类的C4.5则是不能重复利用特征的。

CART树对离散特征取值数目>=3的特征如何处理

因为CART树是二叉树，所以对于样本的有N>=3个取值的离散特征的处理时也只能有两个分支，这就要通过组合人为的创建二取值序列并取GiniGain最小者作为树分叉决策点。

如某特征值具有[“young”,”middle”,”old”]三个取值，那么二分序列会有如下3种可能性（空集和满集在CART分类中没有意义）:

[((‘young’,),(‘middle’,’old’)),((‘middle’,),(‘young’,’old’)),((‘old’,),(‘young’,’middle’))]

采用CART算法，就需要分别计算按照上述List中的二分序列做分叉时的Gini指数，然后选取产生最小的GiniGain的二分序列做该特征的分叉二值序列参与树构建的递归。

因此CART不适用于离散特征有过多个取值可能的场景。此时，若定要使用CART，则最好预先人为的将离散特征的取值缩减。

那么对于二分后的左右分支，如果特征取值tuple中的元素多于2个，该特征还可以继续参与当前子数据集的二分。

决策树的剪枝

决策树剪枝方法

预剪枝

通过提前停止树的构建而对树剪枝，一旦停止，节点就是树叶，该树叶表示子集包含最频繁的类。

常用剪枝条件：

1. 定义一个高度，当决策树达到给高度时就停止决策树的生长；
2. 定义一个阈值，当达到某个节点的实例个数小于阈值时就可以停止决策树的生长；
3. 定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。

缺点：这样做决策树无法到最优，也无法得到比较好的效果。

后剪枝

它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。

1. 错误率降低剪枝
2. 悲观错误剪枝
3. 代价复杂度剪枝

缺点：这种方法比较浪费前面的建立过程（计算上）

决策树需要剪枝的原因

决策树是充分考虑了所有的数据点而生成的复杂树，有可能出现过拟合的情况，决策树越复杂，过拟合的程度会越来越高。

考虑极端的情况，如果我们令所有的叶子节点都只含有一个数据点，那么我们能够保证所有的训练数据都能准确分类，但是很有可能得到高的预测误差，原因是将训练数据中所有的噪声数据都“准确划分”了，强化了噪声数据的作用。（形成决策树的目的是作出合理的预测，尽可能有效的排除噪声数据干扰，影响正确预测的判断）

剪枝修剪分裂前后分类误差相差不大的子树，能够降低决策树的复杂度，降低过拟合出现的概率。

决策树特征

分类树和回归树

分类树

以C4.5分类树为例，C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的阈值，按照该标准分枝得到两个新节点，用同样方法继续分枝得到两个新节点，用同样方法继续分枝直到得到种类唯一的叶子节点，或达到预设的终止条件，若最终叶子节点的种类不唯一，则以占有最多数的种类作为该叶子节点的标识。

回归树

回归树总体流程也是类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差即（每个人的年龄-预测年龄）^ 2的总和/N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

决策树在选择特征进行分类时一个特征被选择过后，之后还会选择到这个特征吗？

决策树中一个特征被选择过后依然是有可能被选择为分裂特征的。

若特征为离散特征，如果决策树为二叉树，则可以在分类的子区间继续划分，如果决策树为多叉树，通常进行一次划分。

若特征为连续特征，则可能在决策树中多次被选择。

常用的决策树一定是二叉树？二叉决策树与多分支决策树相比有什么特点？

决策树并非均为二叉树，CART算法要求其所生成的决策树为二叉树，而ID3和C4.5则允许决策树为多分支的。

二叉决策树不像多叉树那样会形成过多的数据碎片，而二叉决策树可能会得到更深的最终决策树。

决策树需要进行归一化处理吗？

概率模型不需要归一化，因为它们不关心变量的值，而是关心变量的分布和变量之间的条件概率，决策树是一种概率模型，数值缩放，不影响分裂点位置。所以一般可以不对其进行归一化处理。

一棵决策树构建过程耗时的步骤是？

决策树的构建最耗时的步骤是确定最佳分割点，在该步骤中需要对特征的值进行排序，这个过程时间损耗较多。

如果决策树属性用完了仍未对决策树完成划分应该怎么办？

在决策树构造过程中可能会出现这种情况：所有属性都作为分裂属性用光了，但有的子集还不是纯净集，即集合内的元素不属于同一类别。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点。

存在时间序列回归模型效果比决策树模型有更高的精度的原因

时间序列数据有线性关系，而决策树算法是已知的检测非线性交互最好的算法。为什么决策树没能提供好的预测的原因是它不能像回归模型一样做到对线性关系那么好的映射。因此，我们知道了如果我们有一个满足线性回归模型能提供强大的预测。

决策树的优缺点

优点：

1. 易于理解，决策树易于理解和实现。人们在通过解释后都有能力去理解决策树所表达的意义。
2. 数据处理简单，对于决策树，数据的准备往往是简单或者是不必要的。其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。
3. 能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。
4. 是一个白盒模型如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
5. 易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
6. 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

缺点：

1. 很容易在训练数据中生成复杂的树结构，造成过拟合(overfitting)。剪枝可以缓解过拟合的负作用，常用方法是限制树的高度、叶子节点中的最少样本数量。
2. 不适合处理高维数据，当属性数量过大的时候，部分决策树就不太适用了。
3. 对异常值(Outlier)过于敏感，很容易导致树的结构的巨大的变换。
4. 泛化(Generalization)能力太差，对于没有出现过的值几乎没有办法。

决策树对缺失值的处理

决策树缺失值需要考虑3个问题：

1. 当开始决定选择哪个属性用来进行分支时，如果有些训练样本缺失了某些属性值时该怎么办？

• 忽略这些缺失属性a的样本。
• 填充缺失值，例如给缺失属性a的样本赋予属性a一个均值或者最常用的值或者根据其他未知的属性想办法把这些样本缺失的属性补全。
• 计算信息增益或者信息增益率时根据缺失属性样本个数所占的比率对增益/增益率进行相应的“打折”，例如我们对10个样本进行分类，一个样本数据在a属性具有缺失值，我们使用其中九个完全样本计算a属性的信息增益，并将其乘以0.9作为最终信息增益。

1. 一个属性已被选择，那么在决定分支的时候如果有些样本缺失了该属性如何处理？

• 忽略这些样本
• 填充缺失值再进行分类，例如给缺失属性a的样本赋予属性a一个均值或者最常用的值者根据其他未知的属性想办法把这些样本缺失的属性补全。
• 把这些属性缺失样本，按照具有属性a的样本被划分成的子集样本个数的相对比率，分配到各个子集中去。至于哪些缺失的样本被划分到子集1，哪些被划分到子集2，这个没有一定的准则，可以随机而动。
• 把属性缺失样本分配给所有的子集，也就是说每个子集都有这些属性缺失样本。
• 单独为属性缺失的样本划分一个分支子集。

1. 当决策树已经生成，但待分类的样本缺失了某些属性，这些属性该如何处理？

• 如果有单独的缺失值分支，依据此分支预测。
• 把待分类的样本的属性a值分配一个最常出现的a的属性值，然后进行分支预测。
• 根据其他属性为该待分类样本填充一个属性a值，然后进行分支处理。
• 待分类样本在到达属性a节点时就终止分类，然后根据此时a节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。