2010 Лекции МОТП (Ветров) (1185317), страница 14
Текст из файла (страница 14)
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиПусть имеется некоторая выборка X = {xn }Nn=1 , xn ∈ RD .Цель — представить выборку в пространстве меньшейразмерности d < D, причем в новом пространстве «схожие»объекты должны образовывать компактные области.Причины сокращения размерности:• уменьшение вычислительных затрат при обработкеданных• борьба с переобучением• сжатие данных для более эффективного храненияинформации• визуализация данных• извлечение признаков• интерпретация данных• ...План лекцииЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.1 Метод главных компонент (PCA)Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие модели2 Вероятностный метод главных компонентВероятностная формулировка методаEM-алгоритм для PCAВыбор числа главных компонент с помощью байесовского п3 Другие моделиИдея методаЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентИдея метода главных компонент (разложениеКарунена-Лоева, Principal Component Analysis, PCA) —проекция данных на гиперплоскость с наименьшейошибкой проектирования. Эквивалентная формулировка:поиск проекции на гиперплоскость с сохранением большейчасти дисперсии в данных.7Другие модели6543210-1-2-50510Иллюстрация решения PCAЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Выборка висходном пространствеВыборка в пространстведекоррелированных признаков35.5Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонент524.5413.53Другие модели→2.50−121.5−210.512345−3−3−2−1012• Переносим начало координат в центр выборки• Поворачиваем оси координат так, чтобы признакистали декоррелированными• Отбрасываем направления с низкой дисперсией3Линейное преобразованиеЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиПусть D — размерность исходного пространства, d —размерность искомого пространства. Будем искатьпреобразование данных в семействе линейных функций:x = µ + t1 w1 + · · · + td wd = Wt + µЗдесь x ∈ RD , t ∈ Rd — новые координаты объекта,W = (w1 | . . . |wd ) ∈ RD×d , µ ∈ RD .Графическая интерпретация — проекция данных нагиперплоскость, w1 , . .
. , wd — базис гиперплоскости.Критерий поиска гиперплоскостиЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентКритерий выбора гиперплоскости — минимальная ошибкапроектирования в смысле суммы квадратов отклоненийисходных точек и их проекций.Пусть w1 , . . . , wD — ортонормированный базис впространстве RD , первые d компонент которого — базисискомой гиперлоскости.ТогдаДругие моделиxn =DX(xTn wi )wi — исходные точкиi=1x̂n =dXtni wi +i=1DXµi wi — приближениеi=d+1КритерийJ=N1Xkxn − x̂n k2 →minw1 ,...,wd ,t1 ,...,tN ,µNn=1Решение задачиЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.J=N1Xkxn − x̂n k2 →minw1 ,...,wd ,t1 ,...,tN ,µNn=1Можно показать, что решением задачи будет следующее:Метод главныхкомпонент (PCA)N1 Xxn — выборочное среднееNВероятностныйметод главныхкомпонентx̄ =Другие моделиN1 X(xn − x̄)(xn − x̄)T — выборочная матрица ковариацииS=Nn=1n=1w1 , .
. . , wd — ортонормированный базис из собственныхвекторов матрицы S, отвечающих d наибольшимсобственным значениям λ1 ≥ λ2 ≥ · · · ≥ λd .tni = xTn wiµi = x̄T wiПреобразование критерия IЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиà DNNdX1X X T1 X2J=kxn − x̂n k =(xn wi )wi −tni wi −NNn=1n=1 i=1i=1!T à D!DdDXXXXT−µi wi(xn wi )wi −tni wi −µi wi =i=1i=d+11NNXà DXn=1i=1i=1(xTn wi )2 +dX2tni+i=12dXi=1(xTn wi )tnii=d+1DXµ2i −i=d+1−2DX!µi (xTn wi )i=d+1∂: −2(xTn wi ) + 2tni = 0 ⇒ tni = xTn wi∂tni1 XN∂ XN:(−2(xTn wi ) + 2µi ) = 0 ⇒ µi =xTn wi = x̄T win=1n=1∂µiNПреобразование критерия IIЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.tni = xTn wi ,Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентxn − x̂n =µi = x̄T wiDX©ª(xn − x̄)T wi wii=d+1Другие моделиNDDX1 X X TT2(xn wi − x̄ wi ) =wTi Swi → minJ=wd+1 ,...,wDNn=1 i=d+1PNi=d+1Здесь S = N1 n=1 (xn − x̄)(xn − x̄)T — выборочная матрицаковариации данных.Решение IЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.J=Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиDXwTi Swi →i=d+1minwd+1 ,...,wDwTi wj = δijМожно показать, что оптимум достигается, когда вкачестве wd+1 , . . . , wD выбираются собственные вектораматрицы ковариации S, отвечающие наименьшимсобственным значениям λd+1 ≥ · · · ≥ λD . ТогдаJ=DXi=d+1λiРешение IIЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Рассмотрим оптимизацию по wi :J̃ = wTi Swi → minwiwTi wi = 1Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиФункция Лагранжа:L = wTi Swi + λi (1 − wTi wi ) → extrПриравнивая производную к нулю, получаем:Swi = λi wiПодставляя обратно в критерий, получаем:J̃ = wi Swi = λiАльтернативная интерпретация PCAЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентРассмотрим в качестве критерия проектированиямаксимизацию дисперсии спроектированных данных.Пусть d = 1, т.е. необходимо найти некоторое направлениеw1 : wT1 w1 = 1. Каждый объект выборки xn проектируется вwT1 xn . Тогда дисперсия проекций вычисляется какN1X T(w1 xn − wT1 x)2 = wT1 Sw1NДругие моделиn=1Здесьx=N1Xxi ,Nn=1S=N1 X(xn − x)(xn − x)TNn=1Альтернативная интерпретация IIЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиТеперь необходимо максимизировать дисперсию проекцийwT1 Sw1 при ограничении wT1 w1 = 1.
Таким образом, мыприходим к точно такому же критерию, который возникалв случае минимизации невязки. Максимальная дисперсиядостигается для собственного вектора выборочной матрицыковариации, отвечающего максимальному собственномузначению.Рассматривая аналогично проектирование на новыенаправления, ортогональные уже найденным, получим, чтонаилучшее d-мерное линейное подпространствоопределяется собственными векторами выборочнойматрицы ковариации, отвечающие d максимальнымсобственным значениям.Пример с распознаванием рукописных цифрЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Проекция данных на первые два признака (двасобственных вектора матрицы ковариации, отвечающихнаибольшим собственным значениям).1500Метод главныхкомпонент (PCA)1000Другие модели500Feature 2Вероятностныйметод главныхкомпонент’1’’2’’3’0−500−1000−1500−2000−2000−1500−1000−5000Feature 150010001500Интерпретация новых признаковЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентПо построению каждой точке x ∈ RD соответствуетнекоторая картинка. Новые признаки t ∈ Rd — проекции навыбранные направления (собственные вектора). Изменениеодного признака в новом пространстве Rd соответствуетдвижению вдоль собственного вектора в исходномпространстве RD .Движение вдоль первого признака:Другие моделиИнтерпретация: изменение ширины цифрыДвижение вдоль второго признака:Интерпретация: изменение характерного наклона цифрыВыбор размерности подпространства d вPCAЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.55x 104.543.532.52Метод главныхкомпонент (PCA)1.51Вероятностныйметод главныхкомпонент0.500100200300400500600700800Другие модели• Рассматриваем собственные значения в порядкеубывания λ1 ≥ λ2 ≥ . .
. λDPD• Выбираем d так, чтоdXi=1i=d+1λi ¿λi ≥ γDXPdi=1λi либо, чтобыλii=1Здесь γ — доля объясняемой дисперсии, типичныезначения 0.95, 0.99.Неоднозначность решения PCAЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие модели• Если все собственные значения выборочной матрицыковариации различны, т.е. λ1 > λ2 > · · · > λD , тоортонормированный базис из собственных векторовопределен однозначно, т.е. гиперплоскость проекцииопределена однозначно. Тем не менее, в полученнойгиперплоскости базис может быть выбранпроизвольным образом.• Если существуют одинаковые собственные вектора, тотогда гиперплоскость проекции определена неоднозначно.В PCA существует произвол в выборе координатобъектов в новом пространствеПлан лекцииЛекция 6.Снижениеразмерности вданных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
