Участник:Viktorrulev/Алгоритм устойчивой кластеризации с иcпользованием связей: различия между версиями
Новая страница: «{{algorithm | name = Алгоритм устойчивой кластеризации с иcпользованием связей | serial_complexity…» |
Нет описания правки |
||
| Строка 22: | Строка 22: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
В ходе кластеризации | В ходе кластеризации <math>M</math> имеющихся транзакций <math>P=\{p_1,...,p_M\}</math> должны быть разделены на <math>K</math> непересекающихся подмножеств (кластеров) <math>C_1, ..., C_K</math> таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию <math>E(C_1, ..., C_K)</math>. | ||
Будет называть две транзакции <math>p_1</math> и <math>p_2</math> '''соседями''', если мера сходства этих транзакций больше некоторого заранее заданного порогового значения <math>\theta</math>, то есть | Будет называть две транзакции <math>p_1</math> и <math>p_2</math> '''соседями''', если мера сходства этих транзакций больше некоторого заранее заданного порогового значения <math>\theta</math>, то есть | ||
| Строка 43: | Строка 43: | ||
<math>f(\theta)=\frac {1-\theta}{1+\theta}</math> | <math>f(\theta)=\frac {1-\theta}{1+\theta}</math> | ||
Для того, чтобы сформировать кластеры, удовлетворяющие поставленному условию, необходимо последовательно объединять среди имеющихся кластеров такие пары кластеров, для которых метрика | |||
<math>goodness(C_i,C_j)=\frac {\sum_{p_r \in C_i, p_q \in C_j}{link(p_r,p_q)}} {(N(C_i) + N(C_j))^{1+2f(\theta)} - N(C_i)^{1+2f(\theta)} - N(C_j)^{1+2f(\theta)}}</math> | |||
достигает максимального значения среди всех пар кластеров. На начальном этапе каждая транзакция считается отдельным кластером. | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Вычислительное ядро алгоритма можно разделить на три основных этапа: | |||
1. Вычисление количества связей между каждой парой транзакций (<math>\frac {M \times M} {2}</math> вычислений количества связей) | |||
2. Последовательные объединения пар наиболее подходящих кластеров (<math>M-K</math> поисков пар и объединений). | |||
Подробнее оба этапа будут описаны ниже. | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
Версия от 17:54, 15 октября 2016
| Алгоритм устойчивой кластеризации с и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) [1] для кластеризации объектов с категорийными признаками.
Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" ("покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Каждому товару, который есть в наличии у поставщика, в транзакции соответствует отдельный признак, который принимает значение true, если товар присутствует в транзакции, и false, если товар в транзакции отсутствует.
Математическое описание алгоритма
В ходе кластеризации [math]\displaystyle{ M }[/math] имеющихся транзакций [math]\displaystyle{ P=\{p_1,...,p_M\} }[/math] должны быть разделены на [math]\displaystyle{ K }[/math] непересекающихся подмножеств (кластеров) [math]\displaystyle{ C_1, ..., C_K }[/math] таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию [math]\displaystyle{ E(C_1, ..., C_K) }[/math].
Будет называть две транзакции [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{ link(p_1,p_2)=N \Big( \{ p \in P | sim(p_1,p) \lt \theta \} \cap \{ p \in P | sim(p_2,p) \lt \theta \} \Big) }[/math]
В качестве критериальной функции используется функция вида
[math]\displaystyle{ E(C_1,...,C_K)=\sum_{i=1}^{K}N(C_i) \ast \sum_{p_q,p_r \in C_i}\frac{link(p_q,p_r)}{N(C_i)^{1+2f(\theta)}} }[/math]
Здесь [math]\displaystyle{ N(C_i)^{1+2f(\theta)} }[/math] имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция [math]\displaystyle{ f(\theta) }[/math] имеет вид
[math]\displaystyle{ f(\theta)=\frac {1-\theta}{1+\theta} }[/math]
Для того, чтобы сформировать кластеры, удовлетворяющие поставленному условию, необходимо последовательно объединять среди имеющихся кластеров такие пары кластеров, для которых метрика
[math]\displaystyle{ goodness(C_i,C_j)=\frac {\sum_{p_r \in C_i, p_q \in C_j}{link(p_r,p_q)}} {(N(C_i) + N(C_j))^{1+2f(\theta)} - N(C_i)^{1+2f(\theta)} - N(C_j)^{1+2f(\theta)}} }[/math]
достигает максимального значения среди всех пар кластеров. На начальном этапе каждая транзакция считается отдельным кластером.
Вычислительное ядро алгоритма
Вычислительное ядро алгоритма можно разделить на три основных этапа:
1. Вычисление количества связей между каждой парой транзакций ([math]\displaystyle{ \frac {M \times M} {2} }[/math] вычислений количества связей)
2. Последовательные объединения пар наиболее подходящих кластеров ([math]\displaystyle{ M-K }[/math] поисков пар и объединений).
Подробнее оба этапа будут описаны ниже.
Макроструктура алгоритма
Схема реализации последовательного алгоритма
и тут
Последовательная сложность алгоритма
и тут
Информационный граф
и тут
Ресурс параллелизма алгоритма
и тут
Входные и выходные данные алгоритма
и тут
Свойства алгоритма
и тут
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
и тут
Локальность данных и вычислений
и тут
Возможные способы и особенности параллельной реализации алгоритма
и тут
Масштабируемость алгоритма и его реализации
и тут
Динамические характеристики и эффективность реализации алгоритма
и тут
Выводы для классов архитектур
и тут
Существующие реализации алгоритма
нету :(
Литература
<references \>
- ↑ Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366