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

1. Інтелектуальний аналіз даних

Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
1/14

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

Л е к ц і я 7 . М е т о д и Кластеризації
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
2/100

3. Лекція 7.Методи Кластеризації

Л е к ц і я 7 . М е т о д и Кластеризації
Зміст лекції:
1.Кластеризація. Основні Поняття
2 Міри Відстаней
3.Классифікація Методів Кластерного Аналізу
4.Ієрархічні Методи Кластерного Аналізу
5.Ітеративні Методи Кластерного Аналізу
6. Нечітка Кластерізація
7.Деякі Функції Кластер-аналізу У Середовищі
Matlab
8. Нейронні мережі для кластерного аналізу
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
3/100

4.

1.Кластеризація.
Основні поняття
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
4/100

5. 1.Кластеризація. Основні поняття

Термін кластерний аналіз, вперше введений Тріоном
((Tryon) ) в 1939 році, включає в себе більше 100 різних
алгоритмів.
кластерний аналіз паралельно розвивався в кількох
напрямках, таких як біологія, психологія, ін., тому у
більшості методів існує по два і більше назв.
Це істотно ускладнює роботу при використанні
кластерного аналізу.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
5/100

6. 1.Кластеризація. Основні поняття

Кластеризація (або кластерний аналіз) - це задача розбиття множини об'єктів на групи,
які називаються кластерами. Усередині кожної групи повинні виявитися «схожі» об'єкти,
а об'єкти різних групи повинні бути якомога більш відмінні. Головна відмінність
кластеризації від класифікації полягає в тому, що перелік груп чітко не заданий і
визначається в процесі роботи алгоритму.
На відміну від завдань класифікації, кластерний аналіз не вимагає апріорних припущень
про набір даних, не накладає обмеження на уявлення досліджуваних об'єктів, дозволяє
аналізувати показники різних типів даних (інтервальні дані, частоті, бінарні дані).
При цьому необхідно пам'ятати, що змінні повинні вимірюватися в порівнянних шкалах.
Кластерний аналіз дозволяє скорочувати розмірність даних, робити їх наочними.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
6/100

7. 1.Кластеризація. Основні поняття

Відмінність від класифікації
1.
Відповіді НЕВІДОМІ
2.
Немає чіткої міри якості рішень
3.
Задачі поставлені вкрай нечітко
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
?
7/100

8. 1.Кластеризація. Основні поняття Технологія кластерного аналізу

Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
8/100

9. 1.Кластеризація. Основні поняття

Застосування кластерного аналізу в загальному вигляді зводиться до наступних етапів:
1. Відбір вибірки об'єктів для кластеризації.
2. Визначення безлічі змінних, за якими будуть оцінюватися об'єкти у вибірці. При необхідності нормалізація значень змінних.
3. Обчислення значень міри схожості між об'єктами.
4. Застосування методу кластерного аналізу для створення груп схожих об'єктів (кластерів).
5. Представлення результатів аналізу.
Після отримання та аналізу результатів можливе корегування обраної метрики і методу
кластеризації до отримання оптимального результату.
.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
9/100

10. 1.Кластеризація. Основні поняття

Розглянемо приклад процедури кластерного аналізу.
маємо набір даних А, що складається з 14-ти прикладів, у яких є по дві
ознаки X і Y
Набір Даних
№
ознака
приклад
X
у
1
27
2
11
3
25
4
36
5
35
6
10
7
11
8
36
9
10
11
12
13
14
26
26
9
33
27
10
ознака
Y
19
46
15
27
25
43
44
24
14
14
45
23
16
47
Дані в табличній формі
не носять інформативний
характер.
Представимо увигляді
діаграми розсіювання
Діаграма розсіювання змінних X і Y
Бачимо кілька груп "схожих" прикладів.
Приклади (об'єкти), які за значеннями X і Y
"схожі" один на одного, належать до однієї групи (кластеру);
об'єкти з різних кластерів не схожі один на одного.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
10/100

11. 1.Кластеризація. Основні поняття

Завдання на сам. роботу
Набір Даних
№
ознака
приклад
X
у
1
27
2
11
3
25
4
36
5
35
6
10
7
11
8
36
9
10
11
12
13
14
26
26
9
33
27
10
ознака
Y
19
46
15
27
25
43
44
24
14
14
45
23
16
47
Виконати
За допомогою
Мережі КОХОНЕНА
Y лекції “ШТ.Інтелект”
(див
Перевірити якість , роздруківку
“вклеїти” в конспект
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
11/100

12. 1.Кластеризація. Основні поняття

Критерієм для визначення схожості та відмінності кластерів є відстань між точками на діаграмі
розсіювання. Ця схожість можна "виміряти", воно дорівнює відстані між точками на графіку.
способів визначення міри відстані між кластерами, званої ще мірою близькості, існує кілька.
Найбільш поширений спосіб - обчислення евклидова відстані між двома точками я і J на площині,
коли відомі їхні X і координати Y:
Примітка: щоб дізнатися відстань між двома точками, треба взяти різницю їх координат по кожній
осі, звести її в квадрат, скласти отримані значення для всіх осей і витягти квадратний корінь з суми .
Коли осей більше, ніж дві, відстань розраховується таким чином: сума квадратів різниці координат
складається з стількох доданків, скільки осей (вимірювань) присутній в нашому просторі. Наприклад,
якщо нам потрібно знайти відстань між двома точками в просторі трьох вимірів (представлена
​ситуація така на рис 13.2. ), формула набуває вигляду:
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
Відстань між двома точками
12/100
в просторі трьох вимірів

13. 1.Кластеризація. Основні поняття

Кластер має характеристики: центр, радіус, середньоквадратичне
відхилення, розмір кластера.
Центр кластера - це середнє геометричне місце точок в просторі змінних.
Радіус кластера - максимальне відстань точок від центру кластера.
Кластери можуть бути перекриваються.
У цьому випадку неможливо за допомогою математичних процедур однозначно
віднести об'єкт до одного з двох кластерів.
Такі об'єкти називають спірними.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
13/100

14. 1.Кластеризація. Основні поняття

Спірний об'єкт - це об'єкт, який у міру подібності може
бути віднесений до кількох кластерів.
Розмір кластера може бути визначений або по радіусу
кластера, або по середньоквадратичному відхиленню
об'єктів для цього кластера.
Об'єкт відноситься до кластеру, якщо відстань від
об'єкта до центру кластера менше радіуса кластера.
Якщо ця умова виконується для двох і більше кластерів,
об'єкт є спірним.
Неоднозначність може бути усунена
експертом або аналітиком.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
14/100

15. 1.Кластеризація. Основні поняття

Робота кластерного аналізу спирається на два припущення.
Перше припущення - що розглядаються ознаки об'єкта в
принципі допускають бажане розбиття пулу (сукупності)
об'єктів на кластери.
Друге припущення - правильність вибору масштабу або
одиниць вимірювання ознак
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
15/100

16. 1.Кластеризація. Основні поняття

Вибір масштабу в кластерному аналізі має велике значення.
Приклад. Уявімо собі, що дані ознаки х в наборі даних А на два порядки більше
даних ознаки у: значення змінної х знаходяться в діапазоні від 100 до 700, а
значення змінної у - в діапазоні від 0 до 1.
Тоді, при розрахунку величини відстані між точками, що відбивають стан
об'єктів в просторі їх властивостей, змінна, що має великі значення, тобто
змінна х, буде практично повністю домінувати над змінною з малими
значеннями, тобто змінної у. Таким чином через неоднорідність одиниць виміру
ознак стає неможливо коректно розрахувати відстані між точками.
Ця проблема вирішується за допомогою попередньої стандартизації змінних.
стандартизація ( standardization) або нормування ( normalization), призводить
значення всіх перетворених змінних до єдиного діапазону значень шляхом
висловлення через відношення цих значень до якоїсь величини, що відбиває певні
властивості конкретного ознаки.
16/100
Інтелектуальний аналіз даних

17. 2. Міри відстаней

17/100
Інтелектуальний аналіз даних

18. 2 Міри відстаней

Отже, як же визначати «схожість» об'єктів? Для початку потрібно
скласти вектор характеристик для кожного об'єкта - як правило, це
набір числових значень, наприклад, зростання-вага людини. Однак
існують також алгоритми, що працюють з якісними (т.зв.
категорійними) характеристиками.
Після того, як ми визначили вектор характеристик, можна провести
нормалізацію, щоб всі компоненти давали однаковий внесок при
розрахунку «відстані». У процесі нормалізації все значення приводяться
до деякого діапазону, наприклад, [1, -1] або [0, 1].
18/100
Інтелектуальний аналіз даних

19. 2 Міри відстаней

Для кожної пари об'єктів вимірюється «відстань» між ними - ступінь схожості. Існує безліч метрик,
ось лише основні з них:
1. Евклідова відстань
Найбільш поширена функція відстані. Являє собою геометричну відстань в багатовимірному просторі:
2.Квадрат евклидової відстані
Застосовується для додання більшої ваги більш віддаленим один від одного об'єктів. Це відстань
обчислюється таким чином:
19/100
Інтелектуальний аналіз даних

20. 2 Міри відстаней

3.Відстань міських кварталів (Манхеттенська відстань)
Це відстань є середнім різниць по координатах. У більшості випадків ця міра
відстані приводить до таких же результатів, як і для звичайного відстані
Евкліда. Однак для цього заходу вплив окремих великих різниць (викидів)
зменшується (тому що вони не зводяться в квадрат).
Формула
для розрахунку
4.відстань Чебишева
Ця відстань може виявитися корисним, коли потрібно визначити два об'єкти як «різні»,
якщо вони розрізняються за якоюсь однією координаті.
обчислюється за формулою:
20/100
Інтелектуальний аналіз даних

21. 2 Міри відстаней

5. Ступенева відстань
Застосовується в разі, коли необхідно збільшити або зменшити вагу, що
відноситься до розмірності, для якої відповідні об'єкти сильно відрізняються.
обчислюється
за такою
формулою:
де r і p - параметри, що визначаються користувачем.
Параметр p відповідальний за поступове зважування різниць за окремими координатами,
параметр r відповідальний за прогресивне зважування великих відстаней між об'єктами.
Якщо обидва параметри - r і p - дорівнюють двом, то ця відстань
збігається з відстанню Евкліда
6.Відсоток незгоди.
Ця відстань обчислюється, якщо дані
є категоріальними.
21/100
Інтелектуальний аналіз даних

22. 2 Міри відстаней

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

23.

3.Классифікація методів
кластерного аналізу
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
23/100

24. 3.Классифікація методів кластерного аналізу

Існує безліч підходів і ознак класифікації
алгоритмів кластеризації.
Розглянемо лише деякі з підходів
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
24/100

25. 3.Классифікація методів кластерного аналізу

За ознакою 1.
Ієрархічні
плоскі.
Ієрархічні алгоритми (так звані алгоритми таксономії)
будують не одне розбиття вибірки на непересічні
кластери, а систему вкладених розбиттів.
на виході - дерево кластерів, коренем якого є вся
вибірка, а листям - найбільш дрібні кластери.
Плоскі алгоритми будують одне розбиття об'єктів на
кластери.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
25/100

26. 3.Классифікація методів кластерного аналізу

За ознакою 2.
1.Чіткі
2. Нечіткі.
1.Чіткі ( такі, що неперетитаються) алгоритми кожному об'єкту вибірки
ставлять у відповідність номер кластера,
кожен об'єкт належить тільки одному кластеру.
2.Нечіткі ( такі, що перетитаються) алгоритми кожному об'єкту
ставлять у відповідність набір значень, що показують ступінь , з яким
можна віднести об'єкти до кластерів.
кожен об'єкт відноситься до кожного кластеру з певною ймовірністю.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
26/100

27. 3.Классифікація методів кластерного аналізу один з варіантів

Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
27/100

28. 3.Классифікація методів кластерного аналізу один з варіантів

Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
28/100

29. 4.Ієрархічні методи кластерного аналізу

Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
29/100

30. 4.Ієрархічні методи кластерного аналізу

Суть
ієрархічної
кластеризації
в послідовному об'єднанні
менших кластерів в великі
або
поділі великих кластерів на менші.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
30/100

31. 4.Ієрархічні методи кластерного аналізу

1. Ієрархічні агломеративні методи
(Agglomerative Nesting, AGNES)
Ця група методів характеризується послідовним об'єднанням
вихідних елементів і відповідним зменшенням числа кластерів.
На початку роботи алгоритму всі об'єкти є окремими
кластерами.
На першому кроці найбільш схожі об'єкти об'єднуються в
кластер.
На наступних кроках об'єднання триває до тих пір, поки всі
об'єкти не будуть складати один кластер.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
31/100

32. 4.Ієрархічні методи кластерного аналізу

2. Ієрархічні дивізімні (подільні) методи (DIvisive ANAlysis, DIANA)
є логічною протилежністю агломеративним методам.
На початку роботи алгоритму всі об'єкти належать одному кластеру,
який на наступних кроках ділиться на менші кластери,
в результаті утворюється послідовність розщеплення груп.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
32/100

33. 4.Ієрархічні методи кластерного аналізу

Принцип
роботи описаних вище груп методів у вигляді
дендрограмми
Дендрограма агломеративного і дівізімних
методів
© ЄА. Лавров, 2015-2019
Інтелектуальний аналіз даних
33/100

34. 4.Ієрархічні методи кластерного аналізу

Ієрархічні методи кластеризації розрізняються правилами
побудови кластерів.
Як правила виступають критерії, які використовуються при
вирішенні питання
про "схожість" об'єктів при їх об'єднанні в групу
(агломеративні методи)
або
поділу на групи (дівізімні методи).
Ієрархічні методи
використовуються при невеликих обсягах наборів даних.
Перевага - наочність.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
34/100

35. 4.Ієрархічні методи кластерного аналізу

Ієрархічні алгоритми пов'язані з побудовою дендрограмм (від грецького
dendron - "дерево"), які є результатом ієрархічного кластерного аналізу.
Дендрограмма описує близькість окремих точок і кластерів один до одного,
представляє в графічному вигляді послідовність об'єднання (поділу) кластерів.
Дендрограмма ( dendrogram) - деревоподібна діаграма,
що містить n рівнів,
кожен з яких відповідає одному з кроків процесу послідовного укрупнення
кластерів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
35/100

36. 4.Ієрархічні методи кластерного аналізу

Дендрограму також називають деревовидною схемою, деревом об'єднання
кластерів, деревом ієрархічної структури.
Дендрограмма є вкладене угруповання об'єктів, яка змінюється на різних рівнях ієрархії.
Існує багато способів побудови дендрограмм. В дендрограмі об'єкти можуть
розташовуватися вертикально або горизонтально.
приклад вертикальної дендрограми.
Числа 11, 10, 3 і т.д. відповідають номерам об'єктів або спостережень
вихідної вибірки. Ми бачимо, що на першому етапі кожне
спостереження представляє один кластер (вертикальна лінія), на
другому кроці спостерігаємо об'єднання таких спостережень: 11 і 10; 3,
4 і 5; 8 і 9; 2 і 6. На другому кроці триває об'єднання в кластери:
спостереження 11, 10, 3, 4, 5 і 7, 8, 9. Даний процес триває до тих пір,
поки всі спостереження не об'єднаються в один кластер.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
36/100

37. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку
Коли кожен об'єкт являє собою окремий кластер, відстані між цими
об'єктами визначаються обраної мірою.
Виникає наступне питання - як визначити відстані між кластерами?
Існують різні правила, звані методами об'єднання або зв'язку для двох
кластерів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
37/100

38. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку
Метод найближчого сусіда або одиночного зв'язку.
Відстань між двома кластерами визначається відстанню між двома найбільш
близькими об'єктами (найближчими сусідами) в різних кластерах.
1.
Дозволяє виділяти кластери як завгодно складної форми за умови, що різні
частини таких кластерів з'єднані ланцюжками близьких один до одного
елементів.
Кластери представляються довгими "ланцюжками" або "волокнистими"
кластерами, "зчепленими разом" тільки окремими елементами, які випадково
опинилися ближче інших один до одного.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
38/100

39. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку.
2. Метод найбільш віддалених сусідів або повний зв'язок.
Відстані між кластерами визначаються найбільшою відстанню між будь-якими
двома об'єктами в різних кластерах (тобто "найбільш віддаленими сусідами").
Метод добре використовувати, коли об'єкти дійсно виходять з різних "гаїв".
Якщо ж кластери мають в деякому роді подовжену форму або їх природний тип є
«Ланцюговий",
цей
метод
не слід
Інтелектуальний аналіз даних
в и к о р и с т о в у в а т39/100
и.
© ЄА. Лавров, 2015-2019

40. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку.
3. Метод Варда (Ward's method).
Як відстань між кластерами береться приріст суми квадратів відстаней об'єктів
до центрів кластерів, що отримується в результаті їх об'єднання (Ward, 1963).
На відміну від інших методів кластерного аналізу для оцінки відстаней між
кластерами, тут використовуються методи дисперсійного аналізу.
На кожному кроці алгоритму об'єднуються такі два кластери, які призводять до
мінімального збільшення цільової функції, тобто внутрішньогрупової суми
квадратів.
Цей метод направлений на об'єднання близько розташованих кластерів і
"прагне" створювати кластери малого розміру.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
40/100

41. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку.
4. Метод невиваженого попарного середнього (unweighted pair-group
method using arithmetic averages, UPGMA (Sneath, Sokal, 1973)).
Як відстань між двома кластерами береться середня
відстань між усіма парами об'єктів в них.
Слід використовувати, якщо
об'єкти дійсно виходять з різних "гаїв",
у випадках присутності кластерів типу, "ланцюжка«
при припущенні нерівних розмірів кластерів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
41/100

42. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку
5.Метод зваженого попарного середнього (weighted pair-group method
using arithmetic averages, WPGM A (Sneath, Sokal, 1973)).
Схожий на метод невиваженого попарного середнього,
різниця полягає лише в тому, що тут в якості вагового коефіцієнта
використовується розмір кластера (число об'єктів, що містяться в
кластері).
Рекомендується використовувати
саме при наявності припущення
про кластери різних розмірів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
42/100

43. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку
6. Незважений центроїдний метод (метод невиваженого попарного центроїдного
усереднення - unweighted pair-group method using the centroid average (Sneath
and Sokal, 1973)).
Як відстань між двома кластерами береться
відстань між їх центрами тяжкості.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
43/100

44. 4.Ієрархічні методи кластерного аналізу

Методи об'єднання або зв'язку
7.Зважений центроїдний метод (метод зваженого попарного
центроїдного усереднення - weighted pair-group method using
the centroid average, WPGMC (Sneath, Sokal 1973)).
Метод схожий на попередній,
різниця полягає в тому, що для обліку різниці між розмірами кластерів
(числі об'єктів в них), використовуються ваги.
Використання
у випадках, якщо є припущення
щодо істотних відмінностей
в розмірах кластерів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
44/100

45. 4.Ієрархічні методи кластерного аналізу

Побудова в Матлаб
http://matlab.exponenta.ru/statist/book2/14/linkage.php
Вив
Чи
ти
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
45/100

46.

5.Ітеративні методи
кластерного аналізу
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
46/100

47. 5.Ітеративні методи кластерного аналізу

При
великій
кількості
спостережень
кластерного аналізу не придатні.
ієрархічні
методи
У таких випадках використовують неієрархічні методи, основані
на поділі, які представляють собою
ітеративні методи
дроблення вихідної сукупності.
У процесі поділу нові кластери формуються до тих пір,
поки не буде виконано
правило зупинки.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
47/100

48. 5.Ітеративні методи кластерного аналізу

Неієрархічна кластеризація полягає в поділі набору даних на
певну кількість окремих кластерів.
Існує два підходи.
Перший полягає у визначенні меж кластерів як найбільш
щільних ділянок в багатовимірному просторі вихідних даних,
тобто
визначення кластера там, де є велика "згущення
точок".
Другий підхід полягає в мінімізації міри відмінності об'єктів
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
48/100

49. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means)
Найбільш поширений серед неієрархічних методів
(також званий швидким кластерним аналізом)
Повний опис алгоритму можна знайти в роботі Хартігана
і Вонга (Hartigan and Wong, 1978).
На відміну від ієрархічних методів,
які не вимагають попередніх припущень щодо числа
кластерів,
для використання k-means
необхідно мати гіпотезу про
найбільш ймовірне кількості кластерів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
49/100

50. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means)
будує k кластерів, розташованих на можливо великих відстанях
один від одного.
Вимога алгоритма k-середніх, - наявність припущень (гіпотез)
щодо числа кластерів, при цьому вони повинні бути різні
настільки, наскільки це можливо.
Вибір числа k може базуватися на результатах попередніх
досліджень, теоретичних міркуваннях або інтуїції.
Загальна ідея алгоритму:
задане
фіксоване
число
k
кластерів
спостереження
зіставляються кластерам так,
що середні в кластері (для всіх змінних)
максимально можливо
відрізняються один від одного.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
50/100

51. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means) опис алгоритму
1. Початковий розподіл об'єктів по кластерам.
Вибирається число k, і на першому кроці ці точки вважаються
"центрами" кластерів. Кожному кластеру відповідає один центр.
Вибір початкових центроїдів може здійснюватися в такий спосіб:
вибір k-спостережень для максимізації початкової відстані;
випадковий вибір k-спостережень;
вибір перших k-спостережень.
В результаті кожен об'єкт призначений певного кластеру.
.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
51/100

52. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means) опис алгоритму
2. Ітеративний процес.
обчислюються центри кластерів, якими потім і далі вважаються
покоординатно середні кластерів.
Об'єкти знову перерозподіляються.
Процес обчислення центрів і перерозподілу об'єктів триває до тих пір,
поки не виконана одна з умов:
кластерні центри стабілізувалися, тобто всі спостереження належать
кластеру, до якого належали до поточної ітерації;
число ітерацій дорівнює максимальному числу ітерацій.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
52/100

53. 4.Ієрархічні методи кластерного аналізу

.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
53/100

54. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means)
. Приклад роботи алгоритму k-середніх (k = 2)
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
54/100

55. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means) опис алгоритму
Вибір числа кластерів є складним питанням.
Якщо немає припущень щодо цього числа,
рекомендують
створити
2 кластера,
потім 3,
4,
5
і т.д., порівнюючи отримані результати
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
55/100

56. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means)
Перевірка якості кластеризації
Після отримань результатів кластерного аналізу методом k-середніх слід перевірити правильність
кластеризації (тобто оцінити, наскільки кластери відрізняються один від одного).
Для цього розраховуються середні значення для кожного кластера.
При гарній кластеризації повинні бути отримані сильно відмінні середні для всіх вимірювань або хоча
б більшої їх частини.
переваги алгоритму k-середніх:
простота використання;
швидкість використання;
зрозумілість і прозорість алгоритму.
недоліки алгоритму k-середніх:
занадто чутливий до викидів, які можуть спотворювати середнє. Можливим вирішенням цієї
проблеми є використання модифікації алгоритму - алгоритм k-медіани;
алгоритм може повільно працювати на великих базах даних. Можливим вирішенням цієї проблеми
є використання вибірки даних.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
56/100

57. 5.Ітеративні методи кластерного аналізу

1.Алгоритм k-середніх (k-means)
Опис функції kmeans в Mallab
http://matlab.exponenta.ru/statist/book2/14/kmeans.php
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
57/100

58. 5.Ітеративні методи кластерного аналізу

2.Алгоритм PAM
(partitioning around Medoids)
PAM є модифікацією алгоритму k-середніх,
алгоритмом k-медіани (k-medoids, або k-medians).
Алгоритм менш чутливий до шумів і викидів даних,
ніж алгоритм k-means,
оскільки
медіана менше
піддається впливам викидів.
Використання
PAM ефективний для невеликих баз даних,
не слід використовувати для великих наборів даних.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
58/100

59. 5.Ітеративні методи кластерного аналізу

3 . А л г о р и т м и р о д и н и FOREL
FOREL (Формальний Елемент) — оснований
основанный на идеї об’ єднання я в один кластер об’єктів в
місцях їх найбільшого скупчення
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%
82%D0%BC%D1%8B_%D1%81%D0%B5%D0%BC%D0%B5%D0%B9%D1%81%D1%82%
D0%B2%D0%B0_FOREL
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
59/100

60. 5.Ітеративні методи кластеризації 4Алгоритм HCM (Hard C – Means).

Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
60/100

61.

6. нечітка кластеризація
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
61/100

62. 6.нечітка кластеризація

Чітка (непересічна) кластеризація - кластеризація, яка кожен об’єкт
відносить тільки одного кластеру.
Нечітка кластеризація - кластеризація, при якій для кожного об’єкта
визначається дійсне значення, що показує ступінь
приналежності об’єкта до кожного кластеру
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
62/100

63. 6.нечітка кластеризація

1. Алгоритм Fuzzy C-means. – Базовий
Призначення: кластеризація великих наборів числових даних.
Переваги: нечіткість при визначенні об'єкта в кластер дозволяє
визначати об'єкти, які знаходяться на кордоні, в кластери.
Недоліки: обчислювальна складність, завдання кількості кластерів,
виникає невизначеність
з об'єктами, які віддалені від центрів всіх кластерів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
63/100

64. 6.нечітка кластеризація в Маtlab

6.нечітка кластеризація
в
М
а
t
l
a
b
функція
findcluster
для
метода нечітких с-середних (FCM )
метода субтрактивної кластеризации
(subtractive clustering)
Викликає
Графичний
інтерфейс програми
Нечітк.
кластеризації
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
64/100

65.

7. Дея к і Функції
Кластер - аналізу
У Середовищі
Matlab
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
65/100

66. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
Модуль Fuzzy Logic Toolbox пакету MATLAB містить функції для
виділення кластерів.
Функція subclust визначає координати центрів кластерів шляхом
чіткої кластеризації зі зменшенням кількості кластерів.
Функція subclust знаходить оптимальну точку даних для
визначення центра кластера ґрунтуючись на щільності оточення
точок даних.
Усі точки даних у межах відстані RADII до цієї точки
видаляються, щоб визначити наступний кластер даних та його
центр.
Цей процес повторюється поки усі дані не знаходяться у межах
відстані RADII до центра кластера.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
66/100

67. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
[C] = SUBCLUST (X, RADII) кластеризує точки даних SxN матриці
X, де S - кількість точок даних, N - кількість координат точок
даних, RADII - значення між 0 та 1, що визначає розмір кластера
в кожному з вимірювань даних, приймаючи, що дані
знаходяться у межах діапазону [0, 1] (Встановлення меншого
радіуса кластера буде звичайно створювати більше менших за
розміром кластерів.
Коли RADII є скаляром, він застосовується до усіх вимірів
даних.
Коли RADII є вектором, він має окреме значення для кожного
виміру даних), та повертає центри кластерів як рядки матриці C,
що має розмір VxN, де V - кількість кластерів.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
67/100

68. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
[C] = SUBCLUST (..., XBOUNDS) також визначає матрицю
XBOUNDS, розміром 2xN, що використовується для
нормалізації даних X у діапазон [0, 1].
Кожний стовпець XBOUNDS містить мінімальні та
максимальні значення для відповідної розмірності
даних.
Якщо XBOUNDS - порожня матриця або не
використовується, тоді за замовчуванням
використовуються мінімальні та максимальні значення
даних X.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
68/100

69. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
[C] = SUBCLUST(...,OPTIONS) визначає вектор для зміни значень
за замовчуванням параметрів алгоритму:
OPTIONS(1) - коефіцієнт, що використовується для множення на
значення RADII для визначення осередку центру кластера, у
межах якого існування інших центрів кластерів заборонено;
OPTIONS(2) - коефіцієнт прийняття, що встановлює потенціал як
частку потенціалу центра першого кластера, вище якої інша
точка даних буде прийнята як центр кластера;
OPTIONS(3) - коефіцієнт відхилення, що встановлює потенціал
як частку потенціалу центра першого кластера, нижче якої інша
точка даних буде відхилена як центр кластера;
OPTIONS(4) - ознака відображення поточної інформації, якщо не
встановлена як 0.
Значеннями вектора OPTIONS за замовчуванням є [1.25 0.5 0.15
0].
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
69/100

70. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
Приклад використання subclust.
X1
= 10*rand(50,1);
X2 = 5*rand(50,1);
X3 = 20*rand(50,1)-10;
X = [X1 X2 X3]; % генеруємо вибірку даних
[C] = subclust(X,0.5) % знаходимо центри кластерів
C=
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
2.7294
1.2533
6.2250
6.0986
2.1756
1.0976
0.7735
8.9292
1.4203
2.0109
2.6531
0.8750
3.7906
4.6787
4.9397
0.5296
1.2024
0.1222
3.5947
-6.3852
7.3350
0.5009
2.8412
-6.7286
7.0453
-2.1848
-5.4266
70/100

71. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
Ф у н к ц і я f c m здійснює нечітку кластеризацію на основі методу
нечітких с-середніх та має формат виклику:
[CENTER, U, OBJ_FCN] = fcm(DATA, N_CLUSTER,OPTIONS)
де N_CLUSTER - кількість кластерів в наборі даних масиву DATA, який
має розміри SxN,
S - кількість точок даних,
N - кількість координат точок,
CENTER - матриця з координатами центрів кластерів (кластери містяться
у рядках, ознаки - у стовпцях),
U - матриця функції приналежності, що містить рівні приналежності
кожної точки масиву DATA до кожного кластера,
OBJ_FCN - значення цільової функції для центрів кластерів, OPTIONS необов'язковий параметр, що задає вектор опцій для процесу
кластеризації: OPTIONS(1) - експонента для матриці U (за замовчуванням:
2.0),
OPTIONS(2) - максимальна кількість ітерацій (за замовчуванням: 100),
OPTIONS(3) - мінімально прийнятне покращення цільової функції (за
замовчуванням: 10-5),
OPTIONS(4):
ознака
відображення
проміжних
результатів
(за
замовчуванням: 1).
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
71/100

72. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
Функція fcm здійснює нечітку кластеризацію на основі методу нечітких с-середніх та
має формат виклику:
На кожній ітерації цільова функція
мінімізується
для
знаходження
кращого розташування кластерів.
Процес кластеризації зупиняється,
коли
максимально
прийнятна
кількість ітерацій є досягнутою, або
коли покращення цільової функції
між двома послідовними ітераціями
зміна є меншою ніж мінімально
прийнятний приріст.
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
72/100

73. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
Приклад використання fcm.
data = rand(100,2); % генеруємо вибірку
plot(data(:,1), data(:,2),'o'); % зображуємо дані на графіку
hold on;
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
73/100

74. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
Приклад використання fcm.
[center,U,obj_fcn] = fcm(data,2); % виконуємо кластер-аналіз
maxU = max(U);
% Знаходимо точки з найвищим рівнем приналежності до першого кластера
index1 = find(U(1,:) == maxU);
% Знаходимо точки з найвищим рівнем приналежності до другого кластера
index2 = find(U(2,:) == maxU);
line(data(index1,1),data(index1,2),'marker','*','color','g');
line(data(index2,1),data(index2,2),'marker','*','color','r');
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
74/100

75. 7.Деякі Функції Кластер-аналізу У Середовищі Matlab

7.Деякі Функції Кластераналізу У Середовищі Matlab
Приклад використання fcm.
% Зображуємо центри кластерів на графіку
plot([center([1 2],1)],[center([1 2],2)],'*','color','k');
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
75/100

76.

8.Нейронні мережі для
Кластер-аналізу
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
76/100

77.

8.Нейронні мережі для
Кластер-аналізу
Повторити і
опрацювати
самостійно
http://neural-networks.ru/Primer-neyronnoy-setiKohonena-48.html
77/100
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019