الگوریتم OPTICS

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

ایده اولیه

مانند الگوریتم DBSCAN به دو پارامتر نیاز داریم: ε که نشان دهنده ی حداکثر فاصله برای در نظر گرفتن داده ها می باشد؛ MinPts که حداقل تعداد داده در فاصله گفته شده را مشخص می کند که برای ایجاد خوشه لازم می باشد. یک نقطه یا داده را نقطه اصلی (core point) گوییم اگر MinPts نقطه در فاصله ε از همسایگی آن وجود داشته باشد. برای اندازه گیری این مقدار پارامتر به شکل ($N_{\varepsilon }(p)$) در نظر گرفته می شود که نشان دهنده ی تعداد نقاط در فاصله ε برای نقطه p می باشد. همچنین پارامتر فاصله اصلی(core distance) برای هر نقطه تعیین می شود که نشان دهنده ی فاصله ی p تا نقطه شما MinPts نزدیکترین نقاط می باشد:

${\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}}$

برای نقطه o، فاصله دسترسی (reachability distance) به نقطه p به شکل حداکثر فاصله مستقیم o از p یا فاصله ی اصلی p تعریف می شود. به شکل زیر:

${\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}}$

اگر خوشه به اندازه کافی متراکم نباشد طبق تعریف پارامتر ها، فاصله دسترسی و فاصله اصلی تعریف نمی شوند. هرچند اگر ε را به اندازه کافی بزرگ انتخاب کنیم می توانیم از بروز این مشکل جلوگیری کنیم اما باید در نظر داشت که ممکن است با بزرگ شدن ε برای محاسبه پرس و جوی همسایگی ε با توجه به فاصله، تمام داده های موجود در نظر گرفته شود و محاسبات زمانی آن به $O(n^{2})$ تغییر یابد که مطلوب نیست؛ بنابراین باید ε را خیلی بزرگ یا خیلی کوچک در نظر نگرفت تا از ایجاد مشکلات گفته شده جلوگیری کرد.

پارامتر ε ، به طور دقیق، ضروری نیست. به سادگی می توان آن را روی حداکثر مقدار ممکن تنظیم کرد. با این حال، زمانی که یک شاخص فضایی در دسترس باشد، نقش عملی را با توجه به پیچیدگی ایفا می کند. 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 < o.reachability-distance then
                       o.reachability-distance = new-reach-dist
                               Seeds.move-up(o, new-reach-dist)

استخراج خوشه ها

با استفاده از نمودار دسترسی (نوع ویژه دندروگرام )، ساختار سلسله مراتبی خوشه ها را می توان به راحتی به دست آورد. این یک نمودار دوبعدی است، با ترتیب نقاط به صورت پردازش شده توسط OPTICS در محور x و فاصله دسترسی در محور y. از آنجایی که نقاط متعلق به یک خوشه فاصله دستیابی کمی به نزدیکترین همسایه خود دارند، خوشه ها به صورت دره هایی در نمودار دسترس پذیری نشان داده می شوند. هر چه عمق دره بیشتر باشد، خوشه متراکم تر است.

تصویر بالا این مفهوم را نشان می دهد. در قسمت سمت چپ بالای آن، یک مجموعه داده نمونه مصنوعی نشان داده شده است. قسمت بالا سمت راست درخت پوشا تولید شده توسط OPTICS را تجسم می کند و قسمت پایین نمودار دستیابی را همانطور که توسط OPTICS محاسبه می شود نشان می دهد. رنگ ها در این نمودار برچسب هستند و توسط الگوریتم محاسبه نمی شوند. اما به خوبی قابل مشاهده است که چگونه دره ها در نمودار با خوشه های موجود در مجموعه داده های بالا مطابقت دارند. نقاط زرد رنگ در این تصویر به عنوان نویز در نظر گرفته می شوند و هیچ دره ای در طرح دسترسی آنها یافت نمی شود. آنها معمولاً به خوشه‌ها اختصاص داده نمی‌شوند، به جز خوشه همه‌جانبه «همه داده‌ها» در یک نتیجه سلسله مراتبی.

استخراج خوشه ها از این نمودار را می توان به صورت دستی با انتخاب یک محدوده در محور x پس از بازرسی بصری، با انتخاب یک آستانه در محور y انجام داد (نتیجه پس از آن شبیه به یک نتیجه خوشه بندی DBSCAN با همان نتیجه است. $\varepsilon$ و پارامترهای minPts . در اینجا مقدار 0.1 ممکن است نتایج خوبی به همراه داشته باشد)، یا توسط الگوریتم‌های مختلفی که سعی می‌کنند دره‌ها را با شیب زیاد، تشخیص زانو یا حداکثر محلی تشخیص دهند. خوشه‌بندی‌هایی که از این طریق به دست می‌آیند معمولاً سلسله مراتبی هستند و با یک اجرای DBSCAN قابل دستیابی نیستند.

پیچیدگی الگوریتم

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