Fast Spectral Clustering via the Nystr?m Method

详细信息    查看全文

• 作者：Anna Choromanska ; Tony Jebara ; Hyungtae Kim ; Mahesh Mohan ; Claire Monteleoni
• 关键词：spectral clustering ; Nystr?m method ; large ; scale clustering ; sampling ; sparsity ; performance guarantees ; error bounds ; unsupervised learning
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8139
• 期：1
• 页码：382-396
• 全文大小：375KB
• 参考文献：1. Belkin, M., Niyogi, P.: Convergence of Laplacian eigenmaps. In: NIPS 2006, pp. 129-36. MIT Press (2007)
  2. Drineas, P., Mahoney, M.W.: On the Nystr?m Method for Approximating a Gram Matrix for Improved Kernel-Based Learning. Journal of Machine Learning Research 6, 2005 (2005)
  3. Fowlkes, C., Belongie, S., Chung, F., Malik, J.: Spectral grouping using the nystr?m method. IEEE Trans. Pattern Anal. Mach. Intell.?26(2), 214-25 (2004) CrossRef
  4. Fung, W.S., Hariharan, R., Harvey, N.J., Panigrahi, D.: A general framework for graph sparsification. In: STOC (2011)
  5. Kannan, R., Vempala, S.: Spectral algorithms. Foundations and Trends in Theoretical Computer Science?4(3-4), 157-88 (2009)
  6. Kumar, S., Mohri, M., Talwalkar, A.: Sampling techniques for the nystr?m method. Journal of Machine Learning Research?5, 304-11 (2009)
  7. Lashkari, D., Golland, P.: Convex clustering with exemplar-based models. In: NIPS 2007 (2007)
  8. Li, M., Lian, X.-C., Kwok, J.T., Lu, B.-L.: Time and space efficient spectral clustering via column sampling. In: 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, pp. 2297-304. IEEE (2011)
  9. Lloyd, S.P.: Least squares quantization in pcm. IEEE Transactions on Information Theory?28, 129-37 (1982) CrossRef
  10. Luxburg, U.: A tutorial on spectral clustering. Statistics and Computing?17(4), 395-16 (2007) CrossRef
  11. Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: NIPS 2001, pp. 849-56. MIT Press (2001)
  12. Spielman, D.A., Teng, S.-H.: Spectral sparsification of graphs. SIAM Journal on Computing?40(4), 981-025 (2011) CrossRef
  13. Williams, C., Seeger, M.: Using the Nystr?m method to speed up kernel machines. In: NIPS 2000, pp. 682-88. MIT Press (2001)
  14. Yan, D., Huang, L., Jordan, M.I.: Fast approximate spectral clustering. In: ACM SIGKDD, pp. 907-16. ACM (2009)
  
• 作者单位：Anna Choromanska (22)
  Tony Jebara (23)
  Hyungtae Kim (23)
  Mahesh Mohan (24)
  Claire Monteleoni (24)
  
  22. Department of Electrical Engineering, Columbia University, CEPSR 624, 1214 Amsterdam Avenue, 10027, NY, USA
  23. Department of Computer Science, Columbia University, NY, USA
  24. Department of Computer Science, George Washington University, NY, USA
  
• ISSN：1611-3349

文摘

We propose and analyze a fast spectral clustering algorithm with computational complexity linear in the number of data points that is directly applicable to large-scale datasets. The algorithm combines two powerful techniques in machine learning: spectral clustering algorithms and Nystr?m methods commonly used to obtain good quality low rank approximations of large matrices. The proposed algorithm applies the Nystr?m approximation to the graph Laplacian to perform clustering. We provide theoretical analysis of the performance of the algorithm and show the error bound it achieves and we discuss the conditions under which the algorithm performance is comparable to spectral clustering with the original graph Laplacian. We also present empirical results.