Метод главных компонент () — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретён Карлом Пирсоном в 1901 году. Применяется во многих областях, в том числе в эконометрике, биоинформатике, обработке изображений, для сжатия данных, в общественных науках.
Вычисление главных компонент может быть сведено к вычислению сингулярного разложения матрицы данных или к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных. Иногда метод главных компонент называют преобразованием Кархунена — ЛоэваФактически, метод является эмпирической реализацией теоремы Кархунена — Лоэва, согласно которой любой случайный процесс может быть представлен в виде бесконечного ряда ортогональных функций. В русскоязычной научной литературе распространено также написание «преобразование Карунена — Лоэва», соответствующее английскому прочтению финской фамилии или преобразованием Хотеллинга ().
Формальная постановка задачи Задача анализа главных компонент имеет, как минимум, четыре базовые версии: аппроксимировать данные линейными многообразиями меньшей размерности; найти подпространства меньшей размерности, в ортогональной проекции на которые разброс данных (то есть среднеквадратичное отклонение от среднего значения) максимален; найти подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально; для данной многомерной случайной величины построить такое ортогональное преобразование координат, в результате которого корреляции между отдельными координатами обратятся в нуль.
Первые три версии оперируют конечными множествами данных. Они эквивалентны и не используют никакой гипотезы о статистическом порождении данных. Четвёртая версия оперирует случайными величинами. Конечные множества появляются здесь как выборки из данного распределения, а решение трёх первых задач — как приближение к разложению по теореме Кархунена — Лоэва («истинному преобразованию Кархунена — Лоэва»). При этом возникает дополнительный и не вполне тривиальный вопрос о точности этого приближения.
Аппроксимация данных линейными многообразиями
Метод главных компонент начинался с задачи наилучшей аппроксимации конечного множества точек прямыми и плоскостями (Пирсон, 1901). Дано конечное множество векторов , для каждого среди всех -мерных линейных многообразий в найти такое , что сумма квадратов уклонений от минимальна: ,
где — евклидово расстояние от точки до линейного многообразия. Всякое -мерное линейное многообразие в может быть задано как множество линейных комбинаций , где параметры пробегают вещественную прямую , а — ортонормированный набор векторов , где евклидова норма, — евклидово скалярное произведение, или в координатной форме: .
Решение задачи аппроксимации для даётся набором вложенных линейных многообразий , . Эти линейные многообразия определяются ортонормированным набором векторов (векторами главных компонент) и вектором . Вектор ищется как решение задачи минимизации для :
,
то есть
.
Это — выборочное среднее: .
Фреше в 1948 году обратил внимание, что вариационное определение среднего (как точки, минимизирующей сумму квадратов расстояний до точек данных) очень удобно для построения статистики в произвольном метрическом пространстве, и построил обобщение классической статистики для общих пространств (обобщённый метод наименьших квадратов).
Векторы главных компонент могут быть найдены как решения однотипных задач оптимизации: Централизуются данные (вычитанием среднего): . Теперь ; Отыскивается первая главная компонента как решение задачи: . если решение не единственно, то осуществляется выбор одного из них. Из данных вычитается проекция на первую главную компоненту: ; Отыскивается вторая главная компонента как решение задачи: . Если решение не единственно, то выбирается одно из них. Далее процесс продолжается, то есть на шаге вычитается проекция на -ю главную компоненту (к этому моменту проекции на предшествующие главные компоненты уже вычтены): ; и на шаге определяется -я главная компонента как решение задачи: (если решение не единственно, то выбирается одно из них).
На каждом подготовительном шаге вычитается проекция на предшествующую главную компоненту. Найденные векторы ортонормированы просто в результате решения описанной задачи оптимизации, однако чтобы не дать ошибкам вычисления нарушить взаимную ортогональность векторов главных компонент, можно включать в условия задачи оптимизации.
Неединственность в определении помимо тривиального произвола в выборе знака ( и решают ту же задачу) может быть более существенной и происходить, например, из условий симметрии данных. Последняя главная компонента — единичный вектор, ортогональный всем предыдущим .
Поиск ортогональных проекций с наибольшим рассеянием
Пусть нам дан центрированный набор векторов данных (среднее арифметическое значение равно нулю). Задача — найти такое ортогональное преобразование в новую систему координат, для которого были бы верны следующие условия: Выборочная дисперсия данных вдоль первой координаты максимальна (эту координату называют первой главной компонентой); Выборочная дисперсия данных вдоль второй координаты максимальна при условии ортогональности первой координате (вторая главная компонента); … Выборочная дисперсия данных вдоль значений -ой координаты максимальна при условии ортогональности первым координатам; …
Выборочная дисперсия данных вдоль направления, заданного нормированным вектором , это
(поскольку данные центрированы, выборочная дисперсия здесь совпадает со средним квадратом уклонения от нуля).
Решение задачи о наилучшей аппроксимации даёт то же множество главных компонент , что и поиск ортогональных проекций с наибольшим рассеянием, по очень простой причине: и первое слагаемое не зависит от .
Поиск ортогональных проекций с наибольшим среднеквадратичным расстоянием между точками Ещё одна эквивалентная формулировка следует из очевидного тождества, верного для любых векторов :
В левой части этого тождества стоит среднеквадратичное расстояние между точками, а в квадратных скобках справа — выборочная дисперсия. Таким образом, в методе главных компонент ищутся подпространства, в проекции на которые среднеквадратичное расстояние между точками максимально (или, что то же самое, его искажение в результате проекции минимально)Зиновьев А. Ю., Визуализация многомерных данных , Красноярск, Изд. КГТУ, 2000.. Такая переформулировка позволяет строить обобщения с взвешиванием различных парных расстояний (а не только точек).
Аннулирование корреляций между координатами Для заданной -мерной случайной величины найти такой ортонормированный базис, , в котором коэффициент ковариации между различными координатами равен нулю. После преобразования к этому базису
для .
Здесь — коэффициент ковариации, где — математическое ожидание.
Диагонализация ковариационной матрицы Все задачи о главных компонентах приводят к задаче диагонализации ковариационной матрицы или выборочной ковариационной матрицы. Эмпирическая или выборочная ковариационная матрица, это
Ковариационная матрица многомерной случайной величины , это
Векторы главных компонент для задач о наилучшей аппроксимации и о поиске ортогональных проекций с наибольшим рассеянием — это ортонормированный набор собственных векторов эмпирической ковариационной матрицы , расположенных в порядке убывания собственных значений Эти векторы служат оценкой для собственных векторов ковариационной матрицы . В базисе из собственных векторов ковариационной матрицы она, естественно, диагональна, и в этом базисе коэффициент ковариации между различными координатами равен нулю.
Если спектр ковариационной матрицы вырожден, то выбирают произвольный ортонормированный базис собственных векторов. Он существует всегда, а собственные числа ковариационной матрицы всегда вещественны и неотрицательны.
Сингулярное разложение матрицы данных
Идея сингулярного разложения Математическое содержание метода главных компонент — это спектральное разложение ковариационной матрицы , то есть представление пространства данных в виде суммы взаимно ортогональных собственных подпространств , а самой матрицы — в виде линейной комбинации ортогональных проекторов на эти подпространства с коэффициентами . Если — матрица, составленная из векторов-строк (размерности ) центрированных данных, то и задача о спектральном разложении ковариационной матрицы превращается в задачу о сингулярном разложении матрицы данных .
Число называется сингулярным числом матрицы тогда и только тогда, когда существуют правый и левый сингулярные векторы: такие -мерный вектор-строка и -мерный вектор-столбец (оба единичной длины), что выполнено два равенства:
Пусть — ранг матрицы данных. Сингулярное разложение матрицы данных — это её представление в виде
где — сингулярное число, — соответствующий правый сингулярный вектор-столбец, а — соответствующий левый сингулярный вектор-строка (). Правые сингулярные векторы-столбцы , участвующие в этом разложении, являются векторами главных компонент и собственными векторами эмпирической ковариационной матрицы , отвечающими положительным собственным числам .
Хотя формально задачи сингулярного разложения матрицы данных и спектрального разложения ковариационной матрицы совпадают, алгоритмы вычисления сингулярного разложения напрямую, без вычисления ковариационной матрицы и её спектра, более эффективны и устойчивыBau III, D., Trefethen, L. N., Numerical linear algebra , Philadelphia: Society for Industrial and Applied Mathematics, 1997. (Lecture 31) ISBN 978-0-89871-361-9.
Теория сингулярного разложения была создана Джеймсом Джозефом Сильвестром в 1889 году и изложена во всех подробных руководствах по теории матрицГантмахер Ф. Р., Теория матриц. — М.: Наука, 1966. — 576 стр..
Простой итерационный алгоритм сингулярного разложения Основная процедура — поиск наилучшего приближения произвольной матрицы матрицей вида (где — -мерный вектор, а — -мерный вектор) методом наименьших квадратов:
Решение этой задачи даётся последовательными итерациями по явным формулам. При фиксированном векторе значения , доставляющие минимум форме , однозначно и явно определяются из равенств :
Аналогично, при фиксированном векторе определяются значения :
B качестве начального приближения вектора берётся случайный вектор единичной длины, вычисляем вектор , далее для этого вектора вычисляем вектор и т. д. Каждый шаг уменьшает значение . В качестве критерия остановки используется малость относительного уменьшения значения минимизируемого функционала за шаг итерации () или малость самого значения .
В результате для матрицы получается наилучшее приближение матрицей вида (здесь верхним индексом обозначен номер приближения). Далее, из матрицы вычитается полученная матрицу , и для полученной матрицы уклонений вновь ищется наилучшее приближение этого же вида и т. д., пока, например, норма не станет достаточно малой. В результате получили итерационную процедуру разложения матрицы в виде суммы матриц ранга 1, то есть . Полагаем и нормируем векторы : В результате получена аппроксимация сингулярных чисел и сингулярных векторов (правых — и левых — ).
К достоинствам этого алгоритма относится его исключительная простота и возможность почти без изменений перенести его на данные с пробеламиРоссиев А. А.,: Итерационное моделирование неполных данных с помощью многообразий малой размерности , Изд-во СО РАН, 2005., а также взвешенные данные.
Существуют различные модификации базового алгоритма, улучшающие точность и устойчивость. Например, векторы главных компонент при разных должны быть ортогональны «по построению», однако при большом числе итерации (большая размерность, много компонент) малые отклонения от ортогональности накапливаются, и может потребоваться специальная коррекция на каждом шаге, обеспечивающая его ортогональность ранее найденным главным компонентам.