Ієрархічні методи кластерного аналізу. Кластерний аналіз Перевірка якості кластеризації

Кластерний аналіз(КлА) - це сукупність методів багатовимірної класифікації, метою якої є утворення груп (кластерів) схожих між собою об'єктів. На відміну від традиційних угруповань, що розглядаються у загальній теорії статистики, КлА призводить до розбиття на групи з урахуванням усіх групувальних ознак одночасно.

Методи Кла дозволяють вирішувати такі завдання:

Проведення класифікації об'єктів з урахуванням безлічі ознак;

Перевірка припущень про наявність певної структури в досліджуваної сукупності об'єктів, тобто. пошук існуючої структури;

Побудова нових класифікацій для слабо вивчених явищ, коли необхідно встановити наявність зв'язків усередині сукупності та спробувати внести до неї структуру.

Для запису формалізованих алгоритмів КлА використовуються наступні умовні позначення:

- Сукупність об'єктів спостереження;

– i-е спостереженняу m-мірному просторі ознак ();

- Відстань між -м і -м об'єктами;

- Нормовані значення вихідних змінних;

– матриця відстаней між об'єктами.

Задля реалізації будь-якого методу КлА необхідно запровадити поняття «подібність об'єктів». Причому в процесі класифікації в кожен кластер повинні потрапляти об'єкти, що мають найбільшу схожість один з одним з погляду змінних, що спостерігаються.

Для кількісної оцінки подібності запроваджується поняття метрики. Кожен об'єкт описується ознаками і представлений як точка в мірному просторі. Подібність або відмінність між об'єктами, що класифікуються, встановлюється залежно від метричної відстані між ними. Як правило, використовуються такі заходи відстані між об'єктами:

Євклідова відстань ;

Зважена евклідова відстань ;

Відстань city-block ;

Відстань Махаланобіса ,

де - відстань між -им і -им об'єктами;

, - Значення -змінної і відповідно у -го і -го об'єктів;

, - Вектори значень змінних у -го і -го об'єктів;

– загальна коваріаційна матриця;

- Вага, що приписується -й змінної.

Всі методи КлА можна розділити на дві групи: ієрархічні (агломеративні та дивізимні) та ітеративні (метод-cредніх, метод пошуку згущень).

Ієрархічний кластерний аналіз.З усіх методів кластерного аналізуНайбільш поширеними є агломеративний алгоритм класифікації. Сутність аглоритму полягає в тому, що на першому кроці кожен об'єкт вибірки сприймається як окремий кластер. Процес об'єднання кластерів відбувається послідовно: виходячи з матриці відстаней чи матриці подібності об'єднуються найближчі об'єкти. Якщо матриця відстаней спочатку має розмірність (), повністю процес об'єднання завершується за () кроків. У результаті всі об'єкти будуть об'єднані в один кластер.

Послідовність об'єднання може бути подана у вигляді дендрограми, представленої на малюнку 3.1. Дендрограма показує, що на першому кроці об'єднані один кластер другий і третій об'єкти при відстані між ними 0,15. На другому етапі до них приєднався перший об'єкт. Відстань від першого об'єкта до кластера, що містить другий та третій об'єкти, 0,3 і т.д.

Багато методів ієрархічного кластерного аналізу відрізняються алгоритмами об'єднання (подібності), з яких найбільш поширеними є: метод одиночного зв'язку, метод повних зв'язків, метод середнього зв'язку, метод Уорда.

Метод повних зв'язків- включення нового об'єкта в кластер відбувається тільки в тому випадку, якщо подібність між усіма об'єктами не менша за певний заданий рівень подібності (рисунок 1.3).

Метод середнього зв'язку– при включенні нового об'єкта до вже існуючого кластера обчислюється середнє значення міри подібності, яке потім порівнюється із заданим граничним рівнем. Якщо йдеться про об'єднання двох кластерів, то обчислюють міру подібності між їхніми центрами та порівнюють її із заданим пороговим значенням. Розглянемо геометричний приклад із двома кластерами (рисунок 1.4).

Малюнок 1.4. Об'єднання двох кластерів за методом середнього зв'язку:

Якщо міра подібності між центрами кластерів () буде не меншою за заданий рівень, то кластери і будуть об'єднані в один.

Метод Уорда– на першому етапі кожен кластер складається з одного об'єкта. Спочатку об'єднуються два найближчих кластери. Для них визначаються середні значення кожної ознаки та розраховується сума квадратів відхилень

, (1.1)

де - Номер кластера, - Номер об'єкта, - Номер ознаки; - Кількість ознак, що характеризують кожен об'єкт; – кількість об'єктів у - мкластер.

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

Метод Уорда призводить до утворення кластерів приблизно рівних розмірів із мінімальною внутрішньокластерною варіацією.

Алгоритм ієрархічного кластерного аналізу можна подати у вигляді послідовності процедур:

Нормування вихідних значень змінних;

Розрахунок матриці відстаней чи матриці мір подібності;

Визначення пари найближчих об'єктів (кластерів) та їх об'єднання за вибраним алгоритмом;

Повторення перших трьох процедур, доки всі об'єкти не будуть об'єднані в один кластер.

Захід подібності об'єднання двох кластерів визначається такими методами:

Метод «найближчого сусіда» – ступінь подібності між кластерами оцінюється за рівнем подібності між найбільш подібними (найближчими) об'єктами цих кластерів;

Метод «далекого сусіда» – ступінь подібності оцінюється за рівнем подібності між найвіддаленішими (несхожими) об'єктами кластерів;

Метод середнього зв'язку – ступінь подібності оцінюється як середня величина ступенів подібності між об'єктами кластерів;

Метод медіанного зв'язку – відстань між будь-яким кластером Sта новим кластером, який вийшов у результаті об'єднання кластерів рі q,визначається як відстань від центру кластера Sдо середини відрізка, що з'єднує центри кластерів рі q.

Метод пошуку згущень. Одним із ітеративних методів класифікації є алгоритм пошуку згущень. Суть ітеративного алгоритму даного методуполягає у застосуванні гіперсфери заданого радіусу, яка переміщається у просторі класифікаційних ознак з метою пошуку локальних згущень об'єктів.

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

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

Існує кілька способів вибору радіусу сфери. Якщо - відстань між -м і -м об'єктами, то як нижня межа радіусу () вибирають , а верхня межа радіуса може бути визначена як .

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

приклад 1.З наведених даних таблиці 1.1 необхідно провести класифікацію п'яти підприємств з допомогою ієрархічного агломеративного кластерного аналізу.

Таблиця 1.1

Тут: - Середньорічна вартість основних виробничих фондів, млрд. н.; - матеріальні витратина один карбованець виробленої продукції, коп.; - Обсяг виробленої продукції, млрд. н.

Рішення.Перед тим, як обчислювати матрицю відстаней, нормуємо вихідні дані за формулою

Матриця значень нормованих змінних матиме вигляд

.

Класифікацію проведемо з допомогою ієрархічного агломеративного методу. Для побудови матриці відстаней скористаємося евклідовою відстанню. Тоді, наприклад, відстань між першим та другим об'єктами буде

Матриця відстаней характеризує відстані між об'єктами, кожен з яких, на першому кроці є окремим кластером.

.

Як очевидно з матриці , найближчими є об'єкти і . Об'єднаємо їх в один кластер і надамо йому номер . Перерахуємо відстані всіх об'єктів (кластерів) до кластера, що залишилися, отримаємо нову матрицю відстаней

.

У матриці відстані між кластерами визначено алгоритм «далекого сусіда». Тоді відстань між об'єктом і кластером дорівнює

У матриці знову знаходимо найближчі кластери. Це будуть і . Отже, на цьому кроці поєднуємо і кластери; отримаємо новий кластер, що містить об'єкти . Надамо йому номер . Тепер маємо три кластери (1,3), (2,5), (4).

.

Судячи з матриці, на наступному кроці об'єднуємо кластери і в один кластер і надамо йому номер. Тепер маємо лише два кластери:

.

І, нарешті, на останньому кроці об'єднаємо кластери та на відстані 3,861.

Рисунок 3.5.Дендрограма кластеризації п'яти об'єктів

Приклад 2. На підставі даних, наведених нижче, проведіть класифікацію магазинів за трьома ознаками: – площа торгового залу, М 2 - товарообіг на одного продавця, ден. од., - рівень рентабельності, %.

Для класифікації магазинів використовуйте метод пошуку згущень (необхідно виділити перший кластер).

Рішення. 1. Розрахуємо відстані між об'єктами за евклідовою метрикою

,

де , - Стандартизовані значення вихідних змінних відповідно у -го та -го об'єктів; т- Число ознак.

.

2. На основі матриці Z розрахуємо квадратну симетричну матрицю відстаней між об'єктами () .

Аналіз матриці відстаней допомагає визначити положення початкового центру сфери та вибрати радіус сфери.

У даному прикладібільшість «маленьких» відстаней перебувають у першому рядку, тобто. у першого об'єкта чимало «близьких» сусідів. Отже, перший об'єкт можна взяти як центр сфери.

3. Задамо радіус сфери. У цьому випадку до сфери потрапляють об'єкти, відстань яких до першого об'єкта менша за 2.

Для шести точок (об'єкти 1, 2, 3, 6, 7, 8) визначаємо координати центру тяжкості: .

4. На наступному кроці алгоритму поміщаємо центр сфери в точку та визначаємо відстань кожного об'єкта до нового центру.

Сутність цих методів у тому, що класифікації починається із завдання деяких початкових умов (кількість утворених кластерів, поріг завершення процесу класифікації тощо.). До ітераційних методів кластерного аналізу відносять метод k-Середніх (Мак-Куїна), метод пошуку згущень, метод взаємного поглинання та ін.

Метод k-середніх

Для реалізації цього методу спочатку задається кількість класів, на які необхідно розбити наявну сукупність об'єктів. Для того щоб задати початкові умови необхідно мати або додаткову інформаціюпро кількість кластерів або попередньо оцінити кількість кластерів за допомогою ієрархічних кластер-процедур.

Для початку процедури класифікації задаються рвипадково обраних об'єктів – еталонів класів ( ε ). Кожному стандарту приписується порядковий номер, який, одночасно, є номером класу. З тих, що залишилися n-pоб'єктів витягується об'єкт і перевіряється, якого з еталонів він знаходиться ближче. Цей об'єкт приєднується до того стандарту, відстань якого найменше. Ваги та зразки класів перераховуються за правилом:

де - "вага" класу, - номер ітерації.

У цьому нульове наближення будується з допомогою випадково обраних точок досліджуваної сукупності: , , .

Через n-pітерацій всі об'єкти будуть віднесені до одного з pкластерів. Для досягнення стійкого розбиття, все nоб'єктів знову розбиваються на pкласів. Нове розбиття порівнюється з попереднім. Якщо вони збігаються, то робота алгоритму завершується, інакше алгоритм повторюється.

Метод пошуку згущень

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

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

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

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

Існує кілька способів вибору радіусу сфери. Якщо – відстань між -им і -им об'єктами, то нижньої межі радіуса вибирають , а верхня межа радіуса може бути визначена як .

Якщо починати роботу алгоритму з величини і при кожному його повторенні змінювати на невелику величину, можна виявити значення радіусів, які призводять до утворення одного і того ж числа кластерів, тобто до стійкого розбиття.

Метод взаємного поглинання

Ітераційний алгоритм взаємного поглинання також використовує ідею гіперсфери. Його суть полягає в тому, що для кожного i-го об'єкта визначається свій радіус , наприклад так: , де – деяка вибирається величина, постійна всім точок, .

Сфери з радіусами будуються із центрами в точках (). Область перетину сфер радіусами, побудованими в точках, що містить центри цих сфер, називається областю взаємного поглинання. А сукупність центрів сфер, що потрапили до цієї області, називається кластером.

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

Усі завдання кластерного аналізу залежно від призначення можна поділити за такими критеріями:

Таке поділ завдань класифікації хоч і умовно, але необхідно з погляду важливого відмінності ідей і методів, з урахуванням яких конструюються кластер-процедури. Так, ієрархічні кластер-процедури призначені в основному для вирішення завдань типу А1Б1, А1Б2, А1Б3,ітераційні кластер-процедури - А2Б1, А2Б2.

Кластерний аналіз (КЛА) – це сукупність методів багатовимірної класифікації, метою якої є утворення груп (кластерів) схожих між собою об'єктів. На відміну від традиційних угруповань, що розглядаються у загальній теорії статистики, КлА призводить до розбиття на групи з урахуванням усіх групувальних ознак одночасно.

Методи Кла дозволяють вирішувати такі завдання:

- Проведення класифікації об'єктів з урахуванням безлічі ознак;

— перевірка припущень про наявність певної структури в досліджуваній сукупності об'єктів, тобто. пошук існуючої структури;

- Побудова нових класифікацій для слабо вивчених явищ, коли необхідно встановити наявність зв'язків всередині сукупності і спробувати внести до неї структуру.

Для запису формалізованих алгоритмів КлА використовуються такі умовні позначення:

- Сукупність об'єктів спостереження;

– 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.

При велику кількість спостережень ієрархічні методи кластерного аналізу не придатні. У таких випадках використовують неієрархічні методи, засновані на розподілі, які є ітеративні методидроблення вихідної сукупності. У процесі поділу нові кластери формуються доти, доки не буде виконано правило зупинки.

Така неієрархічна кластеризація полягає у поділі набору даних на певну кількість окремих кластерів. Існує два підходи. Перший полягає у визначенні меж кластерів як найбільш щільних ділянок у багатовимірному просторі вихідних даних, тобто. визначення кластера там, де є велике "згущення точок". Другий підхід полягає у мінімізації міри відмінності об'єктів

Алгоритм k-середніх (k-means)

Найбільш поширений серед неієрархічних методів алгоритм k-середніх, також званий швидким кластерним аналізом. Повне опис алгоритму можна знайти у роботі Хартігана і Вонга (Hartigan and Wong, 1978). На відміну від ієрархічних методів, які не вимагають попередніх припущень щодо числа кластерів, для можливості використання цього методу необхідно мати гіпотезу про найбільш ймовірну кількість кластерів.

Алгоритм k-середніхбудує до кластерів, розташованих на можливо більших відстанях один від одного. Основний тип завдань, які вирішує алгоритм k-середніх, - Наявність припущень (гіпотез) щодо числа кластерів, при цьому вони повинні бути різні настільки, наскільки це можливо. Вибір числа k може базуватися на результатах попередніх досліджень, теоретичних міркувань чи інтуїції.

Загальна ідея алгоритму: задане фіксоване число k кластерів спостереження зіставляються кластерам отже середні у кластері (для всіх змінних) максимально можливо відрізняються друг від друга.

Опис алгоритму

1. Початковий розподіл об'єктів за кластерами.

   Вибирається число k, і першому кроці ці точки вважаються " центрами " кластерів. Кожному кластеру відповідає один центр.

   Вибір початкових центроїдів може здійснюватися так:

   • вибір k-спостережень для максимізації початкової відстані;
   • випадковий вибір k-спостережень;
   • вибір перших k-спостережень.

   Через війну кожен об'єкт призначено певному кластеру.

2. Ітеративний процес.

   Обчислюються центри кластерів, Якими потім і далі вважаються покоординатні середні кластери. Об'єкти знову перерозподіляються.

   Процес обчислення центрів та перерозподілу об'єктів триває доти, доки не виконано одну з умов:

   • кластерні центри стабілізувалися, тобто. всі спостереження належать кластеру, якому належали до поточної ітерації;
   • число ітерацій дорівнює максимальному числу ітерацій.

   На рис. 14.1 наведено приклад роботи алгоритму k-середніхдля k, що дорівнює двом.

Мал. 14.1.

Вибір числа кластерів є складним питанням. Якщо немає припущень щодо цього числа, рекомендують створити 2 кластери, потім 3, 4, 5 тощо, порівнюючи отримані результати.

1.1. Ієрархічні агломеративні (об'єднуючі) методи– це методи, які послідовно поєднують об'єкти у кластери. На першому кроці кожен об'єкт вибірки сприймається як окремий кластер; далі на підставі матриці подібності об'єднуються найближчі об'єкти один до одного. Подібно кожен об'єкт або групується з іншим об'єктом або включається до складу існуючого кластера. Процес кластеризації кінцевий і триває до того часу, поки всі об'єкти нічого очікувати об'єднані однією кластер. Зрозуміло, подібний результат у випадку немає сенсу, і дослідник самостійно визначає, який момент кластеризація має бути припинена.

1.2. Ієрархічні дивізимні (роз'єднуючі) методи- Це методи, які послідовно розчленовують групи на окремі об'єкти. Основною вихідною посилкою методів і те, що всі об'єкти належать одному кластеру. У процесі кластеризації за певними правилами від цього кластера відокремлюються групи схожих між собою об'єктів. Отже, кожному етапі кількість кластерів зростає.

Слід зазначити, що як агломеративні, і дивізимні методи можна реалізувати з допомогою різних алгоритмів.

2. Ітеративні методи- сутність методів у тому, що класифікації починається з визначення початкових умов кластеризації (кількості утворених кластерів, координат центрів початкових кластерів та інших.). Зміна початкових умов суттєво змінює і результати кластеризації, тому застосування цих методів вимагає попереднього вивчення генеральної сукупності, зокрема, з допомогою ієрархічних методів кластерного аналізу. Найчастіше ітеративні методи застосовують після ієрархічних. Ітеративні методи можуть призвести до утворення кластерів, що перетинаються, коли один об'єкт належить одночасно декільком кластерам.

До ітеративних методів належать: метод до-Середніх, метод пошуку згущень та ін.

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

Для великих сукупностей всі методи кластерного аналізу є дуже трудомісткими, тому сучасному етапіїх застосування реалізується за допомогою програмних продуктівзокрема програми SPSS.

Достатньо докладний огляді систематизація різних методів кластерного аналізу наводиться у роботі.

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

· Евклідова відстань між об'єктами:

· Зважена евклідова відстань:

Відстань між iі jоб'єктами,

Значення до-й змінної у i-го об'єкту,

Значення до-й змінною у j-го об'єкту,

wk -вага, що приписується до-й змінної.

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