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

Вступление

1 ЧАСТЬ. Свойства и структура алгоритмов

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

Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) решает задачу кластеризации объектов по заранее заданному количеству [math]k[/math] кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта [math]sim(p_i, p_j)[/math]. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

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

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

Пусть дано множество объектов [math]P = \{p_1, \ldots , p_n\}[/math], натуральное число [math]k[/math], функция схожести [math]sim(p_i, p_j)[/math], пороговое значение [math]\theta : 0\leq\theta\leq 1[/math] и функция функция [math] f( \theta ) [/math].

Результатом работы алгоритма является [math]k[/math] непересекающихся кластеров, делящих множество [math]P[/math].

Две точки называются соседними, если [math]sim(p_i, p_j) \geq \theta[/math]

Количеством общих соседей [math]link(p_i, p_j)[/math] называется число точек, являющимися соседними для точек [math]p_i, p_j[/math].

Функцией связи между кластерами называется [math]link[C_i, C_j] = \sum_{\begin{smallmatrix}p_q\in C_i,\; p_r\in C_j\end{smallmatrix}}^{ } link(p_{q},p_r)[/math].

Функцией качества является функция

[math] g(C_i, C_j) = \frac{link[C_i,C_j]}{(n_i + n_j)^{1 + 2f(\theta )} - n_i^{1+2f(\theta )} - n_j^{1+2f(\theta )}}[/math], где [math]n_i[/math] - число объектов в кластере [math]C_i[/math].

Алгоритм начинает работу, разбив всё пространство на [math]n[/math] кластеров.

Затем на каждом шаге он вычисляет значение [math]g(C_i, C_j)[/math] для каждой пары кластеров и объединяет эти кластеры в один.

Алгоритм ведёт свою работу до тех пор, пока не получит [math]k[/math] кластеров.

В качестве функции [math]f( \theta )[/math] обычно используется функция [math]f(\theta ) = \frac{\theta - 1}{\theta + 1}[/math] , [math]n_i^{1+2f(\theta )}[/math] - ожидаемое число связей между парами объектов кластера [math]C_i[/math].

Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:

[math]sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}[/math], где [math]|p_i|[/math] - количество атрибутов в [math]p_i[/math]. Данная функция удобна в случае, если все признаки категориальны

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