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

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Внешние ссылки)
(Согласно Обсуждению залил статью из Викиредии как драфт для более подробной статьи)
Строка 1: Строка 1:
-
'''Метод главных компонент''' — способ снижения размерности пространства данных.
+
'''Метод Главных Компонент''' ({{lang-en|Principal Components Analysis, PCA}}) — один из основных способов уменьшить [[размерность]] данных, потеряв наименьшее количество [[информация|информации]]. Изобретен К. Пирсоном ({{lang-en|[http://en.wikipedia.org/wiki/Karl_Pearson Karl Pearson]}}) в [[1901]] г. Применяется во многих областях, таких как [[распознавание образов]], [[компьютерное зрение]], [[сжатие данных]] и т. п. Вычисление главных компонент сводится к вычислению [[Собственные векторы, значения и пространства|собственных векторов]] и [[Собственные векторы, значения и пространства|собственных значений]] [[Ковариационная матрица| ковариационной матрицы]] исходных данных. Иногда метод главных компонент называют ''преобразованием Кархунена-Лоэва'' ({{lang-en|Karhunen-Loeve}})<ref>В русскоязычной научной литературе распространено также написание ''преобразование Карунена-Лоэва'', соответствующее английскому прочтению финской фамилии</ref> или преобразованием Хотеллинга ({{lang-en|Hotelling transform}}). Другие способы уменьшения размерности данных — это [[метод независимых компонент]], многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, [[Поиск наилучшей проекции|поиск наилучшей проекции]] ({{lang-en|Projection Pursuit}}), [[Искусственная нейронная сеть|нейросетевые]] методы «[[Нейросетевое сжатие данных|узкого горла]]», [[Самоорганизующаяся карта Кохонена|самоорганизующиеся карты Кохонена]] и др.
-
Он заключается в нахождении линейного ортогонального преобразования исходной матрицы данных в пространство меньшей размерности.
+
-
При этом выбираются такая ортогональная система координат, которая обеспечивает наименьшую потерю информации в исходных данных.
+
-
Последнее подразуменает минимальную среднеквадратичную ошибку при проекции данных в пространство заданной размерности.
+
-
== Определение метода главных компонент ==
+
== Формальная постановка задачи ==
-
[[Изображение:Principal_Component_Analysis.gif|right|frame|Векторы-строки матрицы исходных данных&nbsp;<tex>A</tex> показаны звездочками. Красным крестом отмечен первый вектор-столбец матрицы
+
-
вращения&nbsp;<tex>V</tex>. Точками отмечены проекции векторов на новую систему координат. Сумма квадратов длин синих линий есть ошибка&nbsp;&#151;
+
-
количество информации, утраченной при снижении размерности пространства.]]
+
-
Одной из задач аппроксимации является задача приближения множества векторов-строк&nbsp;<tex>\mathbf{a}_i</tex> матрицы&nbsp;<tex>A</tex> их проекциями на некоторую новую ортогональную систему координат.
+
Задача анализа главных компонент, имеет, как минимум, три базовых версии:
-
Эта система отыскивается на множестве преобразований вращений&nbsp;<tex>V</tex> начальной системы координат.
+
* аппроксимировать данные [[Линейное многообразие|линейными многообразиями]] меньшей размерности;
-
При этом множество аппроксимируемых векторов&nbsp;<tex>\mathbf{a}_i</tex>, <tex>i=1,...,m</tex>, отображается в новое множество векторов <tex>\mathbf{z}_i</tex>, где <tex>\mathbf{a}_i,\mathbf{z}_i\in\mathbb{R}^n</tex>.
+
* найти подпространства меньшей размерности, в ортогональной проекции на которые разброс данных максимален;
-
Оператором отображения
+
* для данной многомерной случайной величины построить такое ортогональное преобразования координат, что в результате корреляции между отдельными координатами обратятся в ноль.
-
<center><tex>Z=A^TV</tex></center>
+
-
является ортонормальная матрица&nbsp;<tex>V</tex>, то есть <tex>VV^T=I</tex>&nbsp;&#151; единичная матрица.
+
-
Столбцы&nbsp;<tex>Z</tex> называются главными компонентами матрицы&nbsp;<tex>A</tex>.
+
-
Матрица&nbsp;<tex>V</tex> строится таким образом, что среднеквадратическая
+
-
разность между векторами&nbsp;<tex>\mathbf{a}_i</tex> и проекцией этих векторов на
+
-
ортогональную систему координат, заданных&nbsp;<tex>\mathbf{z}_i</tex> минимальна.
+
-
Наиболее удобным способом получения матрицы&nbsp;<tex>V</tex> является [[сингулярное разложение]] матрицы&nbsp;<tex>A</tex>:
+
-
<center><tex>A=U\Lambda V^T.</tex></center>
+
-
Метод главных компонент позволяет с помощью&nbsp;<tex>k</tex> первых главных компонент можно восстановить исходную матрицу с минимальной ошибкой.
+
Первые две версии оперируют конечными множествами данных. Они эквивалентны и не используют никакой гипотезы о статистическом порождении данных. Третья версия оперирует случайными величинами. Конечные множества появляются здесь как выборки из данного распределения, а решение двух первых задач — как приближение к «истинному» преобразованию Кархунена-Лоэва. При этом возникает дополнительный и не вполне тривиальный вопрос о точности этого приближения.
-
Критерий минимального значения суммы квадратов расстояния от векторов-столбцов матрицы данных до их проекций на
+
-
первую главную компоненту называется критерием наибольшей информативности C.Р.&nbsp;Рао.
+
-
Кроме того, матрица&nbsp;<tex>V</tex> выполняет декоррелирующее преобразование, называемое также преобразованием Карунена-Лоэва.
+
-
В&nbsp;результате этого преобразования исчезает возможная корреляция между векторами-столбцами исходной матрицы&nbsp;<tex>A</tex>.
+
-
Рао было показано, что строки матрицы&nbsp;<tex>V</tex> есть собственные векторы ковариационной матрицы <center><tex>\Sigma=A^TA,</tex></center>
+
-
где матрица&nbsp;<tex>A</tex> <i>центрирована</i>&nbsp;&#151; из каждого ее столбца вычтено среднее значение по этому столбцу.
+
-
== Понятие наибольшей информативности ==
+
=== Аппроксимация данных линейными многообразиями ===
-
Рассмотрим <tex>n</tex>-мерную случайную величину&nbsp;<tex>A</tex> с ковариационной
+
[[Изображение:PearsonFig.jpg|thumb|Иллюстрация к знаменитой работе К. Пирсона (1901): даны точки <math> P_i</math> на плоскости, <math> p_i</math> — расстояние от <math> P_i</math> до прямой <math> AB</math>. Ищется прямая <math> AB</math>, минимизирующая сумму <math>\sum_i p_i^2</math> ]]
-
матрицей&nbsp;<tex>\Sigma=A^TA</tex>. Обозначим&nbsp;<tex>\mu_1,\dots,\mu_n</tex>&nbsp;&#151;
+
-
соответствующие собственные числа и <tex>\mathbf{v}_1,\dots,\mathbf{v}_n</tex>&nbsp;&#151; собственные
+
-
векторы матрицы&nbsp;<tex>\Sigma</tex>.
+
-
Заметим, что собственные числа и элементы собственных векторов
+
-
матрицы&nbsp;<tex>\Sigma</tex> всегда действительны. Тогда по теореме о собственных числах
+
-
<center><tex>\Sigma=\sum_{i=1}^n\mu_i\mathbf{v}_i\mathbf{v}_i^T,</tex>&nbsp;&nbsp;<tex>I=\sum_{i=1}^n\mathbf{v}_i\mathbf{v}_i^T,</tex></center>
+
-
<center><tex>\mathbf{v}_i^T{\Sigma}\mathbf{v}_i=\mu_i,</tex>&nbsp;&nbsp;<tex>\mathbf{v}_i^T{\Sigma}\mathbf{v}_j=0,</tex>&nbsp;&nbsp; <tex>i\neq{j}.</tex> (*)</center>
+
Метод главных компонент начинался с задачи наилучшей аппроксимации конечного множества точек прямыми и плоскостями (К. Пирсон, 1901). Дано конечное множество [[Вектор (алгебра)|векторов]] <math>x_1,x_2,...x_m \in\mathbb{R}^n </math>. Для каждого <math> k = 0,1,..., n-1 </math> среди всех <math>k</math>-мерных [[Линейное многообразие|линейных многообразий]] в <math>\mathbb{R}^n </math> найти такое <math>L_k \subset \mathbb{R}^n </math>, что сумма квадратов уклонений <math> x_i</math> от <math> L_k</math> минимальна:
-
Случайная величина <tex>\mathbf{z}_i=\mathbf{v}_i^TA</tex> называется&nbsp;<tex>i</tex>-й главной
+
-
компонентой случайной величины&nbsp;<tex>A</tex>. Матрица вращения&nbsp;<tex>V</tex>
+
-
составлена из векторов-столбцов&nbsp;<tex>\mathbf{v}_1,\ldots,\mathbf{v}_n</tex>. Матрица
+
-
главных компонент&nbsp;<tex>Z=A^TV</tex> имеет следующие свойства.
+
-
== Смотри также ==
+
: <math>\sum_{i=1}^m \operatorname{dist}^2(x_i, L_k) \to \min</math>,
-
* [[Сингулярное разложение]]
+
 
-
* [[Интегральный индикатор]]
+
где <math>\operatorname{dist}(x_i, L_k) </math> — евклидово расстояние от точки до линейного многообразия. Всякое <math>k </math>-мерное линейное многообразие в <math>\mathbb{R}^n </math> может быть задано как множество линейных комбинаций <math>L_k = \{ a_0 +\beta_1 a_1 +...+ \beta_k a_k | \beta_i \in \mathbb{R} \} </math>, где параметры <math> \beta_i </math> пробегают вещественную прямую <math>\mathbb{R}</math>, <math>a_0 \in \mathbb{R}^n</math> а <math>\left\{a_1,..., a_k \right\} \subset \mathbb{R}^n</math> — ортонормированный набор векторов
-
* [[Обучение без учителя]]
+
: <math>\operatorname{dist}^2(x_i, L_k) = \Vert x_i - a_0 - \sum_{j=1}^k a_j (a_j, x_i - a_0) \Vert ^2</math>,
 +
где <math>\Vert \cdot \Vert </math> евклидова норма, <math> \left(a_j, x_i\right) </math> — евклидово скалярное произведение, или в координатной форме:
 +
: <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,..., n-1 </math> даётся набором вложенных линейных многообразий <math>L_0 \subset L_1 \subset ... L_{n-1} </math>, <math>L_k = \{ a_0 +\beta_1 a_1 +...+ \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> a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left(\sum_{i=1}^m \operatorname{dist}^2(x_i, L_0)\right), </math>
 +
 
 +
то есть
 +
 
 +
: <math>a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left (\sum_{i=1}^m \Vert x_i - a_0\Vert ^2\right) </math>.
 +
 
 +
Это — [[выборочное среднее]]: <math>a_0 = \frac{1}{m} \sum_{i=1}^m x_i = \overline{X}.</math>
 +
[[Фреше, Морис Рене|Фреше]] в [[1948 год]]у обратил внимание, что вариационное определение среднего (как точки, минимизирующей сумму квадратов расстояний до точек данных) очень удобно для построения статистики в произвольном [[Метрическое пространство|метрическом пространстве]], и построил обобщение классической статистики для общих пространств (обобщённый [[метод наименьших квадратов]]).
 +
 
 +
Векторы главных компонент могут быть найдены как решения однотипных задач [[Оптимизация (математика)|оптимизации]]:
 +
: 1) централизуем данные (вычитаем среднее): <math>x_i := x_i - \overline{X_i}</math>. Теперь <math>\sum_{i=1}^m x_i =0 </math>;
 +
: 2) находим первую главную компоненту как решение задачи;
 +
:: <math>a_1 = \underset{\Vert a_1 \Vert =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \Vert x_i - a_1 (a_1,x_i)\Vert ^2\right)</math>.
 +
:: Если решение не единственно, то выбираем одно из них.
 +
: 3) Вычитаем из данных проекцию на первую главную компоненту:
 +
:: <math>x_i := x_i - a_1 \left(a_1,x_i\right) </math>;
 +
: 4) находим вторую главную компоненту как решение задачи
 +
:: <math>a_2 = \underset{\Vert a_2 \Vert =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \Vert x_i - a_2 (a_2,x_i)\Vert ^2\right) </math>.
 +
:: Если решение не единственно, то выбираем одно из них.
 +
:: …
 +
: 2k-1) Вычитаем проекцию на <math>(k-1)</math>-ю главную компоненту (напомним, что проекции на предшествующие <math>(k-2)</math> главные компоненты уже вычтены):
 +
:: <math>x_i := x_i - a_{k-1} \left(a_{k-1},x_i\right) </math>;
 +
: 2k) находим k-ю главную компоненту как решение задачи:
 +
:: <math>a_k = \underset{\Vert a_k \Vert =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \Vert x_i - a_k (a_k,x_i)\Vert ^2\right) </math>.
 +
:: Если решение не единственно, то выбираем одно из них.
 +
:: …
 +
На каждом подготовительном шаге <math> (2k-1)</math> вычитаем проекцию на предшествующую главную компоненту. Найденные векторы <math>\left\{a_1,..., a_{ n -1} \right\}</math> ортонормированы просто в результате решения описанной задачи оптимизации, однако чтобы не дать ошибкам вычисления нарушить взаимную ортогональность векторов главных компонент, можно включать <math>a_k \bot \{a_1,..., a_{k -1} \} </math> в условия задачи оптимизации.
 +
 
 +
Неединственность в определении <math> a_k</math> помимо тривиального произвола в выборе знака (<math> a_k</math> и <math> -a_k</math> решают ту же задачу) может быть более существенной и происходить, например, из условий симметрии данных.
 +
 
 +
=== Поиск ортогональных проекций с наибольшим рассеянием ===
 +
 
 +
[[Изображение:FirstPrincipalComponent.jpg|thumb|Первая главная компонента максимизирует выборочную дисперсию проекции данных]]
 +
 
 +
 
 +
Пусть нам дан центрированный набор векторов данных <math>x_i\in\mathbb{R}^n \; (i=1,...,m)</math> ([[среднее арифметическое]] значение <math> x_i </math> равно нулю). Задача — найти такое [[ортогональное преобразование]] в новую [[Прямоугольная система координат|систему координат]], для которого были бы верны следующие условия:
 +
* [[Выборочная дисперсия]] данных вдоль первой координаты максимальна (эту координату называют первой ''главной компонентой'');
 +
* Выборочная дисперсия данных вдоль второй координаты максимальна при условии ортогональности первой координате (вторая главная компонента);
 +
* …
 +
* Выборочная дисперсия данных вдоль значений <math>k</math>-ой координаты максимальна при условии ортогональности первым <math>k-1</math> координатам;
 +
* …
 +
 
 +
[[Выборочная дисперсия]] данных вдоль направления, заданного нормированным вектором <math> a_k</math>, это
 +
: <math>S^2_m \left[ (X, a_k) \right ] = \frac{1}{m} \sum\limits_{i=1}^m \left(\sum\limits_{j=1}^n x_{ij}a_{kj} \right)^2 </math>
 +
(поскольку данные центрированы, выборочная дисперсия здесь совпадает со средним квадратом уклонения от нуля).
 +
 
 +
Формально, если <math>A=\left \{a_1,...,a_n \right \}^T\in\mathbb{R}^{n \times n}</math>, <math>a_k\in\mathbb{R}^n</math> — искомое преобразование, то для векторов <math>a_k</math> должны выполняться следующие условия:
 +
* <math>a_1 = \underset{\Vert a_1 \Vert =1}{\operatorname{argmax}}\,S^2_m \left [(X, a_1) \right ];</math>
 +
: Если решение не единственно, то выбираем одно из них.
 +
* Вычитаем из данных проекцию на первую главную компоненту:
 +
: <math>x_i := x_i - a_1 \left(a_1,x_i\right) </math>; в результате <math>x_i \bot a_1</math>;
 +
* находим вторую главную компоненту как решение задачи
 +
: <math>a_2 = \underset{\Vert a_2 \Vert =1}{\operatorname{argmax}}\,S^2_m \left [ (X, a_2) \right ];</math>
 +
: Если решение не единственно, то выбираем одно из них.
 +
* …
 +
* Вычитаем проекцию на <math>(k-1)</math>-ю главную компоненту (напомним, что проекции на предшествующие <math>k-2</math> главные компоненты уже вычтены):
 +
: <math>x_i := x_i - a_{k-1} \left(a_{k-1},x_i\right) </math>; в результате <math>x_i \bot a_l, (l = 1, \dots, k-1)</math>;
 +
* находим <math>k</math>-ю главную компоненту как решение задачи
 +
: <math>a_n = \underset{\Vert a_k\Vert = 1}{\operatorname{argmax}}\,S^2_m \left [ (X, a_k) \right ];</math>
 +
: Если решение не единственно, то выбираем одно из них.
 +
* …
 +
 
 +
Фактически, как и для задачи аппроксимации, на каждом шаге решается задача о первой главной компоненте для данных, из которых вычтены проекции на все ранее найденные главные компоненты. При большом числе итерации (большая размерность, много главных компонент) отклонения от ортогональности накапливаются и может потребоваться специальная коррекция алгоритма или другой алгоритм поиска собственных векторов ковариационной матрицы.
 +
 
 +
Решение задачи о наилучшей аппроксимации даёт то же множество решений <math>\left\{a_i\right\}</math>, что и поиск ортогональных проекций с наибольшим рассеянием, по очень простой причине: <math>\Vert x_i - a_k (a_k,x_i)\Vert ^2 = \Vert x_i\Vert ^2 - (a_k,x_i)^2, </math> и первое слагаемое не зависит от <math> a_k</math>. Только одно дополнение к задаче об аппроксимации: появляется последняя главная компонента <math> a_n.</math>
 +
 
 +
=== Поиск ортогональных проекций с наибольшим среднеквадратичным расстоянием между точками ===
 +
 
 +
Ещё одна эквивалентная формулировка следует из очевидного тождества, верного для любых <math>m</math> векторов <math> x_i</math>:
 +
: <math>\frac{1}{m(m-1)}\sum_{i,j=1}^m (x_i-x_j)^2 =\frac{2m^2}{m(m-1)}\left[\frac{1}{m}\sum_{i=1}^m x_i^2 - \left(\frac{1}{m}\sum_{i}^m x_i \right)^2\right].</math>
 +
В левой части этого тождества стоит среднеквадратичное расстояние между точками, а в квадратных скобках справа — выборочная дисперсия. Таким образом, в методе главных компонент ищутся подпространства, в проекции на которые среднеквадратичное расстояние между точками максимально. Такая переформулировка позволяет строить обобщения с взвешиванием различных парных расстояний (а не только точек).
 +
 
 +
=== Аннулирование корреляций между координатами ===
 +
 
 +
Для заданной <math> n</math>-мерной случайной величины <math> X</math> найти такой ортонормированный базис, <math>\left\{a_1,..., a_n \right\}</math>, в котором коэффициент ковариации между различными координатами равен нулю. После преобразования к этому базису
 +
 
 +
: <math>\operatorname{cov}(X_i,X_j)=0</math> для <math>i \neq j </math>.
 +
 
 +
Здесь <math> \operatorname{cov}(X_i,X_j)= \operatorname{E}[(X_i-\overline{X_i})(X_j-\overline{X_j})] </math> — коэффициент ковариации.
 +
 
 +
== Диагонализация ковариационной матрицы ==
 +
 
 +
Все задачи о главных компонентах приводят к задаче диагонализации ковариационной матрицы или выборочной ковариационной матрицы. Эмпирическая или выборочная ковариационная матрица, это
 +
: <math>C = [c_{ij}],\ c_{ij} = \frac{1}{m} \sum_{l=1}^m (x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}).</math>
 +
[[Ковариационная матрица]] многомерной случайной величины <math> X</math>, это
 +
: <math>\Sigma = [\sigma_{ij}],\ \sigma_{ij} = \operatorname{cov}(X_i,X_j)=E[(X_i-\overline{X_i})(X_j-\overline{X_j})].</math>
 +
Векторы главных компонент для задач о наилучшей аппроксимации и о поиске ортогональных проекций с наибольшим рассеянием — это ортонормированный набор <math> \left\{a_1,..., a_n \right\}</math> собственных векторов эмпирической ковариационной матрицы <math>C</math>, расположенных в порядке убывания собственных значений <math>\lambda: \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_n \ge 0. </math> Эти векторы служат оценкой для собственных векторов ковариационной матрицы <math>\operatorname{cov}(X_i,X_j) </math>. В базисе из собственных векторов ковариационной матрицы она, естественно, диагональна, и в этом базисе коэффициент ковариации между различными координатами равен нулю.
 +
 
 +
Если спектр ковариационной матрицы вырожден, то выбирают произвольный ортонормированный базис собственных векторов. Он существует всегда, а собственные числа ковариационной матрицы всегда вещественны и неотрицательны.
 +
 
 +
== Сингулярное разложение матрицы данных ==
 +
 
 +
=== Идея сингулярного разложения ===
 +
Математическое содержание метода главных компонент — это ''спектральное разложение'' ковариационной матрицы <math> C </math>, то есть представление пространства данных в виде суммы взаимно ортогональных собственных подпространств <math> C </math>, а самой матрицы <math> C </math> — в виде линейной комбинации ортогональных проекторов на эти подпространства с коэффициентами <math> \lambda_i </math>. Если <math>\operatorname{X}=\left\{x_1,..., x_m \right\}^T</math> — матрица, составленная из векторов-строк центрированных данных, то <math> C = \operatorname{X}^T\operatorname{X}</math> и задача о спектральном разложении ковариационной матрицы <math> C </math> превращается в задачу о ''сингулярном разложении'' ({{lang-en|[http://en.wikipedia.org/wiki/Singular_value_decomposition Singular value decomposition]}}) матрицы данных <math>\operatorname{X}</math>.
 +
 
 +
Число <math> \sigma \geq 0 </math> называется '''сингулярным числом''' матрицы <math>\operatorname{X}</math> тогда и только тогда, когда существуют '''правый и левый сингулярные векторы''': такие <math>m</math>-мерный вектор-строка <math>b_{\sigma}</math> и <math>n</math>-мерный вектор-столбец <math>a_{\sigma}</math> (оба единичной длины), что выполнено два равенства:
 +
: <math>\operatorname{X} a_{\sigma} = \sigma b_{\sigma}^T ;\, \, b_{\sigma} \operatorname{X}= \sigma a_{\sigma}^T.</math>
 +
Пусть <math>p= \operatorname{rang} \operatorname{X} \leq \min\{n,m\}</math> — [[ранг матрицы]] данных. '''Сингулярное разложение''' матрицы данных <math>\operatorname{X}</math> — это её представление в виде
 +
: <math>\operatorname{X}= \sum_{l=1}^p \sigma_l b_l^T a_l^T ; \;\operatorname{X}^T= \sum_{l=1}^p \sigma_l a_l b_l \; \left(x_{ij}=\sum_{l=1}^p \sigma_l b_{li}a_{lj}\right),</math>
 +
где <math>\sigma_l > 0</math> — сингулярное число, <math>a_l=(a_{li}), \, i=1,... n</math> — соответствующий правый сингулярный вектор-столбец, а <math>b_l=(b_{li}), \, i=1,... m</math> — соответствующий левый сингулярный вектор-строка (<math>l=1,...p</math>). Правые сингулярные векторы-столбцы <math>a_l</math>, участвующие в этом разложении, являются векторами главных компонент и собственными векторами эмпирической ковариационной матрицы
 +
<math>C =\operatorname{X} ^T \operatorname{X} </math>, отвечающими положительным собственным числам <math> \lambda_l=\sigma_l^2 > 0 </math>.
 +
 
 +
Хотя формально задачи сингулярного разложения матрицы данных и спектрального разложения ковариационной матрицы совпадают, алгоритмы вычисления сингулярного разложения напрямую, без вычисления спектра ковариационной матрицы, более эффективны и устойчивы <ref>''Bau III, D., Trefethen, L. N.'', [http://books.google.com/books?id=bj-Lu6zjWbEC&pg=PA136&dq=isbn:9780898713619&sig=BmAatL8LDJZZRhfJIFVRHLQNJw0#PPP1,M1 Numerical linear algebra], Philadelphia: Society for Industrial and Applied Mathematics, 1997. (Lecture 31) ISBN 978-0-89871-361-9 </ref>.
 +
 
 +
Теория сингулярного разложения была создана Дж. Дж. Сильвестром ({{lang-en|[http://en.wikipedia.org/wiki/James_Joseph_Sylvester J. J. Sylvester]}}) в [[1889]] г. и изложена во всех подробных руководствах по теории матриц <ref>''[[Гантмахер, Феликс Рувимович|Гантмахер Ф. Р.]]'', Теория матриц. — М.: Наука, 1966. — 576 стр.</ref>.
 +
 
 +
=== Простой итерационный алгоритм сингулярного разложения ===
 +
 
 +
Основная процедура — поиск наилучшего приближения произвольной <math>m \times n</math> матрицы <math>X=(x_{ij})</math> матрицей вида <math>b \otimes a = (b_i a_j)</math> (где <math>b</math> — <math>m</math>-мерный вектор, а <math>a</math> — <math>n</math>-мерный вектор) методом наименьших квадратов:
 +
: <math>F(b, a) = \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^n (x_{ij} - b_i a_j )^2 \to \min</math>
 +
Решение этой задачи дается последовательными итерациями по явным формулам. При фиксированном векторе <math>a=(a_j) </math> значения <math>b=(b_i) </math>, доставляющие минимум форме <math>F(b, a) </math>, однозначно и явно определяются из равенств <math>\partial F/ \partial b_i = 0</math> :
 +
 
 +
: <math>\frac{\partial F}{\partial b_i} = - \sum_{j=1}^n (x_{ij} - b_i a_j )a_j = 0; \;\; b_i = \frac{\sum_{j=1}^n x_{ij} a_j}{\sum_{j=1}^n a_j^2 }\, . </math>
 +
Аналогично, при фиксированном векторе <math>b =(b_ i) </math> определяются значения <math>a=(a_j) </math>:
 +
: <math>a_j = \frac{\sum_{i=1}^m b_i x_{ij} }{\sum_{i =1}^m b_i ^2 }\, . </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+... +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>a^l</math> при разных <math>l</math> должны быть ортогональны «по построению», однако при большом числе итерации (большая размерность, много компонент) малые отклонения от ортогональности накапливаются и может потребоваться специальная коррекция <math>a^l</math> на каждом шаге, обеспечивающая его ортогональность ранее найденным главным компонентам.
 +
 
 +
Для квадратных симметричных положительно определённых матриц описанный алгоритм превращается в метод прямых итераций для поиска собственных векторов (см. статью [[Собственные векторы, значения и пространства]]).
 +
 
 +
== Матрица преобразования к главным компонентам ==
 +
 
 +
Матрица <math>A</math> преобразования данных к главным компонентам строится из векторов главных компонент: <math>A=\left \{a_1,...,a_n \right \}^T</math>. Здесь <math> a_i</math> — ортонормированные векторы-столбцы главных компонент, расположенные в порядке убывания собственных значений, верхний индекс <math> T</math> означает транспонирование. Матрица <math>A</math> является [[Ортогональная матрица|ортогональной]]: <math>A A^T=1</math>.
 +
 
 +
После преобразования большая часть вариации данных будет сосредоточена в первых координатах, что даёт возможность отбросить оставшиеся и рассмотреть пространство уменьшенной размерности.
 +
 
 +
== Остаточная дисперсия ==
 +
Пусть данные центрированы, <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 ... \ge \lambda_n \ge 0</math> собственные значения эмпирической ковариационной матрицы <math>C</math>, расположенные в порядке убывания, с учетом кратности.
 +
 
 +
Эта величина называется ''остаточной дисперсией''. Величина
 +
: <math>\frac{1}{m} \sum_{i=1}^m \left\Vert \sum_{j=1}^k a_j (a_j, x_i) \right \Vert ^2=
 +
\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}+...+\lambda_{n}}{\lambda_{1}+\lambda_{2}+...+\lambda_{n}}.</math>
 +
 
 +
По относительной ошибке <math> \delta_k</math> оценивается применимость метода главных компонент с проецированием на первые <math> k</math> компонент.
 +
 
 +
'''Замечание''': в большинстве вычислительных алгоритмов собственные числа <math> \lambda_i</math> с соответствуюшими собственными векторами — главными компонентами <math> a_i</math> вычисляются в порядке «от больших <math> \lambda_i</math> — к меньшим». Для вычисления <math> \delta_k</math> достаточно вычислить первые <math> k</math> собственных чисел и след эмпирической ковариационной матрицы <math>C</math>, <math>\operatorname{tr} C</math> (сумму диагональных элементов <math>C</math>, то есть дисперсий по осям). Тогда
 +
: <math>\delta^2_k=\frac{1}{\operatorname{tr} C}\left(\operatorname{tr} C -\sum_{i=1}^k \lambda_{i}\right).</math>
 +
 
 +
== Нормировка ==
 +
 
 +
=== Нормировка после приведения к главным компонентам ===
 +
 
 +
''После'' проецирования на первые <math> k</math> главных компонент с <math>\lambda_1 \ge \lambda_2 \ge ... \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> главных компонент вместе с нормировкой задается матрицей
 +
 
 +
: <math>K=\left \{\frac{a_1}{\sqrt{ \lambda_1}},\frac{a_2}{\sqrt{ \lambda_2}},...,\frac{a_k}{\sqrt{ \lambda_k}} \right \}^T</math>.
 +
 
 +
Именно это преобразование чаще всего называется преобразованием Кархунена-Лоэва. Здесь <math> a_i</math> — векторы-столбцы, а верхний индекс <math> T</math> означает транспонирование.
 +
 
 +
=== Нормировка до вычисления главных компонент ===
 +
 
 +
'''Предупреждение''': не следует путать нормировку, проводимую после преобразования к главным компонентам, с нормировкой и «обезразмериванием» при ''предобработке данных'', проводимой до вычисления главных компонент. Предварительная нормировка нужна для обоснованного выбора метрики, в которой будет вычисляться наилучшая аппроксимация денных, или будут искаться направления наибольшего разброса (что эквивалентно). Например, если данные представляют собой трёхмерные векторы из «метров, литров и килограмм», то при использовании стандартного евклидового расстояния разница в 1 метр по первой координате будет вносить тот же вклад, что разница в 1 литр по второй, или в 1 кг по третьей. Обычно системы единиц, в которых представлены исходные данные, недостаточно точно отображают наши представления о естественных масштабах по осям, и проводится «обезразмеривание»: каждая координата делится на некоторый масштаб, определяемый данными, целями их обработки и процессами измерения и сбора данных.
 +
 
 +
Есть три cущественно различных стандартных подхода к такой нормировке: на ''единичную дисперсию'' по осям (масштабы по осям равны средним квадратичным уклонениям — после этого преобразования ковариационная матрица совпадает с матрицей [[Коэффициент корреляции|коэффициентов корреляции]]), на ''равную точность измерения'' (масштаб по оси пропорционален точности измерения данной величины) и на ''равные требования'' в задаче (масштаб по оси определяется требуемой точностью прогноза данной величины или допустимым её искажением — уровнем толерантности). На выбор предобработки влияют содержательная постановка задачи, а также условия сбора данных (например, если коллекция данных принципиально не завершена и данные будут ещё поступать, то нерационально выбирать нормировку строго на единичную дисперсию, даже если это соответствует смыслу задачи, поскольку это предполагает перенормировку всех данных после получения новой порции; разумнее выбрать некоторый масштаб, грубо оценивающий стандартное отклонение, и далее его не менять).
 +
 
 +
Предварительная нормировка на единичную дисперсию по осям разрушается поворотом системы координат, если оси не являются главными компонентами, и нормировка при предобработке данных не заменяет нормировку после приведения к главным компонентам.
 +
 
 +
== Механическая аналогия и метод главных компонент для взвешенных данных ==
 +
 
 +
Если сопоставить каждому вектору данных единичную массу, то эмпирическая ковариационная матрица
 +
<math> C</math> совпадёт с [[Момент инерции#Тензор инерции и эллипсоид инерции|тензором инерции]] этой системы точечных масс (делённым на полную массу <math> m</math>), а задача о главных компонентых — с задачей приведения тензора инерции к главным осям. Можно использовать дополнительную свободу в выборе значений масс для учета важности точек данных или надежности их значений (важным данным или данным из более надежных источников приписываются бо́льшие массы). Если '''вектору данных <math> x_l</math> придаётся масса <math> w_l</math>,''' то вместо эмпирической ковариационной матрицы <math> C</math> получим
 +
: <math>C^w = [c^w_{ij}],\ c^w_{ij} = \frac{1}{\sum_{l} w_l} \sum_{l=1}^m w_l(x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}).</math>
 +
Все дальнейшие операции по приведению к главным компонентам производятся так же, как и в основной версии метода: ищем ортонормированный собственный базис <math> C^w</math>, упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми <math> k</math> компонентами (по суммам собственных чисел <math> C^w</math>), нормируем и т. п.
 +
 
 +
Более общий способ взвешивания даёт '''максимизация взвешенной суммы попарных расстояний'''<ref>''Koren Y., Carmel L.,'' Robust linear dimensionality reduction, IEEE Transactions on Visualisation and Computer Graphics, 10 (4) (2004), 459—470. [http://pca.narod.ru/ А также на сайте PCA]</ref> между проекциями. Для каждых двух точек данных, <math>x_l , \ x_q</math> вводится вес <math>d_{lq}</math>; <math>d_{lq}=d_{ql}</math> и <math>d_{l}=\sum_{q=1}^m d_{lq}</math>. Вместо эмпирической ковариационной матрицы <math> C</math> используется
 +
: <math>C^d = [c^d_{ij}],\ c^d_{ij} =\sum_{l=1}^m d_l (x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}) -\sum_{l \neq q, \ l,q=1}^m d_{lq}(x_{li} - \overline{X_{i}})(x_{qj}- \overline{X_{j}}).</math>
 +
При <math>d_{lq}>0</math> симметричная матрица <math>C^d</math> положительно определена, поскольку положительна квадратичная форма:
 +
:<math>\sum_{ij} c^d_{ij}a_i a_j = \frac{1}{2}\sum_{lq}d_{lq}\left(\sum_ia_i(x_{li}-x_{qi})\right)^2.</math>
 +
Далее ищем ортонормированный собственный базис <math> C^d</math>, упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми <math> k</math> компонентами и т. д. — в точности так же, как и в основном алгоритме.
 +
 
 +
Этот способ применяется ''при наличии классов'': для <math>x_l , \ x_q</math> из разных классов вес <math>d_{lq}</math> вес выбирается бо́льшим, чем для точек одного класса. В результате, в проекции на взвешенные главные компоненты различные классы «раздвигаются» на большее расстояние.
 +
 
 +
Другое применение — ''снижение влияния больших уклонений'' (оутлайеров, {{lang-en|[http://en.wikipedia.org/wiki/Outlier Outlier]}}), которые могут искажать картину из-за использования среднеквадратичного расстояния: если выбрать <math>d_{lq}=1/ \| x_l -x_q \|</math>, то влияние больших уклонений будет уменьшено. Таким образом, описанная модификация метода главных компонент является более [[Робастность в статистике|робастной]], чем классическая.
 +
 
 +
== Специальная терминология ==
 +
 
 +
В статистике при использовании метода главных компонент используют несколько специальных терминов.
 +
 
 +
'''Матрица данных''' <math>\mathbf{X}=\{x_1,... x_m\}^T</math>; каждая строка — вектор ''предобработанных'' данных (''центрированных'' и правильно ''нормированных''), число строк — <math>m</math> (количество векторов данных), число столбцов — <math>n</math> (размерность пространства данных);
 +
 
 +
'''Матрица нагрузок''' (Loadings) <math>\mathbf{P}=\{a_1,... a_k\}</math>; каждый столбец — вектор главных компонент, число строк — <math>n</math> (размерность пространства данных), число столбцов — <math>k</math> (количество векторов главных компонент, выбранных для проецирования);
 +
 
 +
'''Матрица счетов''' (Scores) <math>\mathbf{T}=[t_{ij}]; \; t_{ij}=(x_i,a_j)</math>; каждая строка — проекция вектора данных на <math>k</math> главных компонент; число строк — <math>m</math> (количество векторов данных), число столбцов — <math>k</math> (количество векторов главных компонент, выбранных для проецирования);
 +
 
 +
'''Матрица Z-счетов''' (Z-scores) <math>\mathbf{Z}=[z_{ij}]; \; z_{ij}=\frac{(x_i,a_j)}{\sqrt{ \lambda_j}}</math>; каждая строка — проекция вектора данных на <math>k</math> главных компонент, нормированная на единичную выборочную дисперсию; число строк — <math>m</math> (количество векторов данных), число столбцов — <math>k</math> (количество векторов главных компонент, выбранных для проецирования);
 +
 
 +
'''Матрица ошибок''' (или '''остатков''') (Errors or residuals) <math>\mathbf{E}=\mathbf{X}-\mathbf{T}\mathbf{P}^T</math>.
 +
 
 +
Основная формула: <math>\mathbf{X}=\mathbf{T}\mathbf{P}^T+\mathbf{E}.</math>
 +
 
 +
== Пределы применимости и ограничения эффективности метода ==
 +
 
 +
 
 +
[[Изображение: BranchingPrincipalComponents.gif|thumb| Построение ветвящихся главных компонент методом топологических грамматик. Крестики — точки данных, красное дерево с желтыми узлами — аппроксимирующий дендрит<ref name="TopGram">Описание метода можно найти в статье: ''Gorban A. N. , Sumner N. R., and Zinovyev A. Y.'', Topological grammars for data approximation, Applied Mathematics Letters, Volume 20, Issue 4 (2007), 382—386; или ''Gorban A. N. , Sumner N. R., and Zinovyev A. Y.'', [http://pca.narod.ru/contentsgkwz.htm Beyond The Concept of Manifolds: Principal Trees, Metro Maps, and Elastic Cubic Complexes] In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0; [http://arxiv.org/abs/0801.0176 а также в arXiv]</ref>.]]
 +
 
 +
Метод главных компонент применим всегда. Распространённое утверждение о том, что он применим только к [[Нормальное распределение|нормально распределённым]] данным (или для распределений, близких к нормальным) неверно: в исходной формулировке К. Пирсона ставится задача об ''аппроксимации'' конечного множества данных и отсутствует даже гипотеза о их статистическом порождении, не говоря уж о распределении.
 +
 
 +
Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность <math> \delta_k</math>. Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности. Для работы с такими «кривыми» главными компонентами изобретен метод главных многообразий<ref>С этой работы началось изучение главных многообразий. Диссертация ''T. Хасти'': ''Hastie T.'', [http://www.slac.stanford.edu/pubs/slacreports/slac-r-276.html Principal Curves and Surfaces], Ph.D Dissertation, Stanford Linear Accelerator Center, Stanford University, Stanford, California, US, November 1984. [http://pca.narod.ru/HastieThesis.htm А также на сайте PCA]</ref> и различные версии нелинейного метода главных компонент<ref>''Scholz M., Fraunholz M., Selbig J.'', [http://pca.narod.ru/contentsgkwz.htm Nonlinear Principal Component Analysis: Neural Network Models and Applications], In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0</ref><ref>''Yin H.'' [http://pca.narod.ru/contentsgkwz.htm Learning Nonlinear Principal Manifolds by Self-Organising Maps], In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0</ref>. Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например [[Самоорганизующаяся карта Кохонена|самоорганизующиеся карты Кохонена]], [[нейронный газ]]<ref>''Martinetz, T.M., Berkovich, S.G., and Schulten K.J.'', Neural-gas network for vector quantization and its application to time-series prediction. IEEE Transactions on Neural Networks, 4 (1993) #4, 558—569.</ref> или топологические грамматики<ref name="TopGram"/>. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к ''независимым компонентам''<ref>''Hyvdrinen A, Karhunen J., and Oja E.'', Independent Component Analysis, A Volume in the Wiley Series on Adaptive and Learning Systems for Signal Processing, Communications, and Control. — John Wiley & Sons, Inc., 2001. — XVI+481 pp. ISBN 0-471-40540-X</ref>, которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.
 +
 
 +
== Примеры использования ==
 +
 
 +
=== Компрессия изображений и видео ===
 +
 
 +
Для уменьшения пространственной избыточности пикселей при кодировании изображений и видео используется линейные преобразования блоков пикселей. Последующие квантования полученных коэффициентов и кодирование без потерь позволяют получить значительные коэффициенты сжатия. Использование преобразования PCA в качестве линейного преобразования является для некоторых типов данных оптимальным с точки зрения размера полученных данных при одинаковом искажении <ref>''Rao, K., Yip P.'' (eds.), The Transform and Data Compression Handbook, CRC Press, Baton Rouge, 2001.</ref>. На данный момент этот метод активно не используется, в основном из-за большой вычислительной сложности. Также сжатия данных можно достичь отбрасывая последние коэффициенты преобразования.
 +
 
 +
=== Подавление шума на изображениях <ref>''Muresan D. D., Parks T. W.'', Adaptive Principal Components and Image Denoising // IEEE International Conference on Image Processing (ICIP), September 2003, 101—104</ref> ===
 +
 
 +
Основная суть метода — при удалении шума из блока пикселей представить окрестность этого блока в виде набора точек в многомерном пространстве, применить к нему PCA и оставить только первые компоненты преобразования. При этом предполагается, что в первых компонентах содержится основная полезная информация, оставшиеся же компоненты содержат ненужный шум. Применив обратное преобразование после редукции базиса главных компонент, мы получим изображение без шума.
 +
 
 +
=== Индексация видео ===
 +
 
 +
Основная идея — представить при помощи PCA каждый кадр видео несколькими значениями, которые в дальнейшем будут использоваться при построении базы данных и запросам к ней. Столь существенная редукция данных позволяет значительно увеличить скорость работы и устойчивость к ряду искажений в видео.
 +
 
 +
=== Биоинформатика ===
 +
 
 +
[[Изображение:Streptomyces_coelicolor_sc.gif|thumb|'''Рис. А.''' Проекция ДНК-блуждания на первые 2 главные компоненты для генома [[бактерии]] Streptomyces coelicolor]]
 +
[[Изображение:Streptomyces_coelicolor_sc_anim.gif|thumb|'''Рис. Б.''' Проекция ДНК-блуждания на первые 3 главные компоненты для генома [[бактерии]] Streptomyces coelicolor. Вращение применяется для визуализации трехмерной конфигурации]]
 +
Метод главных компонент интенсивно используется в [[Биоинформатика|биоинформатике]] для сокращения размерности описания, выделения значимой информации, визуализации данных и др. Один из распространнённых вариантов использования — анализ соответствий ({{lang-en|Correspondence Analysis}}) <ref>''Tekaia F.'', [http://www.pasteur.fr/~tekaia/caongenomes.html Use of Correspondence Analysis in Genome Exploration].</ref>. На иллюстрациях (Рис. А, Б) ''генетический текст'' (см. статью [[Трансляция (биология)]]) представлен как множество точек в 64-мерном пространстве частот триплетов. Каждая точка соответствует фрагменту [[ДНК]] в скользящем окне длиной 300 [[нуклеотид]]ов (ДНК-блуждание). Этот фрагмент разбивается на неперекрывающиеся триплеты, начиная с первой позиции. Относительные частоты этих триплетов в фрагменте и составляют 64-мерный вектор. На Рис. А представлена проекция на первые 2 главные компоненты для генома [[бактерии]] Streptomyces coelicolor. На Рис. Б представлена проекция на первые 3 главные комроненты. Оттенками красного и коричневого выделены фрагменты кодирующих последовательностей в прямой цепи ДНК, а оттенками зеленого выделены фрагменты кодирующих последовательностей в обратной цепи ДНК. Черным помечены фрагменты, принадлежащие некодирующей части. Анализ методом главных компонент большинства известных бактериальных [[геном]]ов представлен на специализированном сайте<ref>''Zinovyev A.'', [http://www.ihes.fr/~zinovyev/7clusters/index.htm Сluster structures in genomic word frequency distributions]; а также в [http://arxiv.org/abs/q-bio/0504013 arXiv: PCA and K-Means decipher genome].</ref>.
 +
 
 +
=== Хемометрика ===
 +
 
 +
Метод главных компонент — один из основных методов в [[Хемометрика|хемометрике]] ({{lang-en|[http://en.wikipedia.org/wiki/Chemometrics Chemometrics]}}). Позволяет разделить матрицу исходных данных X на две части: «содержательную» и «шум». По наиболее популярному определению <ref>Сайт «[http://www.chemometrics.ru/ Хемометрика]»</ref> «Хемометрика — это химическая дисциплина, применяющая математические, статистические и другие методы, основанные на формальной логике, для построения или отбора оптимальных методов измерения и планов эксперимента, а также для извлечения наиболее важной информации при анализе экспериментальных данных».
 +
 
 +
=== Психодиагностика ===
 +
 
 +
[[Психодиагностика]] является одной из наиболее разработанных областей приложения метода главных компонент <ref>Дюк В. А., Компьютерная психодиагностика, С-Пб., 1994; отдельные разделы см. на сайте [http://psyfactor.org/lib/dyuk1.htm «Пси-фактор»]</ref>. Стратегия использования основывается на гипотезе об ''автоинформативности'' экспериментальных данных, которая подразумевает, что диагностическую модель можно создать путем аппроксимации геометрической структуры множества объектов в пространстве исходных признаков. Хорошую линейную диагностическую модель удается построить, когда значительная часть исходных признаков внутренне согласованна. Если эта внутренняя согласованность отражает искомый ''психологический конструкт'', то параметры линейной диагностической модели (веса признаков) дает метод главных компонент.
 +
 
 +
=== [[Общественные науки]] ===
 +
 
 +
Метод главных компонент — один из основных инструментов [[эконометрика|эконометрики]]. Он применяется для: (1) наглядного представления данных; (2) обеспечения лаконизма моделей, упрощения счета и интерпретации; (3) сжатия объемов хранимой информации. Метод обеспечивает максимальную информативность и минимальное искажение геометрической структуры исходных данных. В [[социология|социологии]] метод небходим для решения первых двух основных задач<ref>''Гуц А. К., Фролова Ю. В.'', Математические методы в социологии, Серия: Синергетика: от прошлого к будущему. — Издательство «УРСС», 2007. — 216 с.</ref>: (1) анализ данных (описание результатов опросов или других исследований, представленных в виде массивов числовых данных); (2) описание социальных явлений (построение моделей явлений, в том числе и математических моделей). В [[Политология|политологии]] метод главных компонент был основным инструментом проекта [http://worldpolities.org/ «Политический Атлас Современности»]<ref>Политический атлас современности: Опыт многомерного статистического анализа политических систем современных государств. — М.: Изд-во «МГИМО-Университет», 2007. — 272 с.</ref> для линейного и [http://pca.narod.ru/AtlasCartography2006.pdf нелинейного анализа рейтингов] 192 стран мира по пяти специально разработанным интегральным индексам (уровня жизни, международного влияния, угроз, государственности и демократии). Для картографии результатов этого анализа разработана [http://atlas.savvy.ru/ специальная ГИС] ([[Геоинформационная система]]), объединяющая географическое пространство с пространством признаков.
 +
 
 +
=== Сокращение размерности динамических моделей ===
 +
 
 +
''Проклятие размерности'' ({{lang-en|[http://en.wikipedia.org/wiki/Curse_of_dimensionality Curse of dimensionality]}}) затрудняет моделирование сложных систем. Сокращение размерности модели — необходимое условие успеха моделирования. Для достижения этой цели создана разветвленная математическая технология. Метод главных компонент также используется в этих задачах (часто под названием ''истинное'' или ''собственное ортогональное разложение'' — {{lang-en|proper orthogonal decomposition (POD)}}). Например, при описании динамики [[турбулентность|турбулентности]] динамические переменные — поле скоростей — принадлежат бесконечномерному пространству (или, если предствлять поле его значениями на достаточно мелкой сетке, — конечномерному пространству большой размерности). Можно набрать большую коллекцию мгновенных значений полей и применить к этому множеству многомерных «векторов данных» метод главных компонент. Эти главные компоненты называются также ''эмпирические [[собственные векторы]]''. В некоторых случаях (''структурная турбулентность'') метод дает впечатляющее сокращение размерности<ref>''Berkooz G, Holmes Ph., and. Lumley J. L'', The proper orthogonal decomposition in the analysis of turbulent flows, Annu. Rev. Fluid Mech. 25 (1993), 539—575. Первая публикация для анализа турбулентности — ''Lumley, J. L.'', The structure of inhomogeneous turbulence. In Atmospheric Turbulence and Wave Propagation, ed. A. M. Yaglom, V. I. Tatarski, pp. 166—178. Moscow: Nauka, 1967. (Атмосферная турбулентность и распространение радиоволн. Труды Международного коллоквиума. Москва, 15—22 июня 1965 г. Под ред. А. М. Яглома и В. И. Татарского. М.: Наука, 1967, 374 стр. с илл. и карт. (АН СССР. Междувед. геофиз. ком. Ин-т физики атмосферы). Интересно, что авторы этих работ возводят историю своего подхода к работам Косамби ({{lang-en|Kosambi}}) (1943), Лоэва ({{lang-en|Loeve}}) (1945), Кархунена ({{lang-en|Karhunen}}) (1946), Пугачева ({{lang-en|Pougachev}}) (1953), и Обухова ({{lang-en|Obukhov}}) (1954), потеряв совершенно Пирсона и 40 лет предшествующей истории метода.</ref> Другие области применения этой техники сокращения динамических моделей чрезвычайно разнообразны — от теоретических основ [[Химическая технология|химической технологии]] ({{lang-en|chemical engineering science}}) до [[Океанология|океанологии]] и [[Климатология|климатологии]].
== Литература ==
== Литература ==
-
* Рао&nbsp;С.Р. Линейные статистические методы и их применения. М.:&nbsp;Наука. 1968.&nbsp;&#151; С.&nbsp;530-533.
 
-
* Айвазян&nbsp;С.А., Бухштабер&nbsp;В.М., Енюков&nbsp;И.С., Мешалкин&nbsp;Л.Д. Прикладная статистика. Классификация и снижение размерности. М.:&nbsp;Финансы и статистика.&nbsp;1989.
 
-
* Jolliffe&nbsp;I.T. Principal Component Analysis, Springer Series in Statistics. Springer.&nbsp;2002.
 
-
* Pearson, K. (1901). "On Lines and Planes of Closest Fit to Systems of Points in Space". Philosophical Magazine 2 (6): 559–572. [http://pbil.univ-lyon1.fr/R/liens/pearson1901.pdf]
 
-
== Внешние ссылки ==
+
=== Классические работы ===
-
* [http://pca.narod.ru/ Нелинейный метод главных компонент]
+
 
-
* [http://en.wikipedia.org/wiki/Principal_components_analysis Principal components analysis at wikipedia.org]
+
* ''Pearson K.'', On lines and planes of closest fit to systems of points in space, Philosophical Magazine, (1901) 2, 559—572; [http://pca.narod.ru/ а также на сайте PCA].
-
* [http://ru.wikipedia.org/wiki/%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 Метод главных компонент на wikipedia.org]
+
* ''Sylvester J.J.'', On the reduction of a bilinear quantic of the nth order to the form of a sum of n products by a double orthogonal substitution, Messenger of Mathematics, 19 (1889), 42—46; [http://pca.narod.ru/ а также на сайте PCA].
 +
* ''Frećhet M. '' Les élements aléatoires de nature quelconque dans un espace distancié. Ann. Inst. H. Poincaré, 10 (1948), 215—310.
 +
 
 +
=== Основные руководства (стандарт де-факто) ===
 +
 
 +
* ''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика. Классификация и снижение размерности.— М.: Финансы и статистика, 1989.— 607 с.
 +
* ''Jolliffe I.T.'' [http://www.springer.com/statistics/statistical+theory+and+methods/book/978-0-387-95442-4 Principal Component Analysis], Series: [http://www.springer.com/series/692 Springer Series in Statistics], 2nd ed., Springer, NY, 2002, XXIX, 487 p. 28 illus. ISBN 978-0-387-95442-4
 +
 
 +
=== Сборник современных обзоров ===
 +
 
 +
* ''Gorban A. N., Kegl B., Wunsch D., Zinovyev A. Y.'' (Eds.), [http://www.springer.com/west/home/math/cse?SGWID=4-10045-22-173750210-0 Principal Manifolds for Data Visualisation and Dimension Reduction], [http://www.springer.com/west/home/math/cse?SGWID=4-10045-69-173622682-0 Series: Lecture Notes in Computational Science and Engineering] 58, Springer, Berlin — Heidelberg — New York, 2007, XXIV, 340 p. 82 illus. ISBN 978-3-540-73749-0 (а также [http://pca.narod.ru/ онлайн]).
 +
 
 +
== Ссылки ==
 +
 
 +
* [http://csnet.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf A tutorial on Principal Components Analysis], Lindsay I Smith, 2002
 +
* [http://pca.narod.ru Нелинейный метод главных компонент] (сайт-библиотека)
 +
 
 +
== Примечания ==
 +
{{reflist}}
{{Заготовка}}
{{Заготовка}}

Версия 22:49, 30 июня 2008

Метод Главных Компонент (Шаблон:Lang-en) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (Шаблон:Lang-en) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных. Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (Шаблон:Lang-en)[1] или преобразованием Хотеллинга (Шаблон:Lang-en). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (Шаблон:Lang-en), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

Содержание

Формальная постановка задачи

Задача анализа главных компонент, имеет, как минимум, три базовых версии:

  • аппроксимировать данные линейными многообразиями меньшей размерности;
  • найти подпространства меньшей размерности, в ортогональной проекции на которые разброс данных максимален;
  • для данной многомерной случайной величины построить такое ортогональное преобразования координат, что в результате корреляции между отдельными координатами обратятся в ноль.

Первые две версии оперируют конечными множествами данных. Они эквивалентны и не используют никакой гипотезы о статистическом порождении данных. Третья версия оперирует случайными величинами. Конечные множества появляются здесь как выборки из данного распределения, а решение двух первых задач — как приближение к «истинному» преобразованию Кархунена-Лоэва. При этом возникает дополнительный и не вполне тривиальный вопрос о точности этого приближения.

Аппроксимация данных линейными многообразиями

Иллюстрация к знаменитой работе К. Пирсона (1901): даны точки <math> P_i</math> на плоскости, <math>  p_i</math> — расстояние от <math>  P_i</math> до прямой <math> AB</math>. Ищется прямая <math>  AB</math>, минимизирующая сумму <math>\sum_i p_i^2</math>
Иллюстрация к знаменитой работе К. Пирсона (1901): даны точки <math> P_i</math> на плоскости, <math> p_i</math> — расстояние от <math> P_i</math> до прямой <math> AB</math>. Ищется прямая <math> AB</math>, минимизирующая сумму <math>\sum_i p_i^2</math>

Метод главных компонент начинался с задачи наилучшей аппроксимации конечного множества точек прямыми и плоскостями (К. Пирсон, 1901). Дано конечное множество векторов <math>x_1,x_2,...x_m \in\mathbb{R}^n </math>. Для каждого <math> k = 0,1,..., n-1 </math> среди всех <math>k</math>-мерных линейных многообразий в <math>\mathbb{R}^n </math> найти такое <math>L_k \subset \mathbb{R}^n </math>, что сумма квадратов уклонений <math> x_i</math> от <math> L_k</math> минимальна:

<math>\sum_{i=1}^m \operatorname{dist}^2(x_i, L_k) \to \min</math>,

где <math>\operatorname{dist}(x_i, L_k) </math> — евклидово расстояние от точки до линейного многообразия. Всякое <math>k </math>-мерное линейное многообразие в <math>\mathbb{R}^n </math> может быть задано как множество линейных комбинаций <math>L_k = \{ a_0 +\beta_1 a_1 +...+ \beta_k a_k | \beta_i \in \mathbb{R} \} </math>, где параметры <math> \beta_i </math> пробегают вещественную прямую <math>\mathbb{R}</math>, <math>a_0 \in \mathbb{R}^n</math> а <math>\left\{a_1,..., a_k \right\} \subset \mathbb{R}^n</math> — ортонормированный набор векторов

<math>\operatorname{dist}^2(x_i, L_k) = \Vert x_i - a_0 - \sum_{j=1}^k a_j (a_j, x_i - a_0) \Vert ^2</math>,

где <math>\Vert \cdot \Vert </math> евклидова норма, <math> \left(a_j, x_i\right) </math> — евклидово скалярное произведение, или в координатной форме:

<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,..., n-1 </math> даётся набором вложенных линейных многообразий <math>L_0 \subset L_1 \subset ... L_{n-1} </math>, <math>L_k = \{ a_0 +\beta_1 a_1 +...+ \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> a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left(\sum_{i=1}^m \operatorname{dist}^2(x_i, L_0)\right), </math>

то есть

<math>a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left (\sum_{i=1}^m \Vert x_i - a_0\Vert ^2\right) </math>.

Это — выборочное среднее: <math>a_0 = \frac{1}{m} \sum_{i=1}^m x_i = \overline{X}.</math> Фреше в 1948 году обратил внимание, что вариационное определение среднего (как точки, минимизирующей сумму квадратов расстояний до точек данных) очень удобно для построения статистики в произвольном метрическом пространстве, и построил обобщение классической статистики для общих пространств (обобщённый метод наименьших квадратов).

Векторы главных компонент могут быть найдены как решения однотипных задач оптимизации:

1) централизуем данные (вычитаем среднее): <math>x_i := x_i - \overline{X_i}</math>. Теперь <math>\sum_{i=1}^m x_i =0 </math>;
2) находим первую главную компоненту как решение задачи;
<math>a_1 = \underset{\Vert a_1 \Vert =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \Vert x_i - a_1 (a_1,x_i)\Vert ^2\right)</math>.
Если решение не единственно, то выбираем одно из них.
3) Вычитаем из данных проекцию на первую главную компоненту:
<math>x_i := x_i - a_1 \left(a_1,x_i\right) </math>;
4) находим вторую главную компоненту как решение задачи
<math>a_2 = \underset{\Vert a_2 \Vert =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \Vert x_i - a_2 (a_2,x_i)\Vert ^2\right) </math>.
Если решение не единственно, то выбираем одно из них.
2k-1) Вычитаем проекцию на <math>(k-1)</math>-ю главную компоненту (напомним, что проекции на предшествующие <math>(k-2)</math> главные компоненты уже вычтены):
<math>x_i := x_i - a_{k-1} \left(a_{k-1},x_i\right) </math>;
2k) находим k-ю главную компоненту как решение задачи:
<math>a_k = \underset{\Vert a_k \Vert =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \Vert x_i - a_k (a_k,x_i)\Vert ^2\right) </math>.
Если решение не единственно, то выбираем одно из них.

На каждом подготовительном шаге <math> (2k-1)</math> вычитаем проекцию на предшествующую главную компоненту. Найденные векторы <math>\left\{a_1,..., a_{ n -1} \right\}</math> ортонормированы просто в результате решения описанной задачи оптимизации, однако чтобы не дать ошибкам вычисления нарушить взаимную ортогональность векторов главных компонент, можно включать <math>a_k \bot \{a_1,..., a_{k -1} \} </math> в условия задачи оптимизации.

Неединственность в определении <math> a_k</math> помимо тривиального произвола в выборе знака (<math> a_k</math> и <math> -a_k</math> решают ту же задачу) может быть более существенной и происходить, например, из условий симметрии данных.

Поиск ортогональных проекций с наибольшим рассеянием

Первая главная компонента максимизирует выборочную дисперсию проекции данных
Первая главная компонента максимизирует выборочную дисперсию проекции данных


Пусть нам дан центрированный набор векторов данных <math>x_i\in\mathbb{R}^n \; (i=1,...,m)</math> (среднее арифметическое значение <math> x_i </math> равно нулю). Задача — найти такое ортогональное преобразование в новую систему координат, для которого были бы верны следующие условия:

  • Выборочная дисперсия данных вдоль первой координаты максимальна (эту координату называют первой главной компонентой);
  • Выборочная дисперсия данных вдоль второй координаты максимальна при условии ортогональности первой координате (вторая главная компонента);
  • Выборочная дисперсия данных вдоль значений <math>k</math>-ой координаты максимальна при условии ортогональности первым <math>k-1</math> координатам;

Выборочная дисперсия данных вдоль направления, заданного нормированным вектором <math> a_k</math>, это

<math>S^2_m \left[ (X, a_k) \right ] = \frac{1}{m} \sum\limits_{i=1}^m \left(\sum\limits_{j=1}^n x_{ij}a_{kj} \right)^2 </math>

(поскольку данные центрированы, выборочная дисперсия здесь совпадает со средним квадратом уклонения от нуля).

Формально, если <math>A=\left \{a_1,...,a_n \right \}^T\in\mathbb{R}^{n \times n}</math>, <math>a_k\in\mathbb{R}^n</math> — искомое преобразование, то для векторов <math>a_k</math> должны выполняться следующие условия:

  • <math>a_1 = \underset{\Vert a_1 \Vert =1}{\operatorname{argmax}}\,S^2_m \left [(X, a_1) \right ];</math>
Если решение не единственно, то выбираем одно из них.
  • Вычитаем из данных проекцию на первую главную компоненту:
<math>x_i := x_i - a_1 \left(a_1,x_i\right) </math>; в результате <math>x_i \bot a_1</math>;
  • находим вторую главную компоненту как решение задачи
<math>a_2 = \underset{\Vert a_2 \Vert =1}{\operatorname{argmax}}\,S^2_m \left [ (X, a_2) \right ];</math>
Если решение не единственно, то выбираем одно из них.
  • Вычитаем проекцию на <math>(k-1)</math>-ю главную компоненту (напомним, что проекции на предшествующие <math>k-2</math> главные компоненты уже вычтены):
<math>x_i := x_i - a_{k-1} \left(a_{k-1},x_i\right) </math>; в результате <math>x_i \bot a_l, (l = 1, \dots, k-1)</math>;
  • находим <math>k</math>-ю главную компоненту как решение задачи
<math>a_n = \underset{\Vert a_k\Vert = 1}{\operatorname{argmax}}\,S^2_m \left [ (X, a_k) \right ];</math>
Если решение не единственно, то выбираем одно из них.

Фактически, как и для задачи аппроксимации, на каждом шаге решается задача о первой главной компоненте для данных, из которых вычтены проекции на все ранее найденные главные компоненты. При большом числе итерации (большая размерность, много главных компонент) отклонения от ортогональности накапливаются и может потребоваться специальная коррекция алгоритма или другой алгоритм поиска собственных векторов ковариационной матрицы.

Решение задачи о наилучшей аппроксимации даёт то же множество решений <math>\left\{a_i\right\}</math>, что и поиск ортогональных проекций с наибольшим рассеянием, по очень простой причине: <math>\Vert x_i - a_k (a_k,x_i)\Vert ^2 = \Vert x_i\Vert ^2 - (a_k,x_i)^2, </math> и первое слагаемое не зависит от <math> a_k</math>. Только одно дополнение к задаче об аппроксимации: появляется последняя главная компонента <math> a_n.</math>

Поиск ортогональных проекций с наибольшим среднеквадратичным расстоянием между точками

Ещё одна эквивалентная формулировка следует из очевидного тождества, верного для любых <math>m</math> векторов <math> x_i</math>:

<math>\frac{1}{m(m-1)}\sum_{i,j=1}^m (x_i-x_j)^2 =\frac{2m^2}{m(m-1)}\left[\frac{1}{m}\sum_{i=1}^m x_i^2 - \left(\frac{1}{m}\sum_{i}^m x_i \right)^2\right].</math>

В левой части этого тождества стоит среднеквадратичное расстояние между точками, а в квадратных скобках справа — выборочная дисперсия. Таким образом, в методе главных компонент ищутся подпространства, в проекции на которые среднеквадратичное расстояние между точками максимально. Такая переформулировка позволяет строить обобщения с взвешиванием различных парных расстояний (а не только точек).

Аннулирование корреляций между координатами

Для заданной <math> n</math>-мерной случайной величины <math> X</math> найти такой ортонормированный базис, <math>\left\{a_1,..., a_n \right\}</math>, в котором коэффициент ковариации между различными координатами равен нулю. После преобразования к этому базису

<math>\operatorname{cov}(X_i,X_j)=0</math> для <math>i \neq j </math>.

Здесь <math> \operatorname{cov}(X_i,X_j)= \operatorname{E}[(X_i-\overline{X_i})(X_j-\overline{X_j})] </math> — коэффициент ковариации.

Диагонализация ковариационной матрицы

Все задачи о главных компонентах приводят к задаче диагонализации ковариационной матрицы или выборочной ковариационной матрицы. Эмпирическая или выборочная ковариационная матрица, это

<math>C = [c_{ij}],\ c_{ij} = \frac{1}{m} \sum_{l=1}^m (x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}).</math>

Ковариационная матрица многомерной случайной величины <math> X</math>, это

<math>\Sigma = [\sigma_{ij}],\ \sigma_{ij} = \operatorname{cov}(X_i,X_j)=E[(X_i-\overline{X_i})(X_j-\overline{X_j})].</math>

Векторы главных компонент для задач о наилучшей аппроксимации и о поиске ортогональных проекций с наибольшим рассеянием — это ортонормированный набор <math> \left\{a_1,..., a_n \right\}</math> собственных векторов эмпирической ковариационной матрицы <math>C</math>, расположенных в порядке убывания собственных значений <math>\lambda: \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_n \ge 0. </math> Эти векторы служат оценкой для собственных векторов ковариационной матрицы <math>\operatorname{cov}(X_i,X_j) </math>. В базисе из собственных векторов ковариационной матрицы она, естественно, диагональна, и в этом базисе коэффициент ковариации между различными координатами равен нулю.

Если спектр ковариационной матрицы вырожден, то выбирают произвольный ортонормированный базис собственных векторов. Он существует всегда, а собственные числа ковариационной матрицы всегда вещественны и неотрицательны.

Сингулярное разложение матрицы данных

Идея сингулярного разложения

Математическое содержание метода главных компонент — это спектральное разложение ковариационной матрицы <math> C </math>, то есть представление пространства данных в виде суммы взаимно ортогональных собственных подпространств <math> C </math>, а самой матрицы <math> C </math> — в виде линейной комбинации ортогональных проекторов на эти подпространства с коэффициентами <math> \lambda_i </math>. Если <math>\operatorname{X}=\left\{x_1,..., x_m \right\}^T</math> — матрица, составленная из векторов-строк центрированных данных, то <math> C = \operatorname{X}^T\operatorname{X}</math> и задача о спектральном разложении ковариационной матрицы <math> C </math> превращается в задачу о сингулярном разложении (Шаблон:Lang-en) матрицы данных <math>\operatorname{X}</math>.

Число <math> \sigma \geq 0 </math> называется сингулярным числом матрицы <math>\operatorname{X}</math> тогда и только тогда, когда существуют правый и левый сингулярные векторы: такие <math>m</math>-мерный вектор-строка <math>b_{\sigma}</math> и <math>n</math>-мерный вектор-столбец <math>a_{\sigma}</math> (оба единичной длины), что выполнено два равенства:

<math>\operatorname{X} a_{\sigma} = \sigma b_{\sigma}^T ;\, \, b_{\sigma} \operatorname{X}= \sigma a_{\sigma}^T.</math>

Пусть <math>p= \operatorname{rang} \operatorname{X} \leq \min\{n,m\}</math> — ранг матрицы данных. Сингулярное разложение матрицы данных <math>\operatorname{X}</math> — это её представление в виде

<math>\operatorname{X}= \sum_{l=1}^p \sigma_l b_l^T a_l^T ; \;\operatorname{X}^T= \sum_{l=1}^p \sigma_l a_l b_l \; \left(x_{ij}=\sum_{l=1}^p \sigma_l b_{li}a_{lj}\right),</math>

где <math>\sigma_l > 0</math> — сингулярное число, <math>a_l=(a_{li}), \, i=1,... n</math> — соответствующий правый сингулярный вектор-столбец, а <math>b_l=(b_{li}), \, i=1,... m</math> — соответствующий левый сингулярный вектор-строка (<math>l=1,...p</math>). Правые сингулярные векторы-столбцы <math>a_l</math>, участвующие в этом разложении, являются векторами главных компонент и собственными векторами эмпирической ковариационной матрицы <math>C =\operatorname{X} ^T \operatorname{X} </math>, отвечающими положительным собственным числам <math> \lambda_l=\sigma_l^2 > 0 </math>.

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

Теория сингулярного разложения была создана Дж. Дж. Сильвестром (Шаблон:Lang-en) в 1889 г. и изложена во всех подробных руководствах по теории матриц [1].

Простой итерационный алгоритм сингулярного разложения

Основная процедура — поиск наилучшего приближения произвольной <math>m \times n</math> матрицы <math>X=(x_{ij})</math> матрицей вида <math>b \otimes a = (b_i a_j)</math> (где <math>b</math> — <math>m</math>-мерный вектор, а <math>a</math> — <math>n</math>-мерный вектор) методом наименьших квадратов:

<math>F(b, a) = \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^n (x_{ij} - b_i a_j )^2 \to \min</math>

Решение этой задачи дается последовательными итерациями по явным формулам. При фиксированном векторе <math>a=(a_j) </math> значения <math>b=(b_i) </math>, доставляющие минимум форме <math>F(b, a) </math>, однозначно и явно определяются из равенств <math>\partial F/ \partial b_i = 0</math> :

<math>\frac{\partial F}{\partial b_i} = - \sum_{j=1}^n (x_{ij} - b_i a_j )a_j = 0; \;\; b_i = \frac{\sum_{j=1}^n x_{ij} a_j}{\sum_{j=1}^n a_j^2 }\, . </math>

Аналогично, при фиксированном векторе <math>b =(b_ i) </math> определяются значения <math>a=(a_j) </math>:

<math>a_j = \frac{\sum_{i=1}^m b_i x_{ij} }{\sum_{i =1}^m b_i ^2 }\, . </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+... +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>).

К достоинствам этого алгоритма относится его исключительная простота и возможность почти без изменений перенести его на данные с пробелами[1], а также взвешенные данные.

Существуют различные модификации базового алгоритма, улучшающие точность и устойчивость. Например, векторы главных компонент <math>a^l</math> при разных <math>l</math> должны быть ортогональны «по построению», однако при большом числе итерации (большая размерность, много компонент) малые отклонения от ортогональности накапливаются и может потребоваться специальная коррекция <math>a^l</math> на каждом шаге, обеспечивающая его ортогональность ранее найденным главным компонентам.

Для квадратных симметричных положительно определённых матриц описанный алгоритм превращается в метод прямых итераций для поиска собственных векторов (см. статью Собственные векторы, значения и пространства).

Матрица преобразования к главным компонентам

Матрица <math>A</math> преобразования данных к главным компонентам строится из векторов главных компонент: <math>A=\left \{a_1,...,a_n \right \}^T</math>. Здесь <math> a_i</math> — ортонормированные векторы-столбцы главных компонент, расположенные в порядке убывания собственных значений, верхний индекс <math> T</math> означает транспонирование. Матрица <math>A</math> является ортогональной: <math>A A^T=1</math>.

После преобразования большая часть вариации данных будет сосредоточена в первых координатах, что даёт возможность отбросить оставшиеся и рассмотреть пространство уменьшенной размерности.

Остаточная дисперсия

Пусть данные центрированы, <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 ... \ge \lambda_n \ge 0</math> собственные значения эмпирической ковариационной матрицы <math>C</math>, расположенные в порядке убывания, с учетом кратности.

Эта величина называется остаточной дисперсией. Величина

<math>\frac{1}{m} \sum_{i=1}^m \left\Vert \sum_{j=1}^k a_j (a_j, x_i) \right \Vert ^2=

\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}+...+\lambda_{n}}{\lambda_{1}+\lambda_{2}+...+\lambda_{n}}.</math>

По относительной ошибке <math> \delta_k</math> оценивается применимость метода главных компонент с проецированием на первые <math> k</math> компонент.

Замечание: в большинстве вычислительных алгоритмов собственные числа <math> \lambda_i</math> с соответствуюшими собственными векторами — главными компонентами <math> a_i</math> вычисляются в порядке «от больших <math> \lambda_i</math> — к меньшим». Для вычисления <math> \delta_k</math> достаточно вычислить первые <math> k</math> собственных чисел и след эмпирической ковариационной матрицы <math>C</math>, <math>\operatorname{tr} C</math> (сумму диагональных элементов <math>C</math>, то есть дисперсий по осям). Тогда

<math>\delta^2_k=\frac{1}{\operatorname{tr} C}\left(\operatorname{tr} C -\sum_{i=1}^k \lambda_{i}\right).</math>

Нормировка

Нормировка после приведения к главным компонентам

После проецирования на первые <math> k</math> главных компонент с <math>\lambda_1 \ge \lambda_2 \ge ... \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> главных компонент вместе с нормировкой задается матрицей

<math>K=\left \{\frac{a_1}{\sqrt{ \lambda_1}},\frac{a_2}{\sqrt{ \lambda_2}},...,\frac{a_k}{\sqrt{ \lambda_k}} \right \}^T</math>.

Именно это преобразование чаще всего называется преобразованием Кархунена-Лоэва. Здесь <math> a_i</math> — векторы-столбцы, а верхний индекс <math> T</math> означает транспонирование.

Нормировка до вычисления главных компонент

Предупреждение: не следует путать нормировку, проводимую после преобразования к главным компонентам, с нормировкой и «обезразмериванием» при предобработке данных, проводимой до вычисления главных компонент. Предварительная нормировка нужна для обоснованного выбора метрики, в которой будет вычисляться наилучшая аппроксимация денных, или будут искаться направления наибольшего разброса (что эквивалентно). Например, если данные представляют собой трёхмерные векторы из «метров, литров и килограмм», то при использовании стандартного евклидового расстояния разница в 1 метр по первой координате будет вносить тот же вклад, что разница в 1 литр по второй, или в 1 кг по третьей. Обычно системы единиц, в которых представлены исходные данные, недостаточно точно отображают наши представления о естественных масштабах по осям, и проводится «обезразмеривание»: каждая координата делится на некоторый масштаб, определяемый данными, целями их обработки и процессами измерения и сбора данных.

Есть три cущественно различных стандартных подхода к такой нормировке: на единичную дисперсию по осям (масштабы по осям равны средним квадратичным уклонениям — после этого преобразования ковариационная матрица совпадает с матрицей коэффициентов корреляции), на равную точность измерения (масштаб по оси пропорционален точности измерения данной величины) и на равные требования в задаче (масштаб по оси определяется требуемой точностью прогноза данной величины или допустимым её искажением — уровнем толерантности). На выбор предобработки влияют содержательная постановка задачи, а также условия сбора данных (например, если коллекция данных принципиально не завершена и данные будут ещё поступать, то нерационально выбирать нормировку строго на единичную дисперсию, даже если это соответствует смыслу задачи, поскольку это предполагает перенормировку всех данных после получения новой порции; разумнее выбрать некоторый масштаб, грубо оценивающий стандартное отклонение, и далее его не менять).

Предварительная нормировка на единичную дисперсию по осям разрушается поворотом системы координат, если оси не являются главными компонентами, и нормировка при предобработке данных не заменяет нормировку после приведения к главным компонентам.

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

Если сопоставить каждому вектору данных единичную массу, то эмпирическая ковариационная матрица <math> C</math> совпадёт с тензором инерции этой системы точечных масс (делённым на полную массу <math> m</math>), а задача о главных компонентых — с задачей приведения тензора инерции к главным осям. Можно использовать дополнительную свободу в выборе значений масс для учета важности точек данных или надежности их значений (важным данным или данным из более надежных источников приписываются бо́льшие массы). Если вектору данных <math> x_l</math> придаётся масса <math> w_l</math>, то вместо эмпирической ковариационной матрицы <math> C</math> получим

<math>C^w = [c^w_{ij}],\ c^w_{ij} = \frac{1}{\sum_{l} w_l} \sum_{l=1}^m w_l(x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}).</math>

Все дальнейшие операции по приведению к главным компонентам производятся так же, как и в основной версии метода: ищем ортонормированный собственный базис <math> C^w</math>, упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми <math> k</math> компонентами (по суммам собственных чисел <math> C^w</math>), нормируем и т. п.

Более общий способ взвешивания даёт максимизация взвешенной суммы попарных расстояний[1] между проекциями. Для каждых двух точек данных, <math>x_l , \ x_q</math> вводится вес <math>d_{lq}</math>; <math>d_{lq}=d_{ql}</math> и <math>d_{l}=\sum_{q=1}^m d_{lq}</math>. Вместо эмпирической ковариационной матрицы <math> C</math> используется

<math>C^d = [c^d_{ij}],\ c^d_{ij} =\sum_{l=1}^m d_l (x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}) -\sum_{l \neq q, \ l,q=1}^m d_{lq}(x_{li} - \overline{X_{i}})(x_{qj}- \overline{X_{j}}).</math>

При <math>d_{lq}>0</math> симметричная матрица <math>C^d</math> положительно определена, поскольку положительна квадратичная форма:

<math>\sum_{ij} c^d_{ij}a_i a_j = \frac{1}{2}\sum_{lq}d_{lq}\left(\sum_ia_i(x_{li}-x_{qi})\right)^2.</math>

Далее ищем ортонормированный собственный базис <math> C^d</math>, упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми <math> k</math> компонентами и т. д. — в точности так же, как и в основном алгоритме.

Этот способ применяется при наличии классов: для <math>x_l , \ x_q</math> из разных классов вес <math>d_{lq}</math> вес выбирается бо́льшим, чем для точек одного класса. В результате, в проекции на взвешенные главные компоненты различные классы «раздвигаются» на большее расстояние.

Другое применение — снижение влияния больших уклонений (оутлайеров, Шаблон:Lang-en), которые могут искажать картину из-за использования среднеквадратичного расстояния: если выбрать <math>d_{lq}=1/ \| x_l -x_q \|</math>, то влияние больших уклонений будет уменьшено. Таким образом, описанная модификация метода главных компонент является более робастной, чем классическая.

Специальная терминология

В статистике при использовании метода главных компонент используют несколько специальных терминов.

Матрица данных <math>\mathbf{X}=\{x_1,... x_m\}^T</math>; каждая строка — вектор предобработанных данных (центрированных и правильно нормированных), число строк — <math>m</math> (количество векторов данных), число столбцов — <math>n</math> (размерность пространства данных);

Матрица нагрузок (Loadings) <math>\mathbf{P}=\{a_1,... a_k\}</math>; каждый столбец — вектор главных компонент, число строк — <math>n</math> (размерность пространства данных), число столбцов — <math>k</math> (количество векторов главных компонент, выбранных для проецирования);

Матрица счетов (Scores) <math>\mathbf{T}=[t_{ij}]; \; t_{ij}=(x_i,a_j)</math>; каждая строка — проекция вектора данных на <math>k</math> главных компонент; число строк — <math>m</math> (количество векторов данных), число столбцов — <math>k</math> (количество векторов главных компонент, выбранных для проецирования);

Матрица Z-счетов (Z-scores) <math>\mathbf{Z}=[z_{ij}]; \; z_{ij}=\frac{(x_i,a_j)}{\sqrt{ \lambda_j}}</math>; каждая строка — проекция вектора данных на <math>k</math> главных компонент, нормированная на единичную выборочную дисперсию; число строк — <math>m</math> (количество векторов данных), число столбцов — <math>k</math> (количество векторов главных компонент, выбранных для проецирования);

Матрица ошибок (или остатков) (Errors or residuals) <math>\mathbf{E}=\mathbf{X}-\mathbf{T}\mathbf{P}^T</math>.

Основная формула: <math>\mathbf{X}=\mathbf{T}\mathbf{P}^T+\mathbf{E}.</math>

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

Построение ветвящихся главных компонент методом топологических грамматик. Крестики — точки данных, красное дерево с желтыми узлами — аппроксимирующий дендрит.
Построение ветвящихся главных компонент методом топологических грамматик. Крестики — точки данных, красное дерево с желтыми узлами — аппроксимирующий дендрит[1].

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

Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность <math> \delta_k</math>. Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности. Для работы с такими «кривыми» главными компонентами изобретен метод главных многообразий[1] и различные версии нелинейного метода главных компонент[1][1]. Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например самоорганизующиеся карты Кохонена, нейронный газ[1] или топологические грамматики[1]. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к независимым компонентам[1], которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.

Примеры использования

Компрессия изображений и видео

Для уменьшения пространственной избыточности пикселей при кодировании изображений и видео используется линейные преобразования блоков пикселей. Последующие квантования полученных коэффициентов и кодирование без потерь позволяют получить значительные коэффициенты сжатия. Использование преобразования PCA в качестве линейного преобразования является для некоторых типов данных оптимальным с точки зрения размера полученных данных при одинаковом искажении [1]. На данный момент этот метод активно не используется, в основном из-за большой вычислительной сложности. Также сжатия данных можно достичь отбрасывая последние коэффициенты преобразования.

Подавление шума на изображениях [1]

Основная суть метода — при удалении шума из блока пикселей представить окрестность этого блока в виде набора точек в многомерном пространстве, применить к нему PCA и оставить только первые компоненты преобразования. При этом предполагается, что в первых компонентах содержится основная полезная информация, оставшиеся же компоненты содержат ненужный шум. Применив обратное преобразование после редукции базиса главных компонент, мы получим изображение без шума.

Индексация видео

Основная идея — представить при помощи PCA каждый кадр видео несколькими значениями, которые в дальнейшем будут использоваться при построении базы данных и запросам к ней. Столь существенная редукция данных позволяет значительно увеличить скорость работы и устойчивость к ряду искажений в видео.

Биоинформатика

Рис. А. Проекция ДНК-блуждания на первые 2 главные компоненты для генома бактерии Streptomyces coelicolor
Рис. А. Проекция ДНК-блуждания на первые 2 главные компоненты для генома бактерии Streptomyces coelicolor
Рис. Б. Проекция ДНК-блуждания на первые 3 главные компоненты для генома бактерии Streptomyces coelicolor. Вращение применяется для визуализации трехмерной конфигурации
Рис. Б. Проекция ДНК-блуждания на первые 3 главные компоненты для генома бактерии Streptomyces coelicolor. Вращение применяется для визуализации трехмерной конфигурации

Метод главных компонент интенсивно используется в биоинформатике для сокращения размерности описания, выделения значимой информации, визуализации данных и др. Один из распространнённых вариантов использования — анализ соответствий (Шаблон:Lang-en) [1]. На иллюстрациях (Рис. А, Б) генетический текст (см. статью Трансляция (биология)) представлен как множество точек в 64-мерном пространстве частот триплетов. Каждая точка соответствует фрагменту ДНК в скользящем окне длиной 300 нуклеотидов (ДНК-блуждание). Этот фрагмент разбивается на неперекрывающиеся триплеты, начиная с первой позиции. Относительные частоты этих триплетов в фрагменте и составляют 64-мерный вектор. На Рис. А представлена проекция на первые 2 главные компоненты для генома бактерии Streptomyces coelicolor. На Рис. Б представлена проекция на первые 3 главные комроненты. Оттенками красного и коричневого выделены фрагменты кодирующих последовательностей в прямой цепи ДНК, а оттенками зеленого выделены фрагменты кодирующих последовательностей в обратной цепи ДНК. Черным помечены фрагменты, принадлежащие некодирующей части. Анализ методом главных компонент большинства известных бактериальных геномов представлен на специализированном сайте[1].

Хемометрика

Метод главных компонент — один из основных методов в хемометрике (Шаблон:Lang-en). Позволяет разделить матрицу исходных данных X на две части: «содержательную» и «шум». По наиболее популярному определению [1] «Хемометрика — это химическая дисциплина, применяющая математические, статистические и другие методы, основанные на формальной логике, для построения или отбора оптимальных методов измерения и планов эксперимента, а также для извлечения наиболее важной информации при анализе экспериментальных данных».

Психодиагностика

Психодиагностика является одной из наиболее разработанных областей приложения метода главных компонент [1]. Стратегия использования основывается на гипотезе об автоинформативности экспериментальных данных, которая подразумевает, что диагностическую модель можно создать путем аппроксимации геометрической структуры множества объектов в пространстве исходных признаков. Хорошую линейную диагностическую модель удается построить, когда значительная часть исходных признаков внутренне согласованна. Если эта внутренняя согласованность отражает искомый психологический конструкт, то параметры линейной диагностической модели (веса признаков) дает метод главных компонент.

Общественные науки

Метод главных компонент — один из основных инструментов эконометрики. Он применяется для: (1) наглядного представления данных; (2) обеспечения лаконизма моделей, упрощения счета и интерпретации; (3) сжатия объемов хранимой информации. Метод обеспечивает максимальную информативность и минимальное искажение геометрической структуры исходных данных. В социологии метод небходим для решения первых двух основных задач[1]: (1) анализ данных (описание результатов опросов или других исследований, представленных в виде массивов числовых данных); (2) описание социальных явлений (построение моделей явлений, в том числе и математических моделей). В политологии метод главных компонент был основным инструментом проекта «Политический Атлас Современности»[1] для линейного и нелинейного анализа рейтингов 192 стран мира по пяти специально разработанным интегральным индексам (уровня жизни, международного влияния, угроз, государственности и демократии). Для картографии результатов этого анализа разработана специальная ГИС (Геоинформационная система), объединяющая географическое пространство с пространством признаков.

Сокращение размерности динамических моделей

Проклятие размерности (Шаблон:Lang-en) затрудняет моделирование сложных систем. Сокращение размерности модели — необходимое условие успеха моделирования. Для достижения этой цели создана разветвленная математическая технология. Метод главных компонент также используется в этих задачах (часто под названием истинное или собственное ортогональное разложениеШаблон:Lang-en). Например, при описании динамики турбулентности динамические переменные — поле скоростей — принадлежат бесконечномерному пространству (или, если предствлять поле его значениями на достаточно мелкой сетке, — конечномерному пространству большой размерности). Можно набрать большую коллекцию мгновенных значений полей и применить к этому множеству многомерных «векторов данных» метод главных компонент. Эти главные компоненты называются также эмпирические собственные векторы. В некоторых случаях (структурная турбулентность) метод дает впечатляющее сокращение размерности[1] Другие области применения этой техники сокращения динамических моделей чрезвычайно разнообразны — от теоретических основ химической технологии (Шаблон:Lang-en) до океанологии и климатологии.

Литература

Классические работы

  • Pearson K., On lines and planes of closest fit to systems of points in space, Philosophical Magazine, (1901) 2, 559—572; а также на сайте PCA.
  • Sylvester J.J., On the reduction of a bilinear quantic of the nth order to the form of a sum of n products by a double orthogonal substitution, Messenger of Mathematics, 19 (1889), 42—46; а также на сайте PCA.
  • Frećhet M. Les élements aléatoires de nature quelconque dans un espace distancié. Ann. Inst. H. Poincaré, 10 (1948), 215—310.

Основные руководства (стандарт де-факто)

  • Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика. Классификация и снижение размерности.— М.: Финансы и статистика, 1989.— 607 с.
  • Jolliffe I.T. Principal Component Analysis, Series: Springer Series in Statistics, 2nd ed., Springer, NY, 2002, XXIX, 487 p. 28 illus. ISBN 978-0-387-95442-4

Сборник современных обзоров

Ссылки

Примечания

Шаблон:Reflist

Личные инструменты