Алгоритм CURE

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Недостатки традиционных алгоритмов[править | править код]

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

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

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

Алгоритм кластеризации CURE[править | править код]

Чтобы избежать проблем с неоднородными размерами или формами кластеров, CURE использует алгоритм иерархической кластеризации, который принимает компромиссное решение[en] между центром тяжести и всеми крайностями. В алгоритме 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++.

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]