Розділ 1. Загальний опис кластерного аналізу.

Теоретична частина

Розділ 1. Загальний опис кластерного аналізу.

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

Кластерний аналіз (кластеризація) – це технологія, що дозволяє розподілити вхідні дані на класи – групи однотипних екземплярів вибірки, або кластери – компактні області групування екземплярів вибірки у просторі ознак. Вихідною інформацією для кластеризації є вибірка спостережень 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 із них вважаються основними: царство, тип, клас, загін, сімейство, рід, вид. Таксономії будуються в багатьох областях знань, щоб упорядкувати інформацію про велику кількість об'єктів.

 

Вибір метрики

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

Метрика вибирається залежно від:

1. простору, в якому розташовані об'єкти

2. неявних характеристик кластерів

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

d2(xi, xj) = (ᱠdk=1(xi,k − xj,k)2)1/2 = ||xi − xj||2

Отже, як же визначати «схожість» об'єктів? Для початку потрібно скласти вектор характеристик для кожного об'єкта - як правило, це набір числових значень, наприклад, ріст-вага людини. Однак існують також алгоритми, що працюють з якісними (т.зв. категорійними) характеристиками.

Після того, як ми визначили вектор характеристик, можна провести нормалізацію, щоб всі компоненти давали однаковий внесок при розрахунку «відстані». У процесі нормалізації всі значення зводяться до деякого діапазону, наприклад, [-1, -1] або [0, 1].

Нарешті, для кожної пари об'єктів вимірюється «відстань» між ними - ступінь схожості. Існує безліч метрик, ось лише основні з них:

1. Евклідова відстань

Найбільш поширена функція відстані. Являє собою геометричну відстань в багатомірному просторі:

 

(1.3)

 

2. Квадрат евклідової відстані

Застосовується для надання більшої ваги більш віддаленим один від одного об'єктам. Ця відстань обчислюється таким чином:

 

(1.4)

 

3. Відстань міських кварталів (Манхеттенська відстань)

Ця відстань є середнім різниць по координатах. У більшості випадків ця міра відстані приводить до таких же результатів, як і для звичайної відстані Евкліда. Однак для цієї міри вплив окремих великих різниць (викидів) зменшується (так як вони не зводяться в квадрат). Формула для розрахунку манхеттенської відстані:

 

(1.5)

 

4. Відстань Чебишова

Це відстань може виявитися корисною, коли потрібно визначити два об'єкти як «різні», якщо вони відрізняються по якій-небудь одній координаті. Відстань Чебишова обчислюється за формулою:

 

(1.6)

 

5. Степенева відстань

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

 

(1.7)

 

де r і p - параметри, які визначаються користувачем. Параметр p відповідальний за поступове зважування різниць за окремих координатах, параметр r відповідальний за прогресивне зважування великих відстаней між об'єктами. Якщо обидва параметри - r і p - дорівнюють двом, то ця відстань співпадає з відстанню Евкліда.

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

 

Висновок

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

Вимоги до звіту

Оформити звіт для захисту лабораторної роботи за зразком:

· назва роботи

· мета роботи

· порядок роботи

· короткі теоретичні відомості

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

 

Оформлення звіту

Звіт повинен відповідати вище наведеним вимогам – Вимоги до звіту. Звіт оформляється на листах формату А4 (також додається електронний варіант). Титульна сторінка повинна містити: назву предмету, такий заголовок:

Звіт

до лабораторної роботи №

«Кластеризація в Data Mining. Адаптивний метод кластеризації»

 

ПІБ, номер групи студента і дату виконання лабораторної роботи. Звіт подається викладачу для перевірки на занятті, які є наступними за даною лабораторною роботою.

 

 

Список рекомендованої літератури:

1. http://ru.wikipedia.org/wiki/Кластеризация

2. http://www.intuit.ru/department/database/datamining/14/1.html

3. Воронцов К.В. Алгоритмы кластеризации и многомерного шкалирования. Курс лекций. МГУ, 2007

4. Котов А., Красильников Н. Кластеризация данных. 2006

5. Мандель И. Д. Кластерный анализ. — М.: Финансы и Статистика, 1988.

6. Прикладная статистика: классификация и снижение размерности. / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин — М.: Финансы и статистика, 1989.

7. Чубукова И.А. Курс лекций «Data Mining», Интернет-университет информационных технологий —www.intuit.ru/department/database/datamining/

8. Суботін С.О. Подання й обробка знань у системах штучного інтелекту та підтримки прийняття рішень. – Запорізький національний технічний університет, 2008.

 

Контрольні питання:

1. Що таке кластеризація?

2. Що таке характеристична функція?

3. Як здійснюється вибір оптимальної характеристичної функції?

4. У чому полягає суть кластеризації?

5. В яких галузях і для чого застосовується кластеризація?

6. На чому грунтується вибір найкращого рішення?

7. Способи оцінки якості кластеризації.

8. Порядок процедури адаптивної кластеризації.

9. Перерахуйте критерії оцінки якості кластеризації.

10. Назвіть ентропійні критерії оцінки якості кластеризації.

11. Назвіть складові частини індексу ефективності.

12. Практичне застосування критеріїв якості.

Навчальне видання

“ Інтелектуальний аналіз даних ”

 

Методичні вказівки до лабораторної роботи №6 “ Кластеризація в Data Mining. Адаптивний метод кластеризації ” з дисципліни “ Інтелектуальний аналіз даних ” для студентів спеціальності 0804 “Комп’ютерні науки”

 

Укладач:

Теоретична частина

Розділ 1. Загальний опис кластерного аналізу.