Изменения

DBSCAN - это основанная на плотности пространственная кластеризация для приложений с шумами. Основная идея метода основана на плотности пространства. Если дан заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве, то алгоритм сгруппирует вместе все точкена группы точек, которые лежат друг от друга на малом большом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.

* Основными будем считать точкуТочка является ''основной'', если в окружности с центром в этой точке и радиусом <tex>\epsilon</tex> находится как минимум <tex>m</tex> точек. * Точка <tex>a</tex> является ''прямо достижимой '' из основной точки <tex>b</tex>, если <tex>a</tex> находится на расстоянии, не большем <tex>{\epsilon}</tex> от точки <tex>b</tex>, причем <tex>b</tex> должна быть основной точкой.* Точка <tex>a</tex> является ''достижимой '' из <tex>b</tex>, если существует путь <tex>p_1, \dots, p_n</tex> с <tex>p_1 = a</tex> и <tex>p_n = b</tex>, где каждая точка <tex>p_{i+1}</tex> прямо достижима из точки <tex>p_i</tex> .* Все остальные точки, которые не достижимы из основных точек, считаются ''шумовыми''.

Теперь, если Основная точка является основной, то она формирует кластер вместе со всеми достижимыми из нее точками, достижимые из этой точкиформирует ''кластер''. В кластер будут входить как основные, так и неосновные точки. Таким образом, каждый кластер содержит по меньшей мере одну основную точку.

Алгоритм начинается с произвольной точки из набора, которая еще не просматривалась. Ищется Для точки ищется <tex>{\epsilon}</tex>-окрестность точки. Если она не содержит как минимум <tex>m</tex> точек, то помечается как шумовая. Иначе , иначе образуется кластер <tex>K</tex>, который включает все точки из окрестности. Если точка из окрестности уже является частью другого кластера <tex>C_j</tex>, то все точки данного кластера добавляются в кластер <tex>K</tex>. Затем выбирается и обрабатывается новая непосещённая , не посещённая ранее точка, что ведёт к обнаружению следующего кластера или шума.

Рассмотрим код: Пусть для каждого <tex>x \in X^m</tex> имеем посчитанной его <tex>\epsilon</tex>-окрестность <tex>U_{\epsilon}(x) = \{x' \in X^m \: | \: \rho(x, x') \lt \epsilon\}</tex>.