Adaptive power iteration clustering
Power iteration has been applied to compute the eigenvectors of the similarity matrix in spectral clustering tasks. However, these power iteration based clustering methods usually suffer from the following two problems: (1) the power iteration usually converges very slowly; (2) the singular value de...
Saved in:
Main Authors: | , , , , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2022
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/156037 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-156037 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1560372022-03-31T07:25:19Z Adaptive power iteration clustering Liu, Bo Liu, Yong Zhang, Huiyan Xu, Yonghui Tang, Can Tang, Lianggui Qin, Huafeng Miao, Chunyan School of Computer Science and Engineering Joint NTU-UBC Research Centre of Excellence in Active Living for the Elderly (LILY) Engineering::Computer science and engineering Spectral Clustering Power Iteration Power iteration has been applied to compute the eigenvectors of the similarity matrix in spectral clustering tasks. However, these power iteration based clustering methods usually suffer from the following two problems: (1) the power iteration usually converges very slowly; (2) the singular value decomposition method adopted to obtain the eigenvectors of the similarity matrix is time-consuming. To solve these problems, we propose a novel clustering method named Adaptive Power Iteration Clustering (AdaPIC). Specifically, AdaPIC employs a sequence of rank-one matrices to approximate the normalized similarity matrix. Then, the first K+1 eigenvectors can be computed in parallel, and the stopping condition of power iteration can be automatically yielded based on the target clustering error. We performed extensive experiments on public datasets to demonstrate the effectiveness of the proposed AdaPIC method, comparing with leading baseline methods. The experimental results indicate that the proposed AdaPIC algorithm has a competitive advantage in running time. The running time taken by spectral clustering baseline methods is usually more than 2.52 times of that taken by AdaPIC. For clustering accuracy, AdaPIC outperforms classic PIC by 97% on average, over all experimental datasets. Moreover, AdaPIC achieves comparable clustering accuracy with other 3 baseline methods, and achieves 6%–15% better clustering accuracy than the remaining 6 state-of-the-art baseline methods. AI Singapore National Research Foundation (NRF) Submitted/Accepted version This research is supported, in part, by National Natural Science Foun- dation of China (61976030), Chongqing Municipal Education Commission- funded projects (KJ130709), and Supply Chain System CTBU Open Fund Project(1456025). This research is also supported, in part, by the National Research Foundation, Prime Minister’s Office, Singapore under its AI Singa- pore Programme (AISG Award No: AISG-GC-2019-003) and under its NRF Investigatorship Programme (NRFI Award No. NRF-NRFI05-2019-0002). 2022-03-31T07:25:19Z 2022-03-31T07:25:19Z 2021 Journal Article Liu, B., Liu, Y., Zhang, H., Xu, Y., Tang, C., Tang, L., Qin, H. & Miao, C. (2021). Adaptive power iteration clustering. Knowledge-Based Systems, 225, 107118-. https://dx.doi.org/10.1016/j.knosys.2021.107118 0950-7051 https://hdl.handle.net/10356/156037 10.1016/j.knosys.2021.107118 2-s2.0-85105285022 225 107118 en AISG-GC-2019-003 NRF-NRFI05-2019-0002 Knowledge-Based Systems © 2021 Elsevier B.V. All rights reserved. This paper was published in Knowledge-Based Systems and is made available with permission of Elsevier B.V. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Engineering::Computer science and engineering Spectral Clustering Power Iteration |
spellingShingle |
Engineering::Computer science and engineering Spectral Clustering Power Iteration Liu, Bo Liu, Yong Zhang, Huiyan Xu, Yonghui Tang, Can Tang, Lianggui Qin, Huafeng Miao, Chunyan Adaptive power iteration clustering |
description |
Power iteration has been applied to compute the eigenvectors of the similarity matrix in spectral clustering tasks. However, these power iteration based clustering methods usually suffer from the following two problems: (1) the power iteration usually converges very slowly; (2) the singular value decomposition method adopted to obtain the eigenvectors of the similarity matrix is time-consuming. To solve these problems, we propose a novel clustering method named Adaptive Power Iteration Clustering (AdaPIC). Specifically, AdaPIC employs a sequence of rank-one matrices to approximate the normalized similarity matrix. Then, the first K+1 eigenvectors can be computed in parallel, and the stopping condition of power iteration can be automatically yielded based on the target clustering error. We performed extensive experiments on public datasets to demonstrate the effectiveness of the proposed AdaPIC method, comparing with leading baseline methods. The experimental results indicate that the proposed AdaPIC algorithm has a competitive advantage in running time. The running time taken by spectral clustering baseline methods is usually more than 2.52 times of that taken by AdaPIC. For clustering accuracy, AdaPIC outperforms classic PIC by 97% on average, over all experimental datasets. Moreover, AdaPIC achieves comparable clustering accuracy with other 3 baseline methods, and achieves 6%–15% better clustering accuracy than the remaining 6 state-of-the-art baseline methods. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Liu, Bo Liu, Yong Zhang, Huiyan Xu, Yonghui Tang, Can Tang, Lianggui Qin, Huafeng Miao, Chunyan |
format |
Article |
author |
Liu, Bo Liu, Yong Zhang, Huiyan Xu, Yonghui Tang, Can Tang, Lianggui Qin, Huafeng Miao, Chunyan |
author_sort |
Liu, Bo |
title |
Adaptive power iteration clustering |
title_short |
Adaptive power iteration clustering |
title_full |
Adaptive power iteration clustering |
title_fullStr |
Adaptive power iteration clustering |
title_full_unstemmed |
Adaptive power iteration clustering |
title_sort |
adaptive power iteration clustering |
publishDate |
2022 |
url |
https://hdl.handle.net/10356/156037 |
_version_ |
1729789521675943936 |