Упорядочение точек для идентификации структуры кластеризации ( OPTICS ) — это алгоритм для поиска кластеров на основе плотности [1] в пространственных данных. Он был представлен Михаэлем Анкерстом, Маркусом М. Бройнигом, Хансом-Петером Кригелем и Йоргом Сандером. [2] Его основная идея похожа на DBSCAN , [3], но он решает одну из основных слабостей DBSCAN: проблему обнаружения значимых кластеров в данных различной плотности. Для этого точки базы данных (линейно) упорядочиваются таким образом, что пространственно самые близкие точки становятся соседями в упорядочении. Кроме того, для каждой точки хранится специальное расстояние, которое представляет плотность, которая должна быть принята для кластера, чтобы обе точки принадлежали одному кластеру. Это представлено в виде дендрограммы .
Как и DBSCAN , OPTICS требует два параметра: ε , который описывает максимальное расстояние (радиус) для рассмотрения, и MinPts , описывающий количество точек, необходимых для формирования кластера. Точка p является основной точкой , если в ее ε -окрестности (включая саму точку p ) обнаружено не менее MinPts точек . В отличие от DBSCAN , OPTICS также рассматривает точки, являющиеся частью более плотно упакованного кластера, поэтому каждой точке назначается основное расстояние , которое описывает расстояние до MinPts -й ближайшей точки:
Расстояние достижимости другой точки o из точки p равно либо расстоянию между o и p , либо основному расстоянию p , в зависимости от того, что больше:
Если p и o являются ближайшими соседями, то нам нужно предположить, что p и o принадлежат одному и тому же кластеру.
Оба параметра core-distance и reachability-distance не определены, если нет достаточно плотного кластера (wrt ε ). При достаточно большом ε этого никогда не произойдет, но тогда каждый запрос ε -neighborhood возвращает всю базу данных, что приводит к времени выполнения. Следовательно, параметр ε требуется для отсечения плотности кластеров, которые больше не интересны, и для ускорения алгоритма.
Параметр ε , строго говоря, не является необходимым. Его можно просто установить на максимально возможное значение. Однако, когда доступен пространственный индекс, он играет практическую роль в отношении сложности. OPTICS абстрагируется от DBSCAN, удаляя этот параметр, по крайней мере, в той степени, чтобы дать только максимальное значение.
Основной подход OPTICS аналогичен DBSCAN , но вместо сохранения известных, но пока необработанных элементов кластера в наборе, они сохраняются в приоритетной очереди (например, с использованием индексированной кучи ).
Функция OPTICS(DB, ε, MinPts) для каждой точки p из DB выполняет p.расстояние достижимости = НЕ ОПРЕДЕЛЕНО для каждой необработанной точки p БД сделать N = получитьСоседей(p, ε) пометить p как обработанный вывести p в упорядоченный список если core-distance(p, ε, MinPts) != UNDEFINED тогда Семена = пустая приоритетная очередь обновление(N, p, семена, ε, MinPts) для каждого следующего q в семенах делать N' = getNeighbors(q, ε) отметить q как обработанный вывести q в упорядоченный список если core-distance(q, ε, MinPts) != UNDEFINED сделать обновление(N', q, Seeds, ε, MinPts)
В update() приоритетная очередь Seeds обновляется с учетом -окрестности и , соответственно:
Функция update(N, p, Seeds, ε, MinPts) — это coredist = core-distance(p, ε, MinPts) для каждого o в N если o не обрабатывается , то new-reach-dist = max(coredist, dist(p,o)) если o.reachability-distance == UNDEFINED тогда // o не находится в Seeds o.расстояние-достижимости = новое-расстояние-достижимости Seeds.insert(o, new-reach-dist) else // o в семенах, проверить на предмет улучшения if new-reach-dist < o.reachability-distance then o.расстояние-достижимости = новое-расстояние-достижимости Seeds.move-up(o, new-reach-dist)
Таким образом, OPTICS выводит точки в определенном порядке, аннотированные их наименьшим расстоянием достижимости (в исходном алгоритме также экспортируется основное расстояние, но это не требуется для дальнейшей обработки).
Используя график достижимости (особый вид дендрограммы ), можно легко получить иерархическую структуру кластеров. Это двумерный график с порядком точек, обработанных OPTICS на оси x, и расстоянием достижимости на оси y. Поскольку точки, принадлежащие кластеру, имеют низкое расстояние достижимости до своего ближайшего соседа, кластеры отображаются в виде долин на графике достижимости. Чем глубже долина, тем плотнее кластер.
Изображение выше иллюстрирует эту концепцию. В его верхней левой области показан синтетический пример набора данных. Верхняя правая часть визуализирует связующее дерево, созданное OPTICS, а нижняя часть показывает график достижимости, вычисленный OPTICS. Цвета на этом графике являются метками, а не вычисляются алгоритмом; но хорошо видно, как впадины на графике соответствуют кластерам в наборе данных выше. Желтые точки на этом изображении считаются шумом, и впадины на их графике достижимости не обнаружены. Обычно они не назначаются кластерам, за исключением вездесущего кластера «все данные» в иерархическом результате.
Извлечение кластеров из этого графика может быть выполнено вручную путем выбора диапазонов на оси x после визуального осмотра, путем выбора порога на оси y (результат тогда аналогичен результату кластеризации DBSCAN с теми же параметрами и minPts; здесь значение 0,1 может дать хорошие результаты), или с помощью различных алгоритмов, которые пытаются обнаружить долины по крутизне, обнаружению колена или локальным максимумам. Диапазон графика, начинающийся с крутого спуска и заканчивающийся крутым подъемом, считается долиной и соответствует смежной области высокой плотности. Необходимо проявить дополнительную осторожность, чтобы отнести последние точки в долине к внутреннему или внешнему кластеру, этого можно добиться, рассмотрев предшественника. [4] Кластеризации, полученные таким образом, обычно являются иерархическими и не могут быть достигнуты одним запуском DBSCAN.
Как и DBSCAN , OPTICS обрабатывает каждую точку один раз и выполняет один -запрос соседства во время этой обработки. При наличии пространственного индекса , который предоставляет запрос соседства во время выполнения, получается общее время выполнения . Однако худшим случаем является , как и в случае с DBSCAN. Авторы оригинальной статьи OPTICS сообщают о фактическом постоянном коэффициенте замедления 1,6 по сравнению с DBSCAN. Обратите внимание, что значение может сильно влиять на стоимость алгоритма, поскольку слишком большое значение может повысить стоимость запроса соседства до линейной сложности.
В частности, выбор (больше максимального расстояния в наборе данных) возможен, но приводит к квадратичной сложности, поскольку каждый запрос соседства возвращает полный набор данных. Даже если пространственный индекс недоступен, это приводит к дополнительным затратам на управление кучей. Поэтому следует выбирать соответствующим образом для набора данных.
OPTICS-OF [5] — это алгоритм обнаружения выбросов , основанный на OPTICS. Основное применение — извлечение выбросов из существующего запуска OPTICS с низкими затратами по сравнению с использованием другого метода обнаружения выбросов. Более известная версия LOF основана на тех же концепциях.
ДеЛи-Клу, [6] Кластеризация с плотностью связей объединяет идеи кластеризации с одиночной связью и OPTICS, устраняя параметр и предлагая улучшение производительности по сравнению с OPTICS.
HiSC [7] — это метод иерархической подпространственной кластеризации (параллельной оси), основанный на OPTICS.
HiCO [8] — это иерархический алгоритм корреляционной кластеризации, основанный на OPTICS.
DiSH [9] — это усовершенствованный вариант HiSC, который позволяет находить более сложные иерархии.
FOPTICS [10] — более быстрая реализация, использующая случайные проекции.
HDBSCAN* [11] основан на усовершенствованном DBSCAN, исключающем граничные точки из кластеров и, таким образом, более строго следующему базовому определению уровней плотности Хартигана. [12]
Реализации OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO и DiSH на Java доступны в фреймворке интеллектуального анализа данных ELKI (с ускорением индекса для нескольких функций расстояния и с автоматическим извлечением кластера с использованием метода извлечения ξ). Другие реализации Java включают расширение Weka (без поддержки извлечения кластера ξ).
Пакет R «dbscan» включает реализацию OPTICS на C++ (как с традиционным извлечением типа dbscan, так и с извлечением кластера ξ) с использованием дерева kd для ускорения индекса только для евклидова расстояния.
Реализации OPTICS на Python доступны в библиотеке PyClustering и в scikit-learn . HDBSCAN* доступен в библиотеке hdbscan.