Вступ
Термін кластерний аналіз, вперше введений Тріоном (Tryon) в 1939 році, включає більше 100 різних алгоритмів.
На відміну від класифікаційних завдань, кластерний аналіз не вимагає апріорних припущень про набір даних, не накладає обмеження на подання досліджуваних об'єктів, дозволяє аналізувати показники різних типів даних (інтервальних даних, частот, бінарних даних). При цьому необхідно пам'ятати, що змінні повинні вимірюватись у порівнянних шкалах.
Кластерний аналіздозволяє скорочувати розмірність даних, робити її наочною.
Кластерний аналіз може застосовуватися до сукупностей часових рядів, тут можуть виділятися періоди схожості деяких показників та визначатися групи часових рядів зі схожою динамікою.
Кластерний аналіз паралельно розвивався у кількох напрямах, таких як біологія, психологія та інших, тому більшість методів існує по дві назви і більше.
Завдання кластерного аналізу можна об'єднати у такі групи:
Розробка типології чи класифікації.
Вивчення корисних концептуальних схем групування об'єктів.
Подання гіпотез з урахуванням дослідження даних.
Перевірка гіпотез або досліджень для визначення, чи дійсно типи (групи), виділені тим чи іншим способом, присутні в наявних даних.
Як правило, при практичному використанні кластерного аналізу одночасно вирішується кілька із зазначених завдань.
Мета заняття
Отримання навичок практичного застосування ієрархічних та ітеративних методів кластерного аналізу.
Практичне завдання
Розробити алгоритми методів ближнього сусіда та k-Середніх і реалізувати їх у вигляді комп'ютерних програм. За допомогою ДСЧ згенерувати 50 реалізацій x= (x 1 ,x 2) - Випадкової 2-мірної величини, координати якої розподілені рівномірно в інтервалі (3,8). Розподілити їх за допомогою розроблених програм на мінімальну кількість кластерів, кожен із яких міститься у сфері радіусу 0,15.
Методичні вказівки
Назва кластерний аналіз походить від англійського слова cluster – гроно, скупчення.
Кластер має такі математичні характеристики:
дисперсія кластера;
середньоквадратичне відхилення.
Центр кластера – це середнє геометричне місце точок у просторі змінних.
Радіус кластера – максимальна відстань точок від центру кластера.
Дисперсія кластера – це міра розсіювання точок у просторі щодо центру кластера.
Середньоквадратичне відхилення (СКО) об'єктів щодо центру кластера – квадратний корінь із дисперсії кластера.
Методи кластерного аналізу
Методи кластерного аналізу можна поділити на дві групи:
ієрархічні;
неієрархічні.
Кожна група включає безліч підходів та алгоритмів.
Використовуючи різні методи кластерного аналізу, аналітик може отримати різні рішення на тих самих даних. Це вважається нормальним явищем.
Ієрархічні методи кластерного аналізу
Суть ієрархічної кластеризації полягає у послідовному об'єднанні менших кластерів у великі або поділі великих кластерів на менші.
Ієрархічні агломеративні методи(Agglomerative Nesting, AGNES)
Ця група методів характеризується послідовним поєднанням вихідних елементів та відповідним зменшенням числа кластерів.
На початку роботи алгоритму усі об'єкти є окремими кластерами. На першому етапі найбільш схожі об'єкти об'єднуються в кластер. На наступних кроках об'єднання триває доти, доки всі об'єкти не будуть складати один кластер.
Ієрархічні дивізимні (розподілені) методи(DIvisive ANAlysis, DIANA)
Ці методи є логічною протилежністю агломеративним методам. На початку роботи алгоритму всі об'єкти належать одному кластеру, який на наступних кроках ділиться на менші кластери, у результаті утворюється послідовність груп, що розщеплюють.
Ієрархічні методи кластеризації відрізняються правилами побудови кластерів. В якості правил виступають критерії, які використовуються при вирішенні питання про «схожість» об'єктів при їх об'єднанні до групи.
Заходи подібності
Для обчислення відстані між об'єктами використовуються різні міри подібності (заходи подібності), звані також метриками або функціями відстаней.
Євклідова відстаньє геометричною відстанню в багатовимірному просторі та обчислюється за формулою (4.1).
Евклідова відстань (і її квадрат) обчислюється за вихідними, а чи не за стандартизованими даними.
Квадрат евклідова відстані обчислюється за такою формулою (4.2).
(4.2)
Манхеттенська відстань (відстань міських кварталів), також звана «хемінговою» або «сіті-блок» відстанню, розраховується як середня різниця за координатами. У більшості випадків ця міра відстані призводить до результатів, подібних до розрахунків евклідова відстані. Однак, для цього заходу вплив окремих викидів менший, ніж при використанні евклідової відстані, оскільки тут координати не зводяться у квадрат. Манхеттенська відстань обчислюється за формулою (4.3).
(4.3)
Відстань Чебишева варто використовувати, коли необхідно визначити два об'єкти як «різні», якщо вони відрізняються за якимось виміром. Відстань Чебишева обчислюється за такою формулою (4.4).
(4.4)
Ступінна відстаньвикористовується у тих випадках, коли бажають прогресивно збільшити або зменшити вагу, що відноситься до розмірності, для якої відповідні об'єкти сильно відрізняються. Ступінна відстань обчислюється за формулою (4.5).
(4.5)
де rі p -параметри, що визначаються користувачем. Параметр pвідповідає за поступове зважування різниць за окремими координатами, параметр rза прогресивне зважування великих відстаней між об'єктами Якщо обидва параметри rі pрівні двом, то ця відстань збігається з відстанню Евкліда.
Відсоток незгодивикористовується у тих випадках, коли дані є категоріальними. Ця відстань обчислюється за такою формулою (4.6).
(4.6)
Методи об'єднання чи зв'язку
На першому кроці, коли кожен об'єкт є окремим кластером, відстані між цими об'єктами визначаються обраним заходом. Однак, коли зв'язуються разом кілька об'єктів, необхідно використовувати інші методи визначення відстані між кластерами. Існує безліч методів об'єднання кластерів:
Одиночний зв'язок (метод найближчого сусіда) – відстань між двома кластерами визначається відстанню між двома найближчими об'єктами (найближчими сусідами) у різних кластерах.
Повний зв'язок (метод найбільш віддалених сусідів) – відстані між кластерами визначаються найбільшою відстанню між будь-якими двома об'єктами в різних кластерах (тобто найбільш віддаленими сусідами).
Незважена попарна середня – відстань між двома різними кластерами обчислюється як середня відстань між усіма парами об'єктів у них.
Зважене попарне середнє-метод ідентичний методу невваженого попарного середньогоза винятком того, що при обчисленнях розмір відповідних кластерів (тобто число об'єктів, що містяться в них) використовується як ваговий коефіцієнт.
Незважений центроїдний метод – відстань між двома кластерами визначається як відстань між їхніми центрами тяжіння.
Зважений центроїдний метод (медіана) – метод ідентичний невзвешенному центроїдному методу, за винятком того, що при обчисленнях використовуються ваги для врахування різниці між розмірами кластерів (тобто числа об'єктів у них).
Метод Варда-відстань між кластерами визначається як приріст суми квадратів відстаней об'єктів до центрів кластерів, що отримується в результаті їх об'єднання. Метод відрізняється від інших методів, оскільки він використовує методи дисперсійного аналізу з метою оцінки відстаней між кластерами. Метод мінімізує суму квадратів для будь-яких двох (гіпотетичних) кластерів, які можуть бути сформовані на кожному кроці.
Метод найближчого сусіда
Відстань між двома класами визначається як відстань між найближчими їх представниками.
Перед початком роботи алгоритму розраховується матриця відстанейміж об'єктами. Згідно з критерієм класифікації, об'єднання відбувається між кластерами, відстань між найближчими представниками яких найменша: вибираються два об'єкти з найменшою відстанню в один кластер. Після цього необхідно провести перерахунок матриці відстаней з урахуванням нового кластеру. На кожному кроці в матриці відстаней шукається мінімальне значення, що відповідає відстані між двома найближчими кластерами. Знайдені кластери поєднуються, утворюючи новий кластер. Ця процедура повторюється доти, доки не будуть об'єднані всі кластери.
При використанні методу найближчого сусіда особливу увагу слід приділяти вибору відстань між об'єктами. На основі її формується початкова матриця відстаней, яка визначає весь подальший процес класифікації.
Ітеративні методи.
При велику кількість спостережень ієрархічні методи кластерного аналізу не придатні. У таких випадках використовують неієрархічні методи, засновані на поділі вихідних кластерів на інші кластери, і які є ітеративними методами дроблення вихідної сукупності. У процесі розподілу нові кластери формуються до того часу, доки буде виконано правило зупинки.
Така неієрархічна кластеризація полягає у поділі набору даних на певну кількість окремих кластерів. Існує два підходи. Перший полягає у визначенні меж кластерів як найбільш щільних ділянок у багатовимірному просторі вихідних даних, тобто визначення кластера там, де є велике згущення точок. Другий підхід полягає у мінімізації міри відмінності об'єктів.
На відміну від ієрархічних методів класифікації ітеративні методи можуть призвести до утворення кластерів, що перетинаються, коли один об'єкт може одночасно належати кільком кластерам.
До ітеративних методів належать, наприклад, метод k-Середніх, метод пошуку згущень та інші. Ітеративні методи відносяться до швидкодіючих, що дозволяє їх використовувати для обробки великих масивів вихідної інформації.
Алгоритм k-середніх (k-means)
Серед ітеративних методів найпопулярнішим методом є метод k- середніх Мак-Кіна. На відміну від ієрархічних методів у більшості реалізацій цього методу сам користувач повинен задати шукане число кінцевих кластерів, яке зазвичай позначається. k». Алгоритм k-середніх будує kкластерів, розташованих на можливо більших відстанях один від одного. Основна вимога до типу завдань, які вирішує алгоритм k-Середніх, - наявність припущень (гіпотез) щодо числа кластерів, при цьому вони повинні бути різні настільки, наскільки це можливо. Вибір числа kможе базуватися на результатах попередніх досліджень, теоретичних міркувань чи інтуїції.
Як і в ієрархічних методах кластеризації, користувач може вибрати той чи інший тип міри подібності. Різні алгоритмиметоду k-Середніх відрізняються і способом вибору початкових центрів кластерів, що задаються. У деяких варіантах методу сам користувач може (або повинен) задати такі початкові точки, або вибравши їх із реальних спостережень, або задавши координати цих точок по кожній із змінних. В інших реалізаціях цього методу вибір заданого числа kпочаткових точок проводиться випадковим чином, причому ці початкові точки (центри кластерів) можуть у подальшому уточнюватися в кілька етапів. Можна виділити 4 основні етапи таких методів:
вибираються чи призначаються kспостережень, які будуть первинними центрами кластерів;
при необхідності формуються проміжні кластери приписуванням кожного спостереження до найближчих заданих кластерних центрів;
після призначення всіх спостережень окремим кластерам провадиться заміна первинних кластерних центрів на кластерні середні;
попередня ітерація повторюється до того часу, поки зміни координат кластерних центрів стануть мінімальними.
Загальна ідея алгоритму: задане фіксоване число k кластерів спостереження зіставляються кластерам отже середні у кластері (для всіх змінних) максимально можливо відрізняються друг від друга.
Опис алгоритму
Початковий розподіл об'єктів за кластерами.
Вибирається число kі kточок. На першому етапі ці точки вважаються «центрами» кластерів. Кожному кластеру відповідає один центр. Вибір початкових центроїдів може здійснюватися так:
вибір k-спостережень для максимізації початкової відстані;
випадковий вибір k-спостережень;
вибір перших k-спостережень.
Потім кожен об'єкт призначається певному найближчому кластеру.
Ітеративний процес.
Обчислюються центри кластерів, якими потім і надалі вважаються покоординатні середні кластери. Об'єкти знову перерозподіляються. Процес обчислення центрів та перерозподілу об'єктів триває доти, доки не виконано одну з умов:
кластерні центри стабілізувалися, тобто. всі спостереження належать кластеру, якому належали до поточної ітерації. У деяких варіантах цього методу користувач може задати числове значення критерію, який трактується як мінімальна відстань для відбору нових центрів кластерів. Спостереження не розглядатиметься як претендент на новий центркластера, якщо його відстань до центру кластера, що замінюється, перевищує задане число. Такий параметр у ряді програм називається "радіусом". Крім цього параметра, можливе завдання зазвичай досить малого числа, з яким порівнюється зміна відстані всім кластерних центрів. Цей параметр зазвичай називається "конвергенцією", тому що відображає збіжність ітераційного процесу кластеризації;
число ітерацій дорівнює максимальному числу ітерацій.
Перевірка якості кластеризації
Після отримання результатів кластерного аналізу методом k-середніх слід перевірити правильність кластеризації (тобто оцінити, наскільки кластери відрізняються один від одного). І тому розраховуються середні значення кожному кластеру. При хорошій кластеризації повинні бути отримані сильно відрізняються середні для всіх вимірювань або хоча б більшої частини.
Перевагиалгоритму k-середніх:
простота використання;
швидкість використання;
зрозумілість та прозорість алгоритму.
Недолікиалгоритму k-середніх:
алгоритм занадто чутливий до викидів, які можуть спотворювати середнє. Можливим рішеннямцієї проблеми є використання модифікації алгоритму - алгоритм k-медіани;
алгоритм може повільно працювати великих базах даних. Можливим вирішенням цієї проблеми є використання вибірки даних.
Звіт повинен містити:
опис та блок-схеми алгоритмів;
вихідні тексти програмних модулів;
результати роботи алгоритмів як графіків.
Кластерний аналіз(КлА) - це сукупність методів багатовимірної класифікації, метою якої є утворення груп (кластерів) схожих між собою об'єктів. На відміну від традиційних угруповань, що розглядаються у загальній теорії статистики, КлА призводить до розбиття на групи з урахуванням усіх групувальних ознак одночасно.
Методи Кла дозволяють вирішувати такі завдання:
Проведення класифікації об'єктів з урахуванням безлічі ознак;
Перевірка припущень про наявність певної структури в досліджуваної сукупності об'єктів, тобто. пошук існуючої структури;
Побудова нових класифікацій для слабо вивчених явищ, коли необхідно встановити наявність зв'язків усередині сукупності та спробувати внести до неї структуру.
Для запису формалізованих алгоритмів КлА використовуються наступні умовні позначення:
- Сукупність об'єктів спостереження;
– i-е спостереженняу m-мірному просторі ознак ();
- Відстань між -м і -м об'єктами;
- Нормовані значення вихідних змінних;
– матриця відстаней між об'єктами.
Задля реалізації будь-якого методу КлА необхідно запровадити поняття «подібність об'єктів». Причому в процесі класифікації в кожен кластер повинні потрапляти об'єкти, що мають найбільшу схожість один з одним з погляду змінних, що спостерігаються.
Для кількісної оцінки подібності запроваджується поняття метрики. Кожен об'єкт описується ознаками і представлений як точка в мірному просторі. Подібність або відмінність між об'єктами, що класифікуються, встановлюється залежно від метричної відстані між ними. Як правило, використовуються такі заходи відстані між об'єктами:
Євклідова відстань 
;
Зважена евклідова відстань 
;
Відстань city-block 
;
Відстань Махаланобіса ,
де - відстань між -им і -им об'єктами;
, - Значення -змінної і відповідно у -го і -го об'єктів;
, - Вектори значень змінних у -го і -го об'єктів;
– загальна коваріаційна матриця;
- Вага, що приписується -й змінної.
Всі методи КлА можна розділити на дві групи: ієрархічні (агломеративні та дивізимні) та ітеративні (метод-cредніх, метод пошуку згущень).
Ієрархічний кластерний аналіз.З усіх методів кластерного аналізу найпоширенішими є агломеративний алгоритм класифікації. Сутність аглоритму полягає в тому, що на першому кроці кожен об'єкт вибірки сприймається як окремий кластер. Процес об'єднання кластерів відбувається послідовно: виходячи з матриці відстаней чи матриці подібності об'єднуються найближчі об'єкти. Якщо матриця відстаней спочатку має розмірність (), повністю процес об'єднання завершується за () кроків. У результаті всі об'єкти будуть об'єднані в один кластер.
Послідовність об'єднання може бути подана у вигляді дендрограми, представленої на малюнку 3.1. Дендрограма показує, що на першому кроці об'єднані один кластер другий і третій об'єкти при відстані між ними 0,15. На другому етапі до них приєднався перший об'єкт. Відстань від першого об'єкта до кластера, що містить другий та третій об'єкти, 0,3 і т.д.
Багато методів ієрархічного кластерного аналізу відрізняються алгоритмами об'єднання (подібності), з яких найбільш поширеними є: метод одиночного зв'язку, метод повних зв'язків, метод середнього зв'язку, метод Уорда.
Метод повних зв'язків- включення нового об'єкта в кластер відбувається тільки в тому випадку, якщо подібність між усіма об'єктами не менша за певний заданий рівень подібності (рисунок 1.3).
|
Метод середнього зв'язку– при включенні нового об'єкта до вже існуючого кластера обчислюється середнє значення міри подібності, яке потім порівнюється із заданим граничним рівнем. Якщо мова йдепро об'єднання двох кластерів, то обчислюють міру подібності між їхніми центрами та порівнюють її із заданим пороговим значенням. Розглянемо геометричний приклад із двома кластерами (рисунок 1.4).
Малюнок 1.4. Об'єднання двох кластерів за методом середнього зв'язку:
Якщо міра подібності між центрами кластерів () буде не меншою за заданий рівень, то кластери і будуть об'єднані в один.
Метод Уорда– на першому етапі кожен кластер складається з одного об'єкта. Спочатку об'єднуються два найближчих кластери. Для них визначаються середні значення кожної ознаки та розраховується сума квадратів відхилень
, (1.1)
де - Номер кластера, - Номер об'єкта, - Номер ознаки; - Кількість ознак, що характеризують кожен об'єкт; – кількість об'єктів у - мкластер.
Надалі кожному етапі роботи алгоритму об'єднуються ті об'єкти чи кластери, які дають найменше збільшення величини .
Метод Уорда призводить до утворення кластерів приблизно рівних розмірів із мінімальною внутрішньокластерною варіацією.
Алгоритм ієрархічного кластерного аналізу можна подати у вигляді послідовності процедур:
Нормування вихідних значень змінних;
Розрахунок матриці відстаней чи матриці мір подібності;
Визначення пари найближчих об'єктів (кластерів) та їх об'єднання за вибраним алгоритмом;
Повторення перших трьох процедур, доки всі об'єкти не будуть об'єднані в один кластер.
Захід подібності об'єднання двох кластерів визначається такими методами:
Метод «найближчого сусіда» – ступінь подібності між кластерами оцінюється за рівнем подібності між найбільш подібними (найближчими) об'єктами цих кластерів;
Метод «далекого сусіда» – ступінь подібності оцінюється за рівнем подібності між найвіддаленішими (несхожими) об'єктами кластерів;
Метод середнього зв'язку – ступінь подібності оцінюється як середня величинаступенів подібності між об'єктами кластерів;
Метод медіанного зв'язку – відстань між будь-яким кластером Sта новим кластером, який вийшов у результаті об'єднання кластерів рі q,визначається як відстань від центру кластера Sдо середини відрізка, що з'єднує центри кластерів рі q.
Метод пошуку згущень. Одним із ітеративних методів класифікації є алгоритм пошуку згущень. Суть ітеративного алгоритму даного методуполягає у застосуванні гіперсфери заданого радіусу, яка переміщається у просторі класифікаційних ознак з метою пошуку локальних згущень об'єктів.
 |
Метод пошуку згущень вимагає, перш за все, обчислення матриці відстаней (або матриці подібних заходів) між об'єктами і вибору початкового центру сфери. Зазвичай першому етапі центром сфери служить об'єкт (крапка), найближчого околиці якого розташовано найбільше сусідів. На основі заданого радіусу сфери (R)визначається сукупність точок, що потрапили всередину цієї сфери, і їм обчислюються координати центру (вектор середніх значень ознак).
Коли черговий перерахунок координат центру сфери призводить до такого ж результату, як і попередній крок, переміщення сфери припиняється, а точки, що у неї, утворюють кластер, і з подальшого процесу кластеризації виключаються. Перелічені процедури повторюються для всіх точок, що залишилися. Робота алгоритму завершується за кінцеве число кроків, і всі точки виявляються розподіленими кластерами. Кількість кластерів, що утворилися, заздалегідь невідомо і сильно залежить від радіусу сфери.
Для оцінки стійкості отриманого розбиття доцільно повторити процес кластеризації кілька разів для різних значень радіусу сфери, змінюючи щоразу радіус на невелику величину.
Існує кілька способів вибору радіусу сфери. Якщо - відстань між -м і -м об'єктами, то як нижня межа радіуса () вибирають 
, а верхня межа радіуса може бути визначена як 
.
Якщо починати роботу алгоритму з величини і за кожному його повторенні змінювати на невелику величину, можна виявити значення радіусів, які призводять до утворення однієї й тієї числа кластерів, тобто. до стійкого розбиття.
приклад 1.З наведених даних таблиці 1.1 необхідно провести класифікацію п'яти підприємств з допомогою ієрархічного агломеративного кластерного аналізу.
Таблиця 1.1
Тут: - Середньорічна вартість основних виробничих фондів, млрд. н.; - Матеріальні витрати на один карбованець виробленої продукції, коп.; - Обсяг виробленої продукції, млрд. н.
Рішення.Перед тим, як обчислювати матрицю відстаней, нормуємо вихідні дані за формулою
Матриця значень нормованих змінних матиме вигляд
.
Класифікацію проведемо з допомогою ієрархічного агломеративного методу. Для побудови матриці відстаней скористаємося евклідовою відстанню. Тоді, наприклад, відстань між першим та другим об'єктами буде
Матриця відстаней характеризує відстані між об'єктами, кожен з яких, на першому кроці є окремим кластером.
.
Як видно з матриці, найбільш близькими є об'єкти та . Об'єднаємо їх в один кластер і надамо йому номер . Перерахуємо відстані всіх об'єктів (кластерів), що залишилися, до кластера отримаємо нову матрицю відстаней
.
У матриці відстані між кластерами визначено алгоритм «далекого сусіда». Тоді відстань між об'єктом та кластером дорівнює
У матриці знову знаходимо найближчі кластери. Це будуть і . Отже, на цьому кроці поєднуємо і кластери; отримаємо новий кластер, що містить об'єкти . Надамо йому номер . Тепер маємо три кластери (1,3), (2,5), (4).
.
Судячи з матриці, наступному кроціоб'єднуємо кластери і, в один кластер і надамо йому номер. Тепер маємо лише два кластери:
.
І, нарешті, на останньому кроці об'єднаємо кластери та на відстані 3,861.
 |
Подаємо результати класифікації у вигляді дендрограми (рисунок 1.5). Дендрограма свідчить у тому, що кластер більш однорідний за складом вхідних об'єктів, оскільки у ньому об'єднання відбувалося за менших відстанях, ніж у кластері .
Рисунок 3.5.Дендрограма кластеризації п'яти об'єктів
Приклад 2. На основі даних, наведених нижче, проведіть класифікацію магазинів за трьома ознаками: – площа торгового залу, М 2 - товарообіг на одного продавця, ден. од., - рівень рентабельності,%.
| Номер магазину | Номер магазину | ||||||
Для класифікації магазинів використовуйте метод пошуку згущень (необхідно виділити перший кластер).
Рішення. 1. Розрахуємо відстані між об'єктами за евклідовою метрикою
,
де , - Стандартизовані значення вихідних змінних відповідно у -го та -го об'єктів; т- Число ознак.
.
2. На основі матриці Z розрахуємо квадратну симетричну матрицю відстаней між об'єктами () .
Аналіз матриці відстаней допомагає визначити положення початкового центру сфери та вибрати радіус сфери.
У даному прикладібільшість «маленьких» відстаней перебувають у першому рядку, тобто. у першого об'єкта чимало «близьких» сусідів. Отже, перший об'єкт можна взяти як центр сфери.
3. Задамо радіус сфери. У цьому випадку до сфери потрапляють об'єкти, відстань яких до першого об'єкта менша за 2.
Для шести точок (об'єкти 1, 2, 3, 6, 7, 8) визначаємо координати центру тяжкості: .
4. На наступному кроці алгоритму поміщаємо центр сфери в точку та визначаємо відстань кожного об'єкта до нового центру.
При велику кількість спостережень ієрархічні методи кластерного аналізу не придатні. У таких випадках використовують неієрархічні методи, засновані на розподілі, які є ітеративні методидроблення вихідної сукупності. У процесі поділу нові кластери формуються доти, доки не буде виконано правило зупинки.
Така неієрархічна кластеризація полягає у поділі набору даних на певну кількість окремих кластерів. Існує два підходи. Перший полягає у визначенні меж кластерів як найбільш щільних ділянок у багатовимірному просторі вихідних даних, тобто. визначення кластера там, де є велике "згущення точок". Другий підхід полягає у мінімізації міри відмінності об'єктів
Алгоритм k-середніх (k-means)
Найбільш поширений серед неієрархічних методів алгоритм k-середніх, також званий швидким кластерним аналізом. Повний описалгоритму можна знайти у роботі Хартігана та Вонга (Hartigan and Wong, 1978). На відміну від ієрархічних методів, які не вимагають попередніх припущень щодо числа кластерів, для можливості використання цього методу необхідно мати гіпотезу про найбільш ймовірну кількість кластерів.
Алгоритм k-середніхбудує до кластерів, розташованих на можливо більших відстанях один від одного. Основний тип завдань, які вирішує алгоритм k-середніх, - Наявність припущень (гіпотез) щодо числа кластерів, при цьому вони повинні бути різні настільки, наскільки це можливо. Вибір числа k може базуватися на результатах попередніх досліджень, теоретичних міркувань чи інтуїції.
Загальна ідея алгоритму: задане фіксоване число k кластерів спостереження зіставляються кластерам отже середні у кластері (для всіх змінних) максимально можливо відрізняються друг від друга.
Опис алгоритму
- Початковий розподіл об'єктів за кластерами.
Вибирається число k, і першому кроці ці точки вважаються " центрами " кластерів. Кожному кластеру відповідає один центр.
Вибір початкових центроїдів може здійснюватися так:
- вибір k-спостережень для максимізації початкової відстані;
- випадковий вибір k-спостережень;
- вибір перших k-спостережень.
Через війну кожен об'єкт призначено певному кластеру.
- Ітеративний процес.
Обчислюються центри кластерів, Якими потім і далі вважаються покоординатні середні кластери. Об'єкти знову перерозподіляються.
Процес обчислення центрів та перерозподілу об'єктів триває доти, доки не виконано одну з умов:
- кластерні центри стабілізувалися, тобто. всі спостереження належать кластеру, якому належали до поточної ітерації;
- число ітерацій дорівнює максимальному числу ітерацій.
На рис. 14.1 наведено приклад роботи алгоритму k-середніхдля k, що дорівнює двом.
Мал. 14.1.
Вибір числа кластерів складне питання. Якщо немає припущень щодо цього числа, рекомендують створити два кластери, потім 3, 4, 5 і т.д., порівнюючи отримані результати.
1.1. Ієрархічні агломеративні (об'єднуючі) методи– це методи, які послідовно поєднують об'єкти у кластери. На першому кроці кожен об'єкт вибірки сприймається як окремий кластер; далі на підставі матриці подібності об'єднуються найближчі об'єкти один до одного. Подібно кожен об'єкт або групується з іншим об'єктом або включається до складу існуючого кластера. Процес кластеризації кінцевий і триває до того часу, доки всі об'єкти нічого очікувати об'єднані однією кластер. Зрозуміло, подібний результат у випадку немає сенсу, і дослідник самостійно визначає, у який момент кластеризація має бути припинена.
1.2. Ієрархічні дивізимні (роз'єднуючі) методи- Це методи, які послідовно розчленовують групи на окремі об'єкти. Основною вихідною посилкою методів і те, що всі об'єкти належать одному кластеру. У процесі кластеризації за певними правилами від цього кластера відокремлюються групи схожих між собою об'єктів. Отже, кожному етапі кількість кластерів зростає.
Слід зазначити, що як агломеративні, і дивізимні методи можна реалізувати з допомогою різних алгоритмів.
2. Ітеративні методи- сутність методів у тому, що класифікації починається з визначення початкових умов кластеризації (кількості утворених кластерів, координат центрів початкових кластерів та інших.). Зміна початкових умов суттєво змінює і результати кластеризації, тому застосування цих методів вимагає попереднього вивчення генеральної сукупності, зокрема, з допомогою ієрархічних методів кластерного аналізу. Найчастіше ітеративні методи застосовують після ієрархічних. Ітеративні методи можуть призвести до утворення кластерів, що перетинаються, коли один об'єкт належить одночасно декільком кластерам.
До ітеративних методів належать: метод до-Середніх, метод пошуку згущень та ін.
При виборі методів кластерного аналізу керуються минулим досвідом, наявною інформацією про генеральну сукупність вихідними даними. Слід зазначити, що у початковому етапі, Найчастіше, вибирається відразу кілька методів кластерного аналізу, які призводять до різних результатів кластеризації. Отримані класифікації об'єктів аналізуються за допомогою критеріїв якості, що дозволяють вибрати найбільш якісну класифікацію.
Для великих сукупностей усі методи кластерного аналізу є дуже трудомісткими, тому на етапі їх застосування реалізується за допомогою програмних продуктів, зокрема програми SPSS.
Достатньо докладний огляді систематизація різних методів кластерного аналізу наводиться у роботі.
Основою ієрархічних методів кластерного аналізу є визначення заходи подібностіоб'єктів за змінними, що спостерігаються. Для кількісної оцінки подібності кластерному аналізі вводиться поняття метрики. Подібність чи різницю між об'єктами встановлюється залежно від метричної відстані між об'єктами. Існують різні заходи подібності між об'єктами, серед них найпопулярнішими є такі:
· Евклідова відстань між об'єктами:
· Зважена евклідова відстань:
Відстань між iі jоб'єктами,
Значення до-й змінної у i-го об'єкту,
Значення до-й змінною у j-го об'єкту,
wk -вага, що приписується до-й змінної.
Якщо об'єкти описуються неметричними змінними, тоді як заходи подібності можуть бути використані коефіцієнти рангової кореляції (наприклад, парні коефіцієнти кореляції Пірсона), коефіцієнти асоціативності та інші заходи подібності.
Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче
Студенти, аспіранти, молоді вчені, які використовують базу знань у своєму навчанні та роботі, будуть вам дуже вдячні.
Подібні документи
Цілі сегментації ринку в маркетингової діяльності. Сутність кластерного аналізу, основні етапи виконання. Вибір способу вимірювання відстані або подібності. Ієрархічні, неієрархічні методи кластеризації. Оцінка надійності та достовірності.
доповідь, додано 02.11.2009
Характеристика будівельної галузі Краснодарського краю Прогноз розвитку житлового будівництва. Сучасні методиі інструментальні засобикластерного аналізу Багатовимірні статистичні методи діагностики економічного стану підприємства.
дипломна робота , доданий 20.07.2015
Моделювання. Детермінізм. Завдання детермінованого факторного аналізу. Способи вимірювання впливу факторів детермінованому аналізі. Розрахунок детермінованих економіко-математичних моделей та методів факторного аналізу на прикладі РУП "ГЗЛіН".
курсова робота , доданий 12.05.2008
Основні показники фінансового станупідприємства. Криза на підприємстві, його причини, види та наслідки. Сучасні методи та інструментальні засоби кластерного аналізу, особливості їх використання для фінансово-економічної оцінки підприємства.
дипломна робота , доданий 09.10.2013
Завдання та етапи кластерного аналізу, вимоги до інформації. Приклад класифікації економічних об'єктів за допомогою алгоритму кластерного аналізу, методи перевірки стійкості кластеризації, інтерпретація результатів аналізу та побудування дендрограми.
реферат, доданий 15.07.2011
Основна термінологія, поняття та методи факторного аналізу. Основні етапи проведення факторного аналізу та методика Чеботарьова. Практична значимість факторного аналізу управління підприємством. Метод Лагранжа у вирішенні завдань факторного аналізу.
контрольна робота , доданий 26.11.2008
Виконує кластерний аналіз підприємств за допомогою програми Statgraphics Plus. Побудова лінійного рівняння регресії. Розрахунок коефіцієнтів еластичності за регресійними моделями. Оцінка статистичної значущості рівняння та коефіцієнта детермінації.
