【机器学习】机器学习的基本分类-监督学习-决策树-ID3 算法

ID3（Iterative Dichotomiser 3）是决策树的一种构造算法，由 Ross Quinlan 在 1986 年提出。它主要用于分类问题，通过信息增益选择特征来构建决策树。ID3 假设数据是离散型特征，且不支持连续型数据。

1. 核心思想

划分标准：
- 使用 信息增益（Information Gain）作为特征选择的标准。
- 选择信息增益最大的特征进行分裂。
递归构造：
- 从根节点开始，每次根据信息增益选择特征，生成子节点。
- 对每个子节点重复这一过程，直到满足停止条件（例如数据不可再分，或者所有样本类别相同）。

2. 信息增益

信息增益基于**信息熵（Entropy）**的概念：

信息熵的定义

信息熵衡量数据集的不确定性：

$H(D) = - \sum_{i=1}^C p_i \log_2(p_i)$

D：数据集。
C：类别数。
$p_i$ ：数据集中属于第 i 类的概率。

条件熵

划分数据集 D 后的条件熵为：

$H(D|A) = \sum_{v \in \text{Values}(A)} \frac{|D_v|}{|D|} H(D_v)$

A：划分特征。
$D_v$ ：特征 A 的值为 v 时的子数据集。
$|D_v|/|D|$ ：数据划分到 v 类的比例。

信息增益公式

信息增益是划分前后信息熵的减少：

$IG(D, A) = H(D) - H(D|A)$

H(D)：划分前的熵。
H(D|A)：划分后的条件熵。
特征 A 的信息增益越大，说明使用 A 划分后数据集的不确定性降低越多，划分效果越好。

3. ID3 算法步骤

输入：
- 数据集 D（包含样本和对应的类别标签）。
- 特征集 A。
步骤：
1. 计算当前数据集的熵 H(D)。
2. 对于每个特征 A ∈ A：
  - 计算特征 A 的信息增益 IG(D, A)。
3. 选择信息增益最大的特征 $A^*$ ，作为当前节点的分裂特征。
4. 根据特征的每个取值 v，划分数据集：
  - 如果子数据集 $D_v$ 为空，设置叶节点为多数类别。
  - 如果子数据集 $D_v$ 非空，递归构造子树。
5. 当满足停止条件时，停止分裂。
输出：
- 决策树。

4. 算法特点

优点

简单易实现：基于熵和信息增益的数学原理，计算相对直观。
解释性强：生成的决策树规则可以直接解释分类依据。

缺点

对连续特征无直接支持：需要离散化连续特征。
易过拟合：树可能过于复杂，适应训练数据的噪声。
偏好多值特征：特征的可能取值越多，信息增益往往越高，可能导致模型偏向这些特征。

5. 示例

数据示例

假设有以下样本数据：

天气	温度	湿度	风力	是否运动
晴天	高	高	弱	否
晴天	高	高	强	否
阴天	高	高	弱	是
雨天	中	高	弱	是
雨天	低	正常	弱	是

目标：构造决策树判断是否运动。

计算步骤

计算根节点的熵 H(D) 数据集中是否运动的比例为：
- P(是) = 3/5, P(否) = 2/5。
  熵为：
计算每个特征的条件熵 H(D|A) 和信息增益
- 天气（Weather）：
  - $H(D|\text{Sunny}) = -1 \log_2(1) = 0$ 。
  - 对所有天气取值加权计算条件熵，得到 $H(D|\text{Weather})$ 。
  - 信息增益 $IG(D, \text{Weather}) = H(D) - H(D|\text{Weather})$ 。
- 温度（Temperature）：
  - 类似方法计算温度的条件熵和信息增益。
- 湿度、风力：
  - 按相同方法计算。
选择信息增益最大的特征：
- 设 $A^* = \text{Weather}$ ，构造根节点。
递归分裂子数据集：
- 对子数据集重复计算，直到满足停止条件。

6. 代码实现

Python 示例

from math import log2

# 计算熵
def entropy(labels):
    total = len(labels)
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum((count / total) * log2(count / total) for count in counts.values())

# 计算信息增益
def information_gain(data, labels, feature_index):
    total_entropy = entropy(labels)
    feature_values = [row[feature_index] for row in data]
    unique_values = set(feature_values)
    conditional_entropy = 0
    for value in unique_values:
        subset = [labels[i] for i in range(len(data)) if data[i][feature_index] == value]
        conditional_entropy += (len(subset) / len(data)) * entropy(subset)
    return total_entropy - conditional_entropy

# 示例数据
data = [
    ["晴天", "高", "高", "弱"],
    ["晴天", "高", "高", "强"],
    ["阴天", "高", "高", "弱"],
    ["雨天", "中", "高", "弱"],
    ["雨天", "低", "正常", "弱"]
]
labels = ["否", "否", "是", "是", "是"]

# 特征索引（天气、温度、湿度、风力）
for i in range(4):
    print(f"Feature {i}, Information Gain: {information_gain(data, labels, i):.4f}")

输出结果

Feature 0, Information Gain: 0.9710
Feature 1, Information Gain: 0.4200
Feature 2, Information Gain: 0.1710
Feature 3, Information Gain: 0.3219

7. 扩展

C4.5 算法：
- 使用信息增益比替代信息增益，解决偏好多值特征问题。
- 支持连续型特征。
CART 算法：
- 支持分类与回归，使用基尼指数或均方误差。

ID3 是决策树的早期版本，适用于简单的分类问题，但由于其限制（如无法处理连续型特征、易过拟合），后续算法（如 C4.5 和 CART）进一步改进了 ID3。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/930349.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！