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

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

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

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

{\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}}

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

{\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}}

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

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

Параметр $ε$ , строго говоря, не является необходимым. Его можно просто установить на максимально возможное значение. Однако, когда доступен пространственный индекс, он играет практическую роль в отношении сложности. 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 обновляется с учетом -окрестности и , соответственно: $\varepsilon$ $p$ $q$

Функция 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. $\varepsilon$

Сложность

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

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

Расширения

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

ДеЛи-Клу, ^[6] Кластеризация с плотностью связей объединяет идеи кластеризации с одиночной связью и OPTICS, устраняя параметр и предлагая улучшение производительности по сравнению с OPTICS. $\varepsilon$

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.

Ссылки

^ Кригель, Ханс-Петер; Крёгер, Пир; Зандер, Йорг; Зимек, Артур (май 2011 г.). «Кластеризация на основе плотности». Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery . 1 (3): 231–240. doi :10.1002/widm.30. S2CID 36920706.
^ Михаэль Анкерст; Маркус М. Брейниг; Ханс-Петер Кригель ; Йорг Сандер (1999). ОПТИКА: Упорядочение точек для идентификации структуры кластеризации . Международная конференция ACM SIGMOD по управлению данными. ACM Press . С. 49–60. CiteSeerX 10.1.1.129.6542 .
^ Мартин Эстер ; Ханс-Петер Кригель ; Йорг Сандер; Сяовэй Сюй (1996). Эвангелос Симудис; Цзявэй Хан; Усама М. Файяд (ред.). Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом . Труды Второй международной конференции по обнаружению знаний и интеллектуальному анализу данных (KDD-96). AAAI Press . стр. 226–231. CiteSeerX 10.1.1.71.1980 . ISBN 1-57735-004-9.
^ Шуберт, Эрих; Герц, Майкл (22 августа 2018 г.). Улучшение структуры кластера, извлеченной из графиков ОПТИКИ (PDF) . Лернен, Виссен, Датен, Анализен (LWDA 2018). Том. CEUR-WS 2191. стр. 318–329 – через CEUR-WS.
^ Маркус М. Брейниг; Ханс-Петер Кригель ; Рэймонд Т. Нг; Йорг Сандер (1999). "OPTICS-OF: Определение локальных выбросов". Принципы добычи данных и обнаружения знаний. Конспект лекций по информатике. Том 1704. Springer-Verlag . С. 262–270. doi :10.1007/b72280. ISBN 978-3-540-66490-1. S2CID 27352458.
^ Ахтерт, Элке; Бём, Кристиан; Крёгер, Пир (2006). «DeLi-Clu: повышение надёжности, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайших пар». В Нг, Ви Кеонг; Кицурегава, Масару; Ли, Цзяньчжун; Чанг, Куиюй (ред.). Достижения в области обнаружения знаний и интеллектуального анализа данных, 10-я Тихоокеанско-азиатская конференция, PAKDD 2006, Сингапур, 9–12 апреля 2006 г., Труды . Заметки лекций по информатике. Том 3918. Springer. стр. 119–128. doi :10.1007/11731139_16.
^ Achtert, Elke; Böhm, Christian; Kriegel, Hans-Peter; Kröger, Peer; Müller-Gorman, Ina; Zimek, Arthur (2006). «Finding Hierarchies of Subspace Clusters». В Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (ред.). Knowledge Discovery in Databases: PKDD 2006, 10-я Европейская конференция по принципам и практике Knowledge Discovery in Databases, Берлин, Германия, 18–22 сентября 2006 г., Труды . Lecture Notes in Computer Science. Vol. 4213. Springer. pp. 446–453. doi : 10.1007/11871637_42 .
^ Ахтерт, Э.; Бём, К.; Крёгер, П.; Зимек, А. (2006). «Изучение иерархий корреляционных кластеров». 18-я Международная конференция по управлению научными и статистическими базами данных (SSDBM'06) . стр. 119–128. CiteSeerX 10.1.1.707.7872 . doi :10.1109/SSDBM.2006.35. ISBN 978-0-7695-2590-7. S2CID 2679909.
^ Achtert, Elke; Böhm, Christian; Kriegel, Hans-Peter; Kröger, Peer; Müller-Gorman, Ina; Zimek, Arthur (2007). «Обнаружение и визуализация иерархий кластеров подпространства». В Ramamohanarao, Kotagiri; Krishna, P. Radha; Mohania, Mukesh K.; Nantajeewarawat, Ekawit (ред.). Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings . Lecture Notes in Computer Science. Vol. 4443. Springer. pp. 152–163. doi :10.1007/978-3-540-71703-4_15.
^ Шнайдер, Йоханнес; Влахос, Михаил (2013). «Быстрая кластеризация на основе плотности без параметров с использованием случайных проекций». 22-я Международная конференция ACM по управлению информацией и знаниями (CIKM) .
^ Кампелло, Рикардо Дж. ГБ.; Мулави, Давуд; Зимек, Артур; Сандер, Йорг (22 июля 2015 г.). «Оценки иерархической плотности для кластеризации, визуализации и обнаружения выбросов». Труды ACM по обнаружению знаний из данных . 10 (1): 1–51. doi :10.1145/2733381. S2CID 2887636.
^ JA Hartigan (1975). Алгоритмы кластеризации . John Wiley & Sons.