Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 113 промежуточных версий 4 участников)
Строка 1: Строка 1:
 +
{{Assignment|Algoman|Kronberg}}
 
{{algorithm
 
{{algorithm
 
| name              = Алгоритм динамической иерархической кластеризации CHAMELEON
 
| name              = Алгоритм динамической иерархической кластеризации CHAMELEON
 
| serial_complexity = <math>O(nm + n log n + m^2 log m)</math>
 
| serial_complexity = <math>O(nm + n log n + m^2 log m)</math>
−
| pf_height        = <math></math>
 
−
| pf_width          = <math></math>
 
 
| input_data        = <math>\frac{n (n - 1)}{2}</math>
 
| input_data        = <math>\frac{n (n - 1)}{2}</math>
 
| output_data      = <math>n</math>
 
| output_data      = <math>n</math>
 +
| pf_height        = <math>O(n+ n log(n) + m^2 log (m) + m log(m))</math>
 +
| pf_width          = <math>O(n)</math>
 
}}
 
}}
  
 
Автор описания [[Участник:ЕкатеринаКозырева|Е.А.Козырева]]
 
Автор описания [[Участник:ЕкатеринаКозырева|Е.А.Козырева]]
−
= часть. Свойства и структура алгоритмов =
+
= Свойства и структура алгоритмов =
  
 
== Общее описание алгоритма ==
 
== Общее описание алгоритма ==
−
Алгоритм CHAMELEON был предложен в 1999 году тремя учеными из университета Миннесоты – George Karypis, Eui-Hong (Sam) Han и Vipin Kumar[1].
+
Алгоритм CHAMELEON был предложен в 1999 году тремя учеными из университета Миннесоты – George Karypis, Eui-Hong (Sam) Han и Vipin Kumar<ref>George Karypis, Eui-Hong (Sam) Han и Vipin Kumar, «Chameleon: Hierarchical Clustering Using Dynamic Modeling», 1999.</ref>.
  
 
Предназначен для решения задач кластеризации. Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
 
Предназначен для решения задач кластеризации. Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
  
−
CHAMELEON - это агломеративный иерархический алгоритм кластеризации, ключевой особенностью которого является то, что он учитывает и взаимосвязанность, и близость при определении наиболее похожей пары подкластеров, основываясь на динамической модели. Это означает, что в процессе кластеризации два кластера объединяются, только если взаимосвязанность и близость (соседство) между двумя кластерами являются высокими по отношению к внутренней взаимосвязанности кластеров и близости элементов внутри кластеров. Кроме того, Хамелеон использует подход для моделирования степени взаимосвязанности и близости между каждой парой кластеров, который учитывает внутренние характеристики самих кластеров. Таким образом, он может автоматически адаптироваться к внутренним характеристикам объединяемых кластеров.
+
CHAMELEON - это агломеративный иерархический алгоритм кластеризации, ключевой особенностью которого является то, что он учитывает и взаимную связность, и сходство при определении наиболее похожей пары подкластеров, основываясь на динамической модели. Это означает, что в процессе кластеризации два кластера объединяются, только если их относительная взаимная связность и относительное взаимное сходство являются высокими по отношению к внутренней взаимосвязанности кластеров и близости элементов внутри кластеров. Кроме того, CHAMELEON использует подход для моделирования степени взаимосвязанности и близости между каждой парой кластеров, который учитывает внутренние характеристики самих кластеров. Таким образом, он может автоматически адаптироваться к внутренним характеристикам объединяемых кластеров.
  
−
CHAMELEON находит кластеры в наборе данных с помощью трехфазного алгоритма. На первой фазе происходит построение графа, путём добавления рёбер по принципу k ближайших соседей. На второй фазе CHAMELEON группирует полученные элементы в множество относительно небольших подкластеров. Во время третьей фазы применяется агломеративный иерархический алгоритм кластеризации, с помощью которого находятся естесственные кластеры путем многократного объединения подкластеров, полученных на прошлом этапе.
+
CHAMELEON находит кластеры в наборе данных с помощью трехфазного алгоритма. На первой фазе происходит построение графа, путём добавления рёбер по принципу k ближайших соседей. На второй фазе CHAMELEON группирует полученные элементы в множество относительно небольших подграфов. Во время третьей фазы применяется агломеративный иерархический алгоритм кластеризации, с помощью которого находятся естесственные кластеры путем многократного объединения подграфов, полученных на прошлом этапе.
 +
 
 +
[[File:Chameleon.png|1000px|thumb|center|Рисунок 1. Общая структура алгоритма CHAMELEON]]
  
 
== Математическое описание алгоритма ==
 
== Математическое описание алгоритма ==
 +
 +
''Исходные данные'':
 +
 +
* Множество из n точек <math>V= {v_{ij}}</math> в метрическом пространстве, которое задано симметрической матрицей расстояний <math>A</math> размера <math>n\times n</math>.
 +
* <math>k</math> - количество ближайших соседей для вершин, <math>k \in N, k \leq n</math>.
 +
* <math>l</math> - наименьшее число вершин, которое может содержать наибольший подграф на 2-м этапе, <math>l \in N, l \leq n</math>.
 +
 +
''Обозначения'':
 +
 +
* <math>G = (V, E)</math> - граф, полученный путём соединения каждой точки с её <math>k</math> ближайшими соседями.
 +
 +
* <math>K= \{K_{i}\}</math> - разбиение множества <math>V</math> на набор попарно непересекающихся связных подмножеств, полученное в результате выполнения второй фазы алгоритма.
 +
 +
* <math>G_{2} = (K, E_{2})</math> - взвешенный граф, вершинами которого являются получившиеся подграфы, а ребрами - количество ребер исходного графа, соединяющих соответствующие подграфы.
 +
 +
* <math>C = \{C_{i}\}</math> - итоговое разбиение множества вершин графа <math>G_{2}</math> на набор кластеров.
 +
 +
''Вспомогательные понятия''
 +
 +
*<math>EC_{(C_{i},C_{j})}</math> - абсолютная взаимная связность пары кластеров <math>C_{i}, C{j}</math>. Определяется как сумма весов ребер, соединяющих вершины, принадлежащие <math>C{i}</math> c вершинами из <math>C{j}</math>. Внутренняя связность <math>EC_{(C_{i},C_{i})}</math> вычисляется как сумма ребер, входящих в разделитель, разбивающий <math>C{i}</math> на два равных подграфа.
 +
 +
*<math>RI_{(C_{i},C_{j})} = \frac{|EC_{(C_{i},C_{j})}|}{(|EC_{C_{i}}|+|EC_{C_{j}}|)/2}</math> - относительная взаимная связность пары кластеров <math>C_{i}, C{j}</math>
 +
 +
*<math>S_{EC_{(C_{i},C_{j})}}</math> - абсолютное взаимное сходство пары кластеров <math>C_{i}, C{j}</math>. Подсчитывается как среднее сходство между соединенными вершинами, принадлежащими <math>C{i}</math> и <math>C{j}</math> соответственно. Соединения обусловлены разбиением общего графа, полученного на первом этапе алгоритма.
 +
 +
*<math> 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})}}}</math> - относительное взаимное сходство пары кластеров <math>C_{i}, C{j}</math>. Определяется как абсолютное сходство между этой парой кластеров, нормализованное с учетом их внутреннего сходства<ref>http://studopedia.ru/7_41934_algoritm-dinamicheskoy-ierarhicheskoy-klasterizatsii-CHAMELEON.html</ref>.
 +
 +
 +
 +
'''Первый этап'''
 +
 +
На первом этапе, согласно графо-ориентированному подходу, происходит построение графа <math>G = (V, E)</math> на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.
 +
[[Файл:Снимок chameleon 2.png|2000px|thumb|Рисунок 2. Объекты в пространстве - слева, граф по принципу 1-го ближайшего соседа - по центру, граф по принципу 3-х ближайших соседей - справа ]]
 +
 +
'''Второй этап'''
 +
 +
Алгоритм разделяет полученный граф на множество сравнительно малых подграфов <math>K= \{K_{i}\}</math>. Разделение происходит последовательно. На каждом шаге выбирается подграф, содержащий наибольшее число вершин. Этот граф разделяется на два подграфа так, что разделитель ребер графа минимален и каждый из получаемых подграфов содержит не менее 25 % вершин исходного графа. Процесс разделения останавливается, когда наибольший подграф содержит меньше некоторого заданного числа вершин. Обычно величина этого параметра задается равной значению от 1 до 5 % от числа объектов. Полученное множество связных графов считается множеством начальных кластеров, на котором требуется провести последовательное иерархическое объединение.
 +
 +
'''Третий этап'''
 +
 +
Третий этап заключается в итеративном преобразовании множества подграфов <math>K= \{K_{i}\}</math> в множество кластеров <math>C = \{C_{i}\}</math>. Алгоритм осуществляет агломеративную иерархическую кластеризацию на основании показателей <math>EC_{(C_{i},C_{j})}</math>, <math>S_{EC_{(C_{i},C_{j})}}</math>, <math>RI_{(C_{i},C_{j})} </math>, <math> RC_{(C_{i},C_{j})}</math>. Существует две стратегии анализа показателей сходства. Первая подразумевает наличие некоторых пороговых значений <math>T_{RI}</math> и <math>T_{RC}</math>. В соответствии с этой стратегией, алгоритм для каждого кластера <math>C_{i}</math> проверяет, отвечают ли смежные (наиболее близкие) ему кластеры условиям:
 +
 +
*<math>RI_{(C_{i},C_{j})} \geqslant T_{RI}</math>
 +
 +
*<math>RC_{(C_{i},C_{j})} \geqslant T_{RC}</math>
 +
 +
Если более одного смежного кластера отвечает этим условиям, то алгоритм выбирает для объединения наиболее связный кластер (граф), то есть такой кластер <math>C_{j}</math>, с которым у кластера <math>C_{i}</math> получается наибольшая абсолютная взаимная связность. По завершению прохода по всем кластерам, созданные таким образом пары объединяются. Параметры <math>T_{RI}</math> и <math>T_{RC}</math> могут использоваться для изменения характеристик получаемых кластеров.
 +
 +
Вторая стратегия заключается в использовании специальной функции, объединяющей понятия относительной взаимной связности и относительного взаимного сходства. На каждом шаге выбираются те кластеры для объединения, которые максимизируют эту функцию:
 +
 +
<math>RI_{(C_{i},C_{j})}*RC_{(C_{i},C_{j})}^\alpha</math>,
 +
 +
где <math>\alpha</math> выбирается пользователем. Если <math>\alpha > 1 </math>, то алгоритм придает большее значение относительному взаимному сходству, а если <math>\alpha <  1 </math>, то большее значение имеет относительная взаимная связность.
 +
 +
 +
''Вычисляемые данные'':
 +
 +
<math>U = (u_1, u_2, ..., u_n)</math> - n-мерный вектор, где <math>u_i \in N_{[C]}</math> - порядковый номер кластера, к которому принадлежит вершина i исходного множества V.
 +
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
 +
 +
Алгоритм имеет три вычислительных ядра, по одному на каждый этап.
 +
 +
На первом этапе вычислительным ядром является процесс нахождения <math>k</math> ближайших соседей для каждой вершины, который заключается в анализе матрицы расстояний.
 +
 +
На втором этапе вычислительным ядром является процесс поиска подходящего разбиения очередного подграфа на два графа с минимизацией разделителя ребер графа.
 +
 +
На третьем этапе вычислительным ядром является расчет величин <math>EC_{(C_{i},C_{j})}</math>, <math>S_{EC_{(C_{i},C_{j})}}</math>, <math>RI_{(C_{i},C_{j})} </math>, <math> RC_{(C_{i},C_{j})}</math> для каждой пары смежных кластеров.
 +
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==
 +
 +
Как уже рассказывалось ранее, алгоритм включает в себя три основных этапа, каждый из которых, по сути, является отдельным алгоритмом. Этапы выполняются последовательно относительно друг друга.
 +
 +
Макрооперация на первом этапе - процедура нахождения <math>k</math> ближайших соседей, на втором - процедура разбиения наибольшего подграфа на два графа, на третьем - процедура вычисления показателей сходства, на основе которых принимается решение о слиянии подграфов в кластер.
 +
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
 +
 +
'''Первый этап'''
 +
<source lang="cpp">
 +
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] единицей
 +
            }
 +
 
 +
    }
 +
</source>
 +
 +
'''Второй этап'''
 +
 +
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<>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) Для построения графа на основе метода k ближайших соседей для n вершин требуется <math>O(n log(n))</math> операций <ref>J.H. Friedman, J.L. Bentley, and R.A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3:209–226, 1977.</ref>; для наборов данных большой размерности эта величина составляет <math>O(n^2)</math> операций <ref>S. Berchtold, C. Bohm, D. Keim, and H.-P. Kriegel. Cost model for nearest neighbor search in high dimensional data space. In Proc. of Symposium on Principles of Database Systems, Tucson, Arizona, 1997.</ref>;
 +
 +
2) Для выделения множества сравнительно малых связных подграфов требуется <math>nm</math> операций, где <math>m</math> - количество подграфов, полученных на втором этапе алгоритма;
 +
 +
3) Формирование набора кластеров, на основе множества подграфов, полученных на предыдущем этапе, требует <math>m^2log(m)</math> операций.
 +
 +
Итого, для n вершин получаем последовательную сложность <math>O(n log(n)+nm+m^2log(m))</math>.
 +
 
== Информационный граф ==
 
== Информационный граф ==
 +
[[File:СК.png]]
 +
 
== Ресурс параллелизма алгоритма ==
 
== Ресурс параллелизма алгоритма ==
 +
 +
Первый этап работы алгоритма можно распределить между <math>n</math> процессами. На вход каждому процессу подается своя вершина, далее происходит процедура поиска <math>k</math> ближайших соседей. Параллельная сложность составляет <math>O(n)</math>.
 +
 +
Второй и третий этапы можно распараллелить частично.
 +
 +
Второй этап распараллеливается путем подачи на вход свободному процессу очередного подграфа для разделения. Число итераций оценивается в <math>O(n log(n))</math>.
 +
 +
Третий этап делится на расчет показателей схожести и соединение подграфов в кластеры. Процесс расчета показателей можно распараллелить, подавая каждому процессу на вход пару подграфов. Сложность этого процесса оценивается как <math>m log(m)</math>. Соединение подграфов в кластеры выполняется последовательно, сложность процесса составляет <math>m^2 log(m)</math>
 +
 +
Таким образом получаем общую параллельную сложность алгоритма: <math>O(n+ n log(n) + m^2 log (m) + m log(m))</math>
 +
 
== Входные и выходные данные алгоритма ==
 
== Входные и выходные данные алгоритма ==
−
''Входные данные'':
+
'''Входные данные'''
  
−
1. Симметрическая матрица <math>A</math> расстояний между элементами данных, размера <math>n\times n</math>  (элементы <math>a_{ij}</math>).
+
1. Симметрическая матрица <math>A</math> расстояний между элементами данных размера <math>n\times n</math> с нулями на главной диагонали (<math>a_{ii}= 0, i = 1, \ldots, N</math>).
−
    <math>A</math> – содержит нули на главной диагонали, т.е. <math>d_{ii}= 0, i = 1, \ldots, N</math>
 
  
−
2. <math>k</math> - количество ближайших соседей для вершин (рекомендуемое значение <math>k</math> от 5 до 20 в зависимости от количества анализируемых объектов).
+
2. <math>k</math> - количество ближайших соседей для вершин (рекомендуемое значение <math>k</math> от 5 до 20 в зависимости от количества анализируемых объектов).
  
−
3. <math>l</math> - наименьшее число вершин, которое может содержать наибольший подкластер на 2-м этапе . Величина этого параметра варьируется от 1 до 5 % от общего числа объектов.
+
3. <math>l</math> - наименьшее число вершин, которое может содержать наибольший подкластер на 2-м этапе . Величина этого параметра варьируется от 1 до 5 % от общего числа объектов.
  
−
''Объём входных данных'':
+
'''Объём входных данных'''
−
<math>\frac{n (n - 1)}{2}</math> (в силу симметричности и нулевой главной диагонали достаточно хранить только  над/поддиагональные элементы).
 
  
−
''Выходные данные'':
+
<math>\frac{n (n - 1)}{2}</math> (в силу симметричности и нулевой главной диагонали достаточно хранить только  над/поддиагональные элементы).
−
Вектор из <math>n</math> чисел <math>u_{1}, u_{2}, \ldots, u_{N}</math>, где <math>u_{i}</math> - целое число, соответствующее кластеру <math>i</math>-го объекта.
 
  
−
''Объём выходных данных'':
+
'''Выходные данные'''
−
<math>n</math>
+
 
 +
Вектор из <math>n</math> чисел <math>u_{1}, u_{2}, \ldots, u_{N}</math>, где <math>u_{i}</math> - целое число, соответствующее кластеру <math>i</math>-го объекта.
 +
 
 +
'''Объём выходных данных'''
 +
 
 +
<math>n</math>
  
 
== Свойства алгоритма ==
 
== Свойства алгоритма ==
−
= часть. Программная реализация алгоритма =
+
Соотношение последовательной и параллельной сложности на первом этапе является ''линейным'' для больших наборов данных и логарифмическим для n вершин. На втором этапе сложно оценить это соотношение - оно сильно зависит от параметров <math>k</math> и <math>l</math>. На третьем этапе соотношение равно <math>O(1)</math>;
 +
 
 +
Оценка ''вычислительной мощности'' выглядит следующим образом:
 +
 
 +
<math>O(1)</math>                  для 1-го этапа;
 +
 
 +
<math>O(\frac{nm}{n^2+m^2})</math>  для 2-го этапа;
 +
 
 +
<math>O(\frac{m^2log(m)}{m^2+n})</math> для 3-го этапа;
 +
 
 +
Алгоритм является ''недетерминированным''. Хотя 1-й этап детерминирован, на 2-ом этапе могут быть найдены различные разбиения на подграфы, что повлияет и на итоговый результат работы алгоритма.
 +
 
 +
= Программная реализация алгоритма =
 +
== Особенности реализации последовательного алгоритма ==
 +
== Локальность данных и вычислений ==
 +
== Возможные способы и особенности параллельной реализации алгоритма ==
 
== Масштабируемость алгоритма и его реализации ==
 
== Масштабируемость алгоритма и его реализации ==
 +
 +
Исследовалась масштабируемость параллельной реализации алгоритма для 4 и 8 потоков.<ref name="tr">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>
 +
 +
Результаты отображены в виде графика. Можно отметить, что с увеличением объема входных данных растут ускорение и эффективность работы алгоритма. Однако эффективность снижается при увеличении числа потоков.
 +
 +
[[File:Масштабирование.jpg|1000px|center]]
 +
 +
== Динамические характеристики и эффективность реализации алгоритма ==
 +
== Выводы для классов архитектур ==
 
== Существующие реализации алгоритма ==
 
== Существующие реализации алгоритма ==
 +
Последовательная реализация алгоритма доступна по ссылке <ref>http://read.pudn.com/downloads36/sourcecode/math/115779/chameleon/chameleon.c__.htm</ref>.
 +
 +
CHAMELEON можно реализовать с использованием графовых библиотек METIS <ref>http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
 +
</ref>, hMETIS <ref>http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview</ref> и RANN <ref>https://cran.r-project.org/web/packages/RANN/index.html</ref>.
 +
 +
Существует исследование, связанное с реализацией CHAMELEON посредством технологии OpenMP, оно было рассмотрено в пункте 2.4.
 +
 +
Параллельных реализаций алгоритма CHAMELEON не найдено.
 +
 
= Литература =
 
= Литература =
−
[1] George Karypis, Eui-Hong (Sam) Han и Vipin Kumar, «Chameleon: Hierarchical Clustering Using Dynamic Modeling», 1999.
 
−
 
−
[2] http://studopedia.ru/7_41934_algoritm-dinamicheskoy-ierarhicheskoy-klasterizatsii-CHAMELEON.html
 

Текущая версия на 16:11, 20 декабря 2016

Symbol confirmed.svgЭта работа успешно выполнена
Преподавателю: в основное пространство, в подстраницу
Данное задание было проверено и зачтено.
Проверено Kronberg и Algoman.



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


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

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

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

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

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

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

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

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

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

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

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

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

  • [math]G = (V, E)[/math] - граф, полученный путём соединения каждой точки с её [math]k[/math] ближайшими соседями.
  • [math]K= \{K_{i}\}[/math] - разбиение множества [math]V[/math] на набор попарно непересекающихся связных подмножеств, полученное в результате выполнения второй фазы алгоритма.
  • [math]G_{2} = (K, E_{2})[/math] - взвешенный граф, вершинами которого являются получившиеся подграфы, а ребрами - количество ребер исходного графа, соединяющих соответствующие подграфы.
  • [math]C = \{C_{i}\}[/math] - итоговое разбиение множества вершин графа [math]G_{2}[/math] на набор кластеров.

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

  • [math]EC_{(C_{i},C_{j})}[/math] - абсолютная взаимная связность пары кластеров [math]C_{i}, C{j}[/math]. Определяется как сумма весов ребер, соединяющих вершины, принадлежащие [math]C{i}[/math] c вершинами из [math]C{j}[/math]. Внутренняя связность [math]EC_{(C_{i},C_{i})}[/math] вычисляется как сумма ребер, входящих в разделитель, разбивающий [math]C{i}[/math] на два равных подграфа.
  • [math]RI_{(C_{i},C_{j})} = \frac{|EC_{(C_{i},C_{j})}|}{(|EC_{C_{i}}|+|EC_{C_{j}}|)/2}[/math] - относительная взаимная связность пары кластеров [math]C_{i}, C{j}[/math]
  • [math]S_{EC_{(C_{i},C_{j})}}[/math] - абсолютное взаимное сходство пары кластеров [math]C_{i}, C{j}[/math]. Подсчитывается как среднее сходство между соединенными вершинами, принадлежащими [math]C{i}[/math] и [math]C{j}[/math] соответственно. Соединения обусловлены разбиением общего графа, полученного на первом этапе алгоритма.
  • [math] 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})}}}[/math] - относительное взаимное сходство пары кластеров [math]C_{i}, C{j}[/math]. Определяется как абсолютное сходство между этой парой кластеров, нормализованное с учетом их внутреннего сходства[2].


Первый этап

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

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

Второй этап

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

Третий этап

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

  • [math]RI_{(C_{i},C_{j})} \geqslant T_{RI}[/math]
  • [math]RC_{(C_{i},C_{j})} \geqslant T_{RC}[/math]

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

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

[math]RI_{(C_{i},C_{j})}*RC_{(C_{i},C_{j})}^\alpha[/math],

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


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

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

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

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

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

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

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

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

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

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

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 вершин требуется [math]O(n log(n))[/math] операций [3]; для наборов данных большой размерности эта величина составляет [math]O(n^2)[/math] операций [4];

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

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

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

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

СК.png

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]n[/math]

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

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

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

[math]O(1)[/math] для 1-го этапа;

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

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

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

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

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

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

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

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

Исследовалась масштабируемость параллельной реализации алгоритма для 4 и 8 потоков.[5]

Результаты отображены в виде графика. Можно отметить, что с увеличением объема входных данных растут ускорение и эффективность работы алгоритма. Однако эффективность снижается при увеличении числа потоков.

Масштабирование.jpg

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

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

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

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

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

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

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

3 Литература

  1. ↑ George Karypis, Eui-Hong (Sam) Han и Vipin Kumar, «Chameleon: Hierarchical Clustering Using Dynamic Modeling», 1999.
  2. ↑ http://studopedia.ru/7_41934_algoritm-dinamicheskoy-ierarhicheskoy-klasterizatsii-CHAMELEON.html
  3. ↑ J.H. Friedman, J.L. Bentley, and R.A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3:209–226, 1977.
  4. ↑ S. Berchtold, C. Bohm, D. Keim, and H.-P. Kriegel. Cost model for nearest neighbor search in high dimensional data space. In Proc. of Symposium on Principles of Database Systems, Tucson, Arizona, 1997.
  5. ↑ http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf
  6. ↑ http://read.pudn.com/downloads36/sourcecode/math/115779/chameleon/chameleon.c__.htm
  7. ↑ http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
  8. ↑ http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview
  9. ↑ https://cran.r-project.org/web/packages/RANN/index.html
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:ЕкатеринаКозырева/Алгоритм_динамической_иерархической_кластеризации_CHAMELEON&oldid=21466