caa a22 4500 445871326 CHVBK 20180317145512.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s10618-010-0207-5 doi (NATIONALLICENCE)springer-10.1007/s10618-010-0207-5 Fast density-weighted low-rank approximation spectral clustering [Elektronische Daten] [Fanhua Shang, L. Jiao, Jiarong Shi, Maoguo Gong, R. Shang] While spectral clustering can produce high-quality clusterings on small data sets, computational cost makes it infeasible for large data sets. Affinity Propagation (AP) has a limitation that it is hard to determine the value of parameter ‘preference' which can lead to an optimal clustering solution. These problems limit the scope of application of the two methods. In this paper, we develop a novel fast two-stage spectral clustering framework with local and global consistency. Under this framework, we propose a Fast density-Weighted low-rank Approximation Spectral Clustering (FWASC) algorithm to address the above issues. The proposed algorithm is a high-quality graph partitioning method, and simultaneously considers both the local and global structure information contained in the data sets. Specifically, we first present a new Fast Two-Stage AP (FTSAP) algorithm to coarsen the input sparse graph and produce a small number of final representative exemplars, which is a simple and efficient sampling scheme. Then we present a density-weighted low-rank approximation spectral clustering algorithm to operate those representative exemplars on the global underlying structure of data manifold. Experimental results show that our algorithm outperforms the state-of-the-art spectral clustering and original AP algorithms in terms of speed, memory usage, and quality. The Author(s), 2010 Clustering nationallicence Data mining nationallicence Affinity propagation nationallicence Spectral clustering nationallicence Nyström approximation nationallicence Manifold structure nationallicence Shang Fanhua Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut Jiao L. Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut Shi Jiarong Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut Gong Maoguo Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut Shang R. Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 23/2(2011-09-01), 345-378 1384-5810 23:2<345 2011 23 10618 https://doi.org/10.1007/s10618-010-0207-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10618-010-0207-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Shang Fanhua Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut NATIONALLICENCE 700 1- Jiao L. Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut NATIONALLICENCE 700 1- Shi Jiarong Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut NATIONALLICENCE 700 1- Gong Maoguo Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut NATIONALLICENCE 700 1- Shang R. Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Mailbox 224, No. 2 South TaiBai Road, 710071, Xi'an, People's Republic of China aut NATIONALLICENCE 773 0- Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 23/2(2011-09-01), 345-378 1384-5810 23:2<345 2011 23 10618 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer