Викиконспекты - Вклад участника [ru]

Метод главных компонент (PCA)

2020-01-23T00:50:32Z

Ile86171: PCA v0.0.6

[[File:Pca 3d to 2d example.png|500px|thumb|right|Применение PCA к данным в трехмерном пространстве]]
'''Метод главных компонент''' (англ. ''Principal Components Analysis, PCA'') — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) <ref>[https://zenodo.org/record/1430636 Pearson, K. (1901). "On Lines and Planes of Closest Fit to Systems of Points in Space"]</ref> в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т.п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к [[Сингулярное разложение|сингулярному разложению]] матрицы данных. Иногда метод главных компонент называют преобразованием Карунена-Лоэва (англ. ''Karhunen-Loeve'') <ref>[http://fourier.eng.hmc.edu/e161/lectures/klt/node3.html Karhunen-Loeve Transform (KLT)]</ref> или преобразованием Хотеллинга (англ. ''Hotelling transform'').

==Формальная постановка задачи==
[[File:Pearson pca example.jpg|300px|thumb|right|Иллюстрация к работе К. Пирсона (1901): даны точки <tex> P_i</tex> на плоскости, <tex> p_i</tex> — расстояние от <tex> P_i</tex> до прямой <tex> AB</tex>. Ищется прямая <tex> AB</tex>, минимизирующая сумму <tex>\sum_i p_i^2</tex>]]
Пусть имеется $n$ числовых признаков $f_j(x), j = 1, ... , n$. Объекты обучающей выборки будем отождествлять с их признаковыми описаниями: $x_i \equiv (f_1(x_i), ..., f_n(x_i)), i = 1, ..., l$. Рассмотрим матрицу $F$, строки которой соответствуют признаковым описаниям обучающих объектов:
$$F_{l \times n} =
\begin{pmatrix}
f_1(x_1) & ... & f_n(x_1)\\
... & ... & ...\\
f_1(x_l) & ... & f_n(x_l)
\end{pmatrix}
=
\begin{pmatrix}
x_1\\
...\\
x_l
\end{pmatrix}.$$

Обозначим через $z_i = (g_1(x_i), ..., g_m(x_i))$ признаковые описания тех же объектов в новом пространстве $Z = \mathbb{R}^{m}$ меньшей размерности, $m < n$:

$$G_{l \times m} =
\begin{pmatrix}
g_1(x_1) & ... & g_m(x_1)\\
... & ... & ...\\
g_1(x_l) & ... & g_m(x_l)
\end{pmatrix}
=
\begin{pmatrix}
z_1\\
...\\
z_l
\end{pmatrix}.$$

Потребуем, чтобы исходные признаковые описания можно было восстановить по новым описаниям с помощью некоторого линейного преобразования, определяемого матрицей $U = (u_{js})_{n \times m}$:

$$\hat{f}_j(x) = \sum_{s = 1}^{m} g_s(x)u_{js}, \; j = 1, ..., n, \; x \in X,$$

или в векторной записи: $\hat{x} = z U^T$. Восстановленное описание $\hat{x}$ не обязано в точности совпадать с исходным описанием $x$, но их отличие на объектах обучающей выборки должно быть как можно меньше при выбранной размерности $m$. Будем искать одновременно и матрицу новых признаковых описаний $G$, и матрицу линейного преобразования $U$, при которых суммарная невязка $\Delta^2(G, U) = \sum_{i = 1}^{l} \| \hat{x}_i - x_i \|^2$ восстановленных описаний минимальна:

$$\Delta^2(G, U) = \sum_{i = 1}^{l} \| \hat{x}_i - x_i \|^2 = \sum_{i = 1}^{l} \| z_i U^T - x_i \|^2 = \| GU^T - F \|^2 \to \mathop{min}_{G, U},$$

где все нормы евклидовы.

Будем предполагать, что матрицы $G$ и $U$ невырождены: $rank \, G = rank \, U = m$. Иначе существовало бы представление $\bar{G} \bar{U}^T = G U^T$ с числом столбцов в матрице $\bar{G}$, меньшим $m$. Поэтому интересны лишь случаи, когда $m \leq rank \, F$.

==Решение==

Исчерпывающее решение сформулированной задачи даёт следующая теорема.

{{Теорема
|statement = Если $m \leq rank \, F$, то минимум $\Delta^2(G, U)$ достигается, когда столбцы матрицы $U$ есть собственные векторы $F^T F$, соответствующие $m$ максимальным собственным значениям. При этом $G = F U$, матрицы $U$ и $G$ ортогональны.

|proof = Запишем необходимые условия минимума:

<tex>
\frac{\partial \Delta^2}{\partial G} = (G U^T - F) U = 0;\\ \frac{\partial \Delta^2}{\partial U} = G^T (G U^T - F) = 0.
</tex>

Поскольку искомые матрицы $G$ и $U$ невырождены, отсюда следует:

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Функционал $\Delta^2(G, U)$ зависит только от произведения матриц $G U^T$, поэтому решение задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ определено с точностью до произвольного невырожденного преобразования $R: G U^T = (G R) (R^{-1} U^T)$. Распорядимся свободой выбора $R$ так, чтобы матрицы $U^T U$ и $G^T G$ оказались диагональными. Покажем, что это всегда возможно.

Пусть $\tilde{G} \tilde{U}^T$ {{---}} произвольное решение задачи.

Матрица $\tilde{U}^T \tilde{U}$ симметричная, невырожденная, положительно определенная, поэтому существует невырожденная матрица $S_{m \times m}$ такая, что $S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T = I_m$.

Матрица $S^T \tilde{G}^T \tilde{G} S$ симметричная и невырожденная, поэтому существует ортогональная матрица $T_{m \times m}$ такая, что $T^T (S^T \tilde{G}^T \tilde{G} S) T = diag(\lambda_1, ..., \lambda_m) \equiv \Lambda$ {{---}} диагональная матрица. По определению ортогональности $T^T T = I_m$.

Преобразование $R = S T$ невырождено. Положим $G = \tilde{G} R$, $U^T = R^{-1} \tilde{U}^T$. Тогда

<tex>
G^T G = T^T (S^T \tilde{G}^T \tilde{G} S) T = \Lambda;\\ U^T U = T^{-1} (S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T) (T^{-1})^T = (T^T T)^{-1} = I_m.
</tex>

В силу $G U^T = \tilde{G} \tilde{U}^T$ матрицы $G$ и $U$ являются решением задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ и удовлетворяют необходимому условию минимума. Подставим матрицы $G$ и $U$ в

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Благодаря диагональности $G^T G$ и $U^T U$ соотношения существенно упростятся:

<tex>
G = F U;\\ U \Lambda = F^T G.
</tex>

Подставим первое соотношение во второе, получим $U \Lambda = F^T F U$. Это означает, что столбцы матрицы $U$ обязаны быть собственными векторами матрицы $F^T F$, а диагональные элементы $\lambda_1, ..., \lambda_m$ - соответствующими им собственными значениями.

Аналогично, подставив второе соотношение в первое, получим $G \Lambda = F F^T G$, то есть столбцы матрицы $G$ являются собственными векторами $F F^T$, соответствующими тем же самым собственным значениям.

Подставляя $G$ и $U$ в функционал $\Delta^2(G, U)$, находим:

<tex>
\Delta^2(G, U) = \| F - G U^T \|^2 = tr \, (F^T - U G^t)(F - G U^T) = tr \, F^T (F - G U^T) = tr \, F^T F - tr \, F^T G U^T = \| F \|^2 - tr \, U \Lambda U^T = \| F \|^2 - tr \, \Lambda = \sum_{j = 1}^{n} \lambda_j - \sum_{j = 1}^{m} \lambda_j - \sum_{j = m + 1}^{n} \lambda_j,
</tex>

где $\lambda_1 , ..., \lambda_n$ - все собственные значения матрицы $F^T F$. Минимум $\Delta^2$ достигается, когда $\lambda_1, ..., \lambda_m$ {{---}} наибольшие $m$ из $n$ собственных значений.

Собственные векторы $u_1, ..., u_m$, отвечающие максимальным собственным значениям, называют ''главными компонентами''.
}}

==Свойства==

===Связь с сингулярным разложением===

Если $m = n$, то $\Delta^2(G, U) = 0$. В этом случае представление $F = G U^T$ является точным и совпадает с сингулярным разложением: $F = G U^T = V D U^T$, если положить $G = V D$ и $\Lambda = D^2$. При этом матрица $V$ ортогональна: $V^T V = I_m$.

Если $m < n$, то представление $F \approx G U^T$ является приближённым. Сингулярное разложение матрицы $G U^T$ получается из сингулярного разложения матрицы $F$ путём отбрасывания (обнуления) $n - m$ минимальных собственных значений.

===Преобразование Карунена–Лоэва===

Диагональность матрицы $G^T G = \Lambda$ означает, что новые признаки $g_1, ..., g_m$ не коррелируют на объектах из обучающей выборки. Ортогональное преобразование $U$ называют ''декоррелирующим'' или преобразованием ''Карунена–Лоэва''. Если $m = n$, то о прямое и обратное преобразование вычисляются с помощью одной и той же матрицы $U: F = G U^T$ и $G = F U$.

===Эффективная размерность===

Главные компоненты содержат основную информацию о матрице $F$. Число главных компонент $m$ называют также ''эффективной размерностью'' задачи. На практике её определяют следующим образом. Все собственные значения матрицы $F^T F$ упорядочиваются по убыванию: $\lambda_1 \geq ... \geq \lambda_n \geq 0$. Задаётся пороговое значение $\epsilon \in [0, 1]$, достаточно близкое к нулю, и определяется наименьшее целое $m$, при котором относительная погрешность приближения матрицы $F$ не превышает $\epsilon$:

$$E(m) = \frac{\| G U^T - F \|^2}{\| F \|^2} = \frac{\lambda_{m + 1} + ... + \lambda_n}{\lambda_1 + ... + \lambda_n} \leq \epsilon .$$

Величина $E(m)$ показывает, какая доля информации теряется при замене исходных признаковых описаний длины $n$ на более короткие описания длины $m$. Метод главных компонент особенно эффективен в тех случаях, когда $E(m)$ оказывается малым уже при малых значениях $m$. Если задать число $\epsilon$ из априорных соображений не представляется возможным, прибегают к ''критерию «крутого обрыва»''. На графике $E(m)$ отмечается то значение $m$, при котором происходит резкий скачок: $E(m - 1) \gg E(m)$, при условии, что $E(m)$ уже достаточно мало.

==Визуализация многомерных данных==

[[File:Pca dim reduction.png|650px|thumb|right|Уменьшение размерности данных с помощью PCA]]
Метод главных компонент часто используется для представления многомерной выборки данных на двумерном графике. Для этого полагают $m = 2$ и полученные пары значений $(g_1(x_i), g_2(x_i)), i = 1, ..., l$, наносят как точки на график. Проекция на главные компоненты является наименее искаженной из всех линейных проекций многомерной выборки на какую-либо пару осей. Как правило, в осях главных компонент удаётся увидеть наиболее существенные особенности исходных данных, даже несмотря на неизбежные искажения. В частности, можно судить о наличии кластерных структур и выбросов. Две оси $g_1$ и $g_2$ отражают «две основные тенденции» в данных. Иногда их удаётся интерпретировать, если внимательно изучить, какие точки на графике являются «самыми левыми», «самыми правыми», «самыми верхними» и «самыми нижними». Этот вид анализа не позволяет делать точные количественные выводы и обычно используется
с целью понимания данных. Аналогичную роль играют многомерное шкалирование <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%88%D0%BA%D0%B0%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Многомерное шкалирование]</ref> и карты Кохонена <ref name=Cohonen> [https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%BC%D0%BE%D0%BE%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D1%83%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0 Самоорганизующаяся карта Кохонена]</ref>.

==Пределы применимости и ограничения эффективности метода==

Метод главных компонент применим всегда. Распространённое утверждение о том, что он применим только к нормально распределённым данным (или для распределений, близких к нормальным) неверно: в исходной формулировке К. Пирсона ставится задача об ''аппроксимации'' конечного множества данных и отсутствует даже гипотеза о их статистическом порождении, не говоря уж о распределении.

Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность $E(m)$. Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности.

Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например самоорганизующиеся карты Кохонена <ref name=Cohonen /> или нейронный газ <ref>[https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D0%B0%D0%B7 Нейронный газ]</ref>. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к независимым компонентам <ref>[https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 Анализ независимых компонент]</ref>, которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.

==Пример кода scikit-learn==
Пример применения PCA к датасету Iris для уменьшения размерности:
# Импорт библиотек
import numpy as np
import matplotlib.pyplot as plt
from sklearn import decomposition
from sklearn import datasets

# Загрузка данных
centers = [[1, 1], [-1, -1], [1, -1]]
iris = datasets.load_iris()
X = iris.data
y = iris.target

[[File:Pca iris example.png|275px|thumb|right|Применения PCA к датасету Iris]]
# Преобразование данных датасета Iris, уменьшающее размерность до 2
pca = decomposition.PCA(n_components=3)
pca.fit(X)
X = pca.transform(X)
y = np.choose(y, [1, 2, 0]).astype(np.float)
plt.clf()
plt.cla()
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.nipy_spectral, edgecolor='k')
plt.xlabel("PC1")
plt.ylabel("PC2")
plt.show()

==См. также==

*[[Уменьшение размерности]]
*[[Сингулярное разложение]]

==Примечания==
<references/>

==Источники информации==

#[http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 machinelearning.ru — Метод главных компонент]
#[https://www.youtube.com/watch?v=wcJ0nSUr7ws Лекция "Регрессионный анализ и метод главных компонентов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
#[http://research.cs.tamu.edu/prism/lectures/pr/pr_l9.pdf PCA] {{---}} курс ML Texas A&M University
#[https://en.wikipedia.org/wiki/Principal_component_analysis Principal Component Analysis] {{---}} статья про Principal Component Analysis в Wikipedia
#[https://towardsdatascience.com/understanding-pca-fae3e243731d Understanding PCA]

[[Категория: Машинное обучение]]
[[Категория: Уменьшение размерности]]
[[Категория: Метод главных компонент]]

Метод главных компонент (PCA)

2020-01-23T00:46:01Z

Ile86171: PCA v0.0.5

[[File:Pca 3d to 2d example.png|500px|thumb|right|Применение PCA к данным в трехмерном пространстве]]
'''Метод главных компонент''' (англ. ''Principal Components Analysis, PCA'') — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) <ref>[https://zenodo.org/record/1430636 Pearson, K. (1901). "On Lines and Planes of Closest Fit to Systems of Points in Space"]</ref> в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т.п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к [[Сингулярное разложение|сингулярному разложению]] матрицы данных. Иногда метод главных компонент называют преобразованием Карунена-Лоэва (англ. ''Karhunen-Loeve'') <ref>[http://fourier.eng.hmc.edu/e161/lectures/klt/node3.html Karhunen-Loeve Transform (KLT)]</ref> или преобразованием Хотеллинга (англ. ''Hotelling transform'').

==Формальная постановка задачи==
[[File:Pearson pca example.jpg|300px|thumb|right|Иллюстрация к работе К. Пирсона (1901): даны точки <tex> P_i</tex> на плоскости, <tex> p_i</tex> — расстояние от <tex> P_i</tex> до прямой <tex> AB</tex>. Ищется прямая <tex> AB</tex>, минимизирующая сумму <tex>\sum_i p_i^2</tex>]]
Пусть имеется $n$ числовых признаков $f_j(x), j = 1, ... , n$. Объекты обучающей выборки будем отождествлять с их признаковыми описаниями: $x_i \equiv (f_1(x_i), ..., f_n(x_i)), i = 1, ..., l$. Рассмотрим матрицу $F$, строки которой соответствуют признаковым описаниям обучающих объектов:
$$F_{l \times n} =
\begin{pmatrix}
f_1(x_1) & ... & f_n(x_1)\\
... & ... & ...\\
f_1(x_l) & ... & f_n(x_l)
\end{pmatrix}
=
\begin{pmatrix}
x_1\\
...\\
x_l
\end{pmatrix}.$$

Обозначим через $z_i = (g_1(x_i), ..., g_m(x_i))$ признаковые описания тех же объектов в новом пространстве $Z = \mathbb{R}^{m}$ меньшей размерности, $m < n$:

$$G_{l \times m} =
\begin{pmatrix}
g_1(x_1) & ... & g_m(x_1)\\
... & ... & ...\\
g_1(x_l) & ... & g_m(x_l)
\end{pmatrix}
=
\begin{pmatrix}
z_1\\
...\\
z_l
\end{pmatrix}.$$

Потребуем, чтобы исходные признаковые описания можно было восстановить по новым описаниям с помощью некоторого линейного преобразования, определяемого матрицей $U = (u_{js})_{n \times m}$:

$$\hat{f}_j(x) = \sum_{s = 1}^{m} g_s(x)u_{js}, \; j = 1, ..., n, \; x \in X,$$

или в векторной записи: $\hat{x} = z U^T$. Восстановленное описание $\hat{x}$ не обязано в точности совпадать с исходным описанием $x$, но их отличие на объектах обучающей выборки должно быть как можно меньше при выбранной размерности $m$. Будем искать одновременно и матрицу новых признаковых описаний $G$, и матрицу линейного преобразования $U$, при которых суммарная невязка восстановленных описаний минимальна:

$$\Delta^2(G, U) = \sum_{i = 1}^{l} \| \hat{x}_i - x_i \|^2 = \sum_{i = 1}^{l} \| z_i U^T - x_i \|^2 = \| GU^T - F \|^2 \to \mathop{min}_{G, U},$$

где все нормы евклидовы.

Будем предполагать, что матрицы $G$ и $U$ невырождены: $rank \, G = rank \, U = m$. Иначе существовало бы представление $\bar{G} \bar{U}^T = G U^T$ с числом столбцов в матрице $\bar{G}$, меньшим $m$. Поэтому интересны лишь случаи, когда $m \leq rank \, F$.

==Решение==

Исчерпывающее решение сформулированной задачи даёт следующая теорема.

{{Теорема
|statement = Если $m \leq rank \, F$, то минимум $\Delta^2(G, U)$ достигается, когда столбцы матрицы $U$ есть собственные векторы $F^T F$, соответствующие $m$ максимальным собственным значениям. При этом $G = F U$, матрицы $U$ и $G$ ортогональны.

|proof = Запишем необходимые условия минимума:

<tex>
\frac{\partial \Delta^2}{\partial G} = (G U^T - F) U = 0;\\ \frac{\partial \Delta^2}{\partial U} = G^T (G U^T - F) = 0.
</tex>

Поскольку искомые матрицы $G$ и $U$ невырождены, отсюда следует:

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Функционал $\Delta^2(G, U)$ зависит только от произведения матриц $G U^T$, поэтому решение задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ определено с точностью до произвольного невырожденного преобразования $R: G U^T = (G R) (R^{-1} U^T)$. Распорядимся свободой выбора $R$ так, чтобы матрицы $U^T U$ и $G^T G$ оказались диагональными. Покажем, что это всегда возможно.

Пусть $\tilde{G} \tilde{U}^T$ {{---}} произвольное решение задачи.

Матрица $\tilde{U}^T \tilde{U}$ симметричная, невырожденная, положительно определенная, поэтому существует невырожденная матрица $S_{m \times m}$ такая, что $S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T = I_m$.

Матрица $S^T \tilde{G}^T \tilde{G} S$ симметричная и невырожденная, поэтому существует ортогональная матрица $T_{m \times m}$ такая, что $T^T (S^T \tilde{G}^T \tilde{G} S) T = diag(\lambda_1, ..., \lambda_m) \equiv \Lambda$ {{---}} диагональная матрица. По определению ортогональности $T^T T = I_m$.

Преобразование $R = S T$ невырождено. Положим $G = \tilde{G} R$, $U^T = R^{-1} \tilde{U}^T$. Тогда

<tex>
G^T G = T^T (S^T \tilde{G}^T \tilde{G} S) T = \Lambda;\\ U^T U = T^{-1} (S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T) (T^{-1})^T = (T^T T)^{-1} = I_m.
</tex>

В силу $G U^T = \tilde{G} \tilde{U}^T$ матрицы $G$ и $U$ являются решением задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ и удовлетворяют необходимому условию минимума. Подставим матрицы $G$ и $U$ в

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Благодаря диагональности $G^T G$ и $U^T U$ соотношения существенно упростятся:

<tex>
G = F U;\\ U \Lambda = F^T G.
</tex>

Подставим первое соотношение во второе, получим $U \Lambda = F^T F U$. Это означает, что столбцы матрицы $U$ обязаны быть собственными векторами матрицы $F^T F$, а диагональные элементы $\lambda_1, ..., \lambda_m$ - соответствующими им собственными значениями.

Аналогично, подставив второе соотношение в первое, получим $G \Lambda = F F^T G$, то есть столбцы матрицы $G$ являются собственными векторами $F F^T$, соответствующими тем же самым собственным значениям.

Подставляя $G$ и $U$ в функционал $\Delta^2(G, U)$, находим:

<tex>
\Delta^2(G, U) = \| F - G U^T \|^2 = tr \, (F^T - U G^t)(F - G U^T) = tr \, F^T (F - G U^T) = tr \, F^T F - tr \, F^T G U^T = \| F \|^2 - tr \, U \Lambda U^T = \| F \|^2 - tr \, \Lambda = \sum_{j = 1}^{n} \lambda_j - \sum_{j = 1}^{m} \lambda_j - \sum_{j = m + 1}^{n} \lambda_j,
</tex>

где $\lambda_1 , ..., \lambda_n$ - все собственные значения матрицы $F^T F$. Минимум $\Delta^2$ достигается, когда $\lambda_1, ..., \lambda_m$ {{---}} наибольшие $m$ из $n$ собственных значений.

Собственные векторы $u_1, ..., u_m$, отвечающие максимальным собственным значениям, называют ''главными компонентами''.
}}

==Свойства==

===Связь с сингулярным разложением===

Если $m = n$, то $\Delta^2(G, U) = 0$. В этом случае представление $F = G U^T$ является точным и совпадает с сингулярным разложением: $F = G U^T = V D U^T$, если положить $G = V D$ и $\Lambda = D^2$. При этом матрица $V$ ортогональна: $V^T V = I_m$.

Если $m < n$, то представление $F \approx G U^T$ является приближённым. Сингулярное разложение матрицы $G U^T$ получается из сингулярного разложения матрицы $F$ путём отбрасывания (обнуления) $n - m$ минимальных собственных значений.

===Преобразование Карунена–Лоэва===

Диагональность матрицы $G^T G = \Lambda$ означает, что новые признаки $g_1, ..., g_m$ не коррелируют на объектах из обучающей выборки. Ортогональное преобразование $U$ называют ''декоррелирующим'' или преобразованием ''Карунена–Лоэва''. Если $m = n$, то о прямое и обратное преобразование вычисляются с помощью одной и той же матрицы $U: F = G U^T$ и $G = F U$.

===Эффективная размерность===

Главные компоненты содержат основную информацию о матрице $F$. Число главных компонент $m$ называют также ''эффективной размерностью'' задачи. На практике её определяют следующим образом. Все собственные значения матрицы $F^T F$ упорядочиваются по убыванию: $\lambda_1 \geq ... \geq \lambda_n \geq 0$. Задаётся пороговое значение $\epsilon \in [0, 1]$, достаточно близкое к нулю, и определяется наименьшее целое $m$, при котором относительная погрешность приближения матрицы $F$ не превышает $\epsilon$:

$$E(m) = \frac{\| G U^T - F \|^2}{\| F \|^2} = \frac{\lambda_{m + 1} + ... + \lambda_n}{\lambda_1 + ... + \lambda_n} \leq \epsilon .$$

Величина $E(m)$ показывает, какая доля информации теряется при замене исходных признаковых описаний длины $n$ на более короткие описания длины $m$. Метод главных компонент особенно эффективен в тех случаях, когда $E(m)$ оказывается малым уже при малых значениях $m$. Если задать число $\epsilon$ из априорных соображений не представляется возможным, прибегают к ''критерию «крутого обрыва»''. На графике $E(m)$ отмечается то значение $m$, при котором происходит резкий скачок: $E(m - 1) \gg E(m)$, при условии, что $E(m)$ уже достаточно мало.

==Визуализация многомерных данных==

[[File:Pca dim reduction.png|650px|thumb|right|Уменьшение размерности данных с помощью PCA]]
Метод главных компонент часто используется для представления многомерной выборки данных на двумерном графике. Для этого полагают $m = 2$ и полученные пары значений $(g_1(x_i), g_2(x_i)), i = 1, ..., l$, наносят как точки на график. Проекция на главные компоненты является наименее искаженной из всех линейных проекций многомерной выборки на какую-либо пару осей. Как правило, в осях главных компонент удаётся увидеть наиболее существенные особенности исходных данных, даже несмотря на неизбежные искажения. В частности, можно судить о наличии кластерных структур и выбросов. Две оси $g_1$ и $g_2$ отражают «две основные тенденции» в данных. Иногда их удаётся интерпретировать, если внимательно изучить, какие точки на графике являются «самыми левыми», «самыми правыми», «самыми верхними» и «самыми нижними». Этот вид анализа не позволяет делать точные количественные выводы и обычно используется
с целью понимания данных. Аналогичную роль играют многомерное шкалирование <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%88%D0%BA%D0%B0%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Многомерное шкалирование]</ref> и карты Кохонена <ref name=Cohonen> [https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%BC%D0%BE%D0%BE%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D1%83%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0 Самоорганизующаяся карта Кохонена]</ref>.

==Пределы применимости и ограничения эффективности метода==

Метод главных компонент применим всегда. Распространённое утверждение о том, что он применим только к нормально распределённым данным (или для распределений, близких к нормальным) неверно: в исходной формулировке К. Пирсона ставится задача об ''аппроксимации'' конечного множества данных и отсутствует даже гипотеза о их статистическом порождении, не говоря уж о распределении.

Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность $E(m)$. Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности.

Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например самоорганизующиеся карты Кохонена <ref name=Cohonen /> или нейронный газ <ref>[https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D0%B0%D0%B7 Нейронный газ]</ref>. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к независимым компонентам <ref>[https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 Анализ независимых компонент]</ref>, которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.

==Пример кода scikit-learn==
Пример применения PCA к датасету Iris для уменьшения размерности:
# Импорт библиотек
import numpy as np
import matplotlib.pyplot as plt
from sklearn import decomposition
from sklearn import datasets

# Загрузка данных
centers = [[1, 1], [-1, -1], [1, -1]]
iris = datasets.load_iris()
X = iris.data
y = iris.target

[[File:Pca iris example.png|275px|thumb|right|Применения PCA к датасету Iris]]
# Преобразование данных датасета Iris, уменьшающее размерность до 2
pca = decomposition.PCA(n_components=3)
pca.fit(X)
X = pca.transform(X)
y = np.choose(y, [1, 2, 0]).astype(np.float)
plt.clf()
plt.cla()
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.nipy_spectral, edgecolor='k')
plt.xlabel("PC1")
plt.ylabel("PC2")
plt.show()

==См. также==

*[[Уменьшение размерности]]
*[[Сингулярное разложение]]

==Примечания==
<references/>

==Источники информации==

#[http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 machinelearning.ru — Метод главных компонент]
#[https://www.youtube.com/watch?v=wcJ0nSUr7ws Лекция "Регрессионный анализ и метод главных компонентов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
#[http://research.cs.tamu.edu/prism/lectures/pr/pr_l9.pdf PCA] {{---}} курс ML Texas A&M University
#[https://en.wikipedia.org/wiki/Principal_component_analysis Principal Component Analysis] {{---}} статья про Principal Component Analysis в Wikipedia
#[https://towardsdatascience.com/understanding-pca-fae3e243731d Understanding PCA]

[[Категория: Машинное обучение]]
[[Категория: Уменьшение размерности]]
[[Категория: Метод главных компонент]]

Файл:Pca dim reduction.png

2020-01-23T00:43:01Z

Ile86171:

Метод главных компонент (PCA)

2020-01-23T00:16:10Z

Ile86171: PCA v0.0.4

[[File:Pca 3d to 2d example.png|500px|thumb|right|Применение PCA к данным в трехмерном пространстве]]
'''Метод главных компонент''' (англ. ''Principal Components Analysis, PCA'') — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) <ref>[https://zenodo.org/record/1430636 Pearson, K. (1901). "On Lines and Planes of Closest Fit to Systems of Points in Space"]</ref> в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т.п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к [[Сингулярное разложение|сингулярному разложению]] матрицы данных. Иногда метод главных компонент называют преобразованием Карунена-Лоэва (англ. ''Karhunen-Loeve'') <ref>[http://fourier.eng.hmc.edu/e161/lectures/klt/node3.html Karhunen-Loeve Transform (KLT)]</ref> или преобразованием Хотеллинга (англ. ''Hotelling transform'').

==Формальная постановка задачи==
[[File:Pearson pca example.jpg|300px|thumb|right|Иллюстрация к работе К. Пирсона (1901): даны точки <tex> P_i</tex> на плоскости, <tex> p_i</tex> — расстояние от <tex> P_i</tex> до прямой <tex> AB</tex>. Ищется прямая <tex> AB</tex>, минимизирующая сумму <tex>\sum_i p_i^2</tex>]]
Пусть имеется $n$ числовых признаков $f_j(x), j = 1, ... , n$. Объекты обучающей выборки будем отождествлять с их признаковыми описаниями: $x_i \equiv (f_1(x_i), ..., f_n(x_i)), i = 1, ..., l$. Рассмотрим матрицу $F$, строки которой соответствуют признаковым описаниям обучающих объектов:
$$F_{l \times n} =
\begin{pmatrix}
f_1(x_1) & ... & f_n(x_1)\\
... & ... & ...\\
f_1(x_l) & ... & f_n(x_l)
\end{pmatrix}
=
\begin{pmatrix}
x_1\\
...\\
x_l
\end{pmatrix}.$$

Обозначим через $z_i = (g_1(x_i), ..., g_m(x_i))$ признаковые описания тех же объектов в новом пространстве $Z = \mathbb{R}^{m}$ меньшей размерности, $m < n$:

$$G_{l \times m} =
\begin{pmatrix}
g_1(x_1) & ... & g_m(x_1)\\
... & ... & ...\\
g_1(x_l) & ... & g_m(x_l)
\end{pmatrix}
=
\begin{pmatrix}
z_1\\
...\\
z_l
\end{pmatrix}.$$

Потребуем, чтобы исходные признаковые описания можно было восстановить по новым описаниям с помощью некоторого линейного преобразования, определяемого матрицей $U = (u_{js})_{n \times m}$:

$$\hat{f}_j(x) = \sum_{s = 1}^{m} g_s(x)u_{js}, \; j = 1, ..., n, \; x \in X,$$

или в векторной записи: $\hat{x} = z U^T$. Восстановленное описание $\hat{x}$ не обязано в точности совпадать с исходным описанием $x$, но их отличие на объектах обучающей выборки должно быть как можно меньше при выбранной размерности $m$. Будем искать одновременно и матрицу новых признаковых описаний $G$, и матрицу линейного преобразования $U$, при которых суммарная невязка восстановленных описаний минимальна:

$$\Delta^2(G, U) = \sum_{i = 1}^{l} \| \hat{x}_i - x_i \|^2 = \sum_{i = 1}^{l} \| z_i U^T - x_i \|^2 = \| GU^T - F \|^2 \to \mathop{min}_{G, U},$$

где все нормы евклидовы.

Будем предполагать, что матрицы $G$ и $U$ невырождены: $rank \, G = rank \, U = m$. Иначе существовало бы представление $\bar{G} \bar{U}^T = G U^T$ с числом столбцов в матрице $\bar{G}$, меньшим $m$. Поэтому интересны лишь случаи, когда $m \leq rank \, F$.

==Решение==

Исчерпывающее решение сформулированной задачи даёт следующая теорема.

{{Теорема
|statement = Если $m \leq rank \, F$, то минимум $\Delta^2(G, U)$ достигается, когда столбцы матрицы $U$ есть собственные векторы $F^T F$, соответствующие $m$ максимальным собственным значениям. При этом $G = F U$, матрицы $U$ и $G$ ортогональны.

|proof = Запишем необходимые условия минимума:

<tex>
\frac{\partial \Delta^2}{\partial G} = (G U^T - F) U = 0;\\ \frac{\partial \Delta^2}{\partial U} = G^T (G U^T - F) = 0.
</tex>

Поскольку искомые матрицы $G$ и $U$ невырождены, отсюда следует:

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Функционал $\Delta^2(G, U)$ зависит только от произведения матриц $G U^T$, поэтому решение задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ определено с точностью до произвольного невырожденного преобразования $R: G U^T = (G R) (R^{-1} U^T)$. Распорядимся свободой выбора $R$ так, чтобы матрицы $U^T U$ и $G^T G$ оказались диагональными. Покажем, что это всегда возможно.

Пусть $\tilde{G} \tilde{U}^T$ {{---}} произвольное решение задачи.

Матрица $\tilde{U}^T \tilde{U}$ симметричная, невырожденная, положительно определенная, поэтому существует невырожденная матрица $S_{m \times m}$ такая, что $S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T = I_m$.

Матрица $S^T \tilde{G}^T \tilde{G} S$ симметричная и невырожденная, поэтому существует ортогональная матрица $T_{m \times m}$ такая, что $T^T (S^T \tilde{G}^T \tilde{G} S) T = diag(\lambda_1, ..., \lambda_m) \equiv \Lambda$ {{---}} диагональная матрица. По определению ортогональности $T^T T = I_m$.

Преобразование $R = S T$ невырождено. Положим $G = \tilde{G} R$, $U^T = R^{-1} \tilde{U}^T$. Тогда

<tex>
G^T G = T^T (S^T \tilde{G}^T \tilde{G} S) T = \Lambda;\\ U^T U = T^{-1} (S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T) (T^{-1})^T = (T^T T)^{-1} = I_m.
</tex>

В силу $G U^T = \tilde{G} \tilde{U}^T$ матрицы $G$ и $U$ являются решением задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ и удовлетворяют необходимому условию минимума. Подставим матрицы $G$ и $U$ в

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Благодаря диагональности $G^T G$ и $U^T U$ соотношения существенно упростятся:

<tex>
G = F U;\\ U \Lambda = F^T G.
</tex>

Подставим первое соотношение во второе, получим $U \Lambda = F^T F U$. Это означает, что столбцы матрицы $U$ обязаны быть собственными векторами матрицы $F^T F$, а диагональные элементы $\lambda_1, ..., \lambda_m$ - соответствующими им собственными значениями.

Аналогично, подставив второе соотношение в первое, получим $G \Lambda = F F^T G$, то есть столбцы матрицы $G$ являются собственными векторами $F F^T$, соответствующими тем же самым собственным значениям.

Подставляя $G$ и $U$ в функционал $\Delta^2(G, U)$, находим:

<tex>
\Delta^2(G, U) = \| F - G U^T \|^2 = tr \, (F^T - U G^t)(F - G U^T) = tr \, F^T (F - G U^T) = tr \, F^T F - tr \, F^T G U^T = \| F \|^2 - tr \, U \Lambda U^T = \| F \|^2 - tr \, \Lambda = \sum_{j = 1}^{n} \lambda_j - \sum_{j = 1}^{m} \lambda_j - \sum_{j = m + 1}^{n} \lambda_j,
</tex>

где $\lambda_1 , ..., \lambda_n$ - все собственные значения матрицы $F^T F$. Минимум $\Delta^2$ достигается, когда $\lambda_1, ..., \lambda_m$ {{---}} наибольшие $m$ из $n$ собственных значений.

Собственные векторы $u_1, ..., u_m$, отвечающие максимальным собственным значениям, называют ''главными компонентами''.
}}

==Свойства==

===Связь с сингулярным разложением===

Если $m = n$, то $\Delta^2(G, U) = 0$. В этом случае представление $F = G U^T$ является точным и совпадает с сингулярным разложением: $F = G U^T = V D U^T$, если положить $G = V D$ и $\Lambda = D^2$. При этом матрица $V$ ортогональна: $V^T V = I_m$.

Если $m < n$, то представление $F \approx G U^T$ является приближённым. Сингулярное разложение матрицы $G U^T$ получается из сингулярного разложения матрицы $F$ путём отбрасывания (обнуления) $n - m$ минимальных собственных значений.

===Преобразование Карунена–Лоэва===

Диагональность матрицы $G^T G = \Lambda$ означает, что новые признаки $g_1, ..., g_m$ не коррелируют на объектах из обучающей выборки. Ортогональное преобразование $U$ называют ''декоррелирующим'' или преобразованием ''Карунена–Лоэва''. Если $m = n$, то о прямое и обратное преобразование вычисляются с помощью одной и той же матрицы $U: F = G U^T$ и $G = F U$.

===Эффективная размерность===

Главные компоненты содержат основную информацию о матрице $F$. Число главных компонент $m$ называют также ''эффективной размерностью'' задачи. На практике её определяют следующим образом. Все собственные значения матрицы $F^T F$ упорядочиваются по убыванию: $\lambda_1 \geq ... \geq \lambda_n \geq 0$. Задаётся пороговое значение $\epsilon \in [0, 1]$, достаточно близкое к нулю, и определяется наименьшее целое $m$, при котором относительная погрешность приближения матрицы $F$ не превышает $\epsilon$:

$$E(m) = \frac{\| G U^T - F \|^2}{\| F \|^2} = \frac{\lambda_{m + 1} + ... + \lambda_n}{\lambda_1 + ... + \lambda_n} \leq \epsilon .$$

Величина $E(m)$ показывает, какая доля информации теряется при замене исходных признаковых описаний длины $n$ на более короткие описания длины $m$. Метод главных компонент особенно эффективен в тех случаях, когда $E(m)$ оказывается малым уже при малых значениях $m$. Если задать число $\epsilon$ из априорных соображений не представляется возможным, прибегают к ''критерию «крутого обрыва»''. На графике $E(m)$ отмечается то значение $m$, при котором происходит резкий скачок: $E(m - 1) \gg E(m)$, при условии, что $E(m)$ уже достаточно мало.

==Визуализация многомерных данных==

Метод главных компонент часто используется для представления многомерной выборки данных на двумерном графике. Для этого полагают $m = 2$ и полученные пары значений $(g_1(x_i), g_2(x_i)), i = 1, ..., l$, наносят как точки на график. Проекция на главные компоненты является наименее искаженной из всех линейных проекций многомерной выборки на какую-либо пару осей. Как правило, в осях главных компонент удаётся увидеть наиболее существенные особенности исходных данных, даже несмотря на неизбежные искажения. В частности, можно судить о наличии кластерных структур и выбросов. Две оси $g_1$ и $g_2$ отражают «две основные тенденции» в данных. Иногда их удаётся интерпретировать, если внимательно изучить, какие точки на графике являются «самыми левыми», «самыми правыми», «самыми верхними» и «самыми нижними». Этот вид анализа не позволяет делать точные количественные выводы и обычно используется
с целью понимания данных. Аналогичную роль играют многомерное шкалирование <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%88%D0%BA%D0%B0%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Многомерное шкалирование]</ref> и карты Кохонена <ref name=Cohonen> [https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%BC%D0%BE%D0%BE%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D1%83%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0 Самоорганизующаяся карта Кохонена]</ref>.

==Пределы применимости и ограничения эффективности метода==

Метод главных компонент применим всегда. Распространённое утверждение о том, что он применим только к нормально распределённым данным (или для распределений, близких к нормальным) неверно: в исходной формулировке К. Пирсона ставится задача об ''аппроксимации'' конечного множества данных и отсутствует даже гипотеза о их статистическом порождении, не говоря уж о распределении.

Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность $E(m)$. Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности.

Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например самоорганизующиеся карты Кохонена <ref name=Cohonen /> или нейронный газ <ref>[https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D0%B0%D0%B7 Нейронный газ]</ref>. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к независимым компонентам <ref>[https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 Анализ независимых компонент]</ref>, которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.

==Пример кода scikit-learn==
Пример применения PCA к датасету Iris для уменьшения размерности:
# Импорт библиотек
import numpy as np
import matplotlib.pyplot as plt
from sklearn import decomposition
from sklearn import datasets

# Загрузка данных
centers = [[1, 1], [-1, -1], [1, -1]]
iris = datasets.load_iris()
X = iris.data
y = iris.target

[[File:Pca iris example.png|275px|thumb|right|Применения PCA к датасету Iris]]
# Преобразование данных датасета Iris, уменьшающее размерность до 2
pca = decomposition.PCA(n_components=3)
pca.fit(X)
X = pca.transform(X)
y = np.choose(y, [1, 2, 0]).astype(np.float)
plt.clf()
plt.cla()
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.nipy_spectral, edgecolor='k')
plt.xlabel("PC1")
plt.ylabel("PC2")
plt.show()

==См. также==

*[[Уменьшение размерности]]
*[[Сингулярное разложение]]

==Примечания==
<references/>

==Источники информации==

#[http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 machinelearning.ru — Метод главных компонент]
#[https://www.youtube.com/watch?v=wcJ0nSUr7ws Лекция "Регрессионный анализ и метод главных компонентов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
#[http://research.cs.tamu.edu/prism/lectures/pr/pr_l9.pdf PCA] {{---}} курс ML Texas A&M University
#[https://en.wikipedia.org/wiki/Principal_component_analysis Principal Component Analysis] {{---}} статья про Principal Component Analysis в Wikipedia
#[https://towardsdatascience.com/understanding-pca-fae3e243731d Understanding PCA]

[[Категория: Машинное обучение]]
[[Категория: Уменьшение размерности]]
[[Категория: Метод главных компонент]]

Метод главных компонент (PCA)

2020-01-23T00:03:12Z

Ile86171: PCA v0.0.3

[[File:Pca 3d to 2d example.png|500px|thumb|right|Применение PCA к данным в трехмерном пространстве]]
'''Метод главных компонент''' (англ. ''Principal Components Analysis, PCA'') — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) <ref>[https://zenodo.org/record/1430636 Pearson, K. (1901). "On Lines and Planes of Closest Fit to Systems of Points in Space"]</ref> в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т.п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к [[Сингулярное разложение|сингулярному разложению]] матрицы данных. Иногда метод главных компонент называют преобразованием Карунена-Лоэва (англ. ''Karhunen-Loeve'') <ref>[http://fourier.eng.hmc.edu/e161/lectures/klt/node3.html Karhunen-Loeve Transform (KLT)]</ref> или преобразованием Хотеллинга (англ. ''Hotelling transform'').

==Формальная постановка задачи==
[[File:Pearson pca example.jpg|300px|thumb|right|Иллюстрация к работе К. Пирсона (1901): даны точки <tex> P_i</tex> на плоскости, <tex> p_i</tex> — расстояние от <tex> P_i</tex> до прямой <tex> AB</tex>. Ищется прямая <tex> AB</tex>, минимизирующая сумму <tex>\sum_i p_i^2</tex>]]
Пусть имеется $n$ числовых признаков $f_j(x), j = 1, ... , n$. Объекты обучающей выборки будем отождествлять с их признаковыми описаниями: $x_i \equiv (f_1(x_i), ..., f_n(x_i)), i = 1, ..., l$. Рассмотрим матрицу $F$, строки которой соответствуют признаковым описаниям обучающих объектов:
$$F_{l \times n} =
\begin{pmatrix}
f_1(x_1) & ... & f_n(x_1)\\
... & ... & ...\\
f_1(x_l) & ... & f_n(x_l)
\end{pmatrix}
=
\begin{pmatrix}
x_1\\
...\\
x_l
\end{pmatrix}.$$

Обозначим через $z_i = (g_1(x_i), ..., g_m(x_i))$ признаковые описания тех же объектов в новом пространстве $Z = \mathbb{R}^{m}$ меньшей размерности, $m < n$:

$$G_{l \times m} =
\begin{pmatrix}
g_1(x_1) & ... & g_m(x_1)\\
... & ... & ...\\
g_1(x_l) & ... & g_m(x_l)
\end{pmatrix}
=
\begin{pmatrix}
z_1\\
...\\
z_l
\end{pmatrix}.$$

Потребуем, чтобы исходные признаковые описания можно было восстановить по новым описаниям с помощью некоторого линейного преобразования, определяемого матрицей $U = (u_{js})_{n \times m}$:

$$\hat{f}_j(x) = \sum_{s = 1}^{m} g_s(x)u_{js}, \; j = 1, ..., n, \; x \in X,$$

или в векторной записи: $\hat{x} = z U^T$. Восстановленное описание $\hat{x}$ не обязано в точности совпадать с исходным описанием $x$, но их отличие на объектах обучающей выборки должно быть как можно меньше при выбранной размерности $m$. Будем искать одновременно и матрицу новых признаковых описаний $G$, и матрицу линейного преобразования $U$, при которых суммарная невязка восстановленных описаний минимальна:

$$\Delta^2(G, U) = \sum_{i = 1}^{l} \| \hat{x}_i - x_i \|^2 = \sum_{i = 1}^{l} \| z_i U^T - x_i \|^2 = \| GU^T - F \|^2 \to \mathop{min}_{G, U},$$

где все нормы евклидовы.

Будем предполагать, что матрицы $G$ и $U$ невырождены: $rank \, G = rank \, U = m$. Иначе существовало бы представление $\bar{G} \bar{U}^T = G U^T$ с числом столбцов в матрице $\bar{G}$, меньшим $m$. Поэтому интересны лишь случаи, когда $m \leq rank \, F$.

==Решение==

Исчерпывающее решение сформулированной задачи даёт следующая теорема.

{{Теорема
|statement = Если $m \leq rank \, F$, то минимум $\Delta^2(G, U)$ достигается, когда столбцы матрицы $U$ есть собственные векторы $F^T F$, соответствующие $m$ максимальным собственным значениям. При этом $G = F U$, матрицы $U$ и $G$ ортогональны.

|proof = Запишем необходимые условия минимума:

<tex>
\frac{\partial \Delta^2}{\partial G} = (G U^T - F) U = 0;\\ \frac{\partial \Delta^2}{\partial U} = G^T (G U^T - F) = 0.
</tex>

Поскольку искомые матрицы $G$ и $U$ невырождены, отсюда следует:

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Функционал $\Delta^2(G, U)$ зависит только от произведения матриц $G U^T$, поэтому решение задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ определено с точностью до произвольного невырожденного преобразования $R: G U^T = (G R) (R^{-1} U^T)$. Распорядимся свободой выбора $R$ так, чтобы матрицы $U^T U$ и $G^T G$ оказались диагональными. Покажем, что это всегда возможно.

Пусть $\tilde{G} \tilde{U}^T$ {{---}} произвольное решение задачи.

Матрица $\tilde{U}^T \tilde{U}$ симметричная, невырожденная, положительно определенная, поэтому существует невырожденная матрица $S_{m \times m}$ такая, что $S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T = I_m$.

Матрица $S^T \tilde{G}^T \tilde{G} S$ симметричная и невырожденная, поэтому существует ортогональная матрица $T_{m \times m}$ такая, что $T^T (S^T \tilde{G}^T \tilde{G} S) T = diag(\lambda_1, ..., \lambda_m) \equiv \Lambda$ {{---}} диагональная матрица. По определению ортогональности $T^T T = I_m$.

Преобразование $R = S T$ невырождено. Положим $G = \tilde{G} R$, $U^T = R^{-1} \tilde{U}^T$. Тогда

<tex>
G^T G = T^T (S^T \tilde{G}^T \tilde{G} S) T = \Lambda;\\ U^T U = T^{-1} (S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T) (T^{-1})^T = (T^T T)^{-1} = I_m.
</tex>

В силу $G U^T = \tilde{G} \tilde{U}^T$ матрицы $G$ и $U$ являются решением задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ и удовлетворяют необходимому условию минимума. Подставим матрицы $G$ и $U$ в

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Благодаря диагональности $G^T G$ и $U^T U$ соотношения существенно упростятся:

<tex>
G = F U;\\ U \Lambda = F^T G.
</tex>

Подставим первое соотношение во второе, получим $U \Lambda = F^T F U$. Это означает, что столбцы матрицы $U$ обязаны быть собственными векторами матрицы $F^T F$, а диагональные элементы $\lambda_1, ..., \lambda_m$ - соответствующими им собственными значениями.

Аналогично, подставив второе соотношение в первое, получим $G \Lambda = F F^T G$, то есть столбцы матрицы $G$ являются собственными векторами $F F^T$, соответствующими тем же самым собственным значениям.

Подставляя $G$ и $U$ в функционал $\Delta^2(G, U)$, находим:

<tex>
\Delta^2(G, U) = \| F - G U^T \|^2 = tr \, (F^T - U G^t)(F - G U^T) = tr \, F^T (F - G U^T) = tr \, F^T F - tr \, F^T G U^T = \| F \|^2 - tr \, U \Lambda U^T = \| F \|^2 - tr \, \Lambda = \sum_{j = 1}^{n} \lambda_j - \sum_{j = 1}^{m} \lambda_j - \sum_{j = m + 1}^{n} \lambda_j,
</tex>

где $\lambda_1 , ..., \lambda_n$ - все собственные значения матрицы $F^T F$. Минимум $\Delta^2$ достигается, когда $\lambda_1, ..., \lambda_m$ {{---}} наибольшие $m$ из $n$ собственных значений.

Собственные векторы $u_1, ..., u_m$, отвечающие максимальным собственным значениям, называют ''главными компонентами''.
}}

==Свойства==

===Связь с сингулярным разложением===

Если $m = n$, то $\Delta^2(G, U) = 0$. В этом случае представление $F = G U^T$ является точным и совпадает с сингулярным разложением: $F = G U^T = V D U^T$, если положить $G = V D$ и $\Lambda = D^2$. При этом матрица $V$ ортогональна: $V^T V = I_m$.

Если $m < n$, то представление $F \approx G U^T$ является приближённым. Сингулярное разложение матрицы $G U^T$ получается из сингулярного разложения матрицы $F$ путём отбрасывания (обнуления) $n - m$ минимальных собственных значений.

===Преобразование Карунена–Лоэва===

Диагональность матрицы $G^T G = \Lambda$ означает, что новые признаки $g_1, ..., g_m$ не коррелируют на объектах из обучающей выборки. Ортогональное преобразование $U$ называют ''декоррелирующим'' или преобразованием ''Карунена–Лоэва''. Если $m = n$, то о прямое и обратное преобразование вычисляются с помощью одной и той же матрицы $U: F = G U^T$ и $G = F U$.

===Эффективная размерность===

Главные компоненты содержат основную информацию о матрице $F$. Число главных компонент $m$ называют также ''эффективной размерностью'' задачи. На практике её определяют следующим образом. Все собственные значения матрицы $F^T F$ упорядочиваются по убыванию: $\lambda_1 \geq ... \geq \lambda_n \geq 0$. Задаётся пороговое значение $\epsilon \in [0, 1]$, достаточно близкое к нулю, и определяется наименьшее целое $m$, при котором относительная погрешность приближения матрицы $F$ не превышает $\epsilon$:

$$E(m) = \frac{\| G U^T - F \|^2}{\| F \|^2} = \frac{\lambda_{m + 1} + ... + \lambda_n}{\lambda_1 + ... + \lambda_n} \leq \epsilon .$$

Величина $E(m)$ показывает, какая доля информации теряется при замене исходных признаковых описаний длины $n$ на более короткие описания длины $m$. Метод главных компонент особенно эффективен в тех случаях, когда $E(m)$ оказывается малым уже при малых значениях $m$. Если задать число $\epsilon$ из априорных соображений не представляется возможным, прибегают к ''критерию «крутого обрыва»''. На графике $E(m)$ отмечается то значение $m$, при котором происходит резкий скачок: $E(m - 1) \gg E(m)$, при условии, что $E(m)$ уже достаточно мало.

==Визуализация многомерных данных==

Метод главных компонент часто используется для представления многомерной выборки данных на двумерном графике. Для этого полагают $m = 2$ и полученные пары значений $(g_1(x_i), g_2(x_i)), i = 1, ..., l$, наносят как точки на график. Проекция на главные компоненты является наименее искаженной из всех линейных проекций многомерной выборки на какую-либо пару осей. Как правило, в осях главных компонент удаётся увидеть наиболее существенные особенности исходных данных, даже несмотря на неизбежные искажения. В частности, можно судить о наличии кластерных структур и выбросов. Две оси $g_1$ и $g_2$ отражают «две основные тенденции» в данных. Иногда их удаётся интерпретировать, если внимательно изучить, какие точки на графике являются «самыми левыми», «самыми правыми», «самыми верхними» и «самыми нижними». Этот вид анализа не позволяет делать точные количественные выводы и обычно используется
с целью понимания данных. Аналогичную роль играют многомерное шкалирование <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%88%D0%BA%D0%B0%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Многомерное шкалирование]</ref> и карты Кохонена <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%BC%D0%BE%D0%BE%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D1%83%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0 Самоорганизующаяся карта Кохонена]</ref>.

==Пример кода scikit-learn==
Пример применения PCA к датасету Iris для уменьшения размерности:
# Импорт библиотек
import numpy as np
import matplotlib.pyplot as plt
from sklearn import decomposition
from sklearn import datasets

# Загрузка данных
centers = [[1, 1], [-1, -1], [1, -1]]
iris = datasets.load_iris()
X = iris.data
y = iris.target

[[File:Pca iris example.png|275px|thumb|right|Применения PCA к датасету Iris]]
# Преобразование данных датасета Iris, уменьшающее размерность до 2
pca = decomposition.PCA(n_components=3)
pca.fit(X)
X = pca.transform(X)
y = np.choose(y, [1, 2, 0]).astype(np.float)
plt.clf()
plt.cla()
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.nipy_spectral, edgecolor='k')
plt.xlabel("PC1")
plt.ylabel("PC2")
plt.show()

==См. также==

*[[Уменьшение размерности]]
*[[Сингулярное разложение]]

==Примечания==
<references/>

==Источники информации==

#[http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 machinelearning.ru — Метод главных компонент]
#[https://www.youtube.com/watch?v=wcJ0nSUr7ws Лекция "Регрессионный анализ и метод главных компонентов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
#[http://research.cs.tamu.edu/prism/lectures/pr/pr_l9.pdf PCA] {{---}} курс ML Texas A&M University
#[https://en.wikipedia.org/wiki/Principal_component_analysis Principal Component Analysis] {{---}} статья про Principal Component Analysis в Wikipedia
#[https://towardsdatascience.com/understanding-pca-fae3e243731d Understanding PCA]

[[Категория: Машинное обучение]]
[[Категория: Уменьшение размерности]]
[[Категория: Метод главных компонент]]

Файл:Pca 3d to 2d example.png

2020-01-23T00:01:04Z

Ile86171:

Метод главных компонент (PCA)

2020-01-22T23:57:12Z

Ile86171: PCA v0.0.2

'''Метод главных компонент''' (англ. ''Principal Components Analysis, PCA'') — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) <ref>[https://zenodo.org/record/1430636 Pearson, K. (1901). "On Lines and Planes of Closest Fit to Systems of Points in Space"]</ref> в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т.п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к [[Сингулярное разложение|сингулярному разложению]] матрицы данных. Иногда метод главных компонент называют преобразованием Карунена-Лоэва (англ. ''Karhunen-Loeve'') <ref>[http://fourier.eng.hmc.edu/e161/lectures/klt/node3.html Karhunen-Loeve Transform (KLT)]</ref> или преобразованием Хотеллинга (англ. ''Hotelling transform'').

==Формальная постановка задачи==
[[File:Pearson pca example.jpg|300px|thumb|right|Иллюстрация к работе К. Пирсона (1901): даны точки <tex> P_i</tex> на плоскости, <tex> p_i</tex> — расстояние от <tex> P_i</tex> до прямой <tex> AB</tex>. Ищется прямая <tex> AB</tex>, минимизирующая сумму <tex>\sum_i p_i^2</tex>]]
Пусть имеется $n$ числовых признаков $f_j(x), j = 1, ... , n$. Объекты обучающей выборки будем отождествлять с их признаковыми описаниями: $x_i \equiv (f_1(x_i), ..., f_n(x_i)), i = 1, ..., l$. Рассмотрим матрицу $F$, строки которой соответствуют признаковым описаниям обучающих объектов:
$$F_{l \times n} =
\begin{pmatrix}
f_1(x_1) & ... & f_n(x_1)\\
... & ... & ...\\
f_1(x_l) & ... & f_n(x_l)
\end{pmatrix}
=
\begin{pmatrix}
x_1\\
...\\
x_l
\end{pmatrix}.$$

Обозначим через $z_i = (g_1(x_i), ..., g_m(x_i))$ признаковые описания тех же объектов в новом пространстве $Z = \mathbb{R}^{m}$ меньшей размерности, $m < n$:

$$G_{l \times m} =
\begin{pmatrix}
g_1(x_1) & ... & g_m(x_1)\\
... & ... & ...\\
g_1(x_l) & ... & g_m(x_l)
\end{pmatrix}
=
\begin{pmatrix}
z_1\\
...\\
z_l
\end{pmatrix}.$$

Потребуем, чтобы исходные признаковые описания можно было восстановить по новым описаниям с помощью некоторого линейного преобразования, определяемого матрицей $U = (u_{js})_{n \times m}$:

$$\hat{f}_j(x) = \sum_{s = 1}^{m} g_s(x)u_{js}, \; j = 1, ..., n, \; x \in X,$$

или в векторной записи: $\hat{x} = z U^T$. Восстановленное описание $\hat{x}$ не обязано в точности совпадать с исходным описанием $x$, но их отличие на объектах обучающей выборки должно быть как можно меньше при выбранной размерности $m$. Будем искать одновременно и матрицу новых признаковых описаний $G$, и матрицу линейного преобразования $U$, при которых суммарная невязка восстановленных описаний минимальна:

$$\Delta^2(G, U) = \sum_{i = 1}^{l} \| \hat{x}_i - x_i \|^2 = \sum_{i = 1}^{l} \| z_i U^T - x_i \|^2 = \| GU^T - F \|^2 \to \mathop{min}_{G, U},$$

где все нормы евклидовы.

Будем предполагать, что матрицы $G$ и $U$ невырождены: $rank \, G = rank \, U = m$. Иначе существовало бы представление $\bar{G} \bar{U}^T = G U^T$ с числом столбцов в матрице $\bar{G}$, меньшим $m$. Поэтому интересны лишь случаи, когда $m \leq rank \, F$.

==Решение==

Исчерпывающее решение сформулированной задачи даёт следующая теорема.

{{Теорема
|statement = Если $m \leq rank \, F$, то минимум $\Delta^2(G, U)$ достигается, когда столбцы матрицы $U$ есть собственные векторы $F^T F$, соответствующие $m$ максимальным собственным значениям. При этом $G = F U$, матрицы $U$ и $G$ ортогональны.

|proof = Запишем необходимые условия минимума:

<tex>
\frac{\partial \Delta^2}{\partial G} = (G U^T - F) U = 0;\\ \frac{\partial \Delta^2}{\partial U} = G^T (G U^T - F) = 0.
</tex>

Поскольку искомые матрицы $G$ и $U$ невырождены, отсюда следует:

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Функционал $\Delta^2(G, U)$ зависит только от произведения матриц $G U^T$, поэтому решение задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ определено с точностью до произвольного невырожденного преобразования $R: G U^T = (G R) (R^{-1} U^T)$. Распорядимся свободой выбора $R$ так, чтобы матрицы $U^T U$ и $G^T G$ оказались диагональными. Покажем, что это всегда возможно.

Пусть $\tilde{G} \tilde{U}^T$ {{---}} произвольное решение задачи.

Матрица $\tilde{U}^T \tilde{U}$ симметричная, невырожденная, положительно определенная, поэтому существует невырожденная матрица $S_{m \times m}$ такая, что $S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T = I_m$.

Матрица $S^T \tilde{G}^T \tilde{G} S$ симметричная и невырожденная, поэтому существует ортогональная матрица $T_{m \times m}$ такая, что $T^T (S^T \tilde{G}^T \tilde{G} S) T = diag(\lambda_1, ..., \lambda_m) \equiv \Lambda$ {{---}} диагональная матрица. По определению ортогональности $T^T T = I_m$.

Преобразование $R = S T$ невырождено. Положим $G = \tilde{G} R$, $U^T = R^{-1} \tilde{U}^T$. Тогда

<tex>
G^T G = T^T (S^T \tilde{G}^T \tilde{G} S) T = \Lambda;\\ U^T U = T^{-1} (S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T) (T^{-1})^T = (T^T T)^{-1} = I_m.
</tex>

В силу $G U^T = \tilde{G} \tilde{U}^T$ матрицы $G$ и $U$ являются решением задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ и удовлетворяют необходимому условию минимума. Подставим матрицы $G$ и $U$ в

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Благодаря диагональности $G^T G$ и $U^T U$ соотношения существенно упростятся:

<tex>
G = F U;\\ U \Lambda = F^T G.
</tex>

Подставим первое соотношение во второе, получим $U \Lambda = F^T F U$. Это означает, что столбцы матрицы $U$ обязаны быть собственными векторами матрицы $F^T F$, а диагональные элементы $\lambda_1, ..., \lambda_m$ - соответствующими им собственными значениями.

Аналогично, подставив второе соотношение в первое, получим $G \Lambda = F F^T G$, то есть столбцы матрицы $G$ являются собственными векторами $F F^T$, соответствующими тем же самым собственным значениям.

Подставляя $G$ и $U$ в функционал $\Delta^2(G, U)$, находим:

<tex>
\Delta^2(G, U) = \| F - G U^T \|^2 = tr \, (F^T - U G^t)(F - G U^T) = tr \, F^T (F - G U^T) = tr \, F^T F - tr \, F^T G U^T = \| F \|^2 - tr \, U \Lambda U^T = \| F \|^2 - tr \, \Lambda = \sum_{j = 1}^{n} \lambda_j - \sum_{j = 1}^{m} \lambda_j - \sum_{j = m + 1}^{n} \lambda_j,
</tex>

где $\lambda_1 , ..., \lambda_n$ - все собственные значения матрицы $F^T F$. Минимум $\Delta^2$ достигается, когда $\lambda_1, ..., \lambda_m$ {{---}} наибольшие $m$ из $n$ собственных значений.

Собственные векторы $u_1, ..., u_m$, отвечающие максимальным собственным значениям, называют ''главными компонентами''.
}}

==Свойства==

===Связь с сингулярным разложением===

Если $m = n$, то $\Delta^2(G, U) = 0$. В этом случае представление $F = G U^T$ является точным и совпадает с сингулярным разложением: $F = G U^T = V D U^T$, если положить $G = V D$ и $\Lambda = D^2$. При этом матрица $V$ ортогональна: $V^T V = I_m$.

Если $m < n$, то представление $F \approx G U^T$ является приближённым. Сингулярное разложение матрицы $G U^T$ получается из сингулярного разложения матрицы $F$ путём отбрасывания (обнуления) $n - m$ минимальных собственных значений.

===Преобразование Карунена–Лоэва===

Диагональность матрицы $G^T G = \Lambda$ означает, что новые признаки $g_1, ..., g_m$ не коррелируют на объектах из обучающей выборки. Ортогональное преобразование $U$ называют ''декоррелирующим'' или преобразованием ''Карунена–Лоэва''. Если $m = n$, то о прямое и обратное преобразование вычисляются с помощью одной и той же матрицы $U: F = G U^T$ и $G = F U$.

===Эффективная размерность===

Главные компоненты содержат основную информацию о матрице $F$. Число главных компонент $m$ называют также ''эффективной размерностью'' задачи. На практике её определяют следующим образом. Все собственные значения матрицы $F^T F$ упорядочиваются по убыванию: $\lambda_1 \geq ... \geq \lambda_n \geq 0$. Задаётся пороговое значение $\epsilon \in [0, 1]$, достаточно близкое к нулю, и определяется наименьшее целое $m$, при котором относительная погрешность приближения матрицы $F$ не превышает $\epsilon$:

$$E(m) = \frac{\| G U^T - F \|^2}{\| F \|^2} = \frac{\lambda_{m + 1} + ... + \lambda_n}{\lambda_1 + ... + \lambda_n} \leq \epsilon .$$

Величина $E(m)$ показывает, какая доля информации теряется при замене исходных признаковых описаний длины $n$ на более короткие описания длины $m$. Метод главных компонент особенно эффективен в тех случаях, когда $E(m)$ оказывается малым уже при малых значениях $m$. Если задать число $\epsilon$ из априорных соображений не представляется возможным, прибегают к ''критерию «крутого обрыва»''. На графике $E(m)$ отмечается то значение $m$, при котором происходит резкий скачок: $E(m - 1) \gg E(m)$, при условии, что $E(m)$ уже достаточно мало.

==Визуализация многомерных данных==

Метод главных компонент часто используется для представления многомерной выборки данных на двумерном графике. Для этого полагают $m = 2$ и полученные пары значений $(g_1(x_i), g_2(x_i)), i = 1, ..., l$, наносят как точки на график. Проекция на главные компоненты является наименее искаженной из всех линейных проекций многомерной выборки на какую-либо пару осей. Как правило, в осях главных компонент удаётся увидеть наиболее существенные особенности исходных данных, даже несмотря на неизбежные искажения. В частности, можно судить о наличии кластерных структур и выбросов. Две оси $g_1$ и $g_2$ отражают «две основные тенденции» в данных. Иногда их удаётся интерпретировать, если внимательно изучить, какие точки на графике являются «самыми левыми», «самыми правыми», «самыми верхними» и «самыми нижними». Этот вид анализа не позволяет делать точные количественные выводы и обычно используется
с целью понимания данных. Аналогичную роль играют многомерное шкалирование <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%88%D0%BA%D0%B0%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Многомерное шкалирование]</ref> и карты Кохонена <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%BC%D0%BE%D0%BE%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D1%83%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0 Самоорганизующаяся карта Кохонена]</ref>.

==Пример кода scikit-learn==
Пример применения PCA к датасету Iris для уменьшения размерности:
# Импорт библиотек
import numpy as np
import matplotlib.pyplot as plt
from sklearn import decomposition
from sklearn import datasets

# Загрузка данных
centers = [[1, 1], [-1, -1], [1, -1]]
iris = datasets.load_iris()
X = iris.data
y = iris.target

[[File:Pca iris example.png|275px|thumb|right|Применения PCA к датасету Iris]]
# Преобразование данных датасета Iris, уменьшающее размерность до 2
pca = decomposition.PCA(n_components=3)
pca.fit(X)
X = pca.transform(X)
y = np.choose(y, [1, 2, 0]).astype(np.float)
plt.clf()
plt.cla()
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.nipy_spectral, edgecolor='k')
plt.xlabel("PC1")
plt.ylabel("PC2")
plt.show()

==См. также==

*[[Уменьшение размерности]]
*[[Сингулярное разложение]]

==Примечания==
<references/>

==Источники информации==

#[http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 machinelearning.ru — Метод главных компонент]
#[https://www.youtube.com/watch?v=wcJ0nSUr7ws Лекция "Регрессионный анализ и метод главных компонентов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
#[http://research.cs.tamu.edu/prism/lectures/pr/pr_l9.pdf PCA] {{---}} курс ML Texas A&M University
#[https://en.wikipedia.org/wiki/Principal_component_analysis Principal Component Analysis] {{---}} статья про Principal Component Analysis в Wikipedia
#[https://towardsdatascience.com/understanding-pca-fae3e243731d Understanding PCA]

[[Категория: Машинное обучение]]
[[Категория: Уменьшение размерности]]
[[Категория: Метод главных компонент]]

Уменьшение размерности

2020-01-22T23:56:35Z

Ile86171: Отмена правки 72392, сделанной Ile86171 (обсуждение)

Под '''уменьшением размерности''' (англ. ''dimensionality reduction'') в машинном обучении подразумевается уменьшение числа признаков набора данных. Наличие в нем признаков избыточных, неинформативных или слабо информативных может понизить эффективность модели, а после такого преобразования она упрощается, и соответственно уменьшается размер набора данных в памяти и ускоряется работа алгоритмов ML на нем. Уменьшение размерности может быть осуществлено методами выбора признаков (англ. ''feature selection'') или выделения признаков (англ. ''feature extraction'').
==Выбор признаков==
Методы '''выбора признаков''' оставляют некоторое подмножество исходного набора признаков, избавляясь от признаков избыточных и слабо информативных. Основные преимущества этого класса алгоритмов:
*Уменьшение вероятности [[переобучение|переобучения]];
*Увеличение точности предсказания модели;
*Сокращение времени обучения;
*Увеличивается семантическое понимание модели.

Все методы выбора признаков можно разделить на 5 типов, которые отличаются алгоритмами выбора лишних признаков.
===Фильтры===
'''Фильтры''' (англ. ''filter methods'') измеряют релевантность признаков на основе функции $\mu$, и затем решают по правилу $\kappa$, какие признаки оставить в результирующем множестве.

Фильтры могут быть:
*Одномерные (англ. ''univariate'') {{---}} функция $\mu$ определяет релевантность одного признака по отношению к выходным меткам. В таком случае обычно измеряют "качество" каждого признака и удаляют худшие;
*Многомерные (англ. ''multivariate'') {{---}} функция $\mu$ определяет релевантность некоторого подмножества исходного множества признаков относительно выходных меток.

Распространенными вариантами для $\mu$ являются:
*Коэффициент ранговой корреляции Спирмена <ref>[https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient Определение коэффициента ранговой корреляции Спирмена]</ref>(англ. ''Spearman's rank correlation coefficient''): $p(x, y)=\displaystyle \frac{\sum_{i, j}(x_{ij}-\bar{x_j})(y_i-\bar{y})}{\sqrt{\sum_{i, j}(x_{ij}-\bar{x_j})^2\sum_i(y_i-\bar{y})^2}}$;
*Information gain<ref>[https://en.wikipedia.org/wiki/Information_gain_in_decision_trees Определение information gain]</ref>: $IG(x, y)=\displaystyle -\sum_{i=1}^kp(c_i)\log_2{(p(c_i))}+\sum_{i=1}^{n}p(t_i)\sum_{j=1}^kp(c_j|t_i)log_2{(p(c_j|t_i))}$, и другие.

Преимуществом группы фильтров является простота вычисления релевантности признаков в наборе данных, но недостатком в таком подходе является игнорирование возможных зависимостей между признаками.
===Оберточные методы===
[[File:Feature_selection_wrapper_rus.png|450px|thumb|right|Процесс работы оберточных методов]]
'''Оберточные методы''' (англ. ''wrapper methods'') находят подмножество искомых признаков последовательно, используя некоторый классификатор как источник оценки качества выбранных признаков, т.е. этот процесс является циклическим и продолжается до тех пор, пока не будут достигнуты заданные условия останова. Оберточные методы учитывают зависимости между признаками, что является преимуществом по сравнению с фильтрами, к тому же показывают большую точность, но вычисления занимают длительное время, и повышается риск [[переобучение|переобучения]].

Существует несколько типов оберточных методов: детерминированные, которые изменяют множество признаков по определенному правилу, а также рандомизированные, которые используют генетические алгоритмы для выбора искомого подмножества признаков. Среди детерминированных алгоритмов самыми простыми являются:
*SFS (Sequential Forward Selection) {{---}} жадный алгоритм, который начинает с пустого множества признаков, на каждом шаге добавляя лучший из еще не выбранных признаков в результирующее множество;
*SBS (Sequential Backward Selection) {{---}} алгоритм обратный SFS, который начинает с изначального множества признаков, и удаляет по одному или несколько худших признаков на каждом шаге.

Популярным оберточным методом является SVM-RFE (SVM-based Recursive Feature Elimination), который иногда также обозначается как встроенный <ref>[https://benthamopen.com/FULLTEXT/TOBIOIJ-11-117/ C. Embedded method]</ref>. Этот метод использует как классификатор [[Метод опорных векторов (SVM)| SVM]][на 28.01.19 не создан] и работает итеративно: начиная с полного множества признаков обучает классификатор, ранжирует признаки по весам, которые им присвоил классификатор, убирает какое-то число признаков и повторяет процесс с оставшегося подмножества фичей, если не было достигнуто их требуемое количество. Таким образом, этот метод очень похож на встроенный, потому что непосредственно использует знание того, как устроен классификатор.

===Встроенные методы===
[[File:Feature_selection_embedded_rus.png|450px|thumb|right|Процесс работы встроенных методов]]
Группа '''встроенных методов''' (англ. ''embedded methods'') очень похожа на оберточные методы, но для выбора признаков используется непосредственно структуру некоторого классификатора. В оберточных методах классификатор служит только для оценки работы на данном множестве признаков, тогда как встроенные методы используют какую-то информацию о признаках, которую классификаторы присваивают во время обучения.

Одним из примеров встроенного метода является реализация на [[Дерево решений и случайный лес| случайном лесе]]: каждому дереву на вход подаются случайное подмножество данных из датасета с каким-то случайным набор признаков, в процессе обучения каждое из деревьев решений производит "голосование" за релевантность его признаков, эти данные агрегируются, и на выходе получаются значения важности каждого признака набора данных. Дальнейший выбор нужных нам признаков уже зависит от выбранного критерия отбора.

Встроенные методы используют преимущества оберточных методов и являются более эффективными, при этом на отбор тратится меньше времени, уменьшается риск [[переобучение|переобучения]], но т.к. полученный набор признаков был отобран на основе знаний о классификаторе, то есть вероятность, что для другого классификатора это множество признаков уже не будет настолько же релевантным.

===Другие методы===
[[File:Feature_selection_ensemble_rus.png|thumb|Один из примеров процесса работы ансамблевых методов]]
Есть и другие методы выбора признаков: '''гибридные''' (англ. ''hybrid methods'') и '''ансамблевые''' (англ. ''ensemble methods''). '''Гибридные методы''' комбинируют несколько разных методов выбора признаков, например, некоторое множество фильтров, а потом запускают оберточный или встроенный метод. Таким образом, гибридные методы сочетают в себе преимущества сразу нескольких методов, и на практике повышают эффективность выбора признаков.

'''Ансамблевые методы''' применяются больше для наборов данных с очень большим числом признаков. В данном подходе для начального множества признаков создается несколько подмножеств признаков, и эти группы каким-то образом объединяются, чтобы получить набор самых релевантных признаков. Это довольно гибкая группа методов, т.к. для нее можно применять различные способы выбора признаков и объединения их подмножеств.

<div style="clear:{{{1|both}}};"></div>

===Примеры кода scikit-learn===
Пример кода, реализующего функцию оценки фильтра на основе коэффициента ранговой корреляции:
# Импорт библиотек
import pandas as pd
import numpy as np

# Вспомогательная функция для расчета корреляции
def correlation(X, Y):
return np.cov(X, Y) / np.sqrt(np.var(X) * np.var(Y))

# Сам фильтр на основе метрики ранговой корреляции
# Аргументы X -- значения объектов датасета для какой-то фичи, Y -- метки этих объектов
def measure_spearmans(X, Y):
xr = pd.Series(X).rank()
yr = pd.Series(Y).rank()
return correlation(xr, yr)

Пример кода, реализующего SVM-RFE wrapper:
# Импорт библиотек
import numpy as np
import pandas as pd
from sklearn import svm

# X -- наш датасет, Y -- массив меток
# N -- число признаков, которые хотим оставить, step -- сколько фичей удаляется на каждой итерации
# Возвращает массив из булевых переменных размерностью 1x[число признаков], показывающий, отбрасываем признак или нет
def RFE(X, Y, N, step = 10):
# cache_size нужен, если набор данных большой, иначе можно опустить
clfRFE = svm.SVC(kernel='linear', cache_size=1024)
featureCount = X.shape[1]
featureList = np.arange(0, featureCount )
included = np.full(featureCount, True)
curCount = featureCount
while curCount > N:
actualFeatures = featureList[included]
Xnew = X[:, actualFeatures]

clfRFE.fit(Xnew, Y)
curStep = min(step, curCount - N)
elim = np.argsort(np.abs(clfRFE.coef_[0]))[:curStep]
included[actualFeatures[elim]] = False
curCount -= curStep
return included
==Выделение признаков==
Другим способом уменьшить размерность входных данных является выделение признаков. Эти методы каким-то образом составляют из уже исходных признаков новые, все также полностью описывающие пространство набора данных, но уменьшая его размерность и теряя в репрезентативности данных, т.к. становится непонятно, за что отвечают новые признаки.
Все методы feature extraction можно разделить на '''линейные''' и '''нелинейные'''.

Одним из самых известных методов '''линейного''' выделения признаков является [[Метод главных компонент (PCA)| PCA]][на 28.01.19 не создан] (Principal Component Analysis, рус. ''метод главных компонент''). Основной идеей этого метода является поиск такой гиперплоскости, на которую при ортогональной проекции всех признаков максимизируется дисперсия. Данное преобразование может быть произведено с помощью сингулярного разложения матриц и создает проекцию только на линейные многомерные плоскости, поэтому и метод находится в категории линейных.

К '''нелинейным''' методам, например, могут быть отнесены методы отображающие исходное пространство признаков на нелинейные поверхности или топологические многообразия. Одним из таких алгоритмов является [[Стохастическое вложение соседей с t-распределением |t-SNE]][на 28.01.19 не создан] (t-distributed Stochastic Neighbor Embedding, рус. ''стохастическое вложение соседей с t-распределением''). Данный метод состоит из двух шагов: изначально строится распределение вероятностей по всем парам точек набора данных, каждая условная вероятность $p_{j|i}$ которого означает насколько точка $X_j$ близка к точке $X_i$ при гауссовом распределении вокруг $X_i$. Данное распределение как метрику похожести использует евклидово расстояние. Алгоритм старается получить отображение из точек размерности $\mathbb{R}^k$ в меньшую размерность $\mathbb{R}^d$, для этого вводится еще одно распределение, описывающее насколько точки из нового пространства похожи друг на друга, но используя при этом t-распределение Стьюдента с одной степенью свободы. Как метрику похожести двух распределений используется дивергенция Кульбака-Лейблера<ref>[https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence Дивергенция Кульбака-Лейблера]</ref>, и чтобы найти точки новой размерности $d$ запускается градиентный спуск для минимизации этой величины.
===Пример кода scikit-learn===
Пример выделения признаков с помощью PCA в scikit-learn:
# Импорт библиотек
from sklearn.decomposition import PCA
from sklearn.model_selection import train_test_split

X = ... # загрузка X
Y = ... # загрузка Y
# Разделение данных на train и test
Xtrain, Xtest, Ytrain, Ytest = train_test_split(X, Y)

clf = ... # берем какой-то классификатор
# Обучаем PCA для выделения 5 признаков
pca = PCA(n_components=5)
pca.fit(Xtrain)
# Изменяем наши наборы данных под выбранные признаки
Xtrain = pca.transform(Xtrain)
Xtest = pca.transform(Xtest)
# Обучаем классификатор и проверяем точность его работы
clf.fit(Xtrain, Ytrain)
print ("Score: %.6f" % clf.score(Xtest, Ytest))

===Пример на языке Scala===
SBT зависимость:
libraryDependencies '''+=''' "com.github.haifengl" '''%%''' "smile-scala" '''%''' "1.5.2"
Пример уменьшение размерности используя smile.feature.GAFeatureSelection<ref>[https://haifengl.github.io/smile/feature.html#genetic-algorithm-feature-selection Smile, Genetic Algorithm Based Feature Selection]</ref>:
'''import '''smile.classification._
'''import '''smile.data._
'''import '''smile.feature.GAFeatureSelection
'''import '''smile.read
'''import '''smile.validation.Accuracy

// Загрузка данных
'''val '''data = read.arff("data/weka/segment-test.arff", 19)
'''val '''(x, y) = data.unzipInt
'''val '''trainer = '''new '''GradientTreeBoost.Trainer(100)
'''val '''measure = '''new '''Accuracy
// Cоздание генетического алгоритма и его настройка.
'''val '''selector = '''new '''GAFeatureSelection
// Размер популяции - 50, количество поколений - 20 
// Каждая возращаемая BitString содержит фичи и их качество.
'''val '''result = selector.learn(50, 20, trainer, measure, x, y, 5)
result.foreach { bits =>
print(100*bits.fitness)
println(bits.bits.mkString(" "))
}

===Пример на языке Java===
Пример уменьшения размерности датасета с применением <code>weka.attributeSelection.PrincipalComponents</code><ref>[http://weka.sourceforge.net/doc.dev/weka/attributeSelection/PrincipalComponents.html/ Weka, PCA]</ref>

<code>Maven</code> зависимость:
<dependency>
<groupId>nz.ac.waikato.cms.weka</groupId>
<artifactId>weka-stable</artifactId>
<version>3.8.0</version>
</dependency>

'''import''' weka.attributeSelection.PrincipalComponents;
'''import''' weka.core.Instances;
'''import''' weka.filters.Filter;
'''import''' weka.filters.unsupervised.attribute.NumericToNominal;
'''import''' java.io.BufferedReader;
'''import''' java.io.FileReader;

// load dataset
'''var''' data = new Instances(new BufferedReader(new FileReader("data/bank-data.arff")));
'''var''' filter = new NumericToNominal();
filter.setInputFormat(data);
data = Filter.useFilter(data, filter);
// initialize the PCA-based selector
'''var''' pca = new PrincipalComponents();
// dimensionality reduction is achieved through selecting enough eigenvectors to account
// for some percantege of the variance in the original data
pca.setVarianceCovered(0.95);
pca.buildEvaluator(data);
// transform the dataset
data = pca.transformedData(data);

==См. также==
*[[Переобучение]]
*[[Метод опорных векторов (SVM)| SVM]][на 28.01.19 не создан]
*[[Дерево решений и случайный лес| Случайный лес]]
*[[Метод главных компонент (PCA)| PCA]][на 28.01.19 не создан]
*[[Стохастическое вложение соседей с t-распределением |t-SNE]][на 28.01.19 не создан]
==Примечания==
<references/>
==Источники информации==
#[http://research.cs.tamu.edu/prism/lectures/pr/pr_l11.pdf Sequential feature selection] {{---}} курс ML Texas A&M University
#[https://en.wikipedia.org/wiki/Feature_selection Feature selection] {{---}} статья про Feature Selection в Wikipedia
#[https://benthamopen.com/FULLTEXT/TOBIOIJ-11-117 Публикация про feature selection]
#[https://towardsdatascience.com/feature-selection-using-random-forest-26d7b747597f Embedded random forest]

[[Категория: Машинное обучение]]
[[Категория: Уменьшение размерности]]

Уменьшение размерности

2020-01-22T23:55:19Z

Ile86171: PCA v0.0.2

Файл:Pca iris example.png

2020-01-22T23:50:03Z

Ile86171:

Категория:Метод главных компонент

2020-01-22T01:27:29Z

Ile86171: Новая страница: «Категория: Машинное обучение»

[[Категория: Машинное обучение]]

Категория:Уменьшение размерности

2020-01-22T01:27:18Z

Ile86171: Новая страница: «Категория: Машинное обучение»

[[Категория: Машинное обучение]]

Метод главных компонент (PCA)

2020-01-22T01:25:20Z

Ile86171: PCA v0.0.1

'''Метод главных компонент''' (англ. ''Principal Components Analysis, PCA'') — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) <ref>[https://zenodo.org/record/1430636 Pearson, K. (1901). "On Lines and Planes of Closest Fit to Systems of Points in Space"]</ref> в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т.п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к [[Сингулярное разложение|сингулярному разложению]] матрицы данных. Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. ''Karhunen-Loeve'') <ref>[http://fourier.eng.hmc.edu/e161/lectures/klt/node3.html Karhunen-Loeve Transform (KLT)]</ref> или преобразованием Хотеллинга (англ. ''Hotelling transform'').

==Формальная постановка задачи==
[[File:Pearson pca example.jpg|300px|thumb|right|Иллюстрация к работе К. Пирсона (1901): даны точки <tex> P_i</tex> на плоскости, <tex> p_i</tex> — расстояние от <tex> P_i</tex> до прямой <tex> AB</tex>. Ищется прямая <tex> AB</tex>, минимизирующая сумму <tex>\sum_i p_i^2</tex>]]
Пусть имеется $n$ числовых признаков $f_j(x), j = 1, ... , n$. Объекты обучающей выборки будем отождествлять с их признаковыми описаниями: $x_i \equiv (f_1(x_i), ..., f_n(x_i)), i = 1, ..., l$. Рассмотрим матрицу $F$, строки которой соответствуют признаковым описаниям обучающих объектов:
$$F_{l \times n} =
\begin{pmatrix}
f_1(x_1) & ... & f_n(x_1)\\
... & ... & ...\\
f_1(x_l) & ... & f_n(x_l)
\end{pmatrix}
=
\begin{pmatrix}
x_1\\
...\\
x_l
\end{pmatrix}.$$

Обозначим через $z_i = (g_1(x_i), ..., g_m(x_i))$ признаковые описания тех же объектов в новом пространстве $Z = \mathbb{R}^{m}$ меньшей размерности, $m < n$:

$$G_{l \times m} =
\begin{pmatrix}
g_1(x_1) & ... & g_m(x_1)\\
... & ... & ...\\
g_1(x_l) & ... & g_m(x_l)
\end{pmatrix}
=
\begin{pmatrix}
z_1\\
...\\
z_l
\end{pmatrix}.$$

Потребуем, чтобы исходные признаковые описания можно было восстановить по новым описаниям с помощью некоторого линейного преобразования, определяемого матрицей $U = (u_{js})_{n \times m}$:

$$\hat{f}_j(x) = \sum_{s = 1}^{m} g_s(x)u_{js}, \; j = 1, ..., n, \; x \in X,$$

или в векторной записи: $\hat{x} = z U^T$. Восстановленное описание $\hat{x}$ не обязано в точности совпадать с исходным описанием $x$, но их отличие на объектах обучающей выборки должно быть как можно меньше при выбранной размерности $m$. Будем искать одновременно и матрицу новых признаковых описаний $G$, и матрицу линейного преобразования $U$, при которых суммарная невязка восстановленных описаний минимальна:

$$\Delta^2(G, U) = \sum_{i = 1}^{l} \| \hat{x}_i - x_i \|^2 = \sum_{i = 1}^{l} \| z_i U^T - x_i \|^2 = \| GU^T - F \|^2 \to \mathop{min}_{G, U},$$

где все нормы евклидовы.

Будем предполагать, что матрицы $G$ и $U$ невырождены: $rank \, G = rank \, U = m$. Иначе существовало бы представление $\bar{G} \bar{U}^T = G U^T$ с числом столбцов в матрице $\bar{G}$, меньшим $m$. Поэтому интересны лишь случаи, когда $m \leq rank \, F$.

==Решение==

Исчерпывающее решение сформулированной задачи даёт следующая теорема.

{{Теорема
|statement = Если $m \leq rank \, F$, то минимум $\Delta^2(G, U)$ достигается, когда столбцы матрицы $U$ есть собственные векторы $F^T F$, соответствующие $m$ максимальным собственным значениям. При этом $G = F U$, матрицы $U$ и $G$ ортогональны.

|proof = Запишем необходимые условия минимума:

<tex>
\frac{\partial \Delta^2}{\partial G} = (G U^T - F) U = 0;\\ \frac{\partial \Delta^2}{\partial U} = G^T (G U^T - F) = 0.
</tex>

Поскольку искомые матрицы $G$ и $U$ невырождены, отсюда следует:

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Функционал $\Delta^2(G, U)$ зависит только от произведения матриц $G U^T$, поэтому решение задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ определено с точностью до произвольного невырожденного преобразования $R: G U^T = (G R) (R^{-1} U^T)$. Распорядимся свободой выбора $R$ так, чтобы матрицы $U^T U$ и $G^T G$ оказались диагональными. Покажем, что это всегда возможно.

Пусть $\tilde{G} \tilde{U}^T$ - произвольное решение задачи.

Матрица $\tilde{U}^T \tilde{U}$ симметричная, невырожденная, положительно определенная, поэтому существует невырожденная матрица $S_{m \times m}$ такая, что $S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T = I_m$.

Матрица $S^T \tilde{G}^T \tilde{G} S$ симметричная и невырожденная, поэтому существует ортогональная матрица $T_{m \times m}$ такая, что $T^T (S^T \tilde{G}^T \tilde{G} S) T = diag(\lambda_1, ..., \lambda_m) \equiv \Lambda$ - диагональная матрица. По определению ортогональности $T^T T = I_m$.

Преобразование $R = S T$ невырождено. Положим $G = \tilde{G} R$, $U^T = R^{-1} \tilde{U}^T$. Тогда

<tex>
G^T G = T^T (S^T \tilde{G}^T \tilde{G} S) T = \Lambda;\\ U^T U = T^{-1} (S^{-1} \tilde{U}^T \tilde{U} (S^{-1})^T) (T^{-1})^T = (T^T T)^{-1} = I_m.
</tex>

В силу $G U^T = \tilde{G} \tilde{U}^T$ матрицы $G$ и $U$ являются решением задачи $\Delta^2(G, U) \to \mathop{min}_{G, U}$ и удовлетворяют необходимому условию минимума. Подставим матрицы $G$ и $U$ в

<tex>
G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}.
</tex>

Благодаря диагональности $G^T G$ и $U^T U$ соотношения существенно упростятся:

<tex>
G = F U;\\ U \Lambda = F^T G.
</tex>

Подставим первое соотношение во второе, получим $U \Lambda = F^T F U$. Это означает, что столбцы матрицы $U$ обязаны быть собственными векторами матрицы $F^T F$, а диагональные элементы $\lambda_1, ..., \lambda_m$ - соответствующими им собственными значениями.

Аналогично, подставив второе соотношение в первое, получим $G \Lambda = F F^T G$, то есть столбцы матрицы $G$ являются собственными векторами $F F^T$, соответствующими тем же самым собственным значениям.

Подставляя $G$ и $U$ в функционал $\Delta^2(G, U)$, находим:

<tex>
\Delta^2(G, U) = \| F - G U^T \|^2 = tr \, (F^T - U G^t)(F - G U^T) = tr \, F^T (F - G U^T) = tr \, F^T F - tr \, F^T G U^T = \| F \|^2 - tr \, U \Lambda U^T = \| F \|^2 - tr \, \Lambda = \sum_{j = 1}^{n} \lambda_j - \sum_{j = 1}^{m} \lambda_j - \sum_{j = m + 1}^{n} \lambda_j,
</tex>

где $\lambda_1 , ..., \lambda_n$ - все собственные значения матрицы $F^T F$. Минимум $\Delta^2$ достигается, когда $\lambda_1, ..., \lambda_m$ - наибольшие $m$ из $n$ собственных значений.

Собственные векторы $u_1, ..., u_m$, отвечающие максимальным собственным значениям, называют ''главными компонентами''.
}}

==Свойства==

===Связь с сингулярным разложением===

Если $m = n$, то $\Delta^2(G, U) = 0$. В этом случае представление $F = G U^T$ является точным и совпадает с сингулярным разложением: $F = G U^T = V D U^T$, если положить $G = V D$ и $\Lambda = D^2$. При этом матрица $V$ ортогональна: $V^T V = I_m$.

Если $m < n$, то то представление $F \approx G U^T$ является приближённым. Сингулярное разложение матрицы $G U^T$ получается из сингулярного разложения матрицы $F$ путём отбрасывания (обнуления) $n - m$ минимальных собственных значений.

===Преобразование Карунена–Лоэва===

Диагональность матрицы $G^T G = \Lambda$ означает, что новые признаки $g_1, ..., g_m$ не коррелируют на обучающих объектах. Ортогональное преобразование $U$ называют ''декоррелирующим'' или преобразованием ''Карунена–
Лоэва''. Если $m = n$, то о прямое и обратное преобразование вычисляются с помощью одной и той же матрицы $U: F = G U^T$ и $G = F U$.

===Эффективная размерность===

Главные компоненты содержат основную информацию о матрице $F$. Число главных компонент $m$ называют также ''эффективной размерностью'' задачи. На практике её определяют следующим образом. Все собственные значения матрицы $F^T F$ упорядочиваются по убыванию: $\lambda_1 \geq ... \geq \lambda_n \geq 0$. Задаётся пороговое значение $\epsilon \in [0, 1]$, достаточно близкое к нулю, и определяется наименьшее целое $m$, при котором относительная погрешность приближения матрицы $F$ не превышает $\epsilon$:

$$E(m) = \frac{\| G U^T - F \|^2}{\| F \|^2} = \frac{\lambda_{m + 1} + ... + \lambda_n}{\lambda_1 + ... + \lambda_n} \leq \epsilon .$$

Величина $E(m)$ показывает, какая доля информации теряется при замене исходных признаковых описаний длины $n$ на более короткие описания длины $m$. Метод главных компонент особенно эффективен в тех случаях, когда $E(m)$ оказывается малым уже при малых значениях $m$. Если задать число $\epsilon$ из априорных соображений не представляется возможным, прибегают к ''критерию «крутого обрыва»''. На графике $E(m)$ отмечается то значение $m$, при котором происходит резкий скачок: $E(m - 1) \gg E(m)$, при условии, что $E(m)$ уже достаточно мало.

==Визуализация многомерных данных==

Метод главных компонент часто используется для представления многомерной выборки данных на двумерном графике. Для этого полагают $m = 2$ и полученные пары значений $(g_1(x_i), g_2(x_i)), i = 1, ..., l$, наносят как точки на график. Проекция на главные компоненты является наименее искаженной из всех линейных проекций многомерной выборки на какую-либо пару осей. Как правило, в осях главных компонент удаётся увидеть наиболее существенные особенности исходных данных, даже несмотря на неизбежные искажения. В частности, можно судить о наличии кластерных структур и выбросов. Две оси $g_1$ и $g_2$ отражают «две основные тенденции» в данных. Иногда их удаётся интерпретировать, если внимательно изучить, какие точки на графике являются «самыми левыми», «самыми правыми», «самыми верхними» и «самыми нижними». Этот вид анализа не позволяет делать точные количественные выводы и обычно используется
с целью понимания данных. Аналогичную роль играют многомерное шкалирование <ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%88%D0%BA%D0%B0%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Многомерное шкалирование]</ref> и карты Кохонена <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%BC%D0%BE%D0%BE%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D1%83%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0 Самоорганизующаяся карта Кохонена]</ref>.

==Пример кода scikit-learn==
Пример применения PCA к датасету Iris для уменьшения размерности:
# Импорт библиотек
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from sklearn import decomposition
from sklearn import datasets

# Загрузка данных
centers = [[1, 1], [-1, -1], [1, -1]]
iris = datasets.load_iris()
X = iris.data
y = iris.target

# Инициализация графика
fig = plt.figure(1, figsize=(4, 3))
plt.clf()
ax = Axes3D(fig, rect=[0, 0, .95, 1], elev=48, azim=134)
plt.cla()

# Преобразование данных датасета Iris, уменьшающее размерность до 3
pca = decomposition.PCA(n_components=3)
pca.fit(X)
X = pca.transform(X)

[[File:Sklearn pca plot.png|300px|thumb|right|Применения PCA к датасету Iris]]
# Отображение меток и преобразованных данных на графике
for name, label in [('Setosa', 0), ('Versicolour', 1), ('Virginica', 2)]:
ax.text3D(X[y == label, 0].mean(),
X[y == label, 1].mean() + 1.5,
X[y == label, 2].mean(), name,
horizontalalignment='center',
bbox=dict(alpha=.5, edgecolor='w', facecolor='w'))
y = np.choose(y, [1, 2, 0]).astype(np.float)
ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=y, cmap=plt.cm.nipy_spectral,
edgecolor='k')
ax.w_xaxis.set_ticklabels([])
ax.w_yaxis.set_ticklabels([])
ax.w_zaxis.set_ticklabels([])
plt.show()

==См. также==
*[[Уменьшение размерности]]
*[[Сингулярное разложение]]
==Примечания==
<references/>
==Источники информации==
#[http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 machinelearning.ru — Метод главных компонент]
#[https://www.youtube.com/watch?v=wcJ0nSUr7ws Лекция "Регрессионный анализ и метод главных компонентов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
#[http://research.cs.tamu.edu/prism/lectures/pr/pr_l9.pdf PCA] {{---}} курс ML Texas A&M University
#[https://en.wikipedia.org/wiki/Principal_component_analysis Principal Component Analysis] {{---}} статья про Principal Component Analysis в Wikipedia
#[https://towardsdatascience.com/understanding-pca-fae3e243731d Understanding PCA]

[[Категория: Машинное обучение]]
[[Категория: Уменьшение размерности]]
[[Категория: Метод главных компонент]]

Файл:Sklearn pca plot.png

2020-01-22T01:20:07Z

Ile86171:

Файл:Pearson pca example.jpg

2020-01-22T01:17:20Z

Ile86171: