الگوریتم خوشه‌بندی براساس چگالی الگوریتم DBSCAN

 الگوریتم خوشه‌بندی براساس چگالی الگوریتم DBSCAN

جهت دریافت کد متلب الگوریتم DBSCAN به لینک های زیر مراجعه کنید

جهت دانلود کد متلب الگوریتم مبتنی بر چگالی اینجا را کلیک کنید

جهت دانلود سگمنت کردن تصویر با الگوریتم مبتنی بر چگالی اینجا را کلیک کنید

 

————————————————

خوشه‌بندی بر اساس چگالی

الگوریتم خوشه‌بندی براساس چگالی الگوریتم DBSCAN
الگوریتم خوشه‌بندی براساس چگالی الگوریتم DBSCAN


این روشهای خوشه‌بندی بر این اصل استوارند که خوشه‌ها‌، ناحیه‌هایی از فضای داده با چگالی زیادی هستند که توسط نواحی با چگالی کمتر از همدیگر جدا شده‌اند. برای پیاده‌سازی این روشهای خوشه‌بندی لازم است تا ابتدا اصطلاحاتی تعریف شوند:

چگالی نقاط محلی در نقطه P (Local Point Density) : اگر P را نقطه هسته یک همسایگی و ε شعاع همسایگی برای نقطه P در نظر گرفته شود آنگاه همسایگی به شعاع ε برای نقطه P به صورت زیر تعریف می‌شود:


به تعداد نقاط قرار گرفته شده درون یک همسایگیِ داده شده چگالی نقاط آن همسایگی گفته می‌شود. 

شکل ۱۲: یک همسایگی برای P دارای چگالی نقاط ۵

در دسترسِ مستقیمِ چگالی (Directly Density-Reachable): داده p را در دسترسِ مستقیمِ چگالیِ q گویند اگر p درون یک همسایگی به شعاع ε با هسته q باشد. در شکل زیر بهتر می‌توان این مفهوم را درک کرد.


شکل ۱۳: p در دسترسِ مستقیمِ چگالیِ q قرار دارد.

در دسترسِ چگالی (Density-Reachable): داده p را در دسترسِ چگالیِ q گویند اگر داده‌ای وجود داشته باشد که هم درون یک همسایگی به شعاع ε با هسته p و هم درون یک همسایگی به شعاع ε با هسته q باشد. در شکل زیر بهتر می‌توان این مفهوم را درک کرد

شکل ۱۴: p در دسترسِ چگالیِ q قرار دارد.

متصلِ چگالی (Density-Connected): داده p را متصلِ چگالیِ q گویند اگر داده‌ای مانند o وجود داشته باشد که هم در دسترسِ چگالیِ p و هم در دسترسِ چگالیِ q باشد. در شکل زیر بهتر می‌توان این مفهوم را درک کرد.

شکل ۱۵: p متصلِ چگالیِ q است

خوشه مبتنی بر چگالی (Density-Based Cluster): زیر مجموعه‌ای غیرتهی(S) از مجموعه داده‌ها (D) که دارای دو شرط زیر باشد:

§ حداکثر: اگر p درون S باشد و q در دسترسِ چگالیِ p باشد آنگاه q نیز متعلق به S باشد.

§ اتصال: هر داده درون S متصلِ چگالیِ سایر داده‌های درون S باشد.



o خوشه‌بندی بر اساس چگالی (Density-Based Clustering): خوشه‌بندی بر اساس چگالی بر روی مجموعه داده D مجموعه‌ای به صورت {S1, …, Sn, N} است که :

§ S1, …, Sn تمام خوشه‌های مبتنی چگالیِ درون D است.

§ N=D\{ S1, …, Sn } مجموعه نویز خوانده می‌شود.



شکل ۱۶: خوشه‌بندی بر اساس چگالی

الگوریتم خوشه‌بندی براساس چگالی DBSCAN: در این روش خوشه‌بندی هر داده متعلق به خوشه C در دسترس چگالی سایر داده‌های متعلق به آن خوشه‌ است و در دسترس چگالی هیچ داده دیگری قرار ندارد. شبه کد این الگوریتم را زیر مشاهده می‌کنید.



۱-۱-۱- مثالی از الگوریتم خوشه‌بندی براساس چگالی DBSCAN: در شکل زیر سعی شده است تا نحوه اعمال الگوریتم خوشه‌بندی DBSCAN را بر روی یک مجموعه داده نشان داده شود. همان‌گونه که مشاهده می‌شود، این الگوریتم نوانسته ‌است به خوبی داده‌ها را خوشه‌بندی کند.
a

b

c: 

d: 

f : 

شکل ۱۷: مثالی از روش خوشه‌بندی DBSCAN

نظر خود را اینجا بنویسید!

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