Information Theoretical Clustering Is Hard to Approximate

• Published in: IEEE transactions on information theory 2021-01, Vol.67 (1), p.586-597
• Main Authors: Cicalese, Ferdinando, Laber, Eduardo Sany
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Approximation algorithms; channel quantization; Clustering; Clustering algorithms; computational complexity; Current measurement; Divergence; Entropy; Impurities; impurity measures; Mathematical analysis; Mutual information; mutual information maximization; Polynomials; Quality assessment; Quantization (signal); Signal processing
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2020.3031629

An impurity measures I: \mathbb {R}^{d} \mapsto \mathbb {R}^{+} is a function that assigns a d -dimensional vector \mathbf {v} to a non-negative value I(\mathbf {v}) so that the more homogeneous \mathbf {v} , with respect to the values of its coordinates, the larger its impurity. A well known example of impurity measures is the entropy impurity. We study the problem of clustering based on the entropy impurity measures. Let V be a collection of n many d -dimensional vectors with non-negative components. Given V and an impurity measure I , the goal is to find a partition {\mathcal{ P}} of V into k groups V_{1},\ldots,V_{k} so as to minimize the sum of the impurities of the groups in {\mathcal{ P}} , i.e., I({\mathcal{ P}})= \sum _{i=1}^{k} I\left({\sum _{ \mathbf {v}\in V_{i}} \mathbf {v}}\right) . Impurity minimization has been widely used as quality assessment measure in probability distribution clustering (KL-divergence) as well as in categorical clustering. However, in contrast to the case of metric based clustering, the current knowledge of impurity measure based clustering in terms of approximation and inapproximability results is very limited. Here, we contribute to change this scenario by proving that the problem of finding a clustering that minimizes the Entropy impurity measure is APX-hard, i.e., there exists