Участник: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> -окрестности какого-либо «ядра»), относятся к классу «шум». | |||
Версия от 13:03, 29 сентября 2016
| Плотностный алгоритм кластеризации 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] -окрестности какого-либо «ядра»), относятся к классу «шум».