aiwiki.page
中文
计算机 / 人工智能 / classification-and-regression-trees

分类与回归树

分类与回归树是一种通过递归划分、基于不纯度的分裂和代价复杂度剪枝来构建二叉决策树的框架。

34 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
监督学习决策树学习集成学习人工智能统计学因果关系二叉树训练数据分类与回归…

**分类与回归树(CART)**是一种监督学习框架,通过反复将数据集划分为内部越来越同质的群组,预测类别结果或数值。它是决策树学习中的一种特定方法,而不是所有分类树或回归树的统称。其主要特征包括二叉递归划分、明确的分裂选择准则,以及在预测拟合程度与树的规模之间进行权衡的剪枝过程。

这一框架由利奥·布雷曼、杰罗姆·H. 弗里德曼、理查德·A. 奥尔申和查尔斯·J. 斯通在其于1984年出版的著作《分类与回归树》中确立。它将分类与回归纳入统一的统计学框架,并将树的构建转化为一个系统性的模型选择问题。拟合后的 CART 模型可以解读为一系列条件规则;从数学上看,它则是预测变量空间上的一个分段常数预测函数。

CART 不仅是一种重要的独立方法,也是现代集成学习的基础。它的优势在于,无需预先指定方程,就能自动发现非线性关系、变量间的交互作用以及有用的阈值。它的局限性,尤其是不稳定性、选择偏差和预测结果较为粗糙,也解释了为什么许多现代系统会组合多棵树,而不是依赖单棵树。

历史发展与适用范围

基于树的预测方法早于 CART 框架出现。早期关于自动交互检测的统计研究通过逐次划分,识别响应值不同的群体。与此同时,人工智能领域的研究者也开发了从样例中学习符号化决策规则的方法。这两条研究路线有着共同的理念:复杂的预测问题可以分解为一连串较简单的问题。不过,它们在分裂准则、变量类型的处理方式以及停止划分的判定方法上有所不同。

1984 年出版的 CART 专著为分类和回归提供了一套统一的统计方法。分类将观测对象归入离散类别,例如产品类型;回归则预测数值型响应,例如生产良率。CART 将这两项任务都视为递归划分问题,同时针对各自的特点采用不同的拟合度量。其中一项影响尤为深远的贡献,是将大树的构建与最终树规模的选择分开。该方法并不认定每一次局部效果较弱的分裂都应立即被否决,而是允许先构建一棵较大的树,再对其进行简化。

因此,CART 这一名称的含义比“决策树”更窄。经典 CART 采用二元分裂:每个内部节点都恰好有两个子节点。对于具有多个取值水平的类别型预测变量,处理方式是将这些水平分成两组,而不一定为每个水平各建一个分支。其他树学习方法可能采用多路分裂、不同的统计检验或不同的剪枝程序。例如,J. Ross Quinlan 提出的 ID3 和 C4.5 就属于一个与 CART 相关但有所区别的方法家族;他在 1993 年出版的相关专著使 C4.5 广为人知。

软件中的术语使用并不像上述历史区分那样严谨。某个程序库可能仅因其树采用二元分裂和不纯度降低机制,就将其称为 CART 式树,却省略了原始框架中的某些功能,例如替代分裂。反过来,某个系统也可能保留代价复杂度剪枝,同时扩展可用的损失函数或缺失值处理规则。因此,要确定某个实现是否支持特定功能,必须考察其实际算法,而不能仅凭 CART 这一标签作出推断。

CART 也促进了预测建模与探索性统计学的联系。树无需假定整体上存在线性关系,就能揭示子群及特定条件下的规律。不过,该框架主要服务于预测:仅凭从观测数据中识别出的一个分支,本身并不能确立因果关系;某个变量被选在靠近根节点的位置,也不意味着它自然就是科学意义上决定响应的根本因素。

树结构与预测区域

CART 模型用一棵有根二叉树表示。根节点包含全部训练数据。每个内部节点对一个预测变量进行检验,并根据检验结果将观测样本分配到两个子节点之一。终端节点也称为叶节点,包含最终的预测结果。预测时,只需沿着从根节点到某个叶节点的一条路径向下遍历,逐一执行该路径上的检验。

对于数值型预测变量 xjx_j,典型的分裂形式为 xj≤sx_j\leq s,其中 ss 为阈值。满足条件的观测样本进入一个子节点,其余样本进入另一个子节点。对于类别型预测变量,检验条件是其取值是否属于某个类别子集。例如,按材料类型进行分裂时,可以将铝和铜分到一个子节点,将钢和钛分到另一个子节点。经典的单变量 CART 通常不会根据 2x1−x2>52x_1-x_2>5 这样的线性组合进行分裂;这种分裂属于范围更广的斜决策树方法。

每个叶节点都对应一个区域,该区域由通往该叶节点的路径上所有条件的交集确定。对于数值型预测变量,这些区域的边界与坐标轴平行,并且在某些方向上可能是无界的。如果各叶节点定义的区域为 R1,…,RMR_1,\ldots,R_M,则预测函数可写为

f^(x)=∑m=1Mcm 1{x∈Rm},\hat f(x)=\sum_{m=1}^{M}c_m\,\mathbf{1}\{x\in R_m\},

其中,cmc_m 是赋予区域 RmR_m 的预测值。当观测样本落入该区域时,指示函数的值为 1。因此,即使所逼近的关系是光滑的,模型本身仍是分段常数函数。

在普通平方误差回归中,叶节点以其中训练样本的响应均值作为预测值。在分类中,叶节点通常将出现次数最多的类别作为预测类别,并保存各类别的经验比例作为概率估计。若观测样本的权重为 wiw_i,则叶节点 mm 中类别 kk 的估计概率为

p^mk=∑i:xi∈Rmwi1{yi=k}∑i:xi∈Rmwi.\hat p_{mk} = \frac{\sum_{i:x_i\in R_m}w_i\mathbf{1}\{y_i=k\}} {\sum_{i:x_i\in R_m}w_i}.

类别权重、先验概率和不等的误分类代价,都可能改变实际采用的类别比例或最终的类别判定。

这种结构能够自然地表达交互作用。例如,按机器温度进行的分裂可能只出现在某种特定材料对应的分支内,这意味着温度在该子群中的预测作用与其他子群不同。学习这种条件结构不需要显式构造乘积项。不过,一条简短规则的简单性只体现在局部:一棵深树的不同路径上可能包含数百个彼此交叠的条件,因此,理解单次预测可能远比理解整个模型容易。

分类与回归的分裂准则

在每个节点,CART 根据候选分裂对所得子节点同质性的提升程度进行比较。设 WtW_t 为节点 tt 中观测的总权重,I(t)I(t) 为该节点的不纯度。将节点分为子节点 tLt_L 和 tRt_R 的候选分裂,其局部不纯度降幅为

ΔI=I(t)−WtLWtI(tL)−WtRWtI(tR).\Delta I = I(t) -\frac{W_{t_L}}{W_t}I(t_L) -\frac{W_{t_R}}{W_t}I(t_R).

加权至关重要:一个很小的纯子节点不应与一个较大的子节点具有相同的影响力。在满足最小节点规模及其他约束的前提下,算法选择改进幅度最大的分裂。

对于分类,与 CART 联系最紧密的准则是基尼不纯度:

IG(t)=1−∑k=1Kpk(t)2.I_G(t)=1-\sum_{k=1}^{K}p_k(t)^2.

其中,pk(t)p_k(t) 是该节点中类别 kk 所占的比例,也可能经过权重或先验概率调整。仅包含一个类别的节点,其基尼不纯度为零。当两个类别各占一半时,基尼不纯度为 0.50.5。另一种解释是:按照该节点的类别分布独立抽取两次类别,所得类别不同的概率。

一个数值示例可以说明子节点权重为何重要。假设一个节点包含两个类别,每类各有 50 个观测。一次分裂产生两个大小相同的子节点,类别计数分别为 40,1040,10 和 10,4010,40。每个子节点的基尼不纯度均为 1−0.82−0.22=0.321-0.8^2-0.2^2=0.32,因此降幅为 0.50−0.32=0.180.50-0.32=0.18。相比之下,仅将一个观测单独分出的分裂虽然可能产生一个纯叶节点,却会使另一个子节点几乎保留原有的全部不确定性。有些实现也支持熵和信息增益,但从历史上看,它们并非 CART 的标志性准则。

对于采用平方误差损失的回归,节点的不纯度是节点内各观测值相对于该节点均值的均方偏差。最小化子节点的加权不纯度,等价于最小化它们合计的残差平方和:

SSE⁡(t)=∑i∈twi(yi−yˉt)2.\operatorname{SSE}(t) = \sum_{i\in t}w_i(y_i-\bar y_t)^2.

一次分裂带来的降幅可以表示为

SSE⁡(t)−SSE⁡(tL)−SSE⁡(tR)=WtLWtRWt(yˉtL−yˉtR)2.\operatorname{SSE}(t) -\operatorname{SSE}(t_L) -\operatorname{SSE}(t_R) = \frac{W_{t_L}W_{t_R}}{W_t} (\bar y_{t_L}-\bar y_{t_R})^2.

因此,有效的回归分裂会在兼顾子节点大小的同时,拉开子节点均值之间的差距。采用不同的损失函数会得到不同的叶节点预测值:例如,使绝对误差损失最小的是中位数,而不是均值。用于生成树的准则、用于剪枝的损失函数以及用于外部评估的指标不必完全相同,但它们之间的差异会影响最终选择哪个模型。

递归生长与计算特性

树的构建采用自顶向下的贪心算法。从根节点开始,该过程搜索可用的预测变量及候选划分,选择当前最优的分裂,然后在每个子节点中重复这一操作。这个过程属于递归,因为它在逐步缩小的数据集上反复求解同一个子问题,即寻找一种有效划分观测数据的方式。一旦完成一次分裂,常规的 CART 生长过程就不会根据树中更深层发现的结构重新考虑这次分裂。

对于在某个节点上具有 mm 个不同取值的数值型预测变量,最多存在 m−1m-1 种不同的阈值划分。阈值可以用相邻观测值之间的某个数值来表示,因为在该区间内移动阈值不会改变训练数据的划分结果。按预测变量的取值对观测数据排序后,算法实现就可以在扫描各个可能的分界位置时,同步更新累计类别计数、权重总和或响应值总和,而不必对每个候选划分都从头计算不纯度。

类别型预测变量带来了另一种搜索问题。当互为补集的两个子集视为同一种分裂时,具有 qq 个类别的预测变量共有 2q−1−12^{q-1}-1 种不同的非平凡二元划分。因此,穷举搜索的计算量随类别数呈指数增长。在标准的二分类或平方误差回归设定下,可以按响应变量的某种汇总统计量对类别排序,再沿该顺序搜索,从而避免枚举所有子集。多分类问题以及额外的约束条件则可能需要不同的策略或近似方法。

时间复杂度取决于排序和分裂搜索的具体实现方式。若能高效复用排序信息,对于 nn 个观测和 pp 个预测变量,每层树中数值型变量的分裂扫描成本大致为 O(pn)O(pn);因此,对于一棵平衡树,除排序相关的额外开销外,总计算量约为 O(pnlog⁡n)O(pn\log n)。重复排序、类别型变量的搜索、替代分裂的计算,以及严重不平衡的树生长,都可能增加这一成本。预测时,对于深度为 dd 的一条路径,通常只需进行 O(d)O(d) 次判定,而不必检查所有节点。

树的生长最终必须停止。常见的约束包括最大深度、分裂节点所需的最少观测数、每个叶节点中的最少观测数或最低权重,以及不纯度的最小改善量。这些都是超参数,而不是通过一次分裂估计出的参数。它们限制了搜索范围和计算负担,但过于严格的提前停止条件可能使模型错过有用的结构。某种交互作用可能只有在一次初始收益并不大的分裂之后才会显现。经典的异或模式就说明了这一问题:尽管一棵两层树能够完美区分类别,但单独使用任一个预测变量进行分裂,都可能无法降低不纯度。

代价复杂度剪枝与树规模选择

一棵不断生长的树可能会拟合训练样本中的偶然细节。其叶节点所含的样本越来越少,规则越来越具体,训练误差通常也越来越低。但这并不保证它对新观测的泛化能力有所提高。经典 CART 通过代价复杂度剪枝来应对这种过拟合:从一棵足够大的树开始,考察将分支替换为叶节点后得到的更简单的子树。

带惩罚项的目标函数为

Rα(T)=R(T)+α∣T~∣,R_\alpha(T)=R(T)+\alpha|\widetilde T|,

其中,R(T)R(T) 是树的经验风险,∣T~∣|\widetilde T| 是其叶节点数,α≥0\alpha\geq0 是每个叶节点对应的惩罚。对于回归,风险可以基于平方误差定义。对于分类,即使树在生长时使用的是基尼不纯度,风险也可以基于误分类代价定义。α\alpha 越大,就越倾向于选择较小的树。其数值尺度取决于风险是以总和、平均值还是其他归一化形式表示。

这种高效的剪枝过程称为最弱环节剪枝。令 TtT_t 表示以内部节点 tt 为根的分支,R(t)R(t) 表示将整个分支替换为单个叶节点后的风险。其有效剪枝值为

g(t)=R(t)−R(Tt)∣T~t∣−1.g(t) = \frac{R(t)-R(T_t)} {|\widetilde T_t|-1}.

它表示每移除一个叶节点所带来的经验风险增量。首先剪去有效剪枝值最小的一个或多个分支,然后重新计算这些值。反复执行这一过程,会得到一个嵌套的子树序列,最终得到仅含根节点的树。妥善处理有效剪枝值并列的情况,可使所得子树序列保持代价复杂度准则下的最优性。

从这些子树中进行选择,不能只看它们对训练数据的拟合情况,还需要其他证据。交叉验证通过反复在部分数据上拟合模型,并在留出的观测上进行评估,来估计预测误差。可以选择使估计误差最小的复杂度。另一种常用方法是一个标准误差规则:选择估计误差不超过最小估计误差加上一个估计标准误差的最小树。这是一种偏向简单模型的模型选择惯例,并不保证较小的树与较大的树在统计意义上等效。

有效的交叉验证要求在每一折的训练部分内重新构建树。在全部观测上只生长一次树,再用同一批观测评估其各个剪枝版本,并不能模拟学习过程在未见数据上的表现。需要估计最终性能时,可以使用独立的测试集或嵌套交叉验证,将模型选择与评估分开。因此,代价复杂度剪枝既是一种生成候选子树的计算过程,也是一种正则化方式,其强度必须独立于最终性能评估来选择。

缺失值、类别编码与错误代价

经典 CART 通过替代分裂提供了一套明确的预测变量缺失值处理方法。选定主分裂后,算法会在其他预测变量中寻找能够复现主分裂左右分配结果的判定条件。这些备选分裂根据其与主划分的一致程度排序,一致程度则使用相关变量值均可用的观测来计算。替代分裂旨在模仿主分裂的分支选择,而不只是找出对响应变量具有次优独立预测能力的变量。

在预测时,如果某个观测的主预测变量值缺失,就可以使用排名最高且可用的替代分裂来决定其进入哪个分支。如果该替代分裂所需的值也不可用,则可以尝试另一个。如果没有可用的替代分裂,具体实现就需要采用兜底规则,例如将观测分配到指定的子节点。一致度的调整方式和兜底行为的细节十分重要,尤其是在主分裂高度不平衡时:始终选择较大子节点的替代分裂,即便提供的信息很少,也可能具有很高的原始一致度。

不应将这种历史上形成的机制与如今的所有缺失值处理策略混为一谈。有些树模型系统会在搜索分裂时,直接学习缺失值默认进入的子节点。另一些系统则要求在训练前进行缺失值填补,或者只在特定准则和配置下支持缺失值。缺失本身也可能包含预测信息,例如,某项测量是否被采集,可能反映了某种业务流程。当采集流程发生变化时,这种关系也可能改变,从而产生分布偏移,即使底层物理关系仍然稳定。

类别变量的表示方式也会影响能够学得的树。原生的子集分裂可以在一次判定中将多个类别取值归为一组。采用独热编码时,每个指示变量只判断观测是否属于某一个类别;要表达更大的类别分组,可能需要多次分裂。将类别任意编码为整数会人为引入顺序,并允许依据这一顺序进行阈值划分。对于确实有序的类别,这类划分是合适的,但它未必能反映无序类别的结构。大量稀有类别取值也可能促使模型形成高度依赖特定样本的划分。

错误代价不等与类别不平衡还引出了另一个区别:类别出现的频率并不等同于误判所造成的后果。如果 C(k,a)C(k,a) 表示真实类别为 kk 时预测为类别 aa 的代价,那么叶节点中使期望代价最小的决策为

a^=arg⁡min⁡a∑kC(k,a)p^k.\hat a=\arg\min_a\sum_k C(k,a)\hat p_k.

这一决策不一定是选择多数类。先验概率、类别权重、采样方式和决策代价可能以不同方式影响分裂和分类。重新加权训练样本可能提高模型对稀有类别的敏感度,但也可能使叶节点中未经调整的类别比例不再适合用于估计部署所面向总体中的类别占比。

统计特性、不稳定性与解释

规模较小的 CART 树所能表达的预测函数相对有限,而规模很大的树则能刻画复杂的局部模式。这就带来了近似误差与抽样变异之间的权衡。浅树可能遗漏重要结构,而深树可能仅凭寥寥几个观测值就做出预测。由于每次分裂都会划分现有样本,支撑后续决策的证据量可能随树深度的增加而迅速减少。

不稳定性是 CART 最广为人知的特征之一。根节点的两个候选分裂可能带来几乎相同的不纯度降幅,却产生截然不同的后续分支。训练样本的微小变化就可能颠倒二者的排序,进而改变最终树的大部分结构。预测变量之间的相关性会放大这一效应,因为多个变量可能给出几乎可以相互替代的划分。因此,不同的拟合结构可能得到相近的预测结果,而某个变量未出现在一棵树中,并不能证明它不含有用信息。

结构紧凑的树最具可解释性。从根节点到叶节点的路径可以转化为一组必须同时满足的条件,每个叶节点还可以附上其样本量、预测值和类别构成。这使树模型在可解释人工智能中颇有用处,但这种解释仍然是预测性的,而非因果性的。所选阈值同样是依赖样本的估计值。在 17.4 个单位处进行分裂,并不一定意味着底层系统恰好在该数值处存在真正的不连续性。

基于不纯度的特征重要性,是将整棵树中归于各预测变量的加权不纯度降幅分别求和。它描述了拟合模型如何使用各个变量,却不是衡量科学意义的无偏指标。拥有较多候选切分点的预测变量,有更多机会偶然产生有利的分裂。高度相关的预测变量之间的重要性分配可能不均:先被选中的变量获得的贡献归属,本来也可能由另一个变量提供。基于置换的评估回答的是另一个问题——当某个变量所含的信息被打乱时,预测性能会如何变化——但这类评估同样会受到预测变量之间依赖关系的影响。

CART 还具有一些特有的几何局限。轴对齐分裂通过阶梯状区域来近似斜向边界或平滑的加性函数,因此可能需要大量叶节点。普通回归树无法将持续变化的趋势外推到预测变量的观测范围之外:它们只会返回某个叶节点的常数预测值。当叶节点采用标准的非负权重加权均值时,预测值始终位于训练样本响应值的范围内。另一方面,除数值计算细节外,对数值型预测变量施加严格单调递增变换,会保留其排序以及训练样本中可形成的划分。因此,标准 CART 通常不需要特征缩放,不过变量变换和编码方式仍可能影响具体实现的行为。

评估、实际应用与软件

CART 常用于结构化的表格数据,其中每个观测由数值变量和类别变量描述。应用实例包括预测设备故障、估算房产价值、对制造零件进行分类,以及分析生态栖息地的分布模式。规模适中的树能够揭示一些在整体线性模型中难以看出的操作阈值和条件组合。这些应用的成效取决于观测是否具有代表性,以及所记录的变量是否合适,而不只是树对这些数据的拟合能力。

评估方式必须与预测任务相匹配。对于分类任务,准确率衡量的是标签预测正确的比例,但它可能掩盖模型在少数类别上的不佳表现。各类别的错误率、精确率与召回率,以及混淆矩阵,能够提供不同方面的信息。当模型输出用作概率时,对数损失或布里尔分数等指标不仅评估最终标签,还能评估概率预测的质量。回归评估通常使用均方误差、均方根误差或平均绝对误差;这些指标对较大残差施加的惩罚不同,因此可能倾向于不同规模的模型。

数据的结构决定了怎样的留出验证才是有效的。当多条记录描述的是同一台机器、同一位客户、同一个地点,或同一个随时间变化的过程时,随机划分记录可能产生误导。按组划分可以评估模型向未见过的组迁移的能力,而按时间顺序划分则用于评估对后续时段的预测。当预测时无法获得的信息进入训练或模型选择过程时,就会发生数据泄漏(机器学习)。树可能在靠近根节点的位置选用一个预测能力强得可疑的字段,从而使这类泄漏格外显眼,但结构易于理解并不能防止这一问题。

叶节点的概率估计需要单独审视。一个终端节点中,若十个观测有九个为正例,其经验正例比例就是 0.90.9,但这一估计所依据的证据很少,而且对应区域也是利用同一批数据选出来的。小叶节点可能产生接近零或一的概率,而这些概率在对概率误差敏感的损失函数下可能表现不佳。提高叶节点的最小样本数要求、平滑、剪枝,以及利用外部数据评估概率,分别针对这一问题的不同方面。不能仅凭训练集上的叶节点看起来很纯,就推断模型在样本外也可靠。

广泛使用的实现包括 R 中的 rpart 包,以及 scikit-learn 中的决策树估计器。它们的接口提供了对深度、叶节点大小、分裂准则和剪枝的控制,但所支持的数据类型和缺失值处理机制有所不同。可复现性还取决于并列结果的处理规则、适用时使用的随机种子、数值精度以及库版本。仅保存一张树形图,并不一定就完整记录了模型:类别编码、预处理步骤、对未见类别的处理方式,以及分支比较规则,也都是预测流程的一部分。

CART 作为集成方法的基础

单棵树的局限推动了将多棵树组合起来的方法的发展。树是很有吸引力的基学习器,因为它们能够拟合非线性结构,对数值预处理的要求相对较低,而且可以通过改变训练时可用的观测样本或预测变量来产生不同的树。当聚合能够平抑特定样本引起的波动时,树的不稳定性反而变得有用。尽管每个组成模型仍保留着相同的基本分裂与叶节点结构,最终模型却不再是一个可直接解读的单一决策层次结构。

布雷曼于 1996 年提出的自助聚合,使用从训练数据中有放回抽取的自助样本来拟合模型。对于回归任务,对各模型的预测取平均;对于分类任务,则汇总投票结果或估计概率。深树对抽样数据的变化尤为敏感,因此对它们的预测取平均可以显著降低方差。收益大小取决于各模型误差之间的相关程度:反复拟合几乎相同的树,几乎无法增加独立信息。

布雷曼于 2001 年提出的随机森林方法,在树的生长过程中加入了随机选择预测变量的步骤。在每个节点,只考虑从预测变量中随机选出的一个子集来寻找分裂。这降低了某个预测能力很强的变量主导每棵树的可能性,也能降低所得模型之间的相关性。随机森林通常使用未经剪枝的深树,而不是独立使用 CART 时常见的、经过单独优化和剪枝的树。因此,其准确性来自许多不同学习器的组合,而非选出一棵最理想的解释性树。

弗里德曼于 2001 年为梯度提升建立了影响深远的统计学表述;这种方法按顺序组合多棵树。每棵新树都针对当前集成模型尚未拟合好的那部分损失。对于平方误差回归,这可以理解为拟合残差;对于更一般的可微损失,则涉及负梯度或相关的优化量。树的深度控制交互作用的复杂程度,而迭代轮数和收缩率则调节整体模型。这些树是加性函数的组成部分,而不是各自独立、完整的预测模型。

XGBoost、LightGBM 和 CatBoost 等现代系统,采用不同的优化、正则化、类别特征处理及计算技术,扩展了提升树学习。它们的节点目标函数可以使用梯度和二阶信息,而不是普通 CART 的不纯度公式,因此并非只是反复执行原始 CART 的完整流程。尽管如此,它们仍保留了 CART 的核心表示思想:通过递归划分,将异质的预测变量空间转化为局部简单的预测区域。用一棵紧凑的解释性树替代这样的集成模型,可以使其行为更易于审视,但这棵紧凑的树只是一种近似,并不一定能保持集成模型的预测结果。