Метод невзвешенного попарного среднего

Множество методов иерархического кластерного анализа различается не только используемыми мерами сходства (различия), но и алгоритмами классификации. Один из них метод невзвешенного попарного среднего – Unweighted Pair-Group Method Using Arithmetic Averages или сокращенно UPGMA.

Пусть требуется провести классификацию заданного множества объектов методом невзвешенного попарного среднего.

Перед началом работы алгоритма рассчитывается матрица расстояний между объектами. На каждом шаге в матрице расстояний ищется минимальное значение, соответствующее расстоянию между двумя наиболее близкими кластерами. Найденные кластеры $u$ и $v$ объединяются, образуя новый кластер $k$ . Строки и столбцы, соответствующие кластерам $u$ и $v$ , выбрасываются из матрицы расстояний, и добавляется новая строка и новый столбец, соответствующие кластеру $k$ . В результате матрица сокращается на одну строку и один столбец. Эта процедура повторяется до тех пор, пока не будут объединены все кластеры. Пусть задана следующая матрица расстояний:

	$1$	$2$	$3$	$4$	$5$
$1$	0	2.06	4.03	6.32	2.08
$2$	2.06	0	3.50	4.12	5.43
$3$	4.03	3.50	0	2.25	3.65
$4$	6.32	4.12	2.25	0	4.81
$5$	2.08	5.43	3.65	4.81	0

Пусть кластеры $u$ , $v$ и $k$ содержат $T_{u}$ , $T_{v}$ и $T_{k}$ объектов, соответственно. Кластер $k$ образован путем объединения кластеров $u$ и $v$ , тогда $T_{k}~=~T_{u}~+~T_{v}$ . Необходимо рассчитать удаленность кластера $k$ от некоторого кластера $w$ . Расстояние между этими кластерами определяется согласно формуле:

Решение:

Шаг 1. На первом шаге, когда каждый объект представляет собой отдельный кластер: $delim{|}{1}{|},delim{|}{2}{|},delim{|}{3}{|},delim{|}{4}{|}$ и $delim{|}{5}{|}$ . Согласно критерию классификации, объединение происходит между кластерами, расстояние между которыми наименьшее. Т.о. на этом шаге объединяются кластеры $delim{|}{1}{|}$ и $delim{|}{2}{|}$ . Расстояние объединения – $2.06$ . Необходимо произвести перерасчет матрицы расстояний с учетом нового кластера:

	$1,2$	$3$	$4$	$5$
$1,2$	0	3.765	5.22	3.755
$3$	3.765	0	2.25	3.65
$4$	5.22	2.25	0	4.81
$5$	3.755	3.65	4.81	0

Приведем пример расчета расстояния между кластерами $k~=~delim{|}{1,2}{|}$ и $w~=~delim{|}{3}{|}$ . Кластер $k$ образован путем объединения кластеров $u~=~delim{|}{1}{|}$ и $v~=~delim{|}{2}{|}$ . Расстояния $D(u,w)$ и $D(v,w)$ берем из начальной матрицы расстояний. Подставив полученные значения в формулу, получим:

Шаг 2. Согласно новой матрицы расстояний, кластеры $delim{|}{3}{|}$ и $delim{|}{4}{|}$ наиболее близкие. Расстояние объединения – $2.25$ . Необходимо произвести перерасчет матрицы расстояний с учетом полученного кластера:

	$1,2$	$3,4$	$5$
$1,2$	0	4.4925	3.755
$3,4$	4.4925	0	4.23
$5$	3.755	4.23	0

Приведем пример расчета расстояния между кластерами $k~=~delim{|}{3,4}{|}$ и $w~=~delim{|}{1,2}{|}$ . Кластер $k$ образован путем объединения кластеров $u~=~delim{|}{3}{|}$ и $v~=~delim{|}{4}{|}$ . Расстояния $D(u,w)$ и $D(v,w)$ берем из матрицы расстояний предыдущего шага. Подставив полученные значения в формулу, получим:

Шаг 3. Кластеры на данном шаге: $delim{|}{1,2}{|},delim{|}{3,4}{|}$ и $delim{|}{5}{|}$ ; наиболее близкие кластеры: $delim{|}{1,2}{|}$ и $delim{|}{5}{|}$ . Расстояние объединения – $3.755$ . Необходимо произвести перерасчет матрицы расстояний с учетом нового кластера:

	$1,2,5$	$3,4$
$1,2,5$	0	4.405
$3,4$	4.405	0

Приведем расчет расстояния между кластерами $k~=~delim{|}{1,2,5}{|}$ и $w~=~delim{|}{3,4}{|}$ . Кластер $k$ образован путем объединения кластеров $u~=~delim{|}{1,2}{|}$ и $v~=~delim{|}{5}{|}$ . Расстояния $D(u,w)$ и $D(v,w)$ берем из матрицы расстояний предыдущего шага. Подставив полученные значения в формулу, получим:

Шаг 4. На последнем шаге объединяются два оставшихся кластер $delim{|}{1,2,5}{|}$ и $delim{|}{3,4}{|}$ . Расстояние объединения – $4.405$ . Результат работы алгоритма представлен в виде дендрограммы: