Тема 4. Алгоритми Data Mining: кластеризація

2. Методи кластеризації

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

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

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

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

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

Одним із найбільш поширених способів проведення ітераційних процедур ось уже понад сорок років виступає метод k-середніх (розроблений у 1967 р. Дж. МакКуіном). Застосування його потребує здійснення таких кроків:

• – розділення вихідних даних досліджуваної сукупності на задану кількість кластерів;
• – обчислення багатовимірних середніх (центрів тяжіння) виділених кластерів;
• – розрахунку Евклідової відстані кожної одиниці сукупності до визначених центрів тяжіння кластерів та побудова матриці відстаней, яка ґрунтується на метриці відстаней. Використовують різні метрики відстаней, наприклад: Евклідова відстань (проста і зважена), Манхеттенська, Чебишева, Мінковського, Махалонобіса  тощо;
• – визначення нових центів тяжіння та нових кластерів.

Найбільш відомими та широко застосовуваними методами

формування кластерів є:

• – одиничного зв'язку;
• – повного зв'язку;
• – середнього зв'язку;
• – метод Уорда.

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

Метод повного зв'язку (далекого сусіда) вимагає певного рівня подібності об'єкта (не менше граничного рівня), що передбачається включити у кластер, з будь-яким іншим.

Метод середнього зв'язку ґрунтується на використанні середньої відстані між кандидатом на включення у кластер і представниками наявного кластера.

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

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

Нейронні мережі Кохонена — клас нейронних мереж, основним елементом яких є шар Кохонена. Шар Кохонена складається з адаптивних лінійних суматорів («лінійних формальних нейронів»). Як правило, вихідні сигнали шару Кохонена обробляються за правилом «переможець забирає все»: найбільший сигнал перетворюється в одиничний, решта перетворюються в нуль.

За способами настройки вхідних ваг суматорів і по розв'язуваним завданням розрізняють багато різновидів мереж Кохонена. Найбільш відомі з них:

• Мережі векторного квантування сигналів, тісно пов'язані з найпростішим базовим алгоритмом кластерного аналізу (метод динамічних ядер або K-середніх)
• Самоорганізаційні карти Кохонена (Self-Organising Maps, SOM)
• Мережі векторного квантування, які вивчаються з учителем (Learning Vector Quantization)