Изменения

[[Файл:clusterclusters.png|thumb|300px|Пример кластеризации. Красным цветом выделены неклассифицированные объекты.]]

* не Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.;* число Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<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''). Выбирает центроиды кластеров в областях с наибольшей плотностью;* EMСпектральная кластеризация (англ. ''spectral clustering''). Использует собственные значения матрицы расстояний для понижения размерности перед использованием других методов кластеризации;* Основанная на плотности пространственная кластеризация для приложений с шумами (англ. ''Density-based spatial clustering of applications with noise'', ''DBSCAN''). Алгоритм группирует в один кластер точки в области с высокой плотностью. Одиноко расположенные точки помечает как шум.  [[Файл:cluster_comparison.png|thumb|800px|center|<div style="text-align:center">Сравнение алгоритмов кластеризации из пакета scikit-learn<ref>[https://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html scikit-learn {{---алгоритм}} Comparing different clustering algorithms on toy datasets]</ref></div>]] == Меры качества кластеризации ==* Иерархические алгоритмы Для оценки качества кластеризациизадачу можно переформулировать в терминах задачи дискретной оптимизации. Упорядочивание данных путем создания иерархии вложенных Необходима так сопоставить объектам из множества <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 ='''Иерархическая кластеризация''' == Метод K-средних (англ. ''hierarchical clustering''Алгоритм Ллойда) — множество алгоритмов ===кластеризации, направленных на создание иерархии вложенных разбиений исходного множества объектов.Алгоритм минимизирует сумму квадратов внутрикластерных расстояний:<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>\mathrm{R}(\{x\}, \{y\}) = \rho(x, y)mu_a</tex>.Для вычисления расстояния <tex>\mathrm{R}(U, V)</tex> между кластерами <tex>\mathrm{U}</tex> и для кластеров <tex>a \mathrm{V}in Y</tex> на практике используются различные функции в зависимости от специфики задачи.

<tex>\mu_a :=== Функции расстояния между кластерами ===* '''Метод одиночной связи''' init(англ. ''single linkage''X^m): </tex> <font color="gray"># Инициализируем произвольно начальное приближение для центров кластеров <tex>a \mathrm{R_{min}}in Y</tex></font>. (U, VМожно наиболее удалённые друг от друга объекты выборки) <tex>A := [ -1 \displaystyle: | \min_{u : for \in U, v : x_i \in V} \rho(u, v)X^m ]</tex> <font color="gray"># Инициализируем массив отображений из объектов выборки в их кластеры</font> <tex>changed := True</tex>* '''Метод полной связи''' (англ. ''complete linkage'') <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 \mathrm{R_{max}}(U, V) in X^m</tex>: <font color= \displaystyle\max_"gray"># Относим каждый <tex>x_i</tex> к ближайшему центру</font> <tex>A_{u \in Ui, v \in Vold} \rho(u, v):= A_i</tex>* '''Метод средней связи''' (англ. ''UPGMA (Unweighted Pair Group Method with Arithmetic mean)''): <tex>A_i := arg \mathrmmin_{R_{avg}}(U, V) = a \displaystyle\dfrac{1in Y}{|U| x_i - \cdot mu_a|V|}</tex> <font color="blue"><tex>if</tex></font> <tex>A_i \sum_neq A_{u \in U} \sum_{v \in Vi, old} \rho(u, v)</tex>:* '''Центроидный метод''' (англ. ''UPGMC (Unweighted Pair Group Method with Centroid average)'') <tex>changed : = True</tex>\mathrm{R_{c}}(U, V) <font color= \displaystyle\rho^2\left(\sum_{u \in U}\dfrac{u}{|U|}, \sum_{v "blue"><tex>for</tex></font> <tex>a \in V}\dfrac{v}{|V|}\right)Y</tex>: <font color="gray"># Вычисляем новые положения центров</font>* '''Метод Уорда''' (англ. ''Ward's method''): <tex>\mathrm{R_{ward}}(U, V) mu_a := \displaystyle\dfracfrac{|U| \cdot |V|}sum_{|U| + |V|i = 1}\rho^2\left(\sum_{u \in Um}\dfrac{u[A_i = a] x_i}{|U|}, \sum_{v \in Vi = 1}\dfrac^{vm}{|V|[A_i = a]}</tex> <font color="blue"><tex>return</tex></font> <tex>\mu_a, \right): A</tex> <font color="gray"># Возвращаем центры кластеров и распределение по ним объектов выборки</font>

=== Формула Ланса-Уильямса DBSCAN ===На каждом шаге необходимо уметь быстро подсчитывать расстояние от образовавшегося кластера <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> {{---}} числовые параметрыбудут помечены как шумовые.

Каждая из указанных выше функций расстояния удовлетворяет формуле Ланса-Уильямса со следующими коэффициентамиНа вход алгоритму подаётся набор точек, параметры <tex>\epsilon</tex> (радиус окружности) и <tex>m</tex> (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида:основные точки, прямо достижимые, достижимые и шумовые. * Точка является ''основной'Метод одиночной связи''' (англ. ''single linkage''): , если в окружности с центром в этой точке и радиусом <tex>\alpha_U = \dfrac{1}{2}, \alpha_V = \dfrac{1}{2}, \beta = 0, \gamma = -\dfrac{1}{2}epsilon</tex> находится как минимум <tex>m</tex>точек. * Точка <tex>a</tex> является ''прямо достижимой'Метод полной связи''' (англ. ''complete linkage''): из основной точки <tex>b</tex>, если <tex>a</tex>\alpha_U = \dfrac{1}{2}находится на расстоянии, \alpha_V = \dfracне большем <tex>{1}{2}, \beta = 0, \gamma = \dfrac{1}{2epsilon} </tex>от точки <tex>b</tex>.* Точка <tex>a</tex> является ''достижимой'Метод средней связи''' (англ. ''UPGMA (Unweighted Pair Group Method with Arithmetic mean)''): из <tex>b</tex>\alpha_U = \dfrac{|U|}{|W|}, \alpha_V = \dfrac{|V|}{|W|}если существует путь <tex>p_1, \beta = 0dots, \gamma = 0 p_n</tex>* '''Центроидный метод''' (англ. ''UPGMC (Unweighted Pair Group Method with Centroid average)''): с <tex>\alpha_U p_1 = \dfrac{|U|}{|W|}, \alpha_V = \dfrac{|V|}{|W|}, \beta = -\alpha_U \cdot \alpha_V, \gamma = 0a</tex>* '''Метод Уорда''' (англ. ''Ward's method''): и <tex>\alpha_U p_n = \dfrac{|S|+|U|}{|S|+|W|}b</tex>, \alpha_V = \dfracгде каждая точка <tex>p_{|S|i+|V|1}{|S|+|W|}, \beta = \dfrac{-|S|}{|S|+|W|}, \gamma = 0 </tex>прямо достижима из точки <tex>p_i</tex> .* Все остальные точки, которые не достижимы из основных точек, считаются ''шумовыми''.

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

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

Расстояние является монотонным, если для коэффициентов в формул Ланса-Уильямса верна теорема МиллиганаНа выходе получаем разбиение на кластеры и шумовые объекты.{{Теорема|author=Миллиган, 1979|statement=Если выполняются следующие три условия, то кластеризация является монотонной:# Каждый из полученных кластеров <tex>\alpha_U \geqslant 0, \alpha_V \geqslant 0 C_j</tex>;является непустым множеством точек и удовлетворяет двум условиям:# <tex>\alpha_U + \alpha_V + \beta \geqslant 1</tex>;* Любые две точки в кластере попарно связаны (то есть найдется такая точка в кластере, из которой достижимы обе этих точки).# <tex>\min\{\alpha_U* Если точка достижима из какой-либо точки кластера, \alpha_V\} + \gamma \geqslant 0 </tex>то она принадлежит кластеру.}}

=== Определение числа кластеров ===Для определения числа кластеров находится интервал максимальной длины Пусть для каждого <tex>|x \mathrm{R_{t+1}} - \mathrm{R_t}|in X^m</tex>.В качестве итоговых кластеров выдаются кластеры, полученные на шаге имеем посчитанной его <tex>\mathrm{t}epsilon</tex>.При этом число кластеров равно -окрестность <tex>U_{\epsilon}(x) = \{x' \in X^m - t + 1\: | \: \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>

=== Псевдокод === <font color=darkgreen>// алгоритм принимает множество объектов и возвращает множество кластеров для каждого шага </font> '''function''' hierarchy(X: '''Set<Object>'''): '''Set<Set<Object>>''' t = 1 <tex>\mathrm{C_t} = {{x_1}DBSCAN находит практическое применение во многих реальных задачах, \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которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, 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Пример на языке R =darkgreen># Создание полотна для рисования</font> fig = plt.figure(figsize=(15, 30)) fig.patch.set_facecolor({{Main|Примеры кода на R}}Для реализации алгоритма ''k-средних'white') используется пакет <texcode>ClusterR</texcode>. В нем реализовано 2 функции: <font color=darkgreen># Загрузка набора данных "Ирисы Фишера"</fontcode> iris = datasets.load_irisKMeans_arma() <tex></texcode> и <font color=darkgreen># Реализация иерархической кластеризации при помощи функции linkage</fontcode> mergings = linkageKMeans_rcpp(iris.data, method='ward') <tex></tex> <font color=darkgreencode># Построение дендрограммы. Разными цветами выделены автоматически определенные кластерыВ примере далее рассмотрена реализация с использованием функции </fontcode> R = dendrogramKMeans_arma(mergings, labels=[iris.target_names[i] for i in iris.target], orientation = 'left', leaf_font_size = 12) <tex></tex> <font color=darkgreencode># Отображение дендрограммы</font> plt.show()

{| class <font color="wikitablegray"># importing package and its' dependencies</font>| style library(ClusterR) <font color="textgray"># reading data</font> data <-align:center; read.csv(<font-weight:bold;color="green" colspan = 4 |Дендрограммы кластеризации ирисов Фишера<ref>[https://ru"data.wikipedia.orgcsv"</wikifont>) <font color="gray"># evaluating model</%D0%98%D1%80%D0%B8%D1%81%D1%8B_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0 Википедия {{font> model <---}} Ирисы Фишера]KMeans_arma(data, <font color="#660099">clusters</reffont> в зависимости от функции расстояния между кластерами|-| style= <font color="padding:5px;blue" |[[Файл:hierarchy_min.png|350px|Расстояние минимума.]]| style>2</font>, <font color="padding:5px;#660099" |[[Файл:hierarchy_max.png|350px|Расстояние максимума.]]|-| style>n_iter</font> = <font color="text-align:center;blue" | Метод одиночной связи| style>10</font>, <font color="text-align:center;#660099" | Метод полной связи|-| style>seed_mode</font> = <font color="padding:5px;green" |[[Файл:hierarchy_avg.png|350px|Расстояние среднего.]]>"random_subset"</font>, | style <font color="padding:5px;#660099" |[[Файл:hierarchy_ward.png|350px|Расстояние Уорда.]]|-| style>verbose</font> = T, <font color="text-align:center;#660099" | Метод средней связи>CENTROIDS</font> = NULL) | style <font color="text-align:center;gray" | Метод Уорда># predicting results</font>|} predictions <- predict_KMeans(test_data, model)

* [[Оценка_качества_в_задаче_кластеризации|Оценка качества в задаче кластеризации]]^{[на 14.12.18 не создан]}* [[EM-алгоритм|EM-алгоритм]]* [[Иерархическая_кластеризация|Иерархическая кластеризация]]* [[k-средних|<tex>\mathrm{k}</tex>-средних]]^{[на 1428.1201.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]