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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

Завдання[ред.ред. код]

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

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

Етапи[ред.ред. код]

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

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

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

Методи кластеризації[ред.ред. код]

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

Вхідні дані[ред.ред. код]

Типи вхідних даних[ред.ред. код]

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

Вимоги до вхідних даних[ред.ред. код]

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

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

Результати[ред.ред. код]

Причини неоднозначності[ред.ред. код]

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

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

Інтерпретація результатів[ред.ред. код]

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

Тепер виникає питання стійкості знайденого кластерного рішення. По суті, перевірка стійкості кластеризації зводиться до перевірки її достовірності. Тут існує емпіричне правило — стійка типологія зберігається при зміні методів кластеризації. Результати ієрархічного кластерного аналізу можна перевіряти ітеративним кластерним аналізом методом k-средних. Якщо при порівнянні групи збігаються більше, ніж на 70 % (понад 2/3 збігів), то кластерне рішення приймається.

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

  • Кофенетична кореляція — не рекомендується і обмежена у використанні.
  • Тести значущості (дисперсійний аналіз) — завжди дають значущий результат.
  • Метод повторних випадкових вибірок — не доводить правильність рішення.
  • Тести значущості для зовнішніх ознак — придатні тільки для повторних вимірювань.
  • Методи Монте-Карло — дуже складні і доступні тільки досвідченим математикам.

Джерела[ред.ред. код]

  • Jain, Murty, Flynn Data clustering: a review. // ACM Comput. Surv. 31(3), 1999.
  • Журавлев Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
  • Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
  • Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. ISBN 5-279-00050-7.
  • Олдендерфер М. С., Блэшфилд Р. К. Кластерный анализ / Факторный, дискриминантный и кластерный анализ: пер. с англ.; Под. ред. И. С. Енюкова. — М.: Финансы и статистика, 1989. — 215 с.
  • Шуметов В. Г. Шуметова Л. В. Кластерный анализ: подход с применением ЭВМ. — Орел: ОрелГТУ, 2000. — 118 с.