* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.
* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.
** EM-алгоритм<ref>[http://neerc.ifmo.ru/wiki/index.php?title=EM-алгоритм EM-алгоритм]</ref>
* Иерархические алгоритмы кластеризации. Упорядочивание данных путем создания иерархии вложенных кластеров.
* Алгоритм <tex>\mathrm{k}</tex>-средних (англ. ''<tex>\mathrm{k}</tex>-means'')<ref>[http://neerc.ifmo.ru/wiki/index.php?title=K-средних <tex>\mathrm{k}</tex>-средних]</ref>. Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров.
* Распространение похожести (англ. ''affinity propagation''). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера.
* Сдвиг среднего значения (англ. ''mean shift''). Выбирает центроиды кластеров в областях с наибольшей плотностью.
* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере.
* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
== Иерархическая кластеризация ==
{{Определение
|definition =
'''Иерархическая кластеризация''' (англ. ''hierarchical clustering'') — множество алгоритмов
кластеризации, направленных на создание иерархии вложенных разбиений исходного множества объектов.
}}
Иерархические алгоритмы кластеризации часто называют '''алгоритмами таксономии'''.
Для визуального представления результатов кластеризации используется '''дендрограмма'''
{{---}} дерево, построенное по матрице мер близости между кластерами. В узлах дерева находятся подмножества объектов из обучающей выборки.
При этом на каждом ярусе дерева множество объектов из всех узлов составляет исходное множество объектов.
Объединение узлов между ярусами соответствует слиянию двух кластеров. При этом длина ребра соответствует расстоянию между кластерами.
Дерево строится от листьев к корню. В начальный момент времени каждый объект содержится в собственном кластере.
Далее происходит итеративный процесс слияния двух ближайших кластеров до тех пор, пока все кластеры не объединятся в один или не будет найдено необходимое число кластеров.
На каждом шаге необходимо уметь вычислять расстояние между кластерами и пересчитывать расстояние между новыми кластерами.
Расстояние между одноэлементными кластерами определяется через расстояние между объектами: <tex>\mathrm{R}(\{x\}, \{y\}) = \rho(x, y)</tex>.
Для вычисления расстояния <tex>\mathrm{R}(U, V)</tex> между кластерами <tex>\mathrm{U}</tex> и <tex>\mathrm{V}</tex> на практике используются различные функции в зависимости от специфики задачи.
=== Функции расстояния между кластерами ===
* '''Метод одиночной связи''' (англ. ''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 году:
<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>
, где <tex>\alpha_U, \alpha_V, \beta, \gamma </tex> {{---}} числовые параметры.
Каждая из указанных выше функций расстояния удовлетворяет формуле Ланса-Уильямса со следующими коэффициентами:
* '''Метод одиночной связи''' (англ. ''single linkage'')
: <tex>\alpha_U = \dfrac{1}{2}, \alpha_V = \dfrac{1}{2}, \beta = 0, \gamma = -\dfrac{1}{2}</tex>
* '''Метод полной связи''' (англ. ''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>
}}
Расстояние является монотонным, если для коэффициентов в формул Ланса-Уильямса верна теорема Миллигана.
{{Теорема
|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>.
}}
Из перечисленных выше расстояний теореме удовлетворяют все, кроме центроидного.
=== Определение числа кластеров ===
Для определения числа кластеров находится интервал максимальной длины <tex>|\mathrm{R_{t+1}} - \mathrm{R_t}|</tex>.
В качестве итоговых кластеров выдаются кластеры, полученные на шаге <tex>\mathrm{t}</tex>.
При этом число кластеров равно <tex>m - t + 1</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; font-weight:bold;" 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|350px|Расстояние минимума.]]
| style="padding:5px;" |[[Файл:hierarchy_max.png|350px|Расстояние максимума.]]
|-
| style="text-align:center;" | Метод одиночной связи
| style="text-align:center;" | Метод полной связи
|-
| style="padding:5px;" |[[Файл:hierarchy_avg.png|350px|Расстояние среднего.]]
| style="padding:5px;" |[[Файл:hierarchy_ward.png|350px|Расстояние Уорда.]]
|-
| style="text-align:center;" | Метод средней связи
| style="text-align:center;" | Метод Уорда
|}
Лучше всего с задачей справился алгоритм с использованием расстояния Уорда. Он точно выделил класс ''Iris setosa'' и заметно отделил вид ''Iris virginica'' от ''Iris versicolor''.
== См. также ==
* [[Оценка_качества_в_задаче_кластеризации|Оценка качества в задаче кластеризации]]<sup>[на 1428.12.18 не создан]</sup>* [[EM-алгоритм|EM-алгоритм]]<sup>[на 1428.12.18 не создан]</sup>* [[k-средних|<tex>\mathrm{k}</tex>-средних]]<sup>[на 28.12.18 не создан]</sup>
== Примечания ==
* [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 {{---}} Кластеризация]
* [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 К.В.Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования]
* 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
[[Категория: Машинное обучение]]
[[Категория: Кластеризация]]
