1632
правки
Изменения
м
Необходима Необходимо так сопоставить объектам из множества <tex>X</tex> метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение.
rollbackEdits.php mass rollback
== Меры качества кластеризации ==
Для оценки качества кластеризации задачу можно переформулировать в терминах задачи дискретной оптимизации.
В качестве примера, стремятся достичь минимума среднего внутрикластерного расстояния <tex>F_0 = \dfrac{\sum_{i<j}{[y_i=y_j]\cdot\rho(x_i, x_j)}}{\sum_{i<j}[y_i=y_j]}</tex> или максимума среднего межкластерного расстояния <tex>F_1 = \dfrac{\sum_{i<j}{[y_i\neq y_j]\cdot\rho(x_i, x_j)}}{\sum_{i<j}[y_i\neq y_j]}</tex>.
== Псевдокод некоторых алгоритмов кластеризации ==
=== Метод K-средних (Алгоритм Ллойда) ===
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем объекты снова разбиваются на кластеры в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния.
Алгоритм минимизирует сумму квадратов внутрикластерных расстояний:
<tex> \sum_{i = 1}^{m} ||x_i - \mu_{a_i}||^2 \: \to \: \min_{ \{a_i\}, \{\mu_a\}}, \: \: ||x_i - \mu_a||^2 = \sum_{j = 1}^{n} (f_j(x_i) - \mu_{a_j})^2</tex>
=== DBSCAN ===
Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на большом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые. На вход алгоритму подаётся выборка набор точек, параметры <tex>\epsilon</tex> (радиус окружности) и <tex>X^m = </tex> (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые. * Точка является ''основной'', если в окружности с центром в этой точке и радиусом <tex>\epsilon</tex> находится как минимум <tex>m</tex> точек. * Точка <tex>a</tex> является ''прямо достижимой'' из основной точки <tex>b</tex>, если <tex>a</tex> находится на расстоянии, не большем <tex>{ x_1\epsilon}</tex> от точки <tex>b</tex>.* Точка <tex>a</tex> является ''достижимой'' из <tex>b</tex>, если существует путь <tex>p_1, \dots, x_m \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>.
<tex>U := X^m</tex> <font color="gray"># Непомеченные объекты</font>
<tex>U := U \setminus K</tex>
<font color="blue"><tex>return</tex></font> <tex>a, \: A, \: mark</tex> <font color="gray"># Возвращаем количество кластеров, распределение по кластерам и метки объектов (внутренние, граничные или шумовые)</font>
DBSCAN находит практическое применение во многих реальных задачах, например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей {{---}} в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, делить их на социальные группы, моделировать поведение посетителей сайта. Алгоритм также может использоваться для [[Сегментация изображений|сегментации изображений]].
== Пример кода ==
