.png){kind=icon}
.png){kind=icon}
Return
A Nystrom spectral clustering algorithm based on probability incremental sampling
.png){kind=icon}
PRE
AI
DOI：10.1007/s00500-016-2160-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Spectral clustering will map the data points of the original space into a low-dimensional eigen-space to make them linearly separable, so it is able to process the data with complex structures. However, spectral clustering needs to store the entire similarity matrix and requires eigen-decomposition. Both procedures will consume a lot of time and space resources, limiting the application of spectral clustering algorithm in large-scale data environment. To reduce the complexity of spectral clustering algorithm, we may use the Nystrom extension technique to calculate the approximate eigenvectors by sampling a few of data points. This method sacrifices the clustering accuracy in exchange for the improvement of the algorithm efficiency. To select more representative sample points to reflect the distribution of data sets much better, this paper designs a dynamic incremental sampling method used for the Nystrom spectral clustering, in which the data points are sampled according to different probability distributions and we theoretically prove that the increase of sampling times can effectively decrease the sampling error. The feasibility and effectiveness of the proposed algorithm are analyzed by the experiments on UCI machine learning data sets.
Keywords:
Spectral clustering
Eigen-decomposition
Nystrom method
Incremental sampling
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.5
Papers:
1.0W
Citations:
2.1W
Organization
No organization information available