OPTICS

Як і DBSCAN, OPTICS вимагає двох параметрів: ${\displaystyle \varepsilon }$, що є максимальною відстанню (радіусом) і ${\displaystyle MinPts}$, що показує мінімальну кількість об'єктів, необхідних для формування кластера. Точка(об'єкт) ${\displaystyle p}$ є ядром, якщо хоча б ${\displaystyle MinPts}$ точок (об'єктів) знаходяться в межах ${\displaystyle \varepsilon }$-відстані ${\displaystyle N_{\varepsilon }(p)}$. Всупереч DBSCAN, OPTICS також розглядає об'єкти, які є частиною більш «щільних» кластерів, так, щоб кожна точка була присвоєна основній відстані до ${\displaystyle MinPts}$th її найближчої точки:

${\displaystyle {\text{core-dist}}_{\varepsilon ,MinPts}(p)}$ ${\displaystyle ={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<MinPts\\MinPts{\text{-th smallest distance to }}N_{\varepsilon }(p)&{\text{otherwise}}\end{cases}}}$

Досяжність до об'єкта ${\displaystyle o}$ від об'єкта ${\displaystyle p}$ знаходиться, як відстань між ${\displaystyle o}$ і ${\displaystyle p}$, або, як основна відстань від ${\displaystyle p}$:

${\displaystyle {\text{reachability-dist}}_{\varepsilon ,MinPts}(o,p)}$ ${\displaystyle ={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<MinPts\\\max({\text{core-dist}}_{\varepsilon ,MinPts}(p),{\text{dist}}(p,o))&{\text{otherwise}}\end{cases}}}$

Якщо ${\displaystyle p}$ і ${\displaystyle o}$ є найближчими сусідами, тобто ${\displaystyle \varepsilon '<\varepsilon }$ ми повинні припускати, що ${\displaystyle p}$ і ${\displaystyle o}$ належать до одного кластеру.

Обидва значення основної відстані і досяжності є невідомими, якщо недоступний кластер достатньої щільності (w.r.t. ${\displaystyle \varepsilon }$). Якщо взяти велике значення ${\displaystyle \varepsilon }$, то цього не станеться, проте тоді кожен запит ${\displaystyle \varepsilon }$-сусідів може повертати навіть всю базу даних, що приведе до складності виконання ${\displaystyle O(n^{2})}$. Отже, параметр ${\displaystyle \varepsilon }$ потрібно вибрати, враховуючи щільність кластерів, які не представляють інтересу, щоб пришвидшити час виконання алгоритму.

Строго кажучи, параметр ${\displaystyle \varepsilon }$ не є необхідним. Він можу бути просто встановленим максимально можливого значення.

Базова реалізація OPTICS схожа до реалізації DBSCAN, але використовується не множина відомих, але не кластеризованих даних, a черга з пріоритетом (з використанням індексації heap) .

OPTICS(DB, eps, MinPts)

    for each point p of DB
       p.reachability-distance = UNDEFINED
    for each unprocessed point p of DB
       N = getNeighbors(p, eps)
       mark p as processed
       output p to the ordered list
       if (core-distance(p, eps, Minpts) != UNDEFINED)
          Seeds = empty priority queue
          update(N, p, Seeds, eps, Minpts)
          for each next q in Seeds
             N' = getNeighbors(q, eps)
             mark q as processed
             output q to the ordered list
             if (core-distance(q, eps, Minpts) != UNDEFINED)
                update(N', q, Seeds, eps, Minpts)

В update(), черга з пріоритетом Seeds заповнена ${\displaystyle \varepsilon }$-сусідами ${\displaystyle p}$ і ${\displaystyle q}$, відповідно:

 update(N, p, Seeds, eps, Minpts)
    coredist = core-distance(p, eps, MinPts)
    for each o in N
       if (o is not processed)
          new-reach-dist = max(coredist, dist(p,o))
          if (o.reachability-distance == UNDEFINED) // 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)
                 o.reachability-distance = new-reach-dist
                 Seeds.move-up(o, new-reach-dist)

Отже, OPTICS видає об'єкти(точки) в певному порядку, анотованих з їх найменшою досяжністю (в оригінальному алгоритмі, основна відстань теж враховується, але це не потрібно для подальшої обробки).

Використовуючи графік досяжності (спеціальний вид дендрограми), легко отримати ієрархічну структуру кластерів. Це 2D графік, з упорядкуванням точок, оброблених OPTICS на осі Ох, а відстань досяжності на осі Oy. Так, як точки, що належать до одного кластера мають низьку досяжність для найближчих сусідів, кластери показують ділянки досяжності. Чим глибша ділянка, тим щільніший кластер.

Зображення вище ілюструє цю концепцію. У верхній лівій частині, показано штучний набір даних. Верхня права частина візуалізує сполучне дерево, створене за допомогою OPTICS, і нижня частина показує ділянку досяжності, обчислену OPTICS. Виявлення кластерів з допомогою цього графіку може бути зроблене вручну, вибравши діапазон на осі Ох після візуального огляду, вибравши поріг на осі Оу (результат буде схожий на результат DBSCAN кластеризації з тимb ж ${\displaystyle \varepsilon }$і minPts параметри, тут значення 0,1 може дати добрі результати), або за допомогою різних алгоритмів, які намагаються виявити ділянки, використовуючи крутизну, виявлення коліна або локальні максимуми. Кластери, отримані таким чином можуть мати ієрархічну структуру, чого не може бути досягнуто за допомогою DBSCAN.

OPTICS проходить кожну точку один раз, при цьому вираховує ${\displaystyle \varepsilon }$-найближчих сусідів для кожної. Враховуючи використання просторового індексу, що повертає запит на сусідів в час${\displaystyle O(\log n)}$ runtime, загальна складність алгоритму буде ${\displaystyle O(n\cdot \log n)}$.Автори оригінального OPTICS повідомили, що фактичний константний коефіцієнт уповільнення буде 1.6 в порівнянні з DBSCAN. Варто зауважити, що ${\displaystyle \varepsilon }$ може мати великий вплив на час виконання алгоритму, бо його велике значення може збільшувати складність запиту на найближчих сусідів до лінійної.

Вибір ${\displaystyle \varepsilon >\max _{x,y}d(x,y)}$ (більшим, ніж максимальна відстань між даними в наборі даних) is але приведе до квадратичної складності алгоритму. Ось, чому ${\displaystyle \varepsilon }$ потрібно вибирати під кожен набір даних окремо.

•OPTICS-OF[3] це алгоритм визначення аномалій, який базується на OPTICS. Це знаходження викидів в даному алгоритмі OPTICS, з затратами меншими, ніж за допомогою інших алгоритмів виявлення аномалій.

•DeLi-Clu,[4] (англ. Density-Link-Clustering) поєднує ідею single-linkage clustering і OPTICS, усуваючи параметр ${\displaystyle \varepsilon }$ , покращуючи час виконання OPTICS.

•HiSC[5] метод ієрархічної кластеризації підпростору (паралельно осі), на основі OPTICS.

•HiCO[6]

•DiSH[7] — це покращення HiSC, з допомогою якого можна знаходити складніші ієрархії.

•FOPTICS[8] — це швидша реалізація з використанням випадкових проекцій.

Реалізація OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO і DiSH доступна в фреймворку ELKI(з підтримкою індексів) . Також, неповна і повільна імплементація доступна в розширеннях Weka.MRCангл. The National Institute for Medical Research забезпечує C reimplementation of OPTICS без підтримки індексів.