علوم رایانشی

علوم رایانشی

یک معیار شباهت مبتنی بر محبوبیت برای بهبود کارایی خوشه‌بندی طیفی

نوع مقاله : مقاله پژوهشی

نویسنده
استادیار، دانشکده مهندسی برق و کامپیوتر، دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته، کرمان، ایران
10.22034/csj.2024.203192
چکیده
روش‌های خوشه‌بندی طیفی، به دلیل قابلیتی که در تشخیص خوشه‌های با شکل‌های مختلف دارند، بسیار مورد توجه قرار گرفته‌اند. کارایی این روش‌ها وابستگی شدیدی به نحوه تعریف شباهت بین نمونه‌ها دارد. بنابراین، تلاش‌ها برای بهبود کارایی این الگوریتم‌ها بر روی ارایه معیار شباهت مناسب‌تر متمرکز بوده است. در این مقاله، به هر نمونه شاخصی تحت عنوان شاخص محبوبیت نسبت می‌دهیم که بیانگر میزان مرکزیت آن نمونه در مجموعه داده است. همچنین، معیار شباهت جدیدی مبتنی بر محبوبیت نمونه‌ها پیشنهاد و بر پایه آن الگوریتم خوشه‌بندی طیفی مبتنی بر محبوبیت را پیشنهاد می‌دهیم. از آنجا که شاخص محبوبیت پیشنهادی مستقل از چگالی محلی خوشه‌هاست، الگوریتم پیشنهادی می‌تواند در خوشه‌بندی داده‌های با چگالی‌های متفاوت موفق عمل کند. معیار پیشنهادی ویژگی سودمند دیگری نیز دارد؛ شباهت نمونه‌ها در معیار پیشنهادی با توجه به محبوبیت آنها و جایگاه یک نمونه در لیست همسایگان نمونه دیگر محاسبه می‌شود. این ویژگی به جداسازی خوشه‌های با همپوشانی بالا کمک بسیاری می‌کند. به دلیل سادگی تعریف پیشنهادی برای شاخص محبوبیت، الگوریتم محاسبه ماتریس شباهت پیشنهادی پیچیدگی محاسباتی بسیار پایینی دارد. برای مطالعه و مقایسه کارایی الگوریتم خوشه‌بندی پیشنهادی با همتاهای آن، از منظر معیار انطباق NMI، آزمایش‌هایی بر روی شش مجموعه داده‌ مصنوعی و پانزده مجموعه داده واقعی انجام داده‌ایم. نتایج نشان می‌دهد که الگوریتم خوشه‌بندی پیشنهادی و معیار شباهت مطرح در آن کارایی بهتری نسبت به روش‌های همتای آن از جمله معیار شباهت مبتنی بر میانگین محلی، معیار خود- تنظیم و معیار شباهت محلی مبتنی بر همسایه‌های مشترک دارد و در اغلب موارد بهترین عملکرد را به‌دست می‌آورد.
کلیدواژه‌ها
موضوعات

[1] Xudong Tang‎, ‎Chao Dong‎, ‎Wei Zhang‎: ‎Contrastive author-aware text clustering‎. ‎Pattern Recognit‎. ‎130‎: ‎108787 (2022)‎
[2] Junpeng Tan‎, ‎Zhijing Yang‎, ‎Yongqiang Cheng‎, ‎Jielin Ye‎, ‎Bing Wang‎, ‎Qingyun Dai‎: ‎SRAGL-AWCL‎: ‎A two-step multi-view clustering via sparse representation and adaptive weighted cooperative learning‎. ‎Pattern Recognit‎. ‎117‎: ‎107987 (2021)‎
[3] ‎Hang Zhang‎, ‎Haili Li‎, ‎Ning Chen‎, ‎Shengfeng Chen‎, ‎Jian Liu‎: ‎Novel fuzzy clustering algorithm with variable multi-pixel fitting spatial information for image segmentation‎. ‎Pattern Recognit‎. ‎121‎: ‎108201 (2022)‎
[4] ‎Guillaume Guenard‎, ‎Pierre Legendre‎: ‎Hierarchical Clustering with Contiguity Constraint in R‎. ‎J‎. ‎Stat‎. ‎Softw‎. ‎103(7) (2022)‎
[5] ‎Chunrong Wu‎, ‎Qinglan Peng‎, ‎Jia Lee‎, ‎Kenji Leibnitz‎, ‎Yunni Xia‎: ‎Effective hierarchical clustering based on structural similarities in nearest neighbor graphs‎. ‎Knowl‎. ‎Based Syst‎. ‎228‎: ‎107295 (2021)‎
[6] ‎Jianbo Shi‎, ‎Jitendra Malik‎: ‎Normalized Cuts and Image Segmentation‎. ‎IEEE Trans‎. ‎Pattern Anal‎. ‎Mach‎. ‎Intell‎. ‎22(8)‎: ‎888-905 (2000)‎
[7] Abhishek Kumar, Hal Daume: A Co-training Approach for Multi-view Spectral Clustering. ICML 2011: 393-400
[8] ‎Jiexing Liu‎, ‎Chenggui Zhao‎: ‎Density Gain-Rate Peaks for Spectral Clustering‎. ‎IEEE Access 9‎: ‎46000-46010 (2021)‎
[9]‎ ‎Ng A‎. ‎Y‎, ‎Jordan M‎. ‎I‎, ‎Weiss Y‎, ‎On spectral clustering‎: ‎Analysis and an algorithm‎, ‎NIPS'01‎: ‎Proceedings of the 14th International Conference on Neural Information Processing Systems‎: ‎Natural and Synthetic‎, ‎849-856 (2001)‎.
[10] Von Luxburg U‎, ‎A tutorial on spectral clustering‎, ‎Statistics and Computing‎, ‎17(4)‎, ‎395-416 (2007)‎.
[11] ‎Yessica Nataliani‎, ‎Miin-Shen Yang‎: ‎Powered Gaussian kernel spectral clustering‎. ‎Neural Comput‎. ‎Appl‎. ‎31(S-1)‎: ‎557-572 (2019)‎
[12] Zelnik-Manor L‎, ‎Perona P‎, ‎Self-tuning spectral clustering‎, ‎Neural Information Processing Systems (NIPS 2004) Vancouver‎, ‎British Columbia‎, ‎Canada‎, ‎1601-1608 (2004)‎
[13] ‎Tong Liu‎, ‎Jingting Zhu‎, ‎Jukai Zhou‎, ‎Yongxin Zhu‎, ‎Xiaofeng Zhu‎: ‎Initialization-similarity clustering algorithm‎. ‎Multim‎. ‎Tools Appl‎. ‎78(23)‎: ‎33279-33296 (2019)‎
[14] ‎Xianchao Zhang‎, ‎Jingwei Li‎, ‎Hong Yu‎: ‎Local density adaptive similarity measurement for spectral clustering‎. ‎Pattern Recognit‎. ‎Lett‎. ‎32(2)‎: ‎352-358 (2011)‎
[15] ‎Hassan Motallebi‎, ‎Rabeeh Nasihatkon‎, ‎Mina Jamshidi‎: ‎A Local Mean-based Distance Measure for Spectral Clustering‎. ‎Pattern Analysis \& Applications 25(2)‎, ‎351-359 (2022)‎
[16] ‎Zongqi Cao‎, ‎Hongjia Chen‎, ‎Xiang Wang‎: ‎Spectral clustering based on the local similarity measure of shared neighbors‎, ‎ETRI Journal‎, ‎2022‎, ‎44(5)‎: ‎769-779‎
[17] ‎Paola Favati‎, ‎Grazia Lotti‎, ‎Ornella Menchi‎, ‎Francesco Romani‎: ‎Construction of the similarity matrix for the spectral clustering method‎: ‎Numerical experiments‎. ‎J‎. ‎Comput‎. ‎Appl‎. ‎Math‎. ‎375‎: ‎112795 (2020)‎
[18] Malgorzata Lucinska‎, ‎Slawomir T‎. ‎Wierzchon‎: ‎Spectral Clustering Based on k-Nearest Neighbor Graph‎. ‎CISIM 2012‎: ‎254-265‎
[19] ‎Tan M‎, ‎Zhang S‎, ‎Wu L‎, ‎Mutual KNN based spectral clustering‎, ‎Neural computing and applications‎, ‎32‎, ‎6435-6442 (2020)‎
[20] ‎Mashaan A‎. ‎Alshammari‎, ‎John Stavrakakis‎, ‎Masahiro Takatsuka‎: ‎Refining a k-nearest neighbor graph for a computationally efficient spectral clustering‎. ‎Pattern Recognit‎. ‎114‎: ‎107869 (2021)‎
[21] ‎Yongda Cai‎, ‎Joshua Zhexue Huang‎, ‎Jianfei Yin‎: ‎A new method to build the adaptive k-nearest neighbors similarity graph matrix for spectral clustering‎. ‎Neurocomputing 493‎: ‎191-203 (2022)‎
[22] Xiucai Ye‎, ‎Tetsuya Sakurai‎: ‎Spectral clustering using robust similarity measure based on closeness of shared Nearest Neighbors‎. ‎IJCNN 2015‎: ‎1-8‎
[23] ‎Tulin Inkaya‎: ‎A parameter-free similarity graph for spectral clustering‎. ‎Expert Syst‎. ‎Appl‎. ‎42(24)‎: ‎9489-9498 (2015)‎
[24] ‎F‎. ‎Nie‎, ‎X‎. ‎Wang‎, ‎H‎. ‎Huang‎, ‎Clustering and projected clustering with adaptive neighbors‎, ‎in‎: ‎Proceedings of the 20th ACM SIGKDD International Conference‎
‎on Knowledge Discovery and Data Mining‎, ‎2014‎, ‎pp‎. ‎977–986‎.
[25] ‎Z‎. ‎Bian‎, ‎H‎. ‎Ishibuchi‎, ‎S‎. ‎Wang‎, ‎Joint learning of spectral clustering structure and fuzzy similarity matrix of data‎, ‎IEEE Trans‎. ‎Fuzzy Syst‎. ‎27 (1) (2018) 31–44‎
[26] ‎K.K‎. ‎Sharma‎, ‎A‎. ‎Seal‎, ‎Spectral embedded generalized mean based k-nearest neighbors clustering with s-distance‎, ‎Expert Syst‎. ‎Appl‎. ‎169 (2021) 114326‎.
[27] ‎Ufuk Bahceci‎: ‎New bounds for the empirical robust Kullback-Leibler divergence problem‎. ‎Inf‎. ‎Sci‎. ‎637‎: ‎118972 (2023)‎
[28] Jon Louis Bentley‎: ‎Multidimensional Binary Search Trees Used for Associative Searching‎. ‎Commun‎. ‎ACM 18(9)‎: ‎509-517 (1975)‎
[29] F‎. ‎Pedregosa‎, ‎et al‎. ‎Scikit-learn‎: ‎Machine learning in Python‎, ‎J‎. ‎Mach‎. ‎Learn‎. ‎Res.‎, ‎vol‎. ‎12‎, ‎pp‎. ‎2825-2830‎, ‎‎2011‎.
[30] P. Fanti, and S. Sieranoja, “K-Means Properties on Six Clustering Benchmark Datasets,” Appl. Intell., vol. 48, no. 12, pp. 4743-4759, 2018.
[31] D. Dua, and C. Graff‎, “‎UCI Machine Learning Repository,” http://archive.ics.uci.edu/ml, 2019.
[32] J. ‎B‎. ‎MacQueen‎, ‎"Some methods for classification and analysis of multivariate observations‎,” Proc. 5th Berkeley Symp. Math. Statist. Prob., ‎pp. 281–297, 1967.
[33] C. Malzer‎, and ‎M. Baum, “‎A Hybrid Approach to Hierarchical Density-based Cluster Selection‎," Proc. IEEE Int. Conf. Multisens. Fusion Integr. Intell. Syst., pp. ‎223-228, 2020.
[34] A. Bryant‎, ‎and K. J‎. ‎Cios, "‎RNN-DBSCAN‎: ‎A Density-Based Clustering Algorithm Using Reverse Nearest Neighbor Density Estimates," ‎IEEE Trans‎. ‎Knowl‎. ‎Data Eng‎., vol. ‎30, no. 6, pp. ‎1109-1121, 2018.
[35] M‎. ‎S. Sarfraz‎, ‎V. Sharma‎, ‎and R. Stiefelhagen‎, “‎Efficient Parameter-Free Clustering Using First Neighbor Relations‎,"‎ Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit., pp. ‎8934-8943, 2019.