Уменьшение размерности в данных. Метод главных компонент (1185332)
Текст из файла
Материалы к лекции«Уменьшение размерности в данных. Метод главныхкомпонент»по курсу «Математические основы теориипрогнозирования» 2010Рассмотрим задачу классификации изображений рукописных цифр MNIST1 . Пусть имеетсянекоторое количество черно-белых изображений, на каждом из которых представлена однацифра (см. рис.
1). Задача состоит в автоматическом определении цифры для входногоизображения.Рис. 1: Примеры изображений рукописных цифр из базы данных MNIST.Для того, чтобы применить методы распознавания в данной задаче, необходимопредварительно выбрать пространство признаков, характеризующее изображения цифр. Впростейшей случае в качестве признаков можно взять исходные интенсивности пикселовизображения. Тогда для изображения размера 28 × 28 получаем 784 признака.
Такой способформирования признакового пространства обладает рядом существенных недостатков. Вопервых, получается большое количество признаков. Например, для относительно небольшихизображений размера 300 × 200 получается 60000 признаков. Большое количество признаковприводит к высоким временным затратам на обработку данных, большим объемам памяти,требуемой для хранения информации, а также к необходимости сбора большого числапрецедентов для уверенного восстановления скрытых зависимостей в существенно многомерном1Исходные данные можно скачать по адресу http://yann.lecun.com/exdb/mnist/11’1’’2’’3’0.92’1’’2’’3’00.8-20.7Feature 3430.6-40.5-60.40.3-80.2-100.1000.20.40.6Feature 3420.8-1215(a)0-5(b)Рис. 2: Проекция выборки изображений цифр ’1’, ’2’ и ’3’ на два признака, соответствующихинтенсивностям пикселов (a) и на два признака, полученных с помощью метода главныхкомпонент (b).пространстве.
Другим серьезным недостатком полученного признакового пространстваявляется тот факт, что близкие в пространстве признаков объекты не соответствуют одним итем же классам (см. рис. 2a). Выполнение гипотезы компактности является одним из основныхтребований для большинства методов распознавания. Методы уменьшения размерности вданных позволяют получать представление выборок в маломерных пространствах, обладающихрядом хороших свойств. В частности, для изображений рукописных цифр метод главныхкомпонент позволяет получить существенно более качественное признаковое пространство (см.рис.
2b).DПусть имеется некоторая выборка объектов X = {xn }Nn=1 , xn ∈ R . Задача уменьшенияразмерности состоит в получении представления этой выборки в пространстве меньшейdразмерности T = {tn }Nn=1 , tn ∈ R . Здесь d ≪ D, но в частных случаях d может и совпадать сD. Уменьшение размерности в описании данных может преследовать множество целей:• Сокращение вычислительных затрат при обработке данных;• Борьба с переобучением. Чем меньше количество признаков, тем меньше требуетсяобъектов для уверенного восстановления скрытых зависимостей в данных и тем большекачество восстановления подобных зависимостей;• Сжатие данных для более эффективного хранения информации.
В этом случае помимопреобразования X → T требуется иметь возможность осуществлять также обратноепреобразование T → X;• Визуализация данных. Проектирование выборки на двух-/трехмерное пространствопозволяет графически представить выборку;• Извлечение новых признаков. Новые признаки, полученные в результате преобразованияX → T , могут оказывать значимый вклад при последующем решении задачраспознавания (например, как метод главных компонент в случае рис. 2b);2• и др.Заметим, что все описанные далее методы уменьшения размерности относятся к классуметодов обучения без учителя, т.е. в качестве исходной информации выступает толькопризнаковое описание объектов X. В частности, в задаче классификации рукописных цифррезультат, показанный на рис.
2b, был получен без использования информации о цифрах.1Метод главных компонентМетод главных компонент (разложение Карунена-Лоева, principal component analysis,PCA) является простейшим методом уменьшения размерности в данных, идеи котороговысказывались еще в 19 веке [1, 2]. Идея метода заключается в поиске в исходном пространствегиперплоскости заданной размерности с последующим проектированием выборки на даннуюгиперплоскость. При этом выбирается та гиперплоскость, ошибка проектирования данных накоторую является минимальной в смысле суммы квадратов отклонений.Рассмотрим произвольный ортонормированный базис в пространстве RD : w1 , .
. . , wD ,Twi wj = δij , где δij = [i = j] – символ Кронекера. Не ограничивая общности, будем считать,что первые d векторов этого базиса w1 , . . . , wd образуют базис искомой гиперплоскости. Тогдаточки гиперплоскости определяются какx = w1 t1 + · · · + wd td + µ = W t + µ,где t1 , . . . , td – координаты точки x в базисе гиперплоскости, W = (w1 | . .
. |wd ) ∈ RD×d –матрица, столбцы которой представляют собой базисные вектора w1 , . . . , wd , µ ∈ RD –вектор сдвига. Поиск гиперплоскости, обеспечивающей минимальную квадратичную ошибкупроектирования, может быть записан какJ=N∑∥xn − W tn − µ∥2 →n=1minw1 ,...,wd ,t1 ,...,td ,µ.(1)Введем следующие обозначения:x̄ =N1 ∑xn – выборочное среднее,N n=1N1 ∑S=(xn − x̄)(xn − x̄)T – выборочная матрица ковариации.N n=1Рассмотрим собственные вектора и собственные значения матрицы S: S = QΛQT , где Λ =diag(λ1 , . . .
, λD ), Q – ортогональная матрица (QT Q = I), в столбцах которой стоят собственныевектора. Предположим, без ограничения общности, что собственные значения отсортированыпо убыванию, т.е. λ1 ≥ λ2 ≥ · · · ≥ λD . Можно показать [1, 2] (см. Приложение A), что задачаоптимизации (1) имеет следующее аналитическое решение: w1 , . . . , wd – собственные вектораматрицы S, отвечающие d наибольшим собственным значениям λ1 ≥ λ2 ≥ ·∑· · ≥ λd , µ = x̄,tn = W T (xn − x̄). При этом значение критерия J в точке минимума равно Ni=d+1 λi .
Такимобразом, величина ошибки проектирования для оптимальной гиперплоскости составляет суммудисперсий данных по отбрасываемым размерностям, определяемым собственными векторамиwd+1 , . . . , wD .35.53524.5413.5302.5−121.5−210.51234−3−35−2(a)−10123(b)Рис. 3: Пример применения метода главных компонент.
На рис. a показана исходная выборкав двухмерном пространстве вместе с направлениеми, определяемыми собственными векторамивыборочной матрицы ковариации. На рис. b показан переход к некоррелированным признакам.Наряду с критерием минимизации ошибки проектирования можно рассмотретьальтернативный критерий поиска гиперплоскости, связанный с максимизацией разбросаспроектированных точек выборки. Пусть Ŝ – выборочная матрица ковариации дляспроектированных точек выборки. Тогда величину разброса можно определить как tr(Ŝ).В одномерном случае этот критерий совпадает с дисперсией данных.
Можно показать, чторешение задачиtr(Ŝ) →maxw1 ,...,wd ,t1 ,...,td ,µсовпадает с решениемзадачи (1). При этом для оптимальной гиперплоскости величина∑dкритерия tr(Ŝ) = i=1 λi , где, как и раньше, λi – собственные значения выборочной матрицыковариации S для исходной выборки.Итак, метод главных компонент предполагает переход от исходного базиса к базису изсобственных векторов матрицы ковариации S с дальнейшим отбрасыванием проекций выборкина собственные вектора, отвечающие D − d наименьшим собственным значениям.
В базисе изсобственных векторов матрица ковариации S имеет диагональный вид Λ = diag(λ1 , . . . , λD ).Таким образом, признаки, получаемые с помощью метода главных компонент, являютсянекоррелированными. Переход к некоррелированным признакам часто является разумнымметодом предобработки исходных данных. Поэтому метод главных компонент применяется и вслучае d = D.Рассмотрим простой модельный пример применения метода главных компонент. Пустьисходная выборка представляет собой данные в двухмерном пространстве (см. рис. 3a). Прииспользовании метода главных компонент центр координат нового пространства переноситсяв центр выборки, а оси определяются собственными векторами выборочной матрицыковариации (см. рис.
3b). Таким образом, новые признаки являются некоррелированными.В том случае, если d = 1, то дополнительно осуществляется проекция выборкина направление, соответствующее наибольшему собственному значению (направление снаибольшей дисперсией). Для данного примера это координата x.Гиперплоскость, которая находится с помощью метода главных компонент, определенаоднозначно в том случае, если λd > λd+1 . При этом остается произвол в выборе системы4Алгоритм 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 ; // Проектируем выборку на выбранные направлениякоординат в линейном пространстве, определяемом гиперплоскостью, т.е. выборе значенийT . Этот выбор не оказывает влияние на величину ошибки при восстановлении данных,которая определяется только самой гиперплоскостью.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
