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

Машинное обучение и интеллектуальный анализ данных
Часть серии по

Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

Точки упорядочивания для идентификации структуры кластеров ( ОПТИКА ) - это алгоритм для поиска кластеров на основе плотности ^[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 не определены, если нет достаточно плотного кластера (относительно $ε$ ). При достаточно большом $ε$ этого никогда не происходит, но тогда каждый запрос $ε-$ соседства возвращает всю базу данных, что приводит к времени выполнения. Следовательно, параметр $ε$ необходим для отсечения плотности кластеров, которые больше не представляют интереса, и для ускорения работы алгоритма. $O(n^{2})$

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

Псевдокод [ править ]

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

Функция ОПТИКА (DB, EPS, MinPts) является  для каждой точки р БД делать p.reachability-distance = НЕОПРЕДЕЛЕННО для каждой необработанной точки p БД делаем N = getNeighbors (p, eps) пометить p как обработанный вывод p в упорядоченный список если core-distance (p, eps, MinPts)! = UNDEFINED, то Seeds = пустая приоритетная очередь обновить (N, p, Seeds, eps, MinPts) для каждого следующего q в Seeds do N '= getNeighbors (q, eps) отметить q как обработанный вывести q в упорядоченный список если core-distance (q, eps, MinPts)! = UNDEFINED сделать update (N ', q, Seeds, eps, MinPts)

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

Функция обновления (N, P, семена, EPS, MinPts) является coredist = core-distance (p, eps, MinPts) для каждого o в N, если o не обрабатывается, то новый-охват-расстояние = макс (составитель, расстояние (p, o)) если o.reachability-distance == UNDEFINED, то // o отсутствует в семенах o.reachability-distance = новое-расстояние-досягаемость Seeds.insert (о, новый-ричт-дист) else // o в семенах проверяем на предмет улучшения, если new -reach-dist <o.reachability-distance тогда o.reachability-distance = новое-расстояние-досягаемость Seeds.move-up (o, новый-досягаемость-расст.)

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

Извлечение кластеров [ править ]

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

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

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

Сложность [ править ]

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

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

Расширения [ править ]

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

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

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

HiCO ^[7] - это алгоритм иерархической корреляционной кластеризации , основанный на оптике.

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

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

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

Доступность [ править ]

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

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

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

Ссылки [ править ]

^ Кригель, Ганс-Петер; Крегер, Пер; Сандер, Йорг; Зимек, Артур (май 2011 г.). «Кластеризация на основе плотности». Междисциплинарные обзоры Wiley: интеллектуальный анализ данных и открытие знаний . 1 (3): 231–240. DOI : 10.1002 / widm.30 .
^ Михаэль Анкерст; Маркус М. Бройниг; Ханс-Петер Кригель ; Йорг Сандер (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.
^ Маркус М. Бройниг; Ханс-Петер Кригель ; Раймонд Т. Нг; Йорг Сандер (1999). «ОПТИКА-ОФ: Выявление локальных выбросов» . Принципы интеллектуального анализа данных и обнаружения знаний . Конспект лекций по информатике. 1704 . Springer-Verlag . С. 262–270. DOI : 10.1007 / b72280 . ISBN 978-3-540-66490-1.
^ Achtert, E .; Böhm, C .; Крегер, П. (2006). DeLi-Clu: повышение надежности, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайшей пары . LNCS: достижения в области обнаружения знаний и интеллектуального анализа данных . Конспект лекций по информатике. 3918 . С. 119–128. DOI : 10.1007 / 11731139_16 . ISBN 978-3-540-33206-0.
^ Achtert, E .; Böhm, C .; Кригель, HP ; Kröger, P .; Мюллер-Горман, I .; Зимек, А. (2006). Нахождение иерархий кластеров подпространств . LNCS: обнаружение знаний в базах данных: PKDD 2006 . Конспект лекций по информатике. 4213 . С. 446–453. CiteSeerX 10.1.1.705.2956 . DOI : 10.1007 / 11871637_42 . ISBN 978-3-540-45374-1.
^ Achtert, E .; Böhm, C .; Kröger, P .; Зимек, А. (2006). Иерархии интеллектуального анализа корреляционных кластеров . Proc. 18-я Международная конференция по управлению научными и статистическими базами данных (SSDBM) . С. 119–128. CiteSeerX 10.1.1.707.7872 . DOI : 10.1109 / SSDBM.2006.35 . ISBN 978-0-7695-2590-7.
^ Achtert, E .; Böhm, C .; Кригель, HP ; Kröger, P .; Мюллер-Горман, I .; Зимек, А. (2007). Обнаружение и визуализация иерархий подпространственных кластеров . LNCS: достижения в базах данных: концепции, системы и приложения . Конспект лекций по информатике. 4443 . С. 152–163. CiteSeerX 10.1.1.70.7843 . DOI : 10.1007 / 978-3-540-71703-4_15 . ISBN 978-3-540-71702-7.
^ Шнайдер, Йоханнес; Влахос, Михаил (2013). «Быстрая кластеризация без параметров на основе плотности с помощью случайных проекций». 22-я Международная конференция ACM по управлению информацией и знаниями (CIKM) .
^ Кампелло, Рикардо JGB; Мулави, Давуд; Зимек, Артур; Сандер, Йорг (22 июля 2015 г.). «Иерархические оценки плотности для кластеризации данных, визуализации и обнаружения выбросов». ACM-транзакции при обнаружении знаний из данных . 10 (1): 1–51. DOI : 10.1145 / 2733381 .
↑ JA Hartigan (1975). Алгоритмы кластеризации . Джон Вили и сыновья.

[1] Кригель, Ганс-Петер; Крегер, Пер; Сандер, Йорг; Зимек, Артур (май 2011 г.). «Кластеризация на основе плотности». Междисциплинарные обзоры Wiley: интеллектуальный анализ данных и открытие знаний . 1 (3): 231–240. DOI : 10.1002 / widm.30 .

[:0-2] Михаэль Анкерст; Маркус М. Бройниг; Ханс-Петер Кригель ; Йорг Сандер (1999). ОПТИКА: Точки упорядочивания для определения структуры кластеризации . ACM SIGMOD международная конференция по управлению данными. ACM Press . С. 49–60. CiteSeerX 10.1.1.129.6542 .

[3] Мартин Эстер ; Ханс-Петер Кригель ; Йорг Сандер; Сяовэй Сюй (1996). Эвангелос Симудис; Цзявэй Хан; Усама М. Файяд (ред.). Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом . Труды Второй Международной конференции по открытию знаний и интеллектуальному анализу данных (KDD-96). AAAI Press . С. 226–231. CiteSeerX 10.1.1.71.1980 . ISBN 1-57735-004-9.

[4] Маркус М. Бройниг; Ханс-Петер Кригель ; Раймонд Т. Нг; Йорг Сандер (1999). «ОПТИКА-ОФ: Выявление локальных выбросов» . Принципы интеллектуального анализа данных и обнаружения знаний . Конспект лекций по информатике. 1704 . Springer-Verlag . С. 262–270. DOI : 10.1007 / b72280 . ISBN 978-3-540-66490-1.

[5] Achtert, E .; Böhm, C .; Крегер, П. (2006). DeLi-Clu: повышение надежности, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайшей пары . LNCS: достижения в области обнаружения знаний и интеллектуального анализа данных . Конспект лекций по информатике. 3918 . С. 119–128. DOI : 10.1007 / 11731139_16 . ISBN 978-3-540-33206-0.

[6] Achtert, E .; Böhm, C .; Кригель, HP ; Kröger, P .; Мюллер-Горман, I .; Зимек, А. (2006). Нахождение иерархий кластеров подпространств . LNCS: обнаружение знаний в базах данных: PKDD 2006 . Конспект лекций по информатике. 4213 . С. 446–453. CiteSeerX 10.1.1.705.2956 . DOI : 10.1007 / 11871637_42 . ISBN 978-3-540-45374-1.

[7] Achtert, E .; Böhm, C .; Kröger, P .; Зимек, А. (2006). Иерархии интеллектуального анализа корреляционных кластеров . Proc. 18-я Международная конференция по управлению научными и статистическими базами данных (SSDBM) . С. 119–128. CiteSeerX 10.1.1.707.7872 . DOI : 10.1109 / SSDBM.2006.35 . ISBN 978-0-7695-2590-7.

[8] Achtert, E .; Böhm, C .; Кригель, HP ; Kröger, P .; Мюллер-Горман, I .; Зимек, А. (2007). Обнаружение и визуализация иерархий подпространственных кластеров . LNCS: достижения в базах данных: концепции, системы и приложения . Конспект лекций по информатике. 4443 . С. 152–163. CiteSeerX 10.1.1.70.7843 . DOI : 10.1007 / 978-3-540-71703-4_15 . ISBN 978-3-540-71702-7.

[9] Шнайдер, Йоханнес; Влахос, Михаил (2013). «Быстрая кластеризация без параметров на основе плотности с помощью случайных проекций». 22-я Международная конференция ACM по управлению информацией и знаниями (CIKM) .

[10] Кампелло, Рикардо JGB; Мулави, Давуд; Зимек, Артур; Сандер, Йорг (22 июля 2015 г.). «Иерархические оценки плотности для кластеризации данных, визуализации и обнаружения выбросов». ACM-транзакции при обнаружении знаний из данных . 10 (1): 1–51. DOI : 10.1145 / 2733381 .

[11] JA Hartigan (1975). Алгоритмы кластеризации . Джон Вили и сыновья.