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

Метод главных компонент (PCA - Principal component analysis) - один из основных способов уменьшить размерность данных при наименьшей потере сведений. Изобретенный в 1901 г. Карлом Пирсоном он широко применяется во многих областях. Например, для сжатия данных, «компьютерного зрения», распознавания видимых образов и т.д. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных. Метод главных компонент часто называют преобразованием Кархунена-Лёве (Karhunen-Loeve transform) или преобразованием Хотеллинга (Hotelling transform). Также над этим вопросом работали математики Косамби (1943 г.), Пугачёв (1953 г.) и Обухова (1954 г.).

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

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

Рис.3 Метод главных компонент К. Пирсона (1901 г.).

На приведённом выше рисунке даны точки P_i на плоскости, p_i - расстояние от P_i до прямой AB. Ищется прямая AB, минимизирующая сумму

Метод главных компонент начинался с задачи наилучшей аппроксимации (приближения) конечного множества точек прямыми и плоскостями. Например, дано конечное множество векторов . Для каждого k = 0,1,...,n ? 1 среди всех k-мерных линейных многообразий в найти такое , что сумма квадратов уклонений x_i от L_k минимальна:

,

где ? евклидово расстояние от точки до линейного многообразия.

Всякое k-мерное линейное многообразие в может быть задано как множество линейных комбинаций , где параметры в_i пробегают вещественную прямую , а ? ортонормированный набор векторов

,

где евклидова норма, ? евклидово скалярное произведение, или в координатной форме:

.

Решение задачи аппроксимации для k = 0,1,...,n ? 1 даётся набором вложенных линейных многообразий

,

.

Эти линейные многообразия определяются ортонормированным набором векторов (векторами главных компонент) и вектором a₀. Вектор a₀ ищется, как решение задачи минимизации для L₀:

то есть

.

В итоге получается выборочное среднее:

Французский математик Морис Фреше Фреше Морис Рене (Frйchet Maurice Renй) (02.09.1878 г. - 04.06.1973 г.) - выдающийся французский математик. Трудился в области топологии и функционального анализа, теории вероятностей. Автор современных понятий о метрическом пространстве, компактности и полноте. Авт. в 1948 году обратил внимание, что вариационное определение среднего, как точки, минимизирующей сумму квадратов расстояний до точек данных, очень удобно для построения статистики в произвольном метрическом пространстве, и построил обобщение классической статистики для общих пространств, получившее название обобщённого метода наименьших квадратов.

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

1) централизуем данные (вычитаем среднее):

Теперь ;

2) находим первую главную компоненту как решение задачи;

.

Если решение не единственно, то выбираем одно из них.

3) Вычитаем из данных проекцию на первую главную компоненту:

;

4) находим вторую главную компоненту как решение задачи

.

Если решение не единственно, то выбираем одно из них.

2k-1) Вычитаем проекцию на (k ? 1)-ю главную компоненту (напомним, что проекции на предшествующие (k ? 2) главные компоненты уже вычтены):

;

2k) находим k-ю главную компоненту как решение задачи:

.

Если решение не единственно, то выбираем одно из них.

Рис. 4 Первая главная компонента и максимальная выборочная дисперсия

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

Например, пусть нам дан центрированный набор векторов данных , где среднее арифметическое значение x_i равно нулю. Задача ? найти такое отртогональное преобразование в новую систему координат, для которого были бы верны следующие условия:

1. Выборочная дисперсия данных вдоль первой координаты (главной компоненты) максимальна;

2. Выборочная дисперсия данных вдоль второй координаты (вторая главная компоненты) максимальна при условии ортогональности первой координате;

3. Выборочная дисперсия данных вдоль значений k-ой координаты максимальна при условии ортогональности первым k ? 1 координатам;

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

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

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

и первое слагаемое не зависит от a_k.

Матрица преобразования данных к главным компонентам строится из векторов «A» главных компонент:

Здесь a_i -- ортонормированные векторы-столбцы главных компонент, расположенные в порядке убывания собственных значений, верхний индекс T означает транспонирование. Матрица A является ортогональной: AA^T = 1.

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

Самым старым методом отбора главных компонент является правило Кайзера, Кайзер Иоганн Генрих Густав (Kaiser Johann Henrich Gustav, 16.03.1853 г., г.Брезно, Пруссия - 14.10.1940 г., Германия) - выдающийся немецкий математик, физик, исследователь в области спектрального анализа. Авт. по которому значимы те главные компоненты, для которых

то есть л_i превосходит среднее значение л (среднюю выборочную дисперсию координат вектора данных). Правило Кайзера хорошо работает в простых случаях, когда есть несколько главных компонент с л_i, намного превосходящими среднее значение, а остальные собственные числа меньше него. В более сложных случаях оно может давать слишком много значимых главных компонент. Если данные нормированы на единичную выборочную дисперсию по осям, то правило Кайзера приобретает особо простой вид: значимы только те главные компоненты, для которых л_i > 1.

Одним из наиболее популярных эвристических подходов к оценке числа необходимых главных компонент является правило сломанной трости, когда набор нормированных на единичную сумму собственных чисел (, i = 1,...n) сравнивается с распределением длин обломков трости единичной длины, сломанной в n ? 1-й случайно выбранной точке (точки разлома выбираются независимо и равнораспределены по длине трости). Если L_i (i = 1,...n) - длины полученных кусков трости, занумерованные в порядке убывания длины: , тогда математическое ожидание L_i:

Разберём пример, заключающийся в оценке числа главных компонент по правилу сломанной трости в размерности 5.

Рис. 5. «Правило сломанной трости» в размерности 5

По правилу сломанной трости k-й собственный вектор (в порядке убывания собственных чисел л_i) сохраняется в списке главных компонент, если

На рисунке выше приведён пример для 5-мерного случая:

l₁=(1+1/2+1/3+1/4+1/5)/5; l₂=(1/2+1/3+1/4+1/5)/5; l₃=(1/3+1/4+1/5)/5;

l₄=(1/4+1/5)/5; l₅=(1/5)/5.

Для примера выбрано

=0.5; =0.3; =0.1; =0.06; =0.04.

По правилу сломанной трости в этом примере следует оставлять 2 главных компоненты:

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

После проецирования на первые k главных компонент с удобно произвести нормировку на единичную (выборочную) дисперсию по осям. Дисперсия вдоль iй главной компоненты равна ), поэтому для нормировки надо разделить соответствующую координату на . Это преобразование не является ортогональным и не сохраняет скалярного произведения. Ковариационная матрица проекции данных после нормировки становится единичной, проекции на любые два ортогональных направления становятся независимыми величинами, а любой ортонормированный базис становится базисом главных компонент (напомним, что нормировка меняет отношение ортогональности векторов). Отображение из пространства исходных данных на первые k главных компонент вместе с нормировкой задается матрицей

.

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

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

Матрица данных , где каждая строка - вектор предобработанных данных (центрированных и правильно нормированных), число строк - m (количество векторов данных), число столбцов - n (размерность пространства данных);

Матрица нагрузок (Loadings) , где каждый столбец - вектор главных компонент, число строк -- n (размерность пространства данных), число столбцов - k (количество векторов главных компонент, выбранных для проецирования);

Матрица счетов (Scores)

,

где каждая строка - проекция вектора данных на k главных компонент; число строк - m (количество векторов данных), число столбцов - k (количество векторов главных компонент, выбранных для проецирования);

Матрица Z-счетов (Z-scores)

,

где каждая строка-- проекция вектора данных на k главных компонент, нормированная на единичную выборочную дисперсию; число строк - m (количество векторов данных), число столбцов - k (количество векторов главных компонент, выбранных для проецирования);

Матрица ошибок (остатков) (Errors or residuals)

.

Основная формула:

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