علوم رایانش و فناوری اطلاعات
یک الگوریتم خوشه‌بندی خودکارِ مبتنی بر ساختار هندسی دایره آپولونیوس و رابطه همسایگی متقابل داده‌ها
نوع مقاله : مقاله پژوهشی
نویسندگان
1 دانشکده فناوری اطلاعات و مهندسی کامپیوتر، دانشگاه شهید مدنی آذربایجان، تبریز، ایران
2 دانشکده فناوری اطلاعات و مهندسی کامپیوتر دانشگاه شهید مدنی آذربایجان ، تبریز ایران
چکیده
در بسیاری از مسائل یادگیری ماشین و داده‌کاوی مانند طبقه‌بندی و خوشه‌بندی، از الگوریتم‌های ساخت همسایگی برای مدل‌سازی روابط محلی بین نمونه‌های داده استفاده می‌شود. در یافتن ارتباط بین نقاط داده، تشخیص دقیق همسایگی نقاط به‌طور انکارناپذیری برای کاوش داده‌ها مفید است. طی سالیان اخیر، برخی روش‌های تشخیص همسایگی مبتنی بر ساختارهای هندسی ارائه شده‌اند که به دلیل دقت بالا در مکان‌یابی نقاط همسایگی بسیار کارآمد بوده‌اند. با این حال اغلب این روش‌ها برای تشکیل گروه‌های مشابه نیاز به بررسی همه نقاط همسایگی دارند. به همین دلیل اغلب هزینه‌های محاسباتی بالایی دارند. در این میان، ساختار دایره آپولونیوس در ارزیابی شباهت‌های محلی در بین مشاهدات، عملکرد بهتری از خود نشان داده است و زمینه جدیدی از علم هندسه را در داده‌کاوی گشوده است. ساختار آپولونیوس امکان معرفی دانش پنهان را از طریق معرفی معیارهای هندسه فراهم می‌کند و می‌تواند یک منطقه همسایگی پویا را برای نقاط داده تعریف کند. در این مقاله، با بهره‌گیری از مزایای ساختار هندسی دایره آپولونیوس و ایده همسایگان متقابل داده‌ها، یک الگوریتم خوشه‌بندی خودکار ارائه می‌شود. از ویژگی همسایگی متقابل نقاط داده برای تشخیص سریع و بهینه همسایگی نقاط داده، شناسایی نواحی متراکم و کشف داده‌های پرت (نویز) استفاده می‌شود. از ساختار هندسی دایره آپولونیوس نیز برای تعیین شعاع همسایگی نواحی متراکم (با چگالی داده بالا) استفاده می‌شود. طوریکه برای هریک از نواحی، یک شعاع همسایگی پویا و متناسب با نقاط داده مربوطه استخراج می‌شود. طی این دو فرایند، هم تعداد خوشه‌های بهینه و هم اعضا هر خوشه شناسایی می‌شود. بدین ترتیب یک روش خوشه‌بندی خودکار حاصل می‌شود که نیاز به تعیین تعداد خوشه‌ها ندارد. آزمایش‌های انجام شده بر روی مجموعه داده‌های استاندارد و مقایسه نتایج با دیگر روش‌ها، نشان از عملکرد مناسب روش پیشنهادی دارد.
کلیدواژه‌ها
- [1] M. Hashemzadeh and N. Farajzadeh, "Combining keypoint-based and segment-based features for counting people in crowded scenes," Information Sciences, vol. 345, pp. 199-216, 2016.
- [2] M. Hashemzadeh, A. Golzari Oskouei, and N. Farajzadeh, "New fuzzy C-means clustering method based on feature-weight and cluster-weight learning," Applied Soft Computing, vol. 78, pp. 324-345, 2019/05/01/ 2019, doi: https://doi.org/10.1016/j.asoc.2019.02.038.
- [3] Z. Hu and R. Bhatnagar, "Clustering algorithm based on mutual K‐nearest neighbor relationships," Statistical Analysis and Data Mining: The ASA Data Science Journal, vol. 5, no. 2, pp. 100-113, 2012.
- [4] M. Hashemzadeh and B. A. Azar, "Retinal blood vessel extraction employing effective image features and combination of supervised and unsupervised machine learning methods," Artificial intelligence in medicine, vol. 95, pp. 1-15, 2019.
- [5] M. Hashemzadeh and N. Farajzadeh, "A machine vision system for detecting fertile eggs in the incubation industry," International Journal of Computational Intelligence Systems, vol. 9, no. 5, pp. 850-862, 2016.
- [6] A. G. Oskouei, M. Hashemzadeh, B. Asheghi, and M.-A. Balafar, "CGFFCM: Cluster-weight and Group-local Feature-weight learning in Fuzzy C-Means clustering algorithm for color image segmentation," Applied Soft Computing, p. 108005, 2021.
- [7] S. Pourbahrami and S. Azimpour, "A new method for detection of clustering based on four zones Apollonius circle," Iran Journal of Computer Science, vol. 3, no. 1, pp. 59-64, 2020/03/01 2020, doi: 10.1007/s42044-019-00050-1.
- [8] S. Pourbahrami, M. A. Balafar, L. M. Khanli, and Z. A. Kakarash, "A survey of neighborhood construction algorithms for clustering and classifying data points," Computer Science Review, vol. 38, p. 100315, 2020/11/01/ 2020, doi: https://doi.org/10.1016/j.cosrev.2020.100315.
- [9] S. Pourbahrami, L. M. Khanli, and S. Azimpour, "A novel and efficient data point neighborhood construction algorithm based on Apollonius circle," Expert Systems with Applications, vol. 115, pp. 57-67, 2019/01/01/ 2019, doi: https://doi.org/10.1016/j.eswa.2018.07.066.
- [10] S. Pourbahrami, L. M. Khanli, and S. Azimpour, "Improving neighborhood construction with Apollonius region algorithm based on density for clustering," Information Sciences, vol. 522, pp. 227-240, 2020/06/01/ 2020, doi: https://doi.org/10.1016/j.ins.2020.02.049.
- [11] S. A. Seyedi, A. Lotfi, P. Moradi, and N. N. Qader, "Dynamic graph-based label propagation for density peaks clustering," Expert Systems with Applications, vol. 115, pp. 314-328, 2019/01/01/ 2019, doi: https://doi.org/10.1016/j.eswa.2018.07.075.
- [12] Z. Liu, C. Wu, Q. Peng, J. Lee, and Y. Xia, "Local Peaks-Based Clustering Algorithm in Symmetric Neighborhood Graph," IEEE Access, vol. 8, pp. 1600-1612, 2020, doi: 10.1109/ACCESS.2019.2962394.
- [13] M. Emadi and J. Tanha, "Margin-Based Semi-supervised Learning Using Apollonius Circle," in Topics in Theoretical Computer Science, Cham, L. S. Barbosa and M. Ali Abam, Eds., 2020// 2020: Springer International Publishing, pp. 48-60.
- [14] J. P. Papa, S. E. N. Fernandes, and A. X. Falcão, "Optimum-Path Forest based on k-connectivity: Theory and applications," Pattern Recognition Letters, vol. 87, pp. 117-126, 2017/02/01/ 2017, doi: https://doi.org/10.1016/j.patrec.2016.07.026.
- [15] D. Liu, G. V. Nosovskiy, and O. Sourina, "Effective clustering and boundary detection algorithm based on Delaunay triangulation," Pattern Recognition Letters, vol. 29, no. 9, pp. 1261-1273, 2008/07/01/ 2008, doi: https://doi.org/10.1016/j.patrec.2008.01.028.
- [16] M. Abbas, A. El-Zoghabi, and A. Shoukry, "DenMune: Density peak based clustering using mutual nearest neighbors," Pattern Recognition, vol. 109, p. 107589, 2021/01/01/ 2021, doi: https://doi.org/10.1016/j.patcog.2020.107589.
- [17] K. He and J. Sun, "Computing nearest-neighbor fields via propagation-assisted kd-trees," in 2012 IEEE Conference on Computer Vision and Pattern Recognition, 2012: IEEE, pp. 111-118.
)