Інтелектуальний аналіз даних презентация

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

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

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

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

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

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

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

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

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

1.Кластеризація. Основні поняття
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
/100
Завдання на сам. роботу
Y
Перевірити якість , роздруківку
“вклеїти” в конспект
Виконати
За допомогою
Мережі КОХОНЕНА
(див лекції “ШТ.Інтелект”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
/100

5.Ітеративні методи кластеризації
4Алгоритм HCM (Hard C – Means).
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
/100

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

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

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

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

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

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

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

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

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
/100

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 =
2.7294 2.0109 3.5947
1.2533 2.6531 -6.3852
6.2250 0.8750 7.3350
6.0986 3.7906 0.5009
2.1756 4.6787 2.8412
1.0976 4.9397 -6.7286
0.7735 0.5296 7.0453
8.9292 1.2024 -2.1848
1.4203 0.1222 -5.4266
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
/100

7.Деякі Функції Кластер-аналізу У Середовищі Matlab
Функція fcm здійснює нечітку кластеризацію на основі методу нечітких с-середніх та має формат виклику:
[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
/100

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

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

7.Деякі Функції Кластер-аналізу У Середовищі Matlab
Інтелектуальний аналіз даних
© ЄА. Лавров, 2015-2019
/100
Приклад використання 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');

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

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