机器学习-决策树（Decision Tree）简介
机器学习-决策树（Decision Tree）简介
背景介绍
- 决策树算法属于监督学习的范畴。它们可用于解决回归和分类问题。
- 决策树使用树表示来解决每个叶节点对应于类标签的问题，并且属性在树的内部节点上表示。
- 我们可以使用决策树表示离散属性上的任何布尔函数。
以下是我们在使用决策树时所做的一些假设：
- 一开始，我们将整个训练集视为根。
- 特征值优选是分类的。如果值是连续的，则在构建模型之前将它们离散化。
- 在属性值的基础上，记录以递归方式分布。
- 我们使用统计方法以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个分类
X | Y | Z | C |
|---|---|---|---|
1 | 1 | 1 | I |
1 | 1 | 0 | I |
0 | 0 | 1 | II |
1 | 0 | 0 | II |
在这里，我们有3个特征和2个输出类别。
使用信息增益构建决策树。我们将采用每个功能并计算每个功能的信息。
在特征x上拆分
在特征Y上拆分
在特征Z上拆分
从上面的图像中我们可以看到，当我们对特征Y进行分割时，信息增益是最大的。因此，对于根节点，最合适的特征是特征Y.现在我们可以看到，在按特征Y分割数据集时，孩子 包含目标变量的纯子集。所以我们不需要进一步拆分数据集。
上述数据集的最终树将如下所示：
2、基尼指数
- 基尼指数是衡量随机选择的元素被错误识别的频率的指标。
- 这意味着应该首选具有较低基尼指数的属性。
- Sklearn支持基尼指数的“基尼”标准，默认情况下，它采用“基尼”值。
计算基尼系数的公式如下：
让我们考虑下图中的数据集，并使用指数索引绘制决策树：
INDEX | A | B | C | D | E |
|---|---|---|---|---|---|
1 | 4.8 | 3.4 | 1.9 | 0.2 | positive |
2 | 5 | 3 | 1.6 | 1.2 | positive |
3 | 5 | 3.4 | 1.6 | 0.2 | positive |
4 | 5.2 | 3.5 | 1.5 | 0.2 | positive |
5 | 5.2 | 3.4 | 1.4 | 0.2 | positive |
6 | 4.7 | 3.2 | 1.6 | 0.2 | positive |
7 | 4.8 | 3.1 | 1.6 | 0.2 | positive |
8 | 5.4 | 3.4 | 1.5 | 0.4 | positive |
9 | 7 | 3.2 | 4.7 | 1.4 | negative |
10 | 6.4 | 3.2 | 4.7 | 1.5 | negative |
11 | 6.9 | 3.1 | 4.9 | 1.5 | negative |
12 | 5.5 | 2.3 | 4 | 1.3 | negative |
13 | 6.5 | 2.8 | 4.6 | 1.5 | negative |
14 | 5.7 | 2.8 | 4.5 | 1.3 | negative |
15 | 6.3 | 3.3 | 4.7 | 1.6 | negative |
16 | 4.9 | 2.4 | 3.3 | 1 | negative |
在上面的数据集中，有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）：它是一种动态学习算法，它可以根据因变量生成回归树和分类树。