Алговики - Вклад [ru]

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

2016-12-04T16:11:51Z

Divanov: /* Существующие реализации алгоритма */

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = <math>n \times k</math> (n объектов с k признаками)
| output_data = <math>n</math> (метки кластеров для каждого объекта)
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <math>P = \{p_1, \ldots , p_n\}</math>
*Целевое количество кластеров <math>k</math>
*Матрица размера <math>n \times m</math> (n объектов по k признаков)

:'''Гиперпараметры алгоритма:'''
*Функция схожести <math>sim(p_i, p_j)</math>
*Пороговое значение схожести <math>\theta : 0\leq\theta\leq 1</math>
*Функция ожидания количества соседей <math> f( \theta ) </math>

:'''Результат:'''
*Метка кластера для каждого объекта
*Объём данных: <math>m</math> меток кластера

== Свойства алгоритма ==
*Детерменированность
*Устойчивость
*Вычислительная мощность алгоритма: <math>\frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{n}</math>.
*Отношение последовательной и параллельной сложностей: <math>\frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{O(n * (m_a + log(n)))}</math>.

:Остальные свойства
*ROCK-алгоритм хорошо подходит для категорийных данных (т.е. каждый атрибут объекта принадлежит к небольшому множеству возможных признаков. Например: цвет)
*Хорошая масштабируемость алгоритма по данным
*Скорость работы алгоритма зависит от разреженности объектов в пространстве признаков. Чем меньше среднее количество соседей у объектов во входных данных, тем быстрее работает алгоритм

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
*Реализация алгоритма присутствует в пакете CBA для языка R <ref>https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/RockCluster</ref>
*Реализация алгоритма для языка Java <ref>https://sourceforge.net/projects/feed4weka/files/</ref>

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T10:35:41Z

Divanov: /* Свойства алгоритма */

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = <math>n \times k</math> (n объектов с k признаками)
| output_data = <math>n</math> (метки кластеров для каждого объекта)
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <math>P = \{p_1, \ldots , p_n\}</math>
*Целевое количество кластеров <math>k</math>
*Матрица размера <math>n \times m</math> (n объектов по k признаков)

:'''Гиперпараметры алгоритма:'''
*Функция схожести <math>sim(p_i, p_j)</math>
*Пороговое значение схожести <math>\theta : 0\leq\theta\leq 1</math>
*Функция ожидания количества соседей <math> f( \theta ) </math>

:'''Результат:'''
*Метка кластера для каждого объекта
*Объём данных: <math>m</math> меток кластера

== Свойства алгоритма ==
*Детерменированность
*Устойчивость
*Вычислительная мощность алгоритма: <math>\frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{n}</math>.
*Отношение последовательной и параллельной сложностей: <math>\frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{O(n * (m_a + log(n)))}</math>.

:Остальные свойства
*ROCK-алгоритм хорошо подходит для категорийных данных (т.е. каждый атрибут объекта принадлежит к небольшому множеству возможных признаков. Например: цвет)
*Хорошая масштабируемость алгоритма по данным
*Скорость работы алгоритма зависит от разреженности объектов в пространстве признаков. Чем меньше среднее количество соседей у объектов во входных данных, тем быстрее работает алгоритм

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T10:30:48Z

Divanov: /* Свойства алгоритма */

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = <math>n \times k</math> (n объектов с k признаками)
| output_data = <math>n</math> (метки кластеров для каждого объекта)
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <math>P = \{p_1, \ldots , p_n\}</math>
*Целевое количество кластеров <math>k</math>
*Матрица размера <math>n \times m</math> (n объектов по k признаков)

:'''Гиперпараметры алгоритма:'''
*Функция схожести <math>sim(p_i, p_j)</math>
*Пороговое значение схожести <math>\theta : 0\leq\theta\leq 1</math>
*Функция ожидания количества соседей <math> f( \theta ) </math>

:'''Результат:'''
*Метка кластера для каждого объекта
*Объём данных: <math>m</math> меток кластера

== Свойства алгоритма ==
*Детерменированность
*Устойчивость
*Вычислительная мощность алгоритма: <math>\frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{n}</math>.
*Отношение последовательной и параллельной сложностей: <math>\frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{O(n * (m_a + log(n)))}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T10:29:10Z

Divanov: /* Входные и выходные данные алгоритма */

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = <math>n \times k</math> (n объектов с k признаками)
| output_data = <math>n</math> (метки кластеров для каждого объекта)
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <math>P = \{p_1, \ldots , p_n\}</math>
*Целевое количество кластеров <math>k</math>
*Матрица размера <math>n \times m</math> (n объектов по k признаков)

:'''Гиперпараметры алгоритма:'''
*Функция схожести <math>sim(p_i, p_j)</math>
*Пороговое значение схожести <math>\theta : 0\leq\theta\leq 1</math>
*Функция ожидания количества соседей <math> f( \theta ) </math>

:'''Результат:'''
*Метка кластера для каждого объекта
*Объём данных: <math>m</math> меток кластера

== Свойства алгоритма ==
*Детерменированность алгоритма
*Отношение последовательной и параллельной сложностей: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T10:27:47Z

Divanov:

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = <math>n \times k</math> (n объектов с k признаками)
| output_data = <math>n</math> (метки кластеров для каждого объекта)
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T09:07:01Z

Divanov:

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = <math>n \times m</math> (n объектов с m аттрибутами каждый)
| output_data = <math>n</math> (метки кластеров для каждого объекта)
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T09:05:16Z

Divanov:

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = <math>n \times m</math>
| output_data = <math>n</math>
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T09:00:21Z

Divanov: /* Ресурс параллелизма алгоритма */

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math>O(M^2 + M^2m_{nbr} + M^{2}logM)</math>
| pf_height = <math>O(MlogM)</math>
| pf_width = <math>O(M^2)</math>
| input_data = <math>M \times N</math>
| output_data = <math>M</math>
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==

# Вычисление соседей. Затраты данных операций при условии достаточного количества ядер <math>T_1 = O(n)</math>
# Построения связей происходит в <math>n</math> этапов, в каждом из которых нужно сделать <math>m</math> расчетов(с учетом распараллеливания), где <math>m</math> - количество соседей. В худшем случае <math>T_2 = O(n^2)</math> в среднем случае <math>T_2 = O(n * m_a)</math>, где <math>m_a</math> среднее ожидаемое число соседей.
# Построение одной кучи имеет сложность <math>O(n)</math>. Для каждой кучи сортировка <math>O(n * log(n))</math>. Итоговая сложность создания локальных куч <math>T_3 = O(n * log(n))</math>.
# Построение и сортировка глобальной кучи: <math>T_4 = O(n * log(n))</math>.
# В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность <math>O(log(n))</math>. В худшем случае, одна итерация цикла происходит за <math>T_i = O(log(n))</math>. Количество итераций n - k. Итого: <math>T_5 = O((n - k) * log(n))</math>. При k = 1, <math>T_5 = O(n * log(n))</math>

Итоговая сложность в худшем случае равна:

:<math>T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)</math>

Итоговая сложность в среднем случае равна:

:<math>O(n * m_a) + O(n * log(n))</math>.

Сложность по времени:

:<math>O(n * (m_a + log(n)))</math>.

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T08:42:48Z

Divanov: /* Схема реализации последовательного алгоритма */

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math>O(M^2 + M^2m_{nbr} + M^{2}logM)</math>
| pf_height = <math>O(MlogM)</math>
| pf_width = <math>O(M^2)</math>
| input_data = <math>M \times N</math>
| output_data = <math>M</math>
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Описание реализации алгоритма на псевдокоде
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T08:38:37Z

Divanov:

{{algorithm
| name = Алгоритм устойчивой кластеризации с иcпользованием связей
| serial_complexity = <math>O(M^2 + M^2m_{nbr} + M^{2}logM)</math>
| pf_height = <math>O(MlogM)</math>
| pf_width = <math>O(M^2)</math>
| input_data = <math>M \times N</math>
| output_data = <math>M</math>
}}
= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-12-04T08:37:07Z

Divanov:

{{algorithm
| name = Алгоритм устойчивой кластеризации с использованием связей
| serial_complexity = <math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>
| input_data = Множество <math>S</math> из <math>n</math> элементов, число кластеров <math>k</math>
| output_data = <math>n</math> точек с метками <math>k</math> кластеров
}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T21:41:12Z

Divanov: /* Информационный граф */

{{Assignment}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia2.png]]

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T21:37:24Z

Divanov: /* Информационный граф */

{{Assignment}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==
[[File:Divanov dia.png]]

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T21:04:30Z

Divanov: /* Свойства алгоритма */

{{Assignment}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
*Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T21:04:18Z

Divanov: /* Свойства алгоритма */

{{Assignment}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})}</math>.
:Вычислительная сложность: <math>\frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2}</math>.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T21:00:48Z

Divanov:

{{Assignment}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>

:'''Результат:'''
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:55:34Z

Divanov: /* Ресурс параллелизма алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==
:При <math>p</math> - количество процессов:

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>

:'''Результат:'''
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:55:23Z

Divanov: /* Ресурс параллелизма алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==
При <math>p</math> - количество процессов.

<math>O(\frac{n^2}{p}+nm_m m_\alpha + \frac{n^2\log n}{p})</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>

:'''Результат:'''
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:54:35Z

Divanov: /* Ресурс параллелизма алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==
<math>p</math> - количество процессов.

*Параллельное построение матрицы связей: <math>O(\frac{n^2}{p})</math>
*Параллельное построение начальной кучи (функция <math>build\_local\_heap</math>) - <math>\frac{n}{p}</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>

:'''Результат:'''
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:51:55Z

Divanov: /* Ресурс параллелизма алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==
<math>p</math> - количество процессов.

*Параллельное построение начальной кучи (функция <math>build\_local\_heap</math>) - <math>\frac{n}{p}</math>

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>

:'''Результат:'''
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:45:14Z

Divanov:

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Ресурс параллелизма алгоритма ==

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>

:'''Результат:'''
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:44:32Z

Divanov: /* Входные и выходные данные алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Входные и выходные данные алгоритма ==
:'''Входные данные алгоритма:'''
*Множество объектов <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>

:'''Результат:'''
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:43:49Z

Divanov: /* Входные и выходные данные алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Входные и выходные данные алгоритма ==
:Входные данные алгоритма:
*Множество объектов <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>

:Результат:
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:43:35Z

Divanov: /* Входные и выходные данные алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Входные и выходные данные алгоритма ==
:Входные данные алгоритма:
*Множество объектов <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>

:Результат:
*Метка кластера для каждого объекта

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:38:45Z

Divanov: /* Последовательная сложность алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==
:'''Временная сложность''':
*Инициализация глобальной кучи - <math>O(n)</math>
*Инициализация локальной кучи - требует <math>O(n)</math>
*Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за <math>O(n*n^{2.37})</math>, в среднем за <math>O(n m_\alpha m_m)</math>
*Построение каждой кучи - <math> O(n)</math>
*Сортировка каждой кучи - <math> O( n \log{} n)</math>
*Основной цикл объединения кластеров выполняется в <math>n-k</math> итераций.
**Вставить новый кластер в в <math> O(n)</math> локальных куч размера <math> n</math> - <math> O( n \log{} n)</math>
Итого:
<math> O(n^2 + n m_m m_a + n^2 \log{} n)</math>

:'''Сложность по памяти''':
*Поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей, то общие затраты памяти не превышают <math> O(\min \{ n m_m m_a, n^2 \} )</math>.
*Хранение связей - <math> O(\min \{ n m_m m_a, n^2 \} )</math> ''(поскольку каждая точка <math>i</math> может иметь не более <math>\min \{ m_m m_i, n \} )</math> связей)''
Итого:
<math> O(\min \{ n^2, n m_m m_a \} )</math>

== Информационный граф ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T19:53:25Z

Divanov: /* Схема реализации последовательного алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==
Реализация основной вычислительной части:
<source lang="pascal" line>
procedure cluster(S, k)
begin
link := compute_links(S)
for s in S do
begin
q[s] := build_local_heap(link, s)
end
Q := build_global_heap(S, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := max(q[u])
delete(Q, v)
w := merge(u, v)
for each x in q[u] or q[v] do
begin
link[x, w] := link[x, u] + link[x, v]
delete(q[x], u)
delete(q[x], v)
insert(q[x], w, g(x, w))
insert(q[w], x, g(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
</source>

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T19:31:10Z

Divanov: /* Макроструктура алгоритма */

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
:Алгоритм устойчивой кластеризации с иcпользованием связей ('''robust clustering using links''', ''ROCK'') решает задачу [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F кластеризации] объектов по заранее заданному количеству <math>k</math> кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта <math>sim(p_i, p_j)</math>. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

:Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача [https://en.wikipedia.org/wiki/Association_rule_learning поиска ассоциативных правил].

== Математическое описание алгоритма ==
:Пусть дано множество объектов <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> кластеров.

:В качестве функции <math>f( \theta )</math> обычно используется функция <math>f(\theta ) = \frac{\theta - 1}{\theta + 1}</math> , <math>n_i^{1+2f(\theta )}</math> - ожидаемое число связей между парами объектов кластера <math>C_i</math>.

:Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
:<math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Данная функция удобна в случае, если все признаки категориальны
:Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.

== Вычислительное ядро алгоритма ==
:Вычислительное ядро алгоритма состоит из двух основных частей.
# Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
# Итеративное объединению кластеров. За <math>n-k</math> шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных ''куча''. Для каждого кластера math>i</math> хранится своя куча <math>q[i]</math>, содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча <math>Q</math>, содержащая все кластеры <math>j</math>, упорядоченные по мере убывания функции качества <math>g(j, max(q[j]))</math>. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

== Макроструктура алгоритма ==
:Макроструктура состоит из последовательного выполнения двух шагов, описанных в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]]:
# Построении матрицы связей
# Пересчёте куч и объединении кластеров

== Схема реализации последовательного алгоритма ==

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]

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

2016-10-15T19:27:33Z

Divanov: /* Вычислительное ядро алгоритма */

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

2016-10-15T18:53:40Z

Divanov: /* Математическое описание алгоритма */

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

2016-10-15T18:44:50Z

Divanov: /* Математическое описание алгоритма */

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

2016-10-15T18:21:47Z

Divanov: /* Общее описание алгоритма */

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

2016-10-15T17:09:17Z

Divanov: Новая страница: «Вступление = ЧАСТЬ. Свойства и структура алгоритмов = == Общее описание алгоритма == == Ма…»

Вступление

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

== Вычислительное ядро алгоритма ==

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

== Последовательная сложность алгоритма ==

== Информационный граф ==

== Входные и выходные данные алгоритма ==

== Свойства алгоритма ==

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

[[en:Description of algorithm properties and structure]]