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

Участник:Артем Таран/Графо-ориентированный алгоритм кластеризации CHAMELEON: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 59 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
{{Assignment|Algoman|Kronberg}}
 +
 
{{algorithm
 
{{algorithm
 
| name              = Графо-ориентированный алгоритм кластеризации CHAMELEON
 
| name              = Графо-ориентированный алгоритм кластеризации CHAMELEON
 
| serial_complexity = <math>O(n^2+nm+m^2log(m))</math>
 
| serial_complexity = <math>O(n^2+nm+m^2log(m))</math>
| pf_height        = <math>O(n + log(n) + m^2log(m))</math>
+
| pf_height        = <math>O(n + log(n) + mlog(m) + m^2log(m))</math>
 
| pf_width          = <math>O(n)</math>
 
| pf_width          = <math>O(n)</math>
 
| input_data        = <math>\frac{n (n - 1)}{2}</math>
 
| input_data        = <math>\frac{n (n - 1)}{2}</math>
Строка 8: Строка 10:
 
}}
 
}}
  
Статью подготовили: [[Участник:Артем_Таран|Артём Таран Иванович]]( разделы 1.1 - 1.10), [[Участник:ShimchikN|Шимчик Никита Владимирович]]( разделы 1.1 - 1.10).
+
Статью подготовили: [[Участник:Артем_Таран|Артём Таран Иванович]] (разделы 1.1 - 1.10, 2.7), [[Участник:ShimchikN|Шимчик Никита Владимирович]] (разделы 1.1 - 1.10, 2.7).
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
  
Строка 15: Строка 17:
 
Кластеризация — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры) с минимизацией межкластерного сходства и максимизацией внутрикластерного сходства.
 
Кластеризация — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры) с минимизацией межкластерного сходства и максимизацией внутрикластерного сходства.
  
Графо-ориентированный алгоритм кластеризации CHAMELEON - относительно новый алгоритм, который измеряет сходство двух кластеров на основе
+
Графо-ориентированный алгоритм кластеризации CHAMELEON<ref name="rt">http://www-users.cs.umn.edu/~han/dmclass/chameleon.pdf</ref> - алгоритм, который измеряет сходство двух кластеров на основе
 
динамической модели. В процессе кластеризации два кластера объединяются, только если показатели взаимосвязанности и близости между двумя кластерами являются высокими по отношению к показателям внутренней взаимосвязанности кластеров и близости элементов внутри этих кластеров. Процесс слияния с использованием динамической модели, использующийся в данном алгоритме облегчает открытие
 
динамической модели. В процессе кластеризации два кластера объединяются, только если показатели взаимосвязанности и близости между двумя кластерами являются высокими по отношению к показателям внутренней взаимосвязанности кластеров и близости элементов внутри этих кластеров. Процесс слияния с использованием динамической модели, использующийся в данном алгоритме облегчает открытие
 
природных и однородных кластеров. Методология динамического моделирования кластеров, использующаяся в CHAMELEON,
 
природных и однородных кластеров. Методология динамического моделирования кластеров, использующаяся в CHAMELEON,
 
применима ко всем типам данных, для которых может быть построена матрица подобия.
 
применима ко всем типам данных, для которых может быть построена матрица подобия.
 +
 +
Следует отметить, что конечное число кластеров не задаётся явным образом и зависит как от выбора параметров алгоритма, так и от внутренней структуры входных данных.
  
 
Алгоритм кластеризации CHAMELEON включает в себя три этапа:
 
Алгоритм кластеризации CHAMELEON включает в себя три этапа:
  
 
1) Построение графа, путём добавления рёбер по принципу k ближайших соседей.
 
1) Построение графа, путём добавления рёбер по принципу k ближайших соседей.
 
[[Файл:Графы k ближайших соседей.jpg|500px| На рисунке изображен принцип k ближайших соседей: 1) объекты в пространстве, 2) граф по принципу 1-го ближайшего соседа, 3) граф по принципу 2-го ближайшего соседа, 4)граф по принципу 3-х ближайших соседей]]
 
  
 
2) Выделение множества сравнительно малых связных подграфов.
 
2) Выделение множества сравнительно малых связных подграфов.
  
 
3) Формирование набора кластеров, на основе множества подграфов, полученных на предыдущем этапе.
 
3) Формирование набора кластеров, на основе множества подграфов, полученных на предыдущем этапе.
 +
 +
[[Файл:Графы k ближайших соседей.jpg|1000px|thumb|center|Графы k ближайших соседей: 1) объекты в пространстве, 2) граф по принципу 1-го ближайшего соседа, 3) граф по принципу 2-го ближайшего соседа, 4) граф по принципу 3-х ближайших соседей<ref name="rt">http://www-users.cs.umn.edu/~han/dmclass/chameleon.pdf</ref>]]
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
 
==== Данные ====
 
==== Данные ====
* '''Исходные данные''': множество из <math>n</math> точек <math>V = \{v_{i}\}</math> в метрическом пространстве, которое может быть задано в виде треугольной матрицы расстояний <math>A</math> размера <math>n\times n</math>.
+
* '''Исходные данные''': множество из <math>n</math> точек <math>V = \{v_{i}\}</math> в метрическом пространстве, которое может быть задано в виде треугольной матрицы расстояний <math>A</math> размера <math>n\times n</math>; натуральное число <math>k</math>, используемое в качестве параметра алгоритма поиска k ближайших соседей.
  
 
* '''Промежуточный результат после первого этапа''': граф <math>G = (V, E)</math>, полученный путём соединения каждой точки с её <math>k</math> ближайшими соседями.
 
* '''Промежуточный результат после первого этапа''': граф <math>G = (V, E)</math>, полученный путём соединения каждой точки с её <math>k</math> ближайшими соседями.
Строка 74: Строка 78:
 
<math>RI_{(C_{i},C_{j})}*RC_{(C_{i},C_{j})}^\alpha</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>\alpha</math> выбирается пользователем. Если <math>\alpha > 1 </math>, то алгоритм придает большее значение относительному взаимному сходству, а если <math>\alpha <  1 </math>, то большее значение имеет относительная взаимная связность. Разумеется, данный подход позволяет получить полную дендрограмму кластерного анализа<ref name="rty">http://studopedia.ru/7_41934_algoritm-dinamicheskoy-ierarhicheskoy-klasterizatsii-CHAMELEON.html</ref>.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 103: Строка 107:
 
   integer E[n][n]; // Верхняя треугольная матрица рёбер графа G - изначально инициализирована нулями.
 
   integer E[n][n]; // Верхняя треугольная матрица рёбер графа G - изначально инициализирована нулями.
 
   foreach (integer i in (1,n-1) ) {
 
   foreach (integer i in (1,n-1) ) {
     integer Neighbors[k]; // матрица, используемая хранения ближайших соседей
+
     integer Neighbours[k]; // матрица, используемая хранения ближайших соседей
 
     integer countN = 0;
 
     integer countN = 0;
 
      
 
      
 
     foreach (integer j in (i+1, n) ) {
 
     foreach (integer j in (i+1, n) ) {
       // Заполняем матрицу Neighbors, добавляя новые элементы и увеличивая счётчик countN.
+
       // Заполняем матрицу Neighbours, добавляя новые элементы и увеличивая счётчик countN.
 
       // Когда countN станет равен k, новые элементы будут вставляться на место старых, либо отбрасываться.
 
       // Когда countN станет равен k, новые элементы будут вставляться на место старых, либо отбрасываться.
 
     }
 
     }
Строка 133: Строка 137:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
 +
 +
  [[File:Chameleon_inforgraph.png|811px]]
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
  
Первый этап работы алгоритма можно распределить между <math>n</math> процессами: в этом случае каждому процессу назначается своя точка и происходит поиск <math>k</math> ближайших соседей. Таким образом, его параллельная сложность составляет O(n).
+
Первый этап работы алгоритма можно распределить между <math>n</math> процессами: в этом случае каждому процессу назначается своя точка и происходит поиск <math>k</math> ближайших соседей. Таким образом, его параллельная сложность составляет <math>O(n)</math>.
  
 
На втором этапе количество задействованных процессов может варьироваться в зависимости от входных данных. В худшем случае число итераций можно оценить как <math>O(log(n))</math>.
 
На втором этапе количество задействованных процессов может варьироваться в зависимости от входных данных. В худшем случае число итераций можно оценить как <math>O(log(n))</math>.
  
Третий этап распараллелить не представляется возможным, поскольку выбор очередной пары кластеров для сравнения зависит от результата выполнения предыдущей итерации, поэтому сложность оставляется равной <math>m^2log(m)</math>.
+
На третьем этапе можно распараллелить процесс расчёта метрик сходства между кластерами, однако итоговое слияние всё равно должно выполняться последовательно.
 +
Поскольку процесс сравнения кластеров возможно распараллелить, сложность 3-го этапа составляет <math>mlog(m) + m^2log(m)</math>.
  
Таким образом, суммарная параллельная сложность оказывается равна <math>O(n + log(n) + m^2log(m))</math>
+
Таким образом, суммарная параллельная сложность оказывается равна <math>O(n + log(n) + mlog(m) + m^2log(m))</math>.
  
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
Строка 164: Строка 171:
 
Первый этап алгоритма обладает хорошим ресурсом параллелизма: параллельная сложность его выполнения составляет <math>O(n)</math>, что намного лучше последовательной оценки <math>O(n^2)</math>.
 
Первый этап алгоритма обладает хорошим ресурсом параллелизма: параллельная сложность его выполнения составляет <math>O(n)</math>, что намного лучше последовательной оценки <math>O(n^2)</math>.
  
 +
У второго и третьего этапов алгоритма сложно полностью оценить ресурсы параллелизма. Но оба этапа возможно частично распараллелить.
 +
 +
'''Вычислительную мощность''' для разных этапов алгоритма можно оценить как:
 +
 +
1 этап: <math>O(1)</math>
  
 +
2 этап: <math>O(\frac{nm}{n^2+m^2})</math>
 +
 +
3 этап: <math>O(\frac{m^2log(m)}{m^2+n})</math>
 +
 +
<b>Детерминированность:</b> Важной особенностью данного алгоритма является его недетерминированность. Несмотря на то, что 1-й этап детерминирован, алгоритм в целом является недетерминированным, так как на 2-ом этапе могут быть найдены различные разбиения на подграфы, а это повлияет и на итоговый результат работы алгоритма.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
Строка 175: Строка 192:
  
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
 +
 +
Проводилось исследование масштабируемости экспериментальной версии параллельной реализации алгоритма для малого числа потоков<ref name="tr">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>.
 +
 +
Его результаты отражены на графиках. Из графиков видно, что ускорение и эффективность алгоритма растут с увеличением объема данных.
 +
 +
Однако можно заметить, что с увеличением числа потоков эффективность алгоритма падает.
 +
 +
  [[File:Plot cham.jpg|850px|center]]
 +
 +
[[File:Cham_speedup.png]] [[File:Cham_eff.png]]
  
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
Строка 182: Строка 209:
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
  
Существует несколько последовательных реализаций алгоритма. С одной из них можно ознакомиться по ссылке [http://www.codeforge.com/article/192925].
+
Существует несколько последовательных реализаций алгоритма. С одной из них можно ознакомиться по ссылке <ref name="tra">http://www.codeforge.com/article/192925</ref>.
  
Возможна реализация алгоритма CHAMELEON с использованием графовых библиотек, как, например METIS [http://glaros.dtc.umn.edu/gkhome/metis/metis/overview] , hMETIS [http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview] и RANN [https://cran.r-project.org/web/packages/RANN/index.html].
+
Возможна реализация алгоритма CHAMELEON с использованием графовых библиотек, как, например METIS <ref name="tru">http://glaros.dtc.umn.edu/gkhome/metis/metis/overview</ref> , hMETIS <ref name="tri">http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview</ref> и RANN <ref name="tro">https://cran.r-project.org/web/packages/RANN/index.html</ref>.
  
Параллельных реализаций алгоритма CHAMELEON найдено не было. Однако существует исследование, связанное с реализацией CHAMELEON посредством технологии OpenMP, с которым можно ознакомиться здесь [http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf].
+
Параллельных реализаций алгоритма CHAMELEON найдено не было. Однако существует исследование, связанное с реализацией CHAMELEON посредством технологии OpenMP, с которым можно ознакомиться здесь <ref name="tr">http://research.ijcaonline.org/volume79/number8/pxc3891600.pdf</ref>.
  
 
== Литература ==
 
== Литература ==
  
Данный алгоритм выполняется в два этапа.
+
<references \>
 
 
На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов. Рассмотрим эти этапы подробнее.
 
 
 
На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.
 
[[Файл:Графы k ближайших соседей.jpg|2000px|thumb|left|На рисунке изображены: 1) объекты в пространстве, 2) граф по принципу 1-го ближайшего соседа, 3) граф по принципу 2-го ближайшего соседа, 4)граф по принципу 3-х ближайших соседей]]
 
 
 
Такое представление имеет целый ряд преимуществ.
 
 
 
Во-первых, можно сразу убрать ребра в графе с достаточно малым весом (значением сходства).
 
 
 
Во-вторых, возможно динамически определить для различных участков графа количество k ближайших соседей для вершин, на основе плотности данных отдельно взятого участка, которую, в свою очередь, можно определить на основе весов ребер.
 
 
 
В-третьих, операции на графах (например, разделение графа), имеющих такое представление, выполняются гораздо быстрее, чем на полных графах.
 
 
 
Обычно, k берется в пределах от 5 до 20 в зависимости от количества анализируемых объектов, и, как свидетельствуют авторы, выбор k почти не оказывает влияния на результаты кластеризации.
 
 
 
Далее, алгоритм разделяет полученный граф на множество сравнительно малых подграфов. Разделение происходит последовательно. На каждом шаге выбирается под-граф, содержащий наибольшее число вершин. Этот граф разделяется на два подграфа, так, что разделитель ребер графа минимален и каждый из получаемых подграфов содержит не менее 25 % вершин исходного графа. Процесс разделения останавливается, когда наибольший под-граф содержит меньше некоторого заданного числа вершин. Обычно величина этого параметра задается равной значению от 1 до 5 % от числа объектов. Полученное множество связных графов считается множеством начальных кластеров, на котором требуется провести последовательное иерархическое объединение.
 
 
 
На втором этапе, алгоритм последовательно объединяет кластеры, используя значение их относительной взаимной связности и относительного взаимного сходства. Только если оба эти значения достаточно высоки у двух кластеров, они объединяются.
 
 
 
Относительная взаимная связность пары кластеров определяется абсолютной взаимной связностью кластеров, нормализованной с учетом внутренней связности (п. 0) каждого кластера (подграфа). Нормализация используется для того, чтобы исключить тенденцию к преимущественному объединению крупных кластеров, у которых, определенно, значение взаимной связности будет больше, вследствие их размера.
 
 
 
Абсолютная взаимная связность между парой кластеров Ci и Сj определяется как сумма весов ребер, соединяющих вершины, принадлежащие Ci с вершинами из Сj. Эти ребра, фактически, входят в разделитель ребер графа, состоящего из кластеров Ci и Сj, и разбивающим его на подграфы Ci и Сj. Обозначается эта величина как  . Внутреннюю связность  кластера Ci можно вычислить как сумму ребер, входящих в разделитель ребер, разбивающий Ci на два совершенно равных подграфа.
 
 
 
Относительная взаимная связность  пары кластеров Ci и Сj определяется формулой:
 
 
 
 
 
 
 
Учитывая значения относительной взаимной связности, можно добиться получения кластеров разного размера, формы и плотности, то есть общего внутреннего сходства.
 
 
 
Относительное взаимное сходство пары кластеров определяется как абсолютное сходство между этой парой кластеров, нормализованное с учетом их внутреннего сходства.
 
 
 
Абсолютное взаимное сходство между парой кластеров Ci и Сj подсчитывается как среднее сходство между соединенными вершинами, принадлежащими Ci и Сj соответственно. Эти соединения обусловлены предыдущим (на первом этапе) разбиением общего графа, полученного на матрице сходства.
 
 
 
Итак, относительное взаимное сходство  между парой кластеров Ci и Сj равно:
 
 
 
 
 
 
 
где  и  – средние веса ребер (значения сходства), принадлежащих разделителю ребер кластеров Ci и Сj соответственно, и  – средний вес ребер, соединяющих вершины Ci с вершинами Сj, причем ребра принадлежат разделителю ребер  , определенному ранее. Можно также подсчитать внутреннее сходство как среднее значение весов всех связей в кластере, однако использования разделителя ребер по мнению авторов метода предпочтительнее. Этот факт они связывают с тем, что связи между объектами, помещенными в один кластер на ранних этапах объединения, сильнее, чем на поздних.
 
 
 
Далее, алгоритм применяет агломеративную иерархическую кластеризацию с использованием вышеозначенных показателей. Причем существует две стратегии их учета. Первая подразумевает наличие некоторых пороговых значений. T­RI и T­RC. В соответствии с этой стратегией, алгоритм для каждого кластера Ci проверяет, отвечают ли смежные (наиболее близкие) ему кластеры условиям:
 
 
 
 
 
 
 
Если более одного смежного кластера отвечает этим условиям, то алгоритм выбирает для объединения наиболее связный кластер (граф), то есть такой кластер Сj, с которым у кластера Ci получается наибольшая абсолютная взаимная связность. По завершению прохода по всем кластерам, созданные таким образом пары объединяются. Параметры T­RI и T­RC могут использоваться для изменения характеристик получаемых кластеров.
 
 
 
Таким образом, основное отличие данного подхода от классических агломеративных иерархических методов в том, что, во-первых, на каждом шаге могут быть объединены несколько кластеров, а, во-вторых, на каком-то этапе ни одна пара кластеров не будет удовлетворять вышеуказанным условиям и такое разбиение будет считаться оптимальным, то есть в конце может не получиться один всеохватывающий кластер. Если данное разбиение не удовлетворяет выбранным критериям, то пороговые значения можно уменьшить.
 
 
 
Вторая стратегия заключается в использовании специальной функции, объединяющей понятия относительной взаимной связности и относительного взаимного сходства. На каждом шаге выбираются те кластеры для объединения, которые максимизируют эту функцию:
 
 
 
 
 
 
 
где a выбирается пользователем. Если a > 1, то алгоритм придает большее значение относительному взаимному сходству, а если a < 1, то большее значение имеет относительная взаимная связность. Разумеется, данный подход позволяет получить полную дендрограмму кластерного анализа.
 
 
 
Общая временная сложность этого алгоритма выражается как  , где n – количество анализируемых документов, m­ – количество получившихся после первого этапа малых кластеров.
 

Текущая версия на 17:31, 29 ноября 2016

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

Данное задание было проверено и зачтено.
Проверено Kronberg и Algoman.



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


Статью подготовили: Артём Таран Иванович (разделы 1.1 - 1.10, 2.7), Шимчик Никита Владимирович (разделы 1.1 - 1.10, 2.7).

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

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

Кластеризация — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры) с минимизацией межкластерного сходства и максимизацией внутрикластерного сходства.

Графо-ориентированный алгоритм кластеризации CHAMELEON[1] - алгоритм, который измеряет сходство двух кластеров на основе динамической модели. В процессе кластеризации два кластера объединяются, только если показатели взаимосвязанности и близости между двумя кластерами являются высокими по отношению к показателям внутренней взаимосвязанности кластеров и близости элементов внутри этих кластеров. Процесс слияния с использованием динамической модели, использующийся в данном алгоритме облегчает открытие природных и однородных кластеров. Методология динамического моделирования кластеров, использующаяся в CHAMELEON, применима ко всем типам данных, для которых может быть построена матрица подобия.

Следует отметить, что конечное число кластеров не задаётся явным образом и зависит как от выбора параметров алгоритма, так и от внутренней структуры входных данных.

Алгоритм кластеризации CHAMELEON включает в себя три этапа:

1) Построение графа, путём добавления рёбер по принципу k ближайших соседей.

2) Выделение множества сравнительно малых связных подграфов.

3) Формирование набора кластеров, на основе множества подграфов, полученных на предыдущем этапе.

Графы k ближайших соседей: 1) объекты в пространстве, 2) граф по принципу 1-го ближайшего соседа, 3) граф по принципу 2-го ближайшего соседа, 4) граф по принципу 3-х ближайших соседей[1]

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

1.2.1 Данные

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

1.2.2 Определения

  • Абсолютная взаимная связность между парой кластеров [math]C_{i}[/math] и [math]C_{j}[/math] определяется как сумма весов ребер, соединяющих вершины, принадлежащие [math]C_{i}[/math] с вершинами из [math]C_{j}[/math]. Эти ребра, фактически, входят в разделитель ребер графа, состоящего из кластеров [math]C_{i}[/math] и [math]C_{j}[/math], и разбивающим его на подграфы [math]C_{i}[/math] и [math]C_{j}[/math]. Обозначается эта величина как

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

  • Относительная взаимная [math]RI_{(C_{i},C_{j})}[/math] связность пары кластеров [math]C_{i}[/math] и [math]C_{j}[/math] определяется формулой:

[math]RI_{(C_{i},C_{j})} = \frac{2*|EC_{(C_{i},C_{j})}|}{|EC_{C_{i}}|+|EC_{C_{j}}|}[/math]

Учитывая значения относительной взаимной связности, можно добиться получения кластеров разного размера, формы и плотности, то есть общего внутреннего сходства.

  • Абсолютное взаимное сходство между парой кластеров [math]C_{i}[/math] и [math]C_{j}[/math] подсчитывается как среднее сходство между соединенными вершинами, принадлежащими [math]C_{i}[/math] и [math]C_{j}[/math] соответственно. Эти соединения обусловлены предыдущим разбиением общего графа, полученного на матрице сходства.
  • Относительное взаимное сходство [math]RC_{(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]S_{EC_{(C_{i})}}[/math] и [math]S_{EC_{(C_{i})}}[/math] - средние веса ребер (значения сходства), принадлежащих разделителю ребер кластеров [math]C_{i}[/math] и [math]C_{j}[/math] соответственно, и [math]S_{EC_{(C_{i},C_{j})}}[/math] - средний вес ребер, соединяющих вершины [math]C_{i}[/math] с вершинами [math]C_{j}[/math], причем ребра принадлежат разделителю ребер [math]EC_{(C_{i})}[/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], то большее значение имеет относительная взаимная связность. Разумеется, данный подход позволяет получить полную дендрограмму кластерного анализа[2].

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

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

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

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

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

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

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

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

  • Первый этап (псевдокод):
 integer n; // Количество точек.
 integer k; // Параметр k
 integer A[n][n]; // Верхняя треугольная матрица расстояний между точками.
 
 integer E[n][n]; // Верхняя треугольная матрица рёбер графа G - изначально инициализирована нулями.
 foreach (integer i in (1,n-1) ) {
   integer Neighbours[k]; // матрица, используемая хранения ближайших соседей
   integer countN = 0;
   
   foreach (integer j in (i+1, n) ) {
     // Заполняем матрицу Neighbours, добавляя новые элементы и увеличивая счётчик countN.
     // Когда countN станет равен k, новые элементы будут вставляться на место старых, либо отбрасываться.
   }
 
   foreach (integer j in (0, countN) ) {
     E[min(i,j), max(i,j)] = 1;
   }
 }
 return E;
  • Второй этап:
 Диаграмма шаг 2.png
  • Третий этап:
 Chameleon stage 3.png

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

1) Построение графа на основе метода k ближайших соседей в худшем случае требует [math]O(n^2)[/math] операций;

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

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

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

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

 Chameleon inforgraph.png

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

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

На втором этапе количество задействованных процессов может варьироваться в зависимости от входных данных. В худшем случае число итераций можно оценить как [math]O(log(n))[/math].

На третьем этапе можно распараллелить процесс расчёта метрик сходства между кластерами, однако итоговое слияние всё равно должно выполняться последовательно. Поскольку процесс сравнения кластеров возможно распараллелить, сложность 3-го этапа составляет [math]mlog(m) + m^2log(m)[/math].

Таким образом, суммарная параллельная сложность оказывается равна [math]O(n + log(n) + mlog(m) + m^2log(m))[/math].

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

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

1) Треугольная матрица [math]A[/math] размера [math]n\times n[/math] (где n — количество объектов), в которой элементу [math]a_{ij}[/math] соответствует расстояние между i-м и j-м объектами.

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

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

  • Объём входных данных: [math]\frac{n (n - 1)}{2}[/math]
  • Выходные данные: n-мерный вектор [math]v[/math], в котором элементу [math]v_{i}[/math] соответствует номер кластера, присвоенный i-му объекту
  • Объём выходных данных: [math]n[/math]

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

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

У второго и третьего этапов алгоритма сложно полностью оценить ресурсы параллелизма. Но оба этапа возможно частично распараллелить.

Вычислительную мощность для разных этапов алгоритма можно оценить как:

1 этап: [math]O(1)[/math]

2 этап: [math]O(\frac{nm}{n^2+m^2})[/math]

3 этап: [math]O(\frac{m^2log(m)}{m^2+n})[/math]

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

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

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

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

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

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

Проводилось исследование масштабируемости экспериментальной версии параллельной реализации алгоритма для малого числа потоков[3].

Его результаты отражены на графиках. Из графиков видно, что ускорение и эффективность алгоритма растут с увеличением объема данных.

Однако можно заметить, что с увеличением числа потоков эффективность алгоритма падает.

Plot cham.jpg
Cham speedup.png Cham eff.png

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

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

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

Существует несколько последовательных реализаций алгоритма. С одной из них можно ознакомиться по ссылке [4].

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

Параллельных реализаций алгоритма CHAMELEON найдено не было. Однако существует исследование, связанное с реализацией CHAMELEON посредством технологии OpenMP, с которым можно ознакомиться здесь [3].

3 Литература

<references \>