Алгоритм CURE

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

Недостатки традиционных алгоритмов 
Популярный алгоритм метод k-средних минимизирует :
 
Если имеется большая разница в размерах или геометрии различных кластеров, метод квадратичной ошибки может разбить большие кластеры для минимизации квадрата ошибки, что не всегда правильно. Также в случае алгоритмов иерархической кластеризации эта проблема присутствует, так как никакая из мер расстояний между кластерами () не стремится работать с различными формами кластеров. Также, время работы большое, если n большое.

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

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

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

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

 Случайный отбор: Случайный отбор поддерживает большие наборы данных. В общем случае случайный отбор размещается в оперативной памяти. Случайный отбор есть компромисс между точностью и эффективностью.
 Разбиение: Основной идеей является разбиение пространства элементарных событий на p частей. Каждая часть содержит n/p элементов. Первый проход кластеризует каждую часть, пока общее число кластеров не сократится до n/pq для некоторой константы . Второй проход кластеризации доводит число кластеров до 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-средних

Примечания

Литература 
 
 
 

Алгоритмы кластерного анализа