Постановка задачі
Вихідні дані. Для кластерного аналізу дані, зібрані в процесі дослідження чи отримані експериментально подають у формі таблиці «об’єкт - властивість», в той спосіб, що першим стовпчиком є назви об’єктів, які підлягають групуванню, а решта стовпчиків відповідають конкретним властивостям (ознакам, характеристикам, показникам тощо) і містять їх конкретні значення.
Задача.
Полягає в тім, щоб на підставі даних
таблицею «об’єкт - властивість», розбити
множину
цих об'єктів на
(
– ціле) кластерів – неперетинних
підмножин
так, щоб
,
а
,
тобто:
а)
кожний об'єкт
має належати одній і
тільки одній підмножині розбиття;
б) об'єкти, що належать одному і тому самому кластеру, були подібними;
в) об'єкти, що належать до різних кластерів були відмінними.
Результат. За отриманими даними має бути побудована дендрограма і приведена її інтерпретація.
Ілюстрацію процедури агломеративного ієрархічного кластерного аналізу доцільно провести на конкретному прикладі, з відповідними поясненнями та обґрунтуваннями, використовуючи для розрахунків табличний процесор Ms Excel 2003.
Приклад.
В якості такого прикладу використано результати тренажерної підготовки операторського персоналу систем опрацювання аерокосмічних зображень, задіяних в задачах виявлення на них об’єктів заданого класу. В результаті опрацювання одного і того ж сценарію, який полягав у поданні на монітор послідовності тестових зображень, для кожного оператора отримані дані про час опрацювання кожного тесту, тобто пошуку і виявлення та ідентифікації об’єкта на тестовому даного сценарію. Значення цього часу є випадковими величинами з асиметричним одномодальним розподілом і поданими у вигляді індивідуальних часових рядів.
Формування
таблиці «об’єкт- властивість». В
результаті первинної обробки даних в
сенсі описової статистики в межах
показників визначених для цього в Ms
Excel
2003 побудована
таблиця, яку називають таблицею «об’єкт
- властивість». В даному випадку, більш
коректно, це є таблиця «оператор-індивідуальні
показники» розміром
,
де
– кількість операторів, а
– кількість використаних показників
описової статистики. Отже, для кластерного
аналізу подається множина
,
яка включає
об’єктів, кожен з яких характеризується
ознаками. Дані представлені нижче в
табл. 1
Таблиця 1.
Таблиця «оператор - показник» – значень показників об’єктів за описовою статистикою
|
Показники |
|||||||||||||
Об’єк ти |
Середнє |
Стнд.пом. |
Медіана |
Мода |
Стнд. відх. |
Диспер сія |
Екс цес |
Асимет рія |
Роз мах |
Міні мум |
Макси мум |
Сума |
К-сть |
Надій ність |
Bur |
1886,2 |
26,68 |
1839,5 |
1697 |
322,4 |
103921 |
3,837 |
1,257 |
2290 |
1196 |
3486 |
275378 |
146 |
52,7 |
Cub |
678,9 |
17,57 |
636,0 |
708 |
187,6 |
35189 |
0,790 |
0,995 |
976 |
376 |
1352 |
77395 |
114 |
34,8 |
Cup |
1506,5 |
22,74 |
1484,0 |
1663 |
245,9 |
60482 |
-0,267 |
0,516 |
1130 |
1050 |
2180 |
176263 |
117 |
45,0 |
Hav |
753,7 |
16,74 |
726,5 |
787 |
169,1 |
28600 |
1,714 |
1,208 |
892 |
483 |
1375 |
76878 |
102 |
33,2 |
Hod |
709,5 |
16,62 |
674,0 |
714 |
171,1 |
29272 |
1,742 |
1,261 |
900 |
462 |
1362 |
75204 |
106 |
32,9 |
Kol |
430,2 |
8,96 |
415,0 |
429 |
105,3 |
11089 |
6,887 |
2,169 |
722 |
241 |
963 |
59372 |
138 |
17,7 |
Lob |
665,0 |
18,36 |
622,5 |
601 |
179,9 |
32354 |
0,828 |
1,037 |
845 |
355 |
1200 |
63840 |
96 |
36,4 |
Lot |
608,2 |
15,81 |
593,0 |
623 |
178,2 |
31751 |
2,029 |
1,163 |
981 |
347 |
1328 |
77246 |
127 |
31,3 |
Oli |
655,3 |
16,69 |
619,0 |
609 |
166,0 |
27563 |
3,005 |
1,503 |
890 |
396 |
1286 |
64872 |
99 |
33,1 |
Per |
728,3 |
8,19 |
717,0 |
705 |
96,5 |
9313 |
7,528 |
1,662 |
769 |
504 |
1273 |
101229 |
139 |
16,2 |
Pon |
675,9 |
14,43 |
651,5 |
518 |
165,8 |
27489 |
0,451 |
0,754 |
833 |
395 |
1228 |
89213 |
132 |
28,5 |
Sol |
1633,1 |
28,83 |
1588,0 |
1446 |
311,9 |
97268 |
0,590 |
0,771 |
1524 |
1117 |
2641 |
191070 |
117 |
57,1 |
Syr |
704,4 |
19,03 |
645,5 |
606 |
215,3 |
46362 |
1,952 |
1,325 |
1176 |
318 |
1494 |
90165 |
128 |
37,7 |
Наведені
в табл. 1 показники за величиною і
розмірністю є дуже неоднорідними, а це
означає неможливість обґрунтованої
інтерпретації отриманого результату
кластерного аналізу. Це приводить до
того, що величина, отриманих в результаті
кластеризації відстаней між точками,
що відбивають положення об'єктів у
просторі їхніх властивостей, визначатиметься
довільно обраним масштабом. Щоб усунути
неоднорідність виміру вихідних даних,
всі їхні значення попередньо нормуються,
тобто виражаються через відношення цих
значень до деякої величини, що відбиває
певні властивості даного показника.
Важливо, щоб усі змінні змінювалися в
порівнянних шкалах.крім того, за наявності
значного розкиду величин значень
необхідно привести їх до інтервалу
,
тобто здійснити їх нормування.
Нормування таблиці «об’єкт-властивість». Основні труднощі полягають у виборі способу нормування, оскільки, необхідно максимально врахувати якісну специфіку показників. Нормування використовують в тому випадку коли ознаки представлені різними шкалами і мають різний фізичний зміст (розмірність). Нормування – це перехід до деякого однакового опису для всіх ознак і введення нової умовної одиниці вимірювання, яка допускає формальне зіставлення об'єктів чи їх ознак. Нормування приводить до безрозмірних величин, зберігаючи за ними відповідність ознакам.
Найбільш
розповсюджувані способи нормування
показників, тобто перехід від початкових
значень
до нормованих
,
здійснюють за формулами [Мандель
стор. 27]:
,
, (2)
де
– середньоквадратичне відхилення.
Найбільш поширеним нормування є лінійне перетворення, яке проводять за модифікованою останньою формулою.
Визнання рівноцінності різних показників є виправданим аж ніяк не завжди. Очевидно, що великі значення дисперсії та суми та їх варіації будуть суттєво впливати на результат кластерного аналізу.
В результаті нормування за цією формулою всі дані табл. 1 є приведені до одиничного інтервалу, тобто ця таблиця прийме вигляд табл. 2. Нормування здійснюється по кожному стовпчику окремо, тобто нормуються ознаки одного типу.
Таблиця 2.
Таблиця «оператор - показник» – після нормування
|
Показники |
|||||||||||||
Опера тори |
Середнє |
Стнд. пом. |
Медіа на |
Мода |
Стнд. Відх. |
Диспер сія |
Екс цес |
Асимет рія |
Роз мах |
Міні мум |
Макси мум |
Сумма |
К-сть |
Надій ність |
Bur |
1,000 |
0,896 |
1,000 |
1,000 |
1,000 |
1,000 |
0,527 |
0,447 |
1,000 |
1,000 |
1,000 |
1,000 |
1,000 |
0,893 |
Cub |
0,171 |
0,454 |
0,155 |
0,220 |
0,403 |
0,274 |
0,136 |
0,288 |
0,162 |
0,141 |
0,154 |
0,083 |
0,360 |
0,455 |
Cup |
0,739 |
0,705 |
0,750 |
0,973 |
0,662 |
0,541 |
0,000 |
-0,002 |
0,260 |
0,847 |
0,482 |
0,541 |
0,420 |
0,705 |
Hav |
0,222 |
0,414 |
0,219 |
0,282 |
0,321 |
0,204 |
0,254 |
0,417 |
0,108 |
0,253 |
0,163 |
0,081 |
0,120 |
0,416 |
Hod |
0,192 |
0,408 |
0,182 |
0,225 |
0,330 |
0,211 |
0,258 |
0,449 |
0,114 |
0,231 |
0,158 |
0,073 |
0,200 |
0,410 |
Kol |
0,000 |
0,038 |
0,000 |
0,000 |
0,039 |
0,019 |
0,918 |
1,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,840 |
0,038 |
Lob |
0,161 |
0,493 |
0,146 |
0,136 |
0,369 |
0,244 |
0,141 |
0,313 |
0,078 |
0,119 |
0,094 |
0,021 |
0,000 |
0,495 |
Lot |
0,122 |
0,369 |
0,125 |
0,153 |
0,362 |
0,237 |
0,295 |
0,390 |
0,165 |
0,111 |
0,145 |
0,083 |
0,620 |
0,369 |
Oli |
0,155 |
0,412 |
0,143 |
0,142 |
0,308 |
0,193 |
0,420 |
0,596 |
0,107 |
0,162 |
0,128 |
0,025 |
0,060 |
0,414 |
Per |
0,205 |
0,000 |
0,212 |
0,218 |
0,000 |
0,000 |
1,000 |
0,692 |
0,030 |
0,275 |
0,123 |
0,194 |
0,860 |
0,000 |
Pon |
0,169 |
0,302 |
0,166 |
0,070 |
0,307 |
0,192 |
0,092 |
0,142 |
0,071 |
0,161 |
0,105 |
0,138 |
0,720 |
0,302 |
Sol |
0,826 |
1,000 |
0,823 |
0,802 |
0,954 |
0,930 |
0,110 |
0,152 |
0,511 |
0,917 |
0,665 |
0,610 |
0,420 |
1,000 |
Syr |
0,188 |
0,525 |
0,162 |
0,140 |
0,526 |
0,392 |
0,285 |
0,488 |
0,290 |
0,081 |
0,210 |
0,143 |
0,640 |
0,525 |
Зауважимо, що нормування означає, що всі ознаки є рівноцінними з погляду з'ясування подібності розглянутих об'єктів. Інколи, поряд з нормуванням надають кожному з показників вагу і тим самим вказують на його значущість в ході встановлення подібностей і відмінностей між об'єктами.
Вибір
метрики для побудови матриці близькостей.
Якщо
відстань між об’єктами природно
трактувати як міру відмінності об’єктів,
то обернену величину
можна розглядати як міру подібності
(близькості) об’єктів.
1.
Евклідова метрика.
Найчастіше відстань
між об’єктами вимірюють в евклідовій
матриці, яка найбільш узгоджена з нашими
інтуїтивними представленнями про
близькість об’єктів і визначається за
формулою
, (4)
де
та
– значення
-ї
компоненти в описах 1-го та 2-го об’єктів,
–
розмірність простору ознак, а в даному
випадку
.
Ця метрика є метрикою Мінковського
степеня 2. її часто використовують, коли
ознаки однорідні за фізичним змістом
і однаково важливі для класифікації.
2. Манхетенська метрика. Широко використовується лінійна метрика (метрика міських кварталів або манхетенська метрика) яка задає відстань
. (5)
Ця метрика є окремим випадком метрики Мінковського, тобто є метрикою Мінковського для степеня 1. приведений вираз часто ділять на число ознак.
3. Чебишовська метрика. Цю метрику ще називають sup-норма, яка визначає чебишевську відстань
. (6)
Н
Рис.1.
Ілюстрація змісту відстаней
.
-
довжина відрізка АС;
-
сума довжин відрізків АВ і
ВС;
- довжина більшого
з відрізків АВ і ВС, тобто АВ.
Очевидно,
що
з ростом розмірності
манхетенська відстань
підкреслює, а чебишовська злагоджує
відмінності між об’єктами. Відстані
визначаються для тих описів, в яких
ознаки виражені кількісними шкалами і
є по-суті частинними випадками узагальнення
відстані Мінковського
,
тобто відстані
визначаються значенням степеня
.
Існує досить велика різноманітність
мір, але на практиці ці міри є найуживанішими.
4.
Відстань Брея-Кертиса.
Ця відстань забезпечує значення в межах
,
проте змінні з великими значеннями
мають більший вплив на результат. У
випадку використання даної метрики
значення матриці близькості необхідно
нормувати.
.
Дані після нормування мають бути невід’ємними. Приведена формула в обчислювальному відношенні є досить зручною, проте незвична для користувачів, хоча має своїх прихильників, зокрема в екології.
5. Канберрівська метрика. Ця метрика задається таким виразом
.
Вона
автоматично є нормованою і для невід’ємних
знаходиться в межах 0 і 1. Вона є нечутливою
до дуже значних відхилень значень, що
робить її прийнятною для дуже асиметричних
даних. Основною її особливістю є те, що
у випадку, коли
її величина рівна 1 незалежно від значення
,
тому нульові значення
заміняють меншими ніж найменше з усіх
значень в матриці даних.
В
результаті застосування до даних
будь-якої з цих метрик отримують матрицю
близькостей, розмірність якої
,
а за своєю специфікою вона є симетричною
відносно головної діагоналі.
Евклідова відстань ефективна при дослідженні слабо кореляційних сукупностей об’єктів (кулеподібні класи), а манхетенська тоді, коли об’єкти утворюють плоскі витягнені класи, ортогональні будь-яким координатним осям простору ознак. Тому обробка однієї і тієї ж сукупності даних одним і тим же методом або алгоритмом, але з використанням різних метрик може дати різні, інколи кардинально протилежні, результати.
Отже, до вибору метрики слід підходити дуже продумано і обережно зіставляючи результати використання різних метрик між собою і з цілями здійснюваної обробки даних.
Якщо ознаки представляються в якісних шкалах, зокрема в шкалах найменувань та порядку, використовують відстань Геммінга
для
якої відмінності виражаються числом
неспівпадінь властивостей порівнюваних
об’єктів. У випадку якісних шкал ознаки
розглядаються як бінарні, тобто такі,
що можуть приймати лише два значення
“ 0 “ та “ 1 “. Відстань Геммінга
є максимальною і рівна
1 для об’єктів з
протилежними за значеннями описами,
тобто елементи одного опису є протилежними
до відповідних елементів опису другого
об’єкту. Для об’єктів, всі ознаки яких
(з числа включених в опис) співпадають,
.
При виборі виду міри близькості необхідно врахувати їх формальні властивості і зіставити їх із змістовними особливостями задачі.
В результаті застосування будь-якої з цих метрик до даних отримують матрицю близькостей, розмірність якої , а за своєю специфікою вона є симетричною відносно головної діагоналі.
Побудова таблиці близькостей. Для побудови матриці близькостей за допомогою табличного процесора Ms Excel 2003 використовують дані табл. 2 в такий спосіб.
1. На робочому листі поміщають табл. 2 та її копію, так щоб номери стрічок в них були однакові, наприклад, якщо перший елемент табл. 2 – таблиці-оригіналу розміщений в комірці В3, то перший елемент таблиці-копії цієї таблиці є розміщений в комірці R3.
2. Далі будують матрицю близькостей. При цьому неминуче виникає задача вибору міри близькості. Найчастіше відстань між об’єктами вимірюють в евклідовій метриці, її ще називають евклідовою відстанню і розраховують за такою формулою
(5)
Евклідова метрика, є найбільш узгодженою з нашими інтуїтивними представленнями про близькість об’єктів.
3. В
результаті застосування до матриці
даних цієї метрики отримують матрицю
близькостей, розмірність якої
,
де
–
номер ознаки,
– індекси пари об’єктів, між якими
визначають відстань. Матриця відстаней
за своєю специфікою є симетричною
відносно головної діагоналі.
В Екселі матрицю близькостей будують так. Визначають комірку для розміщення першого елемента матриці близькостей, наприклад, В18, тобто нижче на кілька стрічок під таблицею, в якій розміщують (для даного випадку) таку формулу
=КОРЕНЬ(СУММ(($B$3-$R3)^2+($C$3-$S3)^2+($D$3-$T3)^2+($E$3-$U3)^2+($F$3-$V3)^2+($G$3-$W3)^2+($H$3-$X3)^2+($I$3-$Y3)^2+($J$3-$Z3)^2+($K$3-$AA3)^2+($L$3-$AB3)^2+($M$3-$AC3)^2+($N$3-$AD3)^2+($O$3-$AE3)^2))
і далі,
шляхом автозаповнення в
клітинок стовпчика В
будуть записані
відповідні значення
першого стовпчика матриці близькостей.
В результаті в комірці В19
формула буде мати
вигляд
=КОРЕНЬ(СУММ(($B$3-$R4)^2+($C$3-$S4)^2+($D$3-$T4)^2+($E$3-$U4)^2+($F$3-$V4)^2+($G$3-$W4)^2+($H$3-$X4)^2+($I$3-$Y4)^2+($J$3-$Z4)^2+($K$3-$AA4)^2+($L$3-$AB4)^2+($M$3-$AC4)^2+($N$3-$AD4)^2+($O$3-$AE4)^2)),
тобто, номер і значення стрічок таблиці-оригіналу залишаться без зміни, а зміняться лише номери стрічок таблиці-копії. В результаті, буде визначено відстань між першим об’єктом, визначеним першою стрічкою таблиці-оригіналу, і кожним об’єктом, визначеним стрічкою таблиці-копії.
4. Для визначення відстані між другим об’єктом таблиці –оригіналу і всіма іншими об’єктами таблиці копії копіюють формулу з комірки В18 в комірку С18. Після активізації формули в цій комірці, змінюють адрес першої стрічки таблиці-оригіналу шляхом переміщення всіх кольорових рамок на одну комірку вниз. В результаті цього формула буде мати такий вигляд
=КОРЕНЬ(СУММ(($B$4-$R3)^2+($C$4-$S3)^2+($D$4-$T3)^2+($E$4-$U3)^2+($F$4-$V3)^2+($G$4-$W3)^2+($H$4-$X3)^2+($I$4-$Y3)^2+($J$4-$Z3)^2+($K$4-$AA3)^2+($L$4-$AB3)^2+($M$4-$AC3)^2+($N$4-$AD3)^2+($O$4-$AE3)^2)).
Реалізуємо цю формулу і шляхом автозаповнення формуємо другий стовпчик матриці близькостей. Аналогічно поступають при визначенні решти стовпчиків.
Зауваження. Якщо, виходячи з розмірності власних задач, побудувати матрицю близькостей для максимально можливих кількостей об’єктів і ознак, то використовуючи її як шаблон, можна знайти значення матриць близькостей для будь-якої кількості об’єктів і ознак, замінюючи в таблиці-оригінал і в таблиці-копії їхні значення і відкидаючи порожні комірки шаблону, отримуємо безпосередньо потрібну матрицю близькості. Іншими словами, маючи лист Ексель з один раз зробленою процедурою побудови матриці близькості можна в таблиці ввести інші дані і, відкидаючи лишні або дораховуючи нові стовпчики і стрічки безпосередньо отримати матрицю близькості, але для конкретної метрики.
Після формування останнього стовпчика отримуємо матрицю близькості зображену у вигляді табл. 3.
Таблиця 3.