CART决策树算法：如何处理数值型与分类型特征

CART算法

决策树是一种非参数的监督学习方法，它不对数据集的分布形式做任何具体假设，但会根据数据中的特征类型和标签值动态地生成模型结构可以用于分类和回归问题。决策树的核心思想是递归地将特征空间划分为若干个单元，使得每个单元内的样本尽可能同质（即属于同一类别或具有相似的目标值）。

CART（Classification and Regression Trees）算法是一种常用的决策树算法，由Leo Breiman等人在1984年提出。CART算法的主要特点包括：

  • 二叉树结构：CART生成的是二叉决策树，每个内部节点都有两个子节点。
  • 适用于分类和回归：CART可以处理分类任务和回归任务。
  • 处理多种特征类型：能够同时处理数值型和类别型特征。
  • 基于不纯度度量：使用基尼指数（分类）或均方误差（回归）来选择最佳分割点。
  • 自动特征选择：在构建树的过程中，算法会自动选择最具区分性的特征。
  • 处理缺失值：理论上提供了处理缺失数据的策略，如使用替代分裂（Surrogate Splits）来应对缺失值。但在不同的实现中（例如Scikit-learn），这些机制并不一定内置。因此，用户通常需要在数据预处理阶段手动处理缺失数据。

CART与其它树方法的区别

CART与其他知名的决策树算法，如：ID3和C4.5算法在分割方法、适用的特征和任务类型方面存在以下区别：

区别项 CART ID3 C4.5
分割方法 基尼指数（分类）、均方误差（回归）作为分割标准，每次分割生成二叉树。 使用信息增益作为分割标准，可以生成多叉树，每个特征取值一个分支。 使用信息增益比作为分割标准，可以生成多叉树，减少多值偏好。
适用的特征 同时处理数值型和类别型特征。对于数值型特征，寻找最佳分割点进行二分。 主要处理类别型特征。对于数值型特征，需要先进行离散化处理。 处理数值型和类别型特征，能自动寻找最佳分割点，无需预处理。
任务类型 适用于分类和回归任务。在分类任务中使用基尼指数，在回归任务中使用均方误差。 主要用于分类任务，不适用于回归问题。 主要用于分类任务，也可通过修改处理回归问题。
CART与ID3、C4.5的主要区别

数值型特征与类别特征

数值特征和类别特征是两种最常见的特征类型。数值特征是可以用数字表示并且具有连续性的特征，如年龄、身高、收入和温度等。这类特征可以进行数学运算，如加减乘除，并且通常具有顺序关系。数值特征的这些特性使得它们在许多机器学习算法中易于处理和解释。类别特征是离散的、不具有数值意义的特征。常见的类别特征包括性别（如男/女）、颜色（如红/绿/蓝）、职业（如教师/医生/工程师）和城市（如北京/上海/广州）等。这些特征通常不能进行数学运算。

有关特征类型的详细说明，您也可以查看我之前撰写的一篇博客文章，其中提供了更全面的介绍。 《特征是什么》

CART——数值型特征的处理方法

CART算法处理数值型特征时，选择最佳分割点将数据集分为两部分。CART算法可以直接处理连续型特征，无需预先离散化。这种方法保留了数值特征的原始信息，避免了离散化可能导致的信息损失。相比之下，一些早期的决策树算法（如ID3）只能处理离散值，需要事先对连续特征进行离散化处理。它通过计算不同分割点的基尼指数（分类任务）或均方误差（回归任务），找出能最小化损失函数的最优分割点。CART算法在处理数值型特征时，会考虑数值型特征的大小关系和连续性特点，主要体现在以下几个方面：

  1. 有序性考虑：CART算法会对数值型特征的所有取值进行排序，这一步骤充分利用了数值型特征的有序性质。排序后，算法只需考虑相邻值之间的中点作为候选分割点，而不是随机选择分割点。
  2. 连续性处理：通过选择相邻值的中点作为候选分割点，CART算法能够更好地捕捉数值型特征的连续性。这种方法可以在保持数据连续性的同时，找到最优的分割点。
  3. 二分法分割：对于数值型特征，CART算法采用二分法进行分割，即将数据分为"小于等于"和"大于"两部分。这种方法既保持了数值的顺序关系，又能够有效地区分不同的数值范围。

具体步骤

  1. 寻找分割点：

对于数值型特征，假设特征 \(X\) 的取值为 \({x_1, x_2, ..., x_n}\)，则CART会将这些取值进行排序，并尝试将每个值作为候选分割点。候选分割点的数量通常为 \(n-1\)，即每个相邻值的中点。

  1. 计算分割点的基尼指数（分类任务）或均方误差（回归任务）：
    • 分类任务：CART会计算每个分割点在当前节点上的基尼指数（Gini Index）。基尼指数的计算方式如下：

    \(\displaystyle Gini(D) = 1 - \sum_{i=1}^{k} p_i^2\)

    其中， \(D\) 是数据集， \(p_i\) 是第 \(i\) 类的样本占比， \(k\) 是类别数。基尼指数越小，表示节点中的样本越纯（即节点中样本的类别越一致）。
    • 回归任务：CART会计算每个分割点的均方误差（MSE），即：

    \(\displaystyle MSE = \frac{1}{N} \sum_{i=1}^{N} (y_i - \bar{y})^2\)

    其中， \(N\) 是样本数， \(y_i\) 是第 \(i\) 个样本的真实值， \(\bar{y}\) 是所有样本的均值。MSE越小，表示分割后的子节点中的样本值越接近平均值，波动性越小。
  2. 选择最优分割点：

通过计算每个候选分割点的基尼指数或均方误差，CART会选择能够最小化基尼指数（分类任务）或均方误差（回归任务）的那个分割点作为当前节点的最优分割点。这样，数值型特征的处理结果通常是类似于“特征值小于某个阈值时向左分支，大于该阈值时向右分支”这样的分割规则。

  1. 生成分支：

使用最优分割点，将当前节点的数据集分割为两个子集，并继续对每个子集重复上述过程，直到达到停止条件（如节点纯度足够高或节点样本数低于某个阈值）。

示例

假设有一个数值型特征“年龄”，取值为[25, 32, 37, 45, 50, 55]。CART算法会尝试以下分割点：28.5、34.5、41、47.5、52.5。对于每个分割点，算法计算其基尼指数或均方误差，并选择最优的分割点进行分割，例如“年龄 < 47.5 向左，年龄 ≥ 47.5 向右”。

CART——类别型特征的处理方法

CART算法对分类型特征的处理策略与数值型不同，这是因为类别特征的离散性和不可排序性。CART算法会系统地评估类别型特征的各种取值组合，形成不同的分组方案。对每个潜在分组，CART计算相应的基尼指数（分类任务）或均方误差（回归任务）。通过这种全面评估，算法能识别出最佳分组方式——即最大程度减少不纯度或误差的方案。这种方法不仅高效处理高维度类别特征，还能捕捉类别间的复杂关系，从而提升模型的预测准确性和泛化能力。

具体步骤

  1. 类别的二分划分：
  2. 假设类别型特征 \(X\) 有 \(k\) 个取值 \(\{A, B, C, \ldots, K\}\) ，CART会尝试将这些取值进行二分组合。例如，如果 \(k = 3\) ，即 \(X\) 的取值为 \(\{A, B, C\}\) ，那么CART会尝试以下几种分组方式：\(\{A\}\) 和 \(\{B, C\}\) ； \(\{B\}\) 和 \(\{A, C\}\) ；\(\{C\}\) 和 \(\{A, B\}\) 。
    当 \(k\) 较大时，可能会产生多种分组方式，因此CART通常仅尝试二分策略，以降低计算复杂度。
  3. 计算每种组合的基尼指数（分类任务）或均方误差（回归任务）：

CART会计算每种组合方式下的基尼指数（对于分类任务）或均方误差（对于回归任务），以评估该分组方式是否能够使得子节点中的样本更加纯净（即同一节点中样本的类别更加一致）。

  1. 选择最优分组方式：

在所有候选分组方式中，选择能够最小化基尼指数或均方误差的分组方式。这样，分类型特征的处理结果通常是类似于“类别在 {A, B} 中的样本向左分支，其他类别的样本向右分支”这样的分割规则。

  1. 生成分支：

使用最优分组方式，将当前节点的数据集分割为两个子集，并继续对每个子集重复上述过程，直到达到停止条件。

示例

假设有一个类别型特征“职业”，取值为“教师”、“医生”、“工程师”。CART会尝试以下几种分割方式：

  • “教师”与“医生或工程师”作为两个分支。
  • “医生”与“教师或工程师”作为两个分支。
  • “工程师”与“教师或医生”作为两个分支。

CART会计算这些分割方式的基尼指数，并选择最优的分割方式进行分支，例如“教师”作为一个分支，其他职业作为另一个分支。

浏览量: 332