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

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

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

Алгоритм CHAMELEON - алгоритм динамической иерархической кластеризации графа.

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

Алгоритм состоит из 3-х основных этапов:

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

2-й этап заключается в разбиении построенного графа на небольшие кластеры (связные подграфы)

3-й этап состоит в формировании итогового множества кластеров

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

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

Множество из n объектов и заданные расстояния между объектами. Эта информация позволяет построить матрицу смежности, в которой будут указаны расстояния между соответствующими объектами по некой метрике. Матрица смежности симметрична, на главной диагонали стоят 0, поэтому достаточно хранить [math]\frac{n(n-1)}{2}[/math] элементов. Кроме того задаются параметры, влияющие на работу алгоритма - число k, по которому на первом этапе строится граф по принципу k ближайших соседей, и два параметра [math]{T_{ri}}[/math] и [math]{T_{rc}}[/math], используемые на третьем этапе для того, что определить, что не нужно далее продолжать кластеризацию.

Первый этап

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

Второй этап

Состоит в итеративном разбиении графа на множество подграфов. Изначально (на первой итерации) разбиение состоит из единственного подграфа. Пусть [math]T[/math] - множество подграфов на текущей итерации. Каждая итерация выполняется следующим образом - выбирается максимальный подграф из имеющихся в разбиении по числу вершин (то есть такой подграф [math]G_1(V_1,E_1)\in{T}: \forall {G_2(V_2,E_2)\in{T}: G_2\neq G_1} =\gt |(V_1)|\gt |(V_2)|[/math] ). Выбранный подграф разбивается на 2 подграфа следующим образом - сначала выбираются все разбиения [math]G_2(V_2,E_2)[/math] и [math]G_3(V_3,E_3)[/math], такие, что [math]\min(|V_2|,|V_3|)\geq\frac{|V_1|}{4}[/math]. Далее среди всех таких разбиений выбирается такое, для которого величина [math]\sum{|E_1^*|},E_1^* [/math]- некое ребро, ведущее из вершины, попавшей в [math]G_2[/math] в вершину, попавшую в [math]G_3[/math]. В определенный момент, когда размер наибольшего кластера [math]|V_b|\leq{q*|V|}[/math], где [math]|V|[/math] - количество вершин в изначальном графе, а [math]q[/math] - предварительно заданный параметр, процесс дальнейшего разибения прекращается и алгоритм переходи на 3-й этап

Третий этап алгоритма: 

Введем несколько определений:

Абсолютной взаимной связностью пары кластеров называется величина [math]EC_{({C_i},{C_j})}[/math], вычисляется как сумма весов ребер, соединяющих вершина 1-го кластера [math]C_i[/math] с вершинами второго кластера [math]C_j[/math]. Внутренняя связность кластера [math]E_{C_i}[/math]вычисляется как сумма весов ребер, входящих в разделитель, разбивающих [math]C_i[/math] на 2 равных подграфа.

Относительная взаимная связность пары кластеров [math]RI_{(C_i,C_j)}[/math] вычисляется по формуле [math]RI_{(C_i,C_j)}=\frac{2*|EC_{(C_i,C_j)}|}{|EC_{C_i}|+|EC_{C_j}|}[/math]

Абсолютное взаимное сходство пары кластеров [math]S_{E_{(C_i,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]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_j|}{|C_i|+|C_j|}*S_{EC_{(C_j)}}}}[/math]

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

Есть два различных подхода анализа сходства.

Первый - для каждой пары кластеров проверяется истинность следующих высказываний

[math]RI(Ci,Cj)\geq{T_{RI}} [/math] и [math]RC_{(C_{i},C_{j})}\geq{T_{RC}}[/math]

В случае, если для некоторого [math]C_i[/math] существует несколько кластеров [math]C_j[/math], удовлетворяющих этим условиям, выбирается такой [math]C_j[/math], что

значение [math]EC_{(C_i,C_j)}[/math] максимально.

Процесс останавливается, когда нет кластеров, удовлетворяющих указанным условиям (либо когда остался только 1 кластер)

Второй подход - выбирается такая пара кластеров, что [math]RI_{(C_i,C_j)}*RC^\alpha_{(C_i,C_j)}[/math] максимально, где [math]\alpha[/math] - заданный заранее параметр.

Процесс останавливается, когда нет кластеров, удовлетворяющих указанным условиям (либо когда остался только 1 кластер)

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

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

На втором этапе вычислительное ядро состоит из повторяющегося нахождения разбиения графа на два подграфа, удовлетворяющего ранее описанным условиям

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