بهبود پیچیدگی زمانی الگوریتم DBSCAN با تلفیق شبکه های توری

خوشه بندی یکی از مسائل مهم در پردازش داده ها و داده- کاوی است که هدف اصلی آن پیدا کردن نمونه های مشابه در داده ها است. الگوریتم های خوشه بندی متنوعی وجود دارد. تفاوت الگوریتم ها در رویکرد خوشه بندی و مقیاس شباهتی است که استفاده می کنند. در میان این الگوریتم ها DBSCAN یکی از محبوبترین الگوریتم های چگالی محور است. این روش قادر است که نمونه های آموزشی را با شکل های مختلف شناسایی کند و به همین دلیل کاربردهای بسیار زیادی دارد. اگرچه این الگوریتم، مزایای خاص خود را دارد، اما دو نقطه ضعف مهم دارد. اول اینکه برای پایگاه داده های بسیار بزرگ کارایی مناسبی ندارد، دوم آنکه تعیین کردن پارامترهای eps و MinPts برای به دست آوردن خوشه بندی بهینه کار سختی است. برای حل این مشکلات، در این مقاله یک نوع دیگر از الگوریتم DBSCAN به نام GM2-DBSCAN ارائه شده است که از شبکه بندی و پارامترهای محلی برای حل مشکلات مذکور بهره می برد. با آزمایش الگوریتم جدید روی چندین مجموعه داده مختلف نشان داده شده است که الگوریتم از کارایی بالایی در تشخیص خوشه ها برخوردار بوده و همزمان پیچیدگی زمانی آن نسبت به الگوریتم DBSCAN کمتر است.

Keywords:

داده کاوی , خوشه بندی , DBSCAN , خوشه بندی شبکه محور , خوشه بندی چگالی محور