机器学习-决策树（Decision Tree）简介

• 2019 年 10 月 7 日
• 笔记

背景介绍

• 决策树算法属于监督学习的范畴。它们可用于解决回归和分类问题。
• 决策树使用树表示来解决每个叶节点对应于类标签的问题，并且属性在树的内部节点上表示。
• 我们可以使用决策树表示离散属性上的任何布尔函数。

以下是我们在使用决策树时所做的一些假设：

• 一开始，我们将整个训练集视为根。
• 特征值优选是分类的。如果值是连续的，则在构建模型之前将它们离散化。
• 在属性值的基础上，记录以递归方式分布。
• 我们使用统计方法以root或内部节点对属性进行排序。

从上图中可以看出，决策树在产品总和表上工作，也称为析取范式。在上图中，我们预测计算机在人们日常生活中的使用。

在决策树中，主要挑战是识别每个级别中根节点的属性。 此过程称为属性选择。 我们有两种流行的属性选择措施：

1、信息增益

2、基尼指数

1、信息增益

当我们使用决策树中的节点将训练实例划分为更小的子集时，熵会发生变化。信息增益衡量熵的这种变化。

定义：假设S是一组实例，A是属性，Sv是S的子集，A = v，而值（A）是A的所有可能值的集合，那么

熵

熵是随机变量不确定性的度量，它表征任意一组例子的杂质。熵越高，信息内容越多。

定义：假设S是一组实例，A是属性，Sv是S的子集，A = v，而值（A）是A的所有可能值的集合，那么

例如：

对于集合X = {a，a，a，b，b，b，b，b}

总计：8

b的实例：5

实例：3

= -[0.375 * (-1.415) + 0.625 * (-0.678)]  =-(-0.53-0.424)  = 0.954

使用信息增益构建决策树

要点：

• 从与根节点关联的所有培训实例开始
• 使用信息增益选择标记每个节点的属性
• 注意：没有root-to-leaf路径应该包含两次相同的离散属性
• 递归地构建训练实例子集上的每个子树，这些子树将被分类到树中的路径。

边界案例：

• 如果仍然存在所有肯定或所有负面训练实例，则相应地将该节点标记为“是”或“否”。
• 如果没有剩余属性，则在该节点上留下多数投票训练实例的标签。
• 如果没有实例，则标记父节点培训实例的多数投票

例如：

现在，让我们使用信息增益为以下数据绘制决策树。

训练集：3个特征和2个分类

在这里，我们有3个特征和2个输出类别。

使用信息增益构建决策树。我们将采用每个功能并计算每个功能的信息。

在特征x上拆分

在特征Y上拆分

在特征Z上拆分

从上面的图像中我们可以看到，当我们对特征Y进行分割时，信息增益是最大的。因此，对于根节点，最合适的特征是特征Y.现在我们可以看到，在按特征Y分割数据集时，孩子 包含目标变量的纯子集。所以我们不需要进一步拆分数据集。

上述数据集的最终树将如下所示：

2、基尼指数

• 基尼指数是衡量随机选择的元素被错误识别的频率的指标。
• 这意味着应该首选具有较低基尼指数的属性。
• Sklearn支持基尼指数的“基尼”标准，默认情况下，它采用“基尼”值。

计算基尼系数的公式如下：

让我们考虑下图中的数据集，并使用指数索引绘制决策树：

在上面的数据集中，有5个属性，属性E是预测特征，包含2个（正面和负面）类。我们两个班级的比例相等。

在基尼指数中，我们必须选择一些随机值来对每个属性进行分类。此数据集的这些值为：

    A       B        C         D    >= 5     >= 3.0      >= 4.2    >= 1.4     < 5      < 3.0       < 4.2     < 1.4

计算变量A的基尼指数：

Value >= 5: 12

Attribute A >= 5 & class = positive:

Attribute A >= 5 & class = negative:

Gini(5, 7) = 1 –

Value < 5: 4 Attribute A < 5 & class = positive:

Attribute A < 5 & class = negative:

Gini(3, 1) = 1 –

通过增加权重并将每个基尼指数相加：

计算变量B的基尼指数: Value >= 3: 12 Attribute B >= 3 & class = positive:

Attribute B >= 5 & class = negative :

Gini(5, 7) = 1 –

Value < 3: 4 Attribute A < 3 & class = positive:

Attribute A < 3 & class = negative:

Gini(3, 1) = 1 –

通过增加权重并将每个基尼指数相加：

使用相同的方法，我们可以计算C和D属性的基尼指数：

             Positive    Negative  For A|>= 5.0    5       7       |<5    3       1  Ginin Index of A = 0.45825

             Positive    Negative  For B|>= 3.0    8       4       |< 3.0    0       4  Gini Index of B= 0.3345

             Positive    Negative  For C|>= 4.2    0       6       |< 4.2    8       2  Gini Index of C= 0.2

             Positive    Negative  For D|>= 1.4    0       5       |< 1.4    8       3  Gini Index of D= 0.273

最值得注意的决策树算法类型是：-

1.迭代二分光镜3（ID3）：该算法使用信息增益来决定使用哪个属性对当前数据子集进行分类。对于树的每个级别，递归地计算剩余数据的信息增益。

2. C4.5：该算法是ID3算法的后继算法。该算法使用信息增益或增益比来决定分类属性。它是ID3算法的直接改进，因为它可以处理连续和缺失的属性值。

3.分类和回归树（CART）：它是一种动态学习算法，它可以根据因变量生成回归树和分类树。