Изменения

* не Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.;* число Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<ref>[https://scikit-learn.org/0.20stable/modules/clustering.html scikit-learn {{---}} Clustering]</ref>.;* результат Результат кластеризации существенно зависит от метрики. Однако существует ряд рекомендаций по выбору метрик для определенных классов задач. == Типология задач кластеризации ===== Типы входных данных ===* Признаковое описание объектов<ref>Cornwell, B. Каждый объект описывается набором своих характеристик, называемых признаками (англ2015). ''features'')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>k-\rho</tex>средних (англ. ''должно совпадать со множеством всех возможных разбиений множества объектов <tex>k-X</tex>means'').}} ** EM-Вторая аксиома утверждает, что алгоритм* Иерархические алгоритмы кластеризациидолжен уметь кластеризовать обучающую выборку на любое фиксированное разбиение для какой-то функции расстояния <tex>\rho</tex>. Упорядочивание данных путем создания иерархии вложенных кластеров. == Иерархическая кластеризация ==

Функция расстояния <tex>{\rho}'</tex> является ''Иерархическая кластеризация'допустимым преобразованием'' (англ. 'функции расстояния <tex>\rho</tex>, если#<tex>{\rho}'hierarchical clustering'(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;" | Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние между объектами: <tex>\mathrm{R}(\{x\}, \{y\}) = \rho(xуменьшилось, y)</tex>межклассовое увеличилось.Для вычисления расстояния <tex>\mathrm{R}(U, V)</tex> между кластерами <tex>\mathrm{U}</tex> и <tex>\mathrm{V|}</tex> на практике используются различные функции в зависимости от специфики задачи.

Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:{{Теорема|author=Клейнберга|about== Формула Ланса-Уильямса ===о невозможностиНа каждом шаге необходимо уметь быстро подсчитывать расстояние от образовавшегося кластера <tex>\mathrm{W}|statement=\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)| Несмотря на эту теорему Клейнберг показал<ref>[https://www.cs.cornell.edu/tex>home/kleinber/nips15.pdf Kleinberg J. An Impossibility Theorem for Clustering]</centerref>, , где <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)features''): <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>дальнейшем обрабатывают отдельно.

{{Определение=== Методы кластеризации ===* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике;* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности:** [[EM-алгоритм]];* [[Иерархическая_кластеризация|definition =Иерархические алгоритмы кластеризации]]. Упорядочивание данных путем создания иерархии вложенных кластеров;Функция расстояния * [[K-средних|Алгоритм <tex>\mathrm{Rk}</tex> является -средних]]^{[на 28.01.19 не создан]} (англ. '''монотонной''', если на каждом следующем шаге расстояние между кластерами не уменьшается:<tex>\mathrm{R_2} \leqslant \mathrm{R_3} \leqslant \dots \leqslant \mathrm{R_mk}</tex>-means''). Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров;* Распространение похожести (англ. ''affinity propagation''). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера;}}* Сдвиг среднего значения (англ. ''mean shift''). Выбирает центроиды кластеров в областях с наибольшей плотностью;* Спектральная кластеризация (англ. ''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>|\mathrm{R_{t+1}} - \mathrm{R_t}|X</tex>метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение.В качестве итоговых кластеров выдаются кластерыпримера, полученные на шаге стремятся достичь минимума среднего внутрикластерного расстояния <tex>F_0 = \dfrac{\mathrmsum_{ti<j}{[y_i=y_j]\cdot\rho(x_i, x_j)}}{\sum_{i<j}[y_i=y_j]}</tex>.При этом число кластеров равно или максимума среднего межкластерного расстояния <tex>m - t + 1F_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* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;" | Метод Уорда|}* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.

Лучше всего с задачей справился == См. также ==* [[Оценка_качества_в_задаче_кластеризации|Оценка качества в задаче кластеризации]]* [[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]