Методичні вказівки до лабораторної роботи № 6 «Кластеризація. Базові алгоритми кластеризації. Адаптивний метод кластеризації» з дисципліни «Інтелектуальний аналіз даних» для студентів базового напрямку підготовки по спеціальності “Комп’ютерні науки” (шифр 0804) Львів-2012 Лабораторна робота № 6 Кластеризація. Методи кластеризації. Адаптивний метод кластеризації 1. Теоретична частина Мета: Ознайомлення з поняттям кластерного аналізу та існуючими алгоритмами кластеризації Завдання: Дати визначення поняттю кластеризації, розглянути існуючі алгоритми кластеризації, надати детальний опис адаптивному методу кластеризації. Вступ Кластеризацією є розбиття множини даних на групи за схожими ознаками. Кластеризація використовується при вирішенні різноманітних задач обробки даних, в тому числі при розпізнаванні образів, машинному навчанні, автоматичної класифікації, виробленні стратегій керування і т. д. До цих пір не було знайдено якогось універсального алгоритму, який був би ефективним на даних різної природи. В основному використовуються ітеративні методи кластеризації, які базуються на апріорному завданні кількості кластерів і деякому виборі початкового розбиття. При цьому результат їх застосування істотно залежить від правильності оцінки кількості кластерів. Стійкість кластеризації показує, наскільки різними виходять результуючі розбиття на групи після багаторазового застосування алгоритмів кластеризації для одних і тих же даних. У даній статті наводиться короткий огляд основних методів, що дозволяють оцінити стійкість кластеризації, яка пов'язана з дійсною кількістю кластерів. Описано методи на основі індексів, які порівнюють внутрішні і зовнішні дисперсії кластерів. Також описані алгоритми, що використовують функції стійкості, які визначають відповідність призначених кластерів для вибіркових елементів множини. Обчислювальна складність відомих алгоритмів дослідження стійкості кластеризації істотно зростає при збільшенні потужності досліджуваної безлічі даних. Також більшість з них недостатньо математично обгрунтовані. У статті розглядається кілька завадостійких алгоритмів, які можуть працювати на множинах довільної структури. Завдання кластеризації Кластеризацію можна визначити як процес об'єднання даних у групи за схожими ознаками. Ця задача є однією з фундаментальних в області аналізу даних і Data Mining. Список областей, в яких застосовується кластеризація, дуже широкий: сегментація зображень, прогнозування, аналіз текстів, стиснення даних і багато інших. На сучасному етапі кластеризація часто виступає першим кроком при аналізі даних. Після виділення схожих груп застосовуються інші методи. Для кожної групи будується окрема модель. Рішення задач кластеризації використовуються в таких наукових напрямках, як статистика, розпізнавання образів, машинне навчання, автоматична класифікація, вироблення стратегій управління, моделювання філогенії організмів і інших. Однак варто розрізняти класифікацію та кластеризацію. Класифікацією називається віднесення кожного елемента в певний клас із заздалегідь відомими параметрами, отриманими на етапі навчання. При цьому число класів суворо обмежена. Кластеризація - це розбиття множини даних на кластери. Кластерами будемо називати підмножини, параметри яких заздалегідь невідомі. Кількість кластерів може бути довільним або фіксованим. Цілі кластеризації можуть бути різними залежно від особливостей конкретної прикладної задачі: - Визначити структуру безлічі даних, розбивши його на групи схожих об'єктів, спростивши подальшу обробку даних у кожному кластері окремо; - Скоротити обсяг збережених даних, залишивши по одному найбільш типовому представнику від кожного кластера; - Виділити нетипові об'єкти, які не підходять до жодного з кластерів. Основна суть алгоритмів кластеризації полягає в наступному. Є навчальна послідовність (набір даних) {x1, ..., xn} Є X і функція відстані між об'єктами р(х, х'). Потрібно розбити послідовність на непересічні підмножини (які називаються кластерами) так, щоб ...