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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 16: Строка 16:
 
'''Алгоритм устойчивой кластеризации с и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> для кластеризации объектов с категорийными признаками.
 
'''Алгоритм устойчивой кластеризации с и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_1, ..., p_M\}</math> в <math>N</math>-мерном пространстве признаков. В ходе кластеризации все имеющиеся точки должны быть разделены на <math>k</math> непересекающихся подмножеств (кластеров) <math>\{C_1, ..., C_k\}</math> таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию <math>f(C_1, ..., C_N)</math>.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===

Версия 19:15, 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] для кластеризации объектов с категорийными признаками.

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

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

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

туц туц туц

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
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_устойчивой_кластеризации_с_иcпользованием_связей&oldid=5396