决策树

决策树

参考1

参考2

参考3

​ 决策树算法：利用自变量构造一颗二叉树，以区分出目标变量。决策树算法的要点如下：

• 选择分裂属性：选择分叉的方式决定了决策树的算法类型，分为：

  • ID3：采用信息增益来选择树叉
  • C4.5：采用增益率来选择树叉
  • CART：采用Gini系数来选择树叉

• 剪枝：数据中的噪声和离群点会造成一些分枝反映的是训练数据中的异常。剪枝就是处理这种过拟合问题，有先剪枝和后剪枝两种方法。

  以以下数据为例，介绍三种决策树：

  | 客户ID | 故障原因 | 故障类型 | 修障时长 | 满意度 |
  | —— | ——– | ——– | ——– | —— |
  | 001 | 1 | 5 | 10 | 1 |
  | 002 | 1 | 5 | 12 | 0 |
  | 003 | 1 | 5 | 14 | 1 |
  | 004 | 2 | 5 | 16 | 0 |
  | 005 | 2 | 5 | 18 | 1 |
  | 006 | 2 | 6 | 20 | 0 |
  | 007 | 3 | 6 | 22 | 1 |
  | 008 | 3 | 6 | 24 | 0 |
  | 009 | 3 | 6 | 26 | 1 |
  | 010 | 3 | 6 | 28 | 0 |

​ 目标变量满意度是二分类变量：满意（记为0）和不满意（记为1）；自变量是：故障原因（离散型），故障类型（离散型），修障时长（连续型）。

ID3决策树

原理

​ ID3算法选择具有最高信息增益的自变量作为当前的树叉，信息增益=原信息熵-按某自变量划分后信息熵。选取最大的信息增益率作为分裂属性。

​ D为目标变量，m为目标变量的种类；p_i为每种目标变量对应的概率。原信息熵的计算公式如下：

$$ Entropy(D) = -\sum_{i=1}^m p_i*\log_2p_i ​$$

​ A表示按自变量A对目标变量D进行划分；V表示按自变量A划分后的子集数；|D_j|/|D|表示子集j中样本所占总体的比例；Entropy(D_j)表示子集j的信息熵。按某自变量A划分后信息熵计算公式如下：

$$ EntropyA(D) = \sum{j=1}^V \frac{|Dj|}{|D|} Entropy(Dj) = - \sum{j=1}^v\frac{|Dj|}{|D|} \sum{i=1}^m p{ji}*\log2p{ji} ​$$

$$ Gain_A = Entropy(D) - Entropy_A(D) ​$$

示例

以上述满意度数据为例，分别计算三个字变量的信息增益，选取其中最大的信息增益作为树叉。第一个树叉选择的计算过程如下：

• 原信息熵：

$$ Entropy(满意度) = - \frac{5}{10} \log_2\frac{5}{10} - \frac{5}{10} \log_2\frac{5}{10} =1 $$

• 按故障原因划分：

$$ Entropy_{故障原因}(满意度) = - \frac{3}{10} (\frac{2}{3}\log_2\frac{2}{3}+\frac{1}{3}\log_2\frac{1}{3}) - \frac{3}{10} (\frac{1}{3}\log_2\frac{1}{3}+\frac{2}{3}\log_2\frac{2}{3}) - \frac{4}{10} (\frac{2}{4}\log_2\frac{2}{4}+\frac{2}{4}*\log_2\frac{2}{4}) = 0.95098 $$

信息增益为：1-0.95098=0.04902

• 按故障类型划分：

$$ Entropy_{故障类型}(满意度) = - \frac{5}{10} (\frac{2}{5}\log_2\frac{2}{5}+\frac{3}{5}\log_2\frac{3}{5}) - \frac{5}{10} (\frac{2}{5}\log_2\frac{2}{5}+\frac{3}{5}\log_2\frac{3}{5}) = 0.97095 $$

信息增益为：1-0.97095=0.02905

​ 对于连续型变量，将其排序后，依次取相邻两值的中间值作为划分点后同离散型的方式进行计算。分别算得按各重点划分的信息增益，取信息增益最大的作为此连续变量的分叉。

• 按修障时间划分：

$$ Entropy_{11}(满意度) = - \frac{1}{10} (\frac{1}{1}\log_2\frac{1}{1}) - \frac{9}{10} (\frac{4}{9}\log_2\frac{4}{9}+\frac{5}{9}*\log_2\frac{5}{9}) = 0.89197 $$

$$Entropy_{13}(满意度) = - \frac{2}{10} (\frac{1}{2}\log_2\frac{1}{2}+\frac{1}{2}\log_2\frac{1}{2}) - \frac{8}{10} (\frac{4}{8}\log_2\frac{4}{8}+\frac{4}{8}\log_2\frac{4}{8}) = 1 $$

$$ Entropy_{15}(满意度) = - \frac{3}{10} (\frac{2}{3}\log_2\frac{2}{3}+\frac{1}{3}\log_2\frac{1}{3}) - \frac{7}{10} (\frac{4}{7}\log_2\frac{4}{7}+\frac{3}{7}\log_2\frac{3}{7}) =0.85262 $$

$$ Entropy_{17}(满意度) = - \frac{4}{10} (\frac{2}{4}\log_2\frac{2}{4}+\frac{2}{4}\log_2\frac{2}{4}) - \frac{6}{10} (\frac{3}{6}\log_2\frac{3}{6}+\frac{3}{6}\log_2\frac{3}{6}) =1 ​$$

$$ Entropy_{19}(满意度) = - \frac{5}{10} (\frac{2}{5}\log_2\frac{2}{5}+\frac{3}{5}\log_2\frac{3}{5}) - \frac{5}{10} (\frac{2}{5}\log_2\frac{2}{5}+\frac{3}{5}\log_2\frac{3}{5}) =0.97095 $$

选取最大的信息增益后，信息增益为：1-0.85262=0.14738

综上，第一层分叉选择修障时间（15为分界点）。

缺点

​ 倾向于选择具有大量值的属性。极端情况以客户ID为例，以此变量划分会得到每个划分中只有一个样本，即每个划分都是纯的，信息增益值为1。但是这种划分毫无意义。

C4.5决策树

原理

​ C4.5算法选择具有最高信息增益率的自变量作为当前的树叉。信息增益率 = 信息增益/划分的信息熵

​ 划分的信息熵计算公式如下：

$$ SplitEntropyA(D) = - \sum{j=1}^V(\frac{|D_j|}{|D|}*\log_2\frac{|D_j|}{|D|}) $$

$$ GainRate_A(D) = \frac{Gain(A)}{SplitEntropy_A} $$

示例

​ 以上述满意度数据为例，分别计算三个字变量的信息增益率，选取其中最大的信息增益率作为树叉。第一个树叉选择的计算过程如下：

• 按故障原因划分：

$$ SplitEntropy_{故障原因}(满意度) = - \frac{3}{10}\log_2\frac{3}{10} - \frac{3}{10}\log_2\frac{3}{10} - \frac{4}{10}*\log_2\frac{4}{10} = 1.57095 $$

$$ GainRate_{故障原因} = \frac{0.04902}{1.57095} = 0.03120 $$

• 按故障类型划分：

$$ SplitEntropy_{故障原因}(满意度) = - \frac{5}{10}\log_2\frac{5}{10} - \frac{5}{10}\log_2\frac{5}{10} = 1 $$

$$ GainRate_{故障类型} = \frac{0.02905}{1} = 0.02905 $$

• 按修障时间分类：

$$ SplitEntropy_{11}(满意度) = - \frac{1}{10}\log_2\frac{1}{10} - \frac{9}{10}\log_2\frac{9}{10} = 0.46900 $$

$$ GainRate_{修障时间11} = \frac{1-0.89197}{0.46900} = 0.23034 $$

$$ SplitEntropy_{13}(满意度) = - \frac{2}{10}\log_2\frac{2}{10} - \frac{8}{10}\log_2\frac{8}{10} = 0.72193 ​$$

$$ GainRate_{修障时间13} = \frac{1-1}{0.72893} = 0 $$

$$ SplitEntropy_{15}(满意度) = - \frac{3}{10}\log_2\frac{3}{10} - \frac{7}{10}\log_2\frac{7}{10} = 0.88129 $$

$$ GainRate_{修障时间15} = \frac{1-0.85262}{0..88129} = 0.16723 $$

$$ SplitEntropy_{17}(满意度) = - \frac{4}{10}\log_2\frac{4}{10} - \frac{6}{10}\log_2\frac{6}{10} = 0.97095 $$

$$ GainRate_{修障时间17} = \frac{1-1}{0.97095} = 0 $$

$$ SplitEntropy_{19}(满意度) = - \frac{5}{10}\log_2\frac{5}{10} - \frac{5}{10}\log_2\frac{5}{10} = 1 $$

$$ GainRate_{修障时间19} = \frac{1-0.97095}{1} = 0.97095 $$

选取最大的信息增益率后，信息增益率为：0.23034

综上，第一层分叉选择修障时间（11为分界点）。

CART决策树

原理

​ CART决策树选择基尼系数最小的属性作为树的分叉。CART决策树是一颗二叉树，因此每一个变量划分为两类。当此变量有多种方式划分两类时，计算所有划分的基尼系数，选取值最小的划分方式。为先计算不纯度，再计算基尼系数，公式如下：

$$ Gini(D) = 1- \sum_{i=1}^mp_i^2 $$

$$ GiniIndexA(D) = \sum{j=1}^V\frac{|D_j|}{|D|}*Gini(D_j) $$

示例

• 按故障类型划分，划分的方式有：{1, 2}与{3}，{1, 3}与{2}，{2, 3}与{1}

  • {1,2}与{3}

  $$ GiniIndex = \frac{6}{10}(1-(\frac{3}{6})^2 - (\frac{3}{6})^2) + \frac{4}{10}(1-(\frac{3}{6})^2-(\frac{3}{6})^2) = 0.5 $$

  • {1,3与}{2}

  $$ GiniIndex = \frac{7}{10}(1-(\frac{4}{7})^2 - (\frac{3}{7})^2) + \frac{3}{10}(1-(\frac{1}{3})^2-(\frac{2}{3})^2) = 0.47619 $$

  • {2,3}与{1}

  $$ GiniIndex = \frac{7}{10}(1-(\frac{3}{7})^2 - (\frac{4}{7})^2) + \frac{3}{10}(1-(\frac{2}{3})^2-(\frac{1}{3})^2) = 0.47619 $$

• 按故障原因划分

  $$ GiniIndex = \frac{5}{10} (1-(\frac{3}{5})^2-(\frac{2}{5})^2) + \frac{5}{10} (1-(\frac{2}{5})^2-(\frac{3}{5})^2) = 0.48 ​$$

• G按修障时间划分

$$ GiniIndex_{11} = \frac{1}{10}(1-(\frac{1}{1})^2-(\frac{0}{1})^2) + \frac{9}{10}(1-(\frac{5}{9})^2-(\frac{4}{9})^2) = 0.44444 $$

$$ GiniIndex_{13} = \frac{2}{10}(1-(\frac{1}{2})^2-(\frac{1}{2})^2) + \frac{8}{10}(1-(\frac{4}{8})^2-(\frac{4}{8})^2) = 0.5 $$

$$ GiniIndex_{15} = \frac{3}{10}(1-(\frac{1}{3})^2-(\frac{2}{3})^2) + \frac{7}{10}(1-(\frac{4}{7})^2-(\frac{3}{7})^2) = 0.47619 ​$$

$$ GiniIndex_{17} = \frac{4}{10}(1-(\frac{2}{4})^2-(\frac{2}{4})^2) + \frac{6}{10}(1-(\frac{3}{6})^2-(\frac{3}{6})^2) = 0.5 ​$$

$$ GiniIndex_{19} = \frac{5}{10}(1-(\frac{3}{5})^2-(\frac{2}{5})^2) + \frac{5}{10}(1-(\frac{2}{5})^2-(\frac{3}{5})^2) = 0.48 ​$$

综上，第一层分叉选择修障时间（11为分界点）。

剪枝

• 前剪枝：通过提前停止树的构造，如通过在给定的节点不再分裂或划分训练元组的子集，而对树剪枝，一旦停止，则该节点成为叶子结点。在构造树是，可以使用统计显著性、信息增益等度量来评估分裂的优劣，如果划分一个节点的元组低于预定义阈值的分裂，则给定子集的进一步划分将停止。较高的阈值可能导致过分简化的树，较低的阈值可能导致过分复杂的树。
• 后剪枝：由完全生长的树剪去子树，通过删除节点的分支，并用叶子结点替换它而剪掉给定节点的子树，叶子结点用被替换的子树中最频繁的类标记。

代价复杂性剪枝

计算表面误差率增益值α

$$ \alpha = \frac{R{(t)} - R(T{t})}{|N_{T_t}| - 1}​$$

|N _Tt| 是子树中包含的叶子节点个数

R(t)是如果被剪枝节点t的误差代价，R(t) = r(t)*p(t)

r(t)是节点t的误差率

p(t)是节点t上数据占所有数据的比例

R(Tt)是子树Tt的误差代价，如果该节点不被剪枝，它等于子树Tt上所有叶子节点的误差代价之和