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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Полностью удалено содержимое страницы)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
{{algorithm
 
| name              = Алгоритм устойчивой кластеризации с иcпользованием связей
 
| serial_complexity = <math>...</math>
 
| pf_height        = <math>...</math>
 
| pf_width          = <math>...</math>
 
| input_data        = <math>...</math>
 
| output_data      = <math>...</math>
 
}}
 
  
Автор описания: [[Участник:viktorrulev|В.А. Рулев]].
 
 
== Свойства и структура алгоритма ==
 
 
=== Общее описание алгоритма ===
 
 
Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (то есть принимающими значения из какого-либо множества) и другими. Множество значений, которые может принимать признак, называется доменом этого признака. Так, например, у объекта '''кошка''' может быть категорийный признак '''порода''', доменом которого является множество '''[персидская, бенгальская, сфинкс, мейн-кун, ...]'''.
 
 
'''Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK)''' был предложен в 2000 году Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) <ref>Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366</ref> для кластеризации объектов с категорийными признаками.
 
 
Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" ("покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Каждому товару, который есть в наличии у поставщика, в транзакции соответствует отдельный признак, который принимает значение '''true''', если товар присутствует в транзакции, и '''false''', если товар в транзакции отсутствует.
 
 
=== Математическое описание алгоритма ===
 
 
В ходе кластеризации все имеющиеся транзакции <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)<\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) < \theta \} \cap \{ p \in P | sim(p_2,p) < \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>
 
 
=== Вычислительное ядро алгоритма ===
 
 
тут что-то будет
 
 
=== Макроструктура алгоритма ===
 
 
и тут
 
 
=== Схема реализации последовательного алгоритма ===
 
 
и тут
 
 
=== Последовательная сложность алгоритма ===
 
 
и тут
 
 
=== Информационный граф ===
 
 
и тут
 
 
=== Ресурс параллелизма алгоритма ===
 
 
и тут
 
 
=== Входные и выходные данные алгоритма ===
 
 
и тут
 
 
=== Свойства алгоритма ===
 
 
и тут
 
 
== Программная реализация алгоритма ==
 
 
=== Особенности реализации последовательного алгоритма ===
 
 
и тут
 
 
=== Локальность данных и вычислений ===
 
 
и тут
 
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
 
и тут
 
 
=== Масштабируемость алгоритма и его реализации ===
 
 
и тут
 
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
и тут
 
 
=== Выводы для классов архитектур ===
 
 
и тут
 
 
=== Существующие реализации алгоритма ===
 
 
нету :(
 
 
== Литература ==
 
 
<references \>
 
 
[[Категория:Начатые статьи‏‎]]
 
[[Категория:Алгоритмы кластеризации]]
 

Текущая версия на 23:31, 13 октября 2016