DBSCAN - ویکی‌پدیا، دانشنامهٔ آزاد

این مقاله نیازمند ویکی‌سازی است. لطفاً با توجه به راهنمای ویرایش و شیوه‌نامه، محتوای آن را بهبود بخشید.

یادگیری ماشین و داده‌کاوی
موضوع‌ها طبقه‌بندی آماری خوشه‌بندی تحلیل رگرسیون روش تشخیص ناهنجاری یادگیری قانون وابستگی یادگیری تقویتی پیش بینی ساختاریافته مهندسی ویژگی یادگیری ویژگی یادگیری ماشین برخط یادگیری نیمه‌نظارتی یادگیری بی‌نظارت Learning to rank Grammar induction
یادگیری با نظارت (طبقه‌بندی آماری • تحلیل رگرسیون) یادگیری درخت تصمیم Ensembles (تکنیک بگینگ, بوستینگ، جنگل تصادفی) k-NN رگرسیون خطی دسته‌بندی کننده بیز ساده شبکه‌های عصبی مصنوعی رگرسیون لجستیک پرسپترون ماشین بردار مرتبط (RVM) ماشین بردار پشتیبانی
خوشه‌بندی کاهش و خوشه‌بندی ترازمند و بازکردی با بهره‌گیری از رده‌بندی خوشه‌بندی سلسله‌مراتبی خوشه‌بندی کی-میانگین الگوریتم امید ریاضی–بیشینه کردن DBSCAN OPTICS انتقال میانگین
کاهش ابعاد تحلیل عاملی CCA تحلیل مؤلفه‌های مستقل آنالیز افتراقی خطی فاکتورگیری نامنفی ماتریس تحلیل مؤلفه‌های اصلی t-SNE
پیش‌بینی ساختاریافته مدل‌های گرافیکی (شبکه‌های بیزی، میدان تصادفی شرطی، مدل پنهان مارکف)
روش تشخیص ناهنجاری الگوریتم کی-نزدیکترین همسایه فاکتور پرتی محلی
شبکه عصبی مصنوعی خودرمزگذار یادگیری عمیق پرسپترون چندلایه RNN ماشین بولتزمن محدود شده ترانسفورمر بینایی SOM شبکه عصبی پیچشی
یادگیری تقویتی کیو-یادگیری SARSA یادگیری تفاوت زمانی
نظریه Bias-variance dilemma نظریه یادگیری محاسباتی Empirical risk minimization Occam learning یادگیری احتمالا تقریبا صحیح Statistical learning VC theory
حوزه‌های یادگیری ماشین NIPS ICML ML JMLR ArXiv:cs.LG
ن ب و

DBSCAN یک روش خوشه‌بندی است که توسط مارتین اِستر، هانس-پتر کریگل، یورگ ساندر و شیائووی شو در ۱۹۹۶ میلادی (۱۳۷۵ شمسی) ارائه گردیده‌است. این روش یک الگوریتم بر پایه چگالی نقاط است، به این صورت که نقاطی را که به هم نزدیک هستند را در یک خوشه قرار می‌دهد و نقاطی را نیز که نزدیک به نقاط دیگر نیستند و در منطقه که چگالی کمی دارد، قرار دارند را داده‌ی پرت در نظر می‌گیرند. ^[۱] مزیت این روش به نسبت روش‌ های دیگری خوشه‌بندی مانند خوشه‌بندی K-means این است که نسبت به شکل داده‌ها حساس نمی‌باشد و می‌تواند اشکال غیر منظم را نیز در داده‌ها تشخیص دهد، همچنین نیاز به تعیین تعداد خوشه‌ها نیز ندارد و الگوریتم تعداد دسته‌های مناسب را خودش تشخیص می‌دهد.^[۲]

خلاصه الگوریتم[ویرایش]

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

• نقطه p یک نقطه هسته است اگر حداقل نقاط MinPts (شامل p ) در فاصله ε از آن باشند.
• نقطه q مستقیماً از p قابل دسترسی است اگر نقطه q در فاصله ε از نقطه هسته p باشد. نقاط فقط می‌توانند از نقاط هسته مستقیماً قابل دسترسی باشند.
• نقطه q از p قابل دسترسی است اگر مسیر p₁, ..., p_n با p₁ = p و p_n = q وجود داشته باشد، که در آن هر p_i+1 مستقیماً از p_i قابل دسترسی است. توجه داشته باشید که با توجه به تعریف مستقیماً قابل دسترسی بودن می‌توان گفت تمام نقاط این مسیر بجز q باید نقاط هسته باشند.
• تمام نقاطی که از هیچ نقطه هسته دیگری قابل دسترسی نیستند، نقاط پرت یا نویز محسوب می‌شوند.

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

باید توجه کرد که قابلیت دسترسی یک رابطه متقارن نیست: طبق تعریف، فقط نقاط هسته می توانند به نقاط غیر هسته ای برسند و برعکس آن درست نیست. بنابراین ممکن است یک نقطه غیر هسته ای قابل دسترسی باشد در نتیجه نقطه‌ای مانند p_i وجود دارد که به آن دسترسی داشته باشد اما از آنجایی که نقطه غیر هسته‌ای است هیچ نقطه دیگری (مانند p_i) به آن دسترسی ندارد. به همین دلیل، مفهوم بهتری برای تعریف رسمی نقاط درون خوشه های یافت شده توسط DBSCAN نیاز است. حال مفهموم متصل شده از طریق چگالی را برای این منظور تعریف می‌کنیم، به این شکل که اگر نقطه o وجود داشته باشد که هر دو نقطه p و q از o مسقیم قابل دسترسی باشند، آنگاه دو نقطه p و q از طریق چگالی متصل شده‌اند، که مفهموم تعریف شده متقارن است.

حال با توجه به تعریف بالا یک خوشه دو ویژگی را برآورده می کند:

1. تمام نقاط درون خوشه از طریق چگالی به هم متصل هستند.
2. اگر نقطه‌ای از نقطه‌ای درون خوشه از طریق چگالی متصل باشد، آن نقطه هم بخشی از خوشه است.

جزییات الگوریتم[ویرایش]

برای تشریح الگوریتم، نیازمند آشنایی با پارامترهای ε و μ می‌باشد که توضیح داده می‌شود:

• هر نقطه از داده با نقاط دیگر در فضا فاصله‌ای دارد. هر نقطه‌ای که فاصله اش با یک نقطه مفروض کمتر از (ε (EPS باشد به عنوان همسایه آن نقطه حساب می‌شود.
• هر نقطه مفروض که (μ (MinPoints همسایه داشته باشد، یک نقطه مرکزی است.

اجرای الگوریتم با یک نقطه دلخواه شروع می شود که بازدید نشده است. شعاع همسایگی ε این نقطه بررسی می‌شود، و اگر به اندازه MinPts نقطه در این همسایگی وجود داشته باشد، یک خوشه شروع می‌شود. در غیر این صورت، نقطه به عنوان نویز برچسب گذاری می شود. توجه داشته باشید که بعداً ممکن است در شعاع همسایگی ε این نقطه یک نقطه عضو یک خوشه شود در نتیجه این نقطه نیز در آن زمان می‌توان عضو آن خوشه شود و برچسب نویز آن عوض شود. حال مفهموم اتصال از طریق چگالی را برای این منظور تعریف می‌کنیم که بالاتر در مورد آن توضیح داده شد. حال اگر نقطه ای به عنوان بخشی از یک خوشه در نظر گرفته شود، نقاط در همسایگی ε آن نیز بخشی از آن خوشه هستند. به همین ترتیب خوشه گسترش می‌یابد و نقاطی که در شعاع همسایگی ε نقاط جدید هستند نیز به خوشه اضافه می‌شوند و این کار ادامه پیدا می‌کند تا جایی که نقطه جدیدی برای آن خوشه پیدا نکنیم. حال نقطه تصادفی دیگری را انتخاب می‌کنیم و این کار را تا جایی ادامه می‌دهیم تا زمانی که تمامی نقاط دیده‌شوند و خوشه بندی کامل شود.

این الگوریتم را می‌توان به صورت شبه کد مانند زیر بیان کرد: ^[۳]

DBSCAN(D, eps, MinPts) {  C = ۰  for each point P in dataset D {  if P is visited  continue next point  mark P as visited  NeighborPts = regionQuery(P, eps)  if sizeof(NeighborPts) <MinPts  mark P as NOISE  else {  C = next cluster  expandCluster(P, NeighborPts, C, eps, MinPts)  }  } } 

expandCluster(P, NeighborPts, C, eps, MinPts) {  add P to cluster C  for each point P' in NeighborPts {  if P' is not visited {  mark P' as visited  NeighborPts' = regionQuery(P', eps)  if sizeof(NeighborPts')>= MinPts  NeighborPts = NeighborPts joined with NeighborPts'  }  if P' is not yet member of any cluster  add P' to cluster C  } }  regionQuery(P, eps)  return all points within P's eps-neighborhood (including P) 

مزایا[ویرایش]

1. DBSCAN بر خلاف k-means نیازی به تعیین تعداد خوشه ها در داده ها ندارد.
2. DBSCAN می تواند خوشه هایی با شکل دلخواه پیدا کند. حتی می تواند خوشه ای را پیدا کند که به طور کامل توسط یک خوشه متفاوت احاطه شده است. البته این خوشه‌ها نباید به هم متصل باشند، با این وجود با افزایش پارامتر MinPts خطای حاصل از متصل بودن نقاط خوشه‌های مختلف کاهش می یابد.
3. DBSCAN مفهمو نویز را در خود دارد و نسبت به داده‌های پرت مقاوم است.
4. DBSCAN فقط به دو پارامتر نیاز دارد و عمدتاً به ترتیب نقاط در پایگاه داده حساس نیست. (با این حال، نقاطی که در مرز دو خوشه مختلف قرار دارند، ممکن است در صورت تغییر ترتیب نقاط، در خوشه متفاوتی قرار بگیرند. )
5. DBSCAN برای استفاده با پایگاه های داده ای طراحی شده است که می تواند پرس و جوهای با توجه به منطقه‌های فضای داده‌ها را تسریع کند، به عنوان مثال با استفاده از R* tree.
6. پارامترهای MinPts و ε را می توان توسط متخصصی که نوع قرار گیری داده‌ها را در فضا می‌داند تنظیم کرد.

معایب[ویرایش]

1. DBSCAN کاملاً قطعی نیست: نقاط مرزی که از بیش از یک خوشه قابل دسترسی هستند، بسته به ترتیبی که داده ها پردازش می شوند، می توانند در هرکدام از این خوشه‌ها قرار بگیرند. برای اکثر مجموعه‌ داده‌ها، این وضعیت ایجاد نمی‌شود و این مورد تاثیر کمی بر خوشه بندی داده‌ها دارد.  البته این مشکل فقط برای نقاط مرزی پیش می‌آید.^[۴] الگوریتم DBSCAN* با تغییر جزیی در این الگوریتم بدست می‌آید به این صورت که در الگوریتم DBSCAN*، نقاط مرزی به عنوان نویز در نظر گرفته می‌شوند و به این ترتیب به یک نتیجه کاملاً قطعی بدست می‌آبد.
2. کیفیت DBSCAN به اندازه گیری فاصله مورد استفاده در تابع (regionQuery(P,Q بستگی دارد. متداول ترین معیار فاصله مورد استفاده، فاصله اقلیدسی است. اما برای بعضی داده‌ها به خصوص برای داده‌های با ابعاد بالا ، این معیار فاصله تقریبا می‌تواند به دلیل مشکلی به نام « نفرین ابعاد » بی‌فایده باشد، که یافتن مقدار مناسب برای ε را دشوار می‌کند. با این حال، این اثر در هر الگوریتم‌های دیگر خوشه بندی بر اساس فاصله اقلیدسی نیز وجود دارد.
3. DBSCAN نمی تواند مجموعه داده‌ها با چگالی‌های بسیار متفاوت را به خوبی خوشه بندی کند، زیرا برای نوع داده‌ی چگال باید MinPts زیاد باشد و برای داده‌های با چگالی کم باید MinPts کم باشد که خوشه بندی آن‌ها به خوبی انجام شود، که در نتیجه نمی‌توان مقدار مناسبی برای این پارامتر پیدا کرد.^[۵]
4. اگر داده ها و نوع قرار گیری آن‌ها در فضا به خوبی درک نشده باشد، انتخاب یک شعاع ε خوب می تواند دشوار باشد.

پیاده‌سازی[ویرایش]

این روش در مقاله اصلی با زبان C++ پیاده‌سازی شده‌است ولی اکنون پیاده‌سازی‌های زیادی از آن وجود دارند:

• پیاده‌سازی آپاچی در بسته ریاضی
• پیاده‌سازی در متلب
• پیاده‌سازی برای برنامه Gephi

منابع[ویرایش]