Timezone: »

New results on information theoretic clustering
Ferdinando Cicalese · Eduardo Laber · Lucas Murtinho

Wed Jun 12 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #165

We study the problem of optimizing the clustering of a set of vectors when the quality of the clustering is measured by the Entropy or the Gini impurity measure. Our results contribute to the state of the art both in terms of best known approximation guarantees and inapproximability bounds: (i) we give the first polynomial time algorithm for Entropy impurity based clustering with approximation guarantee independent of the number of vectors and (ii) we show that the problem of clustering based on entropy impurity does not admit a PTAS. This also implies an inapproximability result in information theoretic clustering for probability distributions closing a problem left open in [Chaudhury and McGregor, COLT08] and [Ackermann et al., ECCC11]. We also report experiments with a new clustering method that was designed on top of the theoretical tools leading to the above results. These experiments suggest a practical applicability for our method, in particular, when the number of clusters is large.

Author Information

Ferdinando Cicalese (University of Verona)
Eduardo Laber (PUC-RIO)
Lucas Murtinho Murtinho (PUC-RJ)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors