A New Algorithm for Discriminative Clustering and Its Maximum Entropy Extension

Discriminative clustering DC can effectively integrates subspace selection and clustering into a coherent framework. It performs in the iterative classical Linear Discriminant Analysis LDA dimensionality reduction and clustering processing. DC can effectively cluster the data with high dimension. However, it has complex form and high computational complexity. Recent work shows DC is equivalent to kernel k-means KM with a specific kernel matrix. This new insights provides a chance of simplifying the optimization problem in the original DC algorithm. Based on this equivalence relationship, Discriminative K-means DKM algorithm is proposed. When the number of data points denoted as n is small, DKM is feasible and efficient. However, the construction of kernel matrix needs to compute the inverse of a matrix in DKM, when n is large, which is time consuming. In this paper, we concentratei?źon the efficiency of DC. We present a new framework for DC, namely, Efficient DC EDC, which consists of DKM and the whitening transformation of the regularized total scatter matrix WRTS plus KM clustering WRTS+KM. When m dimensions is small and n far outweighs m, namely, ni?źi?źi?źm, EDC can carry out WRTS+KM on data, which is more efficient than DKM. When n is small and m far outweighs n, namely, mi?źi?źi?źn, EDC can carry out DKM on data, which is more efficient. We also extend EDC to soft case, and propose Efficient Discriminative Maximum Entropy Clustering EDMEC, which is an efficient version of maximum entropy based DC. Extensive experiments on a collection of benchmark data sets are presented to show the effectiveness of the proposed algorithms.