Участник:Elena777mc/Плотностный алгоритм кластеризации DBSCAN: различия между версиями
(Новая страница: «= Свойства и структура алгоритмов = == Общее описание алгоритма == == Математическое описа…») |
|||
| Строка 1: | Строка 1: | ||
| + | {{algorithm | ||
| + | | name = Плотностный алгоритм кластеризации DBSCAN | ||
| + | | serial_complexity = <math>-</math> | ||
| + | | pf_height = <math>-</math> | ||
| + | | pf_width = <math>-</math> | ||
| + | | input_data = <math>-</math> | ||
| + | | output_data = <math>-</math> | ||
| + | }} | ||
| + | |||
| + | |||
| + | |||
= Свойства и структура алгоритмов = | = Свойства и структура алгоритмов = | ||
| Строка 4: | Строка 15: | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
| + | Для построения оценки плотности, на основе соседства точек вводятся понятия | ||
| + | достижимости и связности. Под <math>\varepsilon </math> -соседями точки <math>x \in X</math> понимается множество точек, расстояние до которых не превышает <math>\varepsilon </math>, т. е. <math>N_\varepsilon (x) = \{y \in X | D(x, y) \le \varepsilon\}</math>. Тогда точка y достижима из точки x, если существует последовательность точек <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> -окрестности какого-либо «ядра»), относятся к классу «шум». | ||
Версия 16:03, 29 сентября 2016
| Плотностный алгоритм кластеризации DBSCAN | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]-[/math] |
| Объём входных данных | [math]-[/math] |
| Объём выходных данных | [math]-[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]-[/math] |
| Ширина ярусно-параллельной формы | [math]-[/math] |
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
1.2 Математическое описание алгоритма
Для построения оценки плотности, на основе соседства точек вводятся понятия достижимости и связности. Под [math]\varepsilon [/math] -соседями точки [math]x \in X[/math] понимается множество точек, расстояние до которых не превышает [math]\varepsilon [/math], т. е. [math]N_\varepsilon (x) = \{y \in X | D(x, y) \le \varepsilon\}[/math]. Тогда точка y достижима из точки x, если существует последовательность точек [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] -окрестности какого-либо «ядра»), относятся к классу «шум».
