Участник: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{ \alpha }[/math], параметр [math]\displaystyle{ \delta }[/math], параметр [math]\displaystyle{ \gamma }[/math].

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

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

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

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

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

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

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

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

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

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

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

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

Входные данные: матрица [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] достигается неплохая эффективность.

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

Алгоритм 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