Метод главных компонент
Материал из MachineLearning.
м (→Оценка числа главных компонент по правилу сломанной трости) |
(→Поиск ортогональных проекций с наибольшим рассеянием) |
||
(20 промежуточных версий не показаны.) |
Текущая версия
Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных. Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)[1] или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.
Формальная постановка задачи
Задача анализа главных компонент, имеет, как минимум, четыре базовых версии:
- аппроксимировать данные линейными многообразиями меньшей размерности;
- найти подпространства меньшей размерности, в ортогональной проекции на которые разброс данных (т.е. среднеквадратичное уклонение от среднего значения) максимален;
- найти подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально;
- для данной многомерной случайной величины построить такое ортогональное преобразование координат, что в результате корреляции между отдельными координатами обратятся в ноль.
Первые три версии оперируют конечными множествами данных. Они эквивалентны и не используют никакой гипотезы о статистическом порождении данных. Четвёртая версия оперирует случайными величинами. Конечные множества появляются здесь как выборки из данного распределения, а решение трёх первых задач — как приближение к «истинному» преобразованию Кархунена-Лоэва. При этом возникает дополнительный и не вполне тривиальный вопрос о точности этого приближения.
Аппроксимация данных линейными многообразиями
Метод главных компонент начинался с задачи наилучшей аппроксимации конечного множества точек прямыми и плоскостями (К. Пирсон, 1901). Дано конечное множество векторов . Для каждого
среди всех
-мерных линейных многообразий в
найти такое
, что сумма квадратов уклонений
от
минимальна:
-
,
где — евклидово расстояние от точки до линейного многообразия. Всякое
-мерное линейное многообразие в
может быть задано как множество линейных комбинаций
, где параметры
пробегают вещественную прямую
,
а
— ортонормированный набор векторов
-
,
где евклидова норма,
— евклидово скалярное произведение, или в координатной форме:
-
.
Решение задачи аппроксимации для даётся набором вложенных линейных многообразий
,
. Эти линейные многообразия определяются ортонормированным набором векторов
(векторами главных компонент) и вектором
.
Вектор
ищется, как решение задачи минимизации для
:
то есть
-
.
Это — выборочное среднее:
Фреше в 1948 году обратил внимание, что вариационное определение среднего (как точки, минимизирующей сумму квадратов расстояний до точек данных) очень удобно для построения статистики в произвольном метрическом пространстве, и построил обобщение классической статистики для общих пространств (обобщённый метод наименьших квадратов).
Векторы главных компонент могут быть найдены как решения однотипных задач оптимизации:
- 1) централизуем данные (вычитаем среднее):
. Теперь
;
- 2) находим первую главную компоненту как решение задачи;
-
.
- Если решение не единственно, то выбираем одно из них.
-
- 3) Вычитаем из данных проекцию на первую главную компоненту:
-
;
-
- 4) находим вторую главную компоненту как решение задачи
-
.
- Если решение не единственно, то выбираем одно из них.
- …
-
- 2k-1) Вычитаем проекцию на
-ю главную компоненту (напомним, что проекции на предшествующие
главные компоненты уже вычтены):
-
;
-
- 2k) находим k-ю главную компоненту как решение задачи:
-
.
- Если решение не единственно, то выбираем одно из них.
- …
-
На каждом подготовительном шаге вычитаем проекцию на предшествующую главную компоненту. Найденные векторы
ортонормированы просто в результате решения описанной задачи оптимизации, однако чтобы не дать ошибкам вычисления нарушить взаимную ортогональность векторов главных компонент, можно включать
в условия задачи оптимизации.
Неединственность в определении помимо тривиального произвола в выборе знака (
и
решают ту же задачу) может быть более существенной и происходить, например, из условий симметрии данных.
Поиск ортогональных проекций с наибольшим рассеянием
Пусть нам дан центрированный набор векторов данных (среднее арифметическое значение
равно нулю). Задача — найти такое ортогональное преобразование в новую систему координат, для которого были бы верны следующие условия:
- Выборочная дисперсия данных вдоль первой координаты максимальна (эту координату называют первой главной компонентой);
- Выборочная дисперсия данных вдоль второй координаты максимальна при условии ортогональности первой координате (вторая главная компонента);
- …
- Выборочная дисперсия данных вдоль значений
-ой координаты максимальна при условии ортогональности первым
координатам;
- …
Выборочная дисперсия данных вдоль направления, заданного нормированным вектором , это
(поскольку данные центрированы, выборочная дисперсия здесь совпадает со средним квадратом уклонения от нуля).
Формально, если ,
— искомое преобразование, то для векторов
должны выполняться следующие условия:
- Если решение не единственно, то выбираем одно из них.
- Вычитаем из данных проекцию на первую главную компоненту:
-
; в результате
;
- находим вторую главную компоненту как решение задачи
-
- Если решение не единственно, то выбираем одно из них.
- …
- Вычитаем проекцию на
-ю главную компоненту (напомним, что проекции на предшествующие
главные компоненты уже вычтены):
-
; в результате
;
- находим
-ю главную компоненту как решение задачи
-
- Если решение не единственно, то выбираем одно из них.
- ...
Фактически, как и для задачи аппроксимации, на каждом шаге решается задача о первой главной компоненте для данных, из которых вычтены проекции на все ранее найденные главные компоненты. При большом числе итерации (большая размерность, много главных компонент) отклонения от ортогональности накапливаются и может потребоваться специальная коррекция алгоритма или другой алгоритм поиска собственных векторов ковариационной матрицы.
Решение задачи о наилучшей аппроксимации даёт то же множество решений , что и поиск ортогональных проекций с наибольшим рассеянием, по очень простой причине:
и первое слагаемое не зависит от
. Только одно дополнение к задаче об аппроксимации: появляется последняя главная компонента
Поиск ортогональных проекций с наибольшим среднеквадратичным расстоянием между точками
Ещё одна эквивалентная формулировка следует из очевидного тождества, верного для любых векторов
:
В левой части этого тождества стоит среднеквадратичное расстояние между точками, а в квадратных скобках справа — выборочная дисперсия. Таким образом, в методе главных компонент ищутся подпространства, в проекции на которые среднеквадратичное расстояние между точками максимально (или, что то же самое, его искажение в результате проекции минимально)[1]. Такая переформулировка позволяет строить обобщения с взвешиванием различных парных расстояний (а не только точек).
Аннулирование корреляций между координатами
Для заданной -мерной случайной величины
найти такой ортонормированный базис,
, в котором коэффициент ковариации между различными координатами равен нулю. После преобразования к этому базису
-
для
.
Здесь — коэффициент ковариации.
Диагонализация ковариационной матрицы
Все задачи о главных компонентах приводят к задаче диагонализации ковариационной матрицы или выборочной ковариационной матрицы. Эмпирическая или выборочная ковариационная матрица, это
Ковариационная матрица многомерной случайной величины , это
Векторы главных компонент для задач о наилучшей аппроксимации и о поиске ортогональных проекций с наибольшим рассеянием — это ортонормированный набор собственных векторов эмпирической ковариационной матрицы
, расположенных в порядке убывания собственных значений
Эти векторы служат оценкой для собственных векторов ковариационной матрицы
. В базисе из собственных векторов ковариационной матрицы она, естественно, диагональна, и в этом базисе коэффициент ковариации между различными координатами равен нулю.
Если спектр ковариационной матрицы вырожден, то выбирают произвольный ортонормированный базис собственных векторов. Он существует всегда, а собственные числа ковариационной матрицы всегда вещественны и неотрицательны.
Сингулярное разложение матрицы данных
Математическое содержание метода главных компонент — это спектральное разложение ковариационной матрицы , то есть представление пространства данных в виде суммы взаимно ортогональных собственных подпространств
, а самой матрицы
— в виде линейной комбинации ортогональных проекторов на эти подпространства с коэффициентами
. Если
— матрица, составленная из векторов-строк центрированных данных, то
и задача о спектральном разложении ковариационной матрицы
превращается в задачу о сингулярном разложении (англ. Singular value decomposition) матрицы данных
.
Хотя формально задачи сингулярного разложения матрицы данных и спектрального разложения ковариационной матрицы совпадают, алгоритмы вычисления сингулярного разложения напрямую, без вычисления ковариационной матрицы и её спектра, более эффективны и устойчивы [1].
Теория сингулярного разложения была создана Дж. Дж. Сильвестром (англ. J. J. Sylvester) в 1889 г. и изложена во всех подробных руководствах по теории матриц [1].
Матрица преобразования к главным компонентам
Матрица преобразования данных к главным компонентам строится из векторов главных компонент:
. Здесь
— ортонормированные векторы-столбцы главных компонент, расположенные в порядке убывания собственных значений, верхний индекс
означает транспонирование. Матрица
является ортогональной:
.
После преобразования большая часть вариации данных будет сосредоточена в первых координатах, что даёт возможность отбросить оставшиеся и рассмотреть пространство уменьшенной размерности.
Остаточная дисперсия
Пусть данные центрированы, . При замене векторов данных
на их проекцию на первые
главных компонент
вносится средний квадрат ошибки в расчете на один вектор данных:
где собственные значения эмпирической ковариационной матрицы
, расположенные в порядке убывания, с учетом кратности.
Эта величина называется остаточной дисперсией. Величина
называется объяснённой дисперсией. Их сумма равна выборочной дисперсии. Соответствующий квадрат относительной ошибки — это отношение остаточной дисперсии к выборочной дисперсии (то есть доля необъяснённой дисперсии):
По относительной ошибке оценивается применимость метода главных компонент с проецированием на первые
компонент.
Замечание: в большинстве вычислительных алгоритмов собственные числа с соответствуюшими собственными векторами — главными компонентами
вычисляются в порядке «от больших
— к меньшим». Для вычисления
достаточно вычислить первые
собственных чисел и след эмпирической ковариационной матрицы
,
(сумму диагональных элементов
, то есть дисперсий по осям). Тогда
Оценка числа главных компонент по правилу сломанной трости
Целевой подход к оценке числа главных компонент по необходимой доле объяснённой дисперсии формально применим всегда, однако неявно он предполагает, что нет разделения на "сигнал" и "шум", и любая заранее заданная точность имеет смысл. Поэтому часто более продуктивна иная эвристика, основывающаяся на гипотезе о наличии "сигнала" (сравнительно малая размерность, относительно большая амплитуда) и "шума" (большая размерность, относительно малая амплитуда). С этой точки зрения метод главных компонент работает как фильтр: сигнал содержится, в основном, в проекции на первые главные компоненты, а в остальных компонентах пропорция шума намного выше.
Вопрос, как оценить число необходимых главных компонент, если отношение "сигнал/шум" заранее неизвестно? Одним из наиболее популярных эвристических подходов является правило сломанной трости (англ. Broken stick model)[1]. Набор нормированных собственных чисел (,
) сравнивается с распределением длин обломков трости единичной длины, сломанной в
-й случайно выбранной точке (точки разлома выбираются независимо и равнораспределены по длине трости). Пусть
(
) - длины полученных кусков трости, занумерованные в порядке убывания длины:
. Нетрудно найти математическое ожидание
:
По правилу сломанной трости -й собственный вектор (в порядке убывания собственных чисел
) сохраняется в списке главных компонент, если
На Рис. приведён пример для 5-мерного случая:
=(1+1/2+1/3+1/4+1/5)/5;
=(1/2+1/3+1/4+1/5)/5;
=(1/3+1/4+1/5)/5;
=(1/4+1/5)/5;
=(1/5)/5.
Для примера выбрано
=0.5;
=0.3;
=0.1;
=0.06;
=0.04.
По правилу сломанной трости в этом примере следует оставлять 2 главных компоненты:
Нормировка
Нормировка после приведения к главным компонентам
После проецирования на первые главных компонент с
удобно произвести нормировку на единичную (выборочную) дисперсию по осям. Дисперсия вдоль
й главной компоненты равна
), поэтому для нормировки надо разделить соответствующую координату на
. Это преобразование не является ортогональным и не сохраняет скалярного произведения. Ковариационная матрица проекции данных после нормировки становится единичной, проекции на любые два ортогональных направления становятся независимыми величинами, а любой ортонормированный базис становится базисом главных компонент (напомним, что нормировка меняет отношение ортогональности векторов). Отображение из пространства исходных данных на первые
главных компонент вместе с нормировкой задается матрицей
-
.
Именно это преобразование чаще всего называется преобразованием Кархунена-Лоэва. Здесь — векторы-столбцы, а верхний индекс
означает транспонирование.
Нормировка до вычисления главных компонент
Предупреждение: не следует путать нормировку, проводимую после преобразования к главным компонентам, с нормировкой и «обезразмериванием» при предобработке данных, проводимой до вычисления главных компонент. Предварительная нормировка нужна для обоснованного выбора метрики, в которой будет вычисляться наилучшая аппроксимация денных, или будут искаться направления наибольшего разброса (что эквивалентно). Например, если данные представляют собой трёхмерные векторы из «метров, литров и килограмм», то при использовании стандартного евклидового расстояния разница в 1 метр по первой координате будет вносить тот же вклад, что разница в 1 литр по второй, или в 1 кг по третьей. Обычно системы единиц, в которых представлены исходные данные, недостаточно точно отображают наши представления о естественных масштабах по осям, и проводится «обезразмеривание»: каждая координата делится на некоторый масштаб, определяемый данными, целями их обработки и процессами измерения и сбора данных.
Есть три cущественно различных стандартных подхода к такой нормировке: на единичную дисперсию по осям (масштабы по осям равны средним квадратичным уклонениям — после этого преобразования ковариационная матрица совпадает с матрицей коэффициентов корреляции), на равную точность измерения (масштаб по оси пропорционален точности измерения данной величины) и на равные требования в задаче (масштаб по оси определяется требуемой точностью прогноза данной величины или допустимым её искажением — уровнем толерантности). На выбор предобработки влияют содержательная постановка задачи, а также условия сбора данных (например, если коллекция данных принципиально не завершена и данные будут ещё поступать, то нерационально выбирать нормировку строго на единичную дисперсию, даже если это соответствует смыслу задачи, поскольку это предполагает перенормировку всех данных после получения новой порции; разумнее выбрать некоторый масштаб, грубо оценивающий стандартное отклонение, и далее его не менять).
Предварительная нормировка на единичную дисперсию по осям разрушается поворотом системы координат, если оси не являются главными компонентами, и нормировка при предобработке данных не заменяет нормировку после приведения к главным компонентам.
Механическая аналогия и метод главных компонент для взвешенных данных
Если сопоставить каждому вектору данных единичную массу, то эмпирическая ковариационная матрица
совпадёт с тензором инерции этой системы точечных масс (делённым на полную массу
), а задача о главных компонентых — с задачей приведения тензора инерции к главным осям. Можно использовать дополнительную свободу в выборе значений масс для учета важности точек данных или надежности их значений (важным данным или данным из более надежных источников приписываются бо́льшие массы). Если вектору данных
придаётся масса
, то вместо эмпирической ковариационной матрицы
получим
Все дальнейшие операции по приведению к главным компонентам производятся так же, как и в основной версии метода: ищем ортонормированный собственный базис , упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми
компонентами (по суммам собственных чисел
), нормируем и т. п.
Более общий способ взвешивания даёт максимизация взвешенной суммы попарных расстояний[1] между проекциями. Для каждых двух точек данных, вводится вес
;
и
. Вместо эмпирической ковариационной матрицы
используется
При симметричная матрица
положительно определена, поскольку положительна квадратичная форма:
Далее ищем ортонормированный собственный базис , упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми
компонентами и т. д. — в точности так же, как и в основном алгоритме.
Этот способ применяется при наличии классов: для из разных классов вес
вес выбирается бо́льшим, чем для точек одного класса. В результате, в проекции на взвешенные главные компоненты различные классы «раздвигаются» на большее расстояние.
Другое применение — снижение влияния больших уклонений (оутлайеров, англ.Outlier), которые могут искажать картину из-за использования среднеквадратичного расстояния: если выбрать , то влияние больших уклонений будет уменьшено. Таким образом, описанная модификация метода главных компонент является более робастной, чем классическая.
Устойчивость главных компонент
Анализ соответствий
Анализ соответствий (англ. Correspondence analysis)...
Специальная терминология
В статистике при использовании метода главных компонент используют несколько специальных терминов.
Матрица данных ; каждая строка — вектор предобработанных данных (центрированных и правильно нормированных), число строк —
(количество векторов данных), число столбцов —
(размерность пространства данных);
Матрица нагрузок (Loadings) ; каждый столбец — вектор главных компонент, число строк —
(размерность пространства данных), число столбцов —
(количество векторов главных компонент, выбранных для проецирования);
Матрица счетов (Scores) ; каждая строка — проекция вектора данных на
главных компонент; число строк —
(количество векторов данных), число столбцов —
(количество векторов главных компонент, выбранных для проецирования);
Матрица Z-счетов (Z-scores) ; каждая строка — проекция вектора данных на
главных компонент, нормированная на единичную выборочную дисперсию; число строк —
(количество векторов данных), число столбцов —
(количество векторов главных компонент, выбранных для проецирования);
Матрица ошибок (или остатков) (Errors or residuals) .
Основная формула:
Пределы применимости и ограничения эффективности метода
![Построение ветвящихся главных компонент методом топологических грамматик. Крестики — точки данных, красное дерево с желтыми узлами — аппроксимирующий дендрит.](/wiki/images/e/e0/BranchingPrincipalComponents.gif)
Метод главных компонент применим всегда. Распространённое утверждение о том, что он применим только к нормально распределённым данным (или для распределений, близких к нормальным) неверно: в исходной формулировке К. Пирсона ставится задача об аппроксимации конечного множества данных и отсутствует даже гипотеза о их статистическом порождении, не говоря уж о распределении.
Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность . Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности. Для работы с такими «кривыми» главными компонентами изобретен метод главных многообразий[1] и различные версии нелинейного метода главных компонент[1][1]. Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например самоорганизующиеся карты Кохонена, нейронный газ[1] или топологические грамматики[1]. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к независимым компонентам[1], которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.
Примеры использования
Метод главных компонент — наиболее популярный метод сокращения размерности во многих приложениях, в том числе в следующих областях:
- Визуализация данных;
- Компрессия изображений и видео;
- Подавление шума на изображениях;
- Индексация видео;
- Биоинформатика;
- Хемометрика;
- Психодиагностика;
- Общественные науки (включая политологию);
- Сокращение размерности динамических моделей (в том числе — в вычислительной гидродинамике).
Литература
Классические работы
- 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 с.
- Рао С. Р., Линейные статистические методы и их применения.— М.: Наука (Физматлит), 1968.— 548 с.
- 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
Сборник современных обзоров
- Gorban A. N., Kegl B., Wunsch D., Zinovyev A. Y. (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, Series: Lecture Notes in Computational Science and Engineering 58, Springer, Berlin — Heidelberg — New York, 2008, XXIV, 340 p. 82 illus. ISBN 978-3-540-73749-0 (а также онлайн).
Ссылки
- A tutorial on Principal Components Analysis, Jonathon Shlens, 22, 2009; Version 3.01.
- Нелинейный метод главных компонент (сайт-библиотека)
- Метод главных компонент на wikipedia.org
Учебное програмное обеспечение
Java-апплет «Метод главных компонент и самоорганизующиеся карты» (E.M. Mirkes, Principal Component Analysis and Self-Organizing Maps: applet. University of Leicester, 2011). Свободно распространяемая программа с моделями метода главных компонент, самоорганизуюшихся карт (SOM) и растущих самоорганизующихся карт (Growing Self-Organized Maps, GSOM). Дано описание алгоритмов (англ.), приведены тьюториалы и некоторые публикации. Используется для выполнения небольших студенческих исследовательских работ по сравнению различных алгоритмов аппроксимации данных.
Примечания
Незарегистрированные пользователи не видят примечаний и основных литературных ссылок (дефект системы). Зарегистрироваться безопасно и просто.