Алгоритмы кластеризации

Алгоритмы кластеризации разделяют данные на группы схожих элементов, выявляя естественную структуру без использования каких-либо меток.

Definition

Кластеризация — это неконтролируемое разделение набора данных на группы таким образом, чтобы точки внутри группы были более похожи друг на друга, чем на точки в других группах, где сходство определяется критерием расстояния или плотности, выбранным для конкретного применения.

Scope

Эта тема охватывает основные семейства кластеризации: центроидные методы, такие как k-средних, иерархическую агломеративную кластеризацию, которая строит дерево вложенных групп, плотностные методы, которые находят кластеры произвольной формы, а также выбор мер расстояния и количества кластеров. В ней рассматривается, что делает кластеризацию хорошей и почему проблема по своей сути неоднозначна.

Core questions

• Что делает набор точек кластером?
• Как k-средних итеративно минимизирует внутрикластерную дисперсию?
• Как выбирается количество кластеров?
• Когда иерархические или плотностные методы превосходят центроидные методы?

Key theories

k-средних и алгоритм Ллойда

k-средних минимизирует общую сумму квадратов расстояний до центров кластеров путем чередования присвоения точек ближайшим центрам и пересчета центров, процедура, которая сходится к локальному оптимуму.

Иерархическая кластеризация

Агломеративная кластеризация многократно объединяет ближайшие группы для построения дендрограммы, предоставляя кластеризации с различной степенью детализации и избегая необходимости заранее фиксировать количество кластеров.

Кластеризация на основе смешанных моделей

Рассмотрение кластеров как компонентов вероятностной смеси позволяет осуществлять мягкое присвоение и создавать кластеры различной формы и размера, связывая кластеризацию с оценкой плотности скрытых переменных.

Clinical relevance

Кластеризация лежит в основе сегментации рынка, организации документов и изображений, группировки экспрессии генов и обнаружения аномалий, и является основным инструментом разведочного анализа данных; поскольку кластеризация зависит от выбранного расстояния и количества групп, результаты следует интерпретировать с осторожностью, а не рассматривать как единственную истину.

History

Процедура k-средних восходит к работе Ллойда 1957 года по квантованию, опубликованной в 1982 году, и к независимой формулировке МакКуина. Иерархическая кластеризация возникла в численной таксономии, а плотностные методы, такие как DBSCAN, расширили кластеризацию до групп произвольной формы, вместе образуя стандартный набор инструментов неконтролируемой группировки.

Key figures

• Stuart Lloyd
• James MacQueen
• Trevor Hastie

Seminal works

• lloyd1982
• hastie2009
• bishop2006

Frequently asked questions

Почему k-средних требует выбора количества кластеров?

k-средних оптимизирует размещение фиксированного числа центров, поэтому это число является входным параметром. Его выбор основывается на эвристиках, таких как метод локтя, силуэтные оценки или предметные знания, поскольку добавление большего количества кластеров всегда уменьшает внутрикластерное расстояние.

Могут ли разные методы кластеризации давать разные ответы?

Да. Поскольку не существует единого определения кластера, центроидные, иерархические и плотностные методы могут производить различные разбиения одних и тех же данных, каждое из которых является действительным согласно своему собственному критерию. Правильный выбор зависит от ожидаемых форм кластеров и цели.