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

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

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

Крім терміну кластеризація, існує ряд термінів зі схожими значеннями, включаючи автоматичну класифікацію, числову таксономію, ботріологію (від грецького βότρυς «виноград»), типологічний аналіз і виявлення спільноти. Незначні відмінності часто полягають у використанні результатів: у той час як при інтелектуальному аналізі даних цікавлять результуючі групи, при автоматичній класифікації цікавить кінцева дискримінаційна сила.

Кластерний аналіз був започаткований в антропології Драйвером і Кробером у 1932 році і введений у психологію Джозефом Зубіним у 1938 році і Робертом Трайоном у 1939 році і відомий як використаний Кеттеллом у 1943 році для класифікації теорії рис. в психології особистості.

Визначення

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

Моделі підключення: наприклад, ієрархічна кластеризація будує моделі на основі віддаленого підключення.

Центроїдні моделі: наприклад, алгоритм k-means представляє кожен кластер одним вектором середнього.

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

Моделі щільності: наприклад, DBSCAN і OPTICS визначають кластери як пов’язані щільні області в просторі даних.

Моделі підпростору: у бікластеризації (також відомій як спільна кластеризація або дворежимна кластеризація) кластери моделюються як членами кластера, так і відповідними атрибутами.

Групові моделі: деякі алгоритми не надають уточненої моделі для своїх результатів і лише надають інформацію про групування.

Моделі на основі графів: кліку, тобто підмножину вузлів у графі, так що кожні два вузли в підмножині з’єднані ребром, можна розглядати як прототипну форму кластера. Послаблення повної вимоги зв’язності (частка ребер може бути відсутнім) відомі як квазікліки, як в алгоритмі кластеризації HCS.

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

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

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

Жорстка кластеризація: кожен об'єкт належить до кластеру чи ні

М’яка кластеризація (також: нечітка кластеризація): кожен об’єкт певною мірою належить до кожного кластера (наприклад, ймовірність належності до кластеру)

Можливі й більш тонкі відмінності, наприклад:

Кластеризація зі строгим розділенням: кожен об’єкт належить рівно одному кластеру

Кластеризація із строгим розділенням із викидами: об’єкти також можуть належати до жодного кластера та вважаються викидами

Кластеризація, що перекривається (також: альтернативна кластеризація, кластеризація з кількома видами): об’єкти можуть належати більш ніж одному кластеру; зазвичай залучають жорсткі кластери

Ієрархічна кластеризація: об’єкти, які належать дочірньому кластеру, також належать до батьківського кластера

Кластеризація підпростору: хоча кластеризація, що перекривається, в межах унікально визначеного підпростору, кластери не повинні перекриватися

Алгоритми

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

Об’єктивно «правильного» алгоритму кластеризації не існує, але, як було зазначено, «кластеризація в очах глядача». ^[5] Найбільш прийнятний алгоритм кластеризації для конкретної проблеми часто потрібно вибирати експериментально, якщо немає математичної причини віддати перевагу одній кластерній моделі над іншою. Алгоритм, розроблений для одного типу моделі, як правило, зазнає збою на наборі даних, який містить радикально інший тип моделі. ^[5] Наприклад, k-середні не можуть знайти неопуклі кластери. ^[5]

Кластеризація на основі підключення (ієрархічна кластеризація)

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

Кластеризація на основі з’єднання – це ціла сімейство методів, які відрізняються способом обчислення відстані. Окрім звичайного вибору функцій відстані , користувачеві також потрібно визначитися з критерієм зв’язку (оскільки кластер складається з кількох об’єктів, існує кілька кандидатів для обчислення відстані), які слід використовувати. Популярні варіанти відомі як кластеризація з одним зв’язком (мінімальна відстань до об’єктів), кластеризація з повним зв’язком (максимальна відстань до об’єктів) і UPGMA або WPGMA(«Метод незважених або зважених парних груп із середнім арифметичним», також відомий як кластеризація середніх зв’язків). Крім того, ієрархічна кластеризація може бути агломеративною (починаючи з окремих елементів і об’єднуючи їх у кластери) або роздільною (починаючи з повного набору даних і розділяючи його на частини).

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

{\displaystyle {\mathcal {O}}(n^{3})}

для агломераційного утворення та

{\displaystyle {\mathcal {O}}(2^{n-1})}

для роздільної кластеризації ^[7] , що робить їх надто повільними для великих наборів даних. Для деяких особливих випадків оптимальні ефективні методи (складності

{\displaystyle {\mathcal {O}}(n^{2})}

) відомі: SLINK ^[8] для кластеризації з одним зв’язком і CLINK ^[9] для кластеризації з повним зв’язком.

• Приклади кластеризації зв’язків

Кластеризація на основі центроїда

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

Сама проблема оптимізації, як відомо, є NP-складною , і тому загальним підходом є пошук лише наближених рішень. Особливо добре відомим наближеним методом є алгоритм Ллойда ^[10] , який часто називають « алгоритмом k-середніх » (хоча цю назву ввів інший алгоритм ). Однак він знаходить лише локальний оптимум і зазвичай виконується кілька разів з різними випадковими ініціалізаціями. Варіанти k - середніх часто включають такі оптимізації, як вибір найкращого з кількох циклів, а також обмеження центроїдів членами набору даних ( k -medoids ), вибір медіан( k -медіани кластеризації ), вибираючи початкові центри менш випадково ( k -means++ ) або дозволяючи нечітке призначення кластерів ( fuzzy c-means ).

Більшість алгоритмів типу k середніх вимагають заздалегідь вказати кількість кластерів – k , що вважається одним із найбільших недоліків цих алгоритмів. Крім того, алгоритми віддають перевагу кластерам приблизно однакового розміру, оскільки вони завжди призначатимуть об’єкт найближчому центроїду. Це часто призводить до неправильно вирізаних меж кластерів (що не дивно, оскільки алгоритм оптимізує центри кластерів, а не межі кластерів).

K-means має низку цікавих теоретичних властивостей. По-перше, він розбиває простір даних на структуру, відому як діаграма Вороного . По-друге, він концептуально близький до класифікації найближчих сусідів і тому популярний у машинному навчанні . По-третє, його можна розглядати як варіант кластеризації на основі моделі, а алгоритм Ллойда як варіант алгоритму максимізації очікування для цієї моделі, який обговорюється нижче.

• k - означає кластеризацію прикладів

Кластеризація на основі розподілу

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

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

Один із відомих методів відомий як моделі суміші Гауса (з використанням алгоритму очікування-максимізації ). Тут набір даних зазвичай моделюється за допомогою фіксованої (щоб уникнути переобладнання) кількості розподілів Гауса , які ініціалізуються випадковим чином і параметри яких ітеративно оптимізуються, щоб краще відповідати набору даних. Це буде сходитися до локального оптимуму , тому багаторазові прогони можуть дати різні результати. Щоб отримати жорстку кластеризацію, об’єкти часто призначаються розподілу Гауса, до якого вони, швидше за все, належать; для м’яких кластерів це не обов’язково.

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

• Приклади кластеризації моделі суміші Гауса

Кластеризація на основі щільності

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

Найпопулярнішим методом кластеризації на основі щільності є DBSCAN . На відміну від багатьох нових методів, він має чітко визначену кластерну модель під назвою «щільність-досяжність». Подібно до кластеризації на основі зв’язків, вона базується на точках з’єднання в межах певних порогових значень відстані. Однак він з’єднує лише точки, які задовольняють критерію щільності, у вихідному варіанті визначеному як мінімальна кількість інших об’єктів у цьому радіусі. Кластер складається з усіх пов’язаних за щільністю об’єктів (які можуть утворювати кластер довільної форми, на відміну від багатьох інших методів) плюс усіх об’єктів, які знаходяться в межах діапазону цих об’єктів. Ще одна цікава властивість DBSCAN полягає в тому, що його складність досить низька – він вимагає лінійної кількості запитів діапазону до бази даних – і що він виявляє, по суті, однакові результати (це детермінованийдля основних і шумових точок, але не для граничних точок) під час кожного запуску, тому немає необхідності запускати його кілька разів. OPTICS є узагальненням DBSCAN, яке усуває необхідність вибору відповідного значення для параметра діапазону

{\displaystyle \varepsilon }

, і створює ієрархічний результат, пов’язаний з кластеризацією зв’язків . DeLi-Clu, Density-Link-Clustering поєднує ідеї кластеризації з одним зв’язком і OPTICS, усуваючи

{\displaystyle \varepsilon }

повністю параметр і пропонує покращення продуктивності порівняно з OPTICS за допомогою індексу R-дерева .

Ключовим недоліком DBSCAN і OPTICS є те, що вони очікують певного падіння щільності для виявлення меж кластера. На наборах даних із, наприклад, розподілами Гауса, що перекриваються, – типовим випадком використання штучних даних – межі кластерів, створені цими алгоритмами, часто виглядатимуть довільними, оскільки щільність кластерів постійно зменшується. На наборі даних, що складається із суміші гауссів, ці алгоритми майже завжди перевершують такі методи, як EM кластеризація , які здатні точно моделювати цей тип даних.

Середній зсув — це підхід до кластеризації, коли кожен об’єкт переміщується до найщільнішої області поблизу нього на основі оцінки щільності ядра . Згодом об’єкти зближуються до локальних максимумів щільності. Подібно до кластеризації k-середніх, ці «атрактори щільності» можуть служити представниками набору даних, але зсув середнього значення може виявити кластери довільної форми, подібні до DBSCAN. Через дорогу ітераційну процедуру та оцінку щільності середнє зрушення зазвичай повільніше, ніж DBSCAN або k-Means. Крім того, застосовність алгоритму середнього зсуву до багатовимірних даних перешкоджає негладкій поведінці оцінки щільності ядра, що призводить до надмірної фрагментації хвостів кластера. ^[15]

• Приклади кластеризації на основі щільності

Кластеризація на основі сітки

Техніка на основі сітки використовується для багатовимірного набору даних. ^[16] У цій техніці ми створюємо структуру сітки, а порівняння виконується на сітках (також відомих як комірки). Технологія, заснована на сітці, є швидкою та має низьку обчислювальну складність. Існує два типи методів кластеризації на основі сітки: STING і CLIQUE. Етапи алгоритму кластеризації на основі сітки :

1. Розділіть простір даних на кінцеву кількість клітинок.

2. Довільно виберіть комірку 'c', де c не потрібно обходити заздалегідь.

3. Обчисліть щільність 'c'

4. Якщо щільність 'c' більша за порогову щільність

   1. Позначте клітинку «с» як новий кластер

   2. Обчисліть щільність усіх сусідів 'c'

   3. Якщо щільність сусідньої комірки перевищує порогову щільність, додайте комірку в кластер і повторюйте кроки 4.2 і 4.3, доки не залишиться жодного сусіда з щільністю, вищою за порогову щільність.

5. Повторюйте кроки 2, 3 і 4, доки не буде пройдено всі клітинки.

6. СТОП.

Останні події

В останні роки було докладено значні зусилля для покращення продуктивності існуючих алгоритмів. Серед них CLARANS , і БЕРЕЗА . З недавньою потребою обробляти все більші й більші набори даних (також відомі як великі дані ), готовність обмінювати семантичне значення згенерованих кластерів на продуктивність зростає. Це призвело до розробки методів попередньої кластеризації, таких як кластеризація навісу , яка може ефективно обробляти величезні набори даних, але отримані «кластери» є лише грубим попереднім розділенням набору даних для аналізу розділів за допомогою існуючих повільніших методів, таких як якk-означає кластеризацію .

Для даних великої розмірності багато з існуючих методів не працюють через прокляття розмірності , що робить певні функції відстані проблематичними у просторі великої розмірності. Це призвело до появи нових алгоритмів кластеризації для високовимірних даних , які зосереджені на кластеризації підпростору (де використовуються лише деякі атрибути, а кластерні моделі включають відповідні атрибути для кластера) та кореляційної кластеризації , яка також шукає довільний поворотний («корельований») підпростір кластери, які можна моделювати шляхом надання кореляції їхніх атрибутів. Прикладами таких алгоритмів кластеризації є CLIQUE і SUBCLU.

Ідеї ​​з методів кластеризації на основі щільності (зокрема сімейства алгоритмів DBSCAN / OPTICS ) були адаптовані до підпросторової кластеризації (HiSC, ^[24] ієрархічна підпросторова кластеризація та DiSH ) та кореляційної кластеризації (HiCO, ієрархічна кореляція ) кластеризація, 4C з використанням «кореляційного зв’язку» та ERiC , що досліджує кореляційні кластери на основі ієрархічної щільності).

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