5 Уменьшение размерности описания данных - метод главных компонент (1162173), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Nn=1 xn = 0. ТогдаNNN∑1 ∑1 ∑ TT 1Et =tn =u xn = uxn = 0,N n=1N n=1N n=11NN1 ∑1 ∑ T1 2Dt =(tn − Et ) =u xn xTn u = uT Su.N n=1N n=11Таким образом, задача максимизации дисперсии данных на прямой совпадает с задачейоптимизации (1). Следовательно, оптимальная прямая определяется собственным векторомматрицы S, отвечающим наибольшему собственному значению λmax .Рассмотрим случай произвольного значения d. Характеристикой разброса данных вмногомерном пространстве является выборочная матрица ковариации. В качестве скалярногокритерия разброса выберем след выборочной матрицы ковариации, что эквивалентно суммевыборочных дисперсий по ортогональным направлениям u1 , .

. . , ud . Тогда можно показать,что максимизация следа выборочной матрицы ковариации приводит к решению (6). При этомзначение критерия составляетdd∑∑iJ=Dt =λi .i=1i=1Здесь λ1 ≥ λ2 ≥ · · · ≥ λD .Итак, метод главных компонент предполагает переход от исходного базиса к базису изсобственных векторов матрицы ковариации S с дальнейшим отбрасыванием проекций выборкина собственные вектора, отвечающие D − d наименьшим собственным значениям. В базисе изсобственных векторов матрица ковариации S имеет диагональный вид Λ = diag(λ1 , . .

. , λD ).Таким образом, признаки, получаемые с помощью метода главных компонент, являютсянекоррелированными. Переход к некоррелированным признакам часто является разумным62’1’’2’’3’0-2-4-6-8-10-1250-5Рис. 6: Метод главных компонент может быть использован для решения задачи идентификации.методом предобработки исходных данных.

Поэтому метод главных компонент применяется и вслучае d = D.Рассмотрим простой модельный пример применения метода главных компонент. Пустьисходная выборка представляет собой данные в двухмерном пространстве (см. рис. 5a). Прииспользовании метода главных компонент центр координат нового пространства переноситсяв центр выборки, а оси определяются собственными векторами выборочной матрицыковариации (см. рис. 5b).

Таким образом, новые признаки являются некоррелированными.В том случае, если d = 1, то дополнительно осуществляется проекция выборкина направление, соответствующее наибольшему собственному значению (направление снаибольшей дисперсией). Для данного примера это координата x.Решение задачи идентификацииИнтерпретация метода главных компонент с помощью разброса данных позволяет использоватьего для решения задачи идентификации. Мы знаем, что d наибольших собственных значенийλi выборочной матрицы ковариации определяют дисперсии выборки Dti вдоль направлений ui .Из неравенства Чебышева следует, что вероятность отклонения случайной величины от своегоматематического ожидания на k стандартных отклонения не превышает 1/k 2 .

Следовательно,с вероятностью не выше 1/k 2 значение i-ого признака для n-ого объекта в редуцированномпространстве находится в доверительном интервале√√−k λi ≤ tni ≤ k λi .Если дополнительно известно, что случайная величина ti является нормальной илиприближенно нормальной, то доверительный интервал значительно сокращается. В частности,вероятность отклонения на 3 стандартных отклонения составляет всего 0.3%. Этот результатизвестен как «правило трех сигма».Таким образом, если оказалось, что тестовый объект после проектирования на u1 , . . .

, udимеет хотя бы одно значение проекции, которое не укладывается в доверительный интервал,то это является поводом признать этот объект не соответствующим генеральной совокупностиобъектов, представленной в обучающей выборке. На рис. 6 показан пример идентификациис помощью метода главных компонент. Рассматривается задача распознавания рукописных755x 104.543.532.521.510.500100200300400500600700800Рис. 7: Схема выбора размерности редуцированного пространства для метода главныхкомпонент.цифр с классами ’1’, ’2’, ’3’. Изображение, соответствующее цифре ’4’, не укладывается вдоверительный интервал проекций по первым двум собственным векторам.Выбор размерности редуцированного пространства dДо сих пор предполагалось, что размерность редуцированного пространства d задаетсяпользователем заранее. Это значение легко выбрать в том случае, если стоит задачавизуализации данных (d = 2 или d = 3) или задача вложения выборки в заданный объемпамяти.

Однако, во многих других случаях выбор d является далеко не очевидным изаприорных предположений. Для метода главных компонент существует простой эвристическийприем выбора величины d. Одной из особенностью метода является тот факт, что всередуцированные пространства для d = 1, 2, . . .

, D являются вложенными друг в друга.В частности, однократное вычисление всех собственных векторов и собственных значенийвыборочной матрицы ковариации S позволяет получить редуцированное пространстводля любого значения d. При этом ошибка∑D проектирования данных на соответствующуюгиперплоскость определяется величинойi=d+1 λi . Поэтому для выбора значения d можноотобразить на графике собственные значения в порядке убывания (см.

рис. 7) и выбратьпорог отсечения таким образом, чтобы справа остались значения, незначимо отличные от нуля.Другой способ предполагает выбор порога так, чтобы справа оставался определенный процентот общей площади под кривой (например, 5% или 1%), т.е.∑Dλid : ∑i=d+1< η.Di=1 λiПлощадь под кривой определяется значением tr(S) и соответствует величине разброса вданных.Эффективные вычисления при D > N8Алгоритм 1 Схема метода главных компонентВход: X ∈ RN ×D – исходная выборка данных, d – размерность редуцированного пространстваВыход: ∑T ∈ RN ×d – представление выборки в редуцированном пространстве// Вычисляем выборочное среднееx̄ = N1 Nn=1 xn ;xn ← xn − x̄; // Переносим начало координат в центр выборкиесли N > D тоS = N1 X T X; // Вычисляем выборочную матрицу ковариацииS = QΛQT , Λ = diag(λ1 , .

. . , λD ), QT Q = I, Q = (q 1 | . . . |q D ); // Находим собственныевектора и собственные значения матрицы ковариацииВыбираем d наибольших собственных значений λ1 ≥ λ2 ≥ . . . λd и соответствующие имсобственные вектора W = (q 1 | . . . |q d );иначеS = N1 XX T ;S = QΛQT , Λ = diag(λ1 , . . . , λD ), QT Q = I, Q = (q 1 | . . . |q D ); // Находим собственныевектора и собственныезначения() матрицы SQ ← √1N X T Qdiag √1λ1 , . . . , √λ1 D ; // Переходим к нормированным собственным векторамвыборочной матрицы ковариацииВыбираем собственные вектора, соответствующие d наибольшим собственным значениямW = (q 1 | . . . |q d );T = XW ; // Проектируем выборку на выбранные направленияПри использовании метода главных компонент необходимо вычислять выборочную матрицуковариации, которая имеет размер D × D, а также ее собственные вектора и собственныезначения.

Сложность этих операций составляет O(N D2 ) и O(D3 ). В том случае, если D > N , тосуществует способ более экономного вычисления собственных векторов и собственных значенийматрицы ковариации с помощью матрицы размера N × N и сложностью, соответственно,O(DN 2 ) и O(N 3 ). Действительно, в пространстве размерности D множество из N точекпорождает линейное многообразие максимальной размерности N − 1.

Поэтому не имеет смыслаприменять метод главных компонент для d > N − 1. С точки зрения матрицы ковариации этоозначает, что только N − 1 собственных значений отличны от нуля. Все остальные собственныевектора не имеет смысла вычислять, т.к. дисперсия выборки вдоль этих направлений заведоморавна нулю.∑Пусть X ∈ RN ×D – исходная выборка с нулевым центром, т.е. N1 Nn=1 xn = 0. Тогда1Tвыборочная матрица ковариации S = N X X. Рассмотрим собственные вектора и собственныезначения матрицы S:1 TX Xq i = λi q i .NДомножим обе части этого уравнения на X слева:1XX T (Xq i ) = λi (Xq i ).NОбозначая v i = Xq i , получаем(7)1XX T v i = λi v i .(8)NТаким образом, матрица N1 XX T размера N × N имеет те же собственные значения, что ивыборочная матрица ковариации S (у которой, в свою очередь, есть D − N дополнительных9x2f2f1x1Рис.

8: Иллюстрация ядрового метода главных компонент.нулевых собственных значений). Сложность поиска собственных значений и собственныхвекторов матрицы 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 .

Характеристики

Список файлов лекций