Участник:Elena777mc/Плотностный алгоритм кластеризации DBSCAN
| Плотностный алгоритм кластеризации DBSCAN | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ - }[/math] |
| Объём входных данных | [math]\displaystyle{ - }[/math] |
| Объём выходных данных | [math]\displaystyle{ - }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ - }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ - }[/math] |
Свойства и структура алгоритмов
Общее описание алгоритма
Математическое описание алгоритма
Для построения оценки плотности, на основе соседства точек вводятся понятия достижимости и связности. Под [math]\displaystyle{ \varepsilon }[/math] -соседями точки [math]\displaystyle{ x \in X }[/math] понимается множество точек, расстояние до которых не превышает [math]\displaystyle{ \varepsilon }[/math], т. е. [math]\displaystyle{ N_\varepsilon (x) = \{y \in X | D(x, y) \le \varepsilon\} }[/math]. Тогда точка y достижима из точки x, если существует последовательность точек [math]\displaystyle{ x^{(1)}=x, x^{(2)},... , x^{(p-1)}, x^{(p)}=y }[/math], для которой выполнено:
- [math]\displaystyle{ \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]\displaystyle{ MinPts }[/math] задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее [math]\displaystyle{ MinPts \ \varepsilon }[/math] -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее [math]\displaystyle{ MinPts \ \varepsilon }[/math] -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы. При такой постановке задачи, под кластером понимается максимальное связное подмножество множества [math]\displaystyle{ X }[/math] . Точки, не попавшие в какой-либо кластер (не принадлежащие [math]\displaystyle{ \varepsilon }[/math] -окрестности какого-либо «ядра»), относятся к классу «шум».