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

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

Компьютеры - Метод главных компонент - Формальная постановка задачи

22 января 2011

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

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

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

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

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

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

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

$\sum_{i=1}^m \operatorname{dist}^2 \to \min$ ,

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

$\operatorname{dist}^2 = \Vert x_i - a_0 - \sum_{j=1}^k a_j \Vert ^2$ ,

где $\Vert \cdot \Vert$ евклидова норма, $\left$ — евклидово скалярное произведение, или в координатной форме:

$\operatorname{dist}^2 = \sum_{l=1}^n \left \right)^2$ .

Решение задачи аппроксимации для k = 0,1,...,n − 1 даётся набором вложенных линейных многообразий $L_0 \subset L_1 \subset ... L_{n-1}$ , $L_k = \{ a_0 +\beta_1 a_1 +...+ \beta_k a_k | \beta_i \in \mathbb{R} \}$ . Эти линейные многообразия определяются ортонормированным набором векторов $\left\{a_1,..., a_{n-1} \right\}$ и вектором a₀. Вектор a₀ ищется, как решение задачи минимизации для L₀:

$a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left\right),$

то есть

$a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left$ .

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

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

1) централизуем данные: $x_i := x_i - \overline{X}$ . Теперь $\sum_{i=1}^m x_i =0$ ;

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

$a_1 = \underset{\Vert a_1 \Vert =1}{\operatorname{argmin}} \left$ .

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

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

$x_i := x_i - a_1 \left$ ;

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

$a_2 = \underset{\Vert a_2 \Vert =1}{\operatorname{argmin}} \left$ .

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

…

2k-1) Вычитаем проекцию на -ю главную компоненту главные компоненты уже вычтены):

$x_i := x_i - a_{k-1} \left$ ;

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

$a_k = \underset{\Vert a_k \Vert =1}{\operatorname{argmin}} \left$ .

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

…

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

Неединственность в определении a_k помимо тривиального произвола в выборе знака может быть более существенной и происходить, например, из условий симметрии данных. Последняя главная компонента a_n — единичный вектор, ортогональный всем предыдущим a_k.

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

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

Пусть нам дан центрированный набор векторов данных $x_i\in\mathbb{R}^n \;$ . Задача — найти такое ортогональное преобразование в новую систему координат, для которого были бы верны следующие условия:

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

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

$S^2_m \left = \frac{1}{m} \sum\limits_{i=1}^m^2 = \frac{1}{m} \sum\limits_{i=1}^m \left^2$

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

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

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

$\frac{1}{m}\sum_{i,j=1}^m^2 =\frac{2m^2}{m}\left.$

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

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

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

$\operatorname{cov}=0$ для $i \neq j$ .

Здесь $\operatorname{cov}= \operatorname{E}$ — коэффициент ковариации.

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

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

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

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

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