علوم رایانشی

علوم رایانشی

الگوریتم -میانگین++ مبتنی بر فاصله شواهد و تحلیل پایداری در حضور نوفه و داده‌های پرت

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

نویسندگان
1 گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
2 گروه آمارو ریاضی، دانشکده انرژی و علوم داده، دانشگاه صنعتی خاتم الانبیاء بهبهان، بهبهان، ایران
10.22034/csj.2026.585989.1157
چکیده
در این مقاله، الگوریتم خوشه‌بندی شواهد-محور ED-K-means++ ارائه می‌شود که ترکیبی از مقداردهی اولیه K-means++ و فاصله شواهد ژوسلم در چارچوب نظریه دمپستر- شیفر است. هدف اصلی کاهش حساسیت به مراکز اولیه و بهبود پایداری در حضور نوفه و داده‌های پرت است. هر نمونه به تابع تخصیص احتمال پایه تبدیل شده و مراکز اولیه بر اساس مربع فاصله شواهد انتخاب می‌شوند. عملکرد روش پیشنهادی روی سه مجموعه‌داده استاندارد Iris، Wine و Breast Cancer در ۳۰ اجرای مستقل و در سه حالت بدون اغتشاش، نوفة گاوسی و داده‌های پرت ارزیابی شد. نتایج نشان داد که اگرچه روش پیشنهادی لزوماً موجب افزایش شاخص بیرونیARI در همه مجموعه‌داده‌ها نمی‌شود، اما نسبت به ED-K-means رفتار پایدارتر و ساختار درونی منسجم‌تری در فضای شواهد ایجاد می‌کند. در حالت بدون اغتشاش، ضریب سیلوئت برای Wine به 958/0 و برای Breast Cancer به 972/0 رسید، در حالی که در حالت داده‌های پرت (ρ=0.20) این شاخص برای Breast Cancer تا 984/0 نیز افزایش یافت. شاخص Davies–Bouldin نیز در حالت بدون اغتشاش برای Breast Cancer تا 329/0 کاهش یافت که بیانگر افزایش فشردگی درون‌خوشه‌ای و جدایی بهتر خوشه‌ها است. در تحلیل حساسیت پارامترهای ساخت BPA نیز مقدار مشابهی (394/0) برای این مجموعه‌داده به‌دست آمد. ارزیابی در سطوح مختلف نوفه و داده‌های پرت نشان داد، مقداردهی اولیه مبتنی بر فاصله شواهد از اجراهای ناپایدار جلوگیری می‌کند. در مجموع، نتایج نشان می‌دهد روش پیشنهادی با پایدارسازی مقداردهی اولیه در فضای شواهد، موجب بهبود انسجام درونی خوشه‌ها و کاهش حساسیت الگوریتم به شرایط نوفه‌ای، بدون افزایش پیچیدگی محاسباتی نسبت به روش پایه، می‌شود.
کلیدواژه‌ها
موضوعات

1.     Rousseeuw, P. J. 1987. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis, Journal of Computational and Applied Mathematics, vol. 20, pp. 53–65.
2.     Davies, D. L., & Bouldin, D. W. 1979. A cluster separation measure,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-1, no. 2, pp. 224–227.
3.     MacQueen, J. B. 1967. Some methods for classification and analysis of multivariate observations, in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, Berkeley, CA, USA: University of California Press, 1967, pp. 281–297.
4.     Lloyd, S. P. 1982. Least squares quantization in PCM, IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137.
5.     Arthur, D., & Vassilvitskii, S. 2007. k-means++: The advantages of careful seeding, in Proceedings of the Eighteenth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, USA, pp. 1027–1035.
6.     Dempster, A. P. 1967. Upper and lower probabilities induced by a multivalued mapping, The Annals of Mathematical Statistics, vol. 38, no. 2, pp. 325–339.
7.     Shafer, G. 1976. A Mathematical Theory of Evidence. Princeton, NJ, USA: Princeton University Press.
8.     Jousselme, A.-L., Grenier, D., & Bossé, É. 2001. A new distance between two bodies of evidence, Information Fusion, vol. 2, no. 2, pp. 91–101.
9.     Zhu, A., Hua, Z., Shi, Y., Tang, Y., & Miao, L. 2021. An improved k-means algorithm based on evidence distance,” Entropy, vol. 23, no. 11, Art. no. 1550.
10. Lopes de Souza, V. F., Bakhti, K., Ramdani, S., Mottet, D. & Imoussaten, A. 2025. Explainable evidential clustering, arXiv preprint arXiv:2507.12192.
11. Adamyan, A., Hovanesyan, H., Radrigan, D., Baloian, N., & Harutyunyan, A.2025. Interpretable clustering using Dempster–Shafer theory, Journal of Universal Computer Science, vol. 31, no. 9, pp. 980–1003, 2025.
12. Gan, H., Yang, Z., & Zhou, R. 2023. Safe semi-supervised clustering based on Dempster–Shafer evidence theory, Engineering Applications of Artificial Intelligence, vol. 123, Art. no. 106334.
13. Hubert, L., & Arabie, P. 1985. Comparing partitions, Journal of Classification, vol. 2, no. 1, pp. 193–218.