الگوریتم OPTICS

**نقاط ترتیب برای شناسایی ساختار خوشه‌بندی** ( **OPTICS** ) الگوریتمی برای یافتن خوشه‌های  مبتنی بر چگالی در داده‌های مکانی است. توسط Mihael Ankerst، Markus M. Breunig، Hans-Peter Kriegel و Jörger ارائه شد.  ایده اصلی آن شبیه به DBSCAN است،  اما به یکی از ضعف های اصلی DBSCAN می پردازد: مشکل تشخیص خوشه های معنی دار در داده هایی با چگالی متفاوت. برای انجام این کار، نقاط پایگاه داده (به صورت خطی) به گونه ای مرتب می شوند که نزدیکترین نقاط از نظر مکانی به همسایگی در ترتیب تبدیل می شوند. علاوه بر این، برای هر نقطه یک فاصله ویژه ذخیره می شود که نشان دهنده چگالی است که باید برای یک خوشه پذیرفته شود تا هر دو نقطه متعلق به یک خوشه باشند. این به عنوان دندروگرام نشان داده می شود.

## ایده اولیه
مانند الگوریتم DBSCAN به دو پارامتر نیاز داریم: *ε که نشان دهنده ی حداکثر فاصله برای در نظر گرفتن داده ها می باشد؛ MinPts که حداقل تعداد داده در فاصله گفته شده را مشخص می کند که برای ایجاد خوشه لازم می باشد. یک نقطه یا داده را *'نقطه اصلی (core point)** گوییم اگر  MinPts نقطه در فاصله  ε از همسایگی آن وجود داشته باشد. برای اندازه گیری این مقدار پارامتر به شکل (<math>N_\varepsilon(p)</math>) در نظر گرفته می شود که نشان دهنده ی تعداد نقاط در فاصله ε برای نقطه p می باشد. همچنین پارامتر **فاصله اصلی(core distance)** برای هر نقطه تعیین می شود که نشان دهنده ی فاصله ی p تا نقطه شما MinPts  نزدیکترین نقاط می باشد:''
:<math>\text{core-dist}_\mathit{\varepsilon,MinPts}(p)=
\begin{cases}
\text{UNDEFINED} & \text{if } |N_\varepsilon(p)| < \mathit{MinPts}\\ 
\mathit{MinPts}\text{-th smallest distance in } N_\varepsilon(p) & \text{otherwise}
\end{cases}</math>
برای نقطه o، **فاصله دسترسی (*reachability distance*)** به نقطه p به شکل حداکثر فاصله مستقیم o از p یا فاصله ی اصلی p تعریف می شود. به شکل زیر:
:<math>\text{reachability-dist}_\mathit{\varepsilon,MinPts}(o,p) = 
\begin{cases}
\text{UNDEFINED} & \text{if } |N_\varepsilon(p)| < \mathit{MinPts}\\ 
\max(\text{core-dist}_\mathit{\varepsilon,MinPts}(p), \text{dist}(p,o)) & \text{otherwise}
\end{cases}</math>
اگر خوشه به اندازه کافی متراکم نباشد طبق تعریف پارامتر ها، فاصله دسترسی و فاصله اصلی تعریف نمی شوند. هرچند اگر ''ε را به اندازه کافی بزرگ انتخاب کنیم می توانیم از بروز این مشکل جلوگیری کنیم اما باید در نظر داشت که ممکن است با بزرگ شدن ε برای محاسبه پرس و جوی همسایگی   با توجه به فاصله، تمام داده های موجود در نظر گرفته شود و محاسبات زمانی آن به <math>O(n^2)</math> تغییر یابد که مطلوب نیست؛ بنابراین باید ε را خیلی بزرگ یا خیلی کوچک در نظر نگرفت تا از ایجاد مشکلات گفته شده جلوگیری کرد.''

پارامتر **' ، به طور دقیق، ضروری نیست. به سادگی می توان آن را روی حداکثر مقدار ممکن تنظیم کرد. با این حال، زمانی که یک شاخص فضایی در دسترس باشد، نقش عملی را با توجه به پیچیدگی ایفا می کند. OPTICS با حذف این پارامتر از DBSCAN انتزاع می‌کند، حداقل تا حدی که باید حداکثر مقدار را بدهد.

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

                                                       **function** OPTICS(DB, ε, MinPts) **is**
                                                           **for each** point p of DB **do**
                                             p.reachability-distance = UNDEFINED
                                               **for each** unprocessed point p of DB **do**
                                                          N = getNeighbors(p, ε)
                                                             mark p as processed
                                                    output p to the ordered list
                                **if** core-distance(p, ε, MinPts) != UNDEFINED **then**
                                                Seeds = empty priority queue
                                              update(N, p, Seeds, ε, MinPts)
                                                 **for each** next q in Seeds **do**
                                                 N' = getNeighbors(q, ε)
                                                     mark q as processed
                                            output q to the ordered list
                          **if** core-distance(q, ε, MinPts) != UNDEFINED **do**
                                     update(N', q, Seeds, ε, MinPts)
در تابع آپدیت، هر کدام از اعضای صف اولویت توسط ε تا از همسایه های p و q آپدیت می شوند:
                                                **function** update(N, p, Seeds, ε, MinPts) **is**
                                             coredist = core-distance(p, ε, MinPts)
                                                                    **for each** o in N
                                                  **if** o is not processed **then**
                               new-reach-dist = max(coredist, dist(p,o))
       **if** o.reachability-distance == UNDEFINED **then** // o is not in Seeds   
                            o.reachability-distance = new-reach-dist
                                     Seeds.insert(o, new-reach-dist)
                 **else**               // o in Seeds, check for improvement
                    **if** new-reach-dist \varepsilon و پارامترهای  . در اینجا مقدار 0.1 ممکن است نتایج خوبی به همراه داشته باشد)، یا توسط الگوریتم‌های مختلفی که سعی می‌کنند دره‌ها را با شیب زیاد، تشخیص زانو یا حداکثر محلی تشخیص دهند. خوشه‌بندی‌هایی که از این طریق به دست می‌آیند معمولاً سلسله مراتبی هستند و با یک اجرای DBSCAN قابل دستیابی نیستند.

## پیچیدگی الگوریتم
همانند الگوریتم DBSCAN، الگوریتم OPTICS فرآیند را برای هر داده یکبار انجام می دهد و برای هر یک، پردازش را روی ε همسایه انجام می دهد پس برای هر داده پیچیدگی اجرا O(\log n) می باشد که با داشتن n داده پیچیدگی کلی الگوریتم برابر O(n \cdot \log n) می باشد. نویسندگان مقاله اصلی OPTICS یک ضریب کاهش سرعت ثابت واقعی 1.6 را  در مقایسه با DBSCAN گزارش می دهند. توجه داشته باشید که ارزش \varepsilon ممکن است به شدت بر هزینه الگوریتم تأثیر بگذارد، زیرا یک مقدار خیلی بزرگ ممکن است هزینه یک پرس و جوی همسایگی را به پیچیدگی خطی برساند.

## منابع

رده:الگوریتم‌های دسته‌بندی
رده:دسته‌بندی داده
رده:یادگیری ماشین
رده:روش‌های خوشه‌بندی