一、ID3算法

1. 原理

   • 信息熵（Entropy）：信息熵用于衡量数据集的混乱程度。对于数据集$D$，包含$n$个类别标签，其信息熵$H(D)$计算公式为：
     $$H(D)=-\sum _{k=1}^n{p}_k{\log }_2{p}_k$$
     其中$p_k$是数据集中属于第$k$类样本的比例。例如，在一个简单的天气分类数据集中（晴天、雨天、多云），若晴天样本占比$p_1=0.4$，雨天$p_2=0.3$，多云$p_3=0.3$，则信息熵$H(D)=-0.4{\log }_{2}0.4-0.3{\log }_{2}0.3-0.3{\log }_{2}0.3$。
   • 信息增益（Information Gain）：用于衡量特征对数据集纯度的提升程度。假设数据集$D$，属性$a$有$V$个不同取值{a1,a2,⋯ ,aV}\{a^1,a^2,\cdots,a^V\}{a1,a2,⋯,aV}。使用属性$a$对$D$进行划分，得到$V$个子集{D1,D2,⋯ ,DV}\{D^1,D^2,\cdots,D^V\}{D1,D2,⋯,DV}。信息增益$g(D,a)$计算公式为：
     $$g(D,a)=H(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}H(D^v)$$
     例如，在一个判断水果是苹果还是香蕉的数据集中，有“颜色”这个属性（红、绿）。若红色样本中苹果占比高，绿色样本中香蕉占比高，通过这个属性划分数据集后纯度提升，信息增益较大。
   • 构建树时，从根节点开始，计算每个特征的信息增益，选择信息增益最大的特征作为当前节点的划分特征。对于划分后的子集，重复此步骤，直到满足停止条件（如所有样本属于同一类别、没有可用于划分的特征或子集样本数量小于阈值）。

2. 应用场景

   • 适用于处理离散型特征的分类问题。例如，在文本分类中，根据文章中的词汇（离散特征）判断文章所属类别（如体育类、科技类）。

3. 优点

   • 算法简单易懂，容易实现。计算信息熵和信息增益的概念直观，能够很好地处理离散特征。
   • 对小规模数据表现良好，能快速构建决策树。

4. 缺点

   • 倾向于选择取值较多的属性，可能导致过拟合。例如，一个特征有很多不同的值，每个值对应的类别比较单一，这个特征会被优先选择，但可能只是巧合，对新数据的泛化能力差。
   • 只能处理离散型属性，无法直接处理连续型属性。

二、C4.5算法

1. 原理

   • 信息增益比（Gain Ratio）：为了克服ID3算法倾向于选择取值较多属性的问题，C4.5算法引入信息增益比。首先计算属性$a$的固有值$H_a(D)$：
     $$H_a(D)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$
     信息增益比$g_R(D,a)$计算公式为：
     $$g_R(D,a)=\frac{g(D,a)}{H_a(D)}$$
     例如，在一个植物分类数据集中，有一个特征“叶子形状”有多种取值。通过计算信息增益比，可以更平衡地考虑这个特征的划分效果。
   • 树的构建过程与ID3类似，从根节点开始，计算每个特征的信息增益比，选择信息增益比最大的特征作为划分特征，在划分后的子集上重复此步骤，直到满足停止条件。

2. 应用场景

   • 同ID3一样，主要用于分类问题，尤其在处理离散型特征的分类任务时表现出色。例如，在医疗诊断中，根据患者的症状（离散特征）判断疾病类型。

3. 优点

   • 克服了ID3算法对取值较多属性的偏好，使得决策树的构建更加合理。
   • 能够处理离散型和连续型属性。对于连续型属性，先将其离散化，再进行处理。

4. 缺点

   • 计算信息增益比相对复杂，算法效率比ID3稍低。
   • 连续型属性的离散化过程可能会丢失信息，影响决策树的性能。

三、CART算法（分类与回归树）

1. 原理 - 分类任务

   • 基尼指数（Gini Index）：用于衡量数据集的纯度。对于数据集$D$，基尼指数$Gini(D)$计算公式为：
     $$Gini(D)=\sum _{k=1}^n{p}_k(1-p_k)=1-\sum _{k=1}^n{p}_k^2$$
     当使用属性$a$对数据集$D$进行划分，属性$a$有$V$个取值，得到$V$个子集{D1,D2,⋯ ,DV}\{D^1,D^2,\cdots,D^V\}{D1,D2,⋯,DV}，划分后的基尼指数$Gini\_index(D,a)$为：
     $$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$
     例如，在一个判断用户是否购买某产品的数据集中，计算“用户年龄”这个特征的基尼指数。根据不同年龄划分数据集后，计算每个子集的基尼指数，再根据子集大小加权求和，选择基尼指数最小的属性作为划分属性，使划分后的数据集纯度更高。
   • 构建树时，从根节点开始，计算每个特征的基尼指数，选择基尼指数最小的特征和对应的划分点进行划分。在划分后的子节点上重复此步骤，直到满足停止条件（如树的深度达到限制、节点中的样本数量小于阈值等）。
   • 原理 - 回归任务
   • 最小平方误差（MSE）：对于一个节点的数据集$D$，其目标值（如房价预测中的房价）的均值为$\overline{y}$，则该节点的平方误差为：
     $$MSE=\frac{1}{|D|}\sum _{i\in D}(y_i-\overline{y}{)}^2$$
     在选择划分特征和划分点时，遍历所有特征和可能的划分点，计算划分后的两个子节点的MSE之和。选择使MSE之和最小的特征和划分点进行划分。例如，在房价预测中，对于“房屋面积”这个特征，尝试不同划分点，计算划分后的MSE之和，找到最小的划分点。

2. 应用场景

   • 既可以用于分类任务，如客户流失预测（根据客户行为特征判断是否流失），也可以用于回归任务，如房价预测、销售额预测等。

3. 优点

   • 对于分类和回归任务都有很好的适用性，是一种通用的决策树算法。
   • 可以处理连续型和离散型数据，不需要像C4.5那样对连续型数据进行额外的离散化处理。
   • 能够自动处理缺失值，在一定程度上增强了算法的鲁棒性。

4. 缺点

   • 对异常值比较敏感。在回归任务中，异常值可能会导致MSE计算出现较大偏差，影响树的构建。
   • 构建的树可能会比较复杂，容易出现过拟合现象，需要进行剪枝处理。

四、CHAID算法

1. 原理

   • 卡方检验（Chi - squared test）：基于卡方检验来确定最佳的分类变量和分割点。对于两个分类变量$A$和$B$，$A$有$r$个类别，$B$有$c$个类别，列联表中的每个单元格$(i,j)$表示$A$的第$i$类和$B$的第$j$类的交叉频数$n_{ij}$。卡方统计量${\chi }^2$计算公式为：
     $${\chi }^2=\sum _{i=1}^r\sum _{j=1}^c\frac{(n_{ij}-E_{ij}{)}^2}{E_{ij}}$$
     其中$E_{ij}$是期望频数，$E_{ij}=\frac{n_{i\cdot }{n}_{\cdot j}}{n}$，$n_{i\cdot }$是第$i$行的总和，$n_{\cdot j}$是第$j$列的总和，$n$是总的样本数。
   • 在决策树构建过程中，对于每个节点，对所有可能的分类变量进行卡方检验，计算每个变量作为分割变量时的卡方统计量。根据统计显著性水平（如$p-value=0.05$）来决定是否进行分割。若$p-value$大于设定的显著性水平，说明分割后的子节点之间没有显著差异，就不进行分割。
   • 例如，在市场调查数据中，研究消费者性别（男/女）和购买产品类型（电子产品/日用品/食品）之间的关联。通过卡方检验构建决策树，若性别和产品类型之间有显著关联，就以此为依据进行分割。

2. 应用场景

   • 主要用于分类问题，尤其适用于处理多个分类变量之间的关系。例如，在市场细分中，根据消费者的多种属性（如年龄、性别、收入等分类变量）对市场进行细分。

3. 优点

   • 能够有效处理分类变量之间的相互关系，挖掘变量之间的关联，使得决策树的分割更有意义。
   • 基于统计检验进行分割，具有一定的统计学理论支持，结果相对可靠。

4. 缺点

   • 只能处理分类变量，对于连续型变量需要先进行离散化处理。
   • 计算卡方统计量和进行假设检验相对复杂，当数据量较大时，计算成本较高。

决策树算法对比与示例

一、对比

1. 特征选择标准
   • ID3：基于信息增益选择特征。倾向于选择具有较多取值的特征，因为这样的特征可能会使信息增益较大。例如，在一个有“颜色”（红、绿、蓝）和“形状”（圆、方）的数据集用于区分两种物体时，如果“颜色”这个特征每个取值对应的类别很单一，那么它的信息增益可能会很大，容易被优先选择。
   • C4.5：使用信息增益比来克服ID3对取值较多特征的偏好。通过计算属性的固有值，将信息增益标准化。在一个包含多种植物特征的数据集里，像“叶子形状”这种有多种变化的特征不会因为取值多就被过度选择，而是综合考虑其信息增益比。
   • CART（分类）：依据基尼指数选择特征。基尼指数衡量数据集的不纯度，选择使划分后基尼指数最小的特征。例如在判断客户是否购买产品的数据集，CART会考虑哪个特征能让划分后的子节点纯度更高，更关注类别分布的均匀性。
   • CHAID：以卡方检验来确定最佳分类变量和分割点。重点在于检验分类变量之间的关联性。在市场调研数据中，若研究消费者性别和购买产品类型的关系，通过卡方检验判断这种关联是否显著来决定是否以此为分割变量。
2. 数据类型处理
   • ID3：主要处理离散型特征，对于连续型特征需要先进行离散化处理才能使用。
   • C4.5：可以处理离散型和连续型特征。对于连续型特征，先将其离散化，不过这个过程可能会丢失信息。
   • CART：能够自然地处理连续型和离散型数据。在回归任务中直接利用连续型数据计算最小平方误差，在分类任务中处理离散型数据计算基尼指数。
   • CHAID：主要用于处理分类变量，对于连续型变量要先进行离散化才能应用卡方检验。
3. 树的构建方式
   • ID3：从根节点开始，每次选择信息增益最大的特征进行划分，直到满足停止条件。例如在一个简单的动物分类数据集（分为哺乳动物和非哺乳动物），以“是否有毛发”作为信息增益最大的特征先划分，然后在子节点继续找信息增益最大的特征划分。
   • C4.5：类似于ID3，但以信息增益比来选择划分特征。构建过程中不断寻找信息增益比最大的特征进行划分，递归构建树结构。
   • CART（分类）：从根节点开始，计算每个特征的基尼指数，选择基尼指数最小的特征和对应的划分点进行划分，重复这个过程构建树。
   • CHAID：从根节点开始，对所有可能的分类变量进行卡方检验，根据统计显著性水平决定是否进行分割。若变量之间关联显著，就以此为依据进行分割，递归构建树。
4. 过拟合情况
   • ID3：容易过拟合，因为倾向于选择取值较多的特征，可能会学到数据中的噪声。例如在一个包含很多无关特征且部分特征取值多样的数据集上，ID3可能会构建出过于复杂的树。
   • C4.5：通过信息增益比在一定程度上缓解了过拟合，但连续型特征离散化过程可能引入新问题导致过拟合。
   • CART：也可能过拟合，尤其是在数据有噪声或者树的深度没有有效控制时。不过它的剪枝方法相对成熟，可以较好地处理过拟合。
   • CHAID：如果不注意统计显著性水平的设置，可能会过度分割，导致过拟合。而且它对数据的分布和变量之间的关系比较敏感，容易在复杂的数据关系中产生过拟合。

二、示例

假设我们有一个数据集用于判断是否购买电脑，数据集如下：

1. ID3算法示例
   • 首先计算根节点的信息熵：
     • 数据集中总共有$n=8$个样本，其中购买电脑的样本数为$n_1=5$，不购买电脑的样本数为$n_2=3$。
     • 则购买电脑的样本比例$p_1=\frac{n_1}{n}=\frac{5}{8}$，不购买电脑的样本比例$p_2=\frac{n_2}{n}=\frac{3}{8}$。
     • 根据信息熵公式$H(D)=-{\sum }_{k=1}^n{p}_k{\log }_2{p}_k$，这里$n=2$，所以根节点的信息熵为：
       $$H(D)=-\frac{5}{8}{\log }_2\frac{5}{8}-\frac{3}{8}{\log }_2\frac{3}{8}\approx 0.954$$
   • 然后计算每个特征的信息增益：
     • 年龄特征：“年龄”特征有三个取值：青年、中年、老年。
       • 青年对应的子集$D_{青年}$中有$3$个样本，其中购买电脑的有$1$个，不购买电脑的有$2$个。所以在这个子集中，购买电脑的比例$p_{1,青年}=\frac{1}{3}$，不购买电脑的比例$p_{2,青年}=\frac{2}{3}$。
       • 根据信息熵公式，$D_{青年}$的信息熵为$H(D_{青年})=-\frac{1}{3}{\log }_2\frac{1}{3}-\frac{2}{3}{\log }_2\frac{2}{3}\approx 0.918$。
       • 中年对应的子集$D_{中年}$中有$2$个样本，都购买电脑，所以$H(D_{中年})=0$。
       • 老年对应的子集$D_{老年}$中有$3$个样本，其中购买电脑的有$2$个，不购买电脑的有$1$个。所以$H(D_{老年})=-\frac{2}{3}{\log }_2\frac{2}{3}-\frac{1}{3}{\log }_2\frac{1}{3}\approx 0.918$。
       • “年龄”特征划分后的信息增益$g(D,年龄)$，根据公式$g(D,a)=H(D)-{\sum }_{v=1}^V\frac{|D^v|}{|D|}H(D^v)$，这里$V=3$，$|D_{青年}|=3$，$|D_{中年}|=2$，$|D_{老年}|=3$，$|D|=8$，所以：
         $$g(D,年龄)=0.954-(\frac{3}{8}\times 0.918+\frac{2}{8}\times 0+\frac{3}{8}\times 0.918)\approx 0.042$$
     • 同样地，可以计算“收入”“学生”“信用等级”等特征的信息增益。假设经过计算“学生”特征的信息增益最大。
   • 以“学生”作为根节点的划分特征构建决策树。对于“学生”为“是”的分支，该子集中所有样本都购买电脑，所以这个分支是一个叶节点，标记为“是”。对于“学生”为“否”的分支，这个子集中包含了$4$个样本，在这个子集中继续计算剩余特征（“年龄”、“收入”、“信用等级”）的信息增益，重复上述步骤进行划分，直到所有子集的样本都属于同一类别或者满足停止条件。
2. C4.5算法示例
   • 首先计算根节点信息熵，同ID3算法，$H(D)\approx 0.954$。
   • 计算每个特征的信息增益比。以“年龄”特征为例，先计算其信息增益（同ID3计算过程）$g(D,年龄)\approx 0.042$。
   • 然后计算属性“年龄”的固有值$H_a(D)$：
     • “年龄”有三个取值，$|D_{青年}|=3$，$|D_{中年}|=2$，$|D_{老年}|=3$，$|D|=8$。
     • $H_a(D)=-\frac{3}{8}{\log }_2\frac{3}{8}-\frac{2}{8}{\log }_2\frac{2}{8}-\frac{3}{8}{\log }_2\frac{3}{8}\approx 1.56$
     • 信息增益比$g_R(D,年龄)=\frac{g(D,年龄)}{H_a(D)}=\frac{0.042}{1.56}\approx 0.027$
   • 同样计算其他特征的信息增益比，假设“信用等级”特征的信息增益比最大。以“信用等级”作为根节点的划分特征构建决策树，后续步骤同ID3算法，在划分后的子集上继续计算信息增益比来选择划分特征，直到满足停止条件。
3. CART算法示例（分类）
   • 计算根节点的基尼指数：
     • 数据集中购买电脑的样本比例$p_1=\frac{5}{8}$，不购买电脑的样本比例$p_2=\frac{3}{8}$。
     • 根据基尼指数公式$Gini(D)={\sum }_{k=1}^n{p}_k(1-p_k)=1-{\sum }_{k=1}^n{p}_k^2$，这里$n=2$，所以根节点的基尼指数为：
       $$Gini(D)=1-(\frac{5}{8}{)}^2-(\frac{3}{8}{)}^2=0.469$$
   • 计算每个特征划分后的基尼指数。以“学生”特征为例，“学生”有“是”和“否”两个取值。
     • “学生”为“是”的子集$D_{是}$中有$4$个样本，都购买电脑，$Gini(D_{是})=0$。
     • “学生”为“否”的子集$D_{否}$中有$4$个样本，其中购买电脑的有$1$个，不购买电脑的有$3$个，购买电脑的比例$p_{1,否}=\frac{1}{4}$，不购买电脑的比例$p_{2,否}=\frac{3}{4}$，$Gini(D_{否})=1-(\frac{1}{4}{)}^2-(\frac{3}{4}{)}^2=0.375$。
     • 划分后的基尼指数$Gini\_index(D,学生)=\frac{4}{8}\times 0+\frac{4}{8}\times 0.375=0.188$
   • 同样计算其他特征划分后的基尼指数，假设“信用等级”特征划分后的基尼指数最小。以“信用等级”作为根节点的划分特征构建决策树，对于划分后的子节点，继续计算基尼指数选择划分特征，直到满足停止条件。
4. CHAID算法示例
   • 假设我们要研究“年龄”和“是否购买电脑”之间的关系。构建列联表如下：
     |年龄|购买电脑|不购买电脑|
     |—|—|—|
     |青年|1|2|
     |中年|2|0|
     |老年|2|1|
   • 计算卡方统计量。先计算期望频数，例如对于“青年 - 购买电脑”单元格，期望频数$E_{11}=\frac{(1+2)\times (1+2+2+1)}{8}=\frac{3\times 6}{8}=2.25$。
   • 然后根据卡方统计量公式${\chi }^2={\sum }_{i=1}^r{\sum }_{j=1}^c\frac{(n_{ij}-E_{ij}{)}^2}{E_{ij}}$计算卡方值。假设经过计算与其他特征相比，“年龄”和“是否购买电脑”的卡方值对应的$p-value$小于设定的显著性水平（如$0.05$），则可以以“年龄”作为根节点的划分特征。
   • 对于划分后的子集，继续对其他特征进行卡方检验，决定是否进一步划分，直到满足停止条件（如所有$p-value$大于显著性水平）。