اموزش الگوریتم DBSCAN

اموزش الگوریتم DBSCAN

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

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

الگوریتم DBSCAN نخستین بار توسط مارتین استر و همکاران معرفی شد [5]. این الگوریتم روشی برای

خوشه‌بندی است که بر پایه چگالی داده‌ها عمل می‌کند. در این روش به منظور تخمین چگالی توزیع نقاط از دو پارامتر شعاع همسایگی (Eps) حداقل نقاط مورد نیاز برای تشکیل یک خوشه (MinPts) استفاده می‌شود.

این الگوریتم از یک نقطه اختیاری شروع می­شود. سپس نقاطی که در همسایگی این نقطه با فاصله کمتر از ε قرار دارند شمارش می­شوند. اگر تعداد نقاط بیشتر از پارامتر minPts بود یک خوشه ایجاد می­شود در غیر این صورت نقطه مورد بررسی به عنوان نوفه شناخته می­شود. نکته مهمی که در این روش وجود دارد این است که شاید این نقطه در گام­های بعدی به عنوان قسمتی از یک خوشه دسته بندی شود و حسن دیگر این روش امکان تشخیص و تفکیک نوفه از دیگر داده‌ها است.

در شکل 1 نقطه A یک نقطه مرکزی است که با توجه به اینکه تعداد نقاط همسایگی بیش از معیار minPts (در اینجا مقدار minPts برابر 3 است) است باعث ایجاد یک خوشه جدید می­شود (نقاط قرمز رنگ همگی دارای این خاصیت هستند). نقاط B و C که در همسایگی خود کمتر از minPts نقطه دارند نقاط مرزی هستند به طوری که اگر نقاط همسایه آنها در یک خوشه باشند آنها نیز در همان خوشه قرار می­گیرند در غیر این صورت به عنوان نوفه مشخص می­شوند (در اینجا نقطه B در خوشه بندی قرار می­گیرد و نقطه C به عنوان نوفه شناخته می­شود). نقاطی مانند نقطه N که هیچ نقطه ای در همسایگی خود ندارند به عنوان نوفه شناخته می­شوند.

شکل 1. روش کار الگوریتم DBSCAN

الگوریتم DBSCAN برای خوشه بندی به صورت زیر است :

–          الگوریتم DBSCAN با ورودی‌های SetOfPoints، Eps و MinPts شروع شود.

–          برای تمام نقاط موجود در SetOfPoints حلقه زیر انجام شود.

o        متغیر Point برابر با نقطه جاری از SetOfPoint قرار گیرد.

o        اگر نقطه Point خوشه‌بندی نشده بود آنگاه:

§         اگر خروجی تابع ExpandCluster به ازاء ورودی‌های SetOfPoints، Point، ClusterId، Eps و MinPts صحیح بود آنگاه ClusterId برابر خوشه بعدی ClusterId شود.

§         پایان شرط

o        پایان شرط

–          پایان حلقه

–          پایان الگوریتم

در الگوریتم آورده شده SetOfPoint اطلاعات نقاط موجود برای خوشه ­­بندی است. تابع مهمی که در این الگوریتم به کار رفته تابع ExpandCluster است. این تابع پارامترهای SetOfPoints، Point، ClusterId، Eps و MinPts را به عنوان ورودی دریافت می‌کند و یک مقدار صحیح یا غلط را باز می‌گرداند. در این تابع ابتدا نقاط موجود در همسایگی نقطه Point که در شعاع کمتر از Eps هستند شمرده می‌شوند. اگر تعداد نقاط کمتر از MinPts بود نقطه به عنوان نوفه علامت گذاری می‌شود و مقدار غلط به تابع ExpandCluster باز گردانده می‌شود و کار تابع تمام می‌شود. ولی اگر تعداد نقاط بیشتر از MinPts بود نقطه Point با عنوان ClusterId علامت گذاری می‌شود و تمام نقاطی که در این بازه هستند نیز با عنوان ClusterId علامت گذاری می‌شوند و برای تمام نقاطی که به صورت زنجیر در محدوده نقاط علامت گذاری شده هستند نیز این کار ادامه پیدا می‌کند و در نهایت مقدار صحیح به تابع باز گردانده می‌شود.

ایمیل : matlab24ir@gmail.com و یا info@matlab24.ir

شماره تماس : 09120563264