Изменения

* не Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.;* число Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<ref>[https://scikit-learn.org/0.20stable/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>. == Теорема невозможности Клейнберга ==Для формализации алгоритмов кластеризации была использована аксиоматическая теория. Клейнберг постулировал три простых свойства в качестве аксиом кластеризации и доказал теорему, связывающую эти свойства.{{Определение|definition =Алгоритм кластеризации <tex>a</tex> является '''масштабно инвариантным''' (англ. ''scale-invariant''), если для любой функции расстояния <tex>\rho</tex> и любой константы <tex>\alpha > 0</tex> результаты кластеризации с использованием расстояний <tex>\rho</tex> и <tex>\alpha\cdot\rho</tex> совпадают.}} Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.{{Определение|definition ='''Полнота''' (англ. ''Richness''). Множество результатов кластеризации алгоритма <tex>a</tex> в зависимости от изменения функции расстояния <tex>\rho</tex> должно совпадать со множеством всех возможных разбиений множества объектов <tex>X</tex>.}} Вторая аксиома утверждает, что алгоритм кластеризации должен уметь кластеризовать обучающую выборку на любое фиксированное разбиение для какой-то функции расстояния <tex>\rho</tex>.{{Определение|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> лежат в разных кластерах.}}{{Определение|definition =Алгоритм кластеризации является '''согласованным''' (англ. ''consistent''), если результат кластеризации не изменяется после допустимого преобразования функции расстояния.}} Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния. {| class="wikitable"| style="text-align:center; font-weight:bold;" colspan=3|Примеры преобразований с сохранением кластеров|-| style="padding:5px;" |[[Файл:cluster_0.png|300px]]| 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;" | Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние уменьшилось, межклассовое увеличилось.|}  Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:{{Теорема|author=Клейнберга|about=о невозможности|statement=Для множества объектов, состоящего из двух и более элементов, не существует алгоритма кластеризации, который был бы одновременно масштабно-инвариантным, согласованным и полным.}}Несмотря на эту теорему Клейнберг показал<ref>[https://www.cs.cornell.edu/home/kleinber/nips15.pdf Kleinberg J. An Impossibility Theorem for Clustering]</ref>, что иерархическая кластеризация по методу одиночной связи с различными критериями останова удовлетворяет любым двум из трех аксиом.

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

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

* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.;* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности:** [[EM-алгоритм]];* [[Иерархическая_кластеризация|Иерархические алгоритмы кластеризации]].Упорядочивание данных путем создания иерархии вложенных кластеров;** [[K-средних|Алгоритм <tex>\mathrm{k-}</tex>-средних ]]^{[на 28.01.19 не создан]} (англ. ''<tex>\mathrm{k-}</tex>-means''). Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров;* Распространение похожести (англ. ''affinity propagation''). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера;*Сдвиг среднего значения (англ. ''mean shift''). Выбирает центроиды кластеров в областях с наибольшей плотностью;* Спектральная кластеризация (англ. ''spectral clustering''). Использует собственные значения матрицы расстояний для понижения размерности перед использованием других методов кластеризации;* EMОснованная на плотности пространственная кластеризация для приложений с шумами (англ. ''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>]] == Меры качества кластеризации ==* Иерархические алгоритмы Для оценки качества кластеризациизадачу можно переформулировать в терминах задачи дискретной оптимизации. Упорядочивание данных путем создания иерархии вложенных Необходимо так сопоставить объектам из множества <tex>X</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>.

Подробнее про меры качества можно прочитать в статье [[Оценка_качества_в_задаче_кластеризации|оценка качества в задаче кластеризации]]. == Иерархическая кластеризация Применение =={{Определение|definition === Биология и биоинформатика ==='''Иерархическая * В области экологии кластеризация''' (англиспользуется для выделения пространственных и временных сообществ организмов в однородных условиях;* Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции;* Кластеризация помогает автоматически определять генотипы по различным частям хромосом;* Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома. ''hierarchical clustering'') — множество алгоритмов кластеризации, направленных === Медицина ===* Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на создание иерархии вложенных разбиений исходного множества объектовтрехмерном изображении;* Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.}}=== Маркетинг ===Кластеризация широко используется при изучении рынка для обработки данных, полученных из различных опросов.Иерархические алгоритмы кластеризации часто называют '''алгоритмами таксономии'''Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.Для визуального представления результатов кластеризации используется '''дендрограмма''' === Интернет ===* Выделение групп людей на основе графа связей в социальных сетях;{{* Повышение релевантности ответов на поисковые запросы путем группировки веб---}} дерево, построенное сайтов по матрице мер близости между кластерамисмысловым значениям поискового запроса. В узлах дерева находятся подмножества === Компьютерные науки ===* Кластеризация используется в сегментации изображений для определения границ и распознавания объектов из обучающей выборки.;* Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции;При этом * Подбор рекомендаций для пользователя на каждом ярусе дерева множество объектов из всех узлов составляет исходное множество основе предпочтений других пользователей в данном кластере;* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.Объединение узлов между ярусами соответствует слиянию двух кластеров== Псевдокод некоторых алгоритмов кластеризации ===== Метод 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 = \mathrm{R}(\{x\}x_1, \{y\}) = \rho(xdots, y)</tex>.Для вычисления расстояния <tex>x_m \mathrm{R}(U, V)</tex> между кластерами <tex>\mathrm{U}</tex> и количество кластеров <tex>\mathrm{V}K = |Y|</tex> на практике используются различные функции в зависимости от специфики задачи.

=== Функции расстояния между кластерами ===* '''Метод одиночной связи''' (англ. ''single linkage''): На выходе получаем центры кластеров <tex>\mathrm{R_{min}}(U, V) = \displaystyle\min_{u \in U, v \in V} \rho(u, v)mu_a</tex>* '''Метод полной связи''' (англ. ''complete linkage''): для кластеров <tex>\mathrm{R_{max}}(U, V) = \displaystyle\max_{u a \in U, v \in V} \rho(u, v)Y</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>\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 \mathrmin X^m</tex>: <font color="gray"># Относим каждый <tex>x_i</tex> к ближайшему центру</font> <tex>A_{Wi, old}:= A_i</tex> <tex>A_i :=arg \mathrmmin_{Ua \in Y}||x_i - \cup\mathrm{V}mu_a||</tex> <font color="blue"><tex>if</tex> до любого другого кластера </font> <tex>A_i \mathrmneq A_{Si, old}</tex>, используя известные расстояния с предыдущих шагов.:Это легко выполняется при использовании формулы, предложенной Лансом и Уильямсом в 1967 году <tex>changed := True</tex> <font color="blue"><tex>for</tex><center/font><tex>a \mathrm{R}(W, S) in Y</tex>: <font color= "gray"># Вычисляем новые положения центров</font> <tex>\alpha_U mu_a := \cdot frac{\mathrmsum_{Ri = 1}(U, S) + \alpha_V \cdot \mathrm^{Rm}(V, S) + \beta [A_i = a] x_i}{\cdot \mathrmsum_{Ri = 1}(U, V) + \gamma \cdot |\mathrm^{Rm}(U, S) - \mathrm{R[A_i = a]}(V, S)| </tex> <font color="blue"><tex>return</tex></centerfont>, где <tex>\alpha_Umu_a, \alpha_V, \beta, \gamma : A</tex> {{---}} числовые параметры. <font color="gray"># Возвращаем центры кластеров и распределение по ним объектов выборки</font>

Каждая из указанных выше функций расстояния удовлетворяет формуле Ланса-Уильямса со следующими коэффициентами:* '''Метод одиночной связи''' (англ. ''single linkage''): <tex>\alpha_U = \dfrac{1}{2}, \alpha_V = \dfrac{1}{2}, \beta = 0, \gamma DBSCAN = -\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>\epsilon</tex> (радиус окружности) и <tex>m</tex> (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые. Введем обозначение * Точка является ''основной'', если в окружности с центром в этой точке и радиусом <tex>\mathrmepsilon</tex> находится как минимум <tex>m</tex> точек. * Точка <tex>a</tex> является ''прямо достижимой'' из основной точки <tex>b</tex>, если <tex>a</tex> находится на расстоянии, не большем <tex>{R_t\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>tp_i</tex> для объединения.* Все остальные точки, которые не достижимы из основных точек, считаются ''шумовыми''.

Дендрограмма позволяет представлять зависимости между множеством объектов с любым числом заданных характеристикна двумерном графике, где по одной Основная точка вместе со всеми достижимыми из осей откладываются все объекты, а по другой {{---}} расстояние <tex>\mathrm{R_t}</tex>нее точками формирует ''кластер''.Если не накладывать на это расстояние никаких ограниченийВ кластер будут входить как основные, то дендрограмма будет иметь большое число самопересечений так и изображение перестанет быть нагляднымнеосновные точки.Чтобы любой Таким образом, каждый кластер мог быть представлен в виде непрерывного отрезка на оси объектов и ребра не пересекались,необходимо наложить ограничение монотонности на <tex>\mathrm{R_t}</tex>содержит по меньшей мере одну основную точку.

{{Определение|definition =Функция расстояния Алгоритм начинается с произвольной точки из набора, которая еще не просматривалась. Для точки ищется <tex>{\mathrm{Repsilon}</tex> -окрестность. Если она не содержит как минимум <tex>m</tex> точек, то помечается как шумовая, иначе образуется кластер <tex>K</tex>, который включает все точки из окрестности. Если точка из окрестности уже является '''монотонной'''частью другого кластера <tex>C_j</tex>, если на каждом следующем шаге расстояние между кластерами не уменьшается:то все точки данного кластера добавляются в кластер <tex>\mathrm{R_2} \leqslant \mathrm{R_3} \leqslant \dots \leqslant \mathrm{R_m}K</tex>}}. Затем выбирается и обрабатывается новая, не посещённая ранее точка, что ведёт к обнаружению следующего кластера или шума.

Расстояние На выходе получаем разбиение на кластеры и шумовые объекты. Каждый из полученных кластеров <tex>C_j</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>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_{\mathrmepsilon}(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_{R_{t\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' \mathrmin 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_{R_t\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 \mathrmcup U_{t\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>m - t + 1a, \: A, \: mark</tex>. <font color="gray"># Возвращаем количество кластеров, распределение по кластерам и метки объектов (внутренние, граничные или шумовые)</font>

ОднакоDBSCAN находит практическое применение во многих реальных задачах, когда число кластеров заранее неизвестно например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей {{---}} в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и объектов в выборке не очень многонаходить общие интересы людей, делить их на социальные группы, бывает полезно изучить дендрограмму целикоммоделировать поведение посетителей сайта. Алгоритм также может использоваться для [[Сегментация изображений|сегментации изображений]].

==Пример кода = Псевдокод === <font color=darkgreen>// алгоритм принимает множество объектов и возвращает множество кластеров для каждого шага </font> '''function''' hierarchy(X: '''Set<Object>'''): '''Set<Set<Object>>''' t Пример на языке R = 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}} Main|Примеры кода на 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'k-средних'' используется пакет <texcode> S ClusterR</texcode> '''in''' . В нем реализовано 2 функции: <texcode> C_t KMeans_arma()</texcode> и <texcode>\mathrm{R_{i}}KMeans_rcpp(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)| </texcode> '''return''' . В примере далее рассмотрена реализация с использованием функции <texcode> C KMeans_arma()</texcode>.

=== Пример === <font color=darkgreen"gray"># Подключение библиотекimporting package and its' dependencies</font> from scipy.cluster.hierarchy import linkage, dendrogram from sklearn import datasetslibrary(ClusterR) import matplotlib.pyplot as plt <texfont color="gray"># reading data</texfont> data <- read.csv(<font color=darkgreen"green"># Создание полотна для рисования"data.csv"</font> fig = plt.figure(figsize=(15, 30)) fig.patch.set_facecolor('white') <texfont color="gray"># evaluating model</texfont> model <- KMeans_arma(data, <font color=darkgreen>"# Загрузка набора данных "Ирисы Фишера660099">clusters</font> iris = datasets.load_iris() <texfont color="blue">2</texfont> , <font color=darkgreen"#660099"># Реализация иерархической кластеризации при помощи функции linkagen_iter</font> mergings = linkage(iris.data<font color="blue">10</font>, method<font color='ward') "#660099">seed_mode<tex/font>= <font color="green">"random_subset"</texfont>, <font color=darkgreen"#660099"># Построение дендрограммы. Разными цветами выделены автоматически определенные кластерыverbose</font> R = dendrogram(mergingsT, labels<font color=[iris.target_names[i] for i in iris.target], orientation = 'left', leaf_font_size "#660099">CENTROIDS</font> = 12NULL) <tex></tex> <font color=darkgreen"gray"># Отображение дендрограммыpredicting results</font> plt.showpredictions <- predict_KMeans(test_data, model)

Лучше всего с задачей справился == См. также ==* [[Оценка_качества_в_задаче_кластеризации|Оценка качества в задаче кластеризации]]* [[EM-алгоритм|EM-алгоритм с использованием расстояния Уорда]]* [[Иерархическая_кластеризация|Иерархическая кластеризация]]* [[k-средних|<tex>\mathrm{k}</tex>-средних]]^{[на 28. Он точно выделил класс ''Iris setosa'' и заметно отделили вид ''Iris virginica'' от ''Iris versicolor''01.18 не создан]}

* G[https://www. Ncs. Lance, Wcornell. Tedu/home/kleinber/nips15. Williams; A General Theory of Classificatory Sorting Strategies: 1pdf Kleinberg J. Hierarchical Systems, The Computer Journal, Volume 9, Issue 4, 1 February 1967, Pages 373–380An Impossibility Theorem for Clustering]