Кластеризація багатовимірних даних

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

Задачі

Для того, щоб виконати кластеризацію багатовимірних даних необхідно подолати чотири перешкоди^[1]:

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

${\displaystyle \lim _{d\to \infty }{\frac {dist_{\max }-dist_{\min }}{dist_{\min }}}=0}$

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

Недавні дослідження показують, що проблеми розрізнення виникають лише тоді, коли існує велика кількість нерелевантних вимірів, і що підходи, які використовують метод спільного ближнього сусіда, можуть покращити результати.^[2]

Підходи

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

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

Приклад 2D простору з підпросторовими кластерами.

Сусіднє зображення показує простий двовимірний простір, де можна виділити декілька кластерів. У одновимірних підпросторах, можна побачити кластери ${\displaystyle c_{a}}$ (у підпросторі ${\displaystyle \{x\}}$) і ${\displaystyle c_{b}}$, ${\displaystyle c_{c}}$, ${\displaystyle c_{d}}$ (у підпросторі ${\displaystyle \{y\}}$). ${\displaystyle c_{c}}$ не можна розцінювати як кластер у двовимірному (під-)просторі, оскільки він занадто розкиданий по осі${\displaystyle x}$. У двох вимірах можна ідентифікувати два кластери ${\displaystyle c_{ab}}$ та ${\displaystyle c_{ad}}$.

Проблема кластеризації підпросторів з'являється через те, що існує ${\displaystyle 2^{d}}$ різних підпросторів простору виміру ${\displaystyle d}$. Якщо підпростори не з паралельні осям координат, тоді можливе існування нескінченної кількості підпросторів. Отже, алгоритми кластеризації підпросторів використовують певний евристичний метод, щоб залишатися обчислювально здійсненним, проте з ризиком виникнення хибних результатів. Наприклад, властивість спадного змикання (англ. downward-closure, див. навчання асоціативних правил) може бути використано для побудови підпросторів більшої кількості розмірностей шляхом об'єднання підпросторів менших розмірностей, оскільки будь-який підпростір T, що містить кластер, призведе до того, що повний простір S також буде містити кластер (тобто, S ⊆ T), підхід, який використовується у більшості традиційних алгоритмів, таких як CLIQUE,^[3] SUBCLU^[en].^[4] Також можливо визначити підпростір, що використовує різні ступені актуальності для кожної розмірності, підхід, який використовується iMWK-засобами^[5], EBK-режимами^[6] та CBK-режимами^[7].

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

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

Наприклад, алгоритм PreDeCon перевіряє, які атрибути підтримують кластеризацію для кожної точки, і регулює функцію відстані таким чином, що розміри з низькою дисперсією посилюються в функції відстані.^[8] На малюнку вище, кластер ${\displaystyle c_{c}}$ може бути знайдений за допомогою DBSCAN з функцією довжини, яка ставить менший акцент на осі ${\displaystyle x}$ і таким чином перебільшує низьку різницю в осі ${\displaystyle y}$ достатньо для того, щоб згрупувати точки в кластер.

PROCLUS використовує аналогічний підхід з кластеризацією k-медоїдів^[en].^[9] Початкові медоїди вгадуються, і для кожного медоїда визначається підпростір, натягнутий атрибутами з низьким відхиленням. Бали призначаються найбільш близькому медоїду, враховуючи тільки підпростір цього медоїда при визначенні відстані. Алгоритм потім проходить як звичайний алгоритм PAM^[en].

Якщо функція відстані оцінює атрибути по-різному, але ніколи як 0 (і, отже, ніколи не відкидає нерелевантні атрибути), алгоритм називається «м'яко»-зпрогнозованим алгоритмом кластеризації.

Гібридні підходи

Не всі алгоритми намагаються або знайти унікальне кластерне призначення для кожної точки або всі кластери у всіх підпросторах; багато хто погоджується на результат між ними, де знаходяться ряд можливих перекриттів, але не обов'язково вичерпний набір кластерів. Прикладом є FIRES, який з його основного підходу є алгоритмом кластеризації підпросторів, але використовує евристику занадто агресивно, щоб достовірно виробляти всі підпросторові кластери.^[10] Інший гібридний підхід полягає у включенні «людини-в-алгоритмічний-цикл»: досвід людини в галузі може допомогти зменшити експоненційний простір пошуку через евристичний відбір зразків. Це може бути корисним у сфері охорони здоров'я, де, наприклад, лікарі стикаються з великомасштабними описами стану пацієнта і вимірюваннями щодо успішності деяких терапій. Важливим питанням у таких даних є порівняння та кореляція стану пацієнта та результатів терапії, а також комбінацій вимірів. Кількість розмірів часто дуже велика, отже, їх необхідно зіставити з меншою кількістю відповідних вимірів, щоб бути більш схильними до експертного аналізу. Це пояснюється тим, що нерелевантні, надлишкові та суперечливі виміри можуть негативно вплинути на ефективність та точність всього аналітичного процесу.^[11]

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

Інший тип підпросторів розглядається в кореляційній кластеризації^[en].

Програмне забезпечення

• ELKI^[en] включає різні алгоритми кластеризації підпросторів та кореляції.

Посилання

1. Kriegel, H. P.; Kröger, P.; Zimek, A. (2009). Clustering high-dimensional data. ACM Transactions on Knowledge Discovery from Data. 3: 1—58. doi:10.1145/1497577.1497578.
2. Houle, M. E.; Kriegel, H. P.; Kröger, P.; Schubert, E.; Zimek, A. (2010). Can Shared-Neighbor Distances Defeat the Curse of Dimensionality? (PDF). Scientific and Statistical Database Management. Lecture Notes in Computer Science. Т. 6187. с. 482. doi:10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1. Архів оригіналу (PDF) за 23 Грудня 2018. Процитовано 17 Квітня 2019.
3. Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). Automatic Subspace Clustering of High Dimensional Data. Data Mining and Knowledge Discovery. 11: 5—33. doi:10.1007/s10618-005-1396-1. {{cite journal}}: Cite має пустий невідомий параметр: |1= (довідка)
4. Kailing, K.; Kriegel, H. P.; Kröger, P. (2004). Density-Connected Subspace Clustering for High-Dimensional Data. Proceedings of the 2004 SIAM International Conference on Data Mining. с. 246. doi:10.1137/1.9781611972740.23. ISBN 978-0-89871-568-2.
5. De Amorim, R.C.; Mirkin, B. (2012). Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering. Pattern Recognition. 45 (3): 1061. doi:10.1016/j.patcog.2011.08.012.
6. Carbonera, Joel Luis; Abel, Mara (November 2014). An Entropy-Based Subspace Clustering Algorithm for Categorical Data. IEEE. doi:10.1109/ictai.2014.48. ISBN 9781479965724. {{cite book}}: Проігноровано |journal= (довідка)
7. Carbonera, Joel Luis; Abel, Mara (2015). CBK-Modes: A Correlation-based Algorithm for Categorical Data Clustering. SCITEPRESS - Science and Technology Publications. doi:10.5220/0005367106030608. ISBN 9789897580963. {{cite book}}: Проігноровано |journal= (довідка)
8. Böhm, C.; Kailing, K.; Kriegel, H. -P.; Kröger, P. (2004). Density Connected Clustering with Local Subspace Preferences. Fourth IEEE International Conference on Data Mining (ICDM'04). с. 27. doi:10.1109/ICDM.2004.10087. ISBN 0-7695-2142-8.
9. Aggarwal, C. C.; Wolf, J. L.; Yu, P. S.; Procopiuc, C.; Park, J. S. (1999). Fast algorithms for projected clustering. ACM SIGMOD Record. 28 (2): 61. doi:10.1145/304181.304188. {{cite journal}}: Cite має пустий невідомий параметр: |1= (довідка)
10. Kriegel, H.; Kröger, P.; Renz, M.; Wurst, S. (2005). A Generic Framework for Efficient Subspace Clustering of High-Dimensional Data. Fifth IEEE International Conference on Data Mining (ICDM'05). с. 250. doi:10.1109/ICDM.2005.5. ISBN 0-7695-2278-5.
11. Hund, M.; Böhm, D.; Sturm, W.; Sedlmair, M.; Schreck, T.; Keim, D.A.; Majnaric, L.; Holzinger, A. (2016). Visual analytics for concept exploration in subspaces of patient groups: Making sense of complex datasets with the Doctor-in-the-loop. Brain Informatics. 3 (4): 233—247. doi:10.1007/s40708-016-0043-5. PMC 5106406. PMID 27747817.