Алгоритм кластеризации OPTICS

Упорядочение точек для обнаружения кластерной структуры (англ. Ordering points to identify the clustering structure, OPTICS) — это алгоритм нахождения кластеров в пространственных данных на основе плотности. Алгоритм презентовали Михаэл Анкерст, Маркус М. Бройниг, Ганс-Петер Кригель и Ёрг Сандер. Основная идея алгоритма похожа на DBSCAN, но алгоритм предназначен для избавления от одной из главных слабостей алгоритма DBSCAN — проблемы обнаружения содержательных кластеров в данных, имеющих различные плотности. Чтобы это сделать, точки базы данных (линейно) упорядочиваются так, что пространственно близкие точки становятся соседними в упорядочении. Кроме того, для каждой точки запоминается специальное расстояние, представляющее плотность, которую следует принять для кластера, чтобы точки принадлежали одному кластеру. Это представлено в виде дендрограммы.

Основная идея

Подобно DBSCAN, алгоритм OPTICS требует два параметра — параметр ε описывает максимальное расстояние (радиус), принимаемое во внимание, а параметр MinPts описывает число точек, требующихся для образования кластера. Точка p является основной точкой, если по меньшей мере MinPts точек находятся в её ε-окрестности $N_{\varepsilon }(p)$. В отличие от DBSCAN, алгоритм OPTICS рассматривает также точки, которые являются частью более плотного кластера, так что каждой точке назначается основное расстояние, которое описывает расстояние до MinPts-ой ближайшей точки:

${\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}={\begin{cases}{\text{UNDEFINED}}&|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)&|N_{\varepsilon }(p)|\geqslant {\mathit {MinPts}}\end{cases}}$

Здесь core-dist = основное расстояние, ${\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)$ = ${\mathit {MinPts}}$-ое в порядке возрастания расстояние до $N_{\varepsilon }(p)$ .

Достижимое расстояние точки o от точки p равно либо расстоянию между o и p, либо основному расстоянию точки p, в зависимости от того, какая величина больше:

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

Здесь reachability-dist = достижимое расстояние.

Если p и o являются ближайшими соседями, и $\varepsilon '<\varepsilon$, можно предположить, что p и o принадлежат тому же кластеру.

Как основное, так и достижимое расстояния не определены, если нет достаточно плотного кластера (применительно к ε). Если взять достаточно большое ε, этого никогда не произойдёт, но тогда любой запрос ε-соседства возвращает всю базу данных, что приводит ко времени работы $O(n^{2})$. Параметр ε требуется для отсечения неплотных кластеров, которые более неинтересны, и тем самым ускорить алгоритм.

Параметр ε, строго говоря, не обязателен. Он может просто быть установлен в максимальное возможное значение. Однако при доступности пространственного индекса он влияет на сложность вычислений. OPTICS отличается от DBSCAN тем, что этот параметр не учитывается, если ε и может влиять, то только тем, что задаёт максимальное значение.

Псевдокод

Основной подход алгоритма OPTICS такой же, как у DBSCAN, но вместо поддержки множества известных, но ещё необработанных членов кластера, используется очередь с приоритетом (то есть индексированная куча).

 OPTICS(DB, eps, MinPts)
    для каждой точки p из DB
       p.достижимое_расстояние=не_определено
    для каждой необработанной точки p из DB
       N=получитьСоседей (p, eps)
       пометить p как обработанную
       поместить p в упорядоченный список
       если (основное_расстояние (p, eps, Minpts) != не_определено)
          Seeds=пустая приоритетная очередь
          обновить(N, p, Seeds, eps, Minpts)
          для каждой следующей q из Seeds
             N'=получитьСоседей(q, eps)
             пометить q как обработанную
             поместить q в упорядоченный список
             если (основное_расстояние(q, eps, Minpts) != не_определено)
                обновить(N', q, Seeds, eps, Minpts)

В процедуре обновить(), приоритетная очередь Seeds обновляется по $\varepsilon$-соседям точек $p$ и $q$ соответственно:

 обновить (N, p, Seeds, eps, Minpts)
    coredist=основное_расстояние(p, eps, MinPts)
    для каждого o в N
       если (o не обработана)
          новое_дост_расст=max(coredist, dist(p,o))
          если (o.достижимое_расстояние == не_определено) // точка o не в Seeds
              o.достижимое_расстояние=новое_дост_расст
              Seeds.вставить(o, новое_дост_расст)
          иначе               // точка o в Seeds, проверить на улучшение
              если (новое_дост_раст < o.достижимое_расстояние)
                 o.достижимое_расстояние=новое_дост_раст
                 Seeds.передвинуть_вверх(o, новое_дост_раст)

OPTICS помещает точки в определённом порядке, помечая их наименьшим достижимым расстоянием (в оригинальном алгоритме основное расстояние также запоминается, но это не требуется для дальнейшей обработки).

Извлечение кластеров

Используя график достижимости (особый вид древовидной схемы), легко получить иерархическую структуру кластеров. Это двумерный график, на котором точки по оси x откладываются в порядке их обработки алгоритмом OPTICS, а по оси y откладывается достижимое расстояние. Поскольку точки, принадлежащие кластеру, имеют небольшое достижимое расстояние до ближайшего соседа, кластеры выглядят как долины на графике достижимости. Чем глубже долина, тем плотнее кластер.

Рисунок выше иллюстрирует эту концепцию. В верхней левой области рисунка показан смоделированный набор данных. Область рисунка верху справа визуализирует остовное дерево, полученное алгоритмом OPTICS, а нижняя часть рисунка показывает график достижимости, как его получает OPTICS. Цвета на этом графике являются метками и не вычисляются алгоритмом. Однако хорошо видно, как долины на графике соответствуют кластерам приведённого набора данных. Жёлтые точки на этом изображении считаются шумом и не соответствуют никаким долинам. Они обычно не назначаются никаким кластерам, за исключением всеобъемлющего кластера «все данные» в иерархическом результате.

Извлечение кластеров из такого графика может быть осуществлено вручную путём выбора интервалов по оси x после просмотра графика, путём выбора порога по оси y (тогда результат подобен DBSCAN-кластеризации с теми же значениями параметров $\varepsilon$ и minPts, в нашем случае значение 0,1 может дать хорошие результаты), или с помощью различных алгоритмов, которые пытаются определить долины по крутизне графика, по изгибу или по локальным максимумам. Кластеризации, полученные таким образом, обычно являются иерархическими и не могут быть получены одним прогоном алгоритма DBSCAN.

Сложность

Подобно DBSCAN алгоритм OPTICS обрабатывает каждую точку только один раз и выполняет один запрос $\varepsilon$-соседства во время этой обработки. Если задан пространственный индекс, который гарантирует работу запроса соседства за время $O(\log n)$, получим общее время работы $O(n\cdot \log n)$. Авторы оригинальной статьи по OPTICS сообщают о константном замедлении в 1,6 раза по сравнению с DBSCAN. Заметим, что значение $\varepsilon$ может сильно влиять на затраты алгоритма, поскольку слишком большое значение может увеличивать сложность запроса соседства до линейной.

В частности, выбор $\varepsilon >\max _{x,y}d(x,y)$ (больше, чем максимальное расстояние в наборе данных) возможен, но, очевидно, ведёт к квадратичной сложности, поскольку запрос списка соседей возвращает весь набор данных. Даже если никакой пространственный индекс не доступен, это приводит к дополнительным затратам в поддержке кучи. Таким образом, $\varepsilon$ следует выбрать должным образом для набора данных.

Расширения

OPTICS-OF является алгоритмом выявления аномалий, основанном на OPTICS. В основном он используется для выделения выбросов из существующего прогона алгоритма OPTICS с малыми затратами по сравнению с другим методом выделения выброса. Лучшая известная версия алгоритма выделения локального уровня выброса основывается на тех же концепциях.

DeLi-Clu, (англ. Density-Link-Clustering) комбинирует идеи из метода одиночной кластеризации и алгоритма OPTICS, исключая параметр $\varepsilon$ и добавляя улучшение эффективности по сравнению с OPTICS.

HiSC является иерархическим методом кластеризации подпространств (параллельно осям), основанным на OPTICS.

HiCO является иерархическим алгоритмом корреляционной кластеризации, основанным на OPTICS.

DiSH является улучшением алгоритма HiSC, которое может найти более сложные иерархии.

FOPTICS является быстрой реализацией с помощью случайных проекций.

HDBSCAN* основан на усовершенствовании алгоритма DBSCAN исключением граничных точек из кластеров и отсюда следует более строгое определение уровней плотности (по Хартигану).

Доступность

Реализация на Java OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO и DiSH доступны в системе интеллектуального анализа данных ELKI (с ускоренным индексом для некоторых функций расстояния и с автоматическим выделением кластеров с помощью метода ξ). Другая реализация на языке Java включает расширение набора средств Weka (без поддержки выделения кластеров с помощью ξ). Пакет на языке R «dbscan» включает реализацию на языке C++ алгоритма OPTICS (как с традиционным выделением кластеров, подобным dbscan, так и ξ), используя K-мерное дерево для ускорения индекса для евклидова расстояния.

Для языка Python имеются следующие реализации. OPTICS доступен в библиотеке PyClustering. HDBSCAN доступен в библиотеке hdbscan, которая построена на основе scikit learn.