الگوریتم DBSCAN

نویسنده

دکتر محمدرضا عاطفی

 عضو هیات علمی دانشگاه، رئیس هیات مدیره گروه ناب، مشاور شرکت‌ها و سازمان‌ها

و مریم کامکاردل

ویرایش محتوا
ویرایش محتوا
ویرایش محتوا
ویرایش محتوا
ویرایش محتوا

📌 مقدمه

این نقاط داده با استفاده از این مفهوم اساسی که نقطه داده در محدودیت داده شده از مرکز خوشه قرار دارد، خوشه بندی می شوند. روش ها و تکنیک های مختلف فاصله برای محاسبه outliers استفاده می شود. 

📌 مشکل اساسی این الگوریتم :

خوشه های مختلف ممکن است چگالی بسیار متفاوتی داشته باشند  خوشه ها ممکن است در سلسله مراتب باشند 

📌 پارامترهای مهم الگوریتم DBSCAN

اپسیلون : این اندازه گیری محله است. 

همسایگی 

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

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

EPS بیش از حد کوچک انتخاب شود، بخش بزرگی از داده ها به عنوان یک دور افتاده در نظر گرفته می شود. اگر بسیار بزرگ انتخاب شود، خوشه ها ادغام می شوند و اکثر نقاط داده در همان خوشه ها قرار می گیرند. یک راه برای پیدا کردن مقدار EPS بر اساس گراف k-distance است. 

 min_sample :  این یک استانه در کمترین تعداد نقاط است که ما می خواهیم در محله یک نقطه ببینیم. فرض کنید ما z = 3 را میگیریم 

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

طبقه بندی نقاط 

اکنون بر اساس این دو پارامتر یعنی اپسیلون و min_samples، ما ابتدا هر نقطه در مجموعه داده های خود را به سه دسته طبقه بندی می کنیم.

  1. نقاط اصلی 
  2. نقاط مرزی یا Border Points 
  3. نقاط سر و صدا 

با توجه به اپسیلون و MinPts، اشیاء را به سه گروه انحصاری دسته بندی کنید. 

نقاط اصلی

 یک نقطه اگر بیش از تعداد مشخصی از نقاط (MinPts) در Eps داشته باشد، یک نقطه مرکزی است – اینها نقاطی هستند که در داخل یک خوشه قرار دارند. حالا رقم فوق الذهن را ببینید. من یک نقطه اصلی A را نشان دادم. اگر من یک نقطه را به عنوان یک نقطه اصلی بگویم، باید یک شرط را براورده کند. شرط این است که تعداد همسایگان باید بیشتر یا برابر با استانه ما min_samples یا z باشد. اگر من z = 3 را تنظیم کنم، این نقطه این شرایط را راضی می کند. از این رو، ما می گوییم این نقطه اصلی است. بیایید نوع دوم نقطه را ببینیم. 

نقاط مرزی 

 یک نقطه مرزی کمتر از MinPts درون Eps دارد، اما در همسایگی یک نقطه مرکزی است.  اگر من یک نقطه را به عنوان نقطه مرزی بگویم، باید دو شرط زیر را براورده کند. 

  • تعداد همسایه ها باید کمتر از z باشد. 
  • نقطه باید در همسایگی یک نقطه اصلی باشد. 

همان رقمی را که در بالا ذکر شد در نظر بگیرید. من یک نقطه مرزی B را نمایندگی کردم. این نقطه کمتر از تعداد همسایگان در محله خود است و در همسایگی یک نقطه اصلی دیگر قرار دارد. بنابراین، این نقطه B یک نقطه مرزی یا نقطه مرزی است. 

نقاط سر و صدا 

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

2. سر و صدا را حذف کنید

حذف سر و صدا 

DBSCAN در حذف نویز بسیار موثر است. 

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

  1. خوشه را به یک نقطه اصلی اختصاص دهید. 
  2. تمام نقاط متصل به چگالی یک نقطه اصلی را رنگ کنید. 
  3. نقاط مرزی رنگ با توجه به نزدیکترین نقطه هسته. 

3.  یک نقطه اصلی را می گیریم و ان را به یک خوشه قرمز اختصاص می دهیم 

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

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

الگوریتم DBSCAN انجام شد! 

مثال . شکل بالا خوشه های کشف شده توسط DBSCAN را نشان می دهد 

مجموعه داده مبتنی بر چگالی در شکل 15.1. برای مقادیر پارامتر ǫ = 15 و minpts = 10، پس از تنظیم پارامتر پیدا شد، DBSCAN خوشه‌بندی تقریباً کاملی را ایجاد می‌کند. شامل هر نه خوشه. خوشه با استفاده از نمادها و سایه های مختلف نشان داده شده است. نقاط نویز به صورت نمادهای بعلاوه نشان داده می شوند

📌 تخمین چگالی هسته

ارتباط نزدیکی بین خوشه‌بندی مبتنی بر چگالی و تخمین چگالی وجود دارد. هدف از تخمین چگالی تعیین چگالی احتمال مجهول است با یافتن نواحی متراکم نقاط، که به نوبه خود می تواند برای خوشه بندی استفاده شود، عمل می کند. تخمین چگالی کرنل یک تکنیک ناپارامتریک است که هیچ فرضی ندارد . مدل احتمال ثابت خوشه ها، مانند مورد K-means یا مخلوط مدل فرض شده در الگوریتم EM. در عوض، سعی می‌کند مستقیماً زیربنا را استنباط کند چگالی احتمال در هر نقطه از مجموعه داده

تخمین چگالی تک متغیره: 

فرض کنید X یک متغیر تصادفی پیوسته است، و اجازه دهید x1، x2،…، xn یک متغیر تصادفی باشد. نمونه برگرفته از تابع چگالی احتمال اصلی f (x)، که فرض شده است ناشناخته بودن ما می توانیم به طور مستقیم تابع توزیع تجمعی را از روی تخمین بزنیم داده ها با شمارش چند نقطه کمتر یا مساوی x هستند: 

که در آن I یک تابع نشانگر است که فقط زمانی که آرگومانش درست باشد مقدار 1 و 0 دارد در غیر این صورت. ما می توانیم تابع چگالی را با گرفتن مشتق F (x) ˆ، توسط تخمین بزنیم با در نظر گرفتن یک پنجره با عرض کوچک h با مرکز x، یعنی 

مثال

📌 تعیین اپسیلون و  

این یک سوال دشوار است زیرا الگوریتم DBSCAN به پارامترهای اولیه خود بسیار حساس است. بنابراین، اگر مقادیر اپسیلون و z را حتی کمی تغییر دهید، الگوریتم شما می تواند نتایج بسیار متفاوتی تولید کند. این یکی از معایب این الگوریتم است. اما شما می توانید این ارزش ها را عاقلانه انتخاب کنید اگر دانش دامنه مناسب داشته باشید. به عنوان یک قاعده کلی، اگر تعداد زیادی مثال داشته باشید، می توانید z را به ترتیب ابعاد خود انتخاب کنید. اگر شما با 10 ابعاد کار می کنید، بهتر است مقدار z نزدیک به 10 مانند 12 یا 15 را انتخاب کنید. 

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

بنابراین، شما یک ارایه فاصله و i خواهید داشتهفتم ورودی در این ارایه فاصله 5 را نشان می دهدهفتم همسایه Iهفتم نقطه داده. و سپس شما این ارایه فاصله را مرتب می کنید و می خواهید ان را به این شکل رسم کنید. در محورشما فقط فاصله خواهید داشت و در محورشاخص (i) را خواهید داشت. 

در حالت ایده ال، شما باید یک نمودار مانند این دریافت کنید 

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

نمونه خوشه بندی موفق :  

مقاوم در برابر نویز  می تواند خوشه هایی با اشکال و اندازه های مختلف را اداره کند 

نمونه خوشه بندی نا موفق :  

نمی تواند چگالی های مختلف را تحمل کند  حساس به پارامترهاتعیین مجموعه صحیح پارامترها سخت است 

مثال پایتونی

				
					import matplotlib.pyplot as plt 

import numpy as np 

from sklearn.cluster import DBSCAN 

from sklearn import metrics 

from sklearn.datasets import make_blobs 

from sklearn.preprocessing import StandardScaler 

from sklearn import datasets 

# Load data in X 

X, y_true = make_blobs(n_samples=300, centers=4, 

cluster_std=0.50, random_state=0) 

db = DBSCAN(eps=0.3, min_samples=10).fit(X) 

core_samples_mask = np.zeros_like(db.labels_, dtype=bool)                                 

core_samples_mask[db.core_sample_indices_] = True 

labels = db.labels_ 

# Number of clusters in labels, ignoring noise if present. 

n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0) 

  

# Plot result 

# Black removed and is used for noise instead. 

unique_labels = set(labels) 

colors = ['y', 'b', 'g', 'r'] 

print(colors) 

for k, col in zip(unique_labels, colors): 

if k == -1: 

# Black used for noise. 

col = 'k' 

class_member_mask = (labels == k) 

xy = X[class_member_mask & core_samples_mask] 

plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col, 

markeredgecolor='k', 

markersize=6) 

xy = X[class_member_mask & ~core_samples_mask] 

plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col, 

markeredgecolor='k', 

markersize=6) 

plt.title('number of clusters: %d' % n_clusters_) 

plt.show() 
				
			

بینش های مرتبط

بینش‌های‌ ناب