Метод главных компонент - Сингулярное разложение матрицы данных

Интернет магазин китайских планшетных компьютеров

Компьютеры - Метод главных компонент - Сингулярное разложение матрицы данных

22 января 2011

Оглавление:
1. Метод главных компонент
2. Формальная постановка задачи
3. Диагонализация ковариационной матрицы
4. Сингулярное разложение матрицы данных
5. Матрица преобразования к главным компонентам
6. Отбор главных компонент по правилу Кайзера
7. Оценка числа главных компонент по правилу сломанной трости
8. Нормировка
9. Механическая аналогия и метод главных компонент для взвешенных данных
10. Специальная терминология
11. Примеры использования

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

Математическое содержание метода главных компонент — это спектральное разложение ковариационной матрицы C, то есть представление пространства данных в виде суммы взаимно ортогональных собственных подпространств C, а самой матрицы C — в виде линейной комбинации ортогональных проекторов на эти подпространства с коэффициентами λ_i. Если $\operatorname{X}=\left\{x_1,..., x_m \right\}$ — матрица, составленная из векторов-столбцов центрированных данных, то $C =\frac{1}{m-1} \operatorname{X}^T\operatorname{X}$ и задача о спектральном разложении ковариационной матрицы C превращается в задачу о сингулярном разложении матрицы данных $\operatorname{X}$ .

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

$\operatorname{X} a_{\sigma} = \sigma b_{\sigma}^T ;\, \, b_{\sigma} \operatorname{X}= \sigma a_{\sigma}^T.$

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

$\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,$

где σ_l > 0 — сингулярное число, $a_l=, \, i=1,... n$ — соответствующий правый сингулярный вектор-столбец, а $b_l=, \, i=1,... m$ — соответствующий левый сингулярный вектор-строка. Правые сингулярные векторы-столбцы a_l, участвующие в этом разложении, являются векторами главных компонент и собственными векторами эмпирической ковариационной матрицы $C =\frac{1}{m-1}\operatorname{X} ^T \operatorname{X}$ , отвечающими положительным собственным числам $\lambda_l=\frac{1}{m-1}\sigma_l^2 > 0$ .

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

Теория сингулярного разложения была создана Дж. Дж. Сильвестром в 1889 г. и изложена во всех подробных руководствах по теории матриц .

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

Основная процедура — поиск наилучшего приближения произвольной $m \times n$ матрицы X = матрицей вида $b \otimes a =$ методом наименьших квадратов:

$F = \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^n^2 \to \min$

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

$\frac{\partial F}{\partial b_i} = - \sum_{j=1}^na_j = 0; \;\; b_i = \frac{\sum_{j=1}^n x_{ij} a_j}{\sum_{j=1}^n a_j^2 }\, .$

Аналогично, при фиксированном векторе b = определяются значения a =:

$a_j = \frac{\sum_{i=1}^m b_i x_{ij} }{\sum_{i =1}^m b_i ^2 }\, .$

B качестве начального приближения вектора a возьмем случайный вектор единичной длины, вычисляем вектор b, далее для этого вектора b вычисляем вектор a и т. д. Каждый шаг уменьшает значение F. В качестве критерия остановки используется малость относительного уменьшения значения минимизируемого функционала F за шаг итерации или малость самого значения F.

В результате для матрицы X = получили наилучшее приближение матрицей P₁ вида $b^1 \otimes a^1 =$ . Далее, из матрицы X вычитаем полученную матрицу P₁, и для полученной матрицы уклонений X₁ = X − P₁ вновь ищем наилучшее приближение P₂ этого же вида и т. д., пока, например, норма X_k не станет достаточно малой. В результате получили итерационную процедуру разложения матрицы X в виде суммы матриц ранга 1, то есть $X=P_1+P_2+... +P_q \;$ . Полагаем $\sigma_l = \|a^l\| \|b^l\|$ и нормируем векторы $a^l \, , \, b^l$ : $a^l:= a^l/ \| a^l\|; \, \, b^l:= b^l/ \| b^l\|.$ В результате получена аппроксимация сингулярных чисел σ_l и сингулярных векторов.

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

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

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

Сингулярное разложение тензоров и тензорный метод главных компонент

Часто вектор данных имеет дополнительную структуру прямоугольной таблицы или даже многомерной таблицы — то есть тензора: $x_{i_{1}i_{2}...i_{q}}$ , $1 \leq i_{j} \leq n_j$ . В этом случае также эффективно применять сингулярное разложение. Определение, основные формулы и алгоритмы переносятся практически без изменений: вместо матрицы данных имеем q + 1-индексную величину $\operatorname{X}=$ , где первый индекс i₀-номер точки данных.

Основная процедура — поиск наилучшего приближения тензора $x_{i_{0}i_{1}i_{2}...i_{q}}$ тензором вида $a^0_{i_{0}} a^1_{i_{1}}a^2_{i_{2}}...a^q_{i_{q}}$ " src="http://upload.wikimedia.org/math/0/d/d/0dd71a561a8ee7d34bca45721a95490e.png" /> — m-мерный вектор, $a^l=$ — вектор размерности n_l при l > 0) методом наименьших квадратов:

$F= \frac{1}{2}\sum_{i_{0}=1}^m \sum_{i_{1}=1}^{n_1}...\sum_{i_{q}=1}^{n_q}^2 \to \min$

Решение этой задачи дается последовательными итерациями по явным формулам. Если заданы все векторы-сомножители кроме одного $a^k_{i_{k}}$ , то этот оставшийся определяется явно из достаточных условий минимума.

$a^k_{i_{k}}= \frac{\sum_{i_{0}=1}^m \sum_{i_{1}=1}^{n_1}...\sum_{i_{k-1}=1}^{n_{k-1}}\sum_{i_{k+1}=1}^{n_{k+1}}...\sum_{i_{q}=1}^{n_{q}} x_{i_{0}i_{1}...i_{k-1}i_{k}i_{k+1}...i_{q}} a^0_{i_{0}} a^{k-1}_{i_{k-1}}a^{k+1}_{i_{k+1}}...a^q_{i_{q}}}{\prod_{j\neq k} \|a^j\|^2 }\, .$

B качестве начального приближения векторов $a^l=$ возьмем случайные векторы единичной длины, вычислим вектор a, далее для этого вектора a и данных векторов a,a,...вычисляем вектор a и т. д. Каждый шаг уменьшает значение F. Алгоритм, очевидно, сходится. В качестве критерия остановки используется малость относительного уменьшения значения минимизируемого функционала F за цикл или малость самого значения F. Далее, из тензора $\operatorname {X}$ вычитаем полученное приближение $a^0_{i_{0}} a^1_{i_{1}}a^2_{i_{2}}...a^q_{i_{q}}$ и для остатка вновь ищем наилучшее приближение этого же вида и т. д., пока, например, норма очередного остатка не станет достаточно малой.

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

<<< Инфографика

Нейронная сеть Кохонена >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие