Участник:Иванов Даниил/Алгоритм устойчивой кластеризации с иcпользованием связей
| Алгоритм устойчивой кластеризации с иcпользованием связей | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(n^2 + n m_m m_a + n^2 \log{} n) }[/math] |
| Объём входных данных | [math]\displaystyle{ n \times m }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
ЧАСТЬ. Свойства и структура алгоритмов
Общее описание алгоритма
- Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) решает задачу кластеризации объектов по заранее заданному количеству [math]\displaystyle{ k }[/math] кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта [math]\displaystyle{ sim(p_i, p_j) }[/math]. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.
- Данный алгоритм хорошо подходит для объектов с категориальными признаками (то есть признаками, принимающими небольшое количество значений). С помощью этого алгоритма также часто решается задача поиска ассоциативных правил.
Математическое описание алгоритма
- Пусть дано множество объектов [math]\displaystyle{ P = \{p_1, \ldots , p_n\} }[/math], натуральное число [math]\displaystyle{ k }[/math], функция схожести [math]\displaystyle{ sim(p_i, p_j) }[/math], пороговое значение [math]\displaystyle{ \theta : 0\leq\theta\leq 1 }[/math] и функция функция [math]\displaystyle{ f( \theta ) }[/math].
- Результатом работы алгоритма является [math]\displaystyle{ k }[/math] непересекающихся кластеров, делящих множество [math]\displaystyle{ P }[/math].
- Две точки называются соседними, если [math]\displaystyle{ sim(p_i, p_j) \geq \theta }[/math]
- Количеством общих соседей [math]\displaystyle{ link(p_i, p_j) }[/math] называется число точек, являющимися соседними для точек [math]\displaystyle{ p_i, p_j }[/math].
- Функцией связи между кластерами называется [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ n_i }[/math] - число объектов в кластере [math]\displaystyle{ C_i }[/math].
- Алгоритм начинает работу, разбив всё пространство на [math]\displaystyle{ n }[/math] кластеров.
- Затем на каждом шаге он вычисляет значение [math]\displaystyle{ g(C_i, C_j) }[/math] для каждой пары кластеров и объединяет эти кластеры в один.
- Алгоритм ведёт свою работу до тех пор, пока не получит [math]\displaystyle{ k }[/math] кластеров.
- В качестве функции [math]\displaystyle{ f( \theta ) }[/math] обычно используется функция [math]\displaystyle{ f(\theta ) = \frac{\theta - 1}{\theta + 1} }[/math] , [math]\displaystyle{ n_i^{1+2f(\theta )} }[/math] - ожидаемое число связей между парами объектов кластера [math]\displaystyle{ C_i }[/math].
- Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:
- [math]\displaystyle{ sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|} }[/math], где [math]\displaystyle{ |p_i| }[/math] - количество атрибутов в [math]\displaystyle{ p_i }[/math]. Данная функция удобна в случае, если все признаки категориальны
- Если же признаки непрерывны, то можно использовать функции расстояний в многомерных пространствах, предварительно нормализовав признаки.
Вычислительное ядро алгоритма
- Вычислительное ядро алгоритма состоит из двух основных частей.
- Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
- Итеративное объединению кластеров. За [math]\displaystyle{ n-k }[/math] шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных куча. Для каждого кластера math>i</math> хранится своя куча [math]\displaystyle{ q[i] }[/math], содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча [math]\displaystyle{ Q }[/math], содержащая все кластеры [math]\displaystyle{ j }[/math], упорядоченные по мере убывания функции качества [math]\displaystyle{ g(j, max(q[j])) }[/math]. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.
Макроструктура алгоритма
- Макроструктура состоит из последовательного выполнения двух шагов, описанных в описании ядра алгоритма:
- Построении матрицы связей
- Пересчёте куч и объединении кластеров
Схема реализации последовательного алгоритма
Описание реализации алгоритма на псевдокоде
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
Последовательная сложность алгоритма
- Временная сложность:
- Инициализация глобальной кучи - [math]\displaystyle{ O(n) }[/math]
- Инициализация локальной кучи - требует [math]\displaystyle{ O(n) }[/math]
- Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за [math]\displaystyle{ O(n*n^{2.37}) }[/math], в среднем за [math]\displaystyle{ O(n m_\alpha m_m) }[/math]
- Построение каждой кучи - [math]\displaystyle{ O(n) }[/math]
- Сортировка каждой кучи - [math]\displaystyle{ O( n \log{} n) }[/math]
- Основной цикл объединения кластеров выполняется в [math]\displaystyle{ n-k }[/math] итераций.
- Вставить новый кластер в в [math]\displaystyle{ O(n) }[/math] локальных куч размера [math]\displaystyle{ n }[/math] - [math]\displaystyle{ O( n \log{} n) }[/math]
Итого: [math]\displaystyle{ O(n^2 + n m_m m_a + n^2 \log{} n) }[/math]
- Сложность по памяти:
- Поскольку каждая точка [math]\displaystyle{ i }[/math] может иметь не более [math]\displaystyle{ \min \{ m_m m_i, n \} ) }[/math] связей, то общие затраты памяти не превышают [math]\displaystyle{ O(\min \{ n m_m m_a, n^2 \} ) }[/math].
- Хранение связей - [math]\displaystyle{ O(\min \{ n m_m m_a, n^2 \} ) }[/math] (поскольку каждая точка [math]\displaystyle{ i }[/math] может иметь не более [math]\displaystyle{ \min \{ m_m m_i, n \} ) }[/math] связей)
Итого: [math]\displaystyle{ O(\min \{ n^2, n m_m m_a \} ) }[/math]
Информационный граф
Ресурс параллелизма алгоритма
- Вычисление соседей. Затраты данных операций при условии достаточного количества ядер [math]\displaystyle{ T_1 = O(n) }[/math]
- Построения связей происходит в [math]\displaystyle{ n }[/math] этапов, в каждом из которых нужно сделать [math]\displaystyle{ m }[/math] расчетов(с учетом распараллеливания), где [math]\displaystyle{ m }[/math] - количество соседей. В худшем случае [math]\displaystyle{ T_2 = O(n^2) }[/math] в среднем случае [math]\displaystyle{ T_2 = O(n * m_a) }[/math], где [math]\displaystyle{ m_a }[/math] среднее ожидаемое число соседей.
- Построение одной кучи имеет сложность [math]\displaystyle{ O(n) }[/math]. Для каждой кучи сортировка [math]\displaystyle{ O(n * log(n)) }[/math]. Итоговая сложность создания локальных куч [math]\displaystyle{ T_3 = O(n * log(n)) }[/math].
- Построение и сортировка глобальной кучи: [math]\displaystyle{ T_4 = O(n * log(n)) }[/math].
- В цикле происходит выбор кластеров, сливание, пересчет и обновление куч. Для всех элементов кучи слитых кластеров пересчитывается значение связи, вставляется в кучу выбранного кластера информация о новом кластере, удаляется старое. Сложность [math]\displaystyle{ O(log(n)) }[/math]. В худшем случае, одна итерация цикла происходит за [math]\displaystyle{ T_i = O(log(n)) }[/math]. Количество итераций n - k. Итого: [math]\displaystyle{ T_5 = O((n - k) * log(n)) }[/math]. При k = 1, [math]\displaystyle{ T_5 = O(n * log(n)) }[/math]
Итоговая сложность в худшем случае равна:
- [math]\displaystyle{ 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]\displaystyle{ O(n * m_a) + O(n * log(n)) }[/math].
Сложность по времени:
- [math]\displaystyle{ O(n * (m_a + log(n))) }[/math].
Входные и выходные данные алгоритма
- Входные данные алгоритма:
- Множество объектов [math]\displaystyle{ P = \{p_1, \ldots , p_n\} }[/math]
- Целевое количество кластеров [math]\displaystyle{ k }[/math]
- Гиперпараметры алгоритма:
- Функция схожести [math]\displaystyle{ sim(p_i, p_j) }[/math]
- Пороговое значение схожести [math]\displaystyle{ \theta : 0\leq\theta\leq 1 }[/math]
- Функция ожидания количества соседей [math]\displaystyle{ f( \theta ) }[/math]
- Результат:
- Метка кластера для каждого объекта
Свойства алгоритма
- Детерменированность алгоритма
- Отношение последовательной и параллельной сложностей: [math]\displaystyle{ \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]\displaystyle{ \frac{O(n^2+nm_m m_\alpha + n^2\log n)}{2n+2} }[/math].