Кластерний аналіз

Кластерний аналіз

 

Вступ

1. Завдання та умови.
2. Типи,цілі та методи кластеризації.
3. Формальна постановка задачі кластеризації.

Висновок.

Список літератури.

 

ВСТУП

 

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

 

Кластер — група елементів, що характеризуються загальною|спільною| властивістю, головна мета|ціль| кластерного аналізу — знаходження груп схожих об'єктів у вибірці (примітка|тлумачення| 1). Спектр застосувань|вживань| кластерного аналізу дуже широкий: його використовують в археології, медицині, психології, хімії, біології, державному управлінні, філології, антропології, маркетингу, соціології і інших дисциплінах. «Тематика досліджень варіює від аналізу морфології муміфікованих гризунів в Новій Гвінеї до вивчення результатів голосування сенаторів США, від аналізу поведінкових функцій заморожених тарганів при їх розморожуванні до дослідження географічного розподілу деяких видів позбавляючи в Саськачеване» (примітка|тлумачення| 1). Проте|однак| універсальність застосування|вживання| привела до появи великої кількості несумісних термінів, методів і підходів, що утрудняють однозначне використання і несуперечливу інтерпретацію кластерного аналізу.

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Завдання та  умови

 

Кластерний аналіз з'явився порівняно недавно – у 1939 р. Його запропонував вчений К. Тріон. Дослівно термін "кластер" в перекладі з англійської "cluster" означає гроно, згусток, пучок, група.

 

Особливо бурхливий розвиток кластерного аналізу відбувся у 60-х роках минулого століття. Передумовами цього були поява швидкісних комп'ютерів та визнання класифікацій фундаментальним методом наукових досліджень.

 

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

 

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

 

Мета кластерного аналізу полягає в пошуку наявних структур, що виражається в утворенні груп схожих між собою об'єктів – кластерів.

 

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

 

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

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

 

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

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

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

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

 

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

 

Дослідники застосовують кластерний аналіз в різноманітних дослідженнях, наприклад при вивченні рівня добробуту населення країн СНД (О. Мірошниченко). Спочатку для цього було відібрано 16 статистичних основних соціально-економічних показників, які характеризують рівень життя громадян у різних країнах СНД:

 

1) ВВП у розрахунку  на одну особу, дол. США;

2) середньомісячна номінальна  заробітна плата, рос. руб.;

3) середньомісячний розмір  пенсії, рос. руб.;

4) індекс інвестицій в  основний капітал, процентів;

5) індекс споживчих цін,  процентів;

6) частка витрат на  купівлю продуктів харчування  у споживчих витратах домогосподарств,  процентів;

7) споживання м'яса та  м'ясопродуктів у середньому за  рік у розрахунку на одну  особу, кг;

8) кількість пшеничного  хліба, що можна було б придбати  на суму середнього наявного  грошового доходу за місяць (на  одну особу), кг;

9) загальний коефіцієнт  народжуваності (на 1000 осіб наявного  населення);

10) коефіцієнт дитячої  смертності (померло дітей віком  до одного року на 1000 народжених);

11) число зайнятих у  відсотках до економічно активного  населення;

12) забезпеченість населення  житлом у середньому (на одну  особу), м2 загальної площі;

13) кількість хворих на  злоякісні новоутворення (на 100 000 населення), осіб;

14) кількість зареєстрованих  злочинів (на 100 000 населення), од.;

15) викиди шкідливих речовин  в атмосферу стаціонарними джерелами  забруднення (на одну особу), кг;

16) відвідування музеїв  у середньому за рік (на 1000 населення), од.

 

 

2.Типи,цілі та методи кластеризації.

 

Типи вхідних даних  .

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

 

Цілі кластеризації .

 

• Розуміння даних шляхом виявлення кластерної структури. Розбиття вибірки на групи схожих об'єктів дозволяє спростити подальшу обробку даних і прийняття рішень, застосовуючи до кожного кластеру свій метод аналізу (стратегія " розділяй і володарюй ").
• Стиснення даних. Якщо вихідна вибірка надлишково велика, то можна скоротити її, залишивши по одному найбільш типовому представнику від кожного кластера.
• Виявлення новизни ( англ. novelty detection  ). Виділяються нетипові об'єкти, які не вдається приєднати до жодного з кластерів.

 

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

 

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

 

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

 

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

 

Методи кластеризації :

 

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

-Метод нечіткої кластеризації C-середніх (C-means)

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

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

-Алгоритми сімейства FOREL

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

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

- Ансамбль кластерізаторов

 -Алгоритми сімейства КRAB

-EM-алгоритм

- Алгоритм, заснований на методі просіювання

 

 

3.Формальна постановка  задачі кластеризації

 

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

 

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

 

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

 

Рішення задачі кластеризації принципове неоднозначно, і тому є декілька причин:

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

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

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

 

Групування результатів  пошуку:

 

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

-Clusty| — кластеризуюча пошукова машина компанії Vivнsimo|

-Nigma| — російська пошукова система з|із| автоматичною кластеризацією результатів

-Quintura| — візуальна кластеризація у вигляді хмари ключових|джерельних| слів

-Сегментація зображень (image| segmentation|): Кластеризація може бути використана для розбиття цифрового зображення на окремі області з цілью знаходження| меж|кордонів| (edge| detection|) або розпізнавання об'єктів.

 

 

 

ВИСНОВОК

 

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

 

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