77
правок
Изменения
Нет описания правки
Решение задачи кластеризации объективно неоднозначно по ряду причин:
* Не существует однозначного критерия качества кластеризации. Известен ряд алгоритмов, осуществляющих разумную кластеризацию "по построению", однако все они могут давать разные результаты. Следовательно, для определения качества кластеризации и оценки выделенных кластеров необходим эксперт предметной области.;* Число кластеров, как правило, заранее не известно и выбирается по субъективным критериям. Даже если алгоритм не требует изначального знания о числе классов, конкретные реализации зачастую требуют указать этот параметр<ref>[https://scikit-learn.org/stable/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>.
Алгоритм кластеризации <tex>a</tex> является '''масштабно инвариантным''' (англ. ''scale-invariant''), если для любой функции расстояния <tex>\rho</tex> и любой константы <tex>\alpha > 0</tex> результаты кластеризации с использованием расстояний <tex>\rho</tex> и <tex>\alpha\cdot\rho</tex> совпадают.
}}
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависила зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
{{Определение
|definition =
|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> лежат в разных кластерах.
}}
== Типология задач кластеризации ==
=== Типы входных данных ===
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками (англ. ''features''). Признаки могут быть как числовыми, так и категориальными.;
* Матрица расстояний между объектами. Каждый объект описывается расстоянием до всех объектов из обучающей выборки.
=== Цели кластеризации ===
* Классификация объектов. Попытка понять зависимости между объектами путем выявления их кластерной структуры. Разбиение выборки на группы схожих объектов упрощает дальнейшую обработку данных и принятие решений, позволяет применить к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). В данном случае стремятся уменьшить число кластеров для выявления наиболее общих закономерностей.;* Сжатие данных. Можно сократить размер исходной выборки, взяв один или несколько наиболее типичных представителей каждого кластера. Здесь важно наиболее точно очертить границы каждого кластера, их количество не является важным критерием.;
* Обнаружение новизны (обнаружение шума). Выделение объектов, которые не подходят по критериям ни в один кластер. Обнаруженные объекты в дальнейшем обрабатывают отдельно.
=== Методы кластеризации ===
* Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.;* Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.:** [[EM-алгоритм]]<sup>[на 28.01.19 не создан]</sup>;* [[Иерархическая_кластеризация|Иерархические алгоритмы кластеризации]]. Упорядочивание данных путем создания иерархии вложенных кластеров.;* [[K-средних|Алгоритм <tex>\mathrm{k}</tex>-средних]]<sup>[на 28.01.19 не создан]</sup> (англ. ''<tex>\mathrm{k}</tex>-means''). Итеративный алгоритм, основанный на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров.;* Распространение похожести (англ. ''affinity propagation''). Распространяет сообщения о похожести между парами объектов для выбора типичных представителей каждого кластера.;* Сдвиг среднего значения (англ. ''mean shift''). Выбирает центроиды кластеров в областях с наибольшей плотностью.;* Спектральная кластеризация (англ. ''spectral clustering''). Использует собственные значения матрицы расстояний для понижения размерности перед использованием других методов кластеризации.;
* Основанная на плотности пространственная кластеризация для приложений с шумами (англ. ''Density-based spatial clustering of applications with noise'', ''DBSCAN''). Алгоритм группирует в один кластер точки в области с высокой плотностью. Одиноко расположенные точки помечает как шум.
== Применение ==
=== Биология и биоинформатика ===
* В области экологии кластеризация используется для выделения пространственных и временных сообщест сообществ организмов в однородных условиях.;* Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции.;* Кластеризация помогает автоматически определять генотипы по различным частям хромосом.;
* Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.
=== Медицина ===
* Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении.;
* Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.
=== Маркетинг ===
Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
=== Интернет ===
* Выделение групп людей на основе графа связей в социальных сетях.;
* Повышение релевантности ответов на поисковые запросы путем группировки веб-сайтов по смысловым значениям поискового запроса.
=== Компьютерные науки ===
* Кластеризация используется в сегментации изображений для определения границ и распознавания объектов.;* Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции.;* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере.;
* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
