روش DBSCAN، معروفترین روش خوشهبندی مبتنیبر چگالی (Density Based Clustering) است. در خوشهبندی مبتنی بر چگالی، خوشهها به عنوان نواحی چگال از مجموعهداده، تعریف میشوند. اشیای موجود در نواحی کمتراکم، جداکنندهی خوشهها از هم هستد (این اشیا میوانند نقاط پارازیت یا نقاط مرزی باشند).
این روش نقاطی که در محدودهی معینی (در یک شعاع همسایگی) از هم قرار دارند را به هم وصل میکند. این الگوریتم، تنها نقاطی را متصل میکند که چگالی کمینهای داشته باشند. که این امر به عنوان حداقل تعداد اشیای موجود (MinPoints) در شعاع همسایگی (Epsilon) تعریف شده است و بر خلاف بسیاری از روشهای دیگر، میتواند خوشههای دارای اشکال دلخواه را شناسایی کند. ولی این روش در تشخیص خوشهها با چگالیهای مختلف ناتوان است.
نمونه خوشهبندی DBSCAN:
مزایا:
1. نیازی به مشخص بودن تعداد خوشهها، به صورت اطلاع قبلی، ندارد (بر خلاف روشهای خوشهبندی مبتنیبر مرکز مانند k-means).
2. میتواند خوشههای با اشکال مختلف را بیابد. همچنین میتواند خوشهای را که کاملا توسط خوشهی دیگر احاطه شده است (ولی به آن متصل نیست)، شناسایی کند. مشکل تکیالی (خوشههای مختلف با مسیر نازکی از نقاط به هم متصل باشند) نیز با پارامتر MinPoints کاهش یافته است.
3. از مفهوم پارازیت پشتیبانی میکند.
4. به دو پارامتر نیاز دارد (Epsilon و MinPoints) و نسبت به ترتیب قرار گرفتن نقاط در پایگاهداده حساس نیست. (البته در مورد برخی از نقاط مرزی، این امر صادق نیست. نقاطی که در مرز دو خوشهی متفاوت باشند، با توجه به ترتیبِ در نظر گرفتن نقاط در خوشهبندی، ممکن است در خوشهها جابجا شوند).
معایب:
1. این الگوریتم نمیتواند مجموعه دادههایی با اختلاف چگالی زیاد را خوشهبندی کند، به دلیل اینکه مقادیر MinPoints و Epsilon نمیتواند برای تمام خوشهها مناسب باشند (برای رفع این مشکل، توسعهی DD-DBSCAN برای آن ارایه شده است).
2. سربار بالای محاسباتی دارد. برای نمونه، در نواحی چگال، همسایگی نقاط مختلف اشتراک زیادی باهم دارند. در نتیجه نقاط تکراریِ زیادی را، در محاسبات خود لحاظ میکند و باعث افت کارایی این الگوریتم میشود (برای رفع این مشکل توسعهی IDBSCAN برای آن ارایه شده است).
3. کیفیت DBSCAN به نوع اندازهگیری فاصلهی نقاط بستگی دارد. فاصلهی اقلیدوسی رایجترین نوعی است که استفاده میشود. در دادههای در ابعاد بالا، این نوع اندازهگیری فاصله بیفایده میشود. در نتیجه یافتن مقداری برای Epsilon دشوار میشود.