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

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

---

1. 核心思想

1. 划分标准：

   • 使用 信息增益（Information Gain）作为特征选择的标准。
   • 选择信息增益最大的特征进行分裂。

2. 递归构造：

   • 从根节点开始，每次根据信息增益选择特征，生成子节点。
   • 对每个子节点重复这一过程，直到满足停止条件（例如数据不可再分，或者所有样本类别相同）。

---

2. 信息增益

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

信息熵的定义

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

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

条件熵

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

• A：划分特征。
• ​：特征 A 的值为 v 时的子数据集。
• ：数据划分到 v 类的比例。

信息增益公式

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

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

---

3. ID3 算法步骤

1. 输入：

   • 数据集 D（包含样本和对应的类别标签）。
   • 特征集 A。

2. 步骤：

   1. 计算当前数据集的熵 H(D)。
   2. 对于每个特征 A ∈ A：
      • 计算特征 A 的信息增益 IG(D, A)。
   3. 选择信息增益最大的特征 ，作为当前节点的分裂特征。
   4. 根据特征 的每个取值 v，划分数据集：
      • 如果子数据集 ​ 为空，设置叶节点为多数类别。
      • 如果子数据集 ​ 非空，递归构造子树。
   5. 当满足停止条件时，停止分裂。

3. 输出：

   • 决策树。

---

4. 算法特点

优点

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

缺点

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

---

5. 示例

数据示例

假设有以下样本数据：

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

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

---

计算步骤

1. 计算根节点的熵 H(D) 数据集中是否运动的比例为：

   • P(是) = 3/5, P(否) = 2/5。
     熵为：
   

2. 计算每个特征的条件熵 H(D|A) 和信息增益

   • 天气（Weather）：

     • 。
     • 对所有天气取值加权计算条件熵，得到 。
     • 信息增益 。

   • 温度（Temperature）：

     • 类似方法计算温度的条件熵和信息增益。

   • 湿度、风力：

     • 按相同方法计算。

3. 选择信息增益最大的特征：

   • 设 ，构造根节点。

4. 递归分裂子数据集：

   • 对子数据集重复计算，直到满足停止条件。

---

 6. 代码实现

Python 示例

from math import log2# 计算熵
def entropy(labels):total = len(labels)counts = {}for label in labels:counts[label] = counts.get(label, 0) + 1return -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 = 0for 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. 扩展

1. C4.5 算法：

   • 使用信息增益比替代信息增益，解决偏好多值特征问题。
   • 支持连续型特征。

2. CART 算法：

   • 支持分类与回归，使用基尼指数或均方误差。

---

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