Уменьшение размерности в данных. Метод главных компонент (1185332), страница 2
Текст из файла (страница 2)
Стандартный способ выбора базисав пространстве гиперплоскости – собственные вектора матрицы ковариации с нулем вцентре выборки. Однако, в ряде случаев такой выбор базиса является неадекватным.Например, метод независимых компонент (см. [6]) представляет собой другой способ выборабазиса гиперплоскости, который активно применяется для задачи разделения независимыхисточников.При использовании метода главных компонент необходимо вычислять собственные вектораи собственные значения выборочной матрицы ковариации, которая имеет размер D × D.Сложность этой операции составляет O(D3 ). В том случае, если D > N , то существуетспособ более экономного вычисления собственных векторов и собственных значений матрицыковариации с помощью матрицы размера N × N и сложностью, соответственно, O(N 3 ).Действительно, в пространстве размерности D множество из N точек образует линейноеподпространство максимальной размерности N − 1.
Поэтому не имеет смысла применять методглавных компонент для d > N − 1. С точки зрения матрицы ковариации это означает, чтотолько N − 1 собственных значений отличны от нуля. Все остальные собственные вектора неимеет смысла вычислять, т.к. дисперсия выборки вдоль этих направленийнулю.∑равнаN1N ×DПусть X ∈ R– исходная выборка с нулевым центром, т.е. N n=1 xn = 0.
Тогдавыборочная матрица ковариации S = N1 X T X. Рассмотрим собственные вектора и собственныезначения матрицы S:1 TX Xq i = λi q i .N5Домножим обе части этого уравнения на X:1XX T (Xq i ) = λi (Xq i ).NОбозначая v i = Xq i , получаем1XX T v i = λi v i .NТаким образом, матрица N1 XX T размера N × N имеет те же собственные значения, что ивыборочная матрица ковариации S (у которой, в свою очередь, есть D − N дополнительныхнулевых собственных значений). Сложность поиска собственных значений и собственныхвекторов матрицы N1 XX T составляет O(N 3 ), что может давать значительную выгоду посравнению с O(D3 ) при D > N . Для получения собственных векторов матрицы S домножимобе части последнего уравнения на X T :1 TX X(X T v i ) = λi (X T v i ).NТаким образом, X T v i является собственным вектором матрицы S, отвечающим собственномузначению λi .
Однако, в том случае, если исходные вектора v i являются нормированными, т.е.∥v i ∥ = 1, то вектора X T v i нормированными уже не являются. Нормированные вектора можнополучить с помощью следующего выражения:qi = √1X T vi.N λiТеперь, объединяя все вышесказанное, можно составить схему метода главных компонент,представленную в алгоритме 1.55x 104.543.532.521.510.500100200300400500600700800Рис. 4: Схема выбора размерности редуцированного пространства для метода главныхкомпонент.До сих пор предполагалось, что размерность редуцированного пространства d задаетсяпользователем заранее. Это значение легко выбрать в том случае, если стоит задачавизуализации данных (d = 2 или d = 3) или задача вложения выборки в заданный объем6памяти. Однако, во многих других случаях выбор d является далеко не очевидным изаприорных предположений.
Для метода главных компонент существует простой эвристическийприем выбора величины d. Одной из особенностью метода главных компонент является тотфакт, что все редуцированные пространства для d = 1, 2, . . . являются вложенными другв друга. В частности, однократное вычисление всех собственных векторов и собственныхзначений матрицы ковариации позволяет получить редуцированное пространство для любогозначения d. ∑При этом ошибка проектирования данных на соответствующую гиперплоскостьDсоставляетi=d+1 λi . Поэтому для выбора значения d можно отобразить на графикесобственные значения в порядке убывания (см. рис.
4) и выбрать порог отсечения такимобразом, чтобы справа остались значения, не значимо отличные от нуля. Другой способпредполагает выбор порога так, чтобы справа оставался определенный процент от общейплощади под кривой (например, 5% или 1%), т.е.∑Dλid : ∑i=d+1< η.Di=1 λiПлощадь под кривой определяется значением tr(S) и соответствует величине разброса вданных.2Вероятностный метод главных компонентДля метода главных компонент можно сформулировать вероятностную модель (probabilisticPCA, PPCA) (см. [3]).
Переформулирование метода в вероятностных терминах дает целый рядпреимуществ, а именно:• Возможность использования ЕМ-алгоритма для поиска решения. Для PCA ЕМ-алгоритмявляется вычислительно более эффективной процедурой в ситуациях, когда d ≪ D;• Корректная обработка пропущенных значений. Пропущенные значения простодобавляются в список скрытых переменных вероятностной модели, для которойзатем применяется соответствующий ЕМ-алгоритм;• Возможность перехода к модели смеси вероятностных распределений, котораязначительно расширяет область применимости метода (см.
[7]);• Возможность использования т.н. байесовского подхода для решения задач выбора моделейи, в частности, здесь можно построить теоретически обоснованную схему выбораразмерности редуцированного пространства d (см. [4, 5]);• Возможность генерирования новых объектов из вероятностной модели;• Для задач классификации возможность моделирования распределений отдельных классовобъектов для дальнейшего использования в различных схемах классификации;• Значение функции правдоподобия является универсальным критерием, позволяющимсравнивать различные вероятностные модели между собой.
В частности, в помощьюзначения правдоподобия можно легко определять выбросы в данных.7Рис. 5: Иллюстрация процесса генерации объекта в вероятностной модели PCA для D = 2 иd = 1. Наблюдаемое значение x образуется путем генерирования значения скрытой компонентыt из априорного распределения p(t) и последующего генерирования значения x из изотропногонормального распределения с центром µ + tw и матрицей ковариации σ 2 I.
Зеленые эллипсыпоказывают линии уровня плотности маргинального распределения p(x).Сформулируем вероятностную модель PCA следующим образом:x = W t + µ + ε.Здесь, как и раньше, W t + µ задает точку на гиперплоскости, а ε ∼ N (ε|0, σ 2 I) – нормальнораспределенная шумовая компонента с одинаковой дисперсией σ 2 по всем направлениямв пространстве RD . Символом N (x|µ, Σ) здесь и далее будет обозначаться плотностьмногомерного нормального распределения:)(11T −1N (x|µ, Σ) = √ D √exp − (x − µ) Σ (x − µ) .22πdet ΣВ качестве априорного распределения на значение координат объекта t в базисе гиперплоскостивыберем следующее:p(t) = N (t|0, I).Процесс генерации объекта x в заданной вероятностной модели показан на рис. 5.
Полноесовместное распределение в вероятностной модели PCA задается следующим образом:p(X, T |W, µ, σ) =N∏p(xn , tn |W, µ, σ) =n=1N∏N (xn |W tn + µ, σ 2 I)N (tn |0, I).n=1Здесь X – набор наблюдаемых переменных, T – набор скрытых переменных и (W, µ, σ) – наборпараметров модели.Для поиска значений параметров модели воспользуемся методом максимальногоправдоподобия:N∏p(X|W, µ, σ) =p(xn |W, µ, σ) → max .(2)W,µ,σn=1Маргинальное распределение p(xn ) в вероятностной модели PCA вычисляется как∫p(xn |W, µ, σ) = p(xn |tn , W, µ, σ)p(tn )dtn .8Последний интеграл представляет собой свертку двух нормальных распределений и может бытьвычислен аналитически:∫p(xn |W, µ, σ) = N (xn |W tn + µ, σ 2 I)N (tn |0, I)dtn = N (xn |µ, σ 2 I + W W T ).Таким образом, вероятностная модель PCA представляет собой нормальное распределение, вкотором матрица ковариаций задается специальным образомC = W W T + σ 2 I.(3)Заметим, что также как и классическая модель PCA, вероятностная модель PCA инвариантнаотносительно выбора базиса в гиперплоскости.
Пусть R ∈ Rd – произвольная ортогональнаяматрица, задающая поворот базиса гиперплоскости. Это соответствует использованию матрицыf = W R. Тогда матрица ковариаций равнаWfWfT + σ 2 I = W RRT W T + σ 2 I = W W T + σ 2 I.C=WТаким образом, матрица ковариаций не зависит от R.Вернемся теперь к задаче оптимизации (2). Эту задачу можно эквивалентно переписатьследующим образом:log p(X|W, µ, σ) =N∑log N (xn |µ, σ 2 I + W W T ) =n=1NDN1∑−log 2π − det(σ 2 I + W W T ) −(xn − µ)T (σ 2 I + W W T )−1 (xn − µ) → maxW,µ,σ222 n=1NМожно показать (см.
[7]), что данная задача оптимизации имеет аналитическое решение:N1 ∑µ=xn ,N n=1W = Q(Λ − σ 2 I)1/2 R,σ2 =(4)D∑1λi .D − d i=d+1Здесь Q = (q 1 | . . . |q d ) ∈ RD×d , q 1 , . . . , q d – собственные вектора выборочной матрицыковариации, отвечающие наибольшим собственным значениям λ1 ≥ λ2 ≥ · · · ≥ λd , Λ =diag(λ1 , . .
. , λd ), R – произвольная ортогональная матрица размера d × d.Рассмотрим подробнее решение (4). Заметим, что в отличие от классической моделиPCA, в которой восстанавливается только гиперплоскость, наилучшим образом объясняющаяданные, вероятная модель PCA восстанавливает всю модель изменчивости данных и, вчастности, дисперсии данных по всем направлениям. Поэтому решение (4) включает всебя не только направляющие базисные вектора гиперплоскости, задаваемые собственнымивекторами матрицыковариаций, но также и длины этих базисных векторов, определяемые√2значениями λi − σ (в предположении, что дисперсии скрытых компонент равны единице).Действительно, величина дисперсии данных вдоль направления v составляет v T Cv, гдеv T v = 1. Если v лежит в подпространстве, ортогональном гиперплоскости, то v T Cv = σ 2 .9Теперь пусть v совпадает с одним из собственных векторов q i .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
