Кластерування

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

Результат кластерного аналізу показано у вигляді точок розфарбованих у три кольори.

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

Окрім терміну кластеризація існує багато термінів з аналогічним значенням, серед яких автоматична класифікація, ^[en] та типологічний аналіз. Тонкі розбіжності часто полягають у використанні результатів: для добування даних, отримані групи є предметом інтересу, при автоматичній класифікації, навпаки, більш важливий степінь розбіжності.

Кластерний аналіз походить з антропології, де він був започаткований Драйвером (англ. Driver) і Крьобером (англ. Kroeber) у 1932 році. В психологію він був введений Зубіним у 1938 році і ^[en] у 1939. Став відомий завдяки використанню Кеттелем для класифікації теорії ознак в психології особистості, починаючи з 1943 року.

Загальна характеристика

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

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

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

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

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

Завдання

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

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

Етапи

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

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

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

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

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

• Моделі зв'язності. Наприклад, ієрархічна кластеризація або таксономія будуються на основі відстані між вузлами.
• Центроїдні моделі. Наприклад, метод K-середніх (K-means) представляє кожен кластер єдиним усередненим вектором.
• Статистичні моделі. Кластери будуються ґрунтуючись на статистичних розподілах. Таких як багатовимірний нормальний розподіл з допомогою ЕМ-алгоритму.
• Моделі засновані на щільності. Наприклад, в DBSCAN і в OPTICS кластери визначаються як зв'язані області відповідної щільності у просторі даних.
• Групові моделі. Деякі алгоритми не забезпечують вдосконалену модель для своїх результатів, а просто описують групування об'єктів.
• Графові моделі. Поняття кліки (така підмножина вершин, в якій кожна пара вершин з'єднана ребром) у графі слугує прототипом кластеру. Пом'якшення вимоги до повної зв'язності (тобто, частина ребер може бути відсутня) призводить до поняття відомого як квазі-кліка. Вони будуються алгоритмом ^[en].
• Нейронні моделі. Найбільш відомою моделлю нейронної мережі з некерованим навчанням є нейронна мережа Кохонена. Ці моделі, як правило, можна охарактеризувати як схожі на одну або подібні якійсь з наведених вище моделей, включаючи моделі у підпросторах, коли нейронні мережі реалізують метод головних компонент або ^[en].

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

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

Серед них виділяють декілька доладних:

• Жорстке розбиття на кластери. Кожен об'єкт належить рівно одному кластеру.
• Жорстке розбиття на кластери з викидами. Об'єкт може не належати жодному кластеру і розглядається як викид.
• Кластери з перетином. Об'єкт може належати більш ніж одному кластеру.
• Ієрархічна кластеризація. Якщо об'єкт належить нащадку, то він також належить і предку.
• Підпросторова кластеризація. Хоч кластери і можуть перетинатись, проте в межах визначеного підпростору кластери не перетинаються. Для прикладу дивись ^[en].

Вхідні дані

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

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

• Вектор характеристик. Кожен об'єкт описується набором своїх характеристик; ці характеристики можуть бути числовими або нечисловими.
• . Кожен об'єкт описується відстанями до всіх інших об'єктів вибірки.

Вимоги до вхідних даних

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

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

Результати

Причини неоднозначності

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

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

Інтерпретація результатів

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

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

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

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

Дотичні терміни

• Кластерування (рос. кластерирование, англ. clustering) — метод обробки даних, що полягає у встановленні в певній сукупності за певним алгоритмом членів, які є подібними.

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

Див. також

• 1R-алгоритм

Примітки

1. Bailey, Ken (1994). Numerical Taxonomy and Cluster Analysis. Typologies and Taxonomies. с. 34. ISBN .
2. (1939). Cluster Analysis: Correlation Profile and Orthometric (factor) Analysis for the Isolation of Unities in Mind and Personality. Edwards Brothers.
3. Cattell, R. B. (1943). The description of personality: Basic traits resolved into clusters. Journal of Abnormal and Social Psychology. 38 (4): 476—506. doi:10.1037/h0054116.
4. Estivill-Castro, Vladimir (20 червня 2002). Why so many clustering algorithms – A Position Paper. ACM SIGKDD Explorations Newsletter. 4 (1): 65—75. doi:10.1145/568574.568575.

Джерела

• Jain, Murty, Flynn Data clustering: a review. // ACM Comput. Surv. 31(3), 1999.
• Журавлев Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. .
• Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. .
• Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. .
• Олдендерфер М. С., Блэшфилд Р. К. Кластерный анализ / Факторный, дискриминантный и кластерный анализ: пер. с англ.; Под. ред. И. С. Енюкова. — М.: Финансы и статистика, 1989. — 215 с.
• Шуметов В. Г. Шуметова Л. В. Кластерный анализ: подход с применением ЭВМ. — Орел: ОрелГТУ, 2000. — 118 с.
• Глосарій термінів з хімії // Й. Опейда, О. Швайка. Ін-т фізико-органічної хімії та вуглехімії ім. Л. М. Литвиненка НАН України, Донецький національний університет. — Донецьк: Вебер, 2008. — 758 с. —
• Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). (PDF). Introduction to Data Mining. Addison-Wesley. ISBN . Архів оригіналу (PDF) за 18 Жовтня 2018. Процитовано 3 Серпня 2018.

Посилання

• Кластерний аналіз на фінансових ринках [ 21 лютого 2017 у Wayback Machine.]