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