بررسي مشكلات الگوريتم خوشه بندي DBSCAN و مروري بر بهبودهاي ارائه‌شده براي آن

A study on DBSCAN Clustering algorithm issues and a survey on its improvements

خوشه‌بندي يك از تكنيك‌هاي مهم كشف دانش در پايگاه داده‌ است. الگوريتم‌هاي خوشه‌بندي مبتني بر چگالي يكي از روش‌هاي اصلي براي خوشه‌بندي در داده‌كاوي هستند. عدم محدوديت به شكل خوشه‌ها، ساده و قابل‌فهم بودن از جمله مزاياي اين الگوريتم‌ها است. DBSCAN الگوريتم پايۀ روش‌هاي خوشه‌بندي مبتني بر چگالي است. اين الگوريتم قابليت كشف خوشه‌هاي با اندازه و اشكال متفاوت را از حجم زيادي از داده‌ها دارد و در مقابل نويز نيز مقاوم است. علي‌رغم وجود اين مزايا، اين الگوريتم داراي مشكلاتي نظير سخت بودن تعيين مقدار دقيق پارامترهاي ورودي، عدم‌تشخيص خوشه‌هاي با چگالي متفاوت و عدم‌تشخيص صحيح خوشه‌ها در هنگام نزديك بودن خوشه‌ها به هم نيز مي‌باشد. از سال 1996 كه DBSCAN ارائه شده تا به امروز، الگوريتم‌هاي بسيار زيادي در جهت بهبود DBSCAN ارائه ‌شده‌اند. در اين مقاله ابتدا، مشكلات الگوريتم DBSCAN بررسي مي‌شوند. سپس به مرور و بررسي الگوريتم‌هايي كه در جهت بهبود مشكلات الگوريتم DBSCAN ارائه ‌شده‌اند مي‌پردازيم تا‌ با نقاط ضعف و قوت اين الگوريتم‌ها و ميزان موفقيت اين الگوريتم‌ها در بهبود الگوريتم DBSCAN آشنا شويم. همچنين، با توجه به مطالعات انجام‌شده، اقدام به پياده‌سازي برخي از اين الگوريتم‌ها نموده‌ايم و آن‌ها را بر روي مجموعه داده‌هاي استاندارد، بر اساس معيارهاي ارزيابي خوشه‌بندي تست كرده‌ايم تا بهتر بتوانيم دربارۀ اين الگوريتم‌ها قضاوت كنيم.

Clustering is an important knowledge discovery technique in the database. Density-based clustering algorithms are one of the main methods for clustering in data mining. These algorithms have some special features including being independent from the shape of the clusters, highly understandable and ease of use. DBSCAN is a base algorithm for density-based clustering algorithms. DBSCAN is able to detect clusters with different sizes and shapes in huge amounts of data and is also resistant to noise. Despite its advantages, this algorithm has its own drawbacks such as the difficulty in determining appropriate values for input parameters, inability to detect clusters with different density and inability to detect appropriate clusters when they are too close. Since 1996 that DBSCAN has been introduced, many different algorithms have been proposed as improvements of DBSCAN. In this paper, firstly the drawbacks of DBSCAN algorithm are discussed. Secondly, we review and discuss DBSCAN improvement algorithms in order to know the pros and cons of each algorithm and their success in improving DBSCAN algorithm. We also implemented some of these algorithms according to our studies and tested them according to the clustering evaluation criteria on standard data sets, so that we would to be able to judge the algorithms better.