arXiv:2601.02735cs.LGcs.DS2026-01被引 1

提出稀疏叶碰撞核,让决策森林相似度计算变快且省内存。

Revisiting Forest Proximities via Sparse Leaf-Incidence Kernels

  • 用稀疏叶碰撞结构统一现有森林相似度方法,核心是叶节点共现
  • 精确计算复杂度近线性,比传统方法快数倍,支持大规模数据
  • 适合需要快速嵌入表示的机器学习任务,如推荐与聚类

决策森林通过树的划分结构生成监督相似性。然而,森林相近度计算通常仍被视为样本数的二次操作,限制了可扩展性,并阻碍其在核方法和表示学习流程中的广泛应用。本文通过一类可分离加权叶碰撞(SWLC)核,提出对叶碰撞森林相近度的统一视角,表明大多数现有相近度仅在权重设计上不同,但共享相同的稀疏叶-出现结构。这带来了明确的叶空间表示,澄清其核解释,并实现相近度矩阵的精确有限样本稀疏分解,避免显式全对比较,将计算降至叶碰撞上的稀疏线性代数。我们在一个内存高效的 Python 库中实现了该框架,并在理论上和实证上证明,在标准森林设置下,精确核计算的时间和内存开销近似线性。基准测试验证了预测的缩放行为,覆盖多种数据集、相近度定义和森林设置,并显示所得稀疏叶空间表示可直接用于快速任务感知嵌入。

原文摘要 · Abstract (English)

Decision forests induce supervised similarities through the partition structure of their trees. Yet forest proximity computation is still often treated as a quadratic operation in the number of samples, which limits scalability and restricts broader use in kernel and representation-learning pipelines. We introduce a unified view of leaf-collision forest proximities through a class of Separable Weighted Leaf-Collision (SWLC) kernels, showing that most existing proximities differ only in their weighting scheme while sharing a common sparse leaf-incidence structure. This yields an explicit leaf-space representation that clarifies their kernel interpretation and leads to an exact finite-sample sparse factorization of the proximity matrix, avoiding an explicit all-pairs comparison and reducing computation to sparse linear algebra over leaf collisions. We implement this framework in a memory-efficient Python library and show, both theoretically and empirically, that exact kernel computation scales near-linearly in time and memory under standard forest regimes. Benchmarks verify the predicted scaling behavior in practice across datasets, proximity definitions, and forest settings, and show that the resulting sparse leaf-space representation can also be used directly for fast task-aware embedding.

决策森林相似度计算稀疏核嵌入表示

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。