Метод вардов - Wards method - Wikipedia

В статистика, Метод Уорда это критерий, применяемый в иерархический кластерный анализ. Метод минимальной дисперсии Уорда это частный случай целевая функция подход, первоначально представленный Джо Х. Уордом-младшим.^[1] Уорд предложил генерала агломеративная иерархическая кластеризация процедура, в которой критерием выбора пары кластеров для объединения на каждом шаге является оптимальное значение целевой функции. Этой целевой функцией может быть «любая функция, которая отражает цель исследователя». Многие из стандартных процедур кластеризации содержатся в этом очень общем классе. Чтобы проиллюстрировать процедуру, Уорд использовал пример, в котором целевая функция - это сумма квадратов ошибок, и этот пример известен как Метод Уорда или точнее Метод минимальной дисперсии Уорда.

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

Критерий минимальной дисперсии

Критерий минимальной дисперсии Уорда сводит к минимуму общую дисперсию внутри кластера. Чтобы реализовать этот метод, на каждом шаге найдите пару кластеров, которая приводит к минимальному увеличению общей внутрикластерной дисперсии после слияния. Это увеличение представляет собой взвешенный квадрат расстояния между центрами кластеров. На начальном этапе все кластеры являются синглетонами (кластерами, содержащими одну точку). Чтобы применить рекурсивный алгоритм под этим целевая функция, начальное расстояние между отдельными объектами должно быть (пропорционально) возведено в квадрат Евклидово расстояние.

Следовательно, начальные кластерные расстояния в методе минимальной дисперсии Уорда определяются как квадрат евклидова расстояния между точками:

${\displaystyle d_{ij}=d(\{X_{i}\},\{X_{j}\})={\|X_{i}-X_{j}\|^{2}}.}$

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

Алгоритмы Ланса – Вильямса

Метод минимальной дисперсии Уорда может быть определен и реализован рекурсивно с помощью алгоритма Ланса – Вильямса. Алгоритмы Ланса – Вильямса представляют собой бесконечное семейство алгоритмов агломеративной иерархической кластеризации, которые представлены рекурсивной формулой для обновления расстояний между кластерами на каждом шаге (каждый раз при объединении пары кластеров). На каждом шаге необходимо оптимизировать целевую функцию (найти оптимальную пару кластеров для объединения). Рекурсивная формула упрощает поиск оптимальной пары.

Предположим, что кластеры ${\displaystyle C_{i}}$ и ${\displaystyle C_{j}}$ были следующими, чтобы их объединить. На данный момент известны все текущие попарные кластерные расстояния. Рекурсивная формула дает обновленные кластерные расстояния после ожидающего слияния кластеров. ${\displaystyle C_{i}}$ и ${\displaystyle C_{j}}$. Позволять

• ${\displaystyle d_{ij}}$, ${\displaystyle d_{ik}}$, и ${\displaystyle d_{jk}}$ - попарные расстояния между кластерами ${\displaystyle C_{i}}$, ${\displaystyle C_{j}}$, и ${\displaystyle C_{k}}$, соответственно,
• ${\displaystyle d_{(ij)k}}$ расстояние между новым кластером ${\displaystyle C_{i}\cup C_{j}}$ и ${\displaystyle C_{k}}$.

Алгоритм принадлежит семейству Лэнса-Вильямса, если обновленное кластерное расстояние ${\displaystyle d_{(ij)k}}$ можно вычислить рекурсивно

${\displaystyle d_{(ij)k}=\alpha _{i}d_{ik}+\alpha _{j}d_{jk}+\beta d_{ij}+\gamma |d_{ik}-d_{jk}|,}$

куда ${\displaystyle \alpha _{i},\alpha _{j},\beta ,}$ и ${\displaystyle \gamma }$ параметры, которые могут зависеть от размеров кластера, которые вместе с функцией расстояния кластера ${\displaystyle d_{ij}}$ определить алгоритм кластеризации. Несколько стандартных алгоритмов кластеризации, таких как одинарная связь, полная связь, и метод группового среднего имеют рекурсивную формулу указанного выше типа. Таблица параметров стандартных методов приводится несколькими авторами.^[2][3][4]

Метод минимальной дисперсии Уорда может быть реализован по формуле Ланса – Вильямса. Для непересекающихся кластеров ${\displaystyle C_{i},C_{j},}$ и ${\displaystyle C_{k}}$ с размерами ${\displaystyle n_{i},n_{j},}$ и ${\displaystyle n_{k}}$ соответственно:

${\displaystyle d(C_{i}\cup C_{j},C_{k})={\frac {n_{i}+n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{i},C_{k})+{\frac {n_{j}+n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{j},C_{k})-{\frac {n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{i},C_{j}).}$

Следовательно, метод Уорда может быть реализован как алгоритм Ланса – Вильямса с

${\displaystyle \alpha _{i}={\frac {n_{i}+n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \alpha _{j}={\frac {n_{j}+n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \beta ={\frac {-n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \gamma =0.}$

Вариации

Популярность метода Варда привела к его вариациям. Например, Уорд_п вводит использование весов характеристик конкретных кластеров, следуя интуитивной идее о том, что функции могут иметь разную степень релевантности в разных кластерах. ^[5]

Рекомендации

1. Уорд, Дж. Х. младший (1963), «Иерархическая группировка для оптимизации целевой функции», Журнал Американской статистической ассоциации, 58, 236–244.
2. Кормак, Р. М. (1971), "Обзор классификации", Журнал Королевского статистического общества, Серия А, 134(3), 321-367.
3. Гордон, А. Д. (1999), Классификация, 2-е издание, Чепмен и Холл, Бока-Ратон.
4. Миллиган, Г. У. (1979), "Ультраметрические иерархические алгоритмы кластеризации", Психометрика, 44(3), 343–346.
5. R.C. де Аморим (2015). «Актуальность функции в иерархической кластеризации Уорда с использованием нормы Lp» (PDF). Журнал классификации. 32 (1): 46–62. Дои:10.1007 / s00357-015-9167-1. S2CID  18099326.

дальнейшее чтение

• Эверит, Б. С., Ландау, С. и Лиз, М. (2001), Кластерный анализ, 4-е издание, Oxford University Press, Inc., Нью-Йорк; Арнольд, Лондон. ISBN  0340761199
• Хартиган, Дж. А. (1975), Алгоритмы кластеризации, Нью-Йорк: Wiley.
• Джайн, А.К. и Dubes, R. C. (1988), Алгоритмы кластеризации данных, Нью-Джерси: Прентис – Холл.
• Кауфман, Л. и Руссеу, П. Дж. (1990), Поиск групп в данных: введение в кластерный анализ, Нью-Йорк: Wiley.