موضوع مقاله: DBSCAN | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # DBSCAN | مقدمه: DBSCAN یک روش خوشه‌بندی است که توسط مارتین اِستر، هانس-پتر کریگل، یورگ ساندر و شیائووی شو در ۱۹۹۶ میلادی (۱۳۷۵ شمسی) ارائه گردیده‌است. | ## بخش 1: DBSCAN | این روش یک الگوریتم بر پایه چگالی نقاط است، به این صورت که نقاطی را که به هم نزدیک هستند را در یک خوشه قرار می‌دهد و نقاطی را نیز که نزدیک به نقاط دیگر نیستند و در منطقه که چگالی کمی دارد، قرار دارند را داده‌ی پرت در نظر می‌گیرند. مزیت این روش به نسبت روش‌ های دیگری خوشه‌بندی مانند خوشه‌بندی K-means این است که نسبت به شکل داده‌ها حساس نمی‌باشد و می‌تواند اشکال غیر منظم را نیز در داده‌ها تشخیص دهد، همچنین نیاز به تعیین تعداد خوشه‌ها نیز ندارد و الگوریتم تعداد دسته‌های مناسب را خودش تشخیص می‌دهد. خلاصه الگوریتم مجموعه‌ای از نقاط را در فضا در نظر بگیرید که باید دسته بندی شوند. فرض کنید پارامتری باشد که شعاع یک همسایگی را مشخص می کند، و پارامتر حداقل تعداد یک خوشه را تعیین می‌کند. در خوشه بندی DBSCAN، نقاط به عنوان نقاط هسته ، نقاط قابل دسترسی و نقاط پرت طبقه بندی می شوند، که نحوه تعیین این نقاط توسط این الگوریتم به شرح زیر است: نقطه یک نقطه هسته است اگر حداقل نقاط (شامل ) در فاصله از آن باشند. نقطه از قابل دسترسی است اگر مسیر با و وجود داشته باشد، که در آن هر مستقیماً از قابل دسترسی است. توجه داشته باشید که با توجه به تعریف مستقیماً قابل دسترسی بودن می‌توان گفت تمام نقاط این مسیر بجز باید نقاط هسته باشند. تمام نقاطی که از هیچ نقطه هسته دیگری قابل دسترسی نیستند، نقاط پرت یا نویز محسوب می‌شوند. حال اگر یک نقطه هسته باشد، آنگاه با تمام نقاطی که از آن قابل دسترسی است، یک خوشه تشکیل می دهد. همچنین نقاط غیر هسته ای که جزو نقاط پرت نیستند، می توانند بخشی از یک خوشه باشند و به نوعی "مرز" آن را تشکیل می دهند، زیرا نمی توان از آنها برای رسیدن به نقاط بیشتر استفاده کرد. نقطه A و سایر نقاط قرمز، نقاط هسته هستند، زیرا ناحیه اطراف این نقاط در شعاع حداقل 4 نقطه (از جمله خود نقطه) را شامل می شود. نقاط B و C نقاط هسته نیستند، بلکه از A (از طریق سایر نقاط هسته) قابل دسترسی هستند و بنابراین به همان خوشه نیز تعلق دارند و نقطه مرز این خوشه هستند. نقطه N یک نقطه نویز است که نه یک نقطه هسته است و نه به طور مستقیم از هیچ نقطه دیگری قابل دسترسی است. | ## بخش 2: DBSCAN | باید توجه کرد که قابلیت دسترسی یک رابطه متقارن نیست: طبق تعریف، فقط نقاط هسته می توانند به نقاط غیر هسته ای برسند و برعکس آن درست نیست. بنابراین ممکن است یک نقطه غیر هسته ای قابل دسترسی باشد در نتیجه نقطه‌ای مانند وجود دارد که به آن دسترسی داشته باشد اما از آنجایی که نقطه غیر هسته‌ای است هیچ نقطه دیگری (مانند ) به آن دسترسی ندارد. به همین دلیل، مفهوم بهتری برای تعریف رسمی نقاط درون خوشه های یافت شده توسط DBSCAN نیاز است. حال مفهموم متصل شده از طریق چگالی را برای این منظور تعریف می‌کنیم، به این شکل که اگر نقطه وجود داشته باشد که هر دو نقطه و از مسقیم قابل دسترسی باشند، آنگاه دو نقطه و از طریق چگالی متصل شده‌اند، که مفهموم تعریف شده متقارن است. حال با توجه به تعریف بالا یک خوشه دو ویژگی را برآورده می کند: تمام نقاط درون خوشه از طریق چگالی به هم متصل هستند. اگر نقطه‌ای از نقطه‌ای درون خوشه از طریق چگالی متصل باشد، آن نقطه هم بخشی از خوشه است. جزییات الگوریتم برای تشریح الگوریتم، نیازمند آشنایی با پارامترهای ε و μ می‌باشد که توضیح داده می‌شود: هر نقطه از داده با نقاط دیگر در فضا فاصله‌ای دارد. هر نقطه‌ای که فاصله اش با یک نقطه مفروض کمتر از (ε (EPS باشد به عنوان همسایه آن نقطه حساب می‌شود. شعاع همسایگی ε این نقطه بررسی می‌شود، و اگر به اندازه MinPts نقطه در این همسایگی وجود داشته باشد، یک خوشه شروع می‌شود. توجه داشته باشید که بعداً ممکن است در شعاع همسایگی ε این نقطه یک نقطه عضو یک خوشه شود در نتیجه این نقطه نیز در آن زمان می‌توان عضو آن خوشه شود و برچسب نویز آن عوض شود. حال مفهموم اتصال از طریق چگالی را برای این منظور تعریف می‌کنیم که بالاتر در مورد آن توضیح داده شد. حال اگر نقطه ای به عنوان بخشی از یک خوشه در نظر گرفته شود، نقاط در همسایگی ε آن نیز بخشی از آن خوشه هستند. به همین ترتیب خوشه گسترش می‌یابد و نقاطی که در شعاع همسایگی ε نقاط جدید هستند نیز به خوشه اضافه می‌شوند و این کار ادامه پیدا می‌کند تا جایی که نقطه جدیدی برای آن خوشه پیدا نکنیم. | ## بخش 3: DBSCAN | حال نقطه تصادفی دیگری را انتخاب می‌کنیم و این کار را تا جایی ادامه می‌دهیم تا زمانی که تمامی نقاط دیده‌شوند و خوشه بندی کامل شود. حتی می تواند خوشه ای را پیدا کند که به طور کامل توسط یک خوشه متفاوت احاطه شده است. البته این خوشه‌ها نباید به هم متصل باشند، با این وجود با افزایش پارامتر MinPts خطای حاصل از متصل بودن نقاط خوشه‌های مختلف کاهش می یابد. DBSCAN فقط به دو پارامتر نیاز دارد و عمدتاً به ترتیب نقاط در پایگاه داده حساس نیست. (با این حال، نقاطی که در مرز دو خوشه مختلف قرار دارند، ممکن است در صورت تغییر ترتیب نقاط، در خوشه متفاوتی قرار بگیرند. ) DBSCAN برای استفاده با پایگاه های داده ای طراحی شده است که می تواند پرس و جوهای با توجه به منطقه‌های فضای داده‌ها را تسریع کند، به عنوان مثال با استفاده از R* tree. پارامترهای MinPts و ε را می توان توسط متخصصی که نوع قرار گیری داده‌ها را در فضا می‌داند تنظیم کرد. معایب DBSCAN کاملاً قطعی نیست: نقاط مرزی که از بیش از یک خوشه قابل دسترسی هستند، بسته به ترتیبی که داده ها پردازش می شوند، می توانند در هرکدام از این خوشه‌ها قرار بگیرند. برای اکثر مجموعه‌ داده‌ها، این وضعیت ایجاد نمی‌شود و این مورد تاثیر کمی بر خوشه بندی داده‌ها دارد. الگوریتم DBSCAN* با تغییر جزیی در این الگوریتم بدست می‌آید به این صورت که در الگوریتم DBSCAN*، نقاط مرزی به عنوان نویز در نظر گرفته می‌شوند و به این ترتیب به یک نتیجه کاملاً قطعی بدست می‌آبد. اما برای بعضی داده‌ها به خصوص برای داده‌های با ابعاد بالا ، این معیار فاصله تقریبا می‌تواند به دلیل مشکلی به نام « نفرین ابعاد » بی‌فایده باشد، که یافتن مقدار مناسب برای ε را دشوار می‌کند. با این حال، این اثر در هر الگوریتم‌های دیگر خوشه بندی بر اساس فاصله اقلیدسی نیز وجود دارد. DBSCAN نمی تواند مجموعه داده‌ها با چگالی‌های بسیار متفاوت را به خوبی خوشه بندی کند، زیرا برای نوع داده‌ی چگال باید MinPts زیاد باشد و برای داده‌های با چگالی کم باید MinPts کم باشد که خوشه بندی آن‌ها به خوبی انجام شود، که در نتیجه نمی‌توان مقدار مناسبی برای این پارامتر پیدا کرد. | ## جمع‌بندی | اگر داده ها و نوع قرار گیری آن‌ها در فضا به خوبی درک نشده باشد، انتخاب یک شعاع ε خوب می تواند دشوار باشد.