101
правка
Изменения
→DBSCAN
Решение задачи кластеризации объективно неоднозначно по ряду причин:
* Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.;* Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<ref>[https://scikit-learn.org/stable/modules/clustering.html scikit-learn {{---}} Clustering]</ref>.;* Результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору метрик для определенных классов задач.<ref>Cornwell, B. (2015). Linkage Criteria for Agglomerative Hierarchical Clustering. Social Sequence Analysis, 270–274.</ref>.
Число кластеров фактически является гиперпараметром для алгоритмов кластеризации. Подробнее про другие гиперпараметры и их настройку можно прочитать в статье<ref>Shalamov Viacheslav, Valeria Efimova, Sergey Muravyov, and Andrey Filchenkov. "Reinforcement-based Method for Simultaneous Clustering Algorithm Selection and its Hyperparameters Optimization." Procedia Computer Science 136 (2018): 144-153.</ref>.
Алгоритм кластеризации <tex>a</tex> является '''масштабно инвариантным''' (англ. ''scale-invariant''), если для любой функции расстояния <tex>\rho</tex> и любой константы <tex>\alpha > 0</tex> результаты кластеризации с использованием расстояний <tex>\rho</tex> и <tex>\alpha\cdot\rho</tex> совпадают.
}}
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависила зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
{{Определение
|definition =
|definition =
Функция расстояния <tex>{\rho}'</tex> является '''допустимым преобразованием''' функции расстояния <tex>\rho</tex>, если
#<tex>{\rho}'(x_i, x_j) \leqslant \rho(x_i, x_j)</tex>, если <tex>x_i</tex> и <tex>x_j</tex> лежат в одном кластере;
#<tex>{\rho}'(x_i, x_j) \geqslant \rho(x_i, x_j)</tex>, если <tex>x_i</tex> и <tex>x_j</tex> лежат в разных кластерах.
}}
== Типология задач кластеризации ==
=== Типы входных данных ===
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и категориальными.;
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
=== Цели кластеризации ===
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей.;* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием.;
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
=== Методы кластеризации ===
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.;* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.:** [[EM-алгоритм]];* [[Иерархическая_кластеризация|Иерархические алгоритмы кластеризации]]. Упорядочивание данных путем создания иерархии вложенных кластеров.;* [[K-средних|Алгоритм <tex>\mathrm{k}</tex>-средних]] <sup>[на 28.01.19 не создан]</sup> (англ. ''<tex>\mathrm{k}</tex>-means''). Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров.;* Распространение похожести (англ. ''affinity propagation''). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера.;* Сдвиг среднего значения (англ. ''mean shift''). Выбирает центроиды кластеров в областях с наибольшей плотностью.;* Спектральная кластеризация (англ. ''spectral clustering''). Использует собственные значения матрицы расстояний для понижения размерности перед использованием других методов кластеризации.;
* Основанная на плотности пространственная кластеризация для приложений с шумами (англ. ''Density-based spatial clustering of applications with noise'', ''DBSCAN''). Алгоритм группирует в один кластер точки в области с высокой плотностью. Одиноко расположенные точки помечает как шум.
[[Файл:cluster_comparison.png|thumb|800px|center|<div style="text-align:center">Сравнение алгоритмов кластеризации из пакета scikit-learn<ref>[https://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html scikit-learn {{---}} Comparing different clustering algorithms on toy datasets]</ref></div>]]
== Меры качества кластеризации ==
Для оценки качества кластеризации задачу можно переформулировать в терминах задачи дискретной оптимизации.
== Применение ==
=== Биология и биоинформатика ===
* В области экологии кластеризация используется для выделения пространственных и временных сообщест сообществ организмов в однородных условиях.;* Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции.;* Кластеризация помогает автоматически определять генотипы по различным частям хромосом.;
* Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.
=== Медицина ===
* Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении.;
* Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.
=== Маркетинг ===
Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
=== Интернет ===
* Выделение групп людей на основе графа связей в социальных сетях.;
* Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.
=== Компьютерные науки ===
* Кластеризация используется в сегментации изображений для определения границ и распознавания объектов.;* Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции.;* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере.;
* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
== Псевдокод некоторых алгоритмов кластеризации ==
=== Метод 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>
На вход алгоритму подаётся выборка <tex>X^m = \{ x_1, \dots, x_m \}</tex> и количество кластеров <tex>K = |Y|</tex>.
На выходе получаем центры кластеров <tex>\mu_a</tex> для кластеров <tex>a \in Y</tex>.
<tex>\mu_a := init(X^m)</tex> <font color="gray"># Инициализируем произвольно начальное приближение для центров кластеров <tex>a \in Y</tex></font>. (Можно наиболее удалённые друг от друга объекты выборки)
<tex>A := [ -1 \: | \: for \: x_i \in X^m ]</tex> <font color="gray"># Инициализируем массив отображений из объектов выборки в их кластеры</font>
<tex>changed := True</tex>
<font color="blue"><tex>while</tex></font> <tex>changed</tex>: <font color="gray"># Повторяем пока <tex>A_i</tex> изменяются</font>
<tex>changed := False</tex>
<font color="blue"><tex>for</tex></font> <tex>x_i \in X^m</tex>: <font color="gray"># Относим каждый <tex>x_i</tex> к ближайшему центру</font>
<tex>A_{i, old} := A_i</tex>
<tex>A_i := arg \min_{a \in Y} ||x_i - \mu_a||</tex>
<font color="blue"><tex>if</tex></font> <tex>A_i \neq A_{i, old}</tex>:
<tex>changed := True</tex>
<font color="blue"><tex>for</tex></font> <tex>a \in Y</tex>: <font color="gray"># Вычисляем новые положения центров</font>
<tex>\mu_a := \frac{\sum_{i = 1}^{m}[A_i = a] x_i}{\sum_{i = 1}^{m}[A_i = a]}</tex>
<font color="blue"><tex>return</tex></font> <tex>\mu_a, \: A</tex> <font color="gray"># Возвращаем центры кластеров и распределение по ним объектов выборки</font>
=== 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>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>.
<tex>U := X^m</tex> <font color="gray"># Непомеченные объекты</font>
<tex>A := [ -1 \: | \: for \: x_i \in X^m ]</tex> <font color="gray"># Инициализируем массив отображений из объектов выборки в их кластеры</font>
<tex>a := 0</tex> <font color="gray"># Количество кластеров</font>
<font color="blue"><tex>while</tex></font> <tex>U \neq \varnothing</tex>: <font color="gray"># Пока в выборке есть непомеченные объекты</font>
<tex>x := rand(U)</tex> <font color="gray"># Берём случайную непомеченную точку</font>
<font color="blue"><tex>if</tex></font> <tex>|U_{\epsilon}(x) < m|</tex>:
<tex>mark[x]</tex> <tex>:=</tex> "<tex>noise</tex>" <font color="gray"># Пометим <tex>x</tex> как, возможно, шумовой</font>
<font color="blue"><tex>else</tex></font>:
<tex>K := U_{\epsilon}(x)</tex>
<tex>a := a + 1</tex> <font color="gray"># Создадим новый кластер K</font>
<font color="blue"><tex>for</tex></font> <tex>x' \in K</tex>:
<font color="blue"><tex>if</tex></font> <tex>x' \in U</tex> || <tex>mark[x']</tex> <tex>==</tex> "<tex>noise</tex>": <font color="gray"># Если <tex>x'</tex> не помечен или помечен как шумовой</font>
<font color="blue"><tex>if</tex></font> <tex>|U_{\epsilon}(x')| \geq m</tex>:
<tex>mark[x'] :=</tex> "<tex>interior</tex>" <font color="gray"># Пометим <tex>x'</tex> как внутренний кластера <tex>K</tex></font>
<tex>K := K \cup U_{\epsilon}(x')</tex> <font color="gray"># Добавим вместе с <tex>x'</tex> всю его окрестность</font>
<font color="blue"><tex>else</tex></font>:
<tex>mark[x'] :=</tex> "<tex>frontier</tex>" <font color="gray"># Пометим <tex>x'</tex> как граничный кластера <tex>K</tex></font>
<font color="blue"><tex>for</tex></font> <tex>x_i \in K</tex>:
<tex>A_i := a</tex>
<tex>U := U \setminus K</tex>
<font color="blue"><tex>return</tex></font> <tex>a, \: A, \: mark</tex> <font color="gray"># Возвращаем количество кластеров, распределение по кластерам и метки объектов (внутренние, граничные или шумовые)</font>
DBSCAN находит практическое применение во многих реальных задачах, например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей {{---}} в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, делить их на социальные группы, моделировать поведение посетителей сайта. Алгоритм также может использоваться для [[Сегментация изображений|сегментации изображений]].
== Пример кода ==
=== Пример на языке R ===
{{Main|Примеры кода на R}}
Для реализации алгоритма ''k-средних'' используется пакет <code>ClusterR</code>. В нем реализовано 2 функции: <code>KMeans_arma()</code> и <code>KMeans_rcpp()</code>. В примере далее рассмотрена реализация с использованием функции <code>KMeans_arma()</code>.
<font color="gray"># importing package and its' dependencies</font>
library(ClusterR)
<font color="gray"># reading data</font>
data <- read.csv(<font color="green">"data.csv"</font>)
<font color="gray"># evaluating model</font>
model <- KMeans_arma(data, <font color="#660099">clusters</font> = <font color="blue">2</font>, <font color="#660099">n_iter</font> = <font color="blue">10</font>, <font color="#660099">seed_mode</font> = <font color="green">"random_subset"</font>,
<font color="#660099">verbose</font> = T, <font color="#660099">CENTROIDS</font> = NULL)
<font color="gray"># predicting results</font>
predictions <- predict_KMeans(test_data, model)
== См. также ==
* [[Оценка_качества_в_задаче_кластеризации|Оценка качества в задаче кластеризации]]
* [[EM-алгоритм|EM-алгоритм]]<sup>[на 28.12.18 не создан]</sup>
* [[Иерархическая_кластеризация|Иерархическая кластеризация]]
* [[k-средних|<tex>\mathrm{k}</tex>-средних]]<sup>[на 28.1201.18 не создан]</sup>
== Примечания ==
