Statistical and Computational Trade-Offs in Imbalanced Kernel Clustering
Jing Zhang , Yucong Dai , Hong Tao , Chenping Hou
Imbalanced kernel clustering, distinguished by differing sample counts among diverse clusters,has gained significant prominence in a multitude of real-world nonlinear data mining scenarios. Nevertheless, the computational requirements of such approaches are often associated with the kernel matrix and display a quadratic increase in relation to the data volume, making it unfeasible for scenarios involving large-scale imbalanced datasets. Moreover, despite the importance of theoretical analysis in machine learning, fast imbalanced kernel clustering methods still lack solid statistical guarantees. Understanding the statistical properties of fast imbalanced kernel clustering therefore remains an important and underexplored problem. To solve these problems, we propose a framework of fast Imbalanced Kernel k-Means (IKKM), exploring both computational demands and statistical analysis. According to the theoretical analysis, the proposed fast IKKM can take less time to attain a similar accuracy dimension of approximately Ω() with n denoting the sample count. In particular, we establish the first optimal excess clustering risk bound for the fast IKKM under mild conditions. Comprehensive experiments validate the theoretical analysis of the fast IKKM in addressing the computational challenges of large-scale imbalanced clustering.
Imbalanced data; clustering; excess risk bound; computational trade-off.
Higher Education Press
/
| 〈 |
|
〉 |
PDF
(1655KB)
