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

Вступление

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

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

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

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

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

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

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

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

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

Функцией связи между кластерами называется [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ n_i }[/math] - число объектов в кластере [math]\displaystyle{ C_i }[/math].

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

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

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