Участник:ЕкатеринаКозырева/Алгоритм динамической иерархической кластеризации CHAMELEON

Эта работа прошла предварительную проверку Дата последней правки страницы: 29.11.2016 Данная работа соответствует формальным критериям. Проверено Kronberg.

Алгоритм динамической иерархической кластеризации CHAMELEON
Последовательный алгоритм
Последовательная сложность	$O(nm + n log n + m^2 log m)$
Объём входных данных	$\frac{n (n - 1)}{2}$
Объём выходных данных	$n$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(n+ n log(n) + m^2 log (m) + m log(m))$
Ширина ярусно-параллельной формы	$O(n)$

Автор описания Е.А.Козырева

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

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

Алгоритм CHAMELEON был предложен в 1999 году тремя учеными из университета Миннесоты – George Karypis, Eui-Hong (Sam) Han и Vipin Kumar.

Предназначен для решения задач кластеризации. Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.

CHAMELEON - это агломеративный иерархический алгоритм кластеризации, ключевой особенностью которого является то, что он учитывает и взаимную связность, и сходство при определении наиболее похожей пары подкластеров, основываясь на динамической модели. Это означает, что в процессе кластеризации два кластера объединяются, только если их относительная взаимная связность и относительное взаимное сходство являются высокими по отношению к внутренней взаимосвязанности кластеров и близости элементов внутри кластеров. Кроме того, CHAMELEON использует подход для моделирования степени взаимосвязанности и близости между каждой парой кластеров, который учитывает внутренние характеристики самих кластеров. Таким образом, он может автоматически адаптироваться к внутренним характеристикам объединяемых кластеров.

CHAMELEON находит кластеры в наборе данных с помощью трехфазного алгоритма. На первой фазе происходит построение графа, путём добавления рёбер по принципу k ближайших соседей. На второй фазе CHAMELEON группирует полученные элементы в множество относительно небольших подграфов. Во время третьей фазы применяется агломеративный иерархический алгоритм кластеризации, с помощью которого находятся естесственные кластеры путем многократного объединения подграфов, полученных на прошлом этапе.

Рисунок 1. Общая структура алгоритма CHAMELEON

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

Исходные данные:

• Множество из n точек $V= {v_{ij}}$ в метрическом пространстве, которое задано симметрической матрицей расстояний $A$ размера $n\times n$.
• $k$ - количество ближайших соседей для вершин, $k \in N, k \leq n$.
• $l$ - наименьшее число вершин, которое может содержать наибольший подграф на 2-м этапе, $l \in N, l \leq n$.

Обозначения:

• $G = (V, E)$ - граф, полученный путём соединения каждой точки с её $k$ ближайшими соседями.

• $K= \{K_{i}\}$ - разбиение множества $V$ на набор попарно непересекающихся связных подмножеств, полученное в результате выполнения второй фазы алгоритма.

• $G_{2} = (K, E_{2})$ - взвешенный граф, вершинами которого являются получившиеся подграфы, а ребрами - количество ребер исходного графа, соединяющих соответствующие подграфы.

• $C = \{C_{i}\}$ - итоговое разбиение множества вершин графа $G_{2}$ на набор кластеров.

Вспомогательные понятия

• $EC_{(C_{i},C_{j})}$ - абсолютная взаимная связность пары кластеров $C_{i}, C{j}$. Определяется как сумма весов ребер, соединяющих вершины, принадлежащие $C{i}$ c вершинами из $C{j}$. Внутренняя связность $EC_{(C_{i},C_{i})}$ вычисляется как сумма ребер, входящих в разделитель, разбивающий $C{i}$ на два равных подграфа.

• $RI_{(C_{i},C_{j})} = \frac{|EC_{(C_{i},C_{j})}|}{(|EC_{C_{i}}|+|EC_{C_{j}}|)/2}$ - относительная взаимная связность пары кластеров $C_{i}, C{j}$

• $S_{EC_{(C_{i},C_{j})}}$ - абсолютное взаимное сходство пары кластеров $C_{i}, C{j}$. Подсчитывается как среднее сходство между соединенными вершинами, принадлежащими $C{i}$ и $C{j}$ соответственно. Соединения обусловлены разбиением общего графа, полученного на первом этапе алгоритма.

• $RC_{(C_{i},C_{j})}= \frac{S_{EC_{(C_{i},C_{j})}}}{\frac{|C_{i}|}{|C_{i}+C_{j}|}*S_{EC_{(C_{i})}}+\frac{|C_{i}|}{|C_{i}+C_{j}|}*S_{EC_{(C_{j})}}}$ - относительное взаимное сходство пары кластеров $C_{i}, C{j}$. Определяется как абсолютное сходство между этой парой кластеров, нормализованное с учетом их внутреннего сходства.

Первый этап

На первом этапе, согласно графо-ориентированному подходу, происходит построение графа $G = (V, E)$ на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.

Рисунок 2. Объекты в пространстве - слева, граф по принципу 1-го ближайшего соседа - по центру, граф по принципу 3-х ближайших соседей - справа

Второй этап

Алгоритм разделяет полученный граф на множество сравнительно малых подграфов $K= \{K_{i}\}$. Разделение происходит последовательно. На каждом шаге выбирается подграф, содержащий наибольшее число вершин. Этот граф разделяется на два подграфа так, что разделитель ребер графа минимален и каждый из получаемых подграфов содержит не менее 25 % вершин исходного графа. Процесс разделения останавливается, когда наибольший подграф содержит меньше некоторого заданного числа вершин. Обычно величина этого параметра задается равной значению от 1 до 5 % от числа объектов. Полученное множество связных графов считается множеством начальных кластеров, на котором требуется провести последовательное иерархическое объединение.

Третий этап

Третий этап заключается в итеративном преобразовании множества подграфов $K= \{K_{i}\}$ в множество кластеров $C = \{C_{i}\}$. Алгоритм осуществляет агломеративную иерархическую кластеризацию на основании показателей $EC_{(C_{i},C_{j})}$, $S_{EC_{(C_{i},C_{j})}}$, $RI_{(C_{i},C_{j})}$, $RC_{(C_{i},C_{j})}$. Существует две стратегии анализа показателей сходства. Первая подразумевает наличие некоторых пороговых значений $T_{RI}$ и $T_{RC}$. В соответствии с этой стратегией, алгоритм для каждого кластера $C_{i}$ проверяет, отвечают ли смежные (наиболее близкие) ему кластеры условиям:

• $RI_{(C_{i},C_{j})} \geqslant T_{RI}$

• $RC_{(C_{i},C_{j})} \geqslant T_{RC}$

Если более одного смежного кластера отвечает этим условиям, то алгоритм выбирает для объединения наиболее связный кластер (граф), то есть такой кластер $C_{j}$, с которым у кластера $C_{i}$ получается наибольшая абсолютная взаимная связность. По завершению прохода по всем кластерам, созданные таким образом пары объединяются. Параметры $T_{RI}$ и $T_{RC}$ могут использоваться для изменения характеристик получаемых кластеров.

Вторая стратегия заключается в использовании специальной функции, объединяющей понятия относительной взаимной связности и относительного взаимного сходства. На каждом шаге выбираются те кластеры для объединения, которые максимизируют эту функцию:

$RI_{(C_{i},C_{j})}*RC_{(C_{i},C_{j})}^\alpha$,

где $\alpha$ выбирается пользователем. Если $\alpha \gt 1$, то алгоритм придает большее значение относительному взаимному сходству, а если $\alpha \lt 1$, то большее значение имеет относительная взаимная связность.

Вычисляемые данные:

$U = (u_1, u_2, ..., u_n)$ - n-мерный вектор, где $u_i \in N_{[C]}$ - порядковый номер кластера, к которому принадлежит вершина i исходного множества V.

1.3 Вычислительное ядро алгоритма

Алгоритм имеет три вычислительных ядра, по одному на каждый этап.

На первом этапе вычислительным ядром является процесс нахождения $k$ ближайших соседей для каждой вершины, который заключается в анализе матрицы расстояний.

На втором этапе вычислительным ядром является процесс поиска подходящего разбиения очередного подграфа на два графа с минимизацией разделителя ребер графа.

На третьем этапе вычислительным ядром является расчет величин $EC_{(C_{i},C_{j})}$, $S_{EC_{(C_{i},C_{j})}}$, $RI_{(C_{i},C_{j})}$, $RC_{(C_{i},C_{j})}$ для каждой пары смежных кластеров.

1.4 Макроструктура алгоритма

Как уже рассказывалось ранее, алгоритм включает в себя три основных этапа, каждый из которых, по сути, является отдельным алгоритмом. Этапы выполняются последовательно относительно друг друга.

Макрооперация на первом этапе - процедура нахождения $k$ ближайших соседей, на втором - процедура разбиения наибольшего подграфа на два графа, на третьем - процедура вычисления показателей сходства, на основе которых принимается решение о слиянии подграфов в кластер.

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

Первый этап

 int n; //количество вершин
 int k; //количество соседей
 int A[n][n] //матрица расстояний
 int D[k] //массив вершин-соседей
 int E[n][n] //матрица ребер графа <math>G_{2} = (K, E_{2})</math>
 for i=1 to n-1 do
     {
       for j=i+1 to n do 
            {
               //заполняем массив вершин-соседей вставляя новые вершины, если они ближе, чем самая далекая из массива. 
            }
       for j=0 to k do 
            {
               //для каждой вершины соседа заполняем соответствующую ячейку из матрицы E[n][n] единицей
            }
   
     }

Второй этап

1. Все связные подграфы в отсортированном порядке помещаются в список;
2. Берем наибольший элемент списка, вычисляем количество его вершин. Если число вершин > l, то идем в пункт 3. Иначе в пункт 5;
3. Разбиваем подграф на два подграфа таким образом, чтобы разделитель ребер графа был минимален и каждый из получаемых подграфов содержал не менее 25 % вершин исходного графа;
4. Добавляем полученные элементы в список подграфов таким образом, чтобы список оставался отсортированным. Идем в пункт 2;
5. Нашли искомое множество подграфов math>K = \{K_{i}\}</math>;
6. Создаем и заполняем матрицу матрицу расстояний для графа [math]G_{2} = (K, E_{2})[/math]. Получаем искомый набор рёбер [math]E_{2}[/math].

Третий этап

1. Заводим два массива: а) массив кластеров C, полученных на предыдущем этапе, б) массив объединений кластеров F, которые мы будем получать на этом этапе;
2. Берем следующий кластер [math]C_{i}[/math] (на первом шаге - первый). Если все кластеры просмотрены, идем в пункт 6;
3. Берем следующий кластер [math]C_{j}, i\lt \gt j[/math]. Если все кластеры просмотрены, то идем в пункт 2;
4. Проверяем смежность [math]C_{i}[/math] и [math]C_{j}[/math]. Если не смежны, то возвращаемся в пункт 3. Если смежны, идем в пункт 5;
5. Рассчитываем показатели [math]RI_{(C_{i},C_{j})}[/math] и [math] RC_{(C_{i},C_{j})}[/math]. Проверяем, удовлетворяют ли найденные значения условиям:
*[math]RI_{(C_{i},C_{j})} \geqslant T_{RI}[/math]
*[math]RC_{(C_{i},C_{j})} \geqslant T_{RC}[/math]
Если нет, то идем в пункт 3. Иначе если смежность пары кластеров выше, чем у предыдущих найденных, то [math]F_{i}=j[/math]. Идем в пункт 3;
6. Если в списке F есть хотя бы одна пара кластеров для слияния, то выполняем слияние, обновляем массив кластеров и массив объединений кластеров. Идем в пункт 2.

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

1) Для построения графа на основе метода k ближайших соседей для n вершин требуется $O(n log(n))$ операций ; для наборов данных большой размерности эта величина составляет $O(n^2)$ операций ;

2) Для выделения множества сравнительно малых связных подграфов требуется $nm$ операций, где $m$ - количество подграфов, полученных на втором этапе алгоритма;

3) Формирование набора кластеров, на основе множества подграфов, полученных на предыдущем этапе, требует $m^2log(m)$ операций.

Итого, для n вершин получаем последовательную сложность $O(n log(n)+nm+m^2log(m))$.

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

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

Первый этап работы алгоритма можно распределить между $n$ процессами. На вход каждому процессу подается своя вершина, далее происходит процедура поиска $k$ ближайших соседей. Параллельная сложность составляет $O(n)$.

Второй и третий этапы можно распараллелить частично.

Второй этап распараллеливается путем подачи на вход свободному процессу очередного подграфа для разделения. Число итераций оценивается в $O(n log(n))$.

Третий этап делится на расчет показателей схожести и соединение подграфов в кластеры. Процесс расчета показателей можно распараллелить, подавая каждому процессу на вход пару подграфов. Сложность этого процесса оценивается как $m log(m)$. Соединение подграфов в кластеры выполняется последовательно, сложность процесса составляет $m^2 log(m)$

Таким образом получаем общую параллельную сложность алгоритма: $O(n+ n log(n) + m^2 log (m) + m log(m))$

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

Входные данные

1. Симметрическая матрица $A$ расстояний между элементами данных размера $n\times n$ с нулями на главной диагонали ($a_{ii}= 0, i = 1, \ldots, N$).

2. $k$ - количество ближайших соседей для вершин (рекомендуемое значение $k$ от 5 до 20 в зависимости от количества анализируемых объектов).

3. $l$ - наименьшее число вершин, которое может содержать наибольший подкластер на 2-м этапе . Величина этого параметра варьируется от 1 до 5 % от общего числа объектов.

Объём входных данных

$\frac{n (n - 1)}{2}$ (в силу симметричности и нулевой главной диагонали достаточно хранить только над/поддиагональные элементы).

Выходные данные

Вектор из $n$ чисел $u_{1}, u_{2}, \ldots, u_{N}$, где $u_{i}$ - целое число, соответствующее кластеру $i$-го объекта.

Объём выходных данных

$n$

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

Соотношение последовательной и параллельной сложности на первом этапе является линейным для больших наборов данных и логарифмическим для n вершин. На втором этапе сложно оценить это соотношение - оно сильно зависит от параметров $k$ и $l$. На третьем этапе соотношение равно $O(1)$;

Оценка вычислительной мощности выглядит следующим образом:

$O(1)$ для 1-го этапа;

$O(\frac{nm}{n^2+m^2})$ для 2-го этапа;

$O(\frac{m^2log(m)}{m^2+n})$ для 3-го этапа;

Алгоритм является недетерминированным. Хотя 1-й этап детерминирован, на 2-ом этапе могут быть найдены различные разбиения на подграфы, что повлияет и на итоговый результат работы алгоритма.

2 Программная реализация алгоритма

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

Масштабируемость исследовалась на основе работы, презентующей пробную версию параллельной реализации алгоритма для различного числа потоков. График показывает, что эффективность и скорость работы алгоритма растут с увеличением объема входных данных. Однако, в упомянутой выше работе отмечается, что эффективность алгоритма падает с ростом количества потоков.

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

Последовательная реализация алгоритма доступна по ссылке .

CHAMELEON можно реализовать с использованием графовых библиотек METIS , hMETIS и RANN .

Существует исследование, связанное с реализацией CHAMELEON посредством технологии OpenMP, оно было рассмотрено в пункте 2.4.

Параллельных реализаций алгоритма CHAMELEON не найдено.