Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Алгоритми ієрархічної кластеризації






Ієрархічні алгоритми дозволяють одержувати послідовну розбивку сукупності об'єктів за певним правилом. Вони підрозділяються на подільні й агломеративні.

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

В результаті утворюється ієрархічне дерево кластерів, і аналітик може вибрати ту її конфігурацію, яка краще відповідає розв'язанню задачі (Рис. 2).

Рис 2. Розбиття даних в кластери за допомогою дивізійних алгоритмів.

 

В агломеративній кластеризації також формується ієрархічне дерево, але шляхом об'єднання об'єктів в більш великі кластери з більш дрібних. Спочатку кожен об'єкт вихідної безлічі розглядається як окремий кластер, потім шукаються два об'єкти, відстань між якими мінімальна, і об'єднуються в один і т.д. Дана процедура продовжується до тих пір, поки всі об'єкти не будуть зібрані в єдиний кластер (рис. 3).

Рис 3. Розбиття даних в кластери за допомогою агломеративних алгоритмів

 

Ієрархічні алгоритми характеризуються рядом переваг у порівнянні з іншими процедурами кластерного аналізу. Відзначимо важливіші з них:

· відносна простота й змістовна ясність;

· допустимість втручання в роботу алгоритму;

· можливість графічного подання процесу класифікації у вигляді дендрограми, тобто дерева об'єднання (розбивки);

· порівняно невисока трудомісткість розрахунків.

На першому кроці даних процедур кожний об'єкт вважається окремим кластером і провадиться об'єднання (агломерація) кластерів відповідно до деякого правила, що визначає послідовність (ієрархію) такого об'єднання. Алгоритми зазначеного типу розрізняються між собою, головним чином, критеріями, які використовуються при об'єднанні кластерів. Головні з них наступні:

1. Критерій “ближнього сусіда”. В англомовній літературі даний критерій відомий як простий (одиночний) зв'язок (s ingle linkage). На кожному кроці поєднуються кластери К p і К s, відстань між найближчими об'єктами p і s яких мінімальна.

При його використанні на першому кроці поєднуються два найближчих між собою об'єкта, на другому – кластери за мінімальною відстанню між двома ближніми сусідами й т.д. Звідси й назва критерію: потрібний тільки один мінімальний зв'язок, щоб приєднати об'єкт до кластера, оскільки враховується лише одиночний, простий зв'язок з однією точкою кластера (рис. 4, 5).

Рис.4. Критерій “ближнього сусіда”

Рис. 5. Приклад критерію «ближнього сусіда»

 

2. Критерій “далекого сусіда”. В англомовній літературі даний критерій відомий як повний зв'язок (сomplete linkage). На кожному кроці поєднуються кластери К p і К s, відстань між найбільш віддаленими об'єктами p і s яких мінімальна. (Рис. 6)

Рис. 6. Приклад критерію «далекого сусіда»

 

3. Критерій “середнього зв'язку” (середньої відстані). На кожному кроці поєднуються кластери К p і К s, середнявідстань між всіма парами об'єктів яких мінімальна.

Даний критерій має дві модифікації залежно від способу розрахунку середніх відстаней між об'єктами кожного кластера: 1) критерій середньої відстані, розрахований за формулою простої середньої арифметичної (Unweigted pair-group averrage); 2) критерій середньої відстані, розрахований по формулі зваженої середньої арифметичної (Weigted pair-group averrage). У першому випадку не враховується число об'єктів у кожному кластері, тобто їхня статистична вага, а в другому – враховується.

4. Критерій “середнього сусіда” (центроїда). На кожному кроці поєднуються кластери К p і К s, відстань між центрами ваги яких мінімальна.

Даний критерій також має дві модифікації залежно від способу обліку чисельності кожного кластера: 1) критерій центроїда, розрахований без урахування числа об'єктів (статистичної ваги) поєднуваних груп (Unweigted pair-group centroid); 2) критерій центроїда, розрахований з урахуванням числа об'єктів (статистичної ваги) поєднуваних груп (Weigted pair-group centroid). (Рис. 7)

Рис. 7. Центроїд: середня перехресна подібність.

 

5. Критерій Варда (Ward’s method). Цей метод агломерації відрізняється від попередніх тим, що він ґрунтується на аналізі збільшень всередині групової варіації чинників-симптомів для всіх можливих варіантів об'єднання кластерів. Помічено, що метод Уорда приводить до утворення кластерів приблизно рівних розмірів у формі гіперсфер. (Рис. 8)

 

Рис. 8. Групове усереднення: усереднення всі показників подібності.

Для перших трьох методів існує загальна формула, запропонована А. Н. Колмогоровим для мір подібності.

 

− ∞ ≤ η ≤ +∞

де -[i, j] група з двох об'єктів (кластерів) I i J; k - об'єкт (кластер), з яким шукається схожість зазначеної групи; Ni-число елементів в кластері і; Nj-число елементів в кластері j.

Для відстаней є аналогічна формула Ланса – Вільямса.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал