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

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

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

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

Задачі і умови

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

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

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

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

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

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

Типи задач кластеризації

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

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

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

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

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

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

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

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

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

Нехай [math]X~[/math] - безліч об'єктів, [math]Y~[/math] - множина номерів (імен, міток) кластерів. Задана функція відстані між об'єктами [math]\rho(x,x')~[/math]. Є кінцева навчальна вибірка об'єктів [math]X^m = \{ x_1, \dots, x_m \} \subset X[/math]. Потрібно розбити вибірку на непересічні підмножини, що називаються кластерами, так, щоб кожен кластер складався з об'єктів, які близькі по мітці [math]\rho~[/math], а об'єкти різних кластерів істотно відрізнялися. При цьому кожному об'єкту [math]x_i\in X^m[/math] приписується номер кластеру [math]y_i~[/math].

Алгоритм кластеризації - це функція [math]a\colon X\to Y[/math], яка будь-якого об'єкту [math]x\in X[/math] ставить у відповідність номер кластеру [math]y\in Y[/math]. Безліч в деяких випадках відомо заздалегідь, однак частіше ставиться завдання визначити оптимальне число кластерів, з точки зору того чи іншого критерію якості кластеризації.

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

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

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

Використанння

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

http://www.nigma.ru/ пошукова система з автоматичним кластеруванням

• • Візуалізація даних

http://www.quintura.ru/ інтерактивний візуальний пошук по інтернет ресурсам.

• Групування і розпізнаванння образів

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

• Вибір і пошук інформації
  • Побудова зручних класифікаторів

Список використаних джерел

1. http://www.basegroup.ru/library/analysis/clusterization/
2. http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F
3. http://www.ccas.ru/voron/download/Clustering.pdf