Методи кластеризації: процедура Мак-Кіна, метод К-методів, сітчасті методи

ДЕРЖАВНА ПОДАТКОВА СЛУЖБА УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ДЕРЖАВНОЇ ПОДАТКОВОЇ СЛУЖБИ УКРАЇНИ

Реферат

На тему: «Методи кластеризації: процедура Мак-Кина, метод К-методів, сітчасті методи»

Ірпінь 2013

Вступ

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

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

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

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

Кластерний аналіз виконує наступні основні завдання:

Розробка типології або класифікації.

Дослідження корисних концептуальних схем групування об'єктів.

Породження гіпотез на основі дослідження даних.

Перевірка гіпотез або дослідження для визначення, чи дійсно групи, виділені тим чи іншим способом, присутні в наявних даних.

Незалежно від конкретної сфери, застосування кластерного аналізу передбачає наступні етапи:

Відбір вибірки для кластеризації.

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

Обчислення значень тієї чи іншої міри схожості між об'єктами.

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

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

K-середніх (K-means).

Мак-Кина.

Нечітка кластеризація C-середніх (C-means).

Графові алгоритми кластеризації.

Статистичні алгоритми кластеризації.

Ієрархічна кластеризація або таксономія.

Нейронна мережа Кохонена.

Розглянемо деякі з методів кластеризації.

Процедура Мак-Кіна

Серед ітераційних методів найбільш популярним методом є метод k-середніх Мак-Кина. На відміну від ієрархічних методів у більшості реалізацій цього методу сам користувач повинен задати дані число кінцевих кластерів, яке зазвичай позначається як «k». Як і в ієрархічних методах кластеризації, користувач при цьому може вибрати той чи інший тип метрики. Різні алгоритми методу k-середніх відрізняються і способом вибору початкових центрів задаються кластерів. У деяких варіантах методу сам користувач може (або повинен) задати такі початкові точки, або вибравши їх з реальних спостережень, або задавши координати цих точок по кожній із змінних. В інших реалізаціях цього методу вибір заданого числа k початкових точок проводиться випадковим чином, причому ці початкові точки (зерна кластерів) можуть у подальшому уточнюватися в кілька етапів. Можна виділити 4 основних етапи таких методів:

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

при необхідності формуються проміжні кластери приписуванням кожного спостереження до найближчих заданих кластерним центрам;

після призначення всіх спостережень окремим кластерам проводиться заміна первинних кластерних центрів на кластерні середні;

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

У деяких варіантах цього методу користувач може задати числове значення критерію, трактують як мінімальна відстань для відбору нових центрів кластерів. Спостереження не розглядатиметься як претендент на новий центр кластера, якщо його відстань до замінного центру кластера перевищує задане число. Такий параметр в ряді програм називається «радіусом». Крім цього параметра можливе завдання і максимального числа ітерацій або досягнення певного, зазвичай досить малого, числа, з яким порівнюється зміна відстані для всіх кластерних центрів. Цей параметр зазвичай називається «конвергенцією», тому що відображає збіжність ітераційного процесу кластеризації. Нижче ми наведемо частина результатів, які отримані при використанні методу k-середніх Мак-Кіна до попередніх даних. Число шуканих кластерів задавалося спочатку рівним 3, а потім — 2. Перша їх частина містить результати однофакторного дисперсійного аналізу (10, 18), в якому в якості групують фактора виступає номер кластера. У першому стовпчику — список 12 змінних, далі йдуть суми квадратів (SS) і ступеня свободи (df), потім F-критерій Фішера і в останньому стовпці - досягнутий рівень значимості «р» .

Between Within signif. Змінні SS df SS df F p X1 1606,203 1 165,2964 68 660,7634 0,0 X2 621,964 1 916,1421 68 46,1648 0,0 X3 0,305 1 3,0978 68 6,6914 0,11 832 X4 0,146 1 3,2248 68 3,0697 0,84 272 X5 30,464 1 65,9877 68 31,3934 0,0 X6 6,936 1 17,2187 68 27,3910 0,2 X7 18,213 1 70,8901 68 17,4706 0,85 X8 0,160 1, 6721 68 16,1832 0,147 X9 7,981 1 11,2471 68 48,2525 0,0 X10 6,943 1 8,6925 68 54,3172 0,0 X11 8,598 1 5,4052 68 108,1661 0,0 X12 7,673 1 3,6936 68 141,2533 0,0

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

Кластер Кластер Кластер Змінна № 1 № 2 № 3 X1 46,62 000 33,78 334 48,11 867 X2 51,0 89,4 000 80,62 035 X3 1,75 000 0,37 856 0,55 613 X4 1,25 000 0,36 733 0,49 113 X5 12,75 000 3,25 667 5,10 217 X6 5,0 0,83 222 1,71 883 X7 12,25 000 3,68 889 5,9 550 X8 0,80 000 0,5 556 0,18 833 X9 4,75 000 0,82 222 1,78 233 X10 4,50 000 0,97 778 1,87 567 X11 3,25 000 0,35 444 1,37 067 X12 2,75 000 0,22 222 1,18 567

Рис. 1

Аналіз середніх значень змінних для кожного кластера дозволяє зробити висновок про те, що за ознакою Х1 кластери 1 і 3 мають близькі значення, тоді як кластер 2 має середнє значення набагато менший, ніж у інших двох кластерах. Навпаки, за ознакою Х2 перший кластер має саме мінімальне значення, тоді як 2-й і 3-й кластери мають вищі та близькі між собою середні значення. Для ознак Х3-Х12 середні значення в кластері 1 значно вище, ніж у кластерах 2 і 3. Нагадаємо, що дані 12 ознак були лектронно-мікроскопічними характеристиками еритроцитів трьох груп дітей — «Здорових», «С захворюванням щитовидної залози (до лікування)» і «С захворюванням щитовидної залози (після лікування)». Подальший аналіз цих і багатьох інших результатів статистичного аналізу досліджуваного масиву дозволив встановити цікаві взаємозв'язку захворювання щитовидної залози і електронномікроскопічних характеристик еритроцитів крові.

Наступна таблиця дисперсійного аналізу результатів кластеризації на два кластери також показує необхідність відхилення нульової гіпотези про рівність групових середніх майже за всіма 12 ознаками, за винятком змінної Х4, для якої досягнутий рівень значимості виявився більше 5%.

Нижче наведені графік і таблиця групових середніх для випадку кластеризації на два кластери. Ми пропонуємо нашим читачам самостійно зробити порівняння середніх величин окремих ознак при класифікації на 3 кластера, і на 2 кластери.

Рис. 2

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

Метод К-методів

Кластеризація зображення методом k-середніх полягає у наступному: будується деяка цільова функція Ф (°), що виражає якість поточного розбиття зображення на k кластерів із центрами у точках Сі, і=1,…, n; k — задано.

Вибравши в початковий момент центри кластерів довільним чином, далі для кожного пікселя зображення ітеративно визначаємо його приналежність до одного із k кластерів і обчислюємо нові значення для центрів кластерів, намагаючись при цьому мінімізувати функцію Ф (°).

Одним із недоліків цього методу є порушення умови зв’язності пікселів одного кластера, ось чому розвиваються різні модифікації методу k-середніх, а також його нечіткі аналоги (fuzzy k-means methods), у яких на першій стадії алгоритму допускається приналежність одного пікселя до декількох кластерів (із різним ступенем приналежності).

Алгоритм методу «Кластеризація за схемою к-середніх»:

вибрати k інформаційних точок в якості центрів кластерів поки не завершиться процес зміни центрів кластерів;

зіставити кожну інформаційну точку з кластером, відстань до центра якого мінімальна;

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

центр кожного кластера замінити середнім від елементів кластера;

кінець.

Сітчасті методи

При вирішенні завдань, пов’язаних з моніторингом навколишнього середовища, часто виникає необхідність кластеризації великих масивів даних при відсутності будь-яких апріорних відомостей про шуканих класах. У цих умовах доцільно застосовувати так звані сіткові (grid-based) алгоритми кластеризації, що використовують сітку з фіксованим кроком. Обчислювальна складність таких алгоритмів визначається числом елементів сітковою структури і практично не залежить від кількості класифікуються об'єктів. Крім того, вони дозволяють виділяти кластери складної форми без будь-яких припущень про структуру даних. Однак результати кластеризації при цьому істотно залежать від вибору кроку сітки, що значно ускладнює їх практичне застосування. Для вирішення цієї проблеми в останні роки активно розвиваються сіточні методи, засновані на використанні не однієї, а на декількох сіток з фіксованим кроком. У даній роботі пропонується алгоритм кластеризації, використовує проміжні результати, отримані алгоритмом CCA на послідовності сіток з фіксованими кроками. Алгоритм кластеризації CCA ґрунтується на введенні клітинної структури в просторі ознак і розбитті клітин на класи, використовуючи оцінку щільності розподілу даних. Кінцевий результат визначається за допомогою ансамблевого методу, заснованого на побудові узгодженої матриці відмінностей. Після обчислення узгодженої матриці відмінностей для знаходження підсумкового рішення застосовується метод побудови дендрограмми, заснований на агломеративного кластеризації. Алгоритм дозволяє виділяти багатомодові кластери складної форми і формувати рішення, стійке до зміни кроку сітки.

Висновки

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

Література

кластеризація метод кін

1. Журавлев Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения.

2. Шуметов В. Г. Шуметова Л.В. Кластерный анализ: подход с применением ЭВМ. — Орел: ОрелГТУ, 2000. — 118 с.

3. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. М., 2010.