Minimization of Gini Impurity: NP-completeness and Approximation Algorithm via Connections with the k-means Problem

摘要

The Gini impurity is a very popular criterion to select attributes during decision trees construction. In the problem of finding a partition with minimum weighted Gini impurity (PMWGP), the one faced during the construction of decision trees, a set of vectors must be partitioned intokdifferent clusters such that the partition's overall Gini impurity is minimized.We show thatPMWGPis APX-hard for arbitrarykand admits a randomized PTAS when the number of clusters is fixed. These results significantly improve the current knowledge on the problem. The key idea to obtain these results is to explore connections betweenPMWGPand the geometrick-means clustering problem.