Метод ближайшего соседа или метод одиночной связи

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

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

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

	$1$	$2$	$3$	$4$
$1$	0	2.06	4.03	6.32
$2$	2.06	0	2.50	4.12
$3$	4.03	2.50	0	2.24
$4$	6.32	4.12	2.24	0

Решение:

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

	$1,2$	$3$	$4$
$1,2$	0	2.50	4.12
$3$	2.50	0	2.24
$4$	4.12	2.24	0

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

	$1,2$	$3,4$
$1,2$	0	2.50
$3,4$	2.50	0

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

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