Ознайомлення із поняттям кластерний аналіз.

Кластерний аналіз (кластеризація) – це технологія, що дозволяє розподілити вхідні дані на класи – групи однотипних екземплярів вибірки, або кластери – компактні області групування екземплярів вибірки у просторі ознак. Вихідною інформацією для кластеризації є вибірка спостережень x={xsj}, де xsj – значення j-ої ознаки s-го екземпляра вибірки, s = 1, 2, …,S; j=1, 2, …, N, S – кількість екземплярів вибірки, N – кількість ознак, що характеризують екземпляри вибірки.

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

Методи кластеризації можна класифікувати на чіткі та нечіткі. Чіткі методи кластеризації розбивають вихідну множину об’єктів x на декілька непересічних підмножин. При цьому будь-який об’єкт із x належить тільки одному кластеру.

Нечіткі методи кластерного аналізу дозволяють будь-якому екземпляру одночасно належати до всіх визначених кластерів, але з різним ступенем.

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

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

Більшість методів нечіткої кластеризації спрямовані на мінімізацію суми:

 

(1.1)

 

при виконанні умов:

 

V>1,

 

де S – кількість екземплярів, N – кількість параметрів, що описують один екземпляр (або кластер), V – кількість кластерів; x=(x1, x2,..., xS)T – це матриця входів для екземплярів навчаючої вибірки, xs = (xs1, xs2,..., xsN) – входи s-го екземпляра, s=1,2,...,S, u = (u1, u2,..., uS)T – матриця приналежностей екземплярів до кожного з кластерів, us = (us1, us2,..., usV) – вектор приналежностей s-го екземпляра до кожного з кластерів, usv∈[0,1], C =(C1,C2,...,CV)T – матриця центрів кластерів, Cv = (C1v,C2v,...,CvN) – центр v-го кластера, v = 1, 2,..., V, m > 1 – ступінь нечіткості отриманого розподілу (зазвичай обирається рівним 2), d(xs,Cv) – відстань між s-м екземпляром та центром v-го кластера.

Координати центрів кластерів визначають за формулою:

 

(1.2)

 

Найбільш простим є метод, в якому відстань між екземпляром та кластером знаходиться як евклідова відстань:

 

(1.3)

 

Такий метод шукає кластери як сфери однакового розміру.

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

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

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

 

Загальна схема кластеризації

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

1. Виділення характеристик

2. Визначення метрики

3. Розбиття об’єктів на групи

4. Представлення результатів

 

Цілі кластеризації

Цілі кластеризації можуть бути різними залежно від особливостей конкретної прикладної задачі:

• Зрозуміти структуру множини об'єктів X^ℓ, розбивши його на групи схожих об'єктів. Спростити подальшу обробку даних і прийняття рішень, працюючи з кожним кластером окремо (стратегія «розділяй і володарюй»).

• Скоротити обсяг даних, що зберігаються в разі надвеликої вибірки X^ℓ, залишивши по одному найбільш типовому представнику від кожного кластера.

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

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

У всіх цих випадках може застосовуватися ієрархічна кластеризація, коли великі кластери дробляться на більш дрібні, ті в свою чергу дробляться ще дрібніше, і т.д. Такі завдання називаються завданнями таксономії (taxonomy). Результатом таксономії є не просте розбиття множини об'єктів на кластери, а древоподібна ієрархічна структура. Замість номера кластера об'єкт характеризується перерахуванням всіх кластерів, яким він належить, від великого до дрібного. Класичним прикладом таксономії на основі подібності є систематизація живих істот, запропонована Карлом Ліннеєм в середині XVIII століття. У сучасному поданні біологічна ієрархія має близько 30 рівнів, 7 із них вважаються основними: царство, тип, клас, загін, сімейство, рід, вид. Таксономії будуються в багатьох областях знань, щоб упорядкувати інформацію про велику кількість об'єктів.