Near-optimal Algorithms for Explainable k-Medians and k-Means
Near-optimal Algorithms for Explainable k-Medians and k-Means
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
K. Makarychev;Liren Shan
中科院分区：
文献类型：
--
作者：
K. Makarychev;Liren Shan
我们考虑了Dasgupta，Frost，Moshkovitz和Rashtchian〜（ICML 2020）引入的可解释的$ K $ -Medians和$ k $ -Means的问题。在这个问题中，我们的目标是找到一个阈值决策树，将数据分配到$ k $簇中，并最大程度地减少$ k $ -Medians或$ k $ -MEANS的目标。获得的聚类很容易解释，因为阈值树的每个决策节点都根据单个特征将数据分成两组。我们为此问题提出了一种新算法，即$ \ tilde o（\ log k）$与$ k $ -Medians具有$ \ ell_1 $ norm和$ \ tilde o（k）$竞争$ k $ - $ k $ -means的竞争力。这是Dasgupta等（2020）的$ O（k）$和$ O（k^2）$的先前保证的改进。我们还提供了一种新的算法，该算法是$ o（\ log^{3/2} k）$竞争$ k $ -Medians，带有$ \ ell_2 $ norm。我们的第一个算法几乎是最佳的：Dasgupta等人（2020年）显示了$ \ omega（\ log K）$的下限，$ k $ -Medians；在这项工作中，我们证明了$ k $ -means的$ \ tilde \ omega（k）$的下限。我们还提供$ \ omega（\ log k）$的下限，用于$ k $ -Medians，带有$ \ ell_2 $ norm。
We consider the problem of explainable $k$-medians and $k$-means introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian~(ICML 2020). In this problem, our goal is to find a threshold decision tree that partitions data into $k$ clusters and minimizes the $k$-medians or $k$-means objective. The obtained clustering is easy to interpret because every decision node of a threshold tree splits data based on a single feature into two groups. We propose a new algorithm for this problem which is $\tilde O(\log k)$ competitive with $k$-medians with $\ell_1$ norm and $\tilde O(k)$ competitive with $k$-means. This is an improvement over the previous guarantees of $O(k)$ and $O(k^2)$ by Dasgupta et al (2020). We also provide a new algorithm which is $O(\log^{3/2} k)$ competitive for $k$-medians with $\ell_2$ norm. Our first algorithm is near-optimal: Dasgupta et al (2020) showed a lower bound of $\Omega(\log k)$ for $k$-medians; in this work, we prove a lower bound of $\tilde\Omega(k)$ for $k$-means. We also provide a lower bound of $\Omega(\log k)$ for $k$-medians with $\ell_2$ norm.