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

1. Суть кластерного аналізу

Кластерний аналіз з'явився порівняно недавно – у 1939 р. Його запропонував вчений К. Тріон. Дослівно термін "кластер" в перекладі з англійської "cluster" означає гроно, згусток, пучок, група.

Особливо бурхливий розвиток кластерного аналізу відбувся у 60-х роках минулого століття. Передумовами цього були поява швидкісних комп'ютерів та визнання класифікацій фундаментальним методом наукових досліджень.

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

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

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

Основними завданнями кластерного аналізу є:

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

Кластерний аналіз потребує здійснення таких послідовних кроків:

• 1) проведення вибірки об'єктів для кластеризації;
• 2) визначення множини ознак, за якими будуть оцінюватися відібрані об'єкти;
• 3) оцінка міри подібності об'єктів;
• 4) застосування кластерного аналізу для створення груп подібних об'єктів;
• 5) перевірка достовірності результатів кластерного рішення.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Використання методів кластерного аналізу у практичній діяльності

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

Уластерний аналіз використовують для оцінки ефективності їх господарської діяльності та використання ресурсного потенціалу. При дослідженні ефективності діяльності торговельних підприємства застосування кластерного аналізу можливе на макроекономічному рівні (внутрішньої торгівлі та споживчого ринку) та на мікроекономічному рівні (суб’єктів господарювання торговельної сфери різних організаційно-правових форм власності). У разі застосування кластерного аналізу на макроекономічному рівні ефективність діяльності торговельних підприємств доцільно розглядати за такими критеріальними ознаками, які формують відповідні кластери: обсяг оптового і роздрібного товарообороту; товарна структура товарообороту (продовольчі та непродовольчі товари); кількість суб’єктів господарювання за обсягами діяльності чи чисельністю персоналу (малі, середні, великі); торговельні формати (гіпермаркети, супермаркети, дискаунтери тощо); належність капіталу (національні та міжнародні торговельні підприємства); ступінь підпорядкування (материнські та дочірні структури); територіальне (локальне) функціонування (одноосібне торговельне підприємство та торговельна мережа) тощо.

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

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

Умаркетингу це можуть бути завдання сегментації конкурентів і споживачів.

Уменеджменті прикладами задач кластеризації слугують розбивка персоналу на різні групи, кластеризація споживачів і постачальників, виявлення схожих виробничих ситуацій, за яких виникає брак. У соціології – розбивка респондентів на однорідні групи. У маркетингових дослідженнях кластерний аналіз застосовується як у теоретичних дослідженнях, так і маркетологами, що практикують і вирішують проблеми угруповання різних об’єктів (аналіз поведінки споживача, групування споживачів в однорідні класи для одержання максимально повної картини про поведінку клієнта з кожної групи й про фактори, що впливають на його поведінку). При цьому розв’язуються питання про групи клієнтів, продуктів тощо. В геоінформатиці кластерний аналіз застосовується для спрощення роботи з геоінформацією, візуалізації даних, сегментації зображень, інтелектуального пошуку; в економіці – для аналізу ринків і фінансових потоків, виведення закономірностей на фондових біржах; в астрономії – виділення груп зірок і галактик, в ДЗЗ – автоматичної обробки космічних знімків. Можна стверджувати, що кластерний аналіз добре зарекомендував себе у всіх сферах життєдіяльності людини.

Завдання кластеризації відноситься до статистичної обробки, а також до широкого класу завдань навчання без учителя, на відміну від класифікації – навчання з учителем, де класи визначені первісно.

4. Ієрархічний кластерний аналіз в R

Метод головних компонент в R (principal component analysis)