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

Основные авторы описания: Ю.А. Антохина, С.А. Шатков

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

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

Пусть дан набор точек и заданы правила определения расстояния между ними. Задача кластеризации сгруппировать эти точки в определенное число кластеров. Члены одного кластера похожи, а члены разных классов различны.

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

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

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

Описание шагов

Шаг 1. Если все данные использовать сразу как входные для CURE, то эффективность алгоритма будет низкая, а время выполнения большим. Поэтому на первом шаге мы случайным образом выбираем часть точек которые помещаются в память, затем группируем наиболее похожие с помощью иерархического метода. Дальше работаем с кластерами.

Шаг 2. Для каждого кластера выбираем [math]\displaystyle{ c }[/math] точек представителей, максимально удаленных друг от друга. Чисто [math]\displaystyle{ c }[/math] остается постоянным.

Шаг 3. Объединяем кластеры с наиболее похожими наборами точек представителей. Если не достигнуто нужное число кластеров, то перейти на шаг 2. Чтобы при объединении кластеров не выбирать каждый раз c точек представителей из всех точек, мы выбираем их только из [math]\displaystyle{ 2c }[/math] точек объединенных кластеров.

Выбранные точки сдвигаются на следующем шаге на [math]\displaystyle{ \alpha }[/math] к центроиду кластера. Алгоритм становится основанным на методе поиска центроида при [math]\displaystyle{ \alpha = 1 }[/math], и основанным на всех точках кластера при [math]\displaystyle{ \alpha = 0 }[/math].

Пример работы алгоритма для разных параметров [math]\displaystyle{ \alpha }[/math].

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

Пусть дана матрица [math]\displaystyle{ x \in R^{m\times n} }[/math], количество кластеров [math]\displaystyle{ k }[/math], число точек представителей [math]\displaystyle{ c }[/math], параметр [math]\displaystyle{ \alpha }[/math], параметр [math]\displaystyle{ \gamma }[/math]. Каждая строка матрицы представляет собой точку в [math]\displaystyle{ n }[/math] - мерном пространстве.

m число точек для кластеризации, n размерность.

Расстояние [math]\displaystyle{ \rho(p,k) }[/math] между точками [math]\displaystyle{ p = (p_{1},\dots,p_{n}) }[/math] и [math]\displaystyle{ k = (k_{1},\dots,k_{n}) }[/math] будем вычислять по формуле:

[math]\displaystyle{ \rho(p,k) = \sqrt{\sum_{i=1}^n (p_{i} - k_{i})^2} }[/math]

Шаг "Инициализация"

Выбираются [math]\displaystyle{ \lceil \gamma m\rceil }[/math] строк матрицы случайным образом. Например, можно использовать Алгоритм R.

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

Шаг "Кластеризация"

В самом начале шага считаем каждую выбранную точку одноточечным кластером с центроидой в этой же точке.

Далее выполняем следующие шаги 1-2, пока количество кластеров не станет равно [math]\displaystyle{ k }[/math]:

Шаг 1:

Для каждого [math]\displaystyle{ i }[/math]-го кластера вычисляется центроида [math]\displaystyle{ \mu_{i} }[/math] по формуле:

[math]\displaystyle{ \mu_{i} = \frac{1}{s_{i}}\sum_{j\in S_{i}} x^{j} }[/math], где [math]\displaystyle{ S_{i} }[/math] - номера строк матрицы [math]\displaystyle{ x }[/math], входящие в [math]\displaystyle{ i }[/math]-й кластер; [math]\displaystyle{ s_{i} }[/math] - количество элементов в множестве [math]\displaystyle{ S_{i} }[/math]; [math]\displaystyle{ x^{j} }[/math] - [math]\displaystyle{ j }[/math]-я строка матрицы [math]\displaystyle{ x }[/math].

Шаг 2:

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

Шаг "Назначение представителей"

На данном шаге для каждого кластера определяются [math]\displaystyle{ c }[/math] точек-представителей. Для наилучшего отображения формы множества предполагается использование точек, максимально удалённых друг от друга.

Для этого используем следующий алгоритм:

Выберем произвольную точку кластера и назначим её представителем.

ПОКА количество представителей меньше [math]\displaystyle{ c }[/math] ВЫПОЛНЯТЬ

 Назначаем представителем точку, наименьшее расстояние от которой до уже выбранных точек-представителей является максимальным среди всех оставшихся точек.

Шаг "Сдвиг представителей к центроиде"

Для каждого представителя выполняется сдвиг к центроиде соответствующего кластера в [math]\displaystyle{ \alpha }[/math] раз.

Шаг "Присваивание"

На данном шаге происходит присвоение неиспользованных точек (строк матрицы [math]\displaystyle{ x }[/math]) к кластерам. Для точки-строки [math]\displaystyle{ p }[/math] вычисляется расстояние до каждого представителя. Результат: строка [math]\displaystyle{ p }[/math] добавляется в поддерево кластера, которому принадлежит наиближайший представитель.

Результатом работы алгоритма является дерево, ветвями которого являются отдельные кластеры. Листьями кластеров являются строки из матрицы [math]\displaystyle{ x }[/math].

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

Вычислительное ядро алгоритма представляет собой итерационное построение [math]\displaystyle{ k }[/math] кластеров, вычисление их центроид и назначение точек-представителей.

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

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

Схема реализации последовательного алгоритма

Схема работы алгоритма кластеризаци CURE

Последовательная сложность алгоритма

Максимальное время выполнения алгоритма [math]\displaystyle{ O(n^2 logn) }[/math]. Для двумерного пространства временная сложность может быть [math]\displaystyle{ O(n^2) }[/math]. Так что сложность алгоритма не хуже чем у центроидного. То есть при такой размерности входных данных CURE выполняется за полиномиальное время.

Информационный граф

Шаг "Инициализация"

В зависимости от алгоритма случайная выборка номеров строк матрицы [math]\displaystyle{ x }[/math] может производится либо зависимо, либо независимо друг от друга.

Шаг "Кластеризация"

Шаг "Назначение представителей"

Последовательный информационный граф для точек-представителей

Шаг "Сдвиг представителей к центроиде"

Шаг "Присваивание"

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

Входные данные: матрица [math]\displaystyle{ x \in R^{m\times n} }[/math], количество кластеров [math]\displaystyle{ k }[/math], число точек представителей [math]\displaystyle{ c }[/math], параметр [math]\displaystyle{ \alpha }[/math], параметр [math]\displaystyle{ \gamma }[/math].

[math]\displaystyle{ m }[/math] число точек для кластеризации, [math]\displaystyle{ n }[/math] размерность.

Параметр [math]\displaystyle{ \alpha }[/math] для сжатия точек представления к центру кластера. В оригинальной статье авторы показывают что [math]\displaystyle{ \alpha }[/math] от [math]\displaystyle{ 0.2 }[/math] до [math]\displaystyle{ 0.7 }[/math] помогает хорошо выявлять несферические кластеры и подавлять редкие выбросы.

Параметр [math]\displaystyle{ \gamma }[/math] задаёт какая часть от [math]\displaystyle{ m }[/math] точек будет использована при случайной выборке точек на шаге "Инициализация".

Число точек представителей выбирается в зависимости от данных. Если возможно появление кластеров сложной формы, то точек должно быть больше, чтобы выявить их форму. В оригинальной статье авторы показывают что уже при [math]\displaystyle{ c }[/math] равном [math]\displaystyle{ 10 }[/math] достигается неплохая эффективность.

Пример работы алгоритма для разных параметров [math]\displaystyle{ c }[/math].

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

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

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

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

ЧАСТЬ. Программная реализация алгоритма

Масштабируемость алгоритма и его реализации

Данный раздел будет заполнен к 15 ноября.

Существующие реализации алгоритма

Последовательная реализация CURE-алгоритма для кластеризации для Python/C++ представлена в пакете: pyclustering.

Также существует параллельная реализация алгоритма, описанная в сборнике [3]. Алгоритм предложенный в статье использует массив данных состоящий из размеров кластера, его центроида и репрезентативных точек, а при объединении кластеров информацию о новом кластере просто записывают в строчку предыдущего. Также для каждого алгоритма требуется считать индекс и расстояние до ближайшего кластера. Именно их поиск авторы статьи и предлагают распараллелить.

Литература

[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Sudipto Guha (Stanford), Rajeev Rastogi (Bell Labs), Kyuseok Shim (Korea Institute of Technology). CURE: an efficient clustering algorithm for large databases. SIGMOD '98 Proceedings of the 1998 ACM SIGMOD international conference on Management of data, pp 73-84

[3] Panagiotis E. Hadjidoukas, Laurent Amsaleg. OpenMP Shared Memory Parallel Programming. Volume 4315 of the series Lecture Notes in Computer Science pp 289-299 Parallelization of a Hierarchical Data Clustering Algorithm Using OpenMP