ОПТИКА алгоритм

редактировать

Алгоритм поиска кластеров на основе плотности в пространственных данных

Упорядочивание точек для идентификации структуры кластеризации (ОПТИКА ) представляет собой алгоритм поиска кластеров на основе плотности в пространственных данных. Его представили Михаэль Анкерст, Маркус М. Бройниг, Ханс-Петер Кригель и Йорг Зандер. Его основная идея похожа на DBSCAN, но устраняет один из основных недостатков DBSCAN: проблему обнаружения значимых кластеров в данных различной плотности. Для этого точки базы данных упорядочиваются (линейно) таким образом, что пространственно ближайшие точки становятся соседями в упорядочении. Кроме того, для каждой точки сохраняется особое расстояние, которое представляет плотность, которая должна быть принята для кластера, чтобы обе точки принадлежали одному кластеру. Это представлено в виде дендрограммы.

Содержание

1 Основная идея
2 Псевдокод
3 Извлечение кластеров
4 Сложность
5 Расширения
6 Доступность
7 Ссылки

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

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

core-dist ε, M в P ts (p) = {НЕОПРЕДЕЛЕН, если | N ε (p) | < M i n P t s M i n P t s -th smallest distance in N ε ( p) otherwise {\displaystyle {\text{core-dist}}_{\mathit {\varepsilon,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th smallest distance in }}N_{\varepsilon }(p){\text{otherwise}}\end{cases}}}

{\ displaystyle {\ text {core-dist}} _ {\ mathit {\ varepsilon, MinPts}} (p) = {\ begin {case} {\ text {UNDEFINED}} {\ text {if}} | N _ {\ varepsilon} (p) | <{\ mathit {MinPts}} \\ {\ mathit {MinPts}} {\ text {-ое наименьшее расстояние в}} N _ {\ varepsilon} (p) {\ text {else}} \ end {cases}}}

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

расстояние достижимости ε, M в P ts (o, p) = {НЕОПРЕДЕЛЕННО, если | N ε (p) | < M i n P t s max ( core-dist ε, M i n P t s ( p), dist ( p, o)) otherwise {\displaystyle {\text{reachability-dist}}_{\mathit {\varepsilon,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon,MinPts}}(p),{\text{dist}}(p,o)){\text{otherwise}}\end{cases}}}

{\ displaystyle {\ text {reachability-dist}} _ {\ mathit {\ varepsilon, MinPts}} (o, p) = {\ begin {cases} {\ text {UNDEFINED}} {\ text {if}} | N _ {\ varepsilon} (p) | <{\ mathit {MinPts}} \\ \ max ({\ text {core-dist}} _ {\ mathit {\ varepsilon, MinPts}} (p), {\ text {dist}} (p, o)) {\ text {else}} \ end {case}}}

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

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

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

Псевдокод

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

функция OPTICS (DB, eps, MinPts) isдля каждой точки p базы данных do p.reachability-distance = UNDEFINED для каждого необработанного точка p базы данных do N = getNeighbors (p, eps) пометить p как обработанный вывод p в упорядоченный список if core-distance (p, eps, MinPts)! = UNDEFINED, затем Seeds = пустое обновление очереди приоритетов (N, p, Seeds, eps, MinPts) для каждого следующего q в Seeds do N '= getNeighbors (q, eps) пометить q как обработанный вывод q в упорядоченный список if core-distance (q, eps, MinPts)! = UNDEFINED do update (N ', q, Seeds, eps, MinPts)

В update () начальные значения очереди приоритетов обновляются с помощью $ε {\ displaystyle \ varepsilon}$ $\ varepsilon$ -окрестность $p {\ displaystyle p}$ $p$ и $q {\ displaystyle q}$ $q$ соответственно:

function update (N, p, Seeds, eps, MinPts) is coredist = core-distance (p, eps, MinPts) для каждого o в N, если o не обрабатывается, то new-range-dist = max (coredist, dist (p, o)) если o.reachability-distance == UNDEFINED тогда // o отсутствует в семенах o.reachability-distance = new-range-dist Seeds.insert (o, new- range-dist) else // o в Seeds, проверяем улучшение if new-distance-dist OPTICS, следовательно, выводит точки в определенном порядке, помеченные наименьшим расстоянием достижимости (в исходном алгоритме ядро расстояние также экспортируется, но это не требуется для дальнейшей обработки).
Извлечение кластеров
 
Используя график достижимости (особый вид дендрограммы ), можно легко получить иерархическую структуру кластеров. Это двухмерный график с упорядочением точек, обработанным OPTICS, по оси x и расстоянием достижимости по оси y. Поскольку точки, принадлежащие кластеру, имеют малое расстояние доступности до ближайшего соседа, кластеры отображаются в виде впадин на графике достижимости. Чем глубже долина, тем плотнее скопление.
Изображение выше иллюстрирует эту концепцию. В его верхней левой области показан набор данных синтетического примера. Верхняя правая часть визуализирует связующее дерево, созданное OPTICS, а нижняя часть показывает график достижимости, вычисленный OPTICS. Цвета на этом графике являются метками и не вычисляются алгоритмом; но хорошо видно, как впадины на графике соответствуют кластерам в приведенном выше наборе данных. Желтые точки на этом изображении считаются шумом, и на графике их достижимости нет впадины. Обычно они не назначаются кластерам, за исключением вездесущего кластера «все данные» в иерархическом результате.
Извлечение кластеров из этого графика можно выполнить вручную, выбрав диапазон на оси x после визуального осмотра, выбрав порог на оси y (тогда результат аналогичен результату кластеризации DBSCAN с те же параметры  $ε {\ displaystyle \ varepsilon}$  $\ varepsilon$ и minPts; здесь значение 0,1 может дать хорошие результаты), или с помощью различных алгоритмов, которые пытаются обнаружить впадины по крутизне, обнаружению колена или локальному максимумы. Кластеры, полученные таким образом, обычно являются иерархическими и не могут быть достигнуты одним запуском DBSCAN.
Сложность
Как и DBSCAN, OPTICS обрабатывает каждую точку один раз и выполняет одну  $ε {\ displaystyle \ varepsilon}$  $\ varepsilon$ -соседний запрос во время этой обработки. Учитывая пространственный индекс, который предоставляет запрос соседства в  $O (log ⁡ n) {\ displaystyle O (\ log n)}$  $O (\ log п)$ времени выполнения, общее время выполнения  $О (n ⋅ журнал ⁡ n) {\ displaystyle O (n \ cdot \ log n)}$  $О (п \ cdot \ log n)$ получается. Авторы оригинальной статьи по OPTICS сообщают о фактическом постоянном коэффициенте замедления 1,6 по сравнению с DBSCAN. Обратите внимание, что значение  $ε {\ displaystyle \ varepsilon}$  $\ varepsilon$ может сильно повлиять на стоимость алгоритма, поскольку слишком большое значение может повысить стоимость запроса соседства до линейной сложности.
В частности, выбор  $ε>max x, yd (x, y) {\ displaystyle \ varepsilon>\ max _ {x, y} d (x, y)}$  $\varepsilon>\ max _ {x, y} d (x, y)$ (большее, чем максимальное расстояние в наборе данных) возможно, но приводит к квадратичной сложности, поскольку каждый запрос соседства возвращает полный набор данных. Даже при отсутствии пространственного индекса это требует дополнительных затрат в управление кучей. Следовательно,  $ε {\ displaystyle \ varepsilon}$  $\ varepsilon$ должен быть выбран надлежащим образом для набора данных.
Extensions
OPTICS-OF - это алгоритм обнаружения выбросов на основе OPTICS. Основное применение - извлечение выбросов из существующей серии OPTICS с меньшими затратами по сравнению с использованием другого метода обнаружения выбросов. Более известная версия LOF - это основаны на тех же концепциях.
DeLi-Clu, Density-Link-Clustering объединяет идеи из одинарная кластеризация и OPTICS, исключение параметра  $ε {\ displaystyle \ varepsilon}$  $\ 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" включает реализацию OPTICS C ++ (с традиционным dbscan-подобным извлечением и извлечением кластера ξ) с использованием kd tree для ускорения индекса Только евклидово расстояние.
Реализации OPTICS в Python доступны в библиотеке PyClustering и в scikit-learn. HDBSCAN * доступен в библиотеке hdbscan.
Ссылки