الگوريتم خوشه‌بندي براساس چگالي الگوريتم DBSCAN
جهت دریافت کد متلب الگوريتم DBSCAN به لینک های زیر مراجعه کنید
جهت دانلود کد متلب الگوریتم مبتنی بر چگالی اینجا را کلیک کنید
جهت دانلود سگمنت کردن تصویر با الگوریتم مبتنی بر چگالی اینجا را کلیک کنید
————————————————
خوشه‌بندي بر اساس چگالي
الگوريتم خوشه‌بندي براساس چگالي الگوريتم DBSCAN
اين روشهاي خوشه‌بندي بر اين اصل استوارند که خوشه‌ها، ناحيه‌هايي از فضاي داده با چگالي زيادي هستند که توسط نواحي با چگالي کمتر از همديگر جدا شده‌اند. براي پياده‌سازي اين روشهاي خوشه‌بندي لازم است تا ابتدا اصطلاحاتي تعريف شوند:
چگالي نقاط محلي در نقطة P (Local Point Density) : اگر P را نقطة هستة يک همسايگي و ε شعاع همسايگي براي نقطة P در نظر گرفته شود آنگاه همسايگي به شعاع ε براي نقطة P به صورت زير تعريف مي‌شود:
به تعداد نقاط قرار گرفته شده درون يک همسايگيِ داده شده چگالي نقاط آن همسايگي گفته مي‌شود. 
شکل 12: يک همسايگي براي P داراي چگالي نقاط 5
در دسترسِ مستقيمِ چگالي (Directly Density-Reachable): دادة p را در دسترسِ مستقيمِ چگاليِ q گويند اگر p درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد.
شکل 13: p در دسترسِ مستقيمِ چگاليِ q قرار دارد.
در دسترسِ چگالي (Density-Reachable): دادة p را در دسترسِ چگاليِ q گويند اگر داده‌اي وجود داشته باشد که هم درون يک همسايگي به شعاع ε با هستة p و هم درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد
شکل 14: p در دسترسِ چگاليِ q قرار دارد.
متصلِ چگالي (Density-Connected): دادة p را متصلِ چگاليِ q گويند اگر داده‌اي مانند o وجود داشته باشد که هم در دسترسِ چگاليِ p و هم در دسترسِ چگاليِ q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد.
شکل 15: 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 } مجموعة نويز خوانده مي‌شود.
شکل 16: خوشه‌بندي بر اساس چگالي
الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در اين روش خوشه‌بندي هر دادة متعلق به خوشة C در دسترس چگالي ساير داده‌هاي متعلق به آن خوشه است و در دسترس چگالي هيچ دادة ديگري قرار ندارد. شبه کد اين الگوريتم را زير مشاهده مي‌کنيد.
1-1-1- مثالي از الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در شکل زير سعي شده است تا نحوة اعمال الگوريتم خوشه‌بندي DBSCAN را بر روي يک مجموعه داده نشان داده شود. همان‌گونه که مشاهده مي‌شود، اين الگوريتم نوانسته است به خوبي داده‌ها را خوشه‌بندي کند.
a
b
c: 
d: 
f : 
شکل 17: مثالي از روش خوشه‌بندي DBSCAN
