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

Кластерний аналіз (англ. 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]. Потрібно розбити вибірку на непересічні підмножини, що називаються кластерами, так, щоб кожен кластер складався з об'єктів, які близькі за метриці, а об'єкти різних кластерів істотно відрізнялися. При цьому кожному об'єкту приписується номер кластеру.

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

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

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