الگوریتم مبتنی بر چگالی DBSCAN

 الگوریتم مبتنی بر چگالی DBSCAN

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

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

توضیحات الگوریتم DBSCAN

الگوریتم DBSCAN یک روش بسیار متداول از خانواده الگوریتم های خوشه بندی مبتنی بر چگالی برای داده های خاص می باشد ، مهمترین ویژگی های این الگوریتم شامل: توانایی تشخیص خوشه هایی  با اشکال دلخواه، توانایی خوشه بندی داده های همراه با نویز، و پیچیدگی زمانی پایین می باشند.

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

یک تعریف غیر رسمی از خوشه ممکن به اینصورت باشد: برای هر نقطه درون یک خوشه، همسایه ان  نقطه با شعاع همسایگی مشخص، باید حاوی کمترین تعداد نقاط باشد. این هم معنی با تجاوز تراکم  از برخی مقادیر استانه در همسایگی نقاط است.

تعریف 1 فرض کنید : x ∈X یکدادهو mکمترین تعداد نقاط در همسایگی εاز نقطه ی x باشد .

همسایگی εازیکنقطهدلخواه  Pبا(P) N  نشان داده شده و بصورت زیر تعریف می شود:

تعریف 4 :چگالی پیوندی
نقطه P  در چگالی پیوندی نقطه q  است، اگر یک نقطه r  وجود داشته باشد که p وq با توجه به ε و m،

 از سوی ان در دسترس چگالی باشند.

 الگوریتم کلی DBSCAN را در شکل4 – 5 مشاهده می نمایید

پارامترهای ε و m لازم است، فراهم شوند. نویسندگان مقاله یک روش اکتشافی برای تخمین انها پیشنهاد داده اند. بطور خلاصه، فاصله تمام نقاط از  k- امین نزدیکترین همسایه، محاسبه، مرتب سازی و ترسیم می شود. اغلب، گراف حاصل، حاوی پیچ خوردگی هایی است که نشان دهنده فاصله مطلوب هستند. پارامتر ε را برابر با این فاصله، قرار می دهیم.
الگوریتم DBSCAN از تعدادی ویژگی های مطلوب برخوردار است:
− می تواند خوشه هایی با اشکال دلخواه را پیدا نماید،
− پیچیدگی زمانی کمی دارد ، O(n logn) محاسبه همسایگی ε از مرتبه O(logn) است، و داده ها درون یک ساختمان داده –tree  R  ذخیره می شوند. برای هر داده ، n همسایه جهت محاسبه داریم،
− تعداد خوشه ها بطور صریح توسط کاربر تعیین نمی گردد، بلکه تعداد خوشه ها وابسته به مقدار انتخاب شده برای ε و تابع مسافت است،
− الگوریتم قادر است نمونه ها را با وجود نویز، خوشه بندی نماید.
یک ضعف نا خواسته و مهم این الگوریتم این است که خوشه ها باید حداقل m نمونه داده داشته باشند، و این بدلیل تعریف پیوندپذیری از نظر تراکم است. این امر موجب شده است که DBSCAN نتواند خوشه های بسیار کوچک را درون مجموعه داده های بزرگ پیدا نماید