Вибір найкращого рішення і якість кластеризації

Основним результатом будь-якого методу кластеризації є набір кластерів. Для того щоб алгоритм кластеризації побудував цей набір, необхідно знати кількість кластерів. Змінюючи його, можна отримати багато рівноцінних (з формальної точки зрения) результатів. Тим не менш, мається на увазі, що існує невелика кількість практично корисних рішень задачі кластеризації (найчастіше одне) для заданої кількості даних. Тому, коли про кількість кластерів немає інформації (це найпоширеніша ситуація), виникає проблема вибору найкращого розбиття, а це нетривіальне завдання. Полегшити її рішення можна, додавши в алгоритм кластеризації деякий адаптивний механізм вибору оптимального рішення серед безлічі можливих. Вибір оптимального рішення будемо засновувати на понятті якості кластеризації. Якістю кластиризації назвемо ступінь наближення результату кластеризації до ідеального рішення. Оскільки ідеальне рішення задачі кластеризації невідомим але, то оцінити якість можна двома способами-експертним і формальним. Експертна вибір найкращого рішення задачі полягає в оцінці рішення фахівцями в даній предметній області. Але експертна оцінка найчастіше об'єктивно неможлива через велику обсягу і складності даних. Тому важливу роль відіграють формальні критерії оцінки якості кластеризації.

 

Використання формальних критеріїв якості в адаптивній кластеризації

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

Адаптивна складова добре поєднується з неієрархічних ал-горітмамі, особливо з алгоритмами нечіткої кластеризації. Алгоритми неієрархічних кластеризації, як правило, реалізують ітераційну процедуру наближення до розв'язку задачі. Типова процедура пошуку розв'язку вже була викладена в попередній лекції (наприклад, Fuzzy C-Means). У рядок вирішення основним результатом є матриця приналежності - на її основі виходить розбиття на кластери. Іншим важливим результа том є множина центрів кластерів - векторів, приналежність которих відповідним кластерам максимальна. Таким чином, для побудови критерію необхідно використовувати один або обидва цих результату. Побудувавши критерій (або систему критеріїв), можна буде застосовувати адаптивний механізм кластеризації.

 

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

Для ілюстрації використання адаптивної кластеризації наведемо приклад. Вихідними даними є безліч Iris dataset - класичний приклад, використовуваний для перевірки методів аналізу даних. Один клас лінійно відділимо від двох інших. Інші два класи лінійно невіддільні одне від одного. Кожен вхідний вектор має чотири атрибуту:

- Довжина чашелістніка (в сантиметрах);

- Ширина чашелістніка (в сантиметрах);

- Довжина пелюстки (в сантиметрах);

- Ширина пелюстки (у сантиметрах).

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

 

Рис.1. Залежність значень критеріїв від кількості кластерів. Червоною крапкою показані екстремальні значення критеріїв.

 

 

Рис. 2. Залежність значень критеріїв від кількості кластерів. Індекс ефективності

 

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

Висновок

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

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

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

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

· мета роботи

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

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

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

 

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

Звіт повинен відповідати вище наведеним вимогам – Вимоги до звіту. Звіт оформляється на листах формату А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 “Комп’ютерні науки”

 

Укладач: