Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 32: Строка 32:
 
<math>sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)}</math>
 
<math>sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)}</math>
  
'''Количеством связей''' двух транзакций будем называть количество общих соседей этих транзакций, то есть
+
'''Количеством связей''' между двумя транзакциями будем называть количество общих соседей этих транзакций, то есть
  
 
<math>link(p_1,p_2)=N \Big( \{ p \in P | sim(p_1,p) < \theta \} \cap \{ p \in P | sim(p_2,p) < \theta \} \Big)</math>
 
<math>link(p_1,p_2)=N \Big( \{ p \in P | sim(p_1,p) < \theta \} \cap \{ p \in P | sim(p_2,p) < \theta \} \Big)</math>
Строка 39: Строка 39:
  
 
<math>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>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>N(C_i)^{1+2f(\theta)}</math> имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция <math>f(\theta)</math> имеет вид
 +
 +
<math>f(\theta)=\frac {1-\theta}{1+\theta}</math>
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===

Версия 23:45, 11 октября 2016


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


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

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

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

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

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

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

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

В ходе кластеризации все имеющиеся транзакции [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]sim(p_1,p_2)\lt \theta[/math]

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

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

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

[math]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]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]N(C_i)^{1+2f(\theta)}[/math] имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция [math]f(\theta)[/math] имеет вид

[math]f(\theta)=\frac {1-\theta}{1+\theta}[/math]

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

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

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

и тут

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

нету :(

3 Литература

<references \>

  1. Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366