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...

Full description

Saved in:
Bibliographic Details
Main Authors: Liu, Bo, Liu, Yong, Zhang, Huiyan, Xu, Yonghui, Tang, Can, Tang, Lianggui, Qin, Huafeng, Miao, Chunyan
Other Authors: School of Computer Science and Engineering
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