Участник:Dmitry/Плотностный алгоритм кластеризации

Плотностный алгоритм кластеризации DBSCAN
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n \log n) }[/math]
Объём входных данных	[math]\displaystyle{ n }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]

Авторы описания: Титов Д.Е.

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

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

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки [math]\displaystyle{ X }[/math] определяется двумя параметрами. Первым из них является [math]\displaystyle{ \varepsilon }[/math] – радиус «соседства» (приближенности) точки [math]\displaystyle{ X }[/math]. Тогда множество [math]\displaystyle{ M_\varepsilon(X) }[/math] будет включать в себя такие точки [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math], для которых следующее неравенство будет истинно:

[math]\displaystyle{ dist(X,f_i) \le \varepsilon }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math]

Функция [math]\displaystyle{ dist(var1, var2) }[/math] определяет расстояние между объектами выборки [math]\displaystyle{ D }[/math]. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью метрики Минковского.

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

Точка [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math] будет являться окруженной точкой (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) если:

[math]\displaystyle{ M_\varepsilon(X) \ge MCP }[/math]

Это значит, что точка [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math] окруженная, если количество «соседствующих» точек выборки [math]\displaystyle{ D }[/math] окажется большим, либо равным значению параметра [math]\displaystyle{ MCP }[/math] (рис. 1).

Рис. 1. Окруженная точка при MCP = 5

Точка [math]\displaystyle{ X }[/math] является прямо достижимой по плотности от точки [math]\displaystyle{ f }[/math] (при соответствующих [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]), если точка [math]\displaystyle{ X \in M(X) }[/math], т.е. точка [math]\displaystyle{ X }[/math] – это одна из точек [math]\displaystyle{ f }[/math] для другого окружения (соседства), где [math]\displaystyle{ f }[/math] – окруженная точка (рис. 2).

Рис. 2. Точка X прямо достижима по плотности от точки f

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка [math]\displaystyle{ f }[/math] достижима по плотности из точки [math]\displaystyle{ X }[/math], но точка [math]\displaystyle{ X }[/math] не достижима по плотности из точки [math]\displaystyle{ f }[/math] (рис. 3).

Рис. 3. Достижимость по плотности

Точка [math]\displaystyle{ X }[/math] соединена (связана) по плотности с точкой [math]\displaystyle{ f }[/math] (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) если существует точка [math]\displaystyle{ e }[/math] такая, что обе точки [math]\displaystyle{ X }[/math] и [math]\displaystyle{ f }[/math] являются достижимыми от точки [math]\displaystyle{ e }[/math] (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) (рис. 4).

Рис. 4. Соединение по плотности

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек [math]\displaystyle{ G }[/math] из набора данных [math]\displaystyle{ D }[/math], которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если [math]\displaystyle{ X \in G }[/math] и [math]\displaystyle{ f }[/math] достижима по плотности от точки [math]\displaystyle{ X }[/math], тогда и [math]\displaystyle{ f \in G }[/math], это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве [math]\displaystyle{ G }[/math] соединен по плотности со всеми объектами кластера (при заданных [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]).

Все объекты из набора данных [math]\displaystyle{ D }[/math] представляют собой совокупность подмножеств:

[math]\displaystyle{ D= \{ G_1, G_2,..., G_m, N \} }[/math],

где [math]\displaystyle{ G_1, G_2,..., G_m }[/math] – кластеры, образованные по плотности; [math]\displaystyle{ N }[/math] – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств [math]\displaystyle{ G_1, G_2,..., G_m }[/math].

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки [math]\displaystyle{ X }[/math] входного множества [math]\displaystyle{ D }[/math]. Основное время работы алгоритма используется на функцию [math]\displaystyle{ dist(var1, var2) }[/math], определяющую расстояние между объектами выборки [math]\displaystyle{ D }[/math] и сравнение расстояния с заданной [math]\displaystyle{ \varepsilon }[/math] для того, чтобы определить "соседствующие" точки.

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

Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки [math]\displaystyle{ D }[/math] осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: [math]\displaystyle{ dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}. }[/math]

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

[math]\displaystyle{ dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p} }[/math].

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

Реализация алгоритма DBSCAN может быть разделена на два этапа. В первую очередь из всего набора данных [math]\displaystyle{ D }[/math] необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта [math]\displaystyle{ X }[/math] из набора данных [math]\displaystyle{ D }[/math] определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for [math]\displaystyle{ \forall X \in D }[/math]
  [math]\displaystyle{ \{ }[/math]
    if [math]\displaystyle{  (X \in G_i, i= \overline{1,n}) }[/math]
    [math]\displaystyle{ \{ }[/math]
       if [math]\displaystyle{  (X_i \in M_\varepsilon(X)) }[/math]
       [math]\displaystyle{ \{ }[/math]
         find [math]\displaystyle{ X_i \in D }[/math] достижимы по плотности
         from [math]\displaystyle{ X_i \in M_\varepsilon(X) }[/math]
       [math]\displaystyle{ \} }[/math]
       else if [math]\displaystyle{  (X_i \notin M_\varepsilon(X) }[/math] and [math]\displaystyle{ X }[/math] не достижим от любого другого объекта [math]\displaystyle{ ) }[/math]
       [math]\displaystyle{ \{ }[/math]
         [math]\displaystyle{ X \in N }[/math]
       [math]\displaystyle{ \} }[/math]
 [math]\displaystyle{ \} }[/math]

параметры [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math] задаются пользователем.

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

Сложность алгоритма зависит от поиска всех точек в [math]\displaystyle{ \varepsilon }[/math]-окрестности конкретной точки [math]\displaystyle{ X }[/math] из выборки [math]\displaystyle{ D }[/math]. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность [math]\displaystyle{ O(n^2) }[/math] (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до [math]\displaystyle{ O(\text{n log n}) }[/math].

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

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

• Задаются параметры [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math].
• На входе алгоритма набор данных [math]\displaystyle{ D }[/math] разбивается на множество точек [math]\displaystyle{ X_n }[/math], где [math]\displaystyle{ n }[/math] - количество точек.
• Для каждой точки [math]\displaystyle{ X_n }[/math] из выборки [math]\displaystyle{ D }[/math] с помощью функции [math]\displaystyle{ dist(var1, var2) }[/math] определяется расстояние между остальными точками.
• Далее алгоритм объединяет точки [math]\displaystyle{ X_n }[/math], образуя подмножества [math]\displaystyle{ M_\varepsilon(X_n) }[/math], объекты которого удовлетворяют условию: [math]\displaystyle{ dist(X,f_i) \le \varepsilon }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math].
• Если подмножество [math]\displaystyle{ M_\varepsilon(X_n) }[/math] состоит из [math]\displaystyle{ MCP }[/math] и больше объектов (т. е. [math]\displaystyle{ M_\varepsilon(X_n) \ge MPC }[/math]), то подмножество [math]\displaystyle{ M_\varepsilon(X_n) }[/math] образует кластер [math]\displaystyle{ G_m }[/math].
• Подмножество [math]\displaystyle{ N }[/math] включает в себя все объекты, которые не принадлежат ни одному из подмножеств [math]\displaystyle{ G_1, G_2,..., G_m }[/math].

Рис. 5. Информационный граф алгоритма DBSCAN

Ресурс параллелизма алгоритма

Ширина ярусно-параллельной формы алгоритма [math]\displaystyle{ O(m) }[/math], где m - количество частей, на которые разбиваются все объекты из набора данных [math]\displaystyle{ D }[/math]. Высотой ярусно-параллельной формы алгоритма является [math]\displaystyle{ O(|X| \log |X|) }[/math], где [math]\displaystyle{ \mid X \mid }[/math] - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных [math]\displaystyle{ D }[/math], для которых задана метрическая функция расстояния [math]\displaystyle{ dist(var1, var2) }[/math]. Объём входных данных: [math]\displaystyle{ n }[/math].

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

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра [math]\displaystyle{ MCP }[/math], большие значения параметра [math]\displaystyle{ \varepsilon }[/math] ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

• Число настраиваемых параметров равно двум: [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MPC }[/math].
• Вычислительная сложность алгоритма [math]\displaystyle{ O(\text{n log n}) }[/math].
• Возможность обрабатывать большой объем данных.
• Результат не зависит от порядка ввода данных.
• Не требуется указывать количество кластеров.
• Возможность выделять кластеры в присутствии выбросов.
• Число итераций определено заранее.

Программная реализация алгоритма

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

Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов. Программа реализована на языке C++.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• число процессоров [1 : 128] с шагом по степеням двойки;
• число входных объектов [1000 : 40000].

Рис. 6. График масштабируемости DBSCAN

На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы:

• При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.

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

• При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.

Реализация на языке C++

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

Scikit-Learn включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

SPMF предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

Apache Commons Мath содержит java-реализацию алгоритма выполняющегося за квадратичное время.

ELKI предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

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

GNU R содержит DBSCAN в fpc пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R dbscan.