Multiclass spectral clustering based on discriminant analysis

Many existing spectral clustering algorithms share a conventional graph partitioning criterion: normalized cuts (NC). However, one problem with NC is that it poorly captures the graph¿s local marginal information which is very important to graph-based clustering. In this paper, we present a discriminant analysis based graph partitioning criterion (DAC), which is designed to effectively capture the graph¿s local marginal information characterized by the intra-class compactness and the inter-class separability. DAC preserves the intrinsic topological structures of the similarity graph on data points by constructing a k-nearest neighboring subgraph for each data point. Consequently, the clustering results generated by the DAC-based clustering algorithm (DACA) are robust to the outlier disturbance. Theoretic analysis and experimental evaluations demonstrate the promise and effectiveness of DACA.