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

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

Задачі

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

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

$\underset{d\to \mathrm{\infty }}{\lim }\frac{dis{t}_{\max }-dis{t}_{\min }}{dis{t}_{\min }}=0$

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

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

Підходи

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

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

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

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

Проблема кластеризації підпросторів з'являється через те, що існує $2^d$ різних підпросторів простору виміру $d$. Якщо підпростори не з паралельні осям координат, тоді можливе існування нескінченної кількості підпросторів. Отже, алгоритми кластеризації підпросторів використовують певний евристичний метод, щоб залишатися обчислювально здійсненним, проте з ризиком виникнення хибних результатів. Наприклад, властивість спадного змикання (Шаблон:Lang-en, див. навчання асоціативних правил) може бути використано для побудови підпросторів більшої кількості розмірностей шляхом об'єднання підпросторів менших розмірностей, оскільки будь-який підпростір T, що містить кластер, призведе до того, що повний простір S також буде містити кластер (тобто, S ⊆ T), підхід, який використовується у більшості традиційних алгоритмів, таких як CLIQUE, Шаблон:Iw. Також можливо визначити підпростір, що використовує різні ступені актуальності для кожної розмірності, підхід, який використовується iMWK-засобами, EBK-режимами та CBK-режимами.

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

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

Наприклад, алгоритм PreDeCon перевіряє, які атрибути підтримують кластеризацію для кожної точки, і регулює функцію відстані таким чином, що розміри з низькою дисперсією посилюються в функції відстані. На малюнку вище, кластер $c_c$ може бути знайдений за допомогою DBSCAN з функцією довжини, яка ставить менший акцент на осі $x$ і таким чином перебільшує низьку різницю в осі $y$ достатньо для того, щоб згрупувати точки в кластер.

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

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

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

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

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

Інший тип підпросторів розглядається в Шаблон:Iw.

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

• Шаблон:Iw включає різні алгоритми кластеризації підпросторів та кореляції.