Jump to content

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

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

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

Время работы равно O( n 2 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
  • повторить

Доступность

[ редактировать ]

См. также

[ редактировать ]
  • Гуха, Судипто; Растоги, Раджив; Шим, Кюсок (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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: da61ecf169983d48a352fea393d2bbf2__1651259340
URL1:https://arc.ask3.ru/arc/aa/da/f2/da61ecf169983d48a352fea393d2bbf2.html
Заголовок, (Title) документа по адресу, URL1:
CURE algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)