1.决策树

1.1.原理

决策树很多任务是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则。
邮件分类系统的例子：

在构造决策树时，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。
如果某个分支下的数据属于同一类型，则当前无需阅读的垃圾邮件已经正确地划分数据分类，无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内。

创建分支的伪代码函数create Branch()如下所示：

1.2.ID3算法

每次划分数据集时我们只选取一个特征属性。

例子：特征-- 不浮出水面是否可以生存，以及是否有脚蹼，类别–鱼类和非鱼类

建立的决策树如下：

1.2.1.信息增益

分数据集的大原则：将无序的数据变得更加有序。组织杂乱无章的数据的一种方法就是使用信息论度量信息。熵越高，混合的数据也越多。

熵定义为信息的期望值，在明确这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号的信息定义为：
$l(x_i)=-log_2p(x_i)$l(xi​)=−log2​p(xi​)
其中$p(x_i)$p(xi​)是选择该分类的概率，$p(x_i)=len(x_i\_samples)/len(all\_samples)$p(xi​)=len(xi​_samples)/len(all_samples)。
$x_i\_samples$xi​_samples：类别为的样本个数。
$all\_samples$all_samples：所有样本数。
为了计算香农熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

其中n是分类的数目。

1.2.2.例子

1.2.2.1.ID3

信息熵是代表随机变量的复杂度（不确定度），条件熵代表在某一个条件下，随机变量的复杂度（不确定度）。而我们的信息增益恰好是：信息熵-条件熵。

（1）当前样本集合 D 中第 k 类样本所占的比例为$p_k$pk​ ，则 D 的信息熵定义为

（2）离散属性 a 有 V 个可能的取值 {a1,a2,…,aV}；样本集合中，属性 a 上取值为 av 的样本集合，记为 $D^v$Dv。

（3）用属性 a 对样本集 D 进行划分所获得的“信息增益”

$Gain(D,a)$Gain(D,a)：信息增益
$Ent(D)$Ent(D)：信息熵
条件熵
（4）信息增益表示得知属性 a 的信息而使得样本集合不确定度减少的程度
在决策树算法中，我们的关键就是每次选择一个特征，特征有多个，那么到底按照什么标准来选择哪一个特征。
这个问题就可以用信息增益来度量。如果选择一个特征后，信息增益最大（信息不确定性减少的程度最大），那么我们就选取这个特征。
选择指标就是在所有的特征中，选择信息增益最大的特征。那么如何计算呢？看下面例子：

正例(好瓜)占 8/17，反例占 9/17 ，根结点的信息熵为

计算当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益

色泽有3个可能的取值：{青绿，乌黑，浅白}
D1(色泽=青绿) = {1, 4, 6, 10, 13, 17}，正例 3/6，反例 3/6
D2(色泽=乌黑) = {2, 3, 7, 8, 9, 15}，正例 4/6，反例 2/6
D3(色泽=浅白) = {5, 11, 12, 14, 16}，正例 1/5，反例 4/5

3 个分支结点的信息熵

那么我们可以知道属性色泽的信息增益是：

同理，我们可以求出其它属性的信息增益，分别如下：

于是我们找到了信息增益最大的属性纹理，它的Gain(D，纹理) = 0.381最大。
于是我们选择的划分属性为“纹理”
如下：

于是，我们可以得到了三个子结点，对于这三个子节点，我们可以递归的使用刚刚找信息增益最大的方法进行选择特征属性，
比如：D1(纹理=清晰) = {1, 2, 3, 4, 5, 6, 8, 10, 15}，第一个分支结点可用属性集合{色泽、根蒂、敲声、脐部、触感}，基于 D1各属性的信息增益，分别求的如下：

于是我们可以选择特征属性为根蒂，脐部，触感三个特征属性中任选一个（因为他们三个相等并最大），其它俩个子结点同理，然后得到新一层的结点，再递归的由信息增益进行构建树即可
我们最终的决策树如下：

啊，那到这里为止，我们已经知道了构建树的算法，上面也说了有了树，我们直接遍历决策树就能得到我们预测样例的类别。那么是不是大功告成了呢？
结果是：不是的

我们从上面求解信息增益的公式中，其实可以看出，信息增益准则其实是对可取值数目较多的属性有所偏好！
现在假如我们把数据集中的“编号”也作为一个候选划分属性。我们可以算出“编号”的信息增益是0.998
因为每一个样本的编号都是不同的（由于编号独特唯一，条件熵为0了，每一个结点中只有一类，纯度非常高啊），也就是说，来了一个预测样本，你只要告诉我编号，其它特征就没有用了，这样生成的决策树显然不具有泛化能力。

于是我们就引入了信息增益率来选择最优划分属性！

1.2.2.2.C4.5算法

首先我们来看信息增益率的公式：

由上图我们可以看出，信息增益率=信息增益/IV(a),说明信息增益率是信息增益除了一个属性a的固有值得来的。
我们来看IV(a)的公式：
属性a的固有值：

IV(触感) = 0.874 ( V = 2 )
IV(色泽) = 1.580 ( V = 3 )
IV(编号) = 4.088 ( V = 17
由上面的计算例子，可以看出IV(a)其实能够反映出，当选取该属性，分成的V类别数越大，IV(a)就越大，如果仅仅只用信息增益来选择属性的话，那么我们偏向于选择分成子节点类别大的那个特征。
但是在前面分析了，并不是很好，所以我们需要除以一个属性的固定值，这个值要求随着分成的类别数越大而越小。于是让它做了分母。这样可以避免信息增益的缺点。
那么信息增益率就是完美无瑕的吗？
当然不是，有了这个分母之后，我们可以看到增益率准则其实对可取类别数目较少的特征有所偏好！毕竟分母越小，整体越大。
于是C4.5算法不直接选择增益率最大的候选划分属性，候选划分属性中找出信息增益高于平均水平的属性（这样保证了大部分好的的特征），再从中选择增益率最高的（又保证了不会出现编号特征这种极端的情况）

1.2.2.3.CART算法

CART是一课二叉树
当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据;

分类树？回归树？

• 分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，并以数值表示。
• CART既能是分类树，又能是决策树，如上表所示，如果我们想预测一个人是否已婚，那么构建的CART将是分类树；如果想预测一个人的年龄，那么构建的将是回归树。

假设我们构建了两棵决策树分别预测用户是否已婚和实际的年龄，如图1和图2所示：

图1 预测婚姻情况决策树
图2 预测年龄的决策树

• 图1表示一棵分类树，其叶子节点的输出结果为一个实际的类别，在这个例子里是婚姻的情况（已婚或者未婚），选择叶子节点中数量占比最大的类别作为输出的类别；
• 图2是一棵回归树，预测用户的实际年龄，是一个具体的输出值。怎样得到这个输出值？一般情况下选择使用中值、平均值或者众数进行表示，图2使用节点年龄数据的平均值作为输出值。
  CART如何选择分裂的属性？

如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。
GINI值的计算公式：
　　　　　　　　　　　　　　　　　　
节点越不纯，GINI值越大。以二分类为例，如果节点的所有数据只有一个类别，则$GINI=1-\sum_{i \in I}p_i^2=0$GINI=1−∑i∈I​pi2​=0 ，如果两类数量相同，则 $GINI=1-\sum_{i \in I}p_i^2=1/2$GINI=1−∑i∈I​pi2​=1/2。
回归方差计算公式：
　　　　　　　　　　　　　　　
方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。
因此，无论是分类树还是回归树，CART都要选择使子节点的GINI值或者回归方差最小的属性作为分裂的方案。即最小化（分类树）：

或者（回归树）：

CART如何分裂成一棵二叉树？
节点的分裂分为两种情况，连续型的数据和离散型的数据。
CART对连续型属性的处理与C4.5差不多，通过最小化分裂后的GINI值或者样本方差寻找最优分割点，将节点一分为二，在这里不再叙述，详细请看C4.5。
对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但CART是一棵二叉树，每一次分裂只会产生两个节点，怎么办呢？很简单，只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值X，Y，Z，则该属性的分裂方法有{X}、{Y，Z}，{Y}、{X，Z}，{Z}、{X，Y}，分别计算每种划分方法的基尼值或者样本方差确定最优的方法。
以属性“职业”为例，一共有三个离散值，“学生”、“老师”、“上班族”。该属性有三种划分的方案，分别为{“学生”}、{“老师”、“上班族”}，{“老师”}、{“学生”、“上班族”}，{“上班族”}、{“学生”、“老师”}，分别计算三种划分方案的子节点GINI值或者样本方差，选择最优的划分方法，如下图所示：
第一种划分方法：{“学生”}、{“老师”、“上班族”}

预测是否已婚（分类）：

预测年龄（回归）：

第二种划分方法：{“老师”}、{“学生”、“上班族”}

预测是否已婚（分类）：

预测年龄（回归）：
　　　　
第三种划分方法：{“上班族”}、{“学生”、“老师”}

预测是否已婚（分类）：

预测年龄（回归）：
　　　　
综上，如果想预测是否已婚，则选择{“上班族”}、{“学生”、“老师”}的划分方法，如果想预测年龄，则选择{“老师”}、{“学生”、“上班族”}的划分方法。

1.2.2.4.如何剪枝？

CART采用CCP（代价复杂度）剪枝方法。代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。
可描述如下：
令决策树的非叶子节点为$T_1,T_2,...,T_n$T1​,T2​,...,Tn​。
a）计算所有非叶子节点的表面误差率增益值KaTeX parse error: Undefined control sequence: \alpah at position 33: …1,\alpha_2,...,\̲a̲l̲p̲a̲h̲_n \}
b）选择表面误差率增益值$\alpha_i$αi​最小的非叶子节点$T_i$Ti​（若多个非叶子节点具有相同小的表面误差率增益值，选择节点数最多的非叶子节点）。
c）对$T_i$Ti​进行剪枝
表面误差率增益值的计算公式：
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
其中：
$R(t)$R(t)表示叶子节点的误差代价，$R(t)=r(t)*p(t)$R(t)=r(t)∗p(t) ，
$r(t)$r(t) 为节点的错误率，
$p(t)$p(t)为节点数据量的占比；
$R(T)$R(T)表示子树的误差代价，

$r_i(t)$ri​(t)为子节点i的错误率，
$p_i(t)$pi​(t) 表示节点i的数据节点占比；
$N(T)$N(T)表示子树节点个数。
算例：
下图是其中一颗子树，设决策树的总数据量为40。

该子树的表面误差率增益值可以计算如下：

求出该子树的表面错误覆盖率为 ，只要求出其他子树的表面误差率增益值就可以对决策树进行剪枝。
流程图：

总结：

• （1）CART是一棵二叉树，每一次分裂会产生两个子节点，对于连续性的数据，直接采用与C4.5相似的处理方法，对于离散型数据，选择最优的两种离散值组合方法。
• （2）CART既能是分类数，又能是二叉树。如果是分类树，将选择能够最小化分裂后节点GINI值的分裂属性；如果是回归树，选择能够最小化两个节点样本方差的分裂属性。
• （3）CART跟C4.5一样，需要进行剪枝，采用CCP（代价复杂度的剪枝方法）。

1.3.优缺点

1.3.1.ID3

• （1）ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途；

• （2）ID3采用信息增益大的特征优先建立决策树的节点。缺点是在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大；

• （3）ID3算法对于缺失值的情况没有做考虑；

• （4）没有考虑过拟合的问题。

1.3.2.C4.5

（1）C4.5引入了正则化系数进行初步的剪枝，但是剪枝的效果不够好；

（2）C4.5生成的是多叉树（ID3算法生成的也是多叉树），即一个父节点可以有多个子节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率；

（3）C4.5只能用于分类，不能应用于回归，这也大大的限制了它的用途；

（4）C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
1.3.3.CART
（1）决策树很容易理解和解释，而且决策树也容易可视化（在sklearn中可以使用export_graphviz包进行决策树可视化）；

（2）基本不需要预处理，不需要提前归一化，处理缺失值；

（3）决策树在预测时的时间代价是O(logN)，其中N是预测的样本集大小；

（4）能够处理数值型（连续型）和类别型（离散型）的数据。很多其他技术通常在分析数据集的时候只专注于其中一点，即要么是数值型，要么是类别型；

（5）能够处理多维度输出的分类问题，即我们的预测值有多个维度，且多维度是相关的；

（6）决策树使用是作为一个白盒，相较于黑盒的神经网络，决策树在逻辑上可以得到很好的解释；

（7）可以交叉验证的剪枝来选择模型，从而提高泛化能力；

（8）对异常点的容错能力好，健壮性强。

缺点：
（1）决策树容易过拟合，导致模型的泛化能力很差。可以通过剪枝（目前sklearn中的决策树不支持剪枝，所以需要我们自己设置，如叶节点最小值，树的最大深度等），设置每个叶子节点的最小样本数和树的最大深度来避免这个问题；

（2）决策树不稳定，一些很小的变化可能会导致完全不同的决策树生成。这个问题可以通过集成方法来缓解（如：随机森林）；

（3）学习一棵最优化的决策树是NPC问题，因此实际中的决策树学习算法是基于启发式的算法，例如贪心算法在局部做到最优化决策树的每个节点，这样的方法并不能保证能得到一个全局最优的决策树。这个问题可以通过集成的方法来得到改善；

（4）一些复杂的关系决策树很难去学，因为决策树并不能清楚的表达它们，比如，异或问题，多路复用问题等。一般这种关系可以换神经网络分类方法来解决；

（5）如果某些类别的样本比例过大，生成决策树容易偏向于这些类别。因此建议在创建决策树之前要平衡数据集。