286
правок
Изменения
Пример кода на R
[[File:800px-Pca 3d to 2d example v2.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'').
==Формальная постановка задачи==
$$\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)$ восстановленных описаний минимальна:
$$\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},$$
{{Теорема
|statement = Если $<tex>m \leq rank \, F$</tex>, то минимум $<tex>\Delta^2(G, U)$ </tex> достигается, когда столбцы матрицы $<tex>U$ </tex> есть собственные векторы $<tex>F^T F$</tex>, соответствующие $<tex>m$ </tex> максимальным собственным значениям. При этом $<tex>G = F U$</tex>, матрицы $<tex>U$ </tex> и $<tex>G$ </tex> ортогональны.
|proof = Запишем необходимые условия минимума:
<tex>
\begin{cases}\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.\end{cases}
</tex>
<tex>
\begin{cases}G = F U (U^T U)^{-1};\\ U = F^T G (G^T G)^{-1}. \end{cases}
</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>
\begin{cases}G = F U;\\ U \Lambda = F^T G.\end{cases}
</tex>
Подставляя $G$ и $U$ в функционал $\Delta^2(G, U)$, находим:
<tex>\Delta^2(G, U) </tex> = <tex>\| F - G U^T \|^2 </tex> = <tex>tr \, (F^T - U G^t)(F - G U^T) </tex> = <tex>tr \, F^T (F - G U^T) </tex> = <tex>tr \, F^T F - tr \, F^T G U^T </tex> = <tex>\| F \|^2 - tr \, U \Lambda U^T </tex> = <tex>\| F \|^2 - tr \, \Lambda </tex> = <tex>\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$.
===Эффективная размерность===
==Визуализация многомерных данных==
[[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> и карты Кохонена <refname=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 для уменьшения размерности:
<span style="color:#3D9970># Импорт библиотек</span>
import numpy as np
import matplotlib.pyplot as plt
from sklearn import decomposition
from sklearn import datasets
y = iris.target
pca = decomposition.PCA(n_components=3)
pca.fit(X)
X = pca.transform(X)
y = np.choose(y, [1, 2, 0]).astype(np.float)
plt.show()
=== Пример на языке R ===
{{Main|Примеры кода на R}}
<font color="gray"># importing library and its' dependencies</font>
library(h2o)
h2o.init()
path <- system.file(<font color="green">"extdata"</font>, <font color="green">"data.csv"</font>, <font color="#660099">package</font> = <font color="green">"h2o"</font>)
data <- h2o.uploadFile(<font color="#660099">path</font> = data)
<font color="gray"># evaluating</font>
h2o.prcomp(<font color="#660099">training_frame</font> = data, <font color="#660099">k</font> = <font color="blue">8</font>, <font color="#660099">transform</font> = <font color="green">"STANDARDIZE"</font>)
==См. также==
*[[Уменьшение размерности]]
*[[Сингулярное разложение]]
==Примечания==
<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
