Иерархические методы кластерного анализа

Агломеративные кластер-процедуры

Основной принцип работы иерархических агломеративных кластер-процедур состоит в последовательном объединении групп объектов сначала самых близких, а затем все более отдаленных друг от друга.

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

Рисунок 4.1 – Примеры горизонтальной и вертикальной дендрограмм объединения классов

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

К агломеративным методам кластерного анализа относят:

1. метод одиночной связи;

2. метод полной связи;

3. метод средней связи;

4. метод Уорда.

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

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

По методу средней связи происходит объединение схожих объектов в кластеры, при этом расстояние между объектом и классом вычисляется по принципу «средней связи», а расстояние между двумя классами – по «центрам тяжести» групп.

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

,

где – номер кластера;

– значение j -го признака для i -го объекта класса;

– среднее значение j -го признака в -ом кластере;

– количество объектов в -ом кластере.

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

Иерархические кластер-процедуры по сравнению с другими кластер-процедурами дают более полный и тонкий анализ структуры исследуемого множества объектов. Привлекательной стороной подобных алгоритмов является возможность наглядной интерпретации проведенного анализа. К недостаткам алгоритмов следует отнести громоздкость их вычислительной реализации, т.к. на каждом шаге требуется вычисление всей матрицы расстояний. Поэтому реализация таких алгоритмов при большом числе объектов () оказывается нецелесообразной.

Пример 4.1 Потребительское поведение пяти семей характеризуется расходами в летние месяцы на питание (, тыс. р.) и отдых (, тыс. р.). Значения показателей представлены в таблице:

Номер семьи,

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

Рисунок 4.2 – Расположение исходных данных в двумерном признаковом пространстве

Из геометрических соображений можно предположить существование двух классов: первый класс состоит из объектов , , , второй – из объектов , .

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

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

Объекты
		3, 61	7, 21	10, 0	11, 0
	3, 61		4, 12	8, 94	9, 22
	7, 21	4, 12		6, 40	5, 83
	10, 0	8, 94	6, 40		2, 24
	11, 0	9, 22	5, 83	2, 24

Изначально каждый объект рассматривается как отдельный класс, т.е. , , , , .

На первом шаге объекты и объединяются в один кластер, поскольку расстояние между ними минимально (2, 24). Получаем четыре кластера: , , , . После объединения матрица межклассовых расстояний пересчитывается по принципу «ближайшего соседа». Так, расстояние между классом и будет равно:

.

Проведя аналогичные расчёты для других классов объектов, получим матрицу межклассовых расстояний вида:

Классы				,
		3, 61	7, 21	10, 0
	3, 61		4, 12	8, 94
	7, 21	4, 12		5, 83
,	10, 0	8, 94	5, 83

На втором шаге объекты и , имеющие наименьшее расстояние (3, 61), объединяются в один кластер. Получаем следующие три кластера: , , . Пересчитанная по принципу «ближайшего соседа» матрица расстояний будет иметь вид:

Классы	,		,
,		4, 12	8, 94
	4, 12		5, 83
,	8, 94	5, 83

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

объекты	, ,	,
, ,		5, 83
,	5, 83

На четвертом шаге на расстоянии 5, 83 все объекты объединяются в один кластер .

Представим результаты классификации в виде вертикальной дендрогаммы (рисунок 4.3):

Рисунок 4.3 – Дендрограмма объединения объектов

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

Рассчитав средние значения признаков в кластерах, получим:

Кластеры	Средние значения признаков
	5, 67	8, 67
		13, 5

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

Дивизимные кластер-процедуры

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

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

Общая схема работы агломеративных и дивизимных кластер-процедур приведена на рисунке 4.4:

Рисунок 4.4 – Процесс последовательного объединения (разделения) классов иерархическими методами кластерного анализа

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

Возьмем за основу, рассчитанную с помощью обычной евклидовой метрики, матрицу расстояний между объектами:

объекты
		3, 61	7, 21	10, 0	11, 0
	3, 61		4, 12	8, 94	9, 22
	7, 21	4, 12		6, 40	5, 83
	10, 0	8, 94	6, 40		2, 24
	11, 0	9, 22	5, 83	2, 24

Согласно дивизимному алгоритму, изначально все объекты относятся к одному кластеру .

На первом шаге происходит разделение наиболее удаленных друг от друга объектов и на расстоянии 11, 0: , . Распределим оставшиеся объекты , , по кластерам по принципу, объект следует отнести к тому классу, расстояние до которого наименьшее:

1. < , следовательно, объект следует отнести в первый кластер, т.е. присоединить к объекту ;

2. > , следовательно, ;

3. > , следовательно, объект следует отнести ко второму кластеру.

Таким образом, имеет два класса со следующим составом: , .

На втором шаге выделим из образовавшихся классов два, наиболее удаленных друг от друга, объекта , на расстоянии 6, 40. Получим три кластера, причем оставшийся объект следует присоединить к объекту , поскольку < : , , .

На третьем шаге, на расстоянии 3, 61 следует разделить объекты и .

На четвертом шаге, на расстоянии 2, 24 разделяем последнюю пару объектов и .

Таким образом, все объекты были разделены, и каждый из них образует отдельный кластер6 , , , , .

Представим результаты дивизимного алгоритма классификации графически (рисунок 4.5).

Рисунок 4.5 – Результаты последовательного разделениря объектов с помощью иерархических дивизимных кластер-процедур

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

Рассчитав средние значения признаков в кластерах, получим:

Кластеры	Средние значения признаков
	9, 5
	9, 67

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