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

Материал из Викиконспекты
Перейти к: навигация, поиск
([Major] Hierarchical clustering added)
м
(не показано 17 промежуточных версий 5 участников)
Строка 1: Строка 1:
 +
[[Файл:clusters.png|thumb|300px|Пример кластеризации]]
 
'''Кластеризация''' (англ. ''cluster analysis'') {{---}} задача группировки множества объектов на подмножества ('''кластеры''') таким образом,
 
'''Кластеризация''' (англ. ''cluster analysis'') {{---}} задача группировки множества объектов на подмножества ('''кластеры''') таким образом,
 
чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
 
чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
  
 
Задача кластеризации относится к классу задач обучения без учителя.
 
Задача кластеризации относится к классу задач обучения без учителя.
−
 
 
== Постановка задачи кластеризации ==
 
== Постановка задачи кластеризации ==
 
Пусть <tex>X</tex> {{---}} множество объектов, <tex>Y</tex> {{---}} множество идентификаторов (меток) кластеров.
 
Пусть <tex>X</tex> {{---}} множество объектов, <tex>Y</tex> {{---}} множество идентификаторов (меток) кластеров.
Строка 10: Строка 10:
 
Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту <tex>x_i \in X^m</tex> сопоставить метку <tex>y_i \in Y</tex>,
 
Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту <tex>x_i \in X^m</tex> сопоставить метку <tex>y_i \in Y</tex>,
 
таким образом чтобы объекты внутри каждого кластера были близки относительно метрики <tex>\rho</tex>, а объекты из разных кластеров значительно различались.
 
таким образом чтобы объекты внутри каждого кластера были близки относительно метрики <tex>\rho</tex>, а объекты из разных кластеров значительно различались.
−
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 22: Строка 21:
  
 
Решение задачи кластеризации объективно неоднозначно по ряду причин:
 
Решение задачи кластеризации объективно неоднозначно по ряду причин:
−
* не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.
+
* Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области;
−
* число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<ref>[https://scikit-learn.org/0.20/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>.
−
 
−
== Типология задач кластеризации ==
 
−
=== Типы входных данных ===
 
−
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и нечисловыми.
 
−
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
 
  
−
Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в  
+
Число кластеров фактически является гиперпараметром для алгоритмов кластеризации. Подробнее про другие гиперпараметры и их настройку можно прочитать в статье<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>.
−
зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.
 
  
−
=== Цели кластеризации ===
+
== Теорема невозможности Клейнберга ==
−
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей.
+
Для формализации алгоритмов кластеризации была использована аксиоматическая теория. Клейнберг постулировал три простых свойства в качестве аксиом кластеризации и доказал теорему, связывающую эти свойства.
−
* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием.
+
{{Определение
−
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
+
|definition =
−
 
+
Алгоритм кластеризации <tex>a</tex> является '''масштабно инвариантным''' (англ. ''scale-invariant''), если для любой функции расстояния <tex>\rho</tex> и любой константы <tex>\alpha > 0</tex> результаты кластеризации с использованием расстояний <tex>\rho</tex> и <tex>\alpha\cdot\rho</tex> совпадают.
−
=== Методы кластеризации ===
+
}}
−
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.
+
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
−
* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.
+
{{Определение
−
** Алгоритм <tex>k-</tex>средних (англ. ''<tex>k-</tex>means'')
+
|definition =
−
** EM-алгоритм
+
'''Полнота''' (англ. ''Richness''). Множество результатов кластеризации алгоритма <tex>a</tex> в зависимости от изменения функции расстояния <tex>\rho</tex> должно совпадать со множеством всех возможных разбиений множества объектов <tex>X</tex>.
−
* Иерархические алгоритмы кластеризации. Упорядочивание данных путем создания иерархии вложенных кластеров.
+
}}
−
 
+
Вторая аксиома утверждает, что алгоритм кластеризации должен уметь кластеризовать обучающую выборку на любое фиксированное разбиение для какой-то функции расстояния <tex>\rho</tex>.
−
== Иерархическая кластеризация ==
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
'''Иерархическая кластеризация''' (англ. ''hierarchical clustering'') — множество алгоритмов
+
Функция расстояния <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> лежат в разных кластерах.
 
}}
 
}}
−
Иерархические алгоритмы кластеризации часто называют '''алгоритмами таксономии'''.
+
{{Определение
−
Для визуального представления результатов кластеризации используется '''дендрограмма''' 
+
|definition =
−
{{---}} дерево, построенное по матрице мер близости между кластерами. В узлах дерева находятся подмножества объектов из обучающей выборки.
+
Алгоритм кластеризации является '''согласованным''' (англ. ''consistent''), если результат кластеризации не изменяется после допустимого преобразования функции расстояния.
−
При этом на каждом ярусе дерева множество объектов из всех узлов составляет исходное множество объектов.
+
}}  
−
Объединение узлов между ярусами соответствует слиянию двух кластеров. При этом длина ребра соответствует расстоянию между кластерами.
+
Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.
  
−
Дерево строится от листьев к корню. В начальный момент времени каждый объект содержится в собственном кластере.
+
{| class="wikitable"
−
Далее происходит итеративный процесс слияния двух ближайших кластеров до тех пор, пока все кластеры не объединятся в один или не будет найдено необходимое число кластеров.
+
| style="text-align:center; font-weight:bold;" colspan=3|Примеры преобразований с сохранением кластеров
−
На каждом шаге необходимо уметь вычислять расстояние между кластерами и пересчитывать расстояние между новыми кластерами.
+
|-
−
Расстояние между одноэлементными кластерами определяется через расстояние между объектами: <tex>\mathrm{R}(\{x\}, \{y\}) = \rho(x, y)</tex>.
+
| style="padding:5px;" |[[Файл:cluster_0.png|300px]]
−
Для вычисления расстояния <tex>\mathrm{R}(U, V)</tex> между кластерами <tex>\mathrm{U}</tex> и <tex>\mathrm{V}</tex> на практике используются различные функции в зависимости от специфики задачи.
+
| style="padding:5px;" |[[Файл:clusters_scale_inv.png|300px]]
 +
| style="padding:5px;" |[[Файл:cluster_consist.png|300px]]
 +
|-
 +
| style="text-align:center;width:305px;" | Исходное расположение объектов и их кластеризация
 +
| style="text-align:center;width:305px;" | Пример масштабной инвариантности. Уменьшен масштаб по оси ординат в два раза.
 +
| style="text-align:center;width:305px;" | Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние уменьшилось, межклассовое увеличилось.
 +
|}
  
−
=== Функции расстояния между кластерами ===
 
−
* '''Метод одиночной связи''' (англ. ''single linkage'')
 
−
: <tex>\mathrm{R_{min}}(U, V) = \displaystyle\min_{u \in U, v \in V} \rho(u, v)</tex>
 
−
* '''Метод полной связи''' (англ. ''complete linkage'')
 
−
: <tex>\mathrm{R_{max}}(U, V) = \displaystyle\max_{u \in U, v \in V} \rho(u, v)</tex>
 
−
* '''Метод средней связи''' (англ. ''UPGMA (Unweighted Pair Group Method with Arithmetic mean)'')
 
−
: <tex>\mathrm{R_{avg}}(U, V) = \displaystyle\dfrac{1}{|U| \cdot |V|}\sum_{u \in U} \sum_{v \in V} \rho(u, v)</tex>
 
−
* '''Центроидный метод''' (англ. ''UPGMC (Unweighted Pair Group Method with Centroid average)'')
 
−
: <tex>\mathrm{R_{c}}(U, V) = \displaystyle\rho^2\left(\sum_{u \in U}\dfrac{u}{|U|}, \sum_{v \in V}\dfrac{v}{|V|}\right)</tex>
 
−
* '''Метод Уорда''' (англ. ''Ward's method'')
 
−
: <tex>\mathrm{R_{ward}}(U, V) = \displaystyle\dfrac{|U| \cdot |V|}{|U| + |V|}\rho^2\left(\sum_{u \in U}\dfrac{u}{|U|}, \sum_{v \in V}\dfrac{v}{|V|}\right)</tex>
 
  
−
=== Формула Ланса-Уильямса ===
+
Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:
−
На каждом шаге необходимо уметь быстро подсчитывать расстояние от образовавшегося кластера <tex>\mathrm{W}=\mathrm{U}\cup\mathrm{V}</tex> до любого другого кластера <tex>\mathrm{S}</tex>, используя известные расстояния с предыдущих шагов.
+
{{Теорема
−
Это легко выполняется при использовании формулы, предложенной Лансом и Уильямсом в 1967 году:
+
|author=Клейнберга
−
<center><tex>\mathrm{R}(W, S) = \alpha_U \cdot \mathrm{R}(U, S) + \alpha_V \cdot \mathrm{R}(V, S) + \beta \cdot \mathrm{R}(U, V) + \gamma \cdot |\mathrm{R}(U, S) - \mathrm{R}(V, S)| </tex></center>
+
|about=о невозможности
−
, где <tex>\alpha_U, \alpha_V, \beta, \gamma </tex> {{---}} числовые параметры.
+
|statement=Для множества объектов, состоящего из двух и более элементов, не существует алгоритма кластеризации, который был бы одновременно масштабно-инвариантным, согласованным и полным.
 +
}}
 +
Несмотря на эту теорему Клейнберг показал<ref>[https://www.cs.cornell.edu/home/kleinber/nips15.pdf Kleinberg J. An Impossibility Theorem for Clustering]</ref>,
 +
что иерархическая кластеризация по методу одиночной связи с различными критериями останова удовлетворяет любым двум из трех аксиом.
  
−
Каждая из указанных выше функций расстояния удовлетворяет формуле Ланса-Уильямса со следующими коэффициентами:
+
== Типология задач кластеризации ==
−
* '''Метод одиночной связи''' (англ. ''single linkage'')
+
=== Типы входных данных ===
−
: <tex>\alpha_U = \dfrac{1}{2}, \alpha_V = \dfrac{1}{2}, \beta = 0, \gamma = -\dfrac{1}{2}</tex>
+
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и категориальными;
−
* '''Метод полной связи''' (англ. ''complete linkage'')
+
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
−
: <tex>\alpha_U = \dfrac{1}{2}, \alpha_V = \dfrac{1}{2}, \beta = 0, \gamma = \dfrac{1}{2} </tex>
 
−
* '''Метод средней связи''' (англ. ''UPGMA (Unweighted Pair Group Method with Arithmetic mean)'')
 
−
: <tex>\alpha_U = \dfrac{|U|}{|W|}, \alpha_V = \dfrac{|V|}{|W|}, \beta = 0, \gamma = 0 </tex>
 
−
* '''Центроидный метод''' (англ. ''UPGMC (Unweighted Pair Group Method with Centroid average)'')
 
−
: <tex>\alpha_U = \dfrac{|U|}{|W|}, \alpha_V = \dfrac{|V|}{|W|}, \beta = -\alpha_U \cdot \alpha_V, \gamma = 0</tex>
 
−
* '''Метод Уорда''' (англ. ''Ward's method'')
 
−
: <tex>\alpha_U = \dfrac{|S|+|U|}{|S|+|W|}, \alpha_V = \dfrac{|S|+|V|}{|S|+|W|}, \beta = \dfrac{-|S|}{|S|+|W|}, \gamma = 0 </tex>
 
  
−
=== Свойство монотонности ===
+
Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в
−
Введем обозначение <tex>\mathrm{R_t}</tex> {{---}} расстояние между кластерами, выбранными на шаге <tex>t</tex> для объединения.
+
зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.
  
−
Дендрограмма позволяет представлять зависимости между множеством объектов с любым числом заданных характеристик
+
=== Цели кластеризации ===
−
на двумерном графике, где по одной из осей откладываются все объекты, а по другой {{---}} расстояние <tex>\mathrm{R_t}</tex>.
+
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей;
−
Если не накладывать на это расстояние никаких ограничений, то дендрограмма будет иметь большое число самопересечений и изображение перестанет быть наглядным.
+
* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием;
−
Чтобы любой кластер мог быть представлен в виде непрерывного отрезка на оси объектов и ребра не пересекались,
+
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
−
необходимо наложить ограничение монотонности на <tex>\mathrm{R_t}</tex>.
 
  
−
{{Определение
+
=== Методы кластеризации ===
−
|definition =
+
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике;
−
Функция расстояния <tex>\mathrm{R}</tex> является '''монотонной''', если на каждом следующем шаге расстояние между кластерами не уменьшается:
+
* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности:
−
<tex>\mathrm{R_2} \leqslant \mathrm{R_3} \leqslant \dots \leqslant \mathrm{R_m}</tex>
+
** [[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''). Алгоритм группирует в один кластер точки в области с высокой плотностью. Одиноко расположенные точки помечает как шум.
  
−
{{Теорема
 
−
|author=Миллиган, 1979
 
−
|statement=Если выполняются следующие три условия, то кластеризация является монотонной:
 
−
# <tex>\alpha_U \geqslant 0, \alpha_V \geqslant 0 </tex>;
 
−
# <tex>\alpha_U + \alpha_V + \beta \geqslant 1</tex>;
 
−
# <tex>\min\{\alpha_U, \alpha_V\} + \gamma \geqslant 0 </tex>.
 
−
}}
 
  
−
Из перечисленных выше расстояний теореме удовлетворяют все, кроме центроидного.
+
[[Файл: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>]]
  
−
=== Определение числа кластеров ===
+
== Меры качества кластеризации ==
−
Для определения числа кластеров находится интервал максимальной длины <tex>|\mathrm{R_{t+1}} - \mathrm{R_t}|</tex>.
+
Для оценки качества кластеризации задачу можно переформулировать в терминах задачи дискретной оптимизации.
−
В качестве итоговых кластеров выдаются кластеры, полученные на шаге <tex>\mathrm{t}</tex>.
+
Необходима так сопоставить объектам из множества <tex>X</tex> метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение.  
−
При этом число кластеров равно <tex>m - t + 1</tex>.
+
В качестве примера, стремятся достичь минимума среднего внутрикластерного расстояния <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>.
  
−
Однако, когда число кластеров заранее неизвестно и объектов в выборке не очень много, бывает полезно изучить дендрограмму целиком.
+
Подробнее про меры качества можно прочитать в статье [[Оценка_качества_в_задаче_кластеризации|оценка качества в задаче кластеризации]].
  
−
=== Псевдокод ===
+
== Применение ==
−
<font color=darkgreen>// алгоритм принимает множество объектов и возвращает множество кластеров для каждого шага </font>
+
=== Биология и биоинформатика ===
−
'''function''' hierarchy(X: '''Set<Object>'''): '''Set<Set<Object>>'''
+
* В области экологии кластеризация используется для выделения пространственных и временных сообществ организмов в однородных условиях;
−
  t = 1
+
* Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции;
−
  <tex>\mathrm{C_t} = {{x_1}, \dots, {x_m}}</tex>
+
* Кластеризация помогает автоматически определять генотипы по различным частям хромосом;
−
  '''for''' i = 2 '''to''' m
+
* Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.
−
      <tex>\langle U, V \rangle = \displaystyle \arg \min_{U \neq V, U \in C_{i-1}, V \in C_{i-1}} R(U, V)</tex>
+
=== Медицина ===
−
      <tex>\mathrm{R_{t}} = \mathrm{R}(U, V)</tex>
+
* Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении;
−
      <tex>\mathrm{C_{i}} = \mathrm{C_{i-1}} \cup \{\mathrm{W}\} \setminus \{\mathrm{U}, \mathrm{V}\}</tex>
+
* Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.
−
      '''for''' <tex> S </tex> '''in''' <tex> C_t </tex>
+
=== Маркетинг ===
−
          <tex>\mathrm{R_{i}}(W, S) = \alpha_U \cdot \mathrm{R_{i-1}}(U, S) + \alpha_V \cdot \mathrm{R_{i-1}}(V, S) + \beta \cdot \mathrm{R_{i-1}}(U, V) + \gamma \cdot |\mathrm{R_{i-1}}(U, S) - \mathrm{R{i-1}}(V, S)| </tex>
+
Кластеризация широко используется при изучении рынка для обработки данных, полученных из различных опросов.
−
  '''return''' <tex> C </tex>
+
Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
−
 
+
=== Интернет ===
−
=== Пример ===
+
* Выделение групп людей на основе графа связей в социальных сетях;
−
<font color=darkgreen># Подключение библиотек</font>
+
* Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.
−
from scipy.cluster.hierarchy import linkage, dendrogram
+
=== Компьютерные науки ===
−
from sklearn import datasets
+
* Кластеризация используется в сегментации изображений для определения границ и распознавания объектов;
−
import matplotlib.pyplot as plt
+
* Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции;
−
<tex></tex>
+
* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;
−
<font color=darkgreen># Создание полотна для рисования</font>
+
* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
−
fig = plt.figure(figsize=(15, 30))
 
−
fig.patch.set_facecolor('white')
 
−
<tex></tex>
 
−
<font color=darkgreen># Загрузка набора данных "Ирисы Фишера"</font>
 
−
iris = datasets.load_iris()
 
−
<tex></tex>
 
−
<font color=darkgreen># Реализация иерархической кластеризации при помощи функции linkage</font>
 
−
mergings = linkage(iris.data, method='ward')
 
−
<tex></tex>
 
−
<font color=darkgreen># Построение дендрограммы. Разными цветами выделены автоматически определенные кластеры</font>
 
−
R = dendrogram(mergings, labels=[iris.target_names[i] for i in iris.target], orientation = 'left', leaf_font_size = 12)
 
−
<tex></tex>
 
−
<font color=darkgreen># Отображение дендрограммы</font>
 
−
plt.show()
 
−
 
 
−
{| class="wikitable"
 
−
| style="text-align:center;" colspan = 4 |Дендрограммы кластеризации ирисов Фишера<ref>[https://ru.wikipedia.org/wiki/%D0%98%D1%80%D0%B8%D1%81%D1%8B_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0 Википедия {{---}} Ирисы Фишера]</ref> в зависимости от функции расстояния между кластерами
 
−
|-
 
−
| style="padding:5px;" |[[Файл:hierarchy_min.png|270px|Расстояние минимума.]]
 
−
| style="padding:5px;" |[[Файл:hierarchy_max.png|270px|Расстояние максимума.]]
 
−
| style="padding:5px;" |[[Файл:hierarchy_avg.png|270px|Расстояние среднего.]]
 
−
| style="padding:5px;" |[[Файл:hierarchy_ward.png|270px|Расстояние Уорда.]]
 
−
|-
 
−
| style="text-align:center;" | Метод одиночной связи
 
−
| style="text-align:center;" | Метод полной связи
 
−
| style="text-align:center;" | Метод средней связи
 
−
| style="text-align:center;" | Метод Уорда
 
−
|}
 
  
−
Лучше всего с задачей справился алгоритм с использованием расстояния Уорда. Он точно выделил класс ''Iris setosa'' и заметно отделили вид ''Iris virginica'' от ''Iris versicolor''.
+
== См. также ==
 +
* [[Оценка_качества_в_задаче_кластеризации|Оценка качества в задаче кластеризации]]
 +
* [[EM-алгоритм|EM-алгоритм]]
 +
* [[Иерархическая_кластеризация|Иерархическая кластеризация]]
 +
* [[k-средних|<tex>\mathrm{k}</tex>-средних]]<sup>[на 28.01.18 не создан]</sup>
  
 
== Примечания ==
 
== Примечания ==
Строка 187: Строка 142:
 
* [https://en.wikipedia.org/wiki/Cluster_analysis Wikipedia {{---}} Cluster analysis]
 
* [https://en.wikipedia.org/wiki/Cluster_analysis Wikipedia {{---}} Cluster analysis]
 
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F MachineLearning {{---}} Кластеризация]  
 
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F MachineLearning {{---}} Кластеризация]  
−
* [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F Википедия {{---}} Иерархическая кластеризация]
 
−
* [https://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html Scipy Documentation {{---}} Hierarchical clustering (scipy.cluster.hierarchy)]
 
 
* [http://www.machinelearning.ru/wiki/images/c/ca/Voron-ML-Clustering.pdf К.В.Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования]
 
* [http://www.machinelearning.ru/wiki/images/c/ca/Voron-ML-Clustering.pdf К.В.Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования]
−
* G. N. Lance, W. T. Williams; A General Theory of Classificatory Sorting Strategies: 1. Hierarchical Systems, The Computer Journal, Volume 9, Issue 4, 1 February 1967, Pages 373–380
+
* [https://www.cs.cornell.edu/home/kleinber/nips15.pdf Kleinberg J. An Impossibility Theorem for Clustering]
  
 
[[Категория: Машинное обучение]]
 
[[Категория: Машинное обучение]]
 +
[[Категория: Кластеризация]]

Версия 13:37, 7 июня 2019

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

Кластеризация (англ. 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].

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

Применение

Биология и биоинформатика

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

Медицина

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

Маркетинг

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

Интернет

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

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

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

См. также

Примечания

  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

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Кластеризация&oldid=71641»