在本例中，我们将使用ID3算法作为决策树的构建方法。ID3算法主要依赖于信息增益来选择最佳的特征进行分裂。让我们从一个简单的数据集开始，用于预测一个人是否会去公园玩耍。
数据集：
| 序号 | 天气 | 温度 | 是否去公园玩耍 |
|---|---|---|---|
| 1 | 晴天 | 炎热 | 否 |
| 2 | 晴天 | 适中 | 是 |
| 3 | 阴天 | 炎热 | 否 |
| 4 | 阴天 | 寒冷 | 否 |
| 5 | 雨天 | 适中 | 是 |
我们的目标是构建一个决策树来根据天气和温度预测一个人是否会去公园玩耍。
步骤1：计算数据集的信息熵（entropy）
信息熵是衡量数据集纯度的指标。假设数据集中有k个类别，每个类别的概率为p_i，则数据集的信息熵为：
Entropy(S) = -∑(p_i * log2(p_i))
在我们的例子中，有2个类别（去公园、不去公园）。有3个不去公园的样本，2个去公园的样本。因此，数据集的信息熵为：
Entropy(S) = -[(3/5) * log2(3/5) + (2/5) * log2(2/5)] ≈ 0.971
步骤2：计算每个特征的信息增益
信息增益（Information Gain）表示在给定特征的条件下，数据集的信息熵的减少。计算公式如下：
Gain(S, A) = Entropy(S) – ∑[(|S_v| / |S|) * Entropy(S_v)]
其中，A表示某个特征，S_v表示在特征A上取值为v的子集，|S_v|表示子集中的样本数，|S|表示整个数据集的样本数。
我们需要计算天气和温度两个特征的信息增益。
- 天气特征：
- 晴天子集：{不去公园，去公园}，Entropy = -[(1/2) * log2(1/2) + (1/2) * log2(1/2)] = 1
- 阴天子集：{不去公园，不去公园}，Entropy = -[1 * log2(1) + 0] = 0
- 雨天子集：{去公园}，Entropy = 0
Gain(S, 天气) = Entropy(S) – [(2/5) * 1 + (2/5) * 0 + (1/5) * 0] = 0.971 – 0.4 = 0.571
- 温度特征：
- 炎热子集：{不去公园，不去公园}，Entropy = -[1 * log2(1) + 0] = 0
- 适中子集：{去公园，去公园}，Entropy = -[1 * log2(1) + 0] = 0
- 寒冷子集：{不去公园}，Entropy = 0
Gain(S, 温度) = Entropy(S) – [(2/5) * 0 + (2/5) * 0 + (1/5) * 0] = 0.971 – 0 = 0.971
步骤3：选择最佳特征进行分裂
比较每个特征的信息增益，我们可以看到温度特征具有更高的信息增益，因此选择温度特征进行分裂。
温度
/ | \
炎热 适中 寒冷
| | |
否 是 否现在，我们已经构建了一个简单的决策树。对于炎热天气和寒冷天气，预测结果是不去公园；对于适中天气，预测结果是去公园。
注意：这个例子中的数据集非常简单，因此我们直接得到了一个完美的决策树。实际应用中的数据集通常更复杂，可能需要更多的分裂和剪枝操作来构建一个高效的决策树。
Python代码实现：MLearnPractice/decisionTree.py