Skip to content
Назад к результатам поиска

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

Автор метода
Ward, J. H.
Год
1963
Тип
Unsupervised clustering (agglomerative)

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Ее агломеративная форма основана на критерии группировки целевой функции, введенном Джо Уордом в 1963 году.

Интуиция метода

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

История

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

Когда применять

Используйте его для разведочной группировки, когда вы хотите обнаружить структуру, не задавая заранее количество кластеров, на непрерывных, порядковых или категориальных признаках с как минимум примерно 10 наблюдениями. Он имеет мало предположений, но опирается на два выбора: подходящую метрику расстояния и подходящий метод связи. При менее чем примерно 10 наблюдениях матрица расстояний ненадежна, а дендрограмма не может показать осмысленную структуру, поэтому K-средних является более безопасной альтернативой; на очень малых выборках результаты становятся чрезмерно чувствительными к методу связи, и членство в кластерах нестабильно.

Ограничения и замечания

  • Результаты сильно зависят от выбранной метрики расстояния и метода связи, которые являются решениями пользователя.
  • На малых выборках членство в кластерах нестабильно и чрезмерно чувствительно к методу связи.
  • При менее чем примерно 10 наблюдениях матрица расстояний ненадежна, а дендрограмма не показывает осмысленной структуры.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Не требует предварительного фиксирования количества кластеров — вы считываете его с дендрограммы.
  • Дендрограмма дает интерпретируемую визуальную карту того, как кластеры вложены на разных уровнях сходства.
  • Мало предположений: нет требования нормальности, и он учитывает непрерывные, порядковые и категориальные признаки через выбор расстояния.
  • Работает как разведочный инструмент для выявления структуры перед фиксацией разбиения.

Применение

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

Как это работает

Как это работает

1

Сначала вычисляется расстояние между каждой парой наблюдений с использованием выбранной метрики расстояния, что дает матрицу расстояний. Выбор метрики имеет значение: он определяет, что считать «похожим», и непрерывные, порядковые и категориальные признаки могут требовать разных определений расстояния.

2

Начиная с каждого наблюдения как своего собственного кластера, алгоритм многократно объединяет два ближайших кластера в соответствии с выбранным методом связи. Критерий Уорда, например, объединяет пару, которая дает наименьшее увеличение суммы квадратов внутри кластера, сохраняя результирующие кластеры максимально компактными. Выбор метода связи сильно влияет на окончательную группировку.

Формула
\Delta(A,B) = \sum_{i \in A \cup B} \lVert x_i - m_{A \cup B}\rVert^2 - \sum_{i \in A}\lVert x_i - m_A\rVert^2 - \sum_{i \in B}\lVert x_i - m_B\rVert^2
3

Последовательность объединений записывается в виде дендрограммы — дерева, высота ветвей которого показывает расстояние, на котором кластеры объединились. Обрезка дендрограммы на выбранной высоте дает назначения кластеров, поэтому количество кластеров считывается с дерева, а не указывается заранее.

Частые ошибки

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

Часто задаваемые вопросы

Нужно ли сначала выбирать количество кластеров?

Нет. Иерархическая кластеризация в любом случае строит полное дерево объединений, и вы решаете количество кластеров после этого, разрезая дендрограмму на выбранной высоте — это одно из ее главных преимуществ перед такими методами, как K-средних.

Какую метрику расстояния и метод связи использовать?

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

Сколько наблюдений мне нужно?

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

Почему мои кластеры нестабильны?

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

Похожие методы

Источники

  1. Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association, 58(301), 236–244.

    Открыть ссылку DOI
    Скопировано.