Приклади реалізації неієрархічної кластеризації даних.

Приклад 1:

Нижче на рисунку 2.1. наведено приклад роботи алгоритму к-середніх для k = 2; (k-кількість кластерів)

Рис. 2.1. Приклад роботи алгоритму к-середніх для k = 2

Приклад №2:

Задано довільні точки, координати яких занесені в таблицю 2.1:

Таблиця 2.1.

Наші точки графічно відображені на рис.2.2.

Рис. 2.2. Графічне відображення точок

Нехай число k=2, тоді вибираємо довільні точки, які будуть центрами наших кластерів. Нехай це будуть точки під номерами 6 і 9. Точки будуть належати до того кластера, до центру якого вони ближче розташовані.(рис. 2.3.)

Відстань між центром і точкою обчислюємо за формулою:

(2.1)

Рис. 2.3. Центри кластерів

В нас утворилося 2 кластери:

Таблиця 2.2

Таблиця 2.3

Тепер перераховуємо кластерні центри.

Щоб вирахувати координати нового центру кластера () використовуємо формули:

(2.2)

(2.3)

Координати сформованих центрів для кластера 1 (7, 125; 7, 75), для кластера 2 (16, 75; 2, 5).

Перевіряємо чи не змінилось приналежність точок до кластерів за допомогою формули 2.1.(рис.2.4)

Рис. 2.4. Перевірка на зміну точок

В нашому випадку кластери не змінились, а отже алгоритм k-середніх рахується завершеним. Сформувалось 2 кластери:

Таблиця 2.4

Таблиця 2.5

3. Порядок виконання роботи

3.1. Ознайомитися з теоретичною частиною.

3.2. Виконати реалізацію алгоритму неієрархічної кластеризації на основі свого індивідуального завдання.

3.3. Оформити звіт по результатах виконаної роботи.

Варіанти індивідуальних завдань

Провести неієрархічну кластеризацію точок використовуючи алгоритм k-середніх, за центри кластерів використовувати точки 0N та 1K (де N і K – передостання і остання цифри студентського квитка, відповідно).

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

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

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

· мета роботи;

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

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

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

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

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

Звіт

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

«Кластеризація даних.

Алгоритми неієрархічної кластеразації даних.»

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

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

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

2. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.

3. Хайдуков Д. С. Применение кластерного анализа в государственном управлении// Философия математики: актуальные проблемы. – М.: МАКС Пресс, 2009.

4. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2.

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

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

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

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

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

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

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

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

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

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

4. Які основні завдання вирішує кластеризація?

5. Перелічіть основні цілі кластеризації.

6. Опишіть основні проблеми кластеризації?

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

8. Перелічіть основні алгоритми кластеризації.

9. Опишіть алгоритм k-means.

10. Назвіть переваги та недоліки алгоритму k-means.

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

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

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

Укладач: