Алгоритм устойчивой кластеризации с иcпользованием связей

Алгоритм устойчивой кластеризации с иcпользованием связей
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ ... }[/math]
Объём входных данных	[math]\displaystyle{ ... }[/math]
Объём выходных данных	[math]\displaystyle{ ... }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ ... }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ ... }[/math]

Автор описания: В.А. Рулев.

Свойства и структура алгоритма

Общее описание алгоритма

Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) был предложен в 2000 году Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) для кластеризации объектов с категорийными признаками.

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

Будем считать объекты выборки точками [math]\displaystyle{ P=\{p_1, ..., p_M\} }[/math] в [math]\displaystyle{ N }[/math]-мерном пространстве признаков. В ходе кластеризации все имеющиеся точки должны быть разделены на [math]\displaystyle{ k }[/math] непересекающихся подмножеств (кластеров) [math]\displaystyle{ \C={C_1, ..., C_k\} }[/math] таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию [math]\displaystyle{ f(C_1, ..., C_N) }[/math].

Математическое описание алгоритма

Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" (иногда также называется "покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Количество атрибутов транзакции равно количеству предлагаемых поставщиком товаров, и каждый атрибут может принимать два значения: присутствует (1), если этот товар присутствует в транзакции, или отсутствует (0), если он в транзакции отсутствует.

Будет называть две транзакции [math]\displaystyle{ p_1 }[/math] и [math]\displaystyle{ p_2 }[/math] соседями, если мера сходства этих транзакций больше некоторого заранее заданного порогового значения [math]\displaystyle{ \theta }[/math], то есть

[math]\displaystyle{ sim(p_1,p_2)\lt \theta }[/math]

В качестве меры сходства в алгоритме устойчивой кластеризации с использованием связей используется основанная на коэффициенте Жаккара мера сходства

[math]\displaystyle{ sim(p_1,p_2)=\frac{N)p_1 \cap p_2)}{N(p_1 \cup p_2)} }[/math]

где [math]\displaystyle{ N(p) }[/math] - количество товаров, присутствующих в транзакции [math]\displaystyle{ p }[/math].

Количеством связей двух транзакций будем называть количество общих соседей этих транзакций, то есть

[math]\displaystyle{ links(p_1,p_2)=N(\{p \in P | sim(p_1,p)\lt \theta\} \cap \{p \in P | sim(p_2,p)\lt \theta\}) }[/math]

Вычислительное ядро алгоритма

тут что-то будет

Макроструктура алгоритма

и тут

Схема реализации последовательного алгоритма

и тут

Последовательная сложность алгоритма

и тут

Информационный граф

и тут

Ресурс параллелизма алгоритма

и тут

Входные и выходные данные алгоритма

и тут

Свойства алгоритма

и тут

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

и тут

Локальность данных и вычислений

и тут

Возможные способы и особенности параллельной реализации алгоритма

и тут

Масштабируемость алгоритма и его реализации

и тут

Динамические характеристики и эффективность реализации алгоритма

и тут

Выводы для классов архитектур

и тут

Существующие реализации алгоритма

нету :(

Литература

<references \>