Алгоритм устойчивой кластеризации с иcпользованием связей: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
| Строка 14: | Строка 14: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Алгоритм устойчивой кластеризации с и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> для кластеризации объектов с категорийными признаками. |
| + | |||
| + | Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (т.е. принимающими значения из какого-либо множества) и др. Множество значений, которые может принимать признак, называется доменом этого признака. | ||
| + | |||
| + | Так, например, у объекта '''кошка''' может быть категорийный признак '''порода''', доменом которого является множество '''[персидская, бенгальская, сфинкс, мейн-кун, ...]'''. | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Версия 17:58, 8 октября 2016
| Алгоритм устойчивой кластеризации с иcпользованием связей | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]...[/math] |
| Объём входных данных | [math]...[/math] |
| Объём выходных данных | [math]...[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]...[/math] |
| Ширина ярусно-параллельной формы | [math]...[/math] |
Автор описания: В.А. Рулев.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 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 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) был предложен в 2000 году Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) [1] для кластеризации объектов с категорийными признаками.
Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (т.е. принимающими значения из какого-либо множества) и др. Множество значений, которые может принимать признак, называется доменом этого признака.
Так, например, у объекта кошка может быть категорийный признак порода, доменом которого является множество [персидская, бенгальская, сфинкс, мейн-кун, ...].
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 \>
- ↑ Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366
