Лекція 13. Зменшення розмірності. Метод головних компонент (PCA) #

Огляд #

Досі майже всі набори даних курсу були малорозмірними: одна-дві ознаки в описовій статистиці (Лекція 3), кілька координат у кластеризації (Лекція 9). Реальні дані інші: транзакція банку має сотні полів, зображення — тисячі пікселів, геном — десятки тисяч позицій. Кожна ознака — це окремий вимір простору, у якому «живуть» об’єкти, і зі зростанням числа ознак $p$ цей простір поводиться дедалі гірше з точки зору аналізу — виникає так зване прокляття розмірності.

Ця лекція відкриває Змістовий модуль 6 «Розширені методи аналітики даних» і присвячена зменшенню розмірності (англ. dimensionality reduction) — сімейству методів, що замінюють $p$ вихідних ознак на меншу кількість $k \ll p$ нових, зберігаючи при цьому якомога більше корисної інформації. Навіщо це потрібно:

• візуалізація — людина бачить дані лише у 2D або 3D; щоб «подивитися» на багатовимірну вибірку, її треба спроєктувати на площину;
• прибирання шуму — відкидаючи маловаріативні напрямки, ми часто відкидаємо саме шум, а не сигнал;
• швидкість і пам’ять — менше ознак означає швидше навчання й менші моделі;
• боротьба з перенавчанням (англ. overfitting) — у просторі меншої розмірності моделі мають менше «свободи» підлаштуватися під випадковості.

Центральний метод лекції — метод головних компонент (англ. Principal Component Analysis, PCA). Він спирається безпосередньо на поняття дисперсії та коваріації (Лекція 3, Лекція 5): головні компоненти — це напрямки максимальної дисперсії даних, а знаходять їх як власні вектори коваріаційної матриці. Оскільки багато методів (метод $k$ найближчих сусідів із Лекції 6, метод $k$-середніх із Лекції 9) спираються на відстані, які «псує» висока розмірність, PCA часто застосовують як попередню обробку перед класифікацією чи кластеризацією.

Практичний бік. Коваріаційну матрицю, власні значення й вектори та проєкцію на головні компоненти ви обчислюватимете «руками» в аудиторії, а сам метод PCA реалізуєте програмою в Лабораторній роботі 13. Наступна тема модуля — аналіз часових рядів (Лекція 14).

13.1 Прокляття розмірності #

Означення (прокляття розмірності). Прокляттям розмірності (англ. curse of dimensionality) називають сукупність ефектів, через які зі зростанням числа ознак $p$ дані стають розрідженими, геометрична інтуїція втрачає силу, а обчислення й статистичні оцінки вимагають експоненційно більшого обсягу вибірки.

Пояснимо трьома простими спостереженнями.

Розрідженість. Нехай точки рівномірно розкидані в одиничному гіперкубі $[0,1]^p$. Щоб «локальний» окіл охопив лише $1\%$ точок, його ребро має бути $\ell = 0.01^{1/p}$. Порахуємо:

У сотні вимірів, щоб зібрати лише $1\%$ даних, окіл мусить простягтися на $95.5\%$ довжини кожної осі — він уже не «локальний». Поняття «близькі сусіди» втрачає зміст.

Усі точки — на межі. Частка об’єму гіперкуба, що лежить не далі $0.05$ від його поверхні, дорівнює $1 - 0.9^{\,p}$:

Уже при $p = 100$ практично всі точки притиснуті до «стінок» — внутрішність куба порожня.

Концентрація відстаней. Як наслідок, у високій розмірності відстані від довільної точки до її найближчого й найдальшого сусідів стають майже однаковими. Але саме на різниці цих відстаней тримаються метод $k$ найближчих сусідів (Лекція 6) та метод $k$-середніх (Лекція 9) — тож у сирому багатовимірному просторі вони працюють погано.

Приклад 13.1. У задачі з $p = 10$ ознаками, щоб зберегти таку саму щільність покриття простору, як дають $100$ точок при $p = 1$, знадобилося б $100^{10} = 10^{20}$ точок. Зібрати стільки даних неможливо — тому розмірність доводиться зменшувати.

13.2 Відбір ознак vs виділення ознак #

Зменшити розмірність можна двома принципово різними шляхами.

Означення (відбір ознак). Відбір ознак (англ. feature selection) — вибір підмножини з наявних ознак і відкидання решти. Нові ознаки не створюються; ті, що лишились, зберігають свій первісний зміст.

Означення (виділення ознак). Виділення ознак (англ. feature extraction) — побудова нових ознак як комбінацій вихідних, так щоб невелика кількість нових ознак несла максимум інформації.

Порівняння:

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

13.3 Дисперсія, коваріація, коваріаційна матриця #

PCA цілком побудований на понятті розкиду даних. Нагадаємо (див. Лекцію 3): вибіркова дисперсія ознаки $X$ за $n$ спостереженнями

$$s_X^2 = \frac{1}{n-1} \sum_{i=1}^{n} (x_i - \bar{x})^2$$

вимірює розкид однієї ознаки. Зв’язок двох ознак описує коваріація (Лекція 5):

Означення (вибіркова коваріація). Коваріацією ознак $X$ та $Y$ називають

$$\operatorname{cov}(X, Y) = \frac{1}{n-1} \sum_{i=1}^{n} (x_i - \bar{x})(y_i - \bar{y}).$$

Знак коваріації показує напрямок спільної зміни: $\operatorname{cov} > 0$ — ознаки зростають разом, $\operatorname{cov} < 0$ — одна зростає, коли інша спадає, $\operatorname{cov} \approx 0$ — лінійного зв’язку немає. Зауважте, що $\operatorname{cov}(X, X) = s_X^2$.

Коли ознак $p$, усі попарні коваріації зручно зібрати в одну матрицю.

Означення (коваріаційна матриця). Коваріаційною матрицею набору з $p$ ознак називають матрицю $\Sigma$ розміру $p \times p$, у якій

$$\Sigma_{jk} = \operatorname{cov}(X_j, X_k).$$

На головній діагоналі стоять дисперсії ознак $\Sigma_{jj} = s_{X_j}^2$, поза діагоналлю — коваріації.

Властивості $\Sigma$, важливі для PCA:

1. симетричність: $\Sigma_{jk} = \Sigma_{kj}$, бо $\operatorname{cov}(X_j, X_k) = \operatorname{cov}(X_k, X_j)$;
2. невід’ємна визначеність: усі власні значення $\Sigma$ невід’ємні (дисперсія вздовж будь-якого напрямку не може бути від’ємною);
3. слід дорівнює загальній дисперсії: $\operatorname{tr}(\Sigma) = \sum_j s_{X_j}^2$ — сумарний розкид даних по всіх ознаках.

Зауваження (поділ на $n$ чи на $n-1$). Деякі джерела означують коваріаційну матрицю з дільником $n$ замість $n-1$. Це домножує всю матрицю на сталу $\frac{n-1}{n}$, тому власні вектори й частки поясненої дисперсії не змінюються — змінюються лише самі значення власних чисел. Ми користуємось дільником $n-1$ (вибіркова коваріація), як у Лекції 3.

Приклад 13.2 (коваріаційна матриця). Візьмемо наскрізний набір лекції — п’ять точок із двома ознаками:

$$(1, 3),\ (3, 1),\ (3, 4),\ (3, 5),\ (5, 7).$$

Середні: $\bar{x} = \frac{1+3+3+3+5}{5} = 3$, $\ \bar{y} = \frac{3+1+4+5+7}{5} = 4$. Відхилення $(x_i - 3,\ y_i - 4)$:

$$(-2, -1),\ (0, -3),\ (0, 0),\ (0, 1),\ (2, 3).$$

Обчислюємо суми (дільник $n - 1 = 4$):

$$\sum (x_i-\bar{x})^2 = 4 + 0 + 0 + 0 + 4 = 8 \ \Rightarrow\ s_X^2 = 8/4 = 2,$$

$$\sum (y_i-\bar{y})^2 = 1 + 9 + 0 + 1 + 9 = 20 \ \Rightarrow\ s_Y^2 = 20/4 = 5,$$

$$\sum (x_i-\bar{x})(y_i-\bar{y}) = 2 + 0 + 0 + 0 + 6 = 8 \ \Rightarrow\ \operatorname{cov}(X,Y) = 8/4 = 2.$$

Отже,

$$\Sigma = \begin{pmatrix} 2 & 2 \\ 2 & 5 \end{pmatrix}, \qquad \operatorname{tr}(\Sigma) = 2 + 5 = 7.$$

Матриця симетрична; загальна дисперсія даних дорівнює $7$.

13.4 Власні вектори, власні значення й головні компоненти #

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

Означення (власний вектор і власне значення). Ненульовий вектор $v$ є власним вектором (англ. eigenvector) матриці $\Sigma$, якщо

$$\Sigma v = \lambda v$$

для деякого числа $\lambda$ — власного значення (англ. eigenvalue). Геометрично $\Sigma$ лише розтягує вектор $v$ у $\lambda$ разів, не повертаючи його.

Спроєктуймо центровані дані на напрямок одиничного вектора $v$: координата $i$-го об’єкта стає $t_i = v^{\top}(x_i - \bar{x})$. Можна показати, що дисперсія цих проєкцій дорівнює $v^{\top} \Sigma v$, і що серед усіх одиничних напрямків її максимізує саме власний вектор $\Sigma$ з найбільшим власним значенням, а сама максимальна дисперсія дорівнює цьому $\lambda$.

Означення (головна компонента). Головні компоненти (англ. principal components) набору даних — це власні вектори його коваріаційної матриці $\Sigma$, впорядковані за спаданням власних значень. Перша головна компонента — напрямок максимальної дисперсії; дисперсія даних уздовж $i$-ї компоненти дорівнює її власному значенню $\lambda_i$.

Властивість (ортогональність). Оскільки $\Sigma$ симетрична, її власні вектори (для різних власних значень) ортогональні. Тому головні компоненти утворюють нову систему координат — повернуті осі, вздовж яких ознаки вже не корельовані.

Для матриці $2 \times 2$ власні значення знаходять із характеристичного рівняння

$$\det(\Sigma - \lambda I) = 0.$$

Приклад 13.3 (власні значення й вектори). Продовжимо Приклад 13.2 із $\Sigma = \begin{pmatrix} 2 & 2 \\ 2 & 5 \end{pmatrix}$. Характеристичне рівняння:

$$\det \begin{pmatrix} 2 - \lambda & 2 \\ 2 & 5 - \lambda \end{pmatrix} = (2-\lambda)(5-\lambda) - 4 = \lambda^2 - 7\lambda + 6 = 0.$$

Корені: $\lambda = \dfrac{7 \pm \sqrt{49 - 24}}{2} = \dfrac{7 \pm 5}{2}$, тобто $\lambda_1 = 6$ та $\lambda_2 = 1$ (сума $6 + 1 = 7 = \operatorname{tr}\Sigma$ — контроль).

Перший власний вектор ($\lambda_1 = 6$): розв’язуємо $(\Sigma - 6I)v = 0$:

$$\begin{pmatrix} -4 & 2 \\ 2 & -1 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = 0 \ \Rightarrow\ -4v_1 + 2v_2 = 0 \ \Rightarrow\ v_2 = 2v_1.$$

Беремо $v = (1, 2)$ і нормуємо: $v_1 = \dfrac{1}{\sqrt{5}}(1, 2) \approx (0.447, 0.894)$.

Другий власний вектор ($\lambda_2 = 1$): $(\Sigma - I)v = 0$ дає $v_1 + 2v_2 = 0$, тобто $v = (2, -1)$, нормовано $v_2 = \dfrac{1}{\sqrt{5}}(2, -1) \approx (0.894, -0.447)$.

Перевірка ортогональності: $(1, 2) \cdot (2, -1) = 2 - 2 = 0$. Перша головна компонента вказує в напрямку $(1, 2)$ — це і є вісь найбільшого розкиду хмари точок.

13.5 Алгоритм PCA #

Зберемо кроки разом.

PCA(матриця даних X розміру n×p, число компонент k):
  1. ЦЕНТРУВАННЯ: від кожної ознаки відняти її середнє  ->  X_c = X - mean
     (за потреби ще СТАНДАРТИЗАЦІЯ: поділити на СКВ кожної ознаки)
  2. КОВАРІАЦІЙНА МАТРИЦЯ: Sigma = (1/(n-1)) * X_c^T X_c        (p×p)
  3. ВЛАСНІ ЗНАЧЕННЯ/ВЕКТОРИ: розв'язати  Sigma v = lambda v
  4. ВПОРЯДКУВАННЯ: відсортувати (lambda_i, v_i) за спаданням lambda
  5. ВІДБІР: узяти перші k власних векторів -> матриця W = [v_1 ... v_k]  (p×k)
  6. ПРОЄКЦІЯ: Z = X_c · W                                       (n×k)
  повернути Z (нові координати), W (компоненти), lambda (дисперсії компонент)

Крок 6 дає нові координати об’єктів у системі головних компонент; матриця $W$ задає, як нова ознака збирається зі старих. Якість стиснення оцінюють так.

Означення (частка поясненої дисперсії). Часткою поясненої дисперсії (англ. explained variance ratio) $i$-ї головної компоненти називають

$$\frac{\lambda_i}{\lambda_1 + \lambda_2 + \dots + \lambda_p} = \frac{\lambda_i}{\operatorname{tr}(\Sigma)}.$$

Сума часток перших $k$ компонент — це накопичена пояснена дисперсія: частка загального розкиду даних, збережена після проєкції на $k$ компонент.

Приклад 13.4 (повний прогін PCA). Зведемо набір Прикладу 13.2 до однієї компоненти. Головні компоненти вже знайдено (Приклад 13.3): перша — $v_1 = \frac{1}{\sqrt{5}}(1, 2)$ з $\lambda_1 = 6$. Проєкція центрованого об’єкта: $t_i = v_1^{\top}(x_i - \bar{x}) = \dfrac{(x_i - 3) + 2(y_i - 4)}{\sqrt{5}}$.

Дисперсія проєкцій: $\dfrac{1}{4}\cdot\dfrac{16 + 36 + 0 + 4 + 64}{5} = \dfrac{120}{20} = 6 = \lambda_1$ — як і має бути. Частка поясненої дисперсії першої компоненти:

$$\frac{\lambda_1}{\lambda_1 + \lambda_2} = \frac{6}{6 + 1} = \frac{6}{7} \approx 0.857.$$

Отже, замінивши дві ознаки однією головною компонентою, ми зберегли $85.7\%$ загального розкиду даних і відкинули лише $14.3\%$ (напрямок $v_2$ з $\lambda_2 = 1$).

Стандартизація. Якщо ознаки мають різні одиниці чи масштаби (роки й гривні, метри й кілограми), дисперсія ознаки з більшими числами штучно домінує, і перша компонента просто «вкаже» на неї. Тоді перед PCA дані стандартизують ($z = \frac{x - \bar{x}}{s}$); це рівносильно застосуванню PCA до кореляційної матриці замість коваріаційної.

Типова помилка (нестандартизовані ознаки). Застосувати PCA до ознак у різних масштабах без стандартизації — і отримати «головну компоненту», що майже збігається з ознакою найбільшого числового діапазону. Це та сама пастка несумірних ознак, що й у метода $k$-середніх (Лекція 9): спершу зведіть ознаки до спільного масштабу.

13.6 Вибір числа компонент #

Скільки компонент $k$ лишити? Три поширені підходи.

Поріг накопиченої дисперсії. Обирають найменше $k$, за якого накопичена пояснена дисперсія перевищує заданий поріг (типово $0.90$ або $0.95$).

Графік «кам’яного осипу» (scree-графік). Будують стовпчики (або ламану) власних значень $\lambda_1 \ge \lambda_2 \ge \dots$ і шукають «лікоть» (англ. elbow) — точку, після якої значення різко вирівнюються: подальші компоненти додають мало, їх відкидають. Назва — від «осипу» дрібного каміння біля підніжжя скелі.

Правило Кайзера. Для PCA на кореляційній матриці лишають компоненти з $\lambda_i > 1$ (така компонента пояснює більше, ніж одна вихідна стандартизована ознака).

Приклад 13.5 (scree та накопичена дисперсія). Нехай PCA п’яти стандартизованих ознак дав власні значення (сума дорівнює $p = 5$):

За порогом $0.95$ треба $k = 4$ компоненти; за порогом $0.88$ — $k = 3$. Правило Кайзера ($\lambda > 1$) лишає $k = 2$ компоненти. На scree-графіку «лікоть» припадає на 2–3 компоненту — далі значення вирівнюються. Остаточний вибір — це компроміс між стисненням і збереженою інформацією.

13.7 Застосування та обмеження #

Застосування:

• Візуалізація. Проєкція на дві перші компоненти дає плоску картину багатовимірних даних, на якій часто видно кластери й викиди.
• Попередня обробка. PCA перед класифікацією (Лекції 6–8) чи кластеризацією (Лекція 9) прибирає корельовані й шумні напрямки, прискорює навчання й послаблює прокляття розмірності.
• Стиснення й прибирання шуму. Відкинувши компоненти з малими $\lambda$, дані зберігають компактніше майже без втрати сигналу.

Обмеження:

• Лінійність. PCA шукає лише лінійні комбінації ознак і плоскі напрямки. Нелінійну структуру (дані на «скрученому» многовиді) він не вловлює — для цього існують ядровий PCA, $t$-SNE, UMAP, автокодувальники (поза межами курсу).
• Інтерпретованість. Головна компонента — «суміш» усіх ознак, її не завжди легко пояснити змістовно.
• Дисперсія $\ne$ корисність. PCA максимізує розкид, не знаючи про мітки класів. Напрямок найбільшої дисперсії може виявитися неінформативним для конкретної задачі класифікації; там доречніші методи з учителем (напр., лінійний дискримінантний аналіз).
• Чутливість до масштабу. Без стандартизації результат визначається одиницями вимірювання (див. §13.5).

Застосування в аналітиці даних #

• Розвідувальний аналіз. Перший погляд на незнайомий багатовимірний набір — проєкція на дві головні компоненти й пошук на ній груп та аномалій.
• Конвеєр моделювання. PCA — стандартний крок попередньої обробки: він знижує розмірність входу для регресії, класифікації та кластеризації, зменшуючи ризик перенавчання й вартість обчислень.
• Стиснення сигналів і зображень. Зберігання даних у базисі кількох головних компонент — простий метод стиснення з контрольованою втратою.
• Діагностика мультиколінеарності. Малі власні значення $\Sigma$ сигналізують про майже лінійно залежні ознаки — корисно перед побудовою регресії (Лекція 5).

Підсумок #

• Прокляття розмірності: зі зростанням числа ознак дані розріджуються, майже всі точки опиняються біля межі, а відстані концентруються — методи на основі відстаней псуються. Розмірність доводиться зменшувати.
• Два шляхи: відбір ознак (лишити підмножину старих) і виділення ознак (побудувати нові комбінації). PCA — це виділення ознак.
• Коваріаційна матриця $\Sigma$ ($p \times p$, симетрична, невід’ємно визначена) містить дисперсії на діагоналі й коваріації поза нею; її слід — загальна дисперсія даних.
• Головні компоненти — власні вектори $\Sigma$, впорядковані за спаданням власних значень; вони ортогональні, а дисперсія вздовж $i$-ї компоненти дорівнює $\lambda_i$. Перша компонента — напрямок максимальної дисперсії.
• Алгоритм PCA: центрувати (за потреби стандартизувати) $\to$ коваріаційна матриця $\to$ власні значення/вектори $\to$ впорядкувати за спаданням $\lambda$ $\to$ спроєктувати на перші $k$ компонент. Якість — частка поясненої дисперсії $\lambda_i / \sum_j \lambda_j$.
• Число компонент обирають за порогом накопиченої дисперсії, за «ліктем» scree-графіка або правилом Кайзера ($\lambda > 1$).
• PCA лінійний і некерований: він не бачить нелінійної структури й міток класів, а його компоненти важче інтерпретувати.

Вправи #

Для розігріву #

1. Поясніть своїми словами два прояви прокляття розмірності. Чому метод $k$ найближчих сусідів гірше працює у просторі великої розмірності?
2. Чим відбір ознак відрізняється від виділення ознак? До якого з них належить PCA і чому?
3. Запишіть означення коваріаційної матриці. Чому вона симетрична й що стоїть на її головній діагоналі?

Стандартні #

4. Для набору точок $(2, 0),\ (0, 2),\ (-2, 0),\ (0, -2)$ обчисліть коваріаційну матрицю (дільник $n - 1$). Які її власні значення й що вони означають про форму хмари точок?
5. Коваріаційна матриця даних дорівнює $\Sigma = \begin{pmatrix} 4 & 3 \\ 3 & 4 \end{pmatrix}$. Через характеристичне рівняння знайдіть власні значення й нормовані власні вектори; обчисліть частку поясненої дисперсії першої головної компоненти. (Відповідь для самоконтролю: $\lambda = 7,\ 1$; частка $7/8 = 0.875$.)
6. PCA дав власні значення $\lambda = (6, 3, 2, 1)$. Побудуйте таблицю часток і накопиченої поясненої дисперсії. Скільки компонент треба лишити, щоб зберегти принаймні $90\%$ дисперсії?

Підвищеної складності #

7. Доведіть, що дисперсія проєкцій центрованих даних на одиничний напрямок $v$ дорівнює $v^{\top}\Sigma v$. Виведіть звідси, що напрямок максимальної дисперсії — це власний вектор $\Sigma$ з найбільшим власним значенням (скористайтеся умовним екстремумом за $\lVert v \rVert = 1$).
8. Поясніть, чому застосування PCA до кореляційної матриці рівносильне PCA до коваріаційної матриці стандартизованих ознак. Наведіть приклад даних, де стандартизація суттєво змінює першу головну компоненту.
9. PCA максимізує дисперсію, не зважаючи на мітки класів. Побудуйте (описово) двовимірний приклад, у якому перша головна компонента марна для класифікації, а розділяє класи саме друга компонента. Який висновок про застосовність PCA як попередньої обробки перед класифікацією?

Lectures/DA-L13.md · 33.5 KB · updated 2026-08-05 09:43