# 2. Методичні вказівки

Цей розділ **самодостатній**: у ньому зібрано теорію методу головних компонент,
потрібну для аудиторних задач ([3classroom.md](3classroom.md)) і домашньої
програми ([4task.md](4task.md)). Ширше ту саму теорію викладено в
[Лекції 13](../../Lectures/DA-L13.md).

## 2.1 Ідея зменшення розмірності

Дані з багатьма ознаками (вимірами) важко аналізувати й візуалізувати, а методи на
основі відстаней (kNN, $k$-середніх) у високій розмірності псуються — це
**прокляття розмірності**. **Метод головних компонент** (англ. *Principal
Component Analysis, PCA*) будує нові ознаки — **головні компоненти** — як лінійні
комбінації вихідних, обираючи їх уздовж напрямків **найбільшої дисперсії**. Перші
кілька компонент несуть майже всю інформацію, тож рештою можна знехтувати.

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

**Вибіркова дисперсія** ознаки $X$ ($n$ спостережень):

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

**Коваріація** двох ознак описує їх спільну зміну:

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

**Коваріаційна матриця** $\Sigma$ набору з $p$ ознак — це матриця $p \times p$ з
елементами $\Sigma_{jk} = \operatorname{cov}(X_j, X_k)$: на діагоналі — дисперсії,
поза діагоналлю — коваріації. Вона **симетрична** ($\Sigma_{jk} = \Sigma_{kj}$),
а її слід $\operatorname{tr}(\Sigma) = \sum_j s_{X_j}^2$ дорівнює **загальній
дисперсії** даних. Для двох ознак

$$ \Sigma = \begin{pmatrix} s_X^2 & \operatorname{cov}(X,Y) \\ \operatorname{cov}(X,Y) & s_Y^2 \end{pmatrix}. $$

> **Дільник $n-1$ чи $n$.** Заміна дільника домножує всю $\Sigma$ на сталу, тож
> **власні вектори** й **частки дисперсії** не змінюються. Ми беремо $n - 1$.

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

Ненульовий вектор $v$ — **власний вектор** матриці $\Sigma$ з **власним значенням**
$\lambda$, якщо $\Sigma v = \lambda v$. Дисперсія проєкцій центрованих даних на
одиничний напрямок $v$ дорівнює $v^{\top}\Sigma v$, і максимізує її власний вектор
із найбільшим $\lambda$.

> **Головні компоненти** — власні вектори $\Sigma$, впорядковані за спаданням
> власних значень. Дисперсія даних уздовж $i$-ї компоненти дорівнює $\lambda_i$.
> Компоненти **ортогональні** (бо $\Sigma$ симетрична).

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

$$ \det(\Sigma - \lambda I) = 0 \ \Longleftrightarrow\ \lambda^2 - (\operatorname{tr}\Sigma)\,\lambda + \det\Sigma = 0. $$

Для кожного кореня $\lambda$ власний вектор дістають, розв'язуючи однорідну систему
$(\Sigma - \lambda I) v = 0$, і нормують його до одиничної довжини.

## 2.4 Проєкція та частка поясненої дисперсії

Проєкція центрованого об'єкта $x_i$ на компоненту $v$: $t_i = v^{\top}(x_i - \bar{x})$.
**Частка поясненої дисперсії** $i$-ї компоненти:

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

Сума часток перших $k$ компонент — **накопичена** пояснена дисперсія. Число
компонент $k$ обирають за порогом накопиченої дисперсії (напр., $0.90$), за
«ліктем» **scree-графіка** власних значень або правилом Кайзера ($\lambda > 1$ для
кореляційної матриці).

## 2.5 Алгоритм PCA

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

## 2.6 Демонстраційний приклад (на інших даних, ніж у задачах)

Нехай маємо п'ять об'єктів із двома ознаками:

$$ (1, 1),\ (3, 5),\ (5, 3),\ (5, 5),\ (6, 6). $$

**Крок 1. Центрування.** Середні: $\bar{x} = \frac{1+3+5+5+6}{5} = 4$,
$\ \bar{y} = \frac{1+5+3+5+6}{5} = 4$. Відхилення $(x_i - 4,\ y_i - 4)$:

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

**Крок 2. Коваріаційна матриця** (дільник $n - 1 = 4$):

$$ \sum \Delta x^2 = 9 + 1 + 1 + 1 + 4 = 16 \ \Rightarrow\ s_X^2 = 4, $$
$$ \sum \Delta y^2 = 9 + 1 + 1 + 1 + 4 = 16 \ \Rightarrow\ s_Y^2 = 4, $$
$$ \sum \Delta x\,\Delta y = 9 - 1 - 1 + 1 + 4 = 12 \ \Rightarrow\ \operatorname{cov}(X,Y) = 3, $$
$$ \Sigma = \begin{pmatrix} 4 & 3 \\ 3 & 4 \end{pmatrix}, \qquad \operatorname{tr}\Sigma = 8. $$

**Крок 3. Власні значення.** Характеристичне рівняння:
$(4 - \lambda)^2 - 9 = 0 \Rightarrow 4 - \lambda = \pm 3 \Rightarrow$

$$ \lambda_1 = 7, \qquad \lambda_2 = 1 \qquad (7 + 1 = 8 = \operatorname{tr}\Sigma). $$

**Власні вектори.** Для $\lambda_1 = 7$: $(\Sigma - 7I)v = 0 \Rightarrow -3v_1 + 3v_2 = 0 \Rightarrow v_1 = v_2$,
тобто $v_1 = \frac{1}{\sqrt{2}}(1, 1)$. Для $\lambda_2 = 1$: $3v_1 + 3v_2 = 0 \Rightarrow v_2 = -v_1$,
тобто $v_2 = \frac{1}{\sqrt{2}}(1, -1)$. Перевірка: $(1,1)\cdot(1,-1) = 0$ —
ортогональні.

**Крок 6. Проєкція на 1-шу компоненту.** $t_i = \frac{1}{\sqrt2}\big((x_i - 4) + (y_i - 4)\big)$:

| об'єкт | відхилення | $t_i = \dfrac{\Delta x + \Delta y}{\sqrt2}$ |
|---|:--:|:--:|
| $(1,1)$ | $(-3,-3)$ | $-6/\sqrt2 \approx -4.243$ |
| $(3,5)$ | $(-1,1)$ | $0$ |
| $(5,3)$ | $(1,-1)$ | $0$ |
| $(5,5)$ | $(1,1)$ | $2/\sqrt2 \approx 1.414$ |
| $(6,6)$ | $(2,2)$ | $4/\sqrt2 \approx 2.828$ |

Дисперсія проєкцій: $\frac{1}{4}\cdot\frac{36 + 0 + 0 + 4 + 16}{2} = \frac{56}{8} = 7 = \lambda_1$ — контроль.

**Частка поясненої дисперсії** першої компоненти:

$$ \frac{\lambda_1}{\lambda_1 + \lambda_2} = \frac{7}{8} = 0.875. $$

Отже, одна головна компонента зберігає $87.5\%$ розкиду даних. *(Усі числа
збігаються з `numpy.linalg.eigh`.)*

## 2.7 Робочий контрольний список

- Спершу **центруйте** дані; якщо ознаки в різних масштабах — **стандартизуйте**.
- Коваріаційну матрицю рахуйте з одним і тим самим дільником ($n - 1$); вона має
  бути **симетричною** — це швидка перевірка.
- Власні значення для $2 \times 2$ шукайте через
  $\lambda^2 - (\operatorname{tr}\Sigma)\lambda + \det\Sigma = 0$; контроль:
  $\lambda_1 + \lambda_2 = \operatorname{tr}\Sigma$, $\ \lambda_1\lambda_2 = \det\Sigma$.
- Дисперсія проєкцій на $i$-ту компоненту має дорівнювати $\lambda_i$ — зручна
  перевірка правильності.
- Частки дисперсії — невід'ємні числа, що дають у сумі $1$.