📊 statistics

Partition Tree: Conditional Density Estimation over General Outcome Spaces

本文提出了分区树（Partition Tree），这是一种新颖的非参数框架，通过学习数据自适应的分区以最小化负对数似然来估计一般结果空间上的条件密度，并介绍了其袋装扩展形式分区森林（Partition Forest），该扩展方法在概率预测性能上优于现有的基于树的模型和随机森林方法。

原作者： Felipe Angelim, Alessandro Leite

发布于 2026-05-13

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Felipe Angelim, Alessandro Leite

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试预测天气，但你的目标不仅仅是说“会下雨”或“会放晴”，而是想要描述所有可能性的完整范围。你想知道：“下小雨的概率是多少？下暴雨的概率呢？或者也许是晴雨交加？”

大多数传统的计算机模型（如标准决策树）就像僵化的预报员。它们查看你的数据，将其分割成一个个方框，然后给你一个单一的答案或一个简单的概率（例如，“下雨的概率为 70%"）。如果答案不仅仅是一个单一的数字或一个简单的类别，它们就会感到棘手。

本文介绍了一种名为分区树（Partition Tree）的新工具（及其团队升级版分区森林 Partition Forest），它就像一个超级聪明、灵活的地图绘制者。以下是其工作原理，通过简单的类比来说明：

1. 用“智能地图”代替“单一猜测”

把你的数据想象成一个巨大的房间，里面挤满了人（输入）和他们的情绪（结果）。

旧方法： 标准树会问：“你高吗？”如果是，它就把你放进一个盒子里，并说：“这个盒子里的大多数人情绪都很高涨。”它只给你一个平均情绪。
分区树： 这种新方法不仅仅猜测平均情绪。它在那个盒子里绘制了一张详细的地图。它意识到，在“高个子”群体中，有些人非常快乐，有些人一般，还有些人悲伤。它创建了一张“密度图”，精确显示对于该特定群体，每种情绪出现的可能性有多大。

2. “乐高积木”方法（分段常数）

该论文将模型描述为“分段常数”。想象一下，你正在用乐高积木建造一堵墙。

模型查看你的数据，并建造一堵墙，其中每一块积木代表现实的一个微小、具体的切片。
在每个积木内部，“密度”（结果出现的可能性）是平坦且恒定的，就像乐高积木的顶部一样。
通过以智能、数据驱动的方式将这些积木堆叠在一起，它创造出一个锯齿状但精确的形状，完美地拟合数据，而无需假设形状必须是平滑曲线（如钟形曲线）或直线。

3. 处理“混合”成分

数据科学中最大的头痛问题之一是同时处理不同类型的数据：数值（如年龄或温度）和类别（如“红色”、“蓝色”或“是”、“否”）。

创新之处： 分区树用同一种统一的语言处理这两种类型的数据。它可以根据数值（例如，“年龄是否大于 30？”）或类别（例如，“颜色是否为蓝色？”）来切割数据，并且仍然能为结果构建同样的“情绪地图”。它不需要先将所有内容转换为数字；它可以直接处理你抛给它的任何数据。

4. “最佳优先”构建者

树是如何决定在哪里切割数据的？

想象一下，你是一位厨师，试图整理一堆混合水果。你不会随机切割。你会看着这堆水果并问：“如果我从这里切下去，我得到的两堆水果是否会比我开始时的这堆杂乱无章的水果更加均匀？”
该算法使用一种“贪婪”策略（它在每一步都做出最佳的局部选择）。它不断寻找能最大程度减少“惊喜”（数学上称为负对数似然）的切割点。它持续将数据切割成越来越小、越来越精确的方框，直到地图变得准确。

5. “森林”（自助法）

就像单棵树有时会有点摇晃一样，作者创建了分区森林。

这就像让 100 位不同的厨师为同一堆水果绘制各自的地图。
你不是挑选“最好”的那张地图，而是取这 100 张地图并将它们平均化。
结果： 这片“森林”要稳定和可靠得多。在论文的实验中发现，在预测概率方面，这片森林始终优于标准的“随机森林”（这是此类问题的行业标准），尤其是在数据混乱或嘈杂的情况下。

6. 实验结果表明了什么

作者在各种真实世界的数据集上测试了这个新工具（例如预测房价、诊断疾病或分类电子邮件）。

准确性： 在预测可能性的完整范围（概率预测）方面，它比旧的标准树更好。
速度： 它出奇地快，通常比其他试图做同样事情的高级方法训练得更快。
鲁棒性： 即使数据中存在“噪声”（随机误差）或冗余特征（无用信息），分区树也能很好地站稳脚跟。

总结

这篇论文提出了一种构建决策树的新方法，它不仅仅给你一个单一的答案。相反，它为任何类型的结果构建了一张详细的概率地图，无论结果是数字、类别，还是两者的混合。这就像是从只说“下雨”的气象员，升级为一位能递给你 3D 模型的气象员，该模型精确显示水坑将在哪里形成、会有多深，以及它们发生的可能性有多大。

技术摘要：分区树：一般结果空间上的条件密度估计

问题陈述

决策树因其可解释性和在点预测（分类与回归）中的高效性而广受重视。然而，将基于树的方法扩展到一般结果空间上的条件密度估计（同时支持连续变量和分类变量）仍然具有挑战性。现有方法面临特定的局限性：

参数假设：像 CADET 这样的方法在叶节点采用参数化条件密度，可能无法捕捉复杂的非高斯分布。
可扩展性：像 CDTree 这样的方法联合优化分裂和叶节点直方图，计算需求量大，限制了其在大型数据集上的应用。
统一公式：缺乏一个统一的框架，在不施加目标分布参数约束的情况下，将分类和回归视为条件密度估计的特例。

方法论

1. 理论框架：测度论公式

作者提出了分区树（Partition Tree），这是一个基于测度论的框架。

联合空间划分：与传统仅划分协变量空间 $X$ 的树不同，分区树构建了协变量 - 结果联合空间 $Z = X \times Y$ 的数据自适应划分 $\pi_N$ 。
分段常数估计：条件密度 $f(y|x)$ 被建模为定义在这些划分上的分段常数函数。
Radon–Nikodym 导数：该方法通过相对于乘积测度 $\nu = P_X \otimes \mu_Y$ 的 Radon–Nikodym 导数来定义条件密度，其中 $\mu_Y$ 是参考测度（离散结果为计数测度，连续结果为勒贝格测度）。
估计量：对于划分中的单元格 $A = A_X \times A_Y$ ，密度估计为：
$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$
其中 $n_{XY}$ 和 $n_X$ 是经验计数。该公式自然地处理了混合类型结果，并允许分类和回归作为特例出现。

2. 树构建算法

该树使用贪婪、最佳优先策略进行生长，直接最小化条件负对数似然。

目标：分裂准则最大化对数损失的经验增益：
$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$
分裂类型：
- 协变量分裂（ $X$ ）：细化协变量空间（标准树分裂）。
- 结果分裂（ $Y$ ）：在固定的协变量区域内细化结果箱。这允许树自适应地构建结果分布的直方图。
效率：该算法利用高效的排序和前缀和技术在 $O(d_Z N \log N)$ 时间内评估候选分裂（对于平衡树为 $O(d_Z N \log^2 N)$ ），与标准 CART 的可扩展性相匹配。
截断：对于无界连续结果，该方法采用数据依赖的截断（最小 - 最大框）以确保有限测度，并有理论保证该截断渐近地捕获所有概率质量。

3. 分区森林

为了提高稳定性和预测性能，作者引入了分区森林（Partition Forest），这是一种集成方法。它通过对多个在自助法样本（Bagging）上训练的分区树的条件密度估计进行平均，并可选择性地结合随机特征子采样。

4. 理论保证

该论文建立了估计量 $L^1(\nu)$ -一致性的充分条件。如果划分序列满足以下条件，则一致性得到保证：

单元格数量相对于 $N$ 呈次线性增长。
划分族的生长函数满足特定的 VC 维界限。
单元格的直径收缩至零。
不同协变量投影的数量相对于 $\sqrt{\log N / N}$ 增长得足够慢。

主要贡献

统一框架：一个单一的、非参数的条件密度估计框架，无需参数假设即可处理连续、分类和混合类型结果。
直接优化：一种通过贪婪最佳优先搜索直接优化条件对数损失的树构建算法，避免了先前工作中联合分裂 - 直方图优化的计算瓶颈。
可扩展性：一种计算复杂度与标准 CART 相当的实现，使其适用于大型数据集。
集成扩展：引入了分区森林，证明了其比单棵树具有更优的概率预测能力。
理论分析：在标准复杂度和收缩假设下，对提出的估计量进行了严格的收敛性证明。

实验结果

作者在一系列分类和回归基准测试上评估了分区树和分区森林，并将其与 CART、随机森林、CADET 和 CDTree 进行了比较。

分类：
- 单棵树：在大多数数据集（9 个中的 8 个）上，分区树在对数损失方面优于 CART。
- 集成：分区森林在大多数数据集上实现了比随机森林更低的对数损失，证明了其优越的概率校准能力。
回归：
- 单棵树：分区树提供了具有竞争力的点预测和强大的概率性能。值得注意的是，它在大型数据集（如 Air、Power、California、Protein）上优于参数化 CADET，表明其具有更好的可扩展性和对样本大小的适应性。
- 集成：在大多数回归基准测试（10 个中的 8 个）上，分区森林在对数损失方面始终优于随机森林。
鲁棒性：
- 噪声：该方法对同方差和异方差噪声均表现出鲁棒性，性能下降程度与 CDTree 相当，且比 CADET 具有更好的稳定性。
- 冗余特征：虽然 CDTree 在对抗相关特征重复方面显示出稍好的稳定性，但与 CADET 相比，分区树在特征破坏下产生了更一致的预测（更低的方差）。
效率：在 Physicochemical Protein 数据集上的运行时间比较显示，在 $N=10,000$ 时，分区树的速度比 CADET 快约 5 倍，比 CDTree 快 25 倍。

意义与主张

该论文声称，分区树为现有的概率树方法提供了一种可扩展、非参数的替代方案。其主要意义在于：

灵活性：能够在不假设特定参数形式（例如高斯分布）的情况下，对一般结果空间上的复杂条件分布进行建模。
可解释性：保留了决策树的内在可解释性（通过基于增益的特征重要性和分段常数密度可视化），同时提供完整的概率输出。
性能：通过实证证明，非参数、基于密度的树集成可以优于传统的点预测集成（随机森林）和基于密度的参数树（CADET），特别是在数据集规模增加时。

作者将分区树定位为因果推断流程及其他需要灵活条件密度估计的应用中的自然候选方案，同时承认未来的工作可以探索提升框架和定制的剪枝策略。