PCA, t-SNE та UMAP: Три Рівнізмінні Методи Зменшення Розмірності Високорівневих Даних

Проблема: занадто багато осей для розгляду

Реальні набори даних часто живуть у десятках, сотнях або тисячах вимірів, а людське сприйняття працює лише в двох чи трьох. Зменшення розмірності знаходить низьковимірну систему координат, яка зберігає якомога більше змістовної структури високовимірних даних, щоб кластери, градієнти та викиди, які невидимі у таблиці чисел, стали видимими на точковій діаграмі. Три методи, порівняні тут — PCA, t-SNE та UMAP — вирішують цю проблему з використанням фундаментально різних математичних підходів і з фундаментально різними уявленнями про те, що саме означає «зберігати структуру».

PCA: найкращий лінійний відтінок

Метод головних компонент (Principal Component Analysis) ставить виключно лінійне питання: в якому напрямку даних зберігається найбільша дисперсія? Центруйте дані, обчислюйте її коваріаційну матрицю Σ та діагоналізуйте її:

Σ = (1/n) XᵀX (де X – центровані дані, рядки = зразки) Σ vi = λi vi власні вектори vi = головні компоненти власні значення λi = дисперсія вздовж vi

проєктуйтеся на верхні k власних векторів → k-вимірне уявлення, яке зберігає найбільшу загальну дисперсію з будь-якого лінійного проектування

Еквівалентно, PCA випливає безпосередньо з розкладання сингулярних значень X = UΣVᵀ: праві сингулярні вектори V є головними компонентами, а сингулярні значення в Σ пропорційні квадратним корінням власних значень, зазначених вище. Оскільки це жорстке лінійне проектування – буквально обертання даних і потім відсікання осей з низькою дисперсією – PCA швидкий (одне розкладання власного значення, без ітерацій), детермінований та зворотний у сенсі того, що ви завжди точно знаєте, яку дисперсію було викинуто (відношення викинутого до загального числа власних значень). Його слабкість є точно його силою: лінійне проектування не може розгорнути криволінійний маніфольд. Дані, що мають вигляд швейцарського ролика або двох скручених спіралей, будуть стиснуті в неви інформативну згусток незалежно від того, який лінійний напрямок ви оберете, оскільки цікава структура сутністю нелінійна.

Σ = (1/n) XᵀX                      (X mean-centred, rows = samples)
Σ vi = λi vi                       eigenvectors vi = principal components
                                    eigenvalues λi  = variance along vi

project onto the top k eigenvectors → the k-dimensional view that
                                       preserves the most total variance
                                       of any linear projection

t-SNE: зберігає сусідів, а не відстані

t-distributed Stochastic Neighbor Embedding, представлений ван дер Маатен та Хінтом у 2008 році, відмовляється від збереження відстаней глобально і замість цього намагається зберегти, хто є ким сусідом. У багатовимірному просторі він перетворює парні відстані на умовні ймовірності того, що точка j є сусідом точки i, використовуючи Гауссів розподіл, центрований навколо i, з шириною смуги, яка налаштовується для кожної точки за допомогою цільової перехресної кореляції (розріджено, ефективна кількість сусідів – типові значення 5 до 50):

pj|i ∝ exp( −||xi − xj||² / 2σi² ) ширина смуги σi встановлюється за допомогою цільової перехресної кореляції pij = (pj|i + pi|j) / 2n симетризована спільна ймовірність in низьковимірній карті використовується більш важкий розподіл t-Student: qij ∝ (1 + ||yi − yj||²)⁻¹ мінімізувати KL(P ‖ Q) = Σ pij log(pij / qij) за допомогою градієнтного спуску на yi Важка розподіл t-Student у низьковимірній карті (натомість іншого Гаусса) є ключовою хитрощаю, і це вирішує те, що ван дер Маатен та Хінт назвали проблемою переповнення: багатовимірний простір просто має місце для набагато більшої кількості рівно віддалених сусідів, ніж 2D площина, тому симетричне Гауссове вкладення змушене або стискати помірні відстані разом, або використовувати нереально великі відстані для далеко розташованих точок. Ваги розподілу t-Student дозволяють помірно несхожими точкам комфортно знаходитися далеко один від одного на карті без необхідності мати близькі точки, які також розсіюються, що і дає t-SNE його характерні щільні, добре відокремлені кластери. Ціна полягає в тому, що лише локальна структура є надійною: розмір кластерів, відстань між кластерами та навіть кількість точок, які потрапляють у кластер, можуть бути артефактами перехресної кореляції та випадкового початкового ініціалізування, а не справжньої геометрії даних – класична пастка полягає в тому, щоб читати сенс з того, наскільки далеко розташовані один від одного t-SNE кластери, що алгоритм зовсім не намагається зберегти.

pj|i ∝ exp( −||xi − xj||² / 2σi² )      per-point σi set by target perplexity
pij  = (pj|i + pi|j) / 2n               symmetrised joint probability

in the low-dimensional map, use a heavier-tailed Student-t distribution:
qij ∝ (1 + ||yi − yj||²)⁻¹

minimise  KL(P ‖ Q) = Σ pij log(pij / qij)   by gradient descent on the yi

UMAP: топологія замість ймовірності

Метод однорідної аплікації та проектування багатовиду (Uniform Manifold Approximation and Projection – McInnes, Healy & Melville, 2018) базується на іншому припущенні, що корениться в топоаналітиці: припускається, що багатовимірні дані лежать на (або поблизу) нижньовимірному многовиді, і намагаються відтворити розмиту топологічну репрезентацію цього многовиду – для кожної точки створюється розмитий сфінгідальний набір, побудований з її k найближчих сусідів, де ваги ребер зменшуються зі збільшенням відстані так само, як і ймовірності в t-SNE, але масштаб локальної відстані кожної точки калібрується до її власної відстані до найближчого сусіда, а не глобального параметра «перплексії». Потім оптимізується низьковимірне розташування таким чином, щоб воно максимально нагадувало розмиту топологію, мінімізуючи крос-ентропію між високовимірним і низьковимірним сфінгідальними множинами, використовуючи ефективну стохастичну градієнтний метод з негативним семплюванням, схожий за духом на word2vec.

На практиці UMAP зазвичай працює помітно швидше, ніж t-SNE на великих наборах даних, а його теоретичне обґрунтування надає реальну перевагу в збереженні глобальної структури – відносне положення кластерів несе дещо більше інформації, ніж у t-SNE, хоча він все ще не повинен читатися як збереження справжніх відстаней. Обидва методи мають одну й ту ж основну застереження: вони є нелінійними та стохастичними, тому осі вихідного графіку не несуть прямого фізичного значення (на відміну від PCA, де кожна вісь є конкретною лінійною комбінацією оригінальних ознак із відомою дисперсією), і повторне виконання з іншим випадковим насінням або параметрами може помітно переставляти розташування, незважаючи на те, що взаємозв’язки між сусідами залишаються схожими.

Який з них, і коли?

PCA – швидкий, детермінований, лінійний метод, осі інтерпретовані → перший етап, обробки даних, збереження лінійної структури.

t-SNE – повільніший (іноді), стохастичний, відмінно виявляє локальні кластери, не має глобальної структури → візуальне дослідження, значення відстаней має обмежене сенс, чутливий до параметру перплексії кластерної структури.

UMAP – швидший за t-SNE, краще зберігає глобальну структуру, теоретично обґрунтований, але не є збереженням відстаней → великі набори даних, pipeline/використання в продуктивному середовищі.

PCA      fast, deterministic, linear, axes are interpretable        →  first pass,
                                                                          preprocessing,
                                                                          linear structure
t-SNE    slow(er), stochastic, excellent local clusters, no global      →  visual exploration
         distance meaning, sensitive to perplexity                         of cluster structure
UMAP     faster than t-SNE, more global structure preserved,            →  large datasets,
         theoretically grounded, still not distance-preserving             pipeline/production use

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Dimensionality Reduction і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.