1. Spectral clustering with linear embedding: A discrete clustering method for large-scale data.
- Author
-
Gao, Chenhui, Chen, Wenzhi, Nie, Feiping, Yu, Weizhong, and Wang, Zonghui
- Subjects
- *
TIME complexity , *COMPUTATIONAL complexity , *EIGENVALUES , *FUZZY algorithms - Abstract
In recent decades, spectral clustering has found widespread applications in various real-world scenarios, showcasing its effectiveness. Traditional spectral clustering typically follows a two-step procedure to address the optimization problem. However, this approach may result in substantial information loss and performance decline. Furthermore, the eigenvalue decomposition, a key step in spectral clustering, entails cubic computational complexity. This paper incorporates linear embedding into the objective function of spectral clustering and proposes a direct method to solve the indicator matrix. Moreover, our method achieves a linear time complexity with respect to the input data size. Our method, referred to as Spectral Clustering with Linear Embedding (SCLE), achieves a direct and efficient solution and naturally handles out-of-sample data. SCLE initiates the process with balanced and hierarchical K-means, effectively partitioning the input data into balanced clusters. After generating anchors, we compute a similarity matrix based on the distances between the input data points and the generated anchors. In contrast to the conventional two-step spectral clustering approach, we directly solve the cluster indicator matrix at a linear time complexity. Extensive experiments across multiple datasets underscore the efficiency and effectiveness of our proposed SCLE method. • Addressing spectral clustering time issues with a faster graph construction method. • Eliminating eigendecomposition, our approach saves computational time. • Avoiding intermediate variables, our method prevents information loss in updates. • Our algorithm achieves direct clustering matrix solution in linear time. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF