Участник:LKruglov/Алгоритм устойчивой кластеризации с использованием связей

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

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

Алгоритм устойчивой кластеризации с использованием связей (robust clustering using links, ROCK)построен на основе понятия связей между кластеризуемыми точками и их соседства. Две точки считаются соседями, если являются достаточно близким (схожими): $sim({p_i}, {p_j}) \gt = \theta$, где $\theta$ - заданное пороговое значение в интервале от 0 до 1.

Связь $link({p_i}, {p_j})$ между двумя точками определяется как число общих соседей между точками ${p_i}$ и ${p_j}$. Таким образом, чем большее значение функции связи для двух точек, тем более вероятно они принадлежат одному кластеру.

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

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

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

Итак, задача кластеризации сводиться к такому разбиению точек на кластеры, которое максимизирует сумму связей точек принадлежащих одному кластеру, и минимизирует эту функцию для точек из разных кластеров. Отсюда следует следующая целевая функция для разбияния на $k$ кластеров:

$TODO$ (1)

Данная функция отличается от простой суммы связей для каждого кластера, поскольку такая функция бы не давала уверенности в том, что точки, имеющие мало связей между собой распределялись бы по разным кластерам. Поэтому действительную сумму связей в кластере следует разделить на ожидаемую сумму связей. Функция $f(\theta)$ задается пользователем и должна обладать следующим свойством: каждая точка, принадлежащая кластеру Ci, имеет приблизительно $TODO$ соседей в этом кластере.

Связь между двумя кластерами определяется как

$link({C_i}, {C_j}) = \sum^{}_{{p_q}\in{C_i}, {p_r}\in{C_j}}{link[{C_i}, {C_j}]}$

Тогда для выбора кластеров для объединения используется следующая целевая функция качества:

$TODO$

Аналогично целевой функции (1) значение связи между двумя кластерами делится на ожидаемое число связей между кластерами.