DBSCAN

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

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

خلاصه الگوریتم

[ویرایش]

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

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

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

در این نمودار، MinPts = 4 است. نقطه A و سایر نقاط قرمز، نقاط هسته هستند، زیرا ناحیه اطراف این نقاط در شعاع ε حداقل 4 نقطه (از جمله خود نقطه) را شامل می شود. از آنجا که همه آنها از یکدیگر قابل دسترسی هستند، یک خوشه واحد را تشکیل می دهند. نقاط B و C نقاط هسته نیستند، بلکه از A (از طریق سایر نقاط هسته) قابل دسترسی هستند و بنابراین به همان خوشه نیز تعلق دارند و نقطه مرز این خوشه هستند. نقطه N یک نقطه نویز است که نه یک نقطه هسته است و نه به طور مستقیم از هیچ نقطه دیگری قابل دسترسی است.

باید توجه کرد که قابلیت دسترسی یک رابطه متقارن نیست: طبق تعریف، فقط نقاط هسته می توانند به نقاط غیر هسته ای برسند و برعکس آن درست نیست. بنابراین ممکن است یک نقطه غیر هسته ای قابل دسترسی باشد در نتیجه نقطه‌ای مانند pi وجود دارد که به آن دسترسی داشته باشد اما از آنجایی که نقطه غیر هسته‌ای است هیچ نقطه دیگری (مانند pi) به آن دسترسی ندارد. به همین دلیل، مفهوم بهتری برای تعریف رسمی نقاط درون خوشه های یافت شده توسط 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++ پیاده‌سازی شده‌است ولی اکنون پیاده‌سازی‌های زیادی از آن وجود دارند:

منابع

[ویرایش]
  1. ↑ Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). انجمن پیشبرد هوش مصنوعی. pp. 226–231. CiteSeerX 10.1.1.121.9220. ISBN 1-57735-004-9.
  2. ↑ «نسخه آرشیو شده». بایگانی‌شده از اصلی در ۷ مارس ۲۰۱۶. دریافت‌شده در ۱۰ نوامبر ۲۰۱۵.
  3. ↑ Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (July 2017). "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN". ACM Trans. Database Syst. 42 (3): 19:1–19:21. doi:10.1145/3068335. ISSN 0362-5915.
  4. ↑ Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (July 2017). "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN". ACM Trans. Database Syst. 42 (3): 19:1–19:21. doi:10.1145/3068335. ISSN 0362-5915.
  5. ↑ Kriegel, Hans-Peter; Kröger, Peer (2011). "Density-based Clustering". WIREs Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30. Archived from the original on 2016-11-17. Retrieved 2011-12-12.