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

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

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

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

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

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

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

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

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

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

Вторым параметром определения плотности точек является $MCP$ – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу $\varepsilon$.

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

[math]M_\varepsilon(X) \le MPC[/math]

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

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

Точка $X$ является прямо достижимой по плотности от точки $f$ (при соответствующих $\varepsilon$ и $MPC$), если точка $X \in M(X)$, т.е. точка $X$ – это одна из точек $f$ для другого окружения (соседства), где $f$ – окруженная точка (рис. 2).

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

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка $f$ достижима по плотности из точки $X$, но точка $X$ не достижима по плотности из точки $f$ (рис. 3).

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

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

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

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

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

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

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

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

где $G_1, G_2,..., G_m$ – кластеры, образованные по плотности; $N$ – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств $G_1, G_2,..., G_m$.

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

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

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

Вычисление расстояния между двумя объектами из выборки $D$ осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: $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}.$

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

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

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

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

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

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

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

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

параметры $\varepsilon$ и $MCP$ задаются пользователем.

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

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

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

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

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

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

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

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

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

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