ecliptic

بررسی روش DBSCAN در خوشه بندی

یادگیری ماشین و هوش مصنوعی در RS

DBSCAN یک الگوریتم خوشه ای مبتنی بر تراکم و دارای شباهت به شیفت میانگین است. این روش یکی از روش های متداول خوشه بندی با بررسی میزان تراکم با قابلیت محاسبه نویز است که می توان آن را بر روی داده با شکل های پیچیده پیاده سازی کرد.

یادگیری ماشین[1] حوزه ای تخصصی از هوش مصنوعی[2] با هدف حل مسائل و پردازش آن ها و یادگیری و اجرای آن برای بعد، توسط ماشین(کامپیوتر) است.

یادگیری نظارت نشده[3] یک دسته از روش‌های یادگیری ماشین با هدف کشف الگوهای موجود در میان داده‌ها است. داده‌های ارائه شده به الگوریتم نظارت نشده دارای برچسب نیستند، بدین معنا که متغیر ورودی (X) بدون هیچ متغیر خروجی متناظری داده شده است. در یادگیری نظارت شده، الگوریتم ‌ها به حال خود رها می ‌شوند تا ساختارهای همگن موجود در میان داده‌ ها را کشف کنند.

خوشه بندی[4]

خوشه‌بندی، فرآیندی بدون نظارت است که به کمک آن می ‌توان مجموعه‌ ای از داده ها را به گروه ‌های مجزا گروه بندی کرد. که هر کدام از این گروه ها را خوشه می گویند. کار خوشه‌بندی به این صورت است که  نقاط داده را به منظور (بیشینه کردن مشابهت درون گروهی و کمینه کردن مشابهت برون گروهی)، گروه ‌بندی می‌کند.

هدف از خوشه بندی در این نوع یادگیری بدون نظارت تعیین توزیع داده ها در فضای ورودی  که با نام تخمین چگالی شناخته می شود. یا برای پیش بینی داده ها از فضا با ابعاد به بزرگ که به ابعاد سه و دو کاهش پیدا می کند با هدف مجسم سازی داده ها است(Bishop،2006).

در یک مقاله در وبسایت Towards Data Science  که در سال 2018 منتشر شد 7 الگوریتم زیر به عنوان پر استفاده ترین الگوریتم ها در خوشه بندی معرفی شدند:

  1. K-Means Clustering.
  2. Mean-Shift Clustering for a single sliding window.
  3. The entire process of Mean-Shift Clustering
  4. DBSCAN
  5. Two failure cases for K-Means.
  6. EM Clustering using GMMs.
  7. Agglomerative Hierarchical Clustering.

خوشه بندی DBSCAN

الگوریتم Density-based spatial clustering of applications with noise یا به اختصار DBSCAN به معنای خوشه بندی بر اساس تراکم فضایی از کاربرد با نویز، نوعی خوشه بندی است که در سال 1996 توسط مارتین استر و همکاران پا به عرصه ی وجود نهاد.

همان گونه از نام این الگوریتم پیداست این الگوریتم بر مبنای الگوریتم بر تراکم نقاط داده استوار است به این معنا که نقاط داده در هر کجای فضا دارای بیشترین تراکم باشد آن ها را به عنوان یک خوشه در نظر می گیرد. همان طور که از (شکل 2 ) می توان دید مجموعه نقاطی که دارای تراکم بیشتر هستند را می توان به عنوان گروه های با خاصیت یکسان(همگون) تعریف کرد و آن ها را در یک گروه قرار داد.
در الگوریتم DBSCAN  نیز مجموعه ای از نقاط در برخی فضا ها، نقاط با همسایگان مجاور خود به عنوان یک گروه دسته بندی می شوند و تنها در مناطقی که دارای کمترین تراکم اند(که از همسایگی بسیار دور هستند) به عنوان داده های خارج از محدوده[5] آن ها را حساب می کند.

برخلاف بسیاری از روش های خوشه بندی، DBSCAN نسبت به شکل داده ها حساس نیست و می تواند داده با شکل های بسیار پیچیده را نیز گروه بندی کند(مارتین و همکاران، 1996).

نحوه ی عملکرد الگوریتم

نحوه ی اجرای این الگوریتم بر خلاف نام پیچیده ی خود را می توان در مراحل ساده زیر توصیف کرد:

  • DBSCAN با یک نقطه اولیه دلخواه[6] شروع می شود که بازدید نشده است. محدوده این نقطه با استفاده از فاصله epsilon ε استخراج می شود (تمام نقاطی که در فاصله ε هستند نقاط هم گروه یا همسایه هستند). باید به یاد داشت که الگوریتم برای پیدا کردن همسایگی در یک فضای دو بعدی و سه بعدی از فاصله یابی اقلیدوسی استفاده می کند به این ترتیب همسایگی توسط کمترین مقدار فاصله از نقطه ی اصلی تعریف می شود.

  • اگر تعداد کافی نقاط (minPoints) در این محدوده وجود داشته باشد، فرآیند خوشه سازی شروع می شود(پیداکردن border point) و نقطه داده فعلی به اولین نقطه در خوشه جدید تبدیل می شود. در غیر این صورت، نقطه به عنوان نویز[7] تلقی می شود (بعدها این نقطه نویز ممکن است بخشی از خوشه شود). در هر دو مورد این نقطه به عنوان “بازدید شده” مشخص می شود.

  • برای این اولین نقطه در خوشه جدید، نقاط در محدوده ε فاصله آن نیز بخشی از یک خوشه است. این روش برای ساخت همه نقاط در گروه ε متعلق به یک خوشه مشابه است و سپس برای همه نقاط جدید که فقط به گروه خوشه اضافه شده اند تکرار می شود.
  • این فرآیند در مراحل 2 و 3 تکرار می شود تا تمام نقاط در خوشه ها وارد شوند یعنی همه نقاط در محدوده ε خوشه ای بازدید شده و برچسب گذاری شده اند.

تفسیر شکل 5:

  • نقطه آبی 1 نقطه در همسایگی خود، فقط خود را دارد.
  • نقاط زرد در همسایگی خود هر دو نقطه همسایه دارند.
  • نقاط قرمز در گروه همسایگی خود هر کدام 4-5 نقطه  دارند.

مزایا و معایب DBSCAN

DBSCAN مزایای زیادی را نسبت به سایر الگوریتم های خوشه ای ایجاد می کند.

  • در وهله  اول، تعداد کل خوشه ها به تعداد کل مجموعه ها نیاز ندارد.
  •  همچنین بر خلاف mean-shift که داده های خارج از محدوده را که به عنوان نویز تعيين می کن  که به سادگی آنها را به يک خوشه وارد  می کند، حتی اگر نقطه داده ها کاملا متفاوت باشد. علاوه بر این، می تواند دلخواهانه خوشه ها را به بهترین نحو، برآورد و شکل دهد.
  • اشکال اصلی DBSCAN زمانی پیدا می شود که خوشه ها دارای چگالی متغییر باشد، این امر به این علت است که  تنظیم حدآستانه فاصله ε و minPoints برای شناسایی نقاط همسایگی برای هر خوشه به خوشه دارای تراکم متغیر است که این ضعف در داده های بسیار طولانی به خوبی نمایان می گردد.

اما نتیجه گیری این الگوریتم را به صورت زیر خلاصه کرد:

  1. DBSCANیک الگوریتم انعطاف پذیر است و نسبت به داده ها دینامیک و پویا است.
  2. پارامترهای مورد نیاز برای اجرای الگوریتم می تواند از داده ها به دست آورد.
  3. این الگوریتم خوشه بندی درک پذیر تری را به ارمغان می آورد، زیرا بر اساس چگالی است و نقاطی را که به هیچ جا تعلق ندارند را ترک می کند.
  4. در مقایسه با روش های خوشه ای سنتی مانند K-Means Clustering، این الگوریتم بسیار سریع است.

کد پایتون خوشه بندی DBSCAN

در اين لينک مي توانيد کد پایتون خوشه بندی DBSCAN، مشاهده نماييد

منابع

واژه نامه

[1] Machine Learning

[2] Artificial Intelligence

[3] Unsupervised Learning

[4] Clustering

[5] outliers

[6] Core point

[7] Noise point

:اشتراک گذاری

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *