Кластеризация — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Методы кластеризации)
(Метод K-средних (Алгоритм Ллойда))
 
(не показано 13 промежуточных версий 5 участников)
Строка 21: Строка 21:
  
 
Решение задачи кластеризации объективно неоднозначно по ряду причин:
 
Решение задачи кластеризации объективно неоднозначно по ряду причин:
* Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.
+
* Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области;
* Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<ref>[https://scikit-learn.org/stable/modules/clustering.html scikit-learn {{---}} Clustering]</ref>.
+
* Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<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>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>.
 
Число кластеров фактически является гиперпараметром для алгоритмов кластеризации. Подробнее про другие гиперпараметры и их настройку можно прочитать в статье<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>.
Строка 33: Строка 33:
 
Алгоритм кластеризации <tex>a</tex> является '''масштабно инвариантным''' (англ. ''scale-invariant''), если для любой функции расстояния <tex>\rho</tex> и любой константы <tex>\alpha > 0</tex> результаты кластеризации с использованием расстояний <tex>\rho</tex> и <tex>\alpha\cdot\rho</tex> совпадают.
 
Алгоритм кластеризации <tex>a</tex> является '''масштабно инвариантным''' (англ. ''scale-invariant''), если для любой функции расстояния <tex>\rho</tex> и любой константы <tex>\alpha > 0</tex> результаты кластеризации с использованием расстояний <tex>\rho</tex> и <tex>\alpha\cdot\rho</tex> совпадают.
 
}}  
 
}}  
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависила от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
+
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 42: Строка 42:
 
|definition =
 
|definition =
 
Функция расстояния <tex>{\rho}'</tex> является '''допустимым преобразованием''' функции расстояния <tex>\rho</tex>, если
 
Функция расстояния <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) \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> лежат в разных кластерах.
 
#<tex>{\rho}'(x_i, x_j) \geqslant \rho(x_i, x_j)</tex>, если <tex>x_i</tex> и <tex>x_j</tex> лежат в разных кластерах.
 
}}
 
}}
Строка 75: Строка 75:
 
== Типология задач кластеризации ==
 
== Типология задач кластеризации ==
 
=== Типы входных данных ===
 
=== Типы входных данных ===
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и категориальными.
+
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и категориальными;
 
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
 
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
  
Строка 82: Строка 82:
  
 
=== Цели кластеризации ===
 
=== Цели кластеризации ===
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей.
+
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей;
* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием.
+
* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием;
 
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
 
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
  
 
=== Методы кластеризации ===
 
=== Методы кластеризации ===
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.
+
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике;
* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.
+
* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности:
** [[EM-алгоритм]]<sup>[на 28.01.19 не создан]</sup>
+
** [[EM-алгоритм]];
* [[Иерархическая_кластеризация|Иерархические алгоритмы кластеризации]]. Упорядочивание данных путем создания иерархии вложенных кластеров.
+
* [[Иерархическая_кластеризация|Иерархические алгоритмы кластеризации]]. Упорядочивание данных путем создания иерархии вложенных кластеров;
* [[K-средних|Алгоритм <tex>\mathrm{k}</tex>-средних]]<sup>[на 28.01.19 не создан]</sup> (англ. ''<tex>\mathrm{k}</tex>-means''). Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров.
+
* [[K-средних|Алгоритм <tex>\mathrm{k}</tex>-средних]]<sup>[на 28.01.19 не создан]</sup> (англ. ''<tex>\mathrm{k}</tex>-means''). Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров;
* Распространение похожести (англ. ''affinity propagation''). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера.
+
* Распространение похожести (англ. ''affinity propagation''). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера;
* Сдвиг среднего значения (англ. ''mean shift''). Выбирает центроиды кластеров в областях с наибольшей плотностью.
+
* Сдвиг среднего значения (англ. ''mean shift''). Выбирает центроиды кластеров в областях с наибольшей плотностью;
* Спектральная кластеризация (англ. ''spectral clustering''). Использует собственные значения матрицы расстояний для понижения размерности перед использованием других методов кластеризации.
+
* Спектральная кластеризация (англ. ''spectral clustering''). Использует собственные значения матрицы расстояний для понижения размерности перед использованием других методов кластеризации;
 
* Основанная на плотности пространственная кластеризация для приложений с шумами (англ. ''Density-based spatial clustering of applications with noise'', ''DBSCAN''). Алгоритм группирует в один кластер точки в области с высокой плотностью. Одиноко расположенные точки помечает как шум.
 
* Основанная на плотности пространственная кластеризация для приложений с шумами (англ. ''Density-based spatial clustering of applications with noise'', ''DBSCAN''). Алгоритм группирует в один кластер точки в области с высокой плотностью. Одиноко расположенные точки помечает как шум.
  
Строка 109: Строка 109:
 
== Применение ==
 
== Применение ==
 
=== Биология и биоинформатика ===
 
=== Биология и биоинформатика ===
* В области экологии кластеризация используется для выделения пространственных и временных сообщест организмов в однородных условиях.
+
* В области экологии кластеризация используется для выделения пространственных и временных сообществ организмов в однородных условиях;
* Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции.
+
* Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции;
* Кластеризация помогает автоматически определять генотипы по различным частям хромосом.
+
* Кластеризация помогает автоматически определять генотипы по различным частям хромосом;
 
* Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.
 
* Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.
 
=== Медицина ===
 
=== Медицина ===
* Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении.
+
* Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении;
 
* Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.
 
* Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.
 
=== Маркетинг ===
 
=== Маркетинг ===
Строка 120: Строка 120:
 
Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
 
Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
 
=== Интернет ===
 
=== Интернет ===
* Выделение групп людей на основе графа связей в социальных сетях.
+
* Выделение групп людей на основе графа связей в социальных сетях;
 
* Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.
 
* Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.
 
=== Компьютерные науки ===
 
=== Компьютерные науки ===
* Кластеризация используется в сегментации изображений для определения границ и распознавания объектов.
+
* Кластеризация используется в сегментации изображений для определения границ и распознавания объектов;
* Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции.
+
* Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции;
* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере.
+
* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;
 
* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
 
* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
 +
 +
== Псевдокод некоторых алгоритмов кластеризации ==
 +
=== Метод 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.01.18 не создан]</sup>
+
* [[EM-алгоритм|EM-алгоритм]]
 
* [[Иерархическая_кластеризация|Иерархическая кластеризация]]
 
* [[Иерархическая_кластеризация|Иерархическая кластеризация]]
 
* [[k-средних|<tex>\mathrm{k}</tex>-средних]]<sup>[на 28.01.18 не создан]</sup>
 
* [[k-средних|<tex>\mathrm{k}</tex>-средних]]<sup>[на 28.01.18 не создан]</sup>

Текущая версия на 19:20, 8 февраля 2021

Пример кластеризации

Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.

Задача кластеризации относится к классу задач обучения без учителя.

Постановка задачи кластеризации[править]

Пусть [math]X[/math] — множество объектов, [math]Y[/math] — множество идентификаторов (меток) кластеров. На множестве [math]X[/math] задана функция расстояния между объектами [math]\rho(x,x')[/math]. Дана конечная обучающая выборка объектов [math]X^m = \{ x_1, \dots, x_m \} \subset X[/math]. Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту [math]x_i \in X^m[/math] сопоставить метку [math]y_i \in Y[/math], таким образом чтобы объекты внутри каждого кластера были близки относительно метрики [math]\rho[/math], а объекты из разных кластеров значительно различались.

Определение:
Алгоритм кластеризации — функция [math]a\colon X\to Y[/math], которая любому объекту [math]x\in X[/math] ставит в соответствие идентификатор кластера [math]y\in Y[/math].

Множество [math]Y[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки объектов из обучающей выборки [math]y_i[/math] изначально не заданы, и даже может быть неизвестно само множество [math]Y[/math].

Решение задачи кластеризации объективно неоднозначно по ряду причин:

  • Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области;
  • Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр[1];
  • Результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору метрик для определенных классов задач.[2].

Число кластеров фактически является гиперпараметром для алгоритмов кластеризации. Подробнее про другие гиперпараметры и их настройку можно прочитать в статье[3].

Теорема невозможности Клейнберга[править]

Для формализации алгоритмов кластеризации была использована аксиоматическая теория. Клейнберг постулировал три простых свойства в качестве аксиом кластеризации и доказал теорему, связывающую эти свойства.

Определение:
Алгоритм кластеризации [math]a[/math] является масштабно инвариантным (англ. scale-invariant), если для любой функции расстояния [math]\rho[/math] и любой константы [math]\alpha \gt 0[/math] результаты кластеризации с использованием расстояний [math]\rho[/math] и [math]\alpha\cdot\rho[/math] совпадают.

Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.

Определение:
Полнота (англ. Richness). Множество результатов кластеризации алгоритма [math]a[/math] в зависимости от изменения функции расстояния [math]\rho[/math] должно совпадать со множеством всех возможных разбиений множества объектов [math]X[/math].

Вторая аксиома утверждает, что алгоритм кластеризации должен уметь кластеризовать обучающую выборку на любое фиксированное разбиение для какой-то функции расстояния [math]\rho[/math].

Определение:
Функция расстояния [math]{\rho}'[/math] является допустимым преобразованием функции расстояния [math]\rho[/math], если
  1. [math]{\rho}'(x_i, x_j) \leqslant \rho(x_i, x_j)[/math], если [math]x_i[/math] и [math]x_j[/math] лежат в одном кластере;
  2. [math]{\rho}'(x_i, x_j) \geqslant \rho(x_i, x_j)[/math], если [math]x_i[/math] и [math]x_j[/math] лежат в разных кластерах.


Определение:
Алгоритм кластеризации является согласованным (англ. consistent), если результат кластеризации не изменяется после допустимого преобразования функции расстояния.

Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.

Примеры преобразований с сохранением кластеров
Cluster 0.png Clusters scale inv.png Cluster consist.png
Исходное расположение объектов и их кластеризация Пример масштабной инвариантности. Уменьшен масштаб по оси ординат в два раза. Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние уменьшилось, межклассовое увеличилось.


Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:

Теорема (Клейнберга, о невозможности):
Для множества объектов, состоящего из двух и более элементов, не существует алгоритма кластеризации, который был бы одновременно масштабно-инвариантным, согласованным и полным.

Несмотря на эту теорему Клейнберг показал[4], что иерархическая кластеризация по методу одиночной связи с различными критериями останова удовлетворяет любым двум из трех аксиом.

Типология задач кластеризации[править]

Типы входных данных[править]

  • Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. features). Признаки могут быть как числовыми, так и категориальными;
  • Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.

Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.

Цели кластеризации[править]

  • Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей;
  • Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием;
  • Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.

Методы кластеризации[править]

  • Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике;
  • Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности:
  • Иерархические алгоритмы кластеризации. Упорядочивание данных путем создания иерархии вложенных кластеров;
  • Алгоритм [math]\mathrm{k}[/math]-средних[на 28.01.19 не создан] (англ. [math]\mathrm{k}[/math]-means). Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров;
  • Распространение похожести (англ. affinity propagation). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера;
  • Сдвиг среднего значения (англ. mean shift). Выбирает центроиды кластеров в областях с наибольшей плотностью;
  • Спектральная кластеризация (англ. spectral clustering). Использует собственные значения матрицы расстояний для понижения размерности перед использованием других методов кластеризации;
  • Основанная на плотности пространственная кластеризация для приложений с шумами (англ. Density-based spatial clustering of applications with noise, DBSCAN). Алгоритм группирует в один кластер точки в области с высокой плотностью. Одиноко расположенные точки помечает как шум.


Сравнение алгоритмов кластеризации из пакета scikit-learn[5]

Меры качества кластеризации[править]

Для оценки качества кластеризации задачу можно переформулировать в терминах задачи дискретной оптимизации. Необходима так сопоставить объектам из множества [math]X[/math] метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение. В качестве примера, стремятся достичь минимума среднего внутрикластерного расстояния [math]F_0 = \dfrac{\sum_{i\lt j}{[y_i=y_j]\cdot\rho(x_i, x_j)}}{\sum_{i\lt j}[y_i=y_j]}[/math] или максимума среднего межкластерного расстояния [math]F_1 = \dfrac{\sum_{i\lt j}{[y_i\neq y_j]\cdot\rho(x_i, x_j)}}{\sum_{i\lt j}[y_i\neq y_j]}[/math].

Подробнее про меры качества можно прочитать в статье оценка качества в задаче кластеризации.

Применение[править]

Биология и биоинформатика[править]

  • В области экологии кластеризация используется для выделения пространственных и временных сообществ организмов в однородных условиях;
  • Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции;
  • Кластеризация помогает автоматически определять генотипы по различным частям хромосом;
  • Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.

Медицина[править]

  • Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении;
  • Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.

Маркетинг[править]

Кластеризация широко используется при изучении рынка для обработки данных, полученных из различных опросов. Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.

Интернет[править]

  • Выделение групп людей на основе графа связей в социальных сетях;
  • Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.

Компьютерные науки[править]

  • Кластеризация используется в сегментации изображений для определения границ и распознавания объектов;
  • Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции;
  • Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;
  • Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.

Псевдокод некоторых алгоритмов кластеризации[править]

Метод K-средних (Алгоритм Ллойда)[править]

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

Алгоритм минимизирует сумму квадратов внутрикластерных расстояний: [math] \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[/math]

На вход алгоритму подаётся выборка [math]X^m = \{ x_1, \dots, x_m \}[/math] и количество кластеров [math]K = |Y|[/math].

На выходе получаем центры кластеров [math]\mu_a[/math] для кластеров [math]a \in Y[/math].

 [math]\mu_a := init(X^m)[/math]  # Инициализируем произвольно начальное приближение для центров кластеров [math]a \in Y[/math]. (Можно наиболее удалённые друг от друга объекты выборки)
 [math]A := [ -1 \: | \: for \: x_i \in X^m ][/math]  # Инициализируем массив отображений из объектов выборки в их кластеры
 [math]changed := True[/math]
 [math]while[/math] [math]changed[/math]:  # Повторяем пока [math]A_i[/math] изменяются
     [math]changed := False[/math]
     [math]for[/math] [math]x_i \in X^m[/math]:  # Относим каждый [math]x_i[/math] к ближайшему центру
         [math]A_{i, old} := A_i[/math]
         [math]A_i := arg \min_{a \in Y} ||x_i - \mu_a||[/math]
         [math]if[/math] [math]A_i \neq A_{i, old}[/math]:
             [math]changed := True[/math]
     [math]for[/math] [math]a \in Y[/math]:  # Вычисляем новые положения центров
         [math]\mu_a := \frac{\sum_{i = 1}^{m}[A_i = a] x_i}{\sum_{i = 1}^{m}[A_i = a]}[/math]
 [math]return[/math] [math]\mu_a, \: A[/math]  # Возвращаем центры кластеров и распределение по ним объектов выборки

DBSCAN[править]

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

На вход алгоритму подаётся набор точек, параметры [math]\epsilon[/math] (радиус окружности) и [math]m[/math] (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.

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

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

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

На выходе получаем разбиение на кластеры и шумовые объекты. Каждый из полученных кластеров [math]C_j[/math] является непустым множеством точек и удовлетворяет двум условиям:

  • Любые две точки в кластере попарно связаны (то есть найдется такая точка в кластере, из которой достижимы обе этих точки).
  • Если точка достижима из какой-либо точки кластера, то она принадлежит кластеру.

Рассмотрим код:

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

 [math]U := X^m[/math]  # Непомеченные объекты
 [math]A := [ -1 \: | \: for \: x_i \in X^m ][/math]  # Инициализируем массив отображений из объектов выборки в их кластеры
 [math]a := 0[/math]  # Количество кластеров
 [math]while[/math] [math]U \neq \varnothing[/math]:  # Пока в выборке есть непомеченные объекты
     [math]x := rand(U)[/math]  # Берём случайную непомеченную точку
     [math]if[/math] [math]|U_{\epsilon}(x) \lt  m|[/math]:
         [math]mark[x][/math] [math]:=[/math] "[math]noise[/math]"  # Пометим [math]x[/math] как, возможно, шумовой
     [math]else[/math]:
         [math]K := U_{\epsilon}(x)[/math]
         [math]a := a + 1[/math] # Создадим новый кластер K
         [math]for[/math] [math]x' \in K[/math]:
             [math]if[/math] [math]x' \in U[/math] || [math]mark[x'][/math] [math]==[/math] "[math]noise[/math]":  # Если [math]x'[/math] не помечен или помечен как шумовой
                 [math]if[/math] [math]|U_{\epsilon}(x')| \geq m[/math]:
                     [math]mark[x'] :=[/math] "[math]interior[/math]"  # Пометим [math]x'[/math] как внутренний кластера [math]K[/math]
                     [math]K := K \cup U_{\epsilon}(x')[/math]  # Добавим вместе с [math]x'[/math] всю его окрестность
                 [math]else[/math]:
                     [math]mark[x'] :=[/math] "[math]frontier[/math]"  # Пометим [math]x'[/math] как граничный кластера [math]K[/math]
         [math]for[/math] [math]x_i \in K[/math]:
             [math]A_i := a[/math]
         [math]U := U \setminus K[/math] 
 [math]return[/math] [math]a, \: A, \: mark[/math]  # Возвращаем количество кластеров, распределение по кластерам и метки объектов (внутренние, граничные или шумовые)

DBSCAN находит практическое применение во многих реальных задачах, например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей — в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, делить их на социальные группы, моделировать поведение посетителей сайта. Алгоритм также может использоваться для сегментации изображений.

Пример кода[править]

Пример на языке R[править]

Основная статья: Примеры кода на R

Для реализации алгоритма k-средних используется пакет ClusterR. В нем реализовано 2 функции: KMeans_arma() и KMeans_rcpp(). В примере далее рассмотрена реализация с использованием функции KMeans_arma().

# importing package and its' dependencies
library(ClusterR)

# reading data
data <- read.csv("data.csv")

# evaluating model
model <- KMeans_arma(data, clusters = 2, n_iter = 10, seed_mode = "random_subset", 
                     verbose = T, CENTROIDS = NULL)

# predicting results
predictions <- predict_KMeans(test_data, model)


См. также[править]

Примечания[править]

  1. scikit-learn — Clustering
  2. Cornwell, B. (2015). Linkage Criteria for Agglomerative Hierarchical Clustering. Social Sequence Analysis, 270–274
  3. 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.
  4. Kleinberg J. An Impossibility Theorem for Clustering
  5. scikit-learn — Comparing different clustering algorithms on toy datasets

Источники информации[править]