Изменения

'''Алгоритм кластеризации''' — это функция <tex>a\colon X\to Y</tex>, которая любому объекту <tex>x\in X</tex> ставит в соответствие идентификатор кластера <tex>y\in Y</tex>.

* не Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.;* число Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют ввести указать этот параметр<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>.

{| 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 не создан]}