Алгоритм лечения

CURE (Кластеризация с использованием REpresentatives) — эффективный алгоритм кластеризации данных для больших баз данных. ^{[ нужна ссылка ]}. По сравнению с кластеризацией K-средних, она более устойчива к выбросам и способна идентифицировать кластеры, имеющие несферическую форму и различия в размерах.

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

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

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

Проблема с алгоритмом 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 (каждая входная точка) в u.mean и u.rep сохраняется среднее значение точек в кластере и набор из c репрезентативных точек кластера (изначально c = 1, поскольку каждый кластер имеет одну точку данных) . Также u.closest хранит ближайший к вам кластер.
Все входные точки вставляются в дерево 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++.

См. также

Ссылки

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