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

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

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

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

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

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

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

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

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

Формулы метода:

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

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

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

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

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

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

Первый этап работы CHAMELEON – разделение графа для получения набора малых кластеров ( в зависимости от параметров программы — от 1 до 5 % от вершин исходного графа ).

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

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

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

O – набор из n документов. Документы имеют одинаковую структуру, в качестве примера можно рассмотреть их как векторы длины p. k – количество ближайших соседей, по которым строится первоначальный граф. Также выбирается стратегия объединения кластеров и вещественный параметр A при использовании стратегии с максимизацией специальной функции.

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

Определяется иерархия кластеров, содержащих исходные документы. Эта информация может храниться в виде бинарного дерева или набора бинарных деревьев, суммарно содержащих от m до 2 * m – 1 вершин. Для каждого из документов определяется, к каким кластерам он принадлежит. Эта информация может храниться, например, в виде матрицы размера m * q, где для каждого документа и каждого уровня бинарного дерева указано, к какому кластеру принадлежит документ. Здесь q может меняться от 1 до log2m.

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

Соотношение последовательной и параллельной сложности:

Вычислительная мощность:

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