Участник:Иванов Даниил/Алгоритм устойчивой кластеризации с иcпользованием связей: различия между версиями
Перейти к навигации
Перейти к поиску
Divanov (обсуждение | вклад) |
Divanov (обсуждение | вклад) |
||
Строка 10: | Строка 10: | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
+ | :Пусть дано множество объектов <math>P = \{p_1, \ldots , p_n\}</math>, натуральное число <math>k</math>, функция схожести <math>sim(p_i, p_j)</math>, пороговое значение <math>\theta : 0\leq\theta\leq 1</math> и функция функция <math> f( \theta ) </math>. | ||
+ | :Результатом работы алгоритма является <math>k</math> непересекающихся кластеров, делящих множество <math>P</math>. | ||
+ | |||
+ | :Две точки называются ''соседними'', если <math>sim(p_i, p_j) \geq \theta</math> | ||
+ | |||
+ | :Количеством общих соседей <math>link(p_i, p_j)</math> называется число точек, являющимися соседними для точек <math>p_i, p_j</math>. | ||
+ | |||
+ | :Функцией связи между кластерами называется <math>link[C_i, C_j] = \sum_{\begin{smallmatrix}p_q\in C_i,\; p_r\in C_j\end{smallmatrix}}^{ } link(p_{q},p_r)</math>. | ||
+ | |||
+ | :Функцией качества является функция | ||
+ | :<math> g(C_i, C_j) = \frac{link[C_i,C_j]}{(n_i + n_j)^{1 + 2f(\theta )} - n_i^{1+2f(\theta )} - n_j^{1+2f(\theta )}}</math>, где <math>n_i</math> - число объектов в кластере <math>C_i</math>. | ||
+ | |||
+ | :Алгоритм начинает работу, разбив всё пространство на <math>n</math> кластеров. | ||
+ | :Затем на каждом шаге он вычисляет значение <math>g(C_i, C_j)</math> для каждой пары кластеров и объединяет эти кластеры в один. | ||
+ | :Алгоритм ведёт свою работу до тех пор, пока не получит <math>k</math> кластеров. | ||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == |
Версия 21:44, 15 октября 2016
Вступление
Содержание
- 1 ЧАСТЬ. Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Входные и выходные данные алгоритма
- 1.9 Свойства алгоритма
- 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) решает задачу кластеризации объектов по заранее заданному количеству [math]k[/math] кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта [math]sim(p_i, p_j)[/math]. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.
- Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача поиска ассоциативных правил.
1.2 Математическое описание алгоритма
- Пусть дано множество объектов [math]P = \{p_1, \ldots , p_n\}[/math], натуральное число [math]k[/math], функция схожести [math]sim(p_i, p_j)[/math], пороговое значение [math]\theta : 0\leq\theta\leq 1[/math] и функция функция [math] f( \theta ) [/math].
- Результатом работы алгоритма является [math]k[/math] непересекающихся кластеров, делящих множество [math]P[/math].
- Две точки называются соседними, если [math]sim(p_i, p_j) \geq \theta[/math]
- Количеством общих соседей [math]link(p_i, p_j)[/math] называется число точек, являющимися соседними для точек [math]p_i, p_j[/math].
- Функцией связи между кластерами называется [math]link[C_i, C_j] = \sum_{\begin{smallmatrix}p_q\in C_i,\; p_r\in C_j\end{smallmatrix}}^{ } link(p_{q},p_r)[/math].
- Функцией качества является функция
- [math] g(C_i, C_j) = \frac{link[C_i,C_j]}{(n_i + n_j)^{1 + 2f(\theta )} - n_i^{1+2f(\theta )} - n_j^{1+2f(\theta )}}[/math], где [math]n_i[/math] - число объектов в кластере [math]C_i[/math].
- Алгоритм начинает работу, разбив всё пространство на [math]n[/math] кластеров.
- Затем на каждом шаге он вычисляет значение [math]g(C_i, C_j)[/math] для каждой пары кластеров и объединяет эти кластеры в один.
- Алгоритм ведёт свою работу до тех пор, пока не получит [math]k[/math] кластеров.