Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
biconvex clustering; robust clustering; outlier features and samples; robustness
biconvex clustering; robust clustering; outlier features and samples; robustness
Summary:
Convex clustering formulates the clustering problem as a convex optimization task that encourages similar data points to merge into clusters by minimizing a combination of fitting error and a penalty on differences between cluster centroids. This method has attracted considerable attention due to its capacity to address the challenges associated with local optimal solutions and numerical instability prevalent in traditional nonconvex clustering methods. However, it typically relies on the standard Euclidean metric for measuring distance, which can lead to decreased performance, especially in the presence of outlier features. Additionally, it is not particularly robust against outlier samples. To address these issues, we separate the data into cluster and outlier components, effectively eliminating the outlier features. By incorporating self-paced learning, we develop a model that adaptively selects relevant examples while minimizing interference from outlier instances. This approach enhances robustness by removing outlier features and samples, forming a biconvex clustering framework with strong statistical properties. We propose an efficient, convergent algorithm and establish a finite sample bound for prediction error. Experiments on artificial and benchmarking datasets show improved clustering effectiveness compared to classical convex clustering methods.
References:
[1] Bhatt, R.: Planning relax. UC Irvine Machine Learning Repository. DOI 10.24432/C5T023
[2] Carpineto, C., Romano, G.: Consensus clustering based on a new probabilistic rand index with application to subtopic retrieval. IEEE Trans. Pattern Anal. Machine Intelligence 34 (2012), 2315-2326. DOI 10.1109/TPAMI.2012.80
[3] Cendrowska, J.: Lenses. UC Irvine Machine Learning Repository. DOI 10.24432/C5K88Z
[4] Cerioli, A., Perrotta, D.: Robust clustering around regression lines with high density regions. Adv. Data Anal. Classif. 8 (2014), 5-26. DOI 10.1007/s11634-013-0151-5 | MR 3168677 | Zbl 1474.62217
[5] Chakraborty, S., Xu, J.: Biconvex clustering. J. Comput. Graph. Stat. 32 (2023), 1524-1536. DOI 10.1080/10618600.2023.2197474 | MR 4669266 | Zbl 07792635
[6] Chen, A. I., Ozdaglar, A.: A fast distributed proximal-gradient method. Available at https://arxiv.org/abs/1210.2289 (2012), 10 pages. DOI 10.48550/arXiv.1210.2289
[7] Chen, G. K., Chi, E. C., Ranola, J. M. O., Lange, K.: Convex clustering: An attractive alternative to hierarchical clustering. PLoS Comput. Biol. 11 (2015), Article ID e1004228, 31 pages. DOI 10.1371/journal.pcbi.1004228
[8] Chi, E. C., Lange, K.: Splitting methods for convex clustering. J. Comput. Graph. Stat. 24 (2015), 994-1013. DOI 10.1080/10618600.2014.948181 | Zbl 3432926
[9] Englmeier, K.: The design of self-paced learning for structured learning environments. Procedia Comput. Sci. 256 (2025), 71-77. DOI 10.1016/j.procs.2025.02.097
[10] Ester, M., Kriegel, H.-P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD'96) AAAI Press, Portland (1996), 226-231.
[11] Fisher, R. A.: Iris. UC Irvine Machine Learning Repository. DOI 10.24432/C56C76
[12] García-Escudero, L. A., Mayo-Iscar, A.: Robust clustering based on trimming. Wiley Interdiscip. Rev., WIREs Comput. Stat. 16 (2024), Article ID e1658, 17 pages. DOI 10.1002/wics.1658 | MR 4788899 | Zbl 1548.62007
[13] Gorski, J., Pfeuffer, F., Klamroth, K.: Biconvex sets and optimization with biconvex functions: A survey and extensions. Math. Methods Oper. Res. 66 (2007), 373-407. DOI 10.1007/s00186-007-0161-1 | MR 2357657 | Zbl 1146.90495
[14] Greco, L., Agostinelli, C.: Weighted likelihood mixture modeling and model-based clustering. Stat. Comput. 30 (2020), 255-277. DOI 10.1007/s11222-019-09881-1 | MR 4064621 | Zbl 1436.62255
[15] Hastie, T., Tibshirani, R., Friedman, J.: Boosting and additive trees. The Elements of Statistical Learning Springer Series in Statistics. Springer, Cham (2009), 337-387. DOI 10.1007/978-0-387-84858-7_10 | MR 2722294 | Zbl 1273.62005
[16] Hayes-Roth, B., Hayes-Roth, F.: Hayes-Roth. UC Irvine Machine Learning Repository. DOI 10.24432/C5501T
[17] Hocking, T. D., Joulin, A., Bach, F., Vert, J.-P.: Clusterpath: An algorithm for clustering using convex fusion penalties. Proceedings of the 28th International Conference on Machine Learning (ICML'11) (2011), 745-752.
[18] Jiang, L., Meng, D., Mitamura, T., Hauptmann, A. G.: Easy samples first: Self-paced reranking for zero-example multimedia search. Proceedings of the 22nd ACM international conference on Multimedia (MM'14) MIT Press, Cambridge (2014), 547-556. DOI 10.1145/2647868.2654918
[19] Jiang, L., Meng, D., Zhao, Q., Shan, S., Hauptmann, A. G.: Self-paced curriculum learning. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI'15) AAAI Press, Palo Alto (2015), 2694-2700.
[20] Klochkov, Y., Zhivotovskiy, N.: Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method. Electron. J. Probab. 25 (2020), Article ID 22, 30 pages. DOI 10.1214/20-EJP422 | MR 4073683 | Zbl 1445.60019
[21] Koczkodaj, W.: Somerville happiness survey. UC Irvine Machine Learning Repository. DOI 10.24432/C5PW36
[22] Kumar, M. P., Packer, B., Koller, D.: Self-paced learning for latent variable models. Advances in Neural Information Processing Systems 23 (NIPS 2010) Neural Information Processing Systems Foundation, Montreal (2010), 9 pages.
[23] Li, W., Chen, H., Li, T., Wan, J., Sang, B.: Unsupervised feature selection via self-paced learning and low-redundant regularization. Knowledge-Based Syst. 240 (2022), Article ID 108150, 15 pages. DOI 10.1016/j.knosys.2022.108150
[24] Lindsten, F., Ohlsson, H., Ljung, L.: Clustering using sum-of-norms regularization: With application to particle filter output computation. IEEE Statistical Signal Processing Workshop (SSP) IEEE, Los Alamitos (2011), 201-204. DOI 10.1109/SSP.2011.5967659
[25] Madeira, S. C., Oliveira, A. L.: Biclustering algorithms for biological data analysis: A survey. IEEE/ACM Trans. Comput. Biol. Bioinf. 1 (2004), 24-45. DOI 10.1109/TCBB.2004.2
[26] Meng, D., Zhao, Q., Jiang, L.: A theoretical understanding of self-paced learning. Inf. Sci. 414 (2017), 319-328. DOI 10.1016/j.ins.2017.05.043 | Zbl 1435.68278
[27] Panahi, A., Dubhashi, D., Johansson, F. D., Bhattacharyya, C.: Clustering by sum of norms: Stochastic incremental algorithm, convergence and cluster recovery. Proceedings of the 34th International Conference on Machine Learning MLR Press (2017), 2769-2777.
[28] Pelckmans, K., Brabanter, J. De, Suykens, J. A. K.: Convex clustering shrinkage. Workshop on Statistics and Optimization of Clustering (PASCAL) London (2005), 1-6.
[29] Quan, Z., Chen, S.: Robust convex clustering. Soft. Comput. 24 (2020), 731-744. DOI 10.1007/s00500-019-04471-9
[30] Reynolds, D.: Gaussian mixture models. Encyclopedia of Biometrics Springer, Boston (2009), 659-663. DOI 10.1007/978-0-387-73003-5_196
[31] Shah, S. A., Koltun, V.: Robust continuous clustering. PNAS 114 (2017), 9814-9819. DOI 10.1073/pnas.170077011
[32] Shi, C., Gu, Z., Duan, C., Tian, Q.: Multi-view adaptive semi-supervised feature selection with the self-paced learning. Signal Process. 168 (2020), Article ID 107332, 11 pages. DOI 10.1016/j.sigpro.2019.107332
[33] Sigillito, V., Wing, S., Hutton, L., Baker, K.: Ionosphere. UC Irvine Machine Learning Repository. DOI 10.24432/C5W01B
[34] Sinaga, K. P., Yang, M.-S.: Unsupervised $k$-means clustering algorithm. IEEE Access 8 (2020), 80716-80727. DOI 10.1109/ACCESS.2020.2988796
[35] Sui, X. L., Xu, L., Qian, X., Liu, T.: Convex clustering with metric learning. Pattern Recognition 81 (2018), 575-584. DOI 10.1016/j.patcog.2018.04.019
[36] Sun, D., Toh, K.-C., Yuan, Y.: Convex clustering: Model, theoretical guarantee and efficient algorithm. J. Mach. Learn. Res. 22 (2021), Article ID 9, 32 pages. MR 4253702 | Zbl 1539.68281
[37] Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optimization Theory Appl. 109 (2001), 475-494. DOI 10.1023/A:1017501703105 | MR 1835069 | Zbl 1006.65062
[38] Vega-Pons, S., Ruiz-Shulcloper, J.: A survey of clustering ensemble algorithms. Int. J. Pattern Recognit. Artif. Intell. 25 (2011), 337-372. DOI 10.1142/S0218001411008683 | MR 2934988
[39] Wainwright, M. J.: High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics 48. Cambridge University Press, Cambridge (2019). DOI 10.1017/9781108627771 | MR 3967104 | Zbl 1457.62011
[40] Wang, Q., Gong, P., Chang, S., Huang, T. S., Zhou, J.: Robust convex clustering analysis. 2016 IEEE 16th International Conference on Data Mining (ICDM) (2016), 1263-1268. DOI 10.1109/ICDM.2016.123
[41] Xu, C., Tao, D., Xu, C.: Multi-view self-paced learning for clustering. Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI'15) AAAI Press, Palo Alto (2016), 1263-1268.
[42] Yu, H., Wen, G., Gan, J., Zheng, W., Lei, C.: Self-paced learning for $k$-means clustering algorithm. Pattern Recognit. Lett. 132 (2020), 69-75. DOI 10.1016/j.patrec.2018.08.028
[43] Zheng, W., Zhu, X., Wen, G., Zhu, Y., Yu, H., Gan, J.: Unsupervised feature selection by self-paced learning regularization. Pattern Recognit. Lett. 132 (2020), 4-11. DOI 10.1016/j.patrec.2018.06.029
[44] S. Zhou, H. Xu, Z. Zheng, J. Chen, Z. Li, J. Bu, J. Wu, X. Wang, W. Zhu, M. Ester: A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. ACM Comput. Surv. 57 (2024), Article ID 69, 38 pages. DOI 10.1145/3689036
[45] Zhu, C., Xu, H., Leng, C., Yan, S.: Convex optimization procedure for clustering: Theoretical revisit. Advances in Neural Information Processing Systems 27 (NIPS 2014) Neural Information Processing Systems Foundation, Montreal (2014), 9 pages.
Search
Partner of
