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.
翻译:我们研究了[Dasgupta等人,ICML 2020]提议的框架内一些可解释的集群问题的计算复杂性,在该框架中,可解释性是通过轴承决策树实现的。我们考虑了美元汇率、美元中间值、美元中间值、美元中间值和间距成本功能。我们证明前三个很难优化,而后者在多元时间内可以优化。