Paper Info
Title
Approximation Algorithms for Clustering via Weighted Impurity Measures.
Abstract
An impurity measures $I:{R}^k {R}^+$ maps a $k$-dimensional vector ${bf v}$ to a non-negative value $I({bf v})$ so that the more homogeneous ${bf v}$, the larger its impurity. We study clustering based on impurity measures: given a collection $V$ of $n$ many $k$-dimensional vectors and an impurity measure $I$, the goal is to find a partition ${cal P}$ of $V$ into $L$ groups $V_1,ldots,V_L$ that minimizes the total impurities of the groups ${cal P}$, i.e., $I({cal P})= sum_{m=1}^{L} I(sum_{{bf v} in V_m}{bf v}).$ Impurity minimization is widely used as quality assessment measure probability distribution clustering and categorical clustering where it is not possible to rely on geometric properties of the data set. However, contrast to the case of metric based clustering, the current knowledge of impurity measure based clustering terms of approximation and inapproximability results is very limited. research contributes to fill this gap. We first present a simple linear time algorithm that simultaneously achieves $3$-approximation for the Gini impurity measure and $O(log(sum_{{bf v} in V} | {bf v} |_1))$-approximation for the Entropy impurity measure. Then, for the Entropy impurity measure---where we also show that finding the optimal clustering is strongly NP-hard---we are able to design a polynomial time $O(log^2(min{k,L}))$-approximation algorithm. Our algorithm relies on a nontrivial characterization of a class of clusterings that necessarily includes a partition achieving $O(log^2(min{k,L}))$--approximation of the impurity of the optimal partition. Remarkably, this is the first polynomial time algorithm with approximation guarantee independent of the number of points/vector and not relying on any restriction on the components of the vectors for producing clusterings with minimum entropy.
Year
Venue
Field
2018
arXiv: Data Structures and Algorithms
Discrete mathematics,Impurity,Approximation algorithm,Combinatorics,Categorical variable,Probability distribution,Minification,Partition (number theory),Cluster analysis,Time complexity,Mathematics
DocType
Volume
Citations 
Journal
abs/1807.05241
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Ferdinando Cicalese145048.20
Eduardo Sany Laber222927.12