Участник:Ruslanlazovskiy/CHAMELEON

Авторы статьи: Лазовский Р. А. ( разделы 1.1 - 1.4 , 1.7 , 1.8 ), Мустафаев Э. Э. ( разделы 1.5 , 1.6 , 1.9 , 1.10 , 2.2 )

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

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

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

Алгоритм CHAMELEON работает в 3 этапа. На первом этапе исходное множество объектов организуется в граф по принципу k ближайших соседей. На втором этапе этого граф разбивается на достаточно малые подграфы-кластеры. На третьем этапе происходит агломеративная иерархическая кластеризация полученных подграфов в соответствии с одной из выбранных метрик ( возможные метрики будут подробно описаны далее ).

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

Исходные данные: Первоначально исходными данными алгоритма являются [math]\displaystyle{ n }[/math] векторов длины [math]\displaystyle{ p }[/math], каждый из которых соответствует одному объекту. На основании значений элементов этих векторов строится матрица смежности размера [math]\displaystyle{ n * n }[/math] ( возможно сокращение требуемого объема памяти до [math]\displaystyle{ (n*(n - 1))/ 2 }[/math] в соответствии с выбранной метрикой.

Первый этап алгоритма: На первом этапе на основании матрицы смежности строится граф [math]\displaystyle{ G = (V, E) }[/math] [math]\displaystyle{ k }[/math] ближайших соседей. Указанный граф не обязательно является связным.

Второй этап алгоритма: Граф [math]\displaystyle{ G = (V, E) }[/math] итеративно разбивается на множество подграфов [math]\displaystyle{ G_{i} = (V_{i}, E_{i}), i = 1 .. m }[/math], где [math]\displaystyle{ \cup V_{i} = V, i = 1 .. m }[/math]. На каждой итерации выбирается [math]\displaystyle{ G_{b} }[/math] с числом вершин, наибольшим среди всех подграфов, имеющихся на данной итерации. Этот граф разбивается на 2 подграфа [math]\displaystyle{ G_{bi} }[/math] и [math]\displaystyle{ G_{bj} }[/math] таких, что 1) [math]\displaystyle{ min(V_{bi},V_{bj}) \gt = 0.25 * V_{b} }[/math] ( имеется ввиду количество вершин ) и 2) [math]\displaystyle{ \sum{E_{kl}}, E_{kl} = (v_{k}, v_{l}), v_{k} \in V_{bi} , v_{l} \in V_{bj} }[/math] минимальна среди всех разбиений, удовлетворяющих 1). Итеративный процесс прекращается, когда [math]\displaystyle{ \sum{v_{b}} \lt = q * \sum{v} , v_{b} \in V_{b} , e \in E }[/math] ( имеется ввиду количество вершин ). Здесь [math]\displaystyle{ q }[/math] - задаваемый параметр, на практике он варьируется от [math]\displaystyle{ 0.01 }[/math] до [math]\displaystyle{ 0.05 }[/math]. Полученные подграфы называются малыми кластерами.

Третий этап алгоритма: Множество кластеров [math]\displaystyle{ G_{i} = (V_{i}, E_{i}), i = 1 .. m }[/math] итеративно преобразуется в множество кластеров [math]\displaystyle{ G_{j} = (V_{j}, E_{j}), j = 1 .. l }[/math], [math]\displaystyle{ l \lt = m }[/math]. Для этого вводятся следующие понятия:

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

На основании этих показателей осуществляется агломеративная иерерхическая кластеризация. Существует две стратегии их анализа. В первом случае для каждой пары кластеров [math]\displaystyle{ C{i}, C{j} }[/math] проверяется истинность выражений [math]\displaystyle{ RI_{(C_{i},C_{j})} \gt = T_{RI} }[/math] и [math]\displaystyle{ RC_{(C_{i},C_{j})} \gt = T_{RC} }[/math], где [math]\displaystyle{ T_{RI}, T_{RI} }[/math] - заранее заданные пороговые значения. Если для некоторого [math]\displaystyle{ C_{i} }[/math] таких [math]\displaystyle{ C_{j} }[/math] несколько, то конкретная пара определяется по максимуму значения [math]\displaystyle{ EC_{(C_{i},C_{j})} }[/math]. Во втором случае выбираются пары кластеров, максимизирующие функцию вида [math]\displaystyle{ RI_{(C_{i},C_{j})}*RC_{(C_{i},C_{j})}^\alpha }[/math]. Здесь [math]\displaystyle{ \alpha }[/math] - заданный пользователем параметр. В обоих случаях процесс останавливается либо когда на очередной итерации не находится подходящих пар кластеров, либо когда остаётся только один кластер.

Вычисляемые данные: В процессе агломеративной кластеризации для всех объектов, т.е. всех вершин всех кластеров указывается индекс [math]\displaystyle{ j }[/math] кластера, к которому они принадлежат. После завершения алгоритма возможно перенумеровать кластеры. В любом случае на выходе будет иметься [math]\displaystyle{ n }[/math] значений, так как число объектов в процессе работы алгоритма не изменялось.

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ O }[/math] - набор из [math]\displaystyle{ n }[/math] векторов длины [math]\displaystyle{ p }[/math].
[math]\displaystyle{ k }[/math] - число, определяющиее количество ближайших соседей, по которым строится первоначальный граф.

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

[math]\displaystyle{ B }[/math] - вектор длины [math]\displaystyle{ n }[/math], значение [math]\displaystyle{ i }[/math]-го элемента указывает на принадлежность соответствующего вектора одному из кластеров.

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

Соотношение последовательной и параллельной сложности: Различные этапы алгоритма строго последовательны относительно друг друга. На первом этапе отношение последовательной сложности алгоритма к параллельной есть [math]\displaystyle{ n }[/math]. На втором и третьем этапах различные итерации последовательны относительно друг друга. Однако внутри итераций допускается некоторый параллелизм. Например, для итераций третьего этапа в наилучшем случае отношение сложности последовательной реализации к параллельной есть [math]\displaystyle{ p/2 }[/math], где [math]\displaystyle{ p }[/math] - число кластеров на конкретной итерации.

Вычислительная мощность: графовые алгоритмы, вообще говоря, обладают низкой вычислительной мощностью. В случае CHAMELEON вычислительная мощность первого этапа равна [math]\displaystyle{ O(1) }[/math]. Для второго и третьего этапов оценка вычислительной мощности по сложениям и умножениям затруднительна, однако в терминах макроопераций можно дать грубую оценку. Вычислительная мощность каждой итерации второго этапа - [math]\displaystyle{ 1 / \sum C_n^k }[/math], где [math]\displaystyle{ n }[/math] - число вершин в выбранном подграфе, а [math]\displaystyle{ k }[/math] варьируется от [math]\displaystyle{ 0.25 * n }[/math] до [math]\displaystyle{ 0.5 * n }[/math]. Вычислительная мощность каждой итерации третьего этапа - [math]\displaystyle{ O(1) }[/math]

Детерминированность: Важной особенностью описываемого алгоритма является его недетерминированность. Условия завершения как 2-го, так и 3-го этапа позволяют обозначить CHAMELEON как итерационный алгоритм с выходом по точности. При этом детерминированность 2-го этапа алгоритма можно обеспечить указанием вырожденных условий кластеризации ( такая кластеризация, очевидно, не будет иметь практического смысла ), в то время как 1-ый этап является недетерминированным всегда.