决策树¶
决策树算法属于监督学习的范畴。它们可以用来解决回归和分类问题。 决策树使用树表示法来解决每个叶节点对应一个类标号，属性在树的内部节点上表示的问题。 我们可以用决策树表示离散属性上的任何布尔函数。
下面是我们在使用决策树时做的一些处理:
- 我们将整个训练集作为根。
- 特征值最好是分类的。如果这些值是连续的，则在建立模型之前对它们进行离散化。
- 在属性值的基础上，记录递归分布。
- 我们使用统计方法将属性排序为根或内部节点。
在上图中，我们使用预测计算机在人们日常生活中的使用。在决策树中，主要的挑战是识别每一层的根节点的属性。这个过程称为属性选择。有两个流行的属性选择方法:
- 信息增益(Information Gain)
- 基尼指数(Gini Index)
信息增益¶
当我们使用决策树中的一个节点将训练实例划分为更小的子集时，信息混乱程度——熵(entropy)会发生变化。信息增益是衡量这种熵变化的一个指标。
定义:设S是一组实例，a是一个属性，$S_v$是a = v时S的子集，Values (a)是a的所有可能值的集合，则 $$ \operatorname{Gain}(S, A)=\operatorname{Entropy}(S) - \sum_{v \in \operatorname{Values}(A)}\frac{\left|S_{v}\right|}{|S|} \cdot \operatorname{Entropy}\left(S_{v}\right) $$
熵(Entropy)¶
熵是一个随机变量不确定性的度量，它表征了一个任意样本集合的不纯性。熵越大，信息量越大。
定义:设S是一组实例，a是一个属性，Sv是a = v时S的子集，Values (a)是a的所有可能值的集合，则 $$ \operatorname{Gain}(S, A)=\operatorname{Entropy}(S) - \sum_{v \in \operatorname{Values}(A)}\frac{\left|S_{v}\right|}{|S|} \cdot \operatorname{Entropy}\left(S_{v}\right) $$
例如对集合A={a,a,a,b,b,b,b,b}而言，元素总个数为8，b有5个，a有3个，则
$$ \begin{aligned} \text { EntropyH } &(X)=-\left[\left(\frac{3}{8}\right) \log _{2} \frac{3}{8}+\left(\frac{5}{8}\right) \log _{2} \frac{5}{8}\right] \\ &=-[0.375 *(-1.415)+0.625 *(-0.678)] \\ &=-(-0.53-0.424) \\ &=0.954 \end{aligned} $$利用信息增益构建决策树¶
从与根节点关联的所有培训实例开始，使用info gain选择用哪个属性来标记每个节点(注意:根到叶路径不应该两次包含相同的离散属性),然后递归地在训练实例的子集上构造每个子树，这些子树将沿着树中的路径分类。
现在，让我们使用信息增益为以下数据画一个决策树。 训练集:3个特征，2个类
| X | Y | Z | C | |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | I |
| 1 | 1 | 1 | 0 | I |
| 2 | 0 | 0 | 1 | II |
| 3 | 1 | 0 | 0 | II |
利用信息增益建立决策树。我们将获取每个特征并计算每个特征的信息。
从上面的图片我们可以看到,信息增益最大Y,所以将Y作为第一个划分的指标.
上面数据集的最后一棵树看起来像这样:
基尼指数¶
基尼指数是衡量随机选择的元素被错误识别的频率的指标。这意味着应该首选基尼系数较低的属性。
基尼指数的计算公式如下: $$基尼指数= 1 - \sum_{j}^{}p_{j}^{2}$$
我们考虑下图中的数据集，并使用基尼指数绘制一个决策树:
| Index | A | B | C | D | E | |
|---|---|---|---|---|---|---|
| 0 | 1 | 4.8 | 3.4 | 1.9 | 0.2 | positive |
| 1 | 2 | 5 | 3 | 1.6 | 1.2 | positive |
| 2 | 3 | 5 | 3.4 | 1.6 | 0.2 | positive |
| 3 | 4 | 5.2 | 3.5 | 1.5 | 0.2 | positive |
| 4 | 5 | 5.2 | 3.4 | 1.4 | 0.2 | positive |
| 5 | 6 | 4.7 | 3.2 | 1.6 | 0.2 | positive |
| 6 | 7 | 4.8 | 3.1 | 1.6 | 0.2 | positive |
| 7 | 8 | 5.4 | 3.4 | 1.5 | 0.4 | positive |
| 8 | 9 | 7 | 3.2 | 4.7 | 1.4 | negative |
| 9 | 10 | 6.4 | 3.2 | 4.7 | 1.5 | negative |
| 10 | 11 | 6.9 | 3.1 | 4.9 | 1.5 | negative |
| 11 | 12 | 5.5 | 2.3 | 4 | 1.3 | negative |
| 12 | 13 | 6.5 | 2.8 | 4.6 | 1.5 | negative |
| 13 | 14 | 5.7 | 2.8 | 4.5 | 1.3 | negative |
| 14 | 15 | 6.3 | 3.3 | 4.7 | 1.6 | negative |
| 15 | 16 | 4.9 | 2.4 | 3.3 | 1 | negative |
在上面的数据集中，有5个属性，属性E是预测特征，包含2类(正类和负类)。这两类比例相等。 在基尼指数中，我们必须选择一些临界值来对每个属性进行分类。然后采用类似于信息增益的方法，选择基尼指数小的指标优先进行划分。
决策树算法¶
著名的决策树算法有：
迭代二分类器3 (ID3):该算法使用信息增益来决定使用哪个属性来对数据的当前子集进行分类。对于树的每一层，递归地计算剩余数据的信息增益。
C4.5:该算法是ID3算法的继承者。该算法使用信息增益或增益比来确定分类属性。它是对ID3算法的直接改进，因为它可以处理连续的和缺失的属性值。
CART (Classification and Regression Tree):它是一种动态学习算法，可以根据因变量生成回归树和分类树。
参考资料