DBSCAN چیست؟ توضیح بده.
DBSCAN یک روش خوشه‌بندی است که توسط مارتین اِستر، هانس-پتر کریگل، یورگ ساندر و شیائووی شو در ۱۹۹۶ میلادی (۱۳۷۵ شمسی) ارائه گردیده‌است. این روش یک الگوریتم بر پایه چگالی نقاط است، به این صورت که نقاطی را که به هم نزدیک هستند را در یک خوشه قرار می‌دهد و نقاطی را نیز که نزدیک به نقاط دیگر نیستند و در منطقه که چگالی کمی دارد، قرار دارند را داده‌ی پرت در نظر می‌گیرند. مزیت این روش به نسبت روش‌ های دیگری خوشه‌بندی مانند خوشه‌بندی K-means این است که نسبت به شکل داده‌ها حساس نمی‌باشد و می‌تواند اشکال غیر منظم را نیز در داده‌ها تشخیص دهد، همچنین نیاز به تعیین تعداد خوشه‌ها نیز ندارد و الگوریتم تعداد دسته‌های مناسب را خودش تشخیص می‌دهد.خلاصه الگوریتم.مجموعه‌ای از نقاط را در فضا در نظر بگیرید که باید دسته بندی شوند. فرض کنید "" پارامتری باشد که شعاع یک همسایگی را مشخص می کند، و پارامتر حداقل تعداد یک خوشه را تعیین می‌کند. در خوشه بندی DBSCAN، نقاط به عنوان "نقاط هسته" ، "نقاط قابل دسترسی" و "نقاط پرت" طبقه بندی می شوند، که نحوه تعیین این نقاط توسط این الگوریتم به شرح زیر است:حال اگر "" یک نقطه هسته باشد، آنگاه با تمام نقاطی که از آن قابل دسترسی است، یک "خوشه" تشکیل می دهد. توجه شود که با توجه به این توضیحات هر خوشه باید حداقل شامل یک نقطه هسته باشد. همچنین نقاط غیر هسته ای که جزو نقاط پرت نیستند، می توانند بخشی از یک خوشه باشند و به نوعی "مرز" آن را تشکیل می دهند، زیرا نمی توان از آنها برای رسیدن به نقاط بیشتر استفاده کرد.باید توجه کرد که قابلیت دسترسی یک رابطه متقارن نیست: طبق تعریف، فقط نقاط هسته می توانند به نقاط غیر هسته ای برسند و برعکس آن درست نیست. بنابراین ممکن است یک نقطه غیر هسته ای قابل دسترسی باشد در نتیجه نقطه‌ای مانند وجود دارد که به آن دسترسی داشته باشد اما از آنجایی که نقطه غیر هسته‌ای است هیچ نقطه دیگری (مانند ) به آن دسترسی ندارد. به همین دلیل، مفهوم بهتری برای تعریف رسمی نقاط درون خوشه های یافت شده توسط DBSCAN نیاز است. حال مفهموم متصل شده از طریق چگالی را برای این منظور تعریف می‌کنیم، به این شکل که اگر نقطه ' وجود داشته باشد که هر دو نقطه ' و ' از ' مسقیم قابل دسترسی باشند، آنگاه دو نقطه ' و ' از طریق چگالی متصل شده‌اند، که مفهموم تعریف شده متقارن "است".حال با توجه به تعریف بالا یک خوشه دو ویژگی را برآورده می کند:جزییات الگوریتم.برای تشریح الگوریتم، نیازمند آشنایی با پارامترهای ε و μ می‌باشد که توضیح داده می‌شود:اجرای الگوریتم با یک نقطه دلخواه شروع می شود که بازدید نشده است. شعاع همسایگی ε این نقطه بررسی می‌شود، و اگر به اندازه 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) &lt;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')&gt;= 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)پیاده‌سازی.این روش در مقاله اصلی با زبان C++ پیاده‌سازی شده‌است ولی اکنون پیاده‌سازی‌های زیادی از آن وجود دارند: