Участник:Иванов Даниил/Алгоритм устойчивой кластеризации с иcпользованием связей
Перейти к навигации
Перейти к поиску
Алгоритм устойчивой кластеризации с иcпользованием связей | |
Последовательный алгоритм | |
Последовательная сложность | O(n^2 + n m_m m_a + n^2 \log{} n) |
Объём входных данных | n \times k (n объектов с k признаками) |
Объём выходных данных | n (метки кластеров для каждого объекта) |
Содержание
- 1 ЧАСТЬ. Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 ЧАСТЬ. Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 ЧАСТЬ. Свойства и структура алгоритмов
1.1 Общее описание алгоритма
- Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) решает задачу кластеризации объектов по заранее заданному количеству k кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта sim(p_i, p_j). Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.
- Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача поиска ассоциативных правил.
1.2 Математическое описание алгоритма
- Пусть дано множество объектов P = \{p_1, \ldots , p_n\}, натуральное число k, функция схожести sim(p_i, p_j), пороговое значение \theta : 0\leq\theta\leq 1 и функция функция f( \theta ) .
- Результатом работы алгоритма является k непересекающихся кластеров, делящих множество P.
- Две точки называются соседними, если sim(p_i, p_j) \geq \theta
- Количеством общих соседей link(p_i, p_j) называется число точек, являющимися соседними для точек p_i, p_j.
- Функцией связи между кластерами называется 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).
- Функцией качества является функция
- 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 )}}, где n_i - число объектов в кластере C_i.
- Алгоритм начинает работу, разбив всё пространство на n кластеров.
- Затем на каждом шаге он вычисляет значение g(C_i, C_j) для каждой пары кластеров и объединяет эти кластеры в один.
- Алгоритм ведёт свою работу до тех пор, пока не получит k кластеров.
- В качестве функции f( \theta ) обычно используется функция f(\theta ) = \frac{\theta - 1}{\theta + 1} , n_i^{1+2f(\theta )} - ожидаемое число связей между парами объектов кластера C_i.
- Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
- sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}, где |p_i| - количество атрибутов в p_i. Данная функция удобна в случае, если все признаки категориальны
- Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.
1.3 Вычислительное ядро алгоритма
- Вычислительное ядро алгоритма состоит из двух основных частей.
- Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
- Итеративное объединению кластеров. За n-k шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных куча. Для каждого кластера math>i</math> хранится своя куча q[i], содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча Q, содержащая все кластеры j, упорядоченные по мере убывания функции качества g(j, max(q[j])). На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.
1.4 Макроструктура алгоритма
- Макроструктура состоит из последовательного выполнения двух шагов, описанных в описании ядра алгоритма:
- Построении матрицы связей
- Пересчёте куч и объединении кластеров
1.5 Схема реализации последовательного алгоритма
Описание реализации алгоритма на псевдокоде
1 procedure cluster(S, k)
2 begin
3 link := compute_links(S)
4 for s in S do
5 begin
6 q[s] := build_local_heap(link, s)
7 end
8 Q := build_global_heap(S, q)
9 while size(Q) > k do
10 begin
11 u := extract_max(Q)
12 v := max(q[u])
13 delete(Q, v)
14 w := merge(u, v)
15 for each x in q[u] or q[v] do
16 begin
17 link[x, w] := link[x, u] + link[x, v]
18 delete(q[x], u)
19 delete(q[x], v)
20 insert(q[x], w, g(x, w))
21 insert(q[w], x, g(x, w))
22 update(Q, x, q[x])
23 end
24 insert(Q, w, q[w])
25 deallocate(q[u])
26 deallocate(q[v])
27 end
28 end
1.6 Последовательная сложность алгоритма
- Временная сложность:
- Инициализация глобальной кучи - O(n)
- Инициализация локальной кучи - требует O(n)
- Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за O(n*n^{2.37}), в среднем за O(n m_\alpha m_m)
- Построение каждой кучи - O(n)
- Сортировка каждой кучи - O( n \log{} n)
- Основной цикл объединения кластеров выполняется в n-k итераций.
- Вставить новый кластер в в O(n) локальных куч размера n - O( n \log{} n)
Итого: O(n^2 + n m_m m_a + n^2 \log{} n)
- Сложность по памяти:
- Поскольку каждая точка i может иметь не более \min \{ m_m m_i, n \} ) связей, то общие затраты памяти не превышают O(\min \{ n m_m m_a, n^2 \} ).
- Хранение связей - O(\min \{ n m_m m_a, n^2 \} ) (поскольку каждая точка i может иметь не более \min \{ m_m m_i, n \} ) связей)
Итого: O(\min \{ n^2, n m_m m_a \} )
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
- Вычисление соседей. Затраты данных операций при условии достаточного количества ядер T_1 = O(n)
- Построения связей происходит в n этапов, в каждом из которых нужно сделать m расчетов(с учетом распараллеливания), где m - количество соседей. В худшем случае T_2 = O(n^2) в среднем случае T_2 = O(n * m_a), где m_a среднее ожидаемое число соседей.
- Построение одной кучи имеет сложность O(n). Для каждой кучи сортировка O(n * log(n)). Итоговая сложность создания локальных куч T_3 = O(n * log(n)).
- Построение и сортировка глобальной кучи: T_4 = O(n * log(n)).
- В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность O(log(n)). В худшем случае, одна итерация цикла происходит за T_i = O(log(n)). Количество итераций n - k. Итого: T_5 = O((n - k) * log(n)). При k = 1, T_5 = O(n * log(n))
Итоговая сложность в худшем случае равна:
- 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)
Итоговая сложность в среднем случае равна:
- O(n * m_a) + O(n * log(n)).
Сложность по времени:
- O(n * (m_a + log(n))).
1.9 Входные и выходные данные алгоритма
- Входные данные алгоритма:
- Множество объектов P = \{p_1, \ldots , p_n\}
- Целевое количество кластеров k
- Матрица размера n \times m (n объектов по k признаков)
- Гиперпараметры алгоритма:
- Функция схожести sim(p_i, p_j)
- Пороговое значение схожести \theta : 0\leq\theta\leq 1
- Функция ожидания количества соседей f( \theta )
- Результат:
- Метка кластера для каждого объекта
- Объём данных: m меток кластера
1.10 Свойства алгоритма
- Детерменированность
- Устойчивость
- Вычислительная мощность алгоритма: \frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{n}.
- Отношение последовательной и параллельной сложностей: \frac{O(n^2 + n m_m m_a + n^2 \log{} n)}{O(n * (m_a + log(n)))}.
- Остальные свойства
- ROCK-алгоритм хорошо подходит для категорийных данных (т.е. каждый атрибут объекта принадлежит к небольшому множеству возможных признаков. Например: цвет)
- Хорошая масштабируемость алгоритма по данным
- Скорость работы алгоритма зависит от разреженности объектов в пространстве признаков. Чем меньше среднее количество соседей у объектов во входных данных, тем быстрее работает алгоритм
2 ЧАСТЬ. Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- Реализация алгоритма присутствует в пакете CBA для языка R [1]
- Реализация алгоритма для языка Java [2]