Анализ главных компонентов Энциклопедия алгоритмов PCA

Анализ главных компонентов позволяет использовать низкоразмерные данные для представления наиболее важных особенностей многомерных сложных данных. Идея PCA состоит в том, чтобы$n$карты пространственных признаков в$k$многомерное пространство$k<n$,Этот$k$Размерный объект — это совершенно новый ортогональный объект, построенный заново.$k$размерные характеристики, а не просто$n$Удалить остальное из размерных признаков$n-k$размерные особенности. На основе исходного PCA, по характеристикам данных, исследователи предлагают различные варианты PCA, но основная идея одна и та же. Например, PCA ядра для нелинейных данных, CCIPCA для данных последовательности, 2DPCA, 2D2DPCA и BDPCA для данных двумерного изображения и т. д. Далее сначала подробно представлена ​​идея PCA, а затем кратко представлены другие версии алгоритма PCA.

1. Принцип ППШ

(Этот раздел относится кВнедрение алгоритма анализа главных компонентов (PCA) с нуля) PCA можно определить как ортогональную проекцию данных на низкоразмерное линейное пространство, называемое основным подпространством, так что дисперсия проецируемых данных максимальна (Hotelling, 1933), теория максимальной дисперсии. Эквивалентно, ее также можно определить как линейную проекцию, минимизирующую среднюю стоимость проекции, т. е. теорию минимальной ошибки. Средняя стоимость проекций — это средний квадрат расстояния между точками данных и их проекциями (Пирсон, 1901).

1.1 Теория максимальной дисперсии

При обработке сигналов считается, что сигнал имеет большую дисперсию, а шум — малую.Отношение сигнал/шум — это отношение дисперсии между сигналом и шумом.Чем больше, тем лучше. Из-за того, что мы думаем, лучший$k$размерные характеристики$n$Размерные точки выборки преобразуются в$k$Тогда выборочная дисперсия в каждом измерении будет максимально большой.

Сначала рассмотрим одномерное пространство$(k=1)$проекция на. мы можем использовать$n$размерный вектор$u$Определяет направление этого пространства. Для удобства и без ограничения общности будем считать, что единичный вектор выбран таким, что$u^T u=1$.

(Предполагая, что данные имеют нулевое среднее значение) Как показано на рисунке выше, красная точка представляет исходную точку выборки.$x^{(i)}$,$u$Наклон синей линии также является вектором направления линии и единичным вектором.Синяя точка на линии представляет исходную точку выборки.$x^{(i)}$существует$u$проекция на. Легко узнать, что расстояние точки проекции от начала координат равно$x^{(i)T} u$, поскольку среднее значение каждого измерения этих исходных точек выборки равно 0, оно проецируется на$u$Среднее значение точек выборки по-прежнему равно 0.

Предположим, исходный набор данных$X_{m\times n}$, наша цель — найти оптимальное проекционное пространство$W_{n\times k}=(w_1, w_2, ..., w_k)$,в$w_i$является единичным вектором и$w_i$является единичным вектором и$w_i$и$w_j(i\neq j)$Ортогональный, что лучше$W$? является проекцией исходной точки выборки на$W$После вышеизложенного дисперсия прогнозируемых точек выборки максимальна.

Поскольку среднее значение после проекции равно 0, общая дисперсия после проекции равна:$\frac{1}{m}\sum_{i=1}^m (x^{(i)T}w)^2=\frac{1}{m}\sum_{i=1}^m w^Tx^{(i)} x^{(i)T}w=\sum_{i=1}^m w^T(\frac{1}{m}x^{(i)}x^{(i)T})w$

в$\frac{1}{m}x^{(i)}x^{(i)T}$исходный набор данных$X$ковариационная матрица (поскольку$x^{(i)}$имеет среднее значение 0, из-за несмещенной оценки общая ковариационная матрица делится на$m-1$, то есть в м).

Помните$\lambda=\frac{1}{m}\sum_{i=1}^m (x^{(i)T}w)^2,\Sigma=\frac{1}{m}x^{(i)}x^{(i)T}$, то есть$\lambda=w^T\Sigma w$

Умножьте обе части вышеприведенного уравнения влево$w$, отмечая$ww^T=1$(единичный вектор), затем$\lambda w=\Sigma w$так$w$это матрица$\Sigma$Собственные векторы, соответствующие собственным значениям .

Чтобы максимизировать общую дисперсию после прогнозирования, то есть$\lambda$самый большой и, следовательно, лучший вектор проекции$w$является собственным значением$\lambda$Собственный вектор, соответствующий наибольшему, поэтому, когда мы устанавливаем$w$Когда он установлен равным вектору с наибольшим собственным значением, дисперсия достигает своего максимального значения. Этот вектор признаков называется первым главным компонентом.

Мы можем определить дополнительные основные компоненты поэтапным образом, выбирая новое направление как тот, который максимизирует прогнозную дисперсию между всеми возможными направлениями, которые являются ортогональными тем, которые уже рассматриваются. если мы рассмотрим$k$Общий случай размерного проекционного пространства, тогда оптимальная линейная проекция, которая максимизирует дисперсию проецируемых данных, задается матрицей ковариации данных$\Sigma$из$k$собственные векторы$w_1, ..., w_k$определение, соответствующее$k$наибольшее собственное значение$\lambda_1,...,\lambda_k$. Это легко доказать по индукции.

Следовательно, нам нужно только выполнить разложение по собственным значениям ковариационной матрицы, чтобы получить предварительную оценку.$k$Собственный вектор, соответствующий большому собственному значению, является лучшим$k$Особенности реставрации, и это$k$Функции обновления являются ортогональными. прежде чем получить$k$Кусок$u$Позже исходный набор данных$X$Новые образцы можно получить путем трансформации.

1.2 Теория наименьших квадратов ошибок

Как показано на рисунке выше, предполагая такую ​​двумерную точку выборки (красная точка), в соответствии с теорией максимальной дисперсии, которую мы объяснили ранее, наша цель состоит в том, чтобы найти прямую линию, чтобы дисперсия точки, спроецированная из выборки указать на прямую или плоскость является самым большим. Суть в том, чтобы найти прямую или плоскость, поэтому мерой того, хороша ли прямая, является не только метод максимизации дисперсии. Вспоминая линейную регрессию, которую мы впервые изучили, цель состоит в том, чтобы найти линейную функцию, чтобы прямая линия лучше всего соответствовала точкам выборки, поэтому можем ли мы считать, что лучшая прямая линия — это прямая линия после регрессии? Во время регрессии наш метод наименьших квадратов измеряет расстояние между точками выборки и осью линии. Например, в этой задаче функция$x$, метка класса$y$. Метод наименьших квадратов измеряет расстояние во время регрессии$d$. Если метод регрессии используется для измерения наилучшей прямой линии, то регрессия выполняется непосредственно на исходной выборке, которая не имеет ничего общего с выбором признаков.

Поэтому мы намерены использовать другой метод оценки качества линии, используя расстояние от точки до линии$из'$измерять.

Есть$m$точки выборки$x^{(1)},...,x^{(m)}$, каждая точка выборки$n$измерение. точка выборки$x^{(i)}$Проекция на прямую записывается как$x^{(1)''}$, то мы хотим минимизировать$\sum_{i=1}^m (x^{(i)'}-x^{(i)})^2$

Эта формула называется наименьшей квадратичной ошибкой.

Сначала мы определяем точку, через которую проходит линия, предполагая, что мы хотим найти точку в пространстве$x_0$представлять это$m$Точка выборки, слово «представитель» не определяется количественно, поэтому, если мы хотим провести количественную оценку, нам просто нужно найти$n$точка измерения$x_0$, так что$J_0(x_0)=\sum_{i=1}^m (x^{(i)'}-x^{(i)})^2$минимум. в$J_0(x_0)$функция оценки квадрата ошибки. Предположение$\overline{x}$за$m$Среднее значение выборочных точек, т. е.$\overline{x}=\frac{1}{m}\sum_{i=1}^m x^{(i)}$но$J_0(x_0)=\sum_{i=1}^m(x_0-x^{(i)})^2\\=\sum_{i=1}^m((x_0-\overline{x})-(x^{(i)}-\overline{x}))^2\\=\sum_{i=1}^m(x_0-\overline{x})^2-2\sum_{i=1}^m(x_0-\overline{x})^T(x^{(i)}-\overline{x})+\sum_{i=1}^m(x^{(i)}-\overline{x})^2\\=\sum_{i=1}^m(x_0-\overline{x})^2-2(x_0-\overline{x})^T\sum_{i=1}^m(x^{(i)}-\overline{x})+\sum_{i=1}^m(x^{(i)}-\overline{x})^2\\=-\sum_{i=1}^m(x_0-\overline{x})^2+\sum_{i=1}^m(x^{(i)}-\overline{x})^2$

Очевидно, что второй член приведенного выше уравнения совпадает с$x_0$неактуально, следовательно,$J_0(x_0)$существует$\overline{x}$имеет минимальное значение.

Далее определяем вектор направления линии. Мы уже знаем, что прямая проходит через точку$\overline{x}$, предполагая, что направление линии является единичным вектором$\overrightarrow{e}$. Тогда любая точка на прямой$x^{(i)'}$имеют:$x^{(i)'}=\overline{x}+a_i \overrightarrow{e}$,в,$a_i$да$x_{(i)'}$к точке$\overline{x}$расстояние.

Мы переопределяем ошибку наименьшего квадрата:

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

преимущество:

Это неконтролируемое обучение и полностью без параметров. В процессе расчета PCA нет необходимости вручную задавать параметры или вмешиваться в расчет по какой-либо эмпирической модели, конечный результат связан только с данными и не зависит от пользователя.

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

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

Метод расчета прост и легко реализуем на компьютере.

недостаток:

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

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

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

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

1.3 Разложение по собственным значениям при многомерных данных

В реальной жизни из-за высокоразмерных характеристик выборки (каждый пиксель распознавания изображения является размерностью) это приведет к ковариационной матрице$\Sigma$Это очень большой, и компьютер трудно хранить и вычислять Как сделать разложение по собственным значениям для многомерных данных? мы знаем$\Sigma=XX^T$, рассмотрим матрицу подстановки$P=X^T X$, если выборок 100, размерностей 10000, то$\Sigma$представляет собой 10000-мерную квадратную матрицу, и$P$Просто 100-мерная квадратная матрица. Делаем следующий вывод:$Pv=\lambda v\\X^TXv=\lambda v\\XX^TXv=X\lambda v\\\Sigma(Xv)=\lambda(Xv)$поэтому, спросив$P$Собственные значения и собственные векторы , чьи собственные значения равны$\Sigma$Собственные значения , собственные векторы которых умножаются на случайный вектор$X$это$\Sigma$, чтобы завершить разложение по собственным значениям многомерных данных (можно получить только некоторые из первых нескольких главных компонент).

Проверять:$A^TA$и$AA^T$собственные значения равны? Дополнение: В общем,$AB$и$BA$Собственные значения$0$Количество собственных значений.

Если существует обратимая матрица$P$сделать,$P^{-1}AP=B$, то матрица$A$с матрицей$B$сходство. Если две матрицы подобны, то они имеют одинаковый ранг, один и тот же определитель, одинаковую трассу (сумму всех собственных значений или сумму элементов главной диагонали), и обе имеют одинаковые собственные значения (может быть, еще несколько нулей) собственные значения).

2. Алгоритм инкрементного анализа главных компонентов CCIPCA [1]

Откровенный инкрементальный анализ основных компонентов без ковариаций Прямой бесковариационный инкрементный анализ основных компонентов.

Предположим, что последовательность входных векторов$u'(t),t=1,2,...$;$n$Среднее значение входного изображения равно$m(n)=\frac{1}{n}\sum_{t=1}^n u'(t)$, его ковариационная матрицаA(n)=\frac{1}{n}\sum_{t=1}^n[u'(t)-m(n)][u'(t)-m(n)]^T=\frac{1}{n}\sum_{i=1}^n u(t)u(t)^T \tag{1}здесь$u(t)=u'(t)-m(n)$

$u(n)$Первый$i$Формулы для вычисления собственных значений и собственных значений и собственных векторов:$\lambda_ix_i(n)=A(n)x_i(n)$,в$x_i(n)$во-первых$n$Номер, который нужно запрашивать при входе$i$вектор признаков,$\lambda_i$является соответствующим собственным значением . Чтобы ускорить итерацию алгоритма CCIPCA, вся итерация представляет собой произведение собственного значения и собственного вектора$\lambda_ix_i$выполнено, пусть$n$при вводеv_i(n)=\lambda_ix_i(n)=A(n)x_i(n) \tag{2}Подставим (1) в (2), получимv_i(n)=\frac{1}{n}\sum_{t=1}^n u(t)u(t)^T x_i(n)\tag{3}Если произведение собственного значения и собственного вектора получено путем итерации$v_i$, поскольку собственные векторы нормализованы, поскольку формула (2) является модулем (внутренний продукт, открытый корень), она может быть получена$\lambda_i=||v_i||,x_i=\frac{v_i}{||v_i||}$. Итерация принимает формулу (3), положим$\frac{v_i(n-1)}{||v_i(n-1)||}$примерно$x_i(n)$Подставив в (3), основную итеративную формулу CCIPCA можно получить преобразованием,v_i(n)=\frac{n-1}{n}v_i(n-1)+\frac{1}{n}u(n)u(n)^T\frac{v_i(n-1)}{||v_i(n-1)||} \tag{4}

в$\frac{n-1}{n}$значение итерации предыдущего шага$v_i(n-1)$Вес второго предмета$\frac{1}{n}$Эквивалентно размеру шага корректировки итерации.$u(n)$как первый$n$итеративный вектор новых пар входных данных$v_i(n)$корректировка, в итерациях$v_i(n)$постепенно приближаться к желаемому$i$вектор признаков. Уравнение (4) можно использовать для итерации собственных векторов с разными порядковыми номерами, только входной вектор$u(n)$разные. При нахождении собственного вектора, соответствующего наибольшему собственному значению,$u(n)$Непосредственно собирают для глаз роботов$n$данные. При поиске собственных векторов 2-й, 3-й и даже более высокой размерности требуется следующая обработка: первый собственный вектор получен путем итерации.$u_1(n)=u(n)$, и положи$u_1(n)$Спроецируйте на предыдущий собственный вектор, который был получен (теперь первый собственный вектор), и получите остаточное изображение$u_2(n)$, выраженный следующим образом,$u_2(n)=u_1(n)-u_1^T(n)\frac{v_1(n)}{||v_1(n)||}\frac{v_1(n)}{||v_1(n)||}$ $u_2(n)$В качестве исходных данных для нахождения второго собственного вектора аналогичным образом могут быть получены 3-й, 4-й, .... собственные векторы. Поскольку остаточное изображение и изображение, восстановленное предыдущим собственным вектором, ортогональны, можно получить все взаимно ортогональные собственные векторы. Кроме того, каждый раз, когда вводится новый фрагмент данных, среднее значение также должно обновляться.Для формулы (1) введите первое$n$Среднее значение изображений следующее:$m(n)=\frac{n-1}{n}m(n-1)+\frac{1}{n}u'(n)$

3. KPCA

Супер всеобъемлющий блог о KPCA

• оригинальный ППШ

$XX^T w_i=\lambda_i w_i$

• использовать функцию$\Phi$преобразовать данные$X$карта в многомерное пространство$\Phi(X)$

$\Phi(X)\Phi(X)^T w_i=\lambda_i w_i$

• сделать$w_i = \sum_{k=1}^N \alpha_i\Phi(x_i) = \Phi(X)\alpha$придется

$\Phi(X)\Phi(X)^T \Phi(X) \alpha=\lambda_i \Phi(X)\alpha$

• Умножьте обе части влево$\Phi(X)^T$придется

$\Phi(X)^T\Phi(X)\Phi(X)^T \Phi(X) \alpha=\lambda_i \Phi(X)^T \Phi(X)\alpha$

• Из свойств функции ядра мы можем получить$K=\Phi(X)^T \Phi(X)$

$KK \alpha=\lambda_i K\alpha \\ \Rightarrow K\alpha=\lambda_i \alpha$

Обратите внимание, что вектор признаков$w_i$должно быть дальше$\Phi(X)\alpha$Рассчитано. но,$\Phi(X)$Это невозможно вычислить, поэтому нет возможности получить собственные векторы.

Здесь мы анализируем, можно ли его использовать напрямую$\alpha$Чтобы уменьшить размерность данных, ответ положительный.

Если приходят новые данные$x$, необходимо использовать приведенные выше результаты для получения данных уменьшения размерности$\hat{x}$:

$\hat{x}=w_i^T x\\=(\Phi(x)\alpha)^T \Phi(x)\\=\alpha^T \Phi(X)^T\Phi(x)\\=[\alpha_1,...,\alpha_N][k(x_1,x),..., k(x_N, x)]^T$

Разница между PCA и KPCA

• PCA по-прежнему является хорошим методом анализа.Когда данные имеют нелинейное многообразное распределение или индикаторы имеют нелинейную зависимость, эффект может быть не особенно хорошим для метода линейного анализа, но следует отметить, что он также не является Линейный метод анализа.В фактических экономических показателях существует линейная корреляция (информационная избыточность), что соответствует статистическим законам, а полностью нерелевантные экономические данные встречаются крайне редко.Он имеет преимущества простого расчета PCA, отсутствия предварительных знаний и без настройки параметров.
• PCA не совсем то же самое, что KPCA с линейным ядром, для N выборок данных с P индикаторами. Ковариационная матрица, рассчитанная с помощью PCA, представляет собой матрицу размерности PXP. Количество основных компонентов, которые она может извлечь, равно P, а KPCA вычисляется из матрицы ядра. Максимальный главный компонент, который может быть извлечен, равен N. Чтобы удовлетворить выборку среднее значение в пространстве признаков равно нулю, а также требуется специальная обработка матрицы ядра K, что также является причиной несогласованности со скалярным произведением линейного ядра и исходной выборки.
• Функцию ядра KPCA и параметры ядра выбрать сложно. Собственный вектор ковариационной матрицы PCA соответствует пропорции главных компонентов каждого индекса, так что главные компоненты могут быть объяснены исходным облаком индексов, в то время как собственный вектор KPCA основан на собственном векторе матрицы ядра, которая не имеет соответствующей связи с исходным индексом, поэтому главный компонент ядра объясняет. Во-вторых, после того, как KPCA проецирует индикаторы в многомерное пространство признаков, и фактические данные обрабатываются в исходном пространстве, стоит дополнительно изучить, являются ли его значения имеют смысл сортировки в исходном пространстве.

4. 2DPCA[2]

Предполагать$A_i, i=1,2,...,N$да$N$Образец изображений,$A_i\in R^{m\times n}$. Сначала вычислите ковариационную матрицу, которая является общей матрицей рассеяния.$G_t$ $G_t=\frac{1}{N}\sum_{i=1}^N(A_i-\hat{A})^T(A_i-\hat{A})$в$\hat{A}=\frac{1}{N}\sum_{i=1}^N A_i$является средним значением всей выборки.

рассчитать$G_t$Собственные значения и собственные векторы берут кумулятивную ставку вклада собственных значений$\alpha=0.9~0.99$Соответствующие собственные векторы образуют матрицу проекции$U=[u_1, u_2, ..., u_k]\in R^{n\times k}$. но,$F_i=A_iU\in R^{m\times k}$это$A_j$Характеристики. Можно знать, что оригинальный двумерный размер изображения$m\times n$, который сейчас сводится к$m\times k$,$k$основан на$\alpha$быть уверенным. То есть после выполнения извлечения признака сжимается только количество битов вектора-столбца матрицы изображения, а количество битов вектора-строки остается неизменным.

5. 2D2DPCA

Так же, как 2DPCA, который уменьшает измерение только в направлении столбца, эффект уменьшения размера не идеален. Для лучшего уменьшения размерности D.Q.Zhang и Z.H.Zhou предложили метод двунаправленного двумерного анализа главных компонентов (2D2DPCA), то есть обработка 2DPCA выполняется как в направлениях строк, так и в столбцах.

После обработки всех обучающих выборок вышеуказанным 2DPCA получаются новые обучающие выборки.$F_i, i=1,2,...,N$,в$Y_i\in R^{m\times k}$. Построить ковариационную матрицу на новых образцах$G_t^*$ $G_t^*=\frac{1}{N}\sum_{i=1}^N (F_i-\hat{F})(F_i-\hat{F})^T$

Аналогично, спросите$G_t^*$Собственные значения и собственные векторы принимают совокупный вклад собственных значений как$\alpha$Собственные векторы , получить матрицу проекции в направлении строки$V=[v_1,v_2,...,v_d] \in R^{m\times d}$.$F_i$Проекция$V^TF_i\in R^{d\times k}$.

До сих пор оптимальная матрица проекции двух направлений проекции$U$и$V$получаются, для изображения$A_i\in R^{m\times n}$Окончательная матрица уменьшения размера:$Y_i=V^TA_iU\in R^{d\times k}$, восстановленное изображение$A_i^{approx}=VY_iU^T$

6. BDPCA

BDPCA выполняет уменьшение размерности данных в направлениях строк и столбцов соответственно. Преобразуйте матрицу образца изображения$X_{i}^{\prime}$разбить на$p$Кусок$1\times q$Вектор-строка , тогда общая матрица расхождения в направлении строки:

в,$\overline{X}(n)$является средним значением матрицы образца изображения. прежде чем принимать$k_r$Собственные векторы, соответствующие наибольшим собственным значениям, образуют матрицу проекции направления строки как

Точно так же общая матрица расхождения в направлении столбца и фронта$k_c$Собственные векторы, соответствующие наибольшим собственным значениям, образуют матрицу проекции направления столбца соответственно:

Матрица образца изображения$X_{i}^{\prime}$Соответствующая матрица признаков

Размер матрицы признаков BDPCA составляет всего$k_c\times k_r$, поэтому объем вычислений намного меньше, чем у CCIPCA. Но BDPCA — это двумерное пакетное вычисление.

использованная литература

[1] Juyang Weng, Yilu Zhang и Wey-Shiuan Hwang, «Откровенный инкрементальный анализ главных компонентов без ковариаций», IEEE Transactions on Pattern Analysis and Machine Intelligence, т. 25, № 8, стр. 1034–1040, август 2003 г. [2] Jian Y, David Z, Frangi AF и др. Двумерный PCA: новый подход к представлению и распознаванию лиц на основе внешнего вида [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2004, 26(1). ): 131-137.