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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 8: Строка 8:
 
==Математическое описание алгоритма==
 
==Математическое описание алгоритма==
 
:Входные данные: множество точек <math>P = \{p_1, \ldots , p_n\}</math>.
 
:Входные данные: множество точек <math>P = \{p_1, \ldots , p_n\}</math>.
:Необходимо разделить множество P на k непересекающихся множеств.
+
:Необходимо разделить множество <math>P</math> на <math>k</math> непересекающихся множеств.
  
 
==Вычислительное ядро алгоритма==
 
==Вычислительное ядро алгоритма==

Версия 01:31, 13 октября 2016

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Возможность человека накапливать и сохранять информацию во многом опирается на нашу же способность систематизировать данные, которые мы получаем извне. Мы упорядочиваем все получаемые нами данные в группы и категории, что помогает нам удерживать их в памяти и осмысливать окружающую действительность. Те же принципы используют многие интеллектуальные приложения, используя алгоритмы кластеризации (clustering).
Кластеризация - процесс объединения объектов, имеющих похожие характеристики, в непересекающиеся группы, называемые кластерами, так чтобы каждый кластер состоял из подобных объектов, а объекты разных кластеров отличались. При этом каждый объект характеризуется рядом признаков.
Подавляющее большинство таких алгоритмов позволяют учитывать лишь числовые признаки для описания наблюдаемых объектов. Однако в реальной практике часто встречаются задачи с категориальными признаками, принимающими свои значения из конечного неупорядоченного множества. Одним из алгоритмов кластеризации, хорошо подходящим для категориальных признаков, является алгоритм устойчивой кластеризации с использованием связей (robust clustering using links, ROCK), предложенный Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories)[1] в 2000 году.
ROCK использует понятие степени связи между объектами - количество их общих соседей. Два объекта считаются соседями, если мера их сходства превышает некоторое пороговое значение. Качество кластеризации определяется оценочной функцией, зависящей от степени связи между парами объектов из одного кластера. Ее максимизация определяет наилучшее разбиение пространства на кластеры.

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

Входные данные: множество точек [math]P = \{p_1, \ldots , p_n\}[/math].
Необходимо разделить множество [math]P[/math] на [math]k[/math] непересекающихся множеств.

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. Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: ROCK: A Robust Clustering Algorithm for Categorical Attributes, Volume 25, Issue 5, July 2000, Pages 345-366