Data clustering based on the modified relaxation Cheeger cut model

• Published in: Computational & applied mathematics 2022-02, Vol.41 (1), Article 61
• Main Authors: Yang, Yu-Fei, Zhou, Haojie, Zhou, Bo
• Format: Article
• Language: English
• Subjects: Algorithms; Applications of Mathematics; Applied physics; Clustering; Computational mathematics; Computational Mathematics and Numerical Analysis; Image processing; Mathematical Applications in Computer Science; Mathematical Applications in the Physical Sciences; Mathematics; Mathematics and Statistics; Numerical methods; Object recognition; Optimization; Pattern analysis; Pattern recognition; Robustness (mathematics); Spectra
• ISSN: 2238-3603; 1807-0302
• DOI: 10.1007/s40314-022-01757-x

Graph-based spectral clustering techniques have been developed rapidly in various applications such as the image processing, the networks analysis and the pattern recognition. The spectral graph technique mainly transforms the original data into the graph partitioning problem and then some fast numerical methods can be employed to solve its relaxed form. This paper proposes a novel graph-based spectral clustering model via modifying the relaxation ratio Cheeger cut (RRCC) model. To be specific, in order to enhance the robustness of the clustering, we propose to replace the ℓ 1 -norm in the denominator by the ℓ 2 -norm for the RRCC model. Since the proposed model is the fractional optimization problem, we transform it the difference convex problem. With this transformation, the alternating direction of method of multipliers can be employed to solve it. Experimental comparisons demonstrate the superior clustering capabilities of our proposed model and algorithm when dealing with several benchmark databases.