LOFTER-网易轻博

决策树

决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy （熵）= 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

信息增益（ID3）

首先引入信息论中熵的概念，信息论中的熵主要用来表示信息量的大小。信息量越大（数据分类越不“纯净”），对应的熵值也就越大，反之亦然。有关信息熵的计算公式如下：

对于有K个可能取值的某个事件而言，pk表示第k个可能值的发生概率，因此信息熵反映的是某个事件所有可能值的熵和。在实际应用中，一般将概率值用经验概率替换，因此经验信息熵可以表示为：

其中，|D|表示事件中的所有样本点，|Ck|表示事件的第k个可能值出现的次数。以上计算的是单个事件在不同取值下的熵，如果需要基于其他事件计算某个事件的熵，就称为条件熵；其计算公式为：

其中，P(Ai)表示A事件的第i种值对应的概率；|Di|表示Ai的频数；|Dik|表示Ai下D事件为k值的频数。由决策树的概念得出，从决策树的根节点到最后的叶节点的生长过程中，信息熵是下降的过程，其每一步下降的量就称为信息增益，其计算公式为：

由如上公式可以得到，对于已知事件A来说，事件D的信息增益就是D的信息熵与A事件下D的条件熵之差，事件A对事件D的影响越大，条件熵H(D|A)就会越小，从而其信息增益越大，进而说明事件D的信息熵下降的越多。因此，在根节点或中间节点的变量选择中，选用使信息增益最大的自变量作为节点。

对于连续型的自变量来说，可进行如下操作确定分割点，并用其作为根节点或中间结点的判断条件。首先对连续型的自变量以升序或降序进行排序，然后计算相邻两个数值之间的均值；并依据均值将数据集拆分成两个部分，一个部分为大于等于此均值的部分，另一部分为小于此均值的部分；在各数据子集中，都存在着两个分类所对应的样本，进而计算出将此均值作为判断值下所对应的信息增益；以此类推，将所有的均值所对应的信息增益计算，从中选取最大的变量作为连续型变量的信息增益。

信息增益率（C4.5）

在ID3算法中，使用信息增益作为根节点或中间结点的选取指标存在着一个明显的缺点，即信息增益会偏向选取取值较多的变量。当变量的取值较多时，其加权条件熵会越小，因此所得到的信息增益会越大，但当变量不具普适性时，选用该变量作为根节点或中间节点并没有太大的意义。因此，为了克服这一缺点，可以引入信息增益率的概念，在i信息增益的基础上进行相应的惩罚，其计算公式为：

其中，HA为事件A的信息熵。事件A的取值越多，GainA(D)可能越大，但同时HA也会越大，从而实现的惩罚。

基尼指数（CART）

决策树中C4.5和ID3分别使用信息增益率和信息增益来实现决策树节点的选择，其实质都是针对离散型因变量进行分类。为了实现对连续型因变量的预测，Breiman等人提出了CART算法，即分类回归树，其选用基尼指数作为节点选择的指标，其计算公式为：

式中各表达式意义同信息增益相同，故不赘述。

类似地，在进行根节点或中间节点的选择时需要计算条件基尼指数，其计算公式为：

条件基尼系数采用的是二分法原理，在三个及以上不同取值的离散型变量中，需要分别对每个取值进行二元划分以进行计算，并从中选择最小二值作为该变量的二元划分。与信息增益类似地，还需考虑基尼指数下降速度的快慢程度，并选取基尼指数下降速度最大的变量作为节点，其公式如下：

Python实现

在Python中，sklearn模块中提供了CART算法，它既可以处理离散型分类问题（分类决策树），也可以处理连续型预测问题（回归决策树）。两种不同类型决策树分别对应DecisionTreeClassifier和DecisionTreeRegressor类，其语法参考sklearn提供的官方文档sklearn.tree.DecisionTreeClassifier和sklearn.tree.DecisionTreeRegressor。