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

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

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

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

${\text{core-dist}}_{\mathit{\epsilon },𝑀𝑖𝑛𝑃𝑡𝑠}=\{\begin{array}{cc}\text{UNDEFINED}& |N_{\epsilon }(p)|<𝑀𝑖𝑛𝑃𝑡𝑠\\ 𝑀𝑖𝑛𝑃𝑡𝑠\text{-th}{N}_{\epsilon }(p)& |N_{\epsilon }(p)|⩾𝑀𝑖𝑛𝑃𝑡𝑠\end{array}$

Здесь core-dist = основное расстояние, $𝑀𝑖𝑛𝑃𝑡𝑠\text{-th}{N}_{\epsilon }(p)$ = $𝑀𝑖𝑛𝑃𝑡𝑠$-ое в порядке возрастания расстояние до $N_{\epsilon }(p)$ .

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

${\text{reachability-dist}}_{\mathit{\epsilon },𝑀𝑖𝑛𝑃𝑡𝑠}(o,p)=\{\begin{array}{cc}\text{UNDEFINED}& |N_{\epsilon }(p)|<𝑀𝑖𝑛𝑃𝑡𝑠\\ \max ({\text{core-dist}}_{\mathit{\epsilon },𝑀𝑖𝑛𝑃𝑡𝑠}(p),\text{dist}(p,o))& |N_{\epsilon }(p)|⩾𝑀𝑖𝑛𝑃𝑡𝑠\end{array}$

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

Если Шаблон:Mvar и Шаблон:Mvar являются ближайшими соседями, и ${\epsilon }^{\prime }<\epsilon$, можно предположить, что Шаблон:Mvar и Шаблон:Mvar принадлежат тому же кластеру.

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

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

Псевдокод

Основной подход алгоритма 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 обновляется по $\epsilon$-соседям точек $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-кластеризации с теми же значениями параметров $\epsilon$ и minPts, в нашем случае значение 0,1 может дать хорошие результаты), или с помощью различных алгоритмов, которые пытаются определить долины по крутизне графика, по изгибу или по локальным максимумам. Кластеризации, полученные таким образом, обычно являются иерархическими и не могут быть получены одним прогоном алгоритма DBSCAN.

Сложность

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

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

Расширения

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

DeLi-CluШаблон:Sfn, (Шаблон:Lang-en) комбинирует идеи из Шаблон:Не переведено 5 и алгоритма OPTICS, исключая параметр $\epsilon$ и добавляя улучшение эффективности по сравнению с OPTICS.

HiSCШаблон:Sfn является иерархическим методом Шаблон:Не переведено 5 (параллельно осям), основанным на OPTICS.

HiCOШаблон:Sfn является иерархическим алгоритмом Шаблон:Не переведено 5, основанным на OPTICS.

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

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

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

Доступность

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

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

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга