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

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

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

Популярный алгоритм метод k-средних минимизирует сумму квадратов ошибок^[en]:

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

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

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

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

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

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

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

• Случайный отбор: Случайный отбор поддерживает большие наборы данных. В общем случае случайный отбор размещается в оперативной памяти. Случайный отбор есть компромисс между точностью и эффективностью.
• Разбиение: Основной идеей является разбиение пространства элементарных событий на p частей. Каждая часть содержит n/p элементов. Первый проход кластеризует каждую часть, пока общее число кластеров не сократится до n/pq для некоторой константы ${\displaystyle q\geqslant 1}$ . Второй проход кластеризации доводит число кластеров до n/q. На втором проходе запоминаются только представляющие точки, поскольку процедура слияния кластеров требует только представителей кластеров перед вычислением представителей объединённого кластера. Разбиение входа сокращает время выполнения.
• Пометка данных на диске: Если даны только представители k кластеров, остальные единицы информации также распределяются по кластерам. Чтобы это сделать, отбирается случайно представляющие точки для каждого из k кластеров и единица информации назначается кластеру, содержащему ближайшего к точке представителя.

Псевдокод

CURE (число точек, k)

Вход : Множество точек S

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

• Для каждого кластера u (каждой точки) в u.mean и u.rep запоминается центр тяжести точек кластера и набор из c представителей кластера (начально c = 1, поскольку каждый кластер имеет одну единицу информации). Также в u.closest запоминается ближайший к u кластер.
• Все входные точки вставляются в k-мерное дерево T
• Каждая входная точка трактуется как отдельный кластер, вычисляем u.closest для каждого u, а затем вставляем каждый кластер в кучу Q. (кластеры располагаются в порядке увеличения расстояния от u до u.closest).
• Пока size(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^[en]

Примечания

Литература

• Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. CURE: An Efficient Clustering Algorithm for Large Databases // Information Systems. — 1998. — Т. 26, вып. 1. — С. 35–58. — DOI:10.1016/S0306-4379(01)00008-4.
• Jacob Kogan, Charles K. Nicholas, Teboulle M. Grouping multidimensional data: recent advances in clustering. — Springer, 2006. — ISBN 978-3-540-28348-5.
• Sergios Theodoridis, Konstantinos Koutroumbas. Pattern recognition. — Academic Press, 2006. — С. 572–574. — ISBN 978-0-12-369531-4.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.