×

Ensemble learning using three-way density-sensitive spectral clustering. (English) Zbl 07581230

Summary: As one popular clustering algorithm in the last few years, spectral clustering is advantageous over most existing clustering algorithms. Although spectral clustering can perform well in many instances, the algorithm still has some problems. The clusters obtained by spectral clustering have crisp boundaries, which cannot reflect the fact that one cluster may not have a well-defined boundary in the real situations. Furthermore, the frequently-used distance measures in spectral clustering cannot satisfy both global and local consistency, especially for the data with multi-scale. In order to address the above limitations, we firstly present a three-way density-sensitive spectral clustering algorithm, which uses the core region and the fringe region to represent a cluster. In the proposed algorithm, we use density-sensitive distance to produce a similarity matrix, which can well capture the real data structures. An overlap clustering is introduced to obtain the upper bound (unions of the core regions and the fringe regions) of each cluster and perturbation analysis is applied to separate the core regions from the upper bounds. The fringe region of the specific cluster is the differences between the upper bound and the core region. Because a single clustering algorithm cannot always achieve a good clustering result, we develop an improved ensemble three-way spectral clustering algorithm based on ensemble strategy. The proposed ensemble algorithm randomly extracts feature subset of sample and uses the three-way density-sensitive clustering algorithm to obtain the diverse base clustering results. Based on the base clustering results, voting method is used to generate a three-way clustering result. The experimental results show that the three-way density-sensitive clustering algorithm can well explain the data structure and maintain a good clustering performance at the same time, and the ensemble three-way density-sensitive spectral clustering can improve the robustness and stability of clustering results.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
Full Text: DOI

References:

[1] Xu, D. K.; Tian, Y. J., A comprehensive survey of clustering algorithms, Ann. Data Sci., 2, 165-193 (2015)
[2] Yang, X. B.; Qi, S. Y.; Song, N. X.; Yang, J. Y., Test cost sensitive multigranulation rough set: model and minimal cost selection, Inf. Sci., 250, 184-199 (2013) · Zbl 1320.68197
[3] Xu, W. H.; Yuan, K. H.; Li, W. T., Dynamic updating approximations of local generalized multigranulation neighborhood rough set, Appl. Intell. (2022)
[4] Xu, S. P.; Yang, X. B.; Yu, H. L.; Yu, D. J., Multi-label learning with label-specific feature reduction, Knowl.-Based Syst., 104, 52-61 (2016)
[5] Xu, W. H.; Yu, J. H., A novel approach to information fusion in multi-source datasets: a granular computing viewpoint, Inf. Sci., 378, 410-423 (2017) · Zbl 1429.68301
[6] Liu, K. Y.; Yang, X. B.; Yu, H. L.; Mi, J. S., Rough set based semi-supervised feature selection via ensemble selector, Knowl.-Based Syst., 165, 282-296 (2020)
[7] Song, L. H.; Zhang, X. F., Improved pixel relevance based on Mahalanobis distance for image segmentation, Int. J. Inf. Comput. Secur., 10, 2/3, 237-247 (2018)
[8] Lu, D.; Tripodis, Y.; Gerstenfeld, L. C.; Demissie, S., Clustering of temporal gene expression data with mixtures of mixed effects models with a penalized likelihood, Bioinformatics, 35, 5, 778-786 (2019)
[9] Macqueen, J., Some methods for classification and analysis of multivariate observations, (Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability (1967)), 281-297 · Zbl 0214.46201
[10] Luxburg, U. V., A tutorial on spectral clustering, Stat. Comput., 17, 4, 395-416 (2007)
[11] Wang, X. Y.; Ding, S. F.; Jia, W. K., Active constraint spectral clustering based on Hessian matrix, Soft Comput., 24, 3, 2381-2390 (2020)
[12] Shang, R. H.; Zhang, Z.; Jiao, L. C.; Wang, W. B.; Yang, S. Y., Global discriminative-based nonnegative spectral clustering, Pattern Recognit., 55, 172-182 (2016) · Zbl 1412.62085
[13] Ng, A. Y.; Jordan, M. I.; Weiss, Y., On spectral clustering: analysis and an algorithm, (Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic (2001)), 849-856
[14] Zelnik-Manor, L.; Pietro, P., Self-tuning spectral clustering, Adv. Neural Inf. Process. Syst., 17, 1601-1608 (2004)
[15] Wang, L.; Bo, L. F.; Jiao, L. C., Density-sensitive spectral clustering, Acta Electron. Sin., 35, 8, 1577-1581 (2007)
[16] Yang, P.; Zhu, Q. S.; Huang, B., Spectral clustering with density sensitive similarity function, Knowl.-Based Syst., 24, 5, 621-628 (2011)
[17] Tao, X. M.; Wang, R. T.; Chang, R.; Li, C. X.; Liu, R.; Zou, J. R., Spectral clustering algorithm using density-sensitive distance measure with global and local consistencies, Knowl.-Based Syst., 170, 26-42 (2019)
[18] Xu, R.; Wunsch, D. C., Survey of clustering algorithms, IEEE Trans. Neural Netw., 16, 3, 645-678 (2005)
[19] Yao, Y. Y., Three-way decisions with probabilistic rough sets, Inf. Sci., 180, 3, 341-353 (2010)
[20] Yao, Y. Y., The superiority of three-way decisions in probabilistic rough set models, Inf. Sci., 181, 6, 1080-1096 (2011) · Zbl 1211.68442
[21] Yao, Y. Y., Three-way decision and granular computing, Int. J. Approx. Reason., 103, 107-123 (2018) · Zbl 1448.68427
[22] Yu, H., A framework of three-way cluster analysis, (International Joint Conference on Rough Sets (2017)), 300-312
[23] Yu, H.; Jiao, P.; Yao, Y. Y.; Wang, G. Y., Detecting and refining overlapping regions in complex networks with three-way decisions, Inf. Sci., 373, 21-41 (2016) · Zbl 1429.68245
[24] Strehl, A.; Ghosh, J., Cluster ensembles-a knowledge reuse framework for combining multiple partitions, J. Mach. Learn. Res., 3, 3, 583-617 (2003) · Zbl 1084.68759
[25] Huang, D.; Lai, J. H.; Wang, C.-D., Ensemble clustering using factor graph, Pattern Recognit., 50, 131-142 (2016) · Zbl 1395.62157
[26] Xu, L.; Ding, S. F., A novel clustering ensemble model based on granular computing, Appl. Intell., 51, 8, 5474-5488 (2021)
[27] Yao, Y. Y., Tri-level thinking: models of three-way decision, Int. J. Mach. Learn. Cybern., 11, 5, 947-959 (2020)
[28] Yao, Y. Y., The geometry of three-way decision, Appl. Intell., 51, 9, 6298-6325 (2021)
[29] Luo, J. F.; Hu, M. J.; Qin, K. Y., Three-way decision with incomplete information based on similarity and satisfiability, Int. J. Approx. Reason., 120, 151-183 (2020) · Zbl 1433.68452
[30] Xu, J. F.; Zhang, Y. J.; Miao, D. Q., Three-way confusion matrix for classification: a measure driven view, Inf. Sci., 507, 772-794 (2020) · Zbl 1456.68206
[31] Zhao, X. R.; Hu, B. Q., Three-way decisions with decision theoretic rough sets in multiset-valued information tables, Inf. Sci., 507, 684-699 (2020) · Zbl 1456.68214
[32] Qi, J. J.; Qian, T.; Wei, L., The connections between three-way and classical concept lattices, Knowl.-Based Syst., 91, 143-151 (2016)
[33] Li, J. H.; Huang, C. C.; Qi, J. J.; Qian, Y. H.; Liu, W. Q., Three-way cognitive concept learning via multi-granularity, Inf. Sci., 378, 244-263 (2017) · Zbl 1429.68228
[34] Yuan, K. H.; Xu, W. H.; Li, W. T.; Ding, W. P., An incremental learning mechanism for object classification based on progressive fuzzy three-way concept, Inf. Sci., 584, 127-147 (2022) · Zbl 1535.68285
[35] Shao, M. W.; Lv, M. M.; Li, K. W.; Wang, C. Z., The construction of attribute (object)-oriented multi-granularity concept lattices, Int. J. Mach. Learn. Cybern., 11, 4, 1017-1032 (2020)
[36] Lang, G. M.; Miao, D. Q.; Fujita, H., Three-way group conflict analysis based on Pythagorean fuzzy set theory, IEEE Trans. Fuzzy Syst., 28, 447-461 (2020)
[37] Sun, B. Z.; Chen, X. T.; Zhang, L. Y.; Ma, W. M., Three-way decision making approach to conflict analysis and resolution using probabilistic rough set over two universes, Inf. Sci., 807, 809-822 (2020) · Zbl 1456.68202
[38] Li, X. N., Three-way fuzzy matroids and granular computing, Int. J. Approx. Reason., 114, 44-50 (2019) · Zbl 1468.68238
[39] Fujita, H.; Gaeta, A.; Loia, V.; Orciuoli, F., Improving awareness in early stages of security analysis: a zone partition method based on GrC, Appl. Intell., 49, 3, 1063-1077 (2019)
[40] Yang, X.; Li, T. R.; Liu, D.; Fujita, H., A temporal-spatial composite sequential approach of three-way granular computing, Inf. Sci., 486, 171-189 (2019)
[41] Hu, C. X.; Zhang, L., Incremental updating probabilistic neighborhood three-way regions with time-evolving attributes, Int. J. Approx. Reason., 120, 1-23 (2020) · Zbl 1433.68444
[42] Zhang, L. B.; Li, H. X.; Zhou, X. Z.; Huang, B., Sequential three-way decision based on multi-granular autoencoder features, Inf. Sci., 507, 630-643 (2020)
[43] Yang, X. B.; Yao, Y. Y., Ensemble selector for attribute reduction, Appl. Soft Comput., 70, 1-11 (2018)
[44] Li, W. W.; Jia, X. Y.; Wang, L.; Zhou, B., Multi-objective attribute reduction in three-way decision-theoretic rough set model, Int. J. Approx. Reason., 105, 327-341 (2019) · Zbl 1452.68216
[45] Zhang, X. Y.; Yang, J. L.; Tang, L. Y., Three-way class-specific attribute reducts from the information viewpoint, Inf. Sci., 507, 840-872 (2020) · Zbl 1456.68211
[46] Wang, X.; Wang, P. X.; Yang, X. B.; Yao, Y. Y., Attribution reduction based on sequential three-way search of granularity, Int. J. Mach. Learn. Cybern., 12, 5, 1439-1458 (2021)
[47] Afridi, M. K.; Azam, N.; Yao, J. T.; Alanazi, E., A three-way clustering approach for handling missing data using GTRS, Int. J. Approx. Reason., 98, 11-24 (2018) · Zbl 1451.62070
[48] Wang, P. X.; Yao, Y. Y., CE3: a three-way clustering method based on mathematical morphology, Knowl.-Based Syst., 155, 54-65 (2018)
[49] Wang, P. X.; Shi, H.; Yang, Y. B.; Mi, J. S., Three-way k-means: integrating k-means and three-way decision, Int. J. Mach. Learn. Cybern., 10, 10, 2767-2777 (2019)
[50] Yu, H.; Chen, L. Y.; Yao, J. T., A three-way density peak clustering method based on evidence theory, Knowl.-Based Syst., 211, Article 106532 pp. (2021)
[51] Jia, X. Y.; Rao, Y.; Li, W. W.; Yang, S. C., An automatic three-way clustering method based on sample similarity, Int. J. Mach. Learn. Cybern., 12, 5, 1545-1556 (2021)
[52] Yu, H.; Chen, L. Y.; Yao, J. T.; Wang, X. N., A three-way clustering method based on an improved DBSCAN algorithm, Phys. A, Stat. Mech. Appl., 535, Article 122289 pp. (2019)
[53] Li, F. J.; Qian, Y. H.; Wang, J. T.; Dang, C. Y., Clustering ensemble based on sample’s stability, Artif. Intell., 273, 37-55 (2019) · Zbl 1478.68312
[54] Yu, H.; Chen, Y.; Lingras, P.; Wang, G. Y., A three-way cluster ensemble approach for large-scale data, Int. J. Approx. Reason., 115, 32-49 (2019) · Zbl 1471.62401
[55] Yu, H.; Wang, X. C.; Wang, G. Y.; Zeng, X. H., An active three-way clustering method via low-rank matrices for multi-view data, Inf. Sci., 507, 823-839 (2020)
[56] Chu, X. L.; Sun, B. Z.; Li, X.; Han, K. Y., Neighborhood rough set-based three-way clustering considering attribute correlations: an approach to classification of potential gout groups, Inf. Sci., 535, 28-41 (2020)
[57] Ali, B.; Azam, N.; Shah, A.; Yao, J. T., A spatial filtering inspired three-way clustering approach with application to outlier detection, Int. J. Approx. Reason., 130, 1-21 (2021) · Zbl 1493.62377
[58] Shah, A.; Azam, N.; Alanazi, E.; Yao, J. T., Image blurring and sharpening inspired three-way clustering approach, Appl. Intell. (2022)
[59] Wu, T. F.; Fan, J. C.; Wang, P. X., An improved three-way clustering based on ensemble strategy, Mathematics, 10, 9, 1457 (2022)
[60] Fred, A. L.N.; Jain, A. K., Combining multiple clusterings using evidence accumulation, IEEE Trans. Pattern Anal. Mach. Intell., 27, 6, 835-850 (2005)
[61] Zhou, Z. H.; Tang, W., Cluster ensemble, Knowl.-Based Syst., 19, 1, 77-83 (2006)
[62] Wu, T. F.; Tsai, P. S.; Hu, N. T.; Chen, J. Y., Combining turning point detection and Dijkstra’s algorithm to search the shortest path, Adv. Mech. Eng., 9, 2, 1-12 (2017)
[63] Maulik, U.; Bandyopadhyay, S., Performance evaluation of some clustering algorithms and validity indices, IEEE Trans. Pattern Anal. Mach. Intell., 24, 12, 1650-1654 (2002)
[64] Bezdek, J. C., Pattern recognition with fuzzy objective function algorithms, Adv. Appl. Pattern Recognit., 22, 1171, 203-239 (1981) · Zbl 0503.68069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.