Комбінаторний метод ієрархічної класифікації

Мета роботи. Здійснити методом кластерного аналізу ієрархічну класифікацію даних, представлених матрицею близькостей, отриманою в попередніх дослідженнях та відобразити результати у вигляді дендрограми та площинної діаграми.

 

Зміст роботи. Суть даної роботи полягає в реалізації конкретної процедури класифікації відповідним чином підготовлених даних. Підготовка даних означає, що вони ретельно відібрані, перевірені представлені матрицею близькостей, причому допускається використана при формуванні матриці близькостей метрика, оскільки в іншому випадку матрицю близькостей необхідно обчислювати заново.

Загальний алгоритм процедури класифікації можна представити як основний цикл об’єднань наступними кроками.

Крок 1. Кожен з елементів, які підлягають класифікації, розглядається як окремий кластер. Обчислюється початкова матриця міжкластерних відстаней . Цей крок можна опустити, якщо відстані вже обчислені і повинні бути тільки введеними в програму.

Крок 2. Поглядається матриця і шукається мінімальний елемент .

Крок 3. Об’єднуються два кластери та , визначені на кроці 2, утворюючи новий кластер . Друкується інформація, яка відноситься до цього об’єднання. Якщо залишається лише один кластер, робота програми припиняється.

Крок 4. Обчислюються нові відстані між новим кластером і кожним з тих, що залишились, кластерів , які включаються в матрицю . Переходять до кроку 2.

Зауваження. Якщо об’єднується елементів, то першому кластеру, отриманому при об’єднанні присвоюється номер . Кластерам, отриманим при кожному наступному об’єднанні, присвоюються наступні номери. Взагалі, коли залишається груп, то остання утворена група отримує номер . Якщо необхідно знати склад груп, тоді кожному номеру групи потрібно поставити у відповідність список номерів елементів, які вона містить. Ця необхідна інформація може бути отримана, як тільки буде досягнуто задане значення .

Більш конкретно зміст процедури об’єднання можна пояснити на наступному прикладі.

Припустимо, що маємо п’ять індивідуумів, для яких задані міри відмінностей , які представлені матрицею .

Використовуємо для групування гнучку стратегію, яка зберігає метрику простору, з параметром . Тоді, відповідно параметри . Послідовність кроків має наступний зміст.

 

D
	-	0.227	0.250	0.422	0.897
	0.227	-	0.492	0.387	0.917
	0.250	0.492	-	0.356	1.000
	0.422	0.387	0.356	-	0.773
	0.897	0.917	1.000	0.773	-

 

1. Знаходимо найменше значення в матриці : воно рівне . Об’єднання елементів 1 і 2 утворює групу 6. Перераховуємо відстані, обчислюючи значення , , :

 

	=	0.625 x (0.250+0.492)	-	0.250 x (0.227)	=	0.407
	=	0.625 x (0.422+0.387)	-	0.250 x (0.227)	=	0.449
	=	0.625 x (0.897+0.917)	-	0.250 x (0.227)	=	1.077

 

Стовпчик 1 і стрічка 1 відкидаються, а замість стовпчика 2 і стрічки 2 записується стовпчик 6 і стрічка 6. Отримуємо нову матрицю:

 

	-	0.407	0.449	1.077
	0.407	-	0.356	1.000
	0.449	0.356	-	0.773
	1.077	1.000	0.773	-

 

Тепер найменше значення в матриці рівне . Об’єднуємо 3 і 4, в результаті отримуємо групу 7 і обчислюємо і

 

	=	0.625 x (1.000+0.733)	-	0.250 x (0.356)	=	1.019
	=	0.625 x (0.407+0.449)	-	0.250 x (0.356)	=	0.446

 

Стовпчик 3 і стрічка 3 відкидаються, а замість стовпчика 4 і стрічки 4 записується стовпчик 7 і стрічка 7, після чого матриця має вид:

 

 

	-	0.446	1.077
	0.446	-	1.019
	1.077	1.019	-

 

Найменше значення в матриці тепер дорівнює . Об’єднуємо 6 і 7 і отримуємо групу 8. тепер необхідно обчислити значення , яке рівне

 

=

0.625 x (1.077+1.019)

-

0.250 x (0.446)

=

1.198

 

Об’єднання 5 і 8 дає групу 9. оскільки залишилась лише одна група то процедура класифікації завершується.

Результат може бути представлений у формі таблиці

Таблиця 1.

Об’єднання елементів і груп	Результат об’єднання	Значення відстані
	і		Дає
	і		Дає
	і		дає
	і		дає

 

 

 

Рис. 1. Представлення результатів ієрархічної комбінаторної класифікації: а – дендрограмою, б – площинною діаграмою.