Full Text:   <812>

Summary:  <162>

CLC number: TP311

On-line Access: 2018-12-14

Received: 2017-04-17

Revision Accepted: 2017-08-15

Crosschecked: 2018-11-27

Cited: 0

Clicked: 1544

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Guoqiang Zhong

http://orcid.org/0000-0002-2952-6642

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2018 Vol.19 No.11 P.1385-1396

http://doi.org/10.1631/FITEE.1700262


An anchor-based spectral clustering method


Author(s):  Qin Zhang, Guo-qiang Zhong, Jun-yu Dong

Affiliation(s):  Department of Computer Science and Technology, Ocean University of China, Qingdao 266100, China; more

Corresponding email(s):   gqzhong@ouc.edu.cn

Key Words:  Clustering, Spectral clustering, Graph Laplacian, Anchors


Qin Zhang, Guo-qiang Zhong, Jun-yu Dong. An anchor-based spectral clustering method[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(11): 1385-1396.

@article{title="An anchor-based spectral clustering method",
author="Qin Zhang, Guo-qiang Zhong, Jun-yu Dong",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="19",
number="11",
pages="1385-1396",
year="2018",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1700262"
}

%0 Journal Article
%T An anchor-based spectral clustering method
%A Qin Zhang
%A Guo-qiang Zhong
%A Jun-yu Dong
%J Frontiers of Information Technology & Electronic Engineering
%V 19
%N 11
%P 1385-1396
%@ 2095-9184
%D 2018
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1700262

TY - JOUR
T1 - An anchor-based spectral clustering method
A1 - Qin Zhang
A1 - Guo-qiang Zhong
A1 - Jun-yu Dong
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 19
IS - 11
SP - 1385
EP - 1396
%@ 2095-9184
Y1 - 2018
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1700262


Abstract: 
Spectral clustering is one of the most popular and important clustering methods in pattern recognition, machine learning, and data mining. However, its high computational complexity limits it in applications involving truly large-scale datasets. For a clustering problem with n samples, it needs to compute the eigenvectors of the graph Laplacian with O(n3) time complexity. To address this problem, we propose a novel method called anchor-based spectral clustering (ASC) by employing anchor points of data. Specifically, m (mn) anchor points are selected from the dataset, which can basically maintain the intrinsic (manifold) structure of the original data. Then a mapping matrix between the original data and the anchors is constructed. More importantly, it is proved that this data-anchor mapping matrix essentially preserves the clustering structure of the data. Based on this mapping matrix, it is easy to approximate the spectral embedding of the original data. The proposed method scales linearly relative to the size of the data but with low degradation of the clustering performance. The proposed method, ASC, is compared to the classical spectral clustering and two state-of-the-art accelerating methods, i.e., power iteration clustering and landmark-based spectral clustering, on 10 real-world applications under three evaluation metrics. Experimental results show that ASC is consistently faster than the classical spectral clustering with comparable clustering performance, and at least comparable with or better than the state-of-the-art methods on both effectiveness and efficiency.

一种基于锚点的谱聚类方法

摘要:谱聚类是模式识别、机器学习和数据挖掘中最流行最重要的聚类方法之一。然而,高计算复杂度妨碍了谱聚类在大规模数据集的应用。对于具有n个样本的聚类问题,谱聚类需O(n3)时间复杂度计算图拉普拉斯矩阵特征向量。为解决该问题,提出一种新的基于锚点谱聚类方法(anchor-based spectral clustering,ASC)。首先,在数据集中选择mmn)个可以基本保持原始数据内在(流形)结构的锚点。然后,构造原始数据与锚点之间的映射矩阵,并证明该映射矩阵能保持数据的聚类结构。基于该映射矩阵,近似得到原始数据谱嵌入。ASC方法复杂度与数据集大小呈线性关系。将该方法与经典谱聚类方法和两种最新谱聚类加速方法,即能量迭代聚类(power iteration clustering,PIC)和基于地标聚类(landmark-based spectral clustering,LSC),在10个真实数据集上比较。实验结果表明,ASC算法比经典谱聚类算法具有更快聚类速度,在效率和有效性上与现有方法相当或优于现有方法。

关键词:聚类;谱聚类;图拉普拉斯;锚点

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Arthur D, Vassilvitskii S, 2007. K-means++: the advantages of careful seeding. 18th Annual ACM-SIAM Symp on Discrete Algorithms, p.1027-1035.

[2]Boutsidis C, Gittens A, Kambadur P, 2015. Spectral clustering via the power method–-provably. 32nd Int Conf on Machine Learning, p.40-48.

[3]Chang XJ, Nie FP, Ma ZG, et al., 2015. A convex formulation for spectral shrunk clustering. 29th AAAI Conf on Artificial Intelligence, p.2532-2538.

[4]Chen WY, Song YQ, Bai HJ, et al., 2011. Parallel spectral clustering in distributed systems. IEEE Trans Patt Anal Mach Intell, 33(3):568-586.

[5]Chen XL, Cai D, 2011. Large scale spectral clustering with landmark-based representation. 25th AAAI Conf on Artificial Intelligence, p.313-318.

[6]Davies DL, Bouldin DW, 1979. A cluster separation measure. IEEE Trans Patt Anal Mach Intell, 1(2):224-227.

[7]Delalleau O, Bengio Y, Le Roux N, 2005. Efficient non-parametric function induction in semi-supervised learning. 10th Int Workshop on Artificial Intelligence and Statistics, p.96-103.

[8]Demvšar J, 2006. Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res, 7:1-30.

[9]Fowlkes C, Belongie S, Chung F, et al., 2004. Spectral grouping using the Nyström method. IEEE Trans Patt Anal Mach Intell, 26(2):214-225.

[10]Jia HJ, Ding SF, Xu XZ, et al., 2014. The latest research progress on spectral clustering. Neur Comput Appl, 24(7-8):1477-1486.

[11]Li HZ, Hu XG, Lin YJ, et al., 2016. A social tag clustering method based on common co-occurrence group similarity. Front Inform Technol Electron Eng, 17(2):122-134.

[12]Li JY, Xia YJ, Shan ZY, et al., 2015. Scalable constrained spectral clustering. IEEE Trans Knowl Data Eng, 27(2):589-593.

[13]Lin F, Cohen WW, 2010. Power iteration clustering. 27th Int Conf on Machine Learning, p.655-662.

[14]Liu JL, Wang C, Danilevsky M, et al., 2013. Large-scale spectral clustering on graphs. 23rd Int Joint Conf on Artificial Intelligence, p.1486-1492.

[15]Liu W, He JF, Chang SF, 2010. Large graph construction for scalable semi-supervised learning. 27th Int Conf on Machine Learning, p.679-686.

[16]Luo MN, Nie FP, Chang XJ, et al., 2017. Adaptive unsupervised feature selection with structure regularization. IEEE Trans Neur Netw Learn Syst, 29(4):944-956.

[17]Mall R, Langone R, Suykens JAK, 2013a. FURS: fast and unique representative subset selection retaining large-scale community structure. Soc Netw Anal Min, 3(4):1075-1095.

[18]Mall R, Langone R, Suykens JAK, 2013b. Kernel spectral clustering for big data networks. Entropy, 15(5):1567-1586.

[19]Mall R, Jumutc V, Langone R, et al., 2014. Representative subsets for big data learning using K-NN graphs. IEEE Int Conf on Big Data, p.37-42.

[20]Ng AY, Jordan MI, Weiss Y, et al., 2002. On spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems, p.849-856.

[21]Shi JB, Malik J, 2000. Normalized cuts and image segmentation. IEEE Trans Patt Anal Mach Intell, 22(8):888-905.

[22]Song YQ, Chen WY, Bai HJ, et al., 2008. Parallel spectral clustering. In: Daelemans W, Goethals B, Morik K (Eds.), Machine Learning and Knowledge Discovery in Databases. Springer Berlin Heidelberg, p.374-389.

[23]Tian F, Gao B, Cui Q, et al., 2014. Learning deep representations for graph clustering. 28th AAAI Conf on Artificial Intelligence, p.1293-1299.

[24]von Luxburg U, 2007. A tutorial on spectral clustering. Stat Comput, 17(4):395-416.

[25]Wang L, Leckie C, Ramamohanarao K, et al., 2009. Approximate spectral clustering. In: Theeramunkong T, Kijsirikul B, Cercone N, et al. (Eds.), Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, p.134-146.

[26]Xia RK, Pan Y, Du L, et al., 2014. Robust multi-view spectral clustering via low-rank and sparse decomposition. 28th AAAI Conf on Artificial Intelligence, p.2149-2155.

[27]Xiang T, Gong SG, 2008. Spectral clustering with eigenvector selection. Patt Recog, 41(3):1012-1029.

[28]Xiao P, Li ZY, Guo S, et al., 2016. A $K$ self-adaptive SDN controller placement for wide area networks. Front Inform Technol Electron Eng, 17(7):620-633.

[29]Yan DH, Huang L, Jordan MI, 2009. Fast approximate spectral clustering. 15th Int Conf on Knowledge Discovery and Data Mining, p.907-916.

[30]Yang Y, Xu D, Nie FP, et al., 2010. Image clustering using local discriminant models and global integration. IEEE Trans Image Process, 19(10):2761-2773.

[31]Yang Y, Shen HT, Nie FP, et al., 2011. Nonnegative spectral clustering with discriminative regularization. 25th AAAI Conf on Artificial Intelligence, p.555-560.

[32]Yang Y, Nie F, Xu D, et al., 2012. A multimedia retrieval framework based on semi-supervised ranking and relevance feedback. IEEE Trans Patt Anal Mach Intell, 34(4):723-742.

[33]Zhang XC, Zong LL, You QZ, et al., 2016. Sampling for Nystrom extension-based spectral clustering: incremental perspective and novel analysis. ACM Trans Knowl Discov Data, 11(1):1-25.

[35]Zhu XJ, Lafferty J, 2005. Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning. 22nd Int Conf on Machine Learning, p.1052-1059.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE