|
|
| (не показано 10 промежуточных версий этого же участника) |
| Строка 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> для кластеризации объектов с категорийными признаками.
| |
| − |
| |
| − | Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (т.е. принимающими значения из какого-либо множества) и др. Множество значений, которые может принимать признак, называется доменом этого признака. Так, например, у объекта '''кошка''' может быть категорийный признак '''порода''', доменом которого является множество '''[персидская, бенгальская, сфинкс, мейн-кун, ...]'''.
| |
| − |
| |
| − | Будем считать объекты выборки точками <math>P=\{p_1, ..., p_M\}</math> в <math>N</math>-мерном пространстве признаков. В ходе кластеризации все имеющиеся точки должны быть разделены на <math>k</math> непересекающихся подмножеств (кластеров) <math>\C={C_1, ..., C_k\}</math> таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию <math>f(C_1, ..., C_N)</math>.
| |
| − |
| |
| − | === Математическое описание алгоритма ===
| |
| − |
| |
| − | Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" (иногда также называется "покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Количество атрибутов транзакции равно количеству предлагаемых поставщиком товаров, и каждый атрибут может принимать два значения: '''присутствует''' ('''1'''), если этот товар присутствует в транзакции, или '''отсутствует''' ('''0'''), если он в транзакции отсутствует.
| |
| − |
| |
| − | Будет называть две транзакции <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>N(p)</math> - количество товаров, присутствующих в транзакции <math>p</math>.
| |
| − |
| |
| − | '''Количеством связей''' двух транзакций будем называть количество общих соседей этих транзакций, то есть
| |
| − |
| |
| − | <math>links(p_1,p_2)=N(\{p \in P | sim(p_1,p)<\theta\} \cap \{p \in P | sim(p_2,p)<\theta\})</math>
| |
| − |
| |
| − | === Вычислительное ядро алгоритма ===
| |
| − |
| |
| − | тут что-то будет
| |
| − |
| |
| − | === Макроструктура алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Схема реализации последовательного алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Последовательная сложность алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Информационный граф ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Ресурс параллелизма алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Входные и выходные данные алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Свойства алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | == Программная реализация алгоритма ==
| |
| − |
| |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Локальность данных и вычислений ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Выводы для классов архитектур ===
| |
| − |
| |
| − | и тут
| |
| − |
| |
| − | === Существующие реализации алгоритма ===
| |
| − |
| |
| − | нету :(
| |
| − |
| |
| − | == Литература ==
| |
| − |
| |
| − | <references \>
| |
| − |
| |
| − | [[Категория:Начатые статьи]]
| |
| − | [[Категория:Алгоритмы кластеризации]]
| |
