ID3、C4.5和CART算法构建水果分类树桩模型

本文以水果类型、总个数、长条、甜、黄色等特征为例，使用ID3、C4.5和CART三种算法构建深度为1的决策树模型（树桩模型），并对比分析三种算法的差异。

由于表格中的数据是连续值，需要将其离散化后才能进行决策树的构建。下面给出离散化后的数据表格：

水果类型|总个数|长条|甜|黄色 ---|---|---|---|--- 香蕉|500|1|1|1 橘子|300|0|0|2 其他|200|1|0|0 总计|1000|2|1|3

接下来分别使用ID3，C4.5和CART算法构建树桩模型：

ID3算法

首先需要计算每个特征的信息增益，公式为：信息增益 = 全局熵 - 条件熵

全局熵：E = - (500/1000) * log2(500/1000) - (300/1000) * log2(300/1000) - (200/1000) * log2(200/1000) = 1.57095 条件熵（按'长条'特征分类）：E(长条=1) = - (500/700) * log2(500/700) - (200/700) * log2(200/700) = 0.98523，E(长条=0) = - (300/300) * log2(300/300) = 0 信息增益：IG(长条) = 1.57095 - (700/1000) * 0.98523 - (300/1000) * 0 = 0.22314

条件熵（按'甜'特征分类）：E(甜=1) = - (500/500) * log2(500/500) = 0，E(甜=0) = - (300/500) * log2(300/500) - (200/500) * log2(200/500) = 0.97095 信息增益：IG(甜) = 1.57095 - (500/1000) * 0 - (500/1000) * 0.97095 = 0.64730

条件熵（按'黄色'特征分类）：E(黄色=1) = - (450/450) * log2(450/450) = 0，E(黄色=2) = - (300/300) * log2(300/300) = 0，E(黄色=0) = - (250/250) * log2(250/250) = 0 信息增益：IG(黄色) = 1.57095 - (450/1000) * 0 - (300/1000) * 0 - (250/1000) * 0 = 1.57095

因此，选择信息增益最大的'黄色'特征作为根节点，得到决策树如下：

黄色=1，香蕉黄色=2，橘子黄色=0，其他

C4.5算法

C4.5算法与ID3算法类似，但是在计算信息增益时对特征进行了归一化处理，即信息增益率 = 信息增益 / 分裂信息

分裂信息：SplitInfo(长条) = - (700/1000) * log2(700/1000) - (300/1000) * log2(300/1000) = 0.88129，SplitInfo(甜) = - (500/1000) * log2(500/1000) - (500/1000) * log2(500/1000) = 1，SplitInfo(黄色) = - (450/1000) * log2(450/1000) - (300/1000) * log2(300/1000) - (250/1000) * log2(250/1000) = 1.55861

信息增益率：GainRatio(长条) = 0.22314 / 0.88129 = 0.25302，GainRatio(甜) = 0.64730 / 1 = 0.64730，GainRatio(黄色) = 1.57095 / 1.55861 = 1.008

因此，选择信息增益率最大的'黄色'特征作为根节点，得到决策树如下：

黄色=1，香蕉黄色=2，橘子黄色=0，其他

CART算法

CART算法采用基尼系数作为分裂特征的依据，公式为：GiniIndex = 1 - Σ(p^2)

基尼系数（按'长条'特征分类）：Gini(长条=1) = 1 - ((400/500)^2 + (100/500)^2) = 0.32000，Gini(长条=0) = 1 - ((0/300)^2 + (300/300)^2) = 0 基尼系数（按'甜'特征分类）：Gini(甜=1) = 1 - ((350/500)^2 + (150/500)^2) = 0.46000，Gini(甜=0) = 1 - ((0/300)^2 + (150/300)^2) + ((0/200)^2 + (50/200)^2) = 0.37833 基尼系数（按'黄色'特征分类）：Gini(黄色=1) = 1 - ((450/450)^2) = 0，Gini(黄色=2) = 1 - ((300/300)^2) = 0，Gini(黄色=0) = 1 - ((350/500)^2 + (150/500)^2) - ((450/500)^2 + (50/500)^2) = 0.24000

因此，选择基尼系数最小的'黄色'特征作为根节点，得到决策树如下：

黄色=1，香蕉黄色=2，橘子黄色=0，其他

综上，三种算法得到的树桩模型相同，均以'黄色'特征作为根节点，分别将数据集分成三个子集。