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

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

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

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

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

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

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

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

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

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

Шаг 2. Для каждого кластера выбираем $c$ точек представителей, максимально удаленных друг от друга. Чисто $c$ остается постоянным.

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

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

Пример работы алгоритма для разных параметров $\alpha$.

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

Пусть дана матрица $x \in R^{m\times n}$, количество кластеров $k$, число точек представителей $\alpha$, параметр $\delta$, параметр $\gamma$.

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

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

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

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

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

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

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

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

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

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

(ПОЯСНЕНИЯ, ЕСЛИ ЕСТЬ ВРЕМЯ)

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

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

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

Параметр $\delta$ для сжатия точек представления к центру кластера. В оригинальной статье авторы показывают что $\delta$ от $0.2$ до $0.7$ помогает хорошо выявлять несферические кластеры и подавлять редкие выбросы.

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

Число точек представителей выбирается в зависимости от данных. Если возможно появление кластеров сложной формы, то точек должно быть больше, чтобы выявить их форму. В оригинальной статье авторы показывают что уже при $\alpha$ равном $10$ достигается неплохая эффективность.

(ВЫХОДНЫЕ ДАННЫЕ??)

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

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

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

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

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

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

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

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

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

Также существует параллельная реализация алгоритма, описанная в сборнике [3]. (ДОБАВИТЬ: ЧТО ПРЕДЛАГАЮТ СДЕЛАТЬ АВТОРЫ)

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