0 امتیاز
قبل در کامپیوتر و اینترنت توسط (7.1هزار امتیاز)
روش DBSCAN در داده کاوی چیست و در چه زمینه ای کاربرد دارد؟

1 پاسخ

+1 امتیاز
قبل توسط (1.4هزار امتیاز)
انتخاب شده قبل توسط
 
بهترین پاسخ

روش 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 دشوار می‌شود.

 

سوالات مشابه

0 امتیاز
1 پاسخ 8.6هزار بازدید
0 امتیاز
0 پاسخ 807 بازدید
0 امتیاز
0 پاسخ 400 بازدید
+4 امتیاز
2 پاسخ 6.1هزار بازدید
سوال شده 10 سال قبل در برنامه نویسی توسط hldv (760 امتیاز)
0 امتیاز
0 پاسخ 48 بازدید
...