| Spectral clustering based on matrix perturbation theory |
| |
| 作者单位： | TIAN Zheng（Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an 710072, China;National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Science, Beijing 100080, China） ;
LI XiaoBin （Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an 710072, China） ;
JU YanWei（Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an 710072, China） ; |
| |
| 基金项目： | 国家自然科学基金;航空基础科学基金 |
| |
| 摘 要： | This paper exposes some intrinsic characteristics of the spectral clustering method by using the tools from the matrix perturbation theory. We construct a weight ma- trix of a graph and study its eigenvalues and eigenvectors. It shows that the num- ber of clusters is equal to the number of eigenvalues that are larger than 1, and the number of points in each of the clusters can be approximated by the associated eigenvalue. It also shows that the eigenvector of the weight matrix can be used directly to perform clustering; that is, the directional angle between the two-row vectors of the matrix derived from the eigenvectors is a suitable distance measure for clustering. As a result, an unsupervised spectral clustering algorithm based on weight matrix (USCAWM) is developed. The experimental results on a number of artificial and real-world data sets show the correctness of the theoretical analysis.
|
| 收稿时间： | 20 July 2006 |
| 修稿时间： | 29 August 2006 |
Spectral clustering based on matrix perturbation theory |
| |
| Authors: | Tian Zheng Li XiaoBin Ju YanWei |
| |
| Affiliation: | 1. Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an 710072, China;National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Science, Beijing 100080, China
2. Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an 710072, China |
| |
| Abstract: | This paper exposes some intrinsic characteristics of the spectral clustering method by using the tools from the matrix perturbation theory. We construct a weight ma- trix of a graph and study its eigenvalues and eigenvectors. It shows that the num- ber of clusters is equal to the number of eigenvalues that are larger than 1, and the number of points in each of the clusters can be approximated by the associated eigenvalue. It also shows that the eigenvector of the weight matrix can be used directly to perform clustering; that is, the directional angle between the two-row vectors of the matrix derived from the eigenvectors is a suitable distance measure for clustering. As a result, an unsupervised spectral clustering algorithm based on weight matrix (USCAWM) is developed. The experimental results on a number of artificial and real-world data sets show the correctness of the theoretical analysis. |
| |
| Keywords: | spectral clustering weight matrix spectrum of weight matrix number of the clusters unsupervised spectral clustering algorithm based on weight matrix |
| 本文献已被 万方数据 SpringerLink 等数据库收录！ |
|
