БіоСтатистика — 12. Тема 8. Кластерний аналіз

←

D.A. Shabanov, M.A. Kravchenko. Статистичний аналіз даних у зоології та екології

→

Тема 7. Зв’язок між ознаками

Тема 8. Кластерний аналіз

Тема 9. Метод головних компонент

Біостатистика-11

Біостатистика-12

Біостатистика-13

8.1. Сутність кластерного аналізу
Кластерним аналізом називаються різноманітні формалізовані процедури побудови класифікацій об’єктів. Лідируючою наукою у розвитку кластерного аналізу була біологія. Предмет кластерного аналізу (від англ. «cluster» — грона, пучок, група) був сформульований у 1939 р. психологом Робертом Тріоном. Класиками кластерного аналізу є американські систематики Роберт Сокел і Пітер Сніт. Одне з найважливіших їх досягнень у цій галузі — книга «Начала численной таксономии», випущена у 1963 р. Відповідно до основної ідеї авторів, класифікація має будуватись не на змішуванні погано формалізованих суджень про схожість і родинність об’єктів, а на результатах формалізованої обробки результатів математичного обчислення схожостей/відмінностей класифікованих об’єктів. Для виконання цього завдання потрібні були відповідні процедури, розробкою яких і зайнялися автори.
Основні етапи кластерного аналізу такі:
1. вибір порівнюваних один з одним об’єктів;
2. вибір множини ознак, за якими буде проводитись порівняння, і опис об’єктів за цими ознаками;
3. обчислення міри схожості між об’єктами (або міри різниці об’єктів) відповідно до обраної метрики;
4. групування об’єктів у кластери за допомогою тієї чи іншої процедури об’єднання;
5. перевірка придатності отриманого кластерного рішення.
Отже, найважливішими характеристиками процедури кластеризації є вибір метрики (у різних ситуаціях використовується значна кількість різних метрик) і вибір процедури об’єднання (і в цьому випадку для вибору доступна значна кількість різних варіантів). Для різних ситуацій більше підходять одні чи інші метрики та процедури об’єднання, але в певній мірі вибір між ними є питанням смаку і традиції. Як докладніше пояснюється у статті «Кластери, клади і хімера об’єктивності», надія на те, що кластерний аналіз приведе до побудови класифікації, яка не залежить від довільності дослідника, виявляється недосяжною. З п’яти перелічених етапів дослідження з використанням кластерного аналізу лише етап 4 не пов’язаний із прийняттям більш‑менш довільного рішення, що впливає на кінцевий результат. І вибір об’єктів, і вибір ознак, і вибір метрики разом із процедурою об’єднання суттєво впливають на кінцевий результат. Цей вибір може залежати від багатьох обставин, зокрема — від явних і неявних уподобань і очікувань дослідження. На жаль, зазначена обставина впливає не лише на результат кластерного аналізу. З подібними проблемами стикаються всі «об’єктивні» методи, включаючи всі методи кладистики.
Чи існує єдине правильне рішення, яке треба знайти, обираючи сукупність об’єктів, набір ознак, тип метрики та процедуру об’єднання? Ні. Щоб довести це, наведемо фрагмент статті, посилання на яку дано в попередньому абзаці.
 «На справді, ми не завжди можемо навіть твердо відповісти на питання, які об’єкти більш схожі один на одного, а які відрізняються сильніше. На жаль, для вибору метрики схожості та різниці між класифікованими об’єктами загальноприйнятих (а тим більше «об’єктивних») критеріїв просто немає.

На який об’єкт більш схожий об’єкт А: на B чи на C? Якщо використовувати в якості метрики схожості відстань, то на C: |AC|<|AB|. А якщо покладатися на кореляцію між показаними на рисунку ознаками (яку можна описати як кут між вектором, що йде до об’єкта з початку координат, і віссю абсцис), то на B: . А як правильно? А єдиного правильного відповіді немає. З одного боку, доросла жаба більш схожа на дорослу жабу (обидві дорослі), з іншого — на молодшу жабу (обидві жаби)! Правильність відповіді залежить від того, що ми вважаємо більш важливим».
Кластерний аналіз знайшов широке застосування в сучасній науці. На жаль, у значній частині тих випадків, коли його вживають, краще було б використовувати інші методи. У будь‑якому разі, спеціалістам‑біологам треба чітко розуміти основну логіку кластерного аналізу, і лише в цьому випадку вони зможуть застосовувати його в тих випадках, де він адекватний, і не застосовувати його, коли оптимальним є вибір іншого методу.
8.2. Приклад виконання кластерного аналізу «на пальцях»
Щоб пояснити типову логіку кластерного аналізу, розглянемо його наочний приклад. Розглянемо сукупність з 6 об’єктів (позначених літерами), охарактеризованих за 6 ознаками найпростішого типу: альтернативних, що приймають одне з двох значень: характерний (+) і нехарактерний (—). Опис об’єктів за прийнятими ознаками називається «прямокутною» матрицею. У нашому випадку мова йде про матрицю 6×6, тобто її можна вважати цілком «квадратною», але в загальному випадку кількість об’єктів у аналізі може не дорівнювати кількості ознак, і «прямокутна» матриця може мати різну кількість рядків і стовпців. Отже, задаємо «прямокутну» матрицю (матрицю об’єкти/ознаки):

1

2

3

4

5

6

A

—

+

+

—

+

+

B

—

+

—

—

—

+

C

—

+

—

+

+

—

D

+

—

+

—

—

+

E

+

—

—

+

—

+

F

+

+

—

—

—

+

Вибір об’єктів і опис їх за певним набором ознак відповідають двом першим етапам кластерного аналізу. Наступний етап — побудова матриці схожості або різниці («квадратної» матриці, матриці об’єкти/об’єкти). Для цього треба обрати метрику. Оскільки наш приклад умовний, має сенс вибрати найпростішу метрику. Як найпростіше визначити відстань між об’єктами A і B? Порахувати кількість відмінностей між ними. Як бачите, об’єкти A і B відрізняються за ознаками 3 і 5, отже, відстань між цими двома об’єктами дорівнює двом одиницям. 
Використовуючи цю метрику, побудуємо «квадратну» матрицю (матрицю об’єкти/об’єкти). Як легко переконатися, така матриця складається з двох симетричних половин, і заповнювати можна лише одну з цих половин:

A

B

C

D

E

F

A

—

2

3

3

5

3

B

—

3

3

3

1

C

—

6

4

4

D

—

2

2

E

—

2

F

—

У даному випадку ми побудували матрицю різниць. Матриця схожості виглядала б подібно, лише на кожній позиції стояла б величина, рівна різниці між максимальною дистанцією (6 одиниць) і різницею між об’єктами. Для пари A і B, природно, схожість склала б 4 одиниці.
Які два об’єкти найближчі один до одного? B і F, вони відрізняються лише за однією ознакою. Суть кластерного аналізу — у об’єднанні подібних об’єктів у кластер. Об’єднуємо об’єкти B і F у кластер (BF). Показуємо це на схемі. Як бачите, об’єкти об’єднані на тому рівні, який відповідає дистанції між ними.

Рис. 8.2.1. Перший крок кластеризації умовного набору з 6 об’єктів
Тепер у нас не шість об’єктів, а п’ять. Перебудовуємо «квадратну» матрицю. Для цього нам потрібно визначити, якої величини відстань від кожного об’єкта до кластера. Відстань від A до B становила 2 одиниці, а від A до F — 3 одиниці. Якої величини відстань від A до (BF)? Правильного відповіді тут немає. Ось, подивіться, як розташовані один щодо одного ці три об’єкти.

Рис. 8.2.2. Взаємне розташування трьох об’єктів
Може бути, що відстань від об’єкта до групи — це відстань від об’єкта до найближчого до нього об’єкта в складі групи, тобто │A(BF)│=│AB│? Така логіка відповідає приєднанню за максимальною схожістю.
А може бути, що відстань від об’єкта до групи — це відстань від об’єкта до найвіддаленішого від нього об’єкта в складі групи, тобто │A(BF)│=│AF│? Така логіка відповідає приєднанню за мінімальною схожістю.
Можна також вважати, що відстань від об’єкта до групи — це середнє арифметичне відстаней від цього об’єкта до кожного з об’єктів у складі групи, тобто │A(BF)│=(│AB│+│AF│)/2. Це рішення називається приєднанням за середньою схожістю.
Правильними є всі ці три рішення і ще значна кількість інших, не охарактеризованих тут рішень. Наше завдання полягає у тому, щоб обрати рішення, більш придатне для тієї категорії, до якої належать наші дані. Приєднання за максимальною схожістю призводить, в кінцевому підсумку, до довгих, «стрічкових» кластерів. За мінімальною — до роздроблення груп. Обираючи між трьома охарактеризованими варіантами, у біології частіше використовують приєднання за середньою схожістю. Скористаємося ним і ми. У такому випадку після першого кроку кластеризації «квадратна» матриця виглядатиме так.

A

(BF)

C

D

E

A

—

2,5

3

3

5

(BF)

—

3,5

2,5

2,5

C

—

6

4

D

—

2

E

—

Тепер найближчою парою об’єктів є D і E. Об’єднаємо і їх.

Рис. 8.2.3. Другий крок кластеризації умовного набору з 6 об’єктів
Перебудуємо «квадратну» матрицю для чотирьох об’єктів.

A

(BF)

C

(DE)

A

—

2,5

3

4

(BF)

—

3,5

2,5

C

—

5

(DE)

—

Бачимо, що тут є дві можливості для об’єднання на рівні 2,5: приєднання A до (BF) і приєднання (BF) до (DE). Яку з них обрати?
У нас є різні варіанти, як робити такий вибір. Його можна зробити випадково. Можна прийняти якесь формальне правило, що дозволяє зробити вибір. А можна подивитися, яке з рішень дасть кращий варіант кластеризації. Скористаємося останнім варіантом. Спочатку реалізуємо перший варіант. 

Рис. 8.2.4. Перший варіант третього кроку кластеризації умовного набору з 6 об’єктів
Обравши цей варіант, ми мали б побудувати таку «квадратну» матрицю 3×3.

(ABF)

C

(DE)

(ABF)

—

3,25

3,25

C

—

5

(DE)

—

Якби ми обрали другий варіант третього кроку, у нас вийшла б наступна картина.

Рис. 8.2.5. Другий варіант третього кроку кластеризації умовного набору з 6 об’єктів
Йому відповідає така матриця 3×3:

A

C

(BFDE)

A

—

3

3,25

C

—

4

(BFDE)

—

Отримані матриці 3×3 можна порівняти і переконатися, що більш компактна група об’єктів досягається у другому варіанті. При побудові класифікації об’єктів за допомогою кластерного аналізу ми маємо прагнути виділити групи, які об’єднують схожі об’єкти. Чим вище схожість об’єктів у групах, тим краща така класифікація. Тому обираємо другий варіант третього кроку кластеризації. Звичайно, ми могли б робити подальші кроки (і розділити перший варіант ще на два підваріанти), але в кінцевому підсумку переконалися б, що найкращим варіантом третього кроку кластеризації є саме той, що показаний на рис. 8.5. Зупиняємося на ньому.
У такому випадку наступним кроком є об’єднання об’єктів A і C, показане на рис. 8.6.

Рис. 8.2.6. Четвертий крок кластеризації
Будуємо матрицю 2×2:

(AC)

(BFDE)

(AC)

—

3,625

(BFDE)

—

Тепер вже нічого вибирати не треба. Об’єднуємо два залишкових кластери на потрібному рівні. Відповідно до прийнятого стилю побудови кластерних «дерев» додаємо ще «стовбур», який простягається до рівня максимально можливої при даному наборі ознак дистанції між об’єктами.

Рис. 8.2.7. П’ятий і останній крок кластеризації
Отримана картина є деревоподібним графом (сукупністю вершин і зв’язків між ними). Цей граф побудовано так, що його лінії перетинаються (ми позначили ці перетини «мостиками»). Без зміни характеру зв’язків між об’єктами граф можна перебудувати так, щоб у ньому не було жодних перетинів. Це і зроблено на рис. 8.2.8.

Рис. 8.2.8. Кінцевий вигляд деревоподібного графа, отриманого в результаті кластеризації
Кластерний аналіз нашого умовного прикладу завершено. Нам залишилося лише зрозуміти, що саме ми отримали.
8.3. Принципові обмеження та недоліки кластерного аналізу
Як інтерпретувати граф, показаний на рис. 8.2.8? Однозначної відповіді немає. Щоб відповісти на це питання, треба розуміти, які дані і з якою метою ми кластеризували. «На поверхні» лежить висновок, що ми зафіксували, що початкова сукупність з 6 об’єктів складається з трьох пар. Дивлячись на отриманий графік, у цьому важко сумніватися. Однак чи справедливий цей висновок?
Поверніться до першої «квадратної» матриці 6×6 і переконайтеся: об’єкт E знаходився на відстані двох одиниць і від об’єкта D, і від об’єкта F. Схожість E і D у підсумковому «дереві» відображена, а те, що об’єкт E був так само близький до об’єкта F — зникло без сліду! Як це пояснити?
У результаті кластеризації, показаному на рис. 8.2.8, повністю відсутня інформація про дистанцію │EF│, там є лише інформація про дистанції │DE│ і │(BF)(DE)│!
Кожній «прямокутній» матриці у випадку, коли обрана певна метрика і спосіб приєднання, відповідає одна‑єдина «квадратна» матриця. Однак кожній «квадратній» матриці може відповідати багато «прямокутних» матриць. Після кожного кроку аналізу кожній попередній «квадратній» матриці відповідає наступна, але, виходячи з наступної, ми не змогли б відновити попередню. Це означає, що на кожному кроці кластерного аналізу незворотно втрачається певна частина інформації про різноманітність початкового набору об’єктів.
Зазначена обставина є одним із серйозних недоліків кластерного аналізу. 
Ще один з підступних недоліків кластерного аналізу згадується у статті «Ложь, нагла ложь і…», у розділі «Непорозуміння суті методу».