Алгоритм ОПТИКИ - OPTICS algorithm

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

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

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

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

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

{\ 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 {иначе}} \ end {case}}}

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

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

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

Псевдокод

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

function OPTICS(DB, eps, MinPts) is
    for each point p of DB do
        p.reachability-distance = UNDEFINED
    for each unprocessed point p of DB do
        N = getNeighbors(p, eps)
        mark p as processed
        output p to the ordered list
        if core-distance(p, eps, MinPts) != UNDEFINED then
            Seeds = empty priority queue
            update(N, p, Seeds, eps, MinPts)
            for each next q in Seeds do
                N' = getNeighbors(q, eps)
                mark q as processed
                output q to the ordered list
                if core-distance(q, eps, MinPts) != UNDEFINED do
                    update(N', q, Seeds, eps, MinPts)

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

function update(N, p, Seeds, eps, MinPts) is
    coredist = core-distance(p, eps, MinPts)
    for each o in N
        if o is not processed then
            new-reach-dist = max(coredist, dist(p,o))
            if o.reachability-distance == UNDEFINED then // 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 then
                    o.reachability-distance = new-reach-dist
                    Seeds.move-up(o, new-reach-dist)

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

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

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

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

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

Сложность

Как и DBSCAN , OPTICS обрабатывает каждую точку один раз и во время этой обработки выполняет запрос одного окружения . Учитывая пространственный индекс, который предоставляет запрос соседства во время выполнения, получается общее время выполнения, равное. Авторы оригинальной статьи по OPTICS сообщают о фактическом постоянном коэффициенте замедления 1,6 по сравнению с DBSCAN. Обратите внимание, что значение может сильно повлиять на стоимость алгоритма, поскольку слишком большое значение может повысить стоимость запроса соседства до линейной сложности. ${\ displaystyle \ varepsilon}$ ${\ Displaystyle О (\ журнал п)}$ ${\ Displaystyle О (п \ CDOT \ журнал п)}$ ${\ displaystyle \ varepsilon}$

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

Расширения

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

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

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

HiCO - это алгоритм иерархической корреляционной кластеризации , основанный на ОПТИКЕ.

DiSH - это усовершенствование HiSC, позволяющее находить более сложные иерархии.

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

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

Доступность

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

Пакет R "dbscan" включает реализацию OPTICS C ++ (как с традиционным dbscan-подобным, так и с извлечением кластера ξ), использующим дерево kd для ускорения индекса только для евклидова расстояния.

Реализации OPTICS на Python доступны в библиотеке PyClustering и в scikit-learn . HDBSCAN * доступен в библиотеке hdbscan .

Languages

In other projects