همه چیز درباره الگوریتم DBSCAN

به عنوان یک مهندس ماشین لرنینگ یا دانشمند داده یادگیری الگوریتم‌های بدون ناظر امتیازهای مثبتی برای ما فراهم میاره و به طور کلی خیلی میتونه یادگیری این الگوریتم‌ها و نحوه استفاده از اونا شما رو خاص‌تر کنه.

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

این خیلی مهمه که ما بدونیم یه چیزیو برا چی داریم یاد میگیریم. ما احتمالا با الگوریتمای K-Means و Hierarchical آشناییم و شاید با خودتون فکر کنین وقتی اونا رو بلدین چه کاریه یه الگوریتم جدید یاد بگیرین. اما هم K-Means و هم Hierarchical تو خوشه‌بندی شکل‌های پیچیده و پیچ‌در‌پیچ مثل شکل زیر شکست میخورن. خوشه‌بندی دو الگوریتم بالا رو برای شکل‌های پیچیده ببینید.

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

همنطور که دیدین الگوریتم DBSCAN خیلی میتونه به ما کمک کنه که خوشه‌بندی بهتر و همینطور تشخیص Anomaly و نویز خیلی خوبی داشته باشیم. حتی ممکنه جاهایی فقط هدفشون تشخیص موارد مشکوک یا همون Anomaly باشه.

الگوریتم DBSCAN دقیقا چی هست؟

عبارت DBSCAN مخفف Density Based Spatial of Application with Noise هست. اووف نفسم بند اومد. چقدر طولانی :) این الگوریتم تو سال ۱۹۹۶ توسط آقای Martin Ester اختراع شد. کلا این الگوریتم دو تا پارامتر مهم داره. یکی minPoints و یکی هم Epsilon. اما این دوتا چی هستن اصلا؟!

پارامتر Epsilon نشون دهنده شعاع دایره ایه که دور هر نقطه برای تعیین چگالی اون به کار میره و همینطور minPoints حداقل تعداد داده‌ای رو نشون میده که باید تو دایره یه نقطه باشن تا اون نقطه هسته (Core) به حساب بیاد. نترسین همه اینا رو الان رو شکل یاد میگریم. اگه ابعاد زیادتر بشن دایره به ابرکره یا همون HyperSphere تبدیل میشه. دقیقا وقتی تو SVM خط به Hyperplane تبدیل میشه.

فرض کنید ما میخوایم داده‌های بالا رو خوشه‌بندی کنیم. الگوریتم ما میاد و دور هر نقطه یه دایره با شعاع Epsilon میکشه (مرکز هر دایره هم همون داده است) و هر نقطه رو یا هسته در نظر میگیره یا مرز و یا نویز. اگه بخوایم اصلاحات انگلیسیشونو بگیم هسته میشه Core Point و مرز میشه Border Point و در نهایت نویز هم میشه همون Noise :)

هسته (Core Point): داده‌ای که حداقل به تعداد minPoints دایره اون رو محاصره کرده باشه.

مرز (Border Point): داده‌ای که کمتر از minPoints (بیشتر از یکی) دایره اون رو محاصره کرده باشن.

نویز (Noise): داده‌ای که یدونه دایره اون رو محاصره کرده باشه.

فرض کنید ما minPoints رو ۳ بگیریم. همونطور که میبینید داده‌های قرمز توسط حداقل ۳ دایره محاصره شدن که اونا رو هسته در نظر میگریم. داده‌های زرد توسط بیشتر از یه دایره ولی کمتر از ۳ دایره محاصره شدن و در نهایت داده‌های بنفش توسط کلا یدونه دایره محاصره شدن. برای محاسبه این فاصله‌ها از فاصله اقلیدسی استفاده میشه.

دو مفهوم Reachability و Connectivity

مفهوم Reachability یعنی اینکه دو داده به یکدیگر دسترسی مستقیم یا غیرمستقیم دارند و Connectivity به این معناست که دو داده تو یه خوشه یکسان هستن. برای اینکه این مفاهیم رو بیشتر درک کنیم سه معیار را تعریف میکنیم:

• دسترسی‌پذیری مستقیم بر اساس چگالی (Directly Density-Reachable)
• دسترسی‌پذیری بر اساس چگالی (Density-Reachable)
• اتصال بر اساس چگالی (Density-Connected)

دسترسی‌پذیری مستقیم بر اساس چگالی (DDR) چیه؟

نقطه X از نقطه Y معیار DDR رو داره اگه:

1. داده X همسایه Y باشد به عبارتی فاصله اون از Y حداکثر Epsilon باشه.
2. داده Y هسته یا همون Core Point باشه.

همونطور که میبینید داده X از داده Y معیار DDR رو داره ولی برعکس این قضیه برقرار نیست چون X هسته نیست. دقت کنید که فاصله بین X و Y هم کمتر از Epsilon هست.

دسترسی‌پذیری مستقیم بر اساس چگالی (DR) چیه؟

نقطه X از نقطه Y معیار DR رو داره اگه X از P2 معیار DDR داشته باشه و P2 از P3 معیار DDR داشته باشه. این زنجیره باید جوری باشه که نقطه آخر از Y معیار DDR داشته باشه.

همونطور که میبینید نقطه X از P2 معیار DDR داره و P2 از P3 و در نهایت P3 از Y معیار DDR داره به همین خاطر میگیم X از Y معیار DR داره یا به عبارتی X از Y بر اساس چگالی دسترسی داره (غیرمستقیم).

اتصال بر اساس چگالی (DC) چیه؟

نقطه X از نقطه Y معیار DC رو داره اگه نقطه O وجود داشته باشه که هم X و هم Y از اون نقطه معیار DR رو داشته باشن.

همونطور که میبینید نقطه X از O و همینطور Y از O معیار DR رو دارن به همین خاطر میگیم X و Y تو یه خوشه هستن یا به عبارتی اتصال بر اساس چگالی دارن.

چطور پارامترهای اولیه رو تعیین کنیم؟

این الگوریتم خیلی به ست کردن مقادیر اولیه minPoints و Epsilon حساسه و با تغییر دادن این دوتا نتیجه کلا تغییر میکنه. نکته حداقلی که وجود داره اینه که مقدار minPoints باید حداقل از تعداد ابعاد مسیله یدونه بیشتر باشه. خب این خیلی واضحه که نمیتونیم minPoints رو برابر یک قرار بدیم چون هر نقطه یه خوشه جدا در نظر گرفته میشه. مقدار Epsilon خوب رو میتونیم از K-distance graph پیدا کنیم. همینطور میتونیم از Elbow که تو K-Means هم استفاده میشد کمک بگیریم.