Алгоритм CURE - CURE algorithm

Часть серии о
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий Очистка данных 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 т е

CURE (Clustering Using REpresentatives) - эффективный алгоритм кластеризации данных для больших баз данных . По сравнению с кластеризацией K-средних он более устойчив к выбросам и способен идентифицировать кластеры, имеющие несферическую форму и отклонения в размерах.

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

Популярный алгоритм кластеризации K-средних минимизирует критерий суммы квадратов ошибок :

${\ displaystyle E = \ sum _ {i = 1} ^ {k} \ sum _ {p \ in C_ {i}} (p-m_ {i}) ^ {2},}$

Учитывая большие различия в размерах или геометрии разных кластеров, метод квадратной ошибки может разбить большие кластеры, чтобы минимизировать квадратную ошибку, что не всегда правильно. Кроме того, с алгоритмами иерархической кластеризации эти проблемы существуют, поскольку ни одна из мер расстояния между кластерами ( ) не работает с разными формами кластеров. Также время работы велико, когда n велико. ${\ displaystyle d_ {min}, d_ {mean}}$

Проблема с алгоритмом BIRCH заключается в том, что после создания кластеров после шага 3 он использует центроиды кластеров и назначает каждую точку данных кластеру с ближайшим центроидом. Использование только центроида для перераспределения данных вызывает проблемы, когда кластеры не имеют одинаковых размеров и форм.

Алгоритм кластеризации CURE

Чтобы избежать проблем с кластерами неоднородного размера или формы, CURE использует алгоритм иерархической кластеризации , который выбирает золотую середину между центром тяжести и всеми крайними точками. В CURE выбирается постоянное количество c хорошо разбросанных точек кластера, и они сжимаются к центроиду кластера на долю α. Разбросанные точки после сжатия используются как представители кластера. Кластеры с ближайшей парой представителей - это кластеры, которые объединяются на каждом этапе иерархического алгоритма кластеризации CURE. Это позволяет CURE правильно идентифицировать кластеры и делает его менее чувствительным к выбросам.

Время выполнения составляет O ( n ² log n ), что делает его довольно дорогим, а сложность пространства - O ( n ).

Алгоритм нельзя напрямую применять к большим базам данных из-за высокой сложности выполнения. Усовершенствования отвечают этому требованию.

• Случайная выборка: случайная выборка поддерживает большие наборы данных. Обычно случайная выборка умещается в основной памяти . Случайная выборка предполагает компромисс между точностью и эффективностью.
• Разбиение: основная идея состоит в том, чтобы разделить пробное пространство на p разделов. Каждый раздел содержит n / p элементов. Первый проход частично кластеризует каждый раздел до тех пор, пока окончательное количество кластеров не уменьшится до n / pq для некоторой константы q ≥ 1. Второй проход кластеризации на n / q частично кластеризует разделы. Для второго прохода сохраняются только репрезентативные точки, поскольку процедура слияния требует только репрезентативных точек предыдущих кластеров перед вычислением репрезентативных точек для объединенного кластера. Разделение ввода сокращает время выполнения.
• Маркировка данных на диске: учитывая только репрезентативные точки для k кластеров, остальные точки данных также назначаются кластерам. Для этого выбирается часть случайно выбранных репрезентативных точек для каждого из k кластеров, и точка данных назначается кластеру, содержащему ближайшую к нему репрезентативную точку.

Псевдокод

ЛЕЧЕНИЕ (кол-во баллов, k )

Вход: набор точек S

Выход: k кластеров

• Для каждого кластера u (каждая входная точка) in u.mean и u.rep хранят среднее значение точек в кластере и набор c репрезентативных точек кластера (изначально c = 1, поскольку каждый кластер имеет одну точку данных) . Также u.closest хранит ближайший к u кластер.
• Все входные точки вставляются в kd-дерево T
• Рассматривайте каждую входную точку как отдельный кластер, вычисляйте u.closest для каждого u, а затем вставляйте каждый кластер в кучу Q. (кластеры располагаются в порядке возрастания расстояний между u и u.closest).
• Хотя размер (Q)> k
• Удалите верхний элемент Q (скажем, u) и объедините его с его ближайшим кластером u.closest (скажем, v) и вычислите новые репрезентативные точки для объединенного кластера w.
• Удалите u и v из T и Q.
• Для всех кластеров x в Q обновите x.closest и переместите x
• вставить w в Q
• повторить

Доступность

• Библиотека с открытым исходным кодом pyclustering включает реализацию алгоритма CURE на Python и C ++.

Смотрите также

• k-означает кластеризацию
• Алгоритм BFR

использованная литература

• Гуха, Судипто; Растоги, Раджив; Шим, Кюсок (1998). «CURE: эффективный алгоритм кластеризации для больших баз данных» (PDF) . Информационные системы . 26 (1): 35–58. DOI : 10.1016 / S0306-4379 (01) 00008-4 .
• Коган, Яков; Николас, Чарльз К .; Тебулль М. (2006). Группировка многомерных данных: последние достижения в кластеризации . Springer. ISBN 978-3-540-28348-5.
• Теодоридис, Сергий; Кутроумбас, Константинос (2006). Распознавание образов . Академическая пресса. С. 572–574. ISBN 978-0-12-369531-4.