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

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

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

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

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

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

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

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

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

[math]TODO[/math] (1)

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

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

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

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

[math]TODO[/math]

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

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

Вычислительное ядро алгоритма состоит из двух частей: подсчет количества связей между точками и итеративное объединение кластеров.

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

Итеративная часть алгоритма может быть реализована с помощью структуры данных куча. На каждой итерации с каждым кластером [math]i[/math] связана своя куча [math]q[i][/math], содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также поддерживается глобальная куча [math]Q[/math], содержащая все кластеры [math]j[/math], упорядоченные по мере убывания функции качества [math]g(j, max(q[j]))[/math], где [math]max(q[j])[/math] - это вершина кучи [math]q[j][/math]. Тогда на каждой итерации объединяются кластер [math]j[/math] с вершины глобальной кучи и кластер [math]q[j][/math]. После объединения необходимо обновить все кучи, содержащие объединенные кластеры, и создать кучу для нового кластера. Итеративный процесс продолжается до тех пор, пока в глобальной куче [math]Q[/math] не останется требуемое число кластеров.

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

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