موضوع مقاله: الگوریتم OPTICS | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم OPTICS | مقدمه: نقاط ترتیب برای شناسایی ساختار خوشه‌بندی ( OPTICS ) الگوریتمی برای یافتن خوشه‌های مبتنی بر چگالی در داده‌های مکانی است. | ## بخش 1: الگوریتم OPTICS | برای انجام این کار، نقاط پایگاه داده (به صورت خطی) به گونه ای مرتب می شوند که نزدیکترین نقاط از نظر مکانی به همسایگی در ترتیب تبدیل می شوند. علاوه بر این، برای هر نقطه یک فاصله ویژه ذخیره می شود که نشان دهنده چگالی است که باید برای یک خوشه پذیرفته شود تا هر دو نقطه متعلق به یک خوشه باشند. ایده اولیه مانند الگوریتم DBSCAN به دو پارامتر نیاز داریم: ε که نشان دهنده ی حداکثر فاصله برای در نظر گرفتن داده ها می باشد؛ MinPts که حداقل تعداد داده در فاصله گفته شده را مشخص می کند که برای ایجاد خوشه لازم می باشد. برای اندازه گیری این مقدار پارامتر به شکل در نظر گرفته می شود که نشان دهنده ی تعداد نقاط در فاصله ε برای نقطه p می باشد. به شکل زیر: اگر خوشه به اندازه کافی متراکم نباشد طبق تعریف پارامتر ها، فاصله دسترسی و فاصله اصلی تعریف نمی شوند. هرچند اگر ε را به اندازه کافی بزرگ انتخاب کنیم می توانیم از بروز این مشکل جلوگیری کنیم اما باید در نظر داشت که ممکن است با بزرگ شدن ε برای محاسبه پرس و جوی همسایگی با توجه به فاصله، تمام داده های موجود در نظر گرفته شود و محاسبات زمانی آن به تغییر یابد که مطلوب نیست؛ بنابراین باید ε را خیلی بزرگ یا خیلی کوچک در نظر نگرفت تا از ایجاد مشکلات گفته شده جلوگیری کرد. | ## بخش 2: الگوریتم OPTICS | با این حال، زمانی که یک شاخص فضایی در دسترس باشد، نقش عملی را با توجه به پیچیدگی ایفا می کند. کد روش اولیه ی الگوریتم مانند الگوریتم DBSCAN اما در اینجا به جای قرار دادن اعضای یک مجموعه که شناخته شده اما پردازش نشده اند داخل مجموعه، از یک صف اولویت برای حفظ آنها استفاده می کنیم. این یک نمودار دوبعدی است، با ترتیب نقاط به صورت پردازش شده توسط OPTICS در محور x و فاصله دسترسی در محور y. از آنجایی که نقاط متعلق به یک خوشه فاصله دستیابی کمی به نزدیکترین همسایه خود دارند، خوشه ها به صورت دره هایی در نمودار دسترس پذیری نشان داده می شوند. اما به خوبی قابل مشاهده است که چگونه دره ها در نمودار با خوشه های موجود در مجموعه داده های بالا مطابقت دارند. نقاط زرد رنگ در این تصویر به عنوان نویز در نظر گرفته می شوند و هیچ دره ای در طرح دسترسی آنها یافت نمی شود. | ## بخش 3: الگوریتم OPTICS | آنها معمولاً به خوشه‌ها اختصاص داده نمی‌شوند، به جز خوشه همه‌جانبه «همه داده‌ها» در یک نتیجه سلسله مراتبی. استخراج خوشه ها از این نمودار را می توان به صورت دستی با انتخاب یک محدوده در محور x پس از بازرسی بصری، با انتخاب یک آستانه در محور y انجام داد (نتیجه پس از آن شبیه به یک نتیجه خوشه بندی DBSCAN با همان نتیجه است. در اینجا مقدار 0.1 ممکن است نتایج خوبی به همراه داشته باشد)، یا توسط الگوریتم‌های مختلفی که سعی می‌کنند دره‌ها را با شیب زیاد، تشخیص زانو یا حداکثر محلی تشخیص دهند. خوشه‌بندی‌هایی که از این طریق به دست می‌آیند معمولاً سلسله مراتبی هستند و با یک اجرای DBSCAN قابل دستیابی نیستند. پیچیدگی الگوریتم همانند الگوریتم DBSCAN، الگوریتم OPTICS فرآیند را برای هر داده یکبار انجام می دهد و برای هر یک، پردازش را روی ε همسایه انجام می دهد پس برای هر داده پیچیدگی اجرا می باشد که با داشتن n داده پیچیدگی کلی الگوریتم برابر می باشد. | ## جمع‌بندی | توجه داشته باشید که ارزش ممکن است به شدت بر هزینه الگوریتم تأثیر بگذارد، زیرا یک مقدار خیلی بزرگ ممکن است هزینه یک پرس و جوی همسایگی را به پیچیدگی خطی برساند.