数据挖掘-决策树算法

2020-03-20 本文已影响0人花讽院_和狆

决策树算法是一种比较简易的监督学习分类算法，既然叫做决策树，那么首先他是一个树形结构，简单写一下树形结构（数据结构的时候学过不少了）。

树

树状结构是一个或多个节点的有限集合，在决策树里，构成比较简单，有如下几种元素：

根节点：没有入边（输入），但是有0或者多条出边（输出）。
非叶子节点：有一条入边，两条或者多条出边。
叶子节点：只有一条入边，没有出边。
分支：就是出边和入边，代表决策的结果。
以图为例：

决策树

在决策树中，每个叶子节点都有一个类标签，非叶子节点包含对属性的测试条件，用此进行分类。
所以个人理解，决策树就是对一些样本，用树形结构对样本的特征进行分支，分到叶子节点就能得到样本最终的分类，而其中的非叶子节点和分支就是分类的条件，测试和预测分类就可以照着这些条件来走相应的路径进行分类。

根据这个逻辑，很明显决策树的关键就是如何找出决策条件和什么时候算作叶子节点即决策树终止。

条件分类

决策树的核心是为不同类型的特征提供表示决策条件和对应输出的方法，特征类型和划分方法包括以下几个：

二元属性，产生两个可能的输出（是或不是）。
标称属性，具有多个属性值，有两种表示方式，一种是多路输出（有一个属性值输出一个分支），另外一种是只产生二元划分，这样的话就考虑创建 $k$ 个属性值的二元划分的所有 $2^{k-1}-1$ 中方法。
多路输出

二元划分输出

序数属性，是有序的一组属性值，不能违背序数属性的有序性，进行分组。

序数属性
连续属性：连续属性就是能取任何值的属性，可以通过一定的范围进行划分（离散化）。

连续属性

注意，这些图中的第二层都是分支，不是叶子节点。

最佳特征的划分

如何合理的对特征进行划分，从而找到最优的决策模型呢？在这里需要引入信息熵的概念。

信息熵

先来看熵的概念：

熵，热力学中表征物质状态的参量之一，用符号S表示，其物理意义是体系混乱程度的度量。

在数据集中，参考熵的定义，把信息熵描述为样本中的不纯度，熵越高，不纯度越高，数据越混乱（越难区分分类）。

例如：要给（0，1）分类，熵是0，因为能明显分类，而均衡分布的（0.5，0.5）熵比较高，因为难以划分。

信息熵的计算公式为： $Entropy(t) = -\sum_{i=0}^{c-1}p(i|t)log_2p(i|t)$
其中 $Entropy(t)$ 代表信息熵。 $c$ 是类的个数， $p(i|t)$ 代表在 $t$ 类时 $i$ 发生的概率。
另外有一种Gini系数，也可以用来衡量样本的不纯度： $Gini(t) = 1 - \sum_{i=0}^{c-1}[p(i|t)]^2$
其中 $Gini(t)$ 代表Gini系数，一般用于决策树的CART算法。

举个例子：

分类	计数
类=0	3
类=1	3

如果有上述样本，那么样本中可以知道，能被分为0类的有3个，分为1类的也有3个，那么信息熵为： $Entropy = -\frac{{3}}{{6}}log_2{\frac{3}{6}} - \frac{3}{6}log_2{\frac{3}{6}} = 1$
Gini系数为： $Gini = 1 - (\frac{3}{6})^2 - (\frac{3}{6})^2 = 0.5$
总共有6个数据，那么其中0类3个，占比就是3/6，同理1类。

我们再来计算一个分布比较一下：

分类	计数
类=0	1
类=1	5

信息熵为： $Entropy = -\frac{{1}}{{6}}log_2{\frac{1}{6}} - \frac{5}{6}log_2{\frac{5}{6}} = 0.65$
Gini系数为： $Gini = 1 - (\frac{1}{6})^2 - (\frac{5}{6})^2 = 0.278$

很明显，因为第二个分布中，很明显这些数偏向了其中一类，所以纯度更高，相对的信息熵和Gini系数较低。

有了上述的概念，很明显如果我们有一组数据要进行分类，最快的建立决策树的途径就是让其在每一层都让这个样本纯度最大化，那么就要引入信息增益的概念。

信息增益

所谓增益，就是做了一次决策之后，样本的纯度提升了多少（不纯度降低了多少），也就是比较决策之前的样本不纯度和决策之后的样本不纯度，差越大，效果越好。
让信息熵降低，每一层降低的越快越好。
度量这个信息熵差的方法如下： $Δ = I(parent) - \sum_{j=1}^{k}{\frac{N(v_j)}{N}}I(v_j)$
其中 $Δ$ 代表的就是信息熵（或者其他可以度量不纯度的系数）的差， $I(x)$ 是样本(parent是决策之前， $v_j$ 是决策之后)的信息熵（或者其他可以度量不纯度的系数）， $k$ 为特征值的个数， $N$ 是原样本的记录总数， $N(v_j)$ 是与决策后的样本相关联的记录个数。

当选择信息熵作为样本的不纯度度量时，Δ就叫做信息增益。

我们可以遍历每一个特征，看就哪个特征决策时，产生的信息增益最大，就把他作为当前决策节点，之后在下一层继续这个过程。

举个例子：

判断销量好坏

如果我们的目标是判断什么情况下，销量会比较高（受天气，周末，促销三个因素影响），根据上述的信息增益求法，我们首先应该找到根据哪个特征来决策，以信息熵为例：

首先肯定是要求 $I(parent)$ ，也就是销量这个特征的信息熵：
$I(销量) = -\frac{16}{34}{log_2\frac{16}{34}} - -\frac{18}{34}{log_2\frac{18}{34}} = 0.997503$

接下来，就分别看三个特征关于销量的信息熵，先看天气，天气分为好和坏两种，其中天气为好的条件下，销量为高的有11条，低的有6条；天气坏时，销量为高的有7条，销量为低的有10条，并且天气好的总共17条，天气坏的总共17条。

分别计算天气好和天气坏时的信息熵，天气好时：
$I(天气=好) = -\frac{11}{17}{log_2\frac{11}{17}} - -\frac{6}{17}{log_2\frac{6}{17}} = 0.936667$
$I(天气=坏) = -\frac{7}{17}{log_2\frac{7}{17}} - -\frac{10}{17}{log_2\frac{10}{17}} = 0.977418$

根据公式 $Δ = I(parent) - \sum_{j=1}^{k}{\frac{N(v_j)}{N}}I(v_j)$ ，可以知道，N是34，而天气特征有2个值，则k=2，第一个值有17条可以关联到决策后的节点，第二个值也是17条，则能得出计算： $Δ = 0.997503 - \frac{{17}}{34}*0.936667 - \frac{17}{34}*0.977418 = 0.4046$

再计算周末这个特征，也只有两个特征值，一个是，一个否，其中是有14条，否有20条；周末为是的中有11条销量是高，3条销量低，以此类推有：
$I(周末=是) = -\frac{11}{14}{log_2\frac{11}{14}} - -\frac{3}{14}log_2\frac{3}{14} = 0.749595$
$I(周末=否) = -\frac{7}{20}{log_2\frac{7}{20}} - -\frac{13}{20}{log_2\frac{13}{20}} = 0.934068$
信息增益为：

$Δ = 0.997503 - \frac{{14}}{34}*0.749595 - \frac{20}{34}*0.934068 = 0.139394$

另外可以得到是否有促销的信息增益为0.127268。

可以看出，以周末为决策，可以得到最大的信息增益，因此根节点就可以用周末这个特征进行分支：

根节点和分支

注意再接下来一层的原样本集，不是34个而是周末为“是”和“否”分别计算，为是的是14个，否的是20个。
这样一层一层往下递归，直到判断节点中的样本是否都属于一类，或者都有同一个特征值，此时就不继续往下分了，也就生成了叶子节点。

上述模型的决策树分配如下：

决策树模型

需要注意的是，特征是否出现需要在分支当中看，并不是整体互斥的，周末生成的两个分支，一个需要用促销来决策，一个需要用天气，并不代表再接下来就没有特征可以分了，而是在促销决策层下面可以再分天气，另外一遍天气决策下面可以再分促销。

决策树的模型比较容易解释，看这个树形图就能很容易的说出分类的条件。

计算过程中提到的信息熵，换成Gini系数计算也是一样的。

不同类型属性的划分

我们知道属性有二元属性、标称属性、序数属性和连续属性，其中二元、标称和序数都是类似的，因为是离散的属性，按照上述方式进行信息增益计算即可，而连续属性与这三个不同。

连续属性的决策划分

对于连续的属性，为了降低其时间复杂度，我们可以先将属性内部排序，之后取相邻节点的均值作为决策值，依次取每两个相邻的属性值的均值，之后比较他们的不纯度度量。

连续属性划分处理
这样的话，得到的决策分支就会是这种类型的，指定一个范围而不是一个固定的值。

需要注意的是，连续属性可能在决策树中出现多次，而不是像离散的属性一样在一个分支中出现一次就不会再出现了。

信息增益率

用信息熵或者Gini系数等不纯度度量有一个缺点，就是会倾向于将多分支的属性优先分类——而往往这种属性并不是特征。

例如上面例子中的第一行序号，有34个不同的值，那么信息熵一定很高，但是实际上它并没有任何意义，因此我们需要规避这种情况，如何规避呢，有两种方式：

限制条件只能是二元划分，这样就不会出现多分支的倾斜了，CART算法就是这种算法，采用Gini系数作为度量。
修改决策划分的标准，把决策条件产生的输出数也算进去，C4.5算法就是用这种模式，引入了信息增益率的概念。

公式如下：
$Gain ratio = \frac{Δ_{info}}{-\sum_{i=1}^k{P(v_i)log_2P(v_i)}}$
其中k为划分的总数，如果每个属性值具有相同的记录数，则 $P(v_i)=1/k$ ，划分信息等于 $log_2k$ ，那么如果某个属性产生了大量划分，则划分信息很大，信息增益率低，就能规避这种情况了。

决策树的优化

为了防止过拟合现象，往往会对决策树做优化，一般是通过剪枝的方式，剪枝又分为预剪枝和后剪枝。

预剪枝

在构建决策树时，设定各种各样的条件如叶子节点的样本数不大于多少就停止分支，树的最大深度等，让决策树的层级变少以防止过拟合。
也就是在生成决策树之前，设定了决策树的条件。

后剪枝

后剪枝就是在最大决策树生成之后，进行剪枝，按照自底向上的方式进行修剪，修剪的规则是，评估叶子节点和其父节点的代价函数，如果父节点的代价函数比较小，则去掉这个叶子节点。
这里引入的代价函数公式是： $C(T) = \sum_{t}{N_t·H(t)}$
其中 $N_t$ 代表的是叶子节点中样本个数， $H(t)$ 代表的是该叶子节点上的不纯度度量，把每个叶子节点的 $C(T)$ 加起来，和父节点的 $C(T)$ 比较，之后进行剪枝即可。