Участник:Elena777mc/Плотностный алгоритм кластеризации DBSCAN: различия между версиями
| Строка 15: | Строка 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>\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>, для которой выполнено: | ||
| Строка 26: | Строка 28: | ||
Здесь значение <math>MinPts</math> задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее <math>MinPts \ \varepsilon</math> -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее <math>MinPts \ \varepsilon </math> -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы. | Здесь значение <math>MinPts</math> задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее <math>MinPts \ \varepsilon</math> -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее <math>MinPts \ \varepsilon </math> -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы. | ||
При такой постановке задачи, под кластером понимается максимальное связное подмножество множества <math>X</math> . Точки, не попавшие в какой-либо кластер (не принадлежащие <math>\varepsilon</math> -окрестности какого-либо «ядра»), относятся к классу «шум». | При такой постановке задачи, под кластером понимается максимальное связное подмножество множества <math>X</math> . Точки, не попавшие в какой-либо кластер (не принадлежащие <math>\varepsilon</math> -окрестности какого-либо «ядра»), относятся к классу «шум». | ||
| + | |||
| + | == Вычислительное ядро алгоритма == | ||
| + | |||
| + | == Макроструктура алгоритма == | ||
| + | |||
| + | == Схема реализации последовательного алгоритма == | ||
| + | |||
| + | == Последовательная сложность алгоритма == | ||
| + | Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать специальную структуру данных для определения соседних объектов со сложностью <math>O(n)</math>, то сложность алгоритма <math>O(nlogn)</math>. Если не использовать специальную структуру, то в худшем случае алгоритм будет иметь сложность <math>O(n^2)</math>, так как придется считать полную матрицу расстояний между объектами. | ||
Версия 19:22, 1 октября 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] -окрестности какого-либо «ядра»), относятся к классу «шум».
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать специальную структуру данных для определения соседних объектов со сложностью [math]O(n)[/math], то сложность алгоритма [math]O(nlogn)[/math]. Если не использовать специальную структуру, то в худшем случае алгоритм будет иметь сложность [math]O(n^2)[/math], так как придется считать полную матрицу расстояний между объектами.
