Discriminative cluster analysis

Authors:
  • FTFernando De la Torre
    Fernando De la Torre
  • TKTakeo Kanade
    Takeo Kanade

Abstract
Clustering is one of the most widely used sta- tistical tools for data analysis. Among all existing clustering techniques, k-means is a very popular method because of its ease of programming and because it accomplishes a good trade-o between achieved performance and computational complexity. However, k- means is prone to local minima problems, and it does not scale well with high dimensional data sets. A common approach to dealing with high dimensional data is to cluster in the space spanned by the principal components (PC). In this paper, we show the benefits of clustering in a low dimensional discriminative space rather than in the PC space (genera- tive). In particular, we propose a new cluster- ing algorithm called Discriminative Cluster Analysis (DCA). DCA jointly performs di- mensionality reduction and clustering. Sev- eral toy and real examples show the bene- fits of DCA versus traditional PCA+k-means clustering. Additionally, a new matrix for- mulation is suggested and connections with related techniques such as spectral graph methods and linear discriminant analysis are provided.