提出首个适用于所有p≥1的可解释k-中位数聚类动态算法。
Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
- 基于阈值决策树构造可解释聚类，通过p范数优化目标。
- 实现O(p(log k)^{1+1/p−1/p²})近似比，覆盖所有有限p值。
- 支持动态数据更新，适合大规模演化数据场景。
我们研究了Dasgupta等人（2020）提出的可解释k-中位数聚类问题。该问题旨在构建一个阈值决策树，将数据划分为k个簇，同时最小化k-中位数目标函数。这类树具有可解释性，因为每个内部节点仅基于单个特征进行阈值判断，使用户能够追踪并理解每个点的聚类归属。本文首次提出适用于任意有限p≥1的lp范数下的可解释k-中位数聚类算法，其对最优k-中位数代价的近似比为O(p(log k)^{1 + 1/p - 1/p^2})。此前算法仅适用于p=1和p=2。对于p=2，本算法优于现有O(log^{3/2}k)的界；对于p=1，近似比达到log k + O(1)的紧界，仅差一个O(log log k)乘法因子。此外，我们展示了如何在动态环境中实现该算法：在一系列插入与删除操作下维护可解释聚类，均摊更新时间为O(d log³k)， recourse为O(log k)，适用于大规模与动态数据集。
原文摘要 · Abstract (English)
We study the problem of explainable k-medians clustering introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020). In this problem, the goal is to construct a threshold decision tree that partitions data into k clusters while minimizing the k-medians objective. These trees are interpretable because each internal node makes a simple decision by thresholding a single feature, allowing users to trace and understand how each point is assigned to a cluster. We present the first algorithm for explainable k-medians under lp norm for every finite p >= 1. Our algorithm achieves an O(p(log k)^{1 + 1/p - 1/p^2}) approximation to the optimal k-medians cost for any p >= 1. Previously, algorithms were known only for p = 1 and p = 2. For p = 2, our algorithm improves upon the existing bound of O(log^{3/2}k), and for p = 1, it matches the tight bound of log k + O(1) up to a multiplicative O(log log k) factor. We show how to implement our algorithm in a dynamic setting. The dynamic algorithm maintains an explainable clustering under a sequence of insertions and deletions, with amortized update time O(d log^3 k) and O(log k) recourse, making it suitable for large-scale and evolving datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。