WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Упорядочение точек для обнаружения кластерной структуры (англ. Ordering points to identify the clustering structure, OPTICS) — это алгоритм нахождения^[1] кластеров в пространственных данных на основе плотности. Алгоритм презентовали Михаэл Анкерст, Маркус М. Бройниг, Ганс-Петер Кригель и Ёрг Сандер^[2]. Основная идея алгоритма похожа на DBSCAN^[3], но алгоритм предназначен для избавления от одной из главных слабостей алгоритма DBSCAN — проблемы обнаружения содержательных кластеров в данных, имеющих различные плотности. Чтобы это сделать, точки базы данных (линейно) упорядочиваются так, что пространственно близкие точки становятся соседними в упорядочении. Кроме того, для каждой точки запоминается специальное расстояние, представляющее плотность, которую следует принять для кластера, чтобы точки принадлежали одному кластеру. Это представляется как древовидная схема^[en].

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

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

${\displaystyle {\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}={\begin{cases}{\text{UNDEFINED}}&|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)&|N_{\varepsilon }(p)|\geqslant {\mathit {MinPts}}\end{cases}}}$

Здесь core-dist = основное расстояние, ${\displaystyle {\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)}$ = ${\displaystyle {\mathit {MinPts}}}$ -ое в порядке возрастания расстояние до ${\displaystyle N_{\varepsilon }(p)}$ .

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

${\displaystyle {\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&|N_{\varepsilon }(p)|\geqslant {\mathit {MinPts}}\end{cases}}}$

Здесь reachability-dist = достижимое расстояние.

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

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

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

Псевдокод

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

 OPTICS(DB, eps, MinPts)
    для каждой точки p из DB
       p.достижимое_расстояние=не_определено
    для каждой необработанной точки p из DB
       N=получитьСоседей (p, eps)
       пометить p как обработанную
       поместить p в упорядоченный список
       если (основное_расстояние (p, eps, Minpts) != не_определено)
          Seeds=пустая приоритетная очередь
          обновить(N, p, Seeds, eps, Minpts)
          для каждой следующей q из Seeds
             N'=получитьСоседей(q, eps)
             пометить q как обработанную
             поместить q в упорядоченный список
             если (основное_расстояние(q, eps, Minpts) != не_определено)
                обновить(N', q, Seeds, eps, Minpts)

В процедуре обновить(), приоритетная очередь Seeds обновляется по ${\displaystyle \varepsilon }$ -соседям точек ${\displaystyle p}$ и ${\displaystyle q}$ соответственно:

 обновить (N, p, Seeds, eps, Minpts)
    coredist=достижимое_расстояние(p, eps, MinPts)
    для каждого o в N
       если (o не обработана)
          новое_дост_расст=max(coredist, dist(p,o))
          если (o.достижимое_расстояние == не_определено) // точка o не в Seeds
              o.достижимое_расстояние=новое_дост_расст
              Seeds.вставить(o, новое_дост_расст)
          иначе               // точка o в Seeds, проверить на улучшение
              если (новое_дост_раст < o.достижимое_расстояние)
                 o.достижимое_расстояние=новое_дост_раст
                 Seeds.передвинуть_вверх(o, новое_дост_раст)

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

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

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

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

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

Сложность

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

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

Расширения

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

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

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

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

DiSH^[8] является улучшением алгоритма HiSC, которое может найти более сложные иерархии.

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

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

Доступность

Реализация на Java OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO и DiSH доступны в системе интеллектуального анализа данных ELKI^[en] (с ускоренным индексом для некоторых функций расстояния и с автоматическим выделением кластеров с помощью метода ξ). Другая реализация на языке Java включает расширение набора средств Weka (без поддержки выделения кластеров с помощью ξ). Пакет на языке R «dbscan» включает реализацию на языке C++ алгоритма OPTICS (как с традиционным выделением кластеров, подобным dbscan, так и ξ), используя K-мерное дерево для ускорения индекса для евклидова расстояния.

Для языка Python имеются следующие реализации. OPTICS доступен в библиотеке PyClustering. HDBSCAN доступен в библиотеке hdbscan, которая построена на основе scikit learn.

Примечания

Литература