OPTICS

Частина з циклу
Машинне навчання та добування даних
Задачі класифікація кластерування регресія виявляння аномалій АвтоМН асоціативні правила навчання з підкріпленням структурове передбачування конструювання ознак навчання ознак інтерактивне навчання[en] напівавтоматичне навчання спонтанне навчання навчання ранжуванню виведення граматик[en]
Кероване навчання (класифікація • регресія) ансамблі[en] випадковий ліс натяжкове агрегування підсилювання дерева рішень доречно-векторна машина k-НС лінійна регресія логістична регресія наївне баєсове опорно-векторна машина штучні нейронні мережі перцептрон
Кластерування BIRCH[en] CURE[en] ієрархічне k-середніх очікування-максимізація DBSCAN OPTICS зсув середнього[en]
Зниження розмірності факторний аналіз метод незалежних компонент[en] канонічна кореляція лінійний розділювальний аналіз метод головних компонент власний узагальнений розклад[en] розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості
Структурове передбачування графові моделі баєсова мережа прихована марковська модель умовне випадкове поле
Виявлення аномалій k-НС коефіцієнт локального відхилення[en]
Штучна нейронна мережа автокодувальник когнітивні обчислення[en] глибинне навчання DeepDream[en] багатошаровий перцептрон рекурентна нейронна мережа ДКЧП ВРВ МВС обмежена машина Больцмана ГЗМ самоорганізаційне відображення згорткова нейронна мережа U-Net трансформер спайкова нейронна мережа[en] мемтранзистор[en] Електрохімічна ПДД[en] (ECRAM)
Навчання з підкріпленням Q-навчання SARSA метод часових різниць[en]
Теорія Компроміс зсуву та дисперсії ймовірносно приблизно коректне навчання мінімізація емпіричного ризику оккамове навчання[en] статистичне навчання теорія Вапника — Червоненкіса теорія обчислювального навчання[en]
Місця машинного навчання NeurIPS[en] ICML[en] ML[en] JMLR ArXiv:cs.LG
Пов'язані статті глосарій штучного інтелекту[en] список наборів даних для досліджень з машинного навчання перелік понять машинного навчання[en]
п о р

OPTICS (англ. Ordering points to identify the clustering structure) — це алгоритм знаходження щільності на основі кластерів у просторових даних. Він був представлений Міхаелем Анкерстом, Маркусом Брюінгом, Хансом Крігелем і Йоргом Сандером.^[1] Його основна ідея схожа на DBSCAN,^[2] але він вирішує одну з основних слабостей DBSCAN: проблему визначення значущих кластерів в наборах даних різної щільності. Для цього об'єкти бази даних повинні бути впорядковані(за лін. час) так, що об'єкти, які просторово близькі, будуть сусідами в упорядкуванні. Крім того, особлива відстань зберігається для кожної точки, яка являє собою щільність, яка повинна бути прийнятна для кластера, щоб мати обидві сусідні точки належали до тієї ж групи. Як це представлено в дендрограмі.

Ідея

Як і 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 без підтримки індексів.

Посилання