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

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

Статью подготовили: Артём Таран Иванович, Шимчик Никита Владимирович.

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

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

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

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

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

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

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

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

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

1.2.1 Данные

• Исходные данные: множество из $n$ точек $V = \{v_{i}\}$ в метрическом пространстве, которое может быть задано в виде треугольной матрицы расстояний $A$ размера $n\times n$.

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

• Промежуточный результат после второго этапа: разбиение множества $V$ на набор $C = \{C_{i}\}$ попарно непересекающихся связных подмножеств, из которого образуется взвешенный граф $G_{2} = (C, E_{2})$.

• Промежуточный результат после третьего этапа: итоговое разбиение множества вершин графа $G_{2}$ на набор кластеров $K = \{K_{i}\}$.

• Вычисляемые данные: n-мерный вектор $v$ (элементы $v_{i}$), показывающий отображение исходного множества точек на набор кластеров K.

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

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

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

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

$RI_{(C_{i},C_{j})} = \frac{2*|EC_{(C_{i},C_{j})}|}{|EC_{C_{i}}|+|EC_{C_{j}}|}$

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

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

• Относительное взаимное сходство $RC_{(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})}}}$,

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

Далее, алгоритм применяет агломеративную иерархическую кластеризацию с использованием вышеозначенных показателей. Причем существует две стратегии их учета. Первая подразумевает наличие некоторых пороговых значений $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$, то большее значение имеет относительная взаимная связность. Разумеется, данный подход позволяет получить полную дендрограмму кластерного анализа.

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

• Первый этап (псевдокод):

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

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

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

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

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

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

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

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

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

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

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

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

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

• Объём входных данных: $n$

• Выходные данные: n-мерный вектор $v$, в котором элементу $v_{i}$ соответствует номер кластера, присвоенный i-му объекту

• Объём выходных данных: $\frac{n (n - 1)}{2}$

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

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

3 Литература

Данный алгоритм выполняется в два этапа.

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

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

На рисунке изображены: 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­ – количество получившихся после первого этапа малых кластеров.