A Novel and Effective Method to Directly Solve Spectral Clustering

Area of Science:

• Machine Learning
• Data Mining
• Computer Science

Background:

• Spectral clustering is a powerful technique with a well-defined framework and excellent performance.
• Traditional spectral clustering methods suffer from information loss and suboptimal performance due to the relax-and-discretize strategy.
• The similarity matrix in conventional methods may be suboptimal due to data noise and redundancy.

Purpose of the Study:

• To propose a novel algorithm, Direct Spectral Clustering (DSC), that directly optimizes the spectral clustering model.
• To address the limitations of traditional spectral clustering, including information loss and suboptimal similarity matrices.
• To achieve improved clustering performance without post-processing.

Main Methods:

• Developed Direct Spectral Clustering (DSC) to directly optimize the spectral clustering objective.
• Theoretically proved that DSC can be solved by simultaneously learning a weighted discrete indicator matrix and a structured similarity matrix.
• Employed an effective iterative optimization algorithm to solve the proposed DSC method.

Main Results:

• DSC directly obtains final clustering results without post-processing.
• The structured similarity matrix in DSC has connected components equal to the number of clusters.
• Extensive experiments on synthetic and real-world datasets show DSC outperforms state-of-the-art algorithms.

Conclusions:

• Direct Spectral Clustering (DSC) offers a superior alternative to traditional spectral clustering methods.
• The simultaneous learning of indicator and similarity matrices in DSC leads to enhanced clustering accuracy.
• DSC demonstrates significant effectiveness and superiority across diverse datasets.