论文标题
一些可解释的聚类问题的计算复杂性
The computational complexity of some explainable clustering problems
论文作者
论文摘要
我们研究了[Dasgupta等，ICML 2020]提出的框架中一些可解释的聚类问题的计算复杂性，其中通过轴对准决策树实现了解释性。我们考虑$ k $ -MEANS，$ K $ -MEDIANS，$ K $ - 中心和间距成本功能。我们证明，前三个很难优化，而后者可以在多项式时间进行优化。
We study the computational complexity of some explainable clustering problems in the framework proposed by [Dasgupta et al., ICML 2020], where explainability is achieved via axis-aligned decision trees. We consider the $k$-means, $k$-medians, $k$-centers and the spacing cost functions. We prove that the first three are hard to optimize while the latter can be optimized in polynomial time.
