Statistical and computational trade-offs in imbalanced kernel clustering

Abstract

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 of exact IKKM, when operating with a sketching dimension of approximately \mathrm{\Omega }(\sqrt{n}) 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.

Graphical abstract

Keywords

imbalanced data / clustering / excess risk bound / computational trade-off

References

[1] He H, Garcia E A . Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering, 2009, 21( 9): 1263–1284

[2] Yuan X, Xie L, Abouelenien M . A regularized ensemble framework of deep learning for cancer detection from multi-class, imbalanced training data. Pattern Recognition, 2018, 77: 160–172

[3] Yan Y, Tan M, Xu Y, Cao J, Ng M, Min H, Wu Q. Oversampling for imbalanced data via optimal transport. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence. 2019, 5605–5612

[4] Gan D, Shen J, An B, Xu M, Liu N . Integrating TANBN with cost sensitive classification algorithm for imbalanced data in medical diagnosis. Computers & Industrial Engineering, 2020, 140: 106266

[5] Kemelmacher-Shlizerman I, Seitz S M, Miller D, Brossard E. The megaface benchmark: 1 million faces for recognition at scale. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2016, 4873–4882

[6] Huang C, Li Y, Loy C C, Tang X . Deep imbalanced learning for face recognition and attribute prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42( 11): 2781–2794

[7] Oksuz K, Cam B C, Kalkan S, Akbas E . Imbalance problems in object detection: a review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43( 10): 3388–3415

[8] Bader-El-Den M, Teitei E, Perry T . Biased random forest for dealing with the class imbalance problem. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30( 7): 2163–2172

[9] Yin J, Gan C, Zhao K, Lin X, Quan Z, Wang Z J. A novel model for imbalanced data classification. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 6680–6687

[10] Ju W, Mao Z, Yi S, Qin Y, Gu Y, Xiao Z, Shen J, Qiao Z, Zhang M. Cluster-guided contrastive class-imbalanced graph classification. In: Proceedings of the 39th AAAI Conference on Artificial Intelligence. 2025, 11924–11932

[11] Zhong Y F, Ma A L, Zhang L P . An adaptive memetic fuzzy clustering algorithm with spatial information for remote sensing imagery. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2014, 7( 4): 1235–1248

[12] Mei S, Hou J, Chen J, Chau L P, Du Q . Simultaneous spatial and spectral low-rank representation of hyperspectral images for classification. IEEE Transactions on Geoscience and Remote Sensing, 2018, 56( 5): 2872–2886

[13] Maulik U, Saha I . Modified differential evolution based fuzzy clustering for pixel classification in remote sensing imagery. Pattern Recognition, 2009, 42( 9): 2135–2149

[14] Zhao Q, Jia S, Li Y . Hyperspectral remote sensing image classification based on tighter random projection with minimal intra-class variance algorithm. Pattern Recognition, 2021, 111: 107635

[15] Zhang J, Fan R, Tao H, Jiang J, Hou C . Constrained clustering with weak label prior. Frontiers of Computer Science, 2024, 18( 3): 183338

[16] Liang J, Bai L, Dang C, Cao F . The K -means-type algorithms versus imbalanced data distributions. IEEE Transactions on Fuzzy Systems, 2012, 20( 4): 728–745

[17] Yang Y, Jiang J . Hybrid sampling-based clustering ensemble with global and local constitutions. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27( 5): 952–965

[18] Lu Y, Cheung Y M, Tang Y Y . Self-adaptive multiprototype-based competitive learning approach: a k-means-type algorithm for imbalanced data clustering. IEEE Transactions on Cybernetics, 2021, 51( 3): 1598–1612

[19] Zhang J, Tao H, Hou C . Imbalanced clustering with theoretical learning bounds. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 9): 9598–9612

[20] Kojima K I . Proceedings of Berkeley symposium on mathematical statistics and probability. American Journal of Human Genetics, 1969, 21( 4): 407–408

[21] Krishna K, Murty M N . Genetic K-means algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1999, 29( 3): 433–439

[22] Hamerly G, Elkan C. Learning the k in k-means. In: Proceedings of the 17th International Conference on Neural Information Processing Systems. 2003, 281–288

[23] Kwak N . Nonlinear projection trick in kernel methods: an alternative to the kernel trick. IEEE Transactions on Neural Networks and Learning Systems, 2013, 24( 12): 2113–2119

[24] Guan X, Terada Y . Sparse kernel k-means for high-dimensional data. Pattern Recognition, 2023, 144: 109873

[25] Pourkamali-Anaraki F, Becker S, Wakin M B. Randomized clustered Nyström for large-scale kernel machines. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018, 3960−3967

[26] Calandriello D, Rosasco L. Statistical and computational trade-offs in kernel k-means. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, 9379–9389

[27] Wang S, Gittens A, Mahoney M W . Scalable kernel k-means clustering with Nyström approximation: relative-error bounds. The Journal of Machine Learning Research, 2019, 20( 1): 431–479

[28] Liu Y. Refined learning bounds for kernel and approximate k-means. In: Proceedings of the 35th International Conference on Neural Information Processing System. 2021, 6142−6154

[29] Yin R, Liu Y, Wang W, Meng D. Randomized sketches for clustering: fast and optimal kernel k-means. In: Proceedings of the 36th International Conference on Neural Information Processing System. 2022, 6424−6436

[30] Liang W, Tang C, Liu X, Liu Y, Liu J, Zhu E, He K . On the consistency and large-scale extension of multiple kernel clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024, 46( 10): 6935–6947

[31] Dhillon I S, Guan Y, Kulis B. Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2004, 551–556

[32] Wu J. The uniform effect of K-means clustering. In: Wu J, ed. Advances in K-means Clustering: A Data Mining Thinking. Berlin: Springer, 2012, 17–35

[33] Williams C K I, Seeger M W. Using the Nyström method to speed up kernel machines. In: Proceedings of the 14th International Conference on Neural Information Processing Systems. 2000, 661–667

[34] Biau G, Devroye L, Lugosi G . On the performance of clustering in Hilbert spaces. IEEE Transactions on Information Theory, 2008, 54( 2): 781–790

[35] Wang R, Nie F, Wang Z, He F, Li X . Scalable graph-based clustering with nonnegative relaxation for large hyperspectral image. IEEE Transactions on Geoscience and Remote Sensing, 2019, 57( 10): 7352–7364

[36] He F, Nie F, Wang R, Jia W, Zhang F, Li X . Semisupervised band selection with graph optimization for hyperspectral image classification. IEEE Transactions on Geoscience and Remote Sensing, 2021, 59( 12): 10298–10311

[37] Foster D J, Rakhlin A. l∞ vector contraction for rademacher complexity. 2019, arXiv preprint arXiv: 1911.06468

[38] Lei Y, Dogan Ü, Zhou D X, Kloft M . Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 2019, 65( 5): 2995–3021

[39] Bartlett P L, Mendelson S . Rademacher and Gaussian complexities: risk bounds and structural results. Journal of Machine Learning Research, 2002, 3: 463–482

[40] Linder T. Learning-theoretic methods in vector quantization. In: Györfi L, ed. Principles of Nonparametric Learning. Vienna: Springer, 2002, 163–210

Rights & permissions

Higher Education Press