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

پیاده سازی خوشه بندی با الگوریتم خوشه بندی DBSCAN با متلب ، در این پروژه از میان روش های مختلف برای کلاسترینگ به سراغ روش های مبتنی بر چگالی (Density Based) رفته ایم و کلاسترینگ یا خوشه بندی را با استفاده از الگوریتم DBSCAN که یکی از متداول ترین الگوریتم های مربوط به کلاسترینگ مبتنی بر چگالی است، را انجام داده ایم.

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

سوال اصلی و اساسی که در روش های کلاسترینگ مبتنی بر چگالی وجود دارد این مسئله است که چگونه ما می توانیم مناطق چگال را پیدا کنیم؟ به صورت کلی چگالی یک شیء همانند A توسط تعداد شیء های مجاور و نزدیک آن می تواند اندازه گیری شود. الگوریتم DBSCAN به اصطلاح اشیاء مرکزی (Core Objects) را پیدا می نماید و با اتصال این اشیاء مرکزی به همسایه های مربوط به آن شیء یک ناحیه چگال را تشکیل داده و آن را به عنوان یک کلاستر مطرح می کند (منظور از اشیاء مرکزی اشیایی هستند که در همسایگی آن ها تعداد زیادی شیء وجود دارد و به اصطلاح دارای همسایگی چگال هستند).

سوال بعدی که در ذهن ما شکل می گیرد این مسئله است که الگوریتم DBSCAN چگونه ناحیه همسایگی یک شیء را تشخیص می دهد؟ این الگوریتم دارای پارامتری به نام اپسیلون ( Ɛ ) است که مقدار آن همواره بزرگتر از صفر است و شعاع همسایگی اشیاء را مشخص می کند. پس به صورت کلی همسایگی با شعاع Ɛ برای شیء A شامل فضایی به مرکز این شیء و شعاع Ɛ است. با توجه به اینکه پارامتر Ɛ ثابت است، چگالی یک ناحیه همسایگی برای یک شیء خاص می تواند با شمردن تعداد اشیاء موجود در شعاع همسایگی آن شیء خاص صورت پذیرد.

برای درک بهتر از همسایگی چگال و غیر چگال شکل زیر را در نظر بگیرید :

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

در شکل بالا نقاطی (اشیاء) که با فلش قرمز رنگ مشخص شده اند نقاطی هستند که همسایگی آن ها چگال نیست و یا به عبارتی تعداد خیلی کمی (یا هیچ) شیء در شعاع همسایگی آن ها وجود دارد. اما نقاطی (اشیاء) که با فلش آبی رنگ مشخص شده اند نقاط چگالی هستند که در همسایگی آن ها تعداد مورد قبولی شیء واقع شده است.
نکته ی مهم دیگری که در ارتباط با الگوریتم DBSCAN وجود دارد این مسئله است که این الگوریتم برای تعیین این مسئله که آیا یک شعاع همسایگی چگال محسوب می شود یا خیر از پارامتر دیگری به نام حداقل تعداد نقاط و یا Minpts استفاده می کند. این پارامتر در حقیقت حد آستانه برای چگال محسوب شدن نواحی همسایگی را تعیین می کند. برای درک بهتر از دو پارامتر مطرح شده ( Ɛ و Minpts ) به مثال زیر دقت کنید:

فرض کنید که پارامتر Ɛ که شعاع همسایگی را مشخص می کند برابر با ۱ و پارامتر Minpts برابر با ۳ باشد.در این صورت اشیایی که در شعاعی برابر با ۱ به مرکزیت خود، ۲ شیء دیگر و یا بیشتر را شامل شوند (با احتساب خود شیء ، ۳ شیء یا بیشتر) چگال محسوب می شوند. برای درک بهتر شکل زیر را در نظر بگیرید :

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

در شکل بالا ، نقاط سبز رنگ اشیایی هستند که قصد داریم آن ها را بررسی کنیم که آیا دارای همسایگی چگال هستند و یا خیر و نقاط قرمز رنگ مابقی اشیاء موجود در مسئله هستند. فرض می کنیم که پارامتر Minpts برابر با ۳ می باشد و همچنین فرض می کنیم دایره های بزرگ آبی رنگ پارامتر Ɛ که آن را برابر با ۱ فرض کردیم به تصویر می کشند.
در شکل سمت چپ شرایط مدنظر برقرار است چون حداقل ۳ شیء در همسایگی شیء مورد بررسی ما (سبز رنگ) قرار دارد. از این رو شکل سمت چپ نمایش دهنده یک همسایگی چگال است اما شکل سمت راست چون شرط حداقل ۳ شیء در همسایگی را رعایت نمی کند چگال محسوب نمی شود. قابل توجه است که مابه اشیایی گوییم اشیاء مرکزی (Core Objects) که در شعاع همسایگی آن ها حداقل به تعداد Minpts شیء دیگر حضور داشته باشد. از این رو در مثال گفته شده ، در شکل سمت چپ، شیء سبز رنگ Core Object محسوب می شود. زمانی که یک مجموعه داده برای کلاسترینگ در اختیار ما قرار می گیرد ، ما می توانیم با توجه به دو پارامتر Ɛ و Minpts اشیای مرکزی (Core Objects) را تشخیص دهیم و بعد از آن عملیات کلاسترینگ محدود به استفاده از اشیاء مرکزی و شعاع همسایگی آن ها برای تشکیل مناطق چگال و معرفی این مناطق به عنوان کلاستر می باشد.

در الگوریتم DBSCAN دو مفهوم Directly Density Reachable و Density Connected وجود دارد که آن ها را در ادامه توضیح داده ایم.

اگر ما دارای یک شیء مرکزی (Core Object) مثل Q و یک شیء ساده مثل P باشیم، گوییم P از Q ، Directly Density Reachable است اگر P درون شعاع همسایگی Q قرار داشته باشد. با استفاده از این مفهوم یک شیء مرکزی می تواند تمامی اشیایی که در همسایگی آن قرار دارند را به درون یک ناحیه چگال بیاورد. مفهوم Directly Density Reachable همان طور که از اسم آن بر می آید به صورت مستقیم بین دو شیء عمل می کند اما حالت خاصی نیز از این مفهوم وجود دارد که به صورت مستقیم عمل نمی کند و Density Reachable نام دارد. برای درک این مفهوم فرض کنید دارای ۳ شیء p3 و p2، p1 هستیم به این صورت که p1 با p2 و p2 با p3 خاصیت Directly Density Reachable را دارند. از این رو می توانیم بگوییم که p1 با p3 دارای خصوصیت Density Reachable می باشد. به صورت ساده یعنی شیء p1 می تواند به ناحیه چگال مربوط به p3 به صورت غیر مستقیم بپیوندد. برای اتصال اشیای مرکزی ) همانند اتصال شیء مرکزی به شیء های موجود در ناحیه همسایگی آن ( از مفهوم Density Connectivity استفاده می شود. گوییم که دو شیء p2 و p1 به اصطلاح Density Connected هستند اگر شیء دیگری مثل Q وجود داشته باشد به صورتی که p2 و p1 از طریق Q Density Reachable باشند ( هر دوی آن ها در ناحیه همسایگی Q باشند ).

در ادامه نحوه ی کلاسترینگ توسط DBSCAN را به صورت مرحله به مرحله بیان کرده ایم.

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

۱) ابتدا تمامی رکورد ها (اشیاء) موجود در مجموعه را ملاقات نشده (Unvisited) فرض می کنیم.
۲) یکی از اشیای ملاقات نشده را به صورت تصادفی انتخاب کرده و آن را به عنوان ملاقات شده (Visited) مشخص می کنیم.
۳) شعاع همسایگی شیء برداشته شده را بررسی می کنیم تا مشخص شود آیا شامل حداقل Minpts شیء دیگر هست یا خیر.
۴) اگر در همسایگی شیء مربوطه حداقل Minpts شیء دیگر حضور نداشت، شیء انتخابی را به عنوان Noise در نظر می گیریم (و دیگر با آن کاری نخواهیم داشت) در غیر این صورت یک کلاستر جدید مثل C (با نام دلخواه شما) برای شیء انتخابی تشکیل می دهیم و تمامی اشیاء موجود در همسایگی آن شیء را در یک مجموعه کاندید مثل N ذخیره می کنیم.
۵) در ادامه ، الگوریتم DBSCAN تمامی اشیاء موجود در مجموعه کاندید N که متعلق به کلاستر C است را بررسی می کند. هر شیء از این مجموعه ابتدا بررسی می شود که ملاقات نشده باشد ( Unvisited باشد) سپس اگر شعاع همسایگی آن شامل حداقل Minpts شیء دیگر بود آن اشیاء نیز به مجموعه کاندید N اضافه می شوند. این روال تا زمانی ادامه می یابد که به مجموعه N عضو جدید اضافه نشود.
۶) تمامی اعضای مجموعه N را به کلاستر C نسبت می دهیم و کار کلاستر C را تمام شده می دانیم.
۷) برای ایجاد کلاستر بعدی یکی از اشیایی که ملاقات نشده اند را به صورت تصادفی انتخاب می کنیم و روال گفته شده را برای آن انجام می دهیم.
۸) این عملیات تا زمانی ادامه می یابد که هیچ شیء ای بدون ملاقات نمانده باشد (تمام اشیاء یا Visited باشند یا Noise)

مجموعه داده

برای پیاده سازی این پروژه یک مجموعه داده مورد استفاده قرار گرفته است که دارای ۴ بعد و ۱۰٫۰۰۰ رکورد می باشد.هدف پروژه اجرای الگوریتم DBSCAN بر روی این مجموعه داده و کلاستر کردن تمامی رکورد های آن است. توجه داشته باشید که بسته به انتخاب دو پارامتر این الگوریتم که عبارتند از Ɛ و Minpts خروجی نهایی پیاده سازی ما می تواند متفاوت باشد. هرچقدر میزان شعاع همسایگی بیشتر در نظر گرفته شود تعداد کلاستر های نهایی کمتر خواهد بود و بالعکس. در مورد حداقل تعداد اشیاء موجود در شعاع همسایگی هم هرچقدر حد آستانه بالاتر در نظر گرفته شود الگوریتم تمایل به تشکیل کلاستر هایی با چگالی بالاتر خواهد داشت.

نکات مربوط به پیاده سازی

این پروژه مربوط به مبحث داده کاوی می باشد و در نرم افزار متلب پیاده سازی شده است.

کلاسترینگ به صورت کامل پیاده سازی شده است و نتایج کلاسترینگ که شامل کلاستر ها و رکورد های متعلق به آن ها است در خروجی قابل مشاهده می باشد.

توضیحات پیاده سازی در گزارش  موجود می باشد.

کارشناسان وب سایت MATLABDL قادر به انجام پروژه در زمینه های مشابه (پروژه های داده کاوی و…) نیز می باشند.

قیمت پروژه : ۷۴۰۰۰ تومان

حجم : ۱٫۲۸ مگابایت
توضیحات : پیاده سازی در نرم افزار متلب انجام شده است.
کلمات کلیدی: خوشه بندی,الگوریتم های خوشه بندی,الگوریتم DBSCAN,الگوریتم خوشه بندی DBSCAN,پیاده سازی الگوریتم DBSCAN با متلب,خوشه بندی با روش های مبتنی بر چگالی
منبع : مطلب دی ال
رمز فایل : www.matlabdl.com