Метод главных компонент: различия между версиями

м
многоточие
м (Удаление шаблонов: {{нп5}}×1)
м (многоточие)
: <math> \operatorname{dist}^2(x_i, L_k) = \sum_{l=1}^n \left(x_{il} - a_{0l}- \sum_{j=1}^k a_{jl} \sum_{q=1}^n a_{jq}(x_{iq} - a_{0q}) \right)^2 </math>.
 
Решение задачи аппроксимации для <math> k = 0,1, \dots , n-1 </math> даётся набором вложенных линейных многообразий <math>L_0 \subset L_1 \subset \dots L_{n-1} </math>, <math>L_k = \{ a_0 +\beta_1 a_1 +...\ldots+ \beta_k a_k | \beta_i \in \mathbb{R} \} </math>. Эти линейные многообразия определяются ортонормированным набором векторов <math>\left\{a_1,..., a_{n-1} \right\} </math> (векторами главных компонент) и вектором <math> a_0 </math>.
Вектор <math> a_0 </math> ищется как решение задачи минимизации для <math> L_0 </math>:
 
[[Ковариационная матрица]] многомерной случайной величины <math> X</math>, это
: <math>\Sigma = [\sigma_{ij}],\ \sigma_{ij} = \operatorname{cov}(X_i,X_j)=\operatorname{E}[(X_i-\operatorname{E}[X_i])(X_j-\operatorname{E}[X_j])].</math>
Векторы главных компонент для задач о наилучшей аппроксимации и о поиске ортогональных проекций с наибольшим рассеянием — это ортонормированный набор <math> \left\{a_1,..., a_n \right\}</math> собственных векторов эмпирической ковариационной матрицы <math>C</math>, расположенных в порядке убывания собственных значений <math>\lambda: \lambda_1 \ge \lambda_2 \ge ...\ldots \ge \lambda_n \ge 0. </math> Эти векторы служат оценкой для собственных векторов ковариационной матрицы <math>\operatorname{cov}(X_i,X_j) </math>. В базисе из собственных векторов ковариационной матрицы она, естественно, диагональна, и в этом базисе коэффициент ковариации между различными координатами равен нулю.
 
Если спектр ковариационной матрицы вырожден, то выбирают произвольный ортонормированный базис собственных векторов. Он существует всегда, а собственные числа ковариационной матрицы всегда вещественны и неотрицательны.
B качестве начального приближения вектора <math>a</math> берётся случайный вектор единичной длины, вычисляем вектор <math>b</math>, далее для этого вектора <math>b</math> вычисляем вектор <math>a</math> и т. д. Каждый шаг уменьшает значение <math>F(b, a) </math>. В качестве критерия остановки используется малость относительного уменьшения значения минимизируемого функционала <math>F(b, a) </math> за шаг итерации (<math>\Delta F / F </math>) или малость самого значения <math>F</math>.
 
В результате для матрицы <math>X=(x_{ij})</math> получается наилучшее приближение матрицей <math>P_1</math> вида <math>b^1 \otimes a^1 = (b_i^1 a_j^1)</math> (здесь верхним индексом обозначен номер приближения). Далее, из матрицы <math>X</math> вычитается полученная матрицу <math>P_1</math>, и для полученной матрицы уклонений <math>X_1=X-P_1</math> вновь ищется наилучшее приближение <math>P_2</math> этого же вида и т. д., пока, например, норма <math>X_k</math> не станет достаточно малой. В результате получили итерационную процедуру разложения матрицы <math>X</math> в виде суммы матриц ранга 1, то есть <math>X=P_1+P_2+...\ldots +P_q \; (P_l = b^l \otimes a^l) </math> . Полагаем <math> \sigma_l = \|a^l\| \|b^l\|</math> и нормируем векторы <math> a^l \, , \, b^l</math>: <math>a^l:= a^l/ \| a^l\|; \, \, b^l:= b^l/ \| b^l\|.</math> В результате получена аппроксимация сингулярных чисел <math> \sigma_l </math> и сингулярных векторов (правых — <math> a^l</math> и левых — <math>b^l</math>).
 
К достоинствам этого алгоритма относится его исключительная простота и возможность почти без изменений перенести его на данные с пробелами<ref>''Россиев А. А.'',: [http://pca.narod.ru/DisRos.htm Итерационное моделирование неполных данных с помощью многообразий малой размерности], Изд-во СО РАН, 2005.</ref>, а также взвешенные данные.
Пусть данные центрированы, <math>\overline{ X}=0</math>. При замене векторов данных <math> x_i</math> на их проекцию на первые <math> k</math> главных компонент <math>x_i \mapsto \sum_{j=1}^k a_j (a_j, x_i) </math> вносится средний квадрат ошибки в расчете на один вектор данных:
: <math>\frac{1}{m} \sum_{i=1}^m \left\Vert x_i - \sum_{j=1}^k a_j (a_j, x_i) \right \Vert ^2=\sum_{l=k+1}^n \lambda_l, </math>
где <math>\lambda_1 \ge \lambda_2 \ge ...\ldots \ge \lambda_n \ge 0</math> собственные значения эмпирической ковариационной матрицы <math>C</math>, расположенные в порядке убывания, с учётом кратности.
 
Эта величина называется ''остаточной дисперсией''. Величина
\frac{1}{m} \sum_{i=1}^m \sum_{j=1}^k (a_j, x_i)^2=\sum_{l=1}^k \lambda_l </math>
называется ''объяснённой дисперсией''. Их сумма равна выборочной дисперсии. Соответствующий квадрат относительной ошибки — это отношение остаточной дисперсии к выборочной дисперсии (то есть ''доля необъяснённой дисперсии''):
: <math>\delta^2_k=\frac{\lambda_{k+1}+\lambda_{k+2}+...\ldots+\lambda_{n}}{\lambda_{1}+\lambda_{2}+...\ldots+\lambda_{n}}.</math>
 
По относительной ошибке <math> \delta_k</math> оценивается применимость метода главных компонент с проецированием на первые <math> k</math> компонент.
 
=== Нормировка после приведения к главным компонентам ===
''После'' проецирования на первые <math> k</math> главных компонент с <math>\lambda_1 \ge \lambda_2 \ge ...\ldots \ge \lambda_k > 0</math> удобно произвести нормировку на единичную (выборочную) дисперсию по осям. Дисперсия вдоль <math> i</math>й главной компоненты равна
<math>\lambda_i > 0 \; (1 \le i \le k</math>), поэтому для нормировки надо разделить соответствующую координату на <math> \sqrt{ \lambda_i}</math>. Это преобразование не является ортогональным и не сохраняет скалярного произведения. Ковариационная матрица проекции данных после нормировки становится единичной, проекции на любые два ортогональных направления становятся независимыми величинами, а любой ортонормированный базис становится базисом главных компонент (напомним, что нормировка меняет отношение ортогональности векторов). Отображение из пространства исходных данных на первые <math> k</math> главных компонент вместе с нормировкой задается матрицей