ارائه یک الگوریتم خوشه‌بندی مبتنی بر چگالی توسعه‌یافته در کلان‌داده‌ها

قائمی, رضا; آراد, یعقوب; حاج قاضی, فرشته

doi:10.22034/aimj.2023.182055

ارائه یک الگوریتم خوشه‌بندی مبتنی بر چگالی توسعه‌یافته در کلان‌داده‌ها

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

نویسندگان

رضا قائمی ¹

یعقوب آراد ²

فرشته حاج قاضی ²

¹ استادیار، گروه مهندسی کامپیوتر، واحد قوچان، دانشگاه آزاد اسلامی، قوچان، ایران

² دانشجوی دکتری، گروه مهندسی کامپیوتر، واحد علوم و تحقیقات، دانشگاه آزاد اسلامی، نیشابور، ایران

10.22034/aimj.2023.182055

چکیده

امروزه تولید داده از طریق تجهیزات هوشمند، ازجمله تلفن‌های همراه، با رشد چشم‌گیری روبه‌رو بوده و خوشه‌بندی یکی از تکنیک‌های پرکاربرد کشف دانش در کلان‌داده‌ها است. خوشه‌بندی مبتنی بر چگالی (DBSCAN)، از الگوریتم‌های خوشه‌بندی کارا در داده‌کاوی بوده و با وجود داشتن مزایا، دارای مشکلاتی ازجمله سختی در تعیین پارامترهای ورودی و همچنین، نداشتن توانایی در کشف خوشه‌هایی با چگالی متفاوت نیز هست. در الگوریتم پیشنهادی این مقاله، از الگوریتم K-DBSCAN در گروه‌بندی داده‌های حجیم با هدف کاهش زمان اجرای خوشه‌بندی الهام گرفته شده است. به‌علاوه، با استفاده از الگوریتم‌های K-Means و H-DBSCAN، چگالی‌های مختلف مجموعه‌داده تشخیص داده می‌شود، برای هر چگالی یک شعاع Eps تعیین شده و سپس، الگوریتم پیشنهادی خوشه‌بندی مبتنی بر چگالی توسعه‌یافته با پارامترهای منطبق روی داده‌ها اعمال می‌شود. در واقع، نوآوری این مقاله استفاده از خوشه‌بندی K-Means و تخمین چگالی‌های مختلف در روش خوشه‌بندی DBSCAN است. الگوریتم پیشنهادی روی چهار مجموعه‌داده استاندارد Image segmentation، Pendigit، Letters و Shuttle control با الگوریتم خوشه‌بندی DBSCAN ساده و دو الگوریتم توسعه‌یافته K-DBSCAN و H-DBSCAN مقایسه شده است. نتایج نشان می‌دهد که الگوریتم پیشنهادی در زمانی که هر دو معیار زمان و دقت در خوشه‌بندی ملاک باشند، در مقایسه با الگوریتم‌های دیگر، الگوریتم برتری است.

کلیدواژه‌ها

کلان‌داده‌ها

خوشه‌بندی

DBSCAN

K-DBSCAN

H-DBSCAN

K-Means

عنوان مقاله English

An Extended Density-based Clustering Algorithm in Big Data

نویسندگان English

Reza Ghaemi ¹

Yaghoob Arad ²

Fereshteh Hajghazi ²

¹ Assistant Prof., Department of Computer Engineering, Quchan Branch, Islamic Azad University, Quchan, Iran

² Ph.D. Candidate, Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Neyshabour, Iran

چکیده English

Today, data generation through smart equipment, including mobile phones, has faced a significant growth, and clustering is one of the most widely used knowledge discovery techniques in big data. Density-based clustering (DBSCAN) is one of the most efficient clustering algorithms in data mining, and despite having advantages, it also has problems, such as the difficulty in determining the input parameters, as well as not being able to detect clusters. with different densities. In the proposed algorithm of this article, it is inspired by the K-DBSCAN algorithm in grouping large data with the aim of reducing the clustering execution time.In addition, by using K-Means and H-DBSCAN algorithms, different densities of the data set were identified and an Eps radius was determined for each density, and then, the proposed density-based clustering algorithm was developed with parameters The matching is applied to the data, and in fact, the innovation of this article is the use of K Means clustering and the estimation of different densities in the DBSCAN clustering method. The proposed algorithm has been compared with the simple DBSCAN clustering algorithm and two developed K-DBSCAN and H-DBSCAN algorithms on four standard data sets: Image segmentation, Pendigit, Letters and Shuttle control. The results show that the proposed algorithm is superior to other algorithms when both time and accuracy are criteria in clustering.

کلیدواژه‌ها English

Big data

Clustering

DBSCAN

K-DBSCAN

H-DBSCAN

K-Means

Ankerst, M., Breunig, M. M., Kriegel, H.P., & Sander, J. (1999). OPTICS. ACM SIGMOD Record, 28(2), 49–60.

Bechini, A., Criscione, M., Ducange, P., Marcelloni, F., & Renda, A. (2020). FDBSCAN-APT: A Fuzzy Density-based Clustering Algorithm with Automatic Parameter Tuning. 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE).

Botts, C. H. (2021). A Novel Metric for Detecting Anomalous Ship Behavior Using a Variation of the DBSCAN Clustering Algorithm. SN Computer Science, 2(5).

Chen, Y., Tang, S., Bouguila, N., Wang, C., Du, J., & Li, H. (2018). A fast clustering algorithm based on pruning unnecessary distance computations in DBSCAN for high-dimensional data. Pattern Recognition, 83, 375–387.

Chen, Y., Zhou, L., Bouguila, N., Wang, C., Chen, Y., & Du, J. (2020). BLOCK-DBSCAN: Fast Clustering For Large Scale Data. Pattern Recognition, 107624.

Chimwayi, K. B., & Anuradha, J. (2018). Clustering West Nile Virus Spatio-temporal data using ST-DBSCAN. Procedia Computer Science, 132, 1218–1227.

De Moura Ventorim, I., Luchi, D., Rodrigues, A. L., & Varejão, F. M. (2021). BIRCHSCAN: A sampling method for applying DBSCAN to large datasets. Expert Systems with Applications, 184, 115518.

Deng, D. (2020). DBSCAN Clustering Algorithm Based on Density. 2020 7th International Forum on Electrical Engineering and Automation (IFEEA).

Galán, S. F. (2019). Comparative evaluation of region query strategies for DBSCAN clustering. Information Sciences, 502, 76–90.

Gholizadeh, N., Saadatfar, H., & Hanafi, N. (2021). K-DBSCAN: An improved DBSCAN algorithm for big data. The Journal of supercomputing, 77, 6214-6235.

Hartmann, S., Ma, H., Hameurlain, A., Pernul, G., & Wagner, R. R. (Eds.). (2018). Database and Expert Systems Applications. Lecture Notes in Computer Science.

Heidari, S., Alborzi, M., Radfar, R., Afsharkazemi, M. A., & Rajabzadeh Ghatari, A. (2019). Big data clustering with varied density based on MapReduce. Journal of Big Data, 6, 1-16.

Kim, J. H., Choi, J.H., Yoo, K. H., & Nasridinov, A. (2018). AA-DBSCAN: an approximate adaptive DBSCAN for finding clusters with varying densities. The Journal of Supercomputing, 75(1), 142- 169.

Kuo, F. Y., Wen, T.H., & Sabel, C. E. (2018). Characterizing Diffusion Dynamics of Disease Clustering: A Modified Space–Time DBSCAN (MST-DBSCAN) Algorithm. Annals of the American Association of Geographers, 108(4), 1168–1186.

Lai, W., Zhou, M., Hu, F., Bian, K., & Song, Q. (2019). A New DBSCAN Parameters Determination Method Based on Improved MVO. IEEE Access, 7, 104085–104095.

Li, S. (2020). An Improved DBSCAN Algorithm Based on the Neighbor Similarity and Fast Nearest Neighbor Query. IEEE Access, 1–1.

Louhichi, S., Gzara, M., & Abdallah, H. B. (2018). Skin Lesion Segmentation Using Multiple Density Clustering Algorithm MDCUT And Region Growing. 2018 IEEE/ACIS 17th International Conference on Computer and Information Science (ICIS).

Louhichi, S., Gzara, M., & Ben-Abdallah, H. (2018). MDCUT2: a multi-density clustering algorithm with automatic detection of density variation in data with noise. Distributed and Parallel Databases, 37, 73-99.

Pavlis, M., Dolega, L., & Singleton, A. (2017). A Modified DBSCAN Clustering Method to Estimate Retail Center Extent. Geographical Analysis, 50(2), 141–161.

Sabor, K., Jougnot, D., Guerin, R., Steck, B., Henault, J.M., Apffel, L., & Vautrin, D. (2021). A data mining approach for improved interpretation of ERT inverted sections using the DBSCAN clustering algorithm. Geophysical Journal International, 225(2), 1304–1318.

Sharma, A., & Upadhyay, D. (2018). VDBSCAN clustering with map-reduce technique. In Recent Findings in Intelligent Computing Techniques: Proceedings of the 5th ICACNI 2017, Volume 2 (pp. 305-314). Springer Singapore.

Sheridan, K., Puranik, T. G., Mangortey, E., Pinon-Fischer, O. J., Kirby, M., & Mavris, D. N. (2020). An application of dbscan clustering for flight anomaly detection during the approach phase. In AIAA Scitech 2020 Forum (p. 1851).

Wang, Q., Wang, Z., Zhang, L., Liu, P., & Zhang, Z. (2020). A novel consistency evaluation method for series-connected battery systems based on real-world operation data. IEEE Transactions on Transportation Electrification, 7(2), 437-451.

Wang, Y., Gu, Y., & Shun, J. (2020, June). Theoretically-efficient and practical parallel DBSCAN. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (pp. 2555-2571).

Weng, S., Gou, J. & Fan, Z. (2021). h-DBSCAN: A simple fast DBSCAN algorithm for big data. Proceedings of The 13th Asian Conference on Machine Learning, PMLR 157:81-96, 2021.

Wu, X., Cheng, C., Zurita-Milla, R., & Song, C. (2020). An overview of clustering methods for geo-referenced time series: from one-way clustering to co- and tri-clustering. International Journal of Geographical Information Science, 1–27.

Yu, X., Zeng, F., Mwakapesa, D. S., Nanehkaran, Y. A., Mao, Y. -M., Xu, K. -B., & Chen, Z. -G. (2021). DBWGIE-MR: A density-based clustering algorithm by using the weighted grid and information entropy based on MapReduce. Journal of Intelligent & Fuzzy Systems, 40(6), 10781–10796.