101
правка
Изменения
→DBSCAN
=== DBSCAN ===
На вход алгоритму подаётся набор точек, параметры <tex>\epsilon</tex> (радиус окружности) и <tex>m</tex> (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые. * Основными будем считать точку, если в окружности с центром в этой точке и радиусом <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>C_j</tex> является непустым множеством точек и удовлетворяет двум условиям:* Любые две точки в кластере попарно связаны (то есть найдется такая точка в кластере, из которой достижимы обе этих точки).* Если точка достижима из какой-либо точки кластера, то она принадлежит кластеру.
Пусть для каждого <tex>x \in X^m</tex> имеем посчитанной его <tex>\epsilon</tex>-окрестность <tex>U_{\epsilon}(x) = \{x' \in X^m \: | \: \rho(x, x') \lt \epsilon\}</tex>
