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

Плотностный алгоритм кластеризации DBSCAN
Последовательный алгоритм
Последовательная сложность	[math]-[/math]
Объём входных данных	[math]-[/math]
Объём выходных данных	[math]-[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]-[/math]
Ширина ярусно-параллельной формы	[math]-[/math]

Авторы описания: Вашуров И.М., Шемякин Р.О.

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

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

Исходные данные: объекты, которые нужно кластеризовать, параметры [math]MinPts, \ \varepsilon[/math] . Между объектами можно считать расстояния.

Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных.

Для построения оценки плотности, на основе соседства точек вводятся понятия достижимости и связности. Под [math]\varepsilon [/math] -соседями точки [math]x \in X[/math] понимается множество точек, расстояние до которых не превышает [math]\varepsilon [/math], т. е. [math]N_\varepsilon (x) = \{y \in X | D(x, y) \le \varepsilon\}[/math]. Тогда точка [math]y[/math] достижима из точки [math]x[/math], если существует последовательность точек [math]x^{(1)}=x, x^{(2)},... , x^{(p-1)}, x^{(p)}=y[/math], для которой выполнено:

[math] \begin{align} x^{(i+1)} \in N_\varepsilon (x^{(i)}), i=1,... ,p-1 \\ \mid N_\varepsilon (x^{(i)}) \mid \ge MinPts, i=1,... ,p-1 \end{align} [/math]

Здесь значение [math]MinPts[/math] задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее [math]MinPts \ \varepsilon[/math] -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее [math]MinPts \ \varepsilon [/math] -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы. При такой постановке задачи, под кластером понимается максимальное связное подмножество множества [math]X[/math] . Точки, не попавшие в какой-либо кластер (не принадлежащие [math]\varepsilon[/math] -окрестности какого-либо «ядра»), относятся к классу «шум».

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

Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов. Это может быть R*-дерево или k-d дерево. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Также для построения этих деревьев нужно уметь находить расстояние между объектами [math]\rho(u,v)[/math], в, это расстояние можно вводить разными способами. Например, если [math]\rho(u,v)[/math] - метрика в евклидовом пространстве, [math]u=(u_1,...,u_n)[/math] и [math](v_1,...,v_n)[/math], то расстояние вычисляется следующим образом: [math]\rho(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]

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

Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать специальную пространственную структуру данных для определения соседних объектов со сложностью [math]O(n)[/math], то сложность алгоритма [math]O(nlogn)[/math]. Если не использовать пространственную структуру, то в худшем случае алгоритм будет иметь сложность [math]O(n^2)[/math], так как придется считать полную матрицу расстояний между объектами.