Заглянути під капот алгоритму PCA

Привіт! Мене звати Ганна Сафонова, я аналітик-початківиця, працюю викладачкою в політехнічному коледжі.

Познайомившись з алгоритмом аналізу головних компонентів (Principal ComponentAnalysis) машинного навчання, я була зачарована тим, як в одному підході одночасно поєднані принципи статистики та лінійної алгебри, лінійної регресії та власних розкладів.

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

Теоретична основа алгоритму

Спочатку варто зазначити, що головна мета алгоритму PCA — це зменшити розмірність вихідних даних. Але яким способом це реалізується?

Для прикладу візьмемо дві характеристики з бази даних The world happiness report in 2018, Healthy life expectancy (Life) та GDP per capita (GDP).

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

Рис. 1 Графік розсіювання для змінних Life та GDP

Крім описаних, розглянута база даних містить також інші характеристики, як-от: Social support (х3), Freedom to make life choices (х4), Generosity (х5), Perceptions of corruption (х6). І для подальшого аналізу нам потрібно зменшити розмірність цієї бази. Для цього, використавши той факт, що змінні Life та GDP сильно корелюють, об’єднаємо їх в одну змінну. Наприклад, так: «Забезпечення тривалості здорового життя» (Healthy Aging).

Ця задача зменшення розмірності може бути вирішена за допомогою PCA. Якщо узагальнити, проблема полягає в тому, як накреслити вектор так, щоб під час проєктування заданих точок у напряму цього вектору варіація (дисперсія) спроєктованої множини точок була максимальна. Тобто точки мають бути максимально розкидані відносно одна одної (рис. 2).

Рис. 2 Об’єднання характеристик шляхом проєктування на вектор

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

Рис. 3 Залежність розміру дисперсії від вибору напряму вектору

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

Щоб відповісти на це питання, повернімося до множини точок, які описують вибрані нами характеристики: тривалість здорового життя (Life) та ВВП на душу населення (GDP). Фактично ми хочемо дослідити розподіл їх проєкцій, а саме: дисперсію цього розподілу на деякий вектор.

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

де, наприклад, cov(x₁, х₂) є коваріація між змінними x₁ та х₂.

Підтвердженням цього факту є те, що коваріаційна матриця і є узагальненням дисперсії (var) тільки для багатовимірного випадку:

де μ — середнє значення.

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

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

де Q — матриця ортонормованих власних векторів (одиничних перпендикулярних власних векторів);

Λ — діагональна матриця власних значень (матриця на головній діагоналі, якої знаходяться власні значення, а всі інші елементи дорівнюють нулю).

Зауваження: якщо вектор власний для матриці C, то C = λ, де λ — власне значення матриці C, яке вказує, на скільки вектор масштабується в ході лінійного перетворення.

Для нашого прикладу розклад матриці С буде мати наступний вигляд:

де , — власні вектори, λ₁, λ₂ — відповідні їм власні значення.

Таким чином, можна сказати, що розклад QΛQ^T матриці С представляє процес переходу до нової системи координат, в якій стовпці матриці Q слугують новим базисом, а діагональні елементи матриці Λ вказують на масштаби зміни у відповідних напрямках. Тобто, іншими словами, відбувається перехід матриці С від оригінального базису (який для розглянутого прикладу може бути представлений) у декартовій системі координат з одиничними векторами = (1,0) та = (0,1) до нового базису = (v1_x, v1_y), = (v2_x, v2_y)

В результаті цього переходу матриця С перетворюється на матрицю Λ:

Рис 4. Перехід до нового базису

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

Чому саме цей вектор? Якщо розглянути співвідношення (6), то можна побачити, що в новому базисі коваріації між змінними дорівнюють нулю (cov(x₁, х₂) = cov(x₂, х₁) → 0), тобто між змінними в цьому базисі немає залежності (рис.5).

Дисперсії ж кожної змінної окремо відповідно дорівнюють власним значенням (var(x₁) → λ₁, var(x₂) → λ₂).

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

Рис 5. Демонстрація відсутності лінійної залежності між змінними в новому базисі

Реалізація алгоритму PCA за допомогою Mathcad

Для більш чіткого розуміння описаної вище теорії повернімося до нашого прикладу і застосуємо математичну модель алгоритму PCA поетапно до конкретних даних.

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

Напишемо дані характеристик Life та GDP у вигляді векторів:

Хоча діапазони вимірювання даних суттєво не відрізняються (GPD ∈ [0; 2.096], Life ∈ [0; 1.03]), щоб усунити можливі різниці в масштабах, перед застосуванням алгоритму нормалізуємо дані. Для цього від кожного значення потрібно відняти середнє характеристики та поділити на її стандартне відхилення (рис.6).

Рис. 6 Дані після нормалізації

Формули для знаходження середнього значення:

стандартного відхилення (середньоквадратичного відхилення):

Зауваження: будемо використовувати виправлене стандартне відхилення, якщо маємо не усі дані, як в цьому прикладі, а лише вибірку:

Обчислюємо середні для кожної характеристики та стандартні відхилення:

Далі, використовуючи формули (1), (2), (3) знайдемо матрицю коваріацій:

Зауваження: в обчисленнях вище μ=0 оскільки дані нормалізовані.

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

де det — визначник порядку, який відповідає розмірності матриці коваріацій С, λ — змінна, яка описує власні значення матриці С, І — одинична матриця такої ж розмірності, що і матриця С.

Таким чином ми знайшли власні значення для матриці коваріацій С, більше з яких λ₂ ≈ 1.84427. Знайдемо тепер власні вектори, які відповідатимуть знайденим власним значенням. Потім нормуємо їх, поділивши на довжину.

Для цього потрібно розв’язати матричні рівняння:

де = (v1_x, v1_y), = (v2_x, v2_y) — власні вектори, λ₁, λ₂ — відповідні їм власні значення.

Тобто ми знайшли власні вектори матриці С. Вектор = (0.707, 0.707) відповідає більшому власному значенню λ₂ ≈ 1.84427, він і є першим головним компонентом PCA (PC₁), вектор = (—0.707, 0.707) відповідає меншому власному значенню λ₁ ≈ 0.15573, він є другим головним компонентом PCA (PC₂). Фактично отримані власні вектори дозволяють знайти нові дані, виразивши їх через вихідні значення так (рис. 7):

Рис. 7 Побудова нової системи координат

Проєкції зроблені в напрямку PC1 пояснюють варіацію на рівні

усіх розглянутих даних, для порівняння у напрямку PC2 лише

варіації враховується (рис. 8)

Рис. 8 Об’єднання даних у напрямку першої головної компоненти

Реалізація алгоритму PCA за допомогою Python бібліотеки sklearn

Для чистоти експерименту порівняємо отриманий розв’язок з результатами використання автоматизованого алгоритму Python бібліотеки sklearn.

Як ми бачимо, отримали ті самі власні значення, але протилежно направленні власні вектори, що для даної задачі є допустимим (рис 9).

Рис. 9 Напрямки головних компонент отримані у Python

Більш складний приклад використання алгоритму PCA

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

Крім GDP per capita, Healthy life expectancy включимо до нашого прикладу ще такі характеристики, як: Social support (Support), Freedom to make life choices (Freedom).

З теплової карти видно, що характеристики корелюють між собою, сильно корелюють перші три. Далі застосуємо PCA.

З лістингу 7 (explained_variance_ratio_) можемо побачити, що 87% дисперсії пояснюються першими двома компонентами. У першу компоненту всі характеристики входять приблизно однаковими частинами, трохи менше, Freedom. Неважливо, що від’ємними частинами (напрям стрілочки вектору ми можемо взяти протилежний), головне що знак у всіх однаковий. Можна сказати, що перша головна компонента описує загальний рівень щастя країни.

А що до другої компоненти? Тут цікавіше, вона розрізняє країни з високим рівнем благополуччя (GDP, Life, Support) та високим рівнем свободи (Freedom), бо Freedom має протилежний знак до всіх інших характеристик.

Причому на благополуччя тут приблизно в однакових частинах впливають характеристики GDP, Life, менше Support, а контраст зі Freedom значний, бо ця характеристика входить найбільшою по модулю частиною порівняно з усіма іншими характеристиками. Отже зменшивши розмірність даних з 4 до 2 ми можемо зробити достатньо цікавий аналіз країнами, порівнюючи не тільки їхній загальний рівень щастя та благополуччя, а й прослідкувати за впливом на щастя такої важливої характеристики як Freedom to make life choices.

Висновки

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

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

1. Нормалізація даних.
2. Знаходження матриці коваріацій.
3. Обчислення власних значень матриці коваріацій.
4. Сортування власних значень за спаданням та вибір k найбільших.
5. Знаходження всіх власних векторів, які відповідають власним значенням.
6. Вибір перших k власних векторів.
7. Трансформація вихідних даних відповідно до вибраного базису власних векторів.

Посилання на код вище на моєму GitHub.

Корисні джерела

• The Math of Principal Component Analysis (PCA)
• The Mathematics Behind Principal Component Analysis
• Understanding Principle Component Analysis(PCA) step by step

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті