TY - JOUR
T1 - Fast adaptively balanced min-cut clustering
AU - Nie, Feiping
AU - Xie, Fangyuan
AU - Wang, Jingyu
AU - Li, Xuelong
N1 - Publisher Copyright:
© 2024 Elsevier Ltd
PY - 2025/2
Y1 - 2025/2
N2 - Min-cut clustering is a typical graph clustering method, which has been extensively applied for pattern recognition, data analysis and image processing. However, min-cut has trivial solutions, which leads to skewed clustering performance. Spectral clustering (SC) alleviates this by relaxing indicator matrix into continuous embedding and then discretizes the embedding. However, there are two primary challenges in SC, which are high computational complexity and two-stage process. To resolve these issues, a fast adaptively balanced min-cut clustering model (FBMC) is proposed, which directly solves the discrete indicator matrix without any post-processing. We utilize the bipartite graph to accelerate the construction of affinity graph and process of optimization. Besides, the balance factors are added in the model, which could alleviate skewed clustering results. Two specific methods are proposed, in which one adds a balance factor to all clusters while the other assigns balance factors to each cluster separately, referred to as FBMC1 and FBMC2. What is more, a one-step optimization is proposed to solve FBMC1 and FBMC2, the complexity of which is linear of time. Finally, comprehensive experiments results highlight the superior performance of our proposed method.
AB - Min-cut clustering is a typical graph clustering method, which has been extensively applied for pattern recognition, data analysis and image processing. However, min-cut has trivial solutions, which leads to skewed clustering performance. Spectral clustering (SC) alleviates this by relaxing indicator matrix into continuous embedding and then discretizes the embedding. However, there are two primary challenges in SC, which are high computational complexity and two-stage process. To resolve these issues, a fast adaptively balanced min-cut clustering model (FBMC) is proposed, which directly solves the discrete indicator matrix without any post-processing. We utilize the bipartite graph to accelerate the construction of affinity graph and process of optimization. Besides, the balance factors are added in the model, which could alleviate skewed clustering results. Two specific methods are proposed, in which one adds a balance factor to all clusters while the other assigns balance factors to each cluster separately, referred to as FBMC1 and FBMC2. What is more, a one-step optimization is proposed to solve FBMC1 and FBMC2, the complexity of which is linear of time. Finally, comprehensive experiments results highlight the superior performance of our proposed method.
KW - Balanced min-cut clustering
KW - Bipartite graph
KW - Coordinate descent method
KW - Fast clustering
UR - http://www.scopus.com/inward/record.url?scp=85205422533&partnerID=8YFLogxK
U2 - 10.1016/j.patcog.2024.111027
DO - 10.1016/j.patcog.2024.111027
M3 - 文章
AN - SCOPUS:85205422533
SN - 0031-3203
VL - 158
JO - Pattern Recognition
JF - Pattern Recognition
M1 - 111027
ER -