Файл: Курсовая работа Научный Невоструев К. Н. СанктПетербург 2014 г.pdf

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математико-Механический факультет
Кафедра Системного Программирования
Сайфутдинов Руслан Айдарович
Исследование алгоритмов уменьшения размерности данных для задачи классификации
Курсовая работа
Научный руководитель:
Невоструев К. Н.
Санкт-Петербург
2014 г.

Содержание
Введение
3 1.1
Мотивация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 1.2
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 1.3
Доступные программные средства . . . . . . . . . . . . . . . . . . . . . . .
3 1.4
Обзор существующих работ
3 2
Алгоритмы уменьшения размерности
4 2.1
PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 2.2
ICA
6 2.2.1
FastICA для одной компоненты . . . . . . . . . . . . . . . . . . . .
7 2.2.2
FastICA для нескольких компонент . . . . . . . . . . . . . . . . . .
7 2.2.3
Свойства алгоритма FastICA . . . . . . . . . . . . . . . . . . . . . .
8 2.3
SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 3
SVM
10 3.1
Бинарная классификация . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10 3.2
Случай линейной неразделимости . . . . . . . . . . . . . . . . . . . . . . .
10 3.3
Мультиклассификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11 4
Сравнения
12 4.1
Методика тестирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 4.2
Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Заключение
14 2

Введение
1.1
Мотивация
В современном мире данные, такие как аудио, цифровые изображения, тексты, обыч- но имеют большую размерность. Для обработки таких данных, их размерность должна быть уменьшена. Уменьшение размерности — преобразование исходных данных с боль- шой размерностью в новое представление меньшей размерности, сохраняющее основ- ную информацию. В идеальном случае размерность преобразованного представления соответствует внутренней размерности данных. Внутренняя размерность данных — ми- нимальное число переменных, необходимое, чтобы выразить все возможные свойства данных.
Уменьшение размерности помогает смягчить влияние проклятия размерности и дру- гих нежелательных свойств пространств большой размерности. В результате умень- шение размерности способствует, среди прочего, классификации, визуализации и ком- прессии данных большой размерности. Традиционно, для уменьшения размерности используются алгоритмы, такие как Principal Component Analisys (PCA), Independent
Component Analisys (ICA), Singular Value Decomposition (SVD) и другие.
1.2
Постановка задачи
Цель работы состоит в обзоре существующих подходов и алгоритмов для умень- шения размерности данных. А также в проведении исследования зависимостей между количеством компонент, получившимся после уменьшения размерности, и эффективно- стью различных алгоритмов. В этой работе планировалось решить следующие задачи:
∙ Реализовать несколько алгоритмов уменьшения размерности данных
∙ Установить зависимость эффективности алгоритмов от количества получившихся компонент
1.3
Доступные программные средства
Все вычисления производились с использованием языка программирования Python 2.7
и библиотек numpy, scipy, libsvm.
1.4
Обзор существующих работ
При выполнении данной работы был проведён анализ существующих публикаций по схожим темам [10], [11], [12]. Но ни в одной из них не исследовалось поведение алгоритмов уменьшения размерности данных в зависимости от числа получивших после преобразования компонент. Поэтому было решено провести данное исследование.
3

2
Алгоритмы уменьшения размерности
2.1
PCA
PCA — метод, который проецирует данные на новую координатную систему меньшей размерности, определяемую собственными векторами и собственными числами матри- цы. Хотя существует несколько алгоритмов, работающих таким образом, PCA является наиболее популярным из них. По этой причине он включен в данное сравнение.
PCA включает в себя вычисление ковариационной матрицы данных, чтобы мини- мизировать избыточность и максимизировать дисперсию. Математически PCA опреде- ляется как ортогональное линейное преобразование и полагает все базисные векторы ортонормированной матрицей [1] [2].
исходное пространство данных
преобразованное пространство
PCA
Рис. 1: Principal Component Analisys
PCA работает с помощью нахождения собственных чисел и собственных векторов матрицы ковариации. Матрица ковариации используется, чтобы измерить, как много размерностей отличаются от среднего по отношению друг к другу. Ковариация двух случайных величин (размерностей) — мера их линейной зависимости:
cov(????, ???? ) = E [(???? − E????)(???? − E???? )] ,
где E[????] и E[???? ] — математическое ожидание случайной величины ???? и ???? соответствен- но. Для определенного набора данных мы можем записать:
cov(????, ???? ) =
????
∑︁
????=1
(????
????
− ¯
????)(????
????
− ¯
????)
????
,
где ¯
???? — среднее ????, ¯
???? — среднее ???? , а ???? — размерность данных. Матрица ковариации
— матрица ???? с элементами ????
????????
= cov(????, ????). Она центрирует данные, вычитая среднее из каждого объекта.
В ковариационной матрице точное значение не так важно, как его знак (т.е. поло- жительное или отрицательное). Если значение положительное, это означает, что обе координаты возрастают, то есть если значение координаты ???? растёт, то же самое про- исходит с координатой ???? . Если значение отрицательное, тогда если одна координата растёт, то другая уменьшается. В таком случае координаты в итоге примут противопо- ложные значения. В последнем случае, если ковариация равна нулю, две координаты
4

независимы друг от друга. По свойству коммутативности, ковариация ???? и ???? (cov(????, ???? ))
равна ковариации ???? и ???? (cov(????, ????)).
После того, как собственные векторы и собственные числа найдены, собственные числа сортируются в порядке убывания. Благодаря этому можно получить компоненты в порядке уменьшения значимости. Собственный вектор с самым большим собственным числом —самая главная компонента набора данных. Он выражает самые существенные отношения между координатами. Поэтому главные компоненты получаются умножени- ем строк из собственных векторов на отсортированные собственные значения.
Как было сказано ранее, PCA используется для уменьшения размерности с помощью нахождения главных компонент входных данных. Для этого с помощью собственных чисел и собственных векторов матрицы ковариации определяется лучшее простран- ство меньшей размерности. Лучшим пространством меньшей размерности называется пространство, имеющее минимальную ошибку между исходным набором данных и по- лученным по следующему критерию:
∑︀
????
????=1
????
????
∑︀
????
????=1
????
????
> Θ,
где ???? — выбранная новая размерность, Θ — порог, а ????
????
— собственные числа.
Основываясь на этом критерии, матрица ???? × ???? линейно преобразуется в матрицу
???? × ????. Хотя размерность матрицы уменьшилась после PCA, разница между исходной и полученной матрицами невелика.
PCA пытается найти линейное отображение ???? , которое максимизирует оценочную функцию tr(????
????
cov(????)???? ). Таким образом, PCA решает задачу:
cov(????)???? = ????????
Представление уменьшенной размерности ????
????
точек ????
????
находится с помощью линейного отображения ???? , ???? = ???????? .
Можно также искать отображение ???? , которое минимизирует оценочную функцию
????(???? ).
????(???? ) =
????
∑︁
????=1
????
∑︁
????=1
(????
2
????????
− ‖????
????
− ????
????
‖
2
),
где ????
????????
— евклидово расстояние между точками ????
????
и ????
????
, ‖????
????
− ????
????
‖ — евклидово расстояние между точками ????
????
и ????
????
, ????
????
= ????
????
???? , ‖????
????
‖
2
= 1 ∀????. Можно показать, что минимум этой оценочной функции получается из спектрального разложения матрицы Грама ???? =
????????
????
данных большой размерности. Значения матрицы Грама могут быть получены двойным центрированием квадратов попарных расстояний ????
????????
. То есть вычислением:
????
????????
= −
1 2
(︃
????
2
????????
−
1
????
????
∑︁
????=1
????
2
????????
−
1
????
????
∑︁
????=1
????
2
????????
+
1
????
2
????
∑︁
????=1
????
∑︁
????=1
????
2
????????
)︃
Минимум оценочной функции ???? теперь может быть получен умножением собственных векторов дважды центрированной матрицы евклидовых расстояний (то есть собствен- ных векторов матрицы Грама) на корень из соответствующих собственных чисел.
Похожесть между этими двумя постановками задачи PCA связана с отношением между собственными векторами матрицы ковариации и матрицы Грама: можно пока- зать, что собственные векторы ????
????
и ????
????
матриц ????
????
???? и ????????
????
удовлетворяют равенству
√
????
????
????
????
= ????????
????
[3]. Эта связь описывается более подробно, например, в [4].
5

PCA может быть успешно использован для распознования лиц [5], анализа движе- ний, классификации [6]. Но у PCA есть два основных недостатка.
Во-первых, в PCA размер ковариационной матрицы прямо пропорционален размер- ности входных данных. Из-за этого поиск собственных векторов может быть невозмо- жен для очень больших размерностей данных.
Во-вторых, оценочная функция ???? показывает, что PCA фокусируется в основном на сохранении больших попарных расстояний ????
2
????????
, вместо того чтобы фокусироваться на сохранении маленьких попарных расстояний, которые являются более важными.
2.2
ICA
Метод независимых компонент получил широкое распространение при обработке сигналов. Это статистическая техника общего назначения, которая пытается линей- но преобразовать исходные данные в новые компоненты, которые будут максималь- но независимы друг от друга в статистическом смысле. Независимые компоненты не обязательно ортогональны друг другу, но статистически независимы. Это более стро- гое условие, чем статистическая некоррелированность, которая используется в PCA. В
данной работе используется реализация FastICA [7]. FastICA известен как надежный и эффективный алгоритм обнаружения лежащих в основе независимых компонент дан- ных для широкого диапазона распределений. Математические детали FastICA могут быть найдены в [7]. В практическом применении FastICA требуется два шага предва- рительной обработки. Во-первых, центрирование, то есть вычитание среднего из дан- ных. Во-вторых, «отбеливание» (whitening), которое означает линейное преобразование вектора ???? в новый вектор, такой что его координаты не коррелированы, а дисперсия координат равна единице.
Критерием независимости в FastICA является негауссовость, которая измеряется с помощью коэффициента эксцесса:
kurt(????) = E[????
4
] − 3(E[????
2
]
2
)
Для гауссовых случайных величин он равна нулю, поэтому FastICA пытается макси- мизировать это значение. Если
̃︀
???? —
«отбеленные» данные, то матрица ковариации
«отбеленных» данных — единичная матрица.
E
[︀
̃︀
????
̃︀
????
????
]︀ = ????
Такое преобразование всегда возможно. Популярный метод «отбеливания» использует спектральное разложение матрицы ковариации E[????????
????
] = ????????????
????
, где ???? — ортогональ- ная матрица собственных векторов, а ???? — диагональная матрица собственных чисел,
???? = diag(????
1
, . . . , ????
????
). Теперь «отбеливание» может быть выполнено как
̃︀
???? = ????????
−1/2
????
????
????,
где матрица ????
−1/2
вычисляется простой покомпонентной операцией, как
????
−1/2
= diag(????
−1/2 1
, . . . , ????
−1/2
????
)
6

2.2.1
FastICA для одной компоненты
Итеративный алгоритм ищет направление весового вектора ????, максимизируя негаус- совость проекции ????
????
???? данных ????. Функция ????(????) — производная неквадратичной нели- нейной функции ???? (????). В [7] автор даёт хорошие функции ???? :
???? (????) = log cosh ????
???? (????) = −????
−????
2
/2
Их первые и вторые производные:
????(????) = tanh(????)
????
′
(????) = 1 − tanh
2
(????)
????(????) = ????????
−????
2
/2
????
′
(????) = (1 − ????
2
)????
−????
2
/2
Первая функция хорошо подходит для общего назначения, тогда как вторая более устойчива к различным выбросам.
Базовый алгоритм FastICA заключается в следующем:
1. Выбрать начальный (случайный) вектор ????.
2. ????
+
= E
[︀????????(????
????
????)
]︀ − E [︀????
′
(????
????
????)
]︀ ????.
3. ???? =
????
+
‖????
+
‖
4. Если последовательность ???? не сошлась, перейти к шагу 2.
Сходимость означает, что старые и новые значения вектора ???? совпадают, то есть их скалярное произведение почти равно единице. На практике математические ожидания должны быть заменены их оценками. Естественными оценками являются средние зна- чения. В идеальном случае все доступные данные должны использоваться, но часто это не очень хорошая идея, потому что вычисления могут стать слишком требовательны- ми к ресурсам. Тогда могут быть получены усредненные результаты с использованием только части данных, размер которой значительно влияет на итоговый результат. Если сходимость неудовлетворительна, нужно увеличить размер рассматриваемых данных.
2.2.2
FastICA для нескольких компонент
Алгоритм в предыдущем пункте находит только одну из независимых компонент или одно направление наилучшей проекции. Для того, чтобы получить несколько неза- висимых компонент алгоритм должен быть повторён несколько раз. Чтобы избеж- дать схождения разных векторов к одному и тому же максимуму, полученные векторы
????
????
1
????, . . . , ????
????
????
???? должны быть декоррелированы после каждой итерации. Существует три метода, чтобы это сделать. Простой способ достижения декорреляции основан на орто- гонализации Грама-Шмидта. Независимые компоненты вычисляются последователь- но. Когда найдено ???? независимых компонент или ???? векторов ????
1
, . . . , ????
????
, запускается алгоритм для одной компоненты ????
????+1
, и после каждой итерации вычитается из ????
????+1
«проекции» ????
????
????+1
????
????
????
????
, ???? = 1, . . . , ???? предыдущих найденных векторов, после чего ????
????+1
нормализуется:
1. ????
????+1
= ????
????+1
−
????
∑︀
????=1
????
????
????+1
????
????
????
????
2. ????
????+1
= ????
????+1
/
√︁
????
????
????+1
????
????+1 7

Иногда, однако, возникает желание использовать симметричную декорреляцию, когда ни один вектор не «привилегирован» по сравнению с другими. Это может быть осу- ществлено, например, классическим методом с использованием матричных квадратных корней:
???? = (???? ????
????
)
−1/2
????,
где ???? матрица (????
1
, . . . , ????
????
)
????
векторов, а обратный квадратный корень (???? ????
????
)
−1/2
по- лучается из спектрального разложения ???? ????
????
= ???? ????????
????
, как (???? ????
????
)
−1/2
= ???? ????
−1/2
????
????
Более простая альтернатива — следующий итерационный алгоритм:
1. ???? =
????
√
‖???? ????
????
‖
2. ???? =
3 2
???? −
1 2
???? ????
????
????
3. Повторять 2 до тех пор, пока не сойдётся.
Норма в шаге 1 может быть практически любой обыкновенной матричной нормой, на- пример наибольшей по модулю суммой строки или столбца.
2.2.3
Свойства алгоритма FastICA
Алгоритм FastICA имеет несколько важных свойств по сравнению с другими суще- ствующими алгоритмами ICA:
1. Кубическая сходимость (или хотя бы квадратичная), в отличие от других алго- ритмов ICA, основанных на методе градиентного спуска, где сходимость только линейная.
2. По сравнению с алгоритмами, основанными на градиентном спуске, не нужно выбирать параметр размера шага. Это делает FastICA легким в использовании.
3. Алгоритм находит независимые компоненты практически любого негауссового распределения, используя любую нелинейную функцию ????.
4. Независимые компоненты вычисляются одна за другой, что приблизительно эк- вивалентно методу поиска наилучшей проекции.
5. Производительность алгоритма может быть оптимизирована выбором подходя- щей нелинейной функции ????.
2.3
SVD
В линейной алгебре сингулярное разложение — факторизация вещественной или комплексной матрицы с множеством полезных применений в обработке сигналов и ста- тистике.
Пусть матрица ???? порядка ???? × ???? состоит из элементов из поля ????, где ???? —– либо поле вещественных чисел, либо поле комплексных чисел.
Неотрицательное вещественное число ???? называется сингулярным числом матрицы
???? тогда и только тогда, когда существуют два вектора единичной длины ???? ∈ ????
????
и
???? ∈ ????
????
такие, что:
???? ???? = ????????,
????
*
???? = ????????
8

Такие векторы ???? и ???? называются, соответственно, левым сингулярным вектором и пра- вым сингулярным вектором, соответствующим сингулярному числу ????.
Сингулярным разложением [8] матрицы ???? порядка ???? × ???? является разложение следующего вида:
???? = ???? Σ????
*
,
где Σ —– размера ???? × ????, у которой элементы, лежащие на главной диагонали — это сингулярные собственные числа (а все элементы, не лежащие на главной диагонали,
являются нулевыми), а матрицы ???? (порядка ????) и ???? (порядка ????) —– это две унитарные матрицы, состоящие из левых и правых собственных сингулярных векторов соответ- ственно (а ????
*
—– это сопряжённо-транспонированная матрица к ???? ). Причем диаго- нальные элементы ????
????
матрицы Σ упорядоченны следующим образом:
Σ = diag(????
1
, ????
2
, . . . , ????
????
)
????
1
> ????
2
> . . . > ????
????
= . . . = ????
????
= 0,
где ???? = rank(????). В частности, ‖????‖ = ????
1
Пусть матрице ???? поставлен в соответствие линейный оператор. Сингулярное раз- ложение можно переформулировать в геометрических терминах. Линейный оператор,
отображающий элементы пространства R
????
в себя, представим в виде последователь- но выполняемых линейных операторов вращения и растяжения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отоб- ражении линейным оператором ???? множества векторов из векторного пространства в себя или в векторное пространство другой размерности.
Для уменьшения размерности данных требуется приближение заданной матрицы ????
некоторой другой матрицей ????
????
с заранее заданным рангом ???? [9]. Известна следующая теорема, которую иногда называют теоремой Эккарта – Янга.
Если потребовать, чтобы такое приближение было наилучшим в том смысле, что норма Фробениуса разности матриц ???? и ????
????
минимальна при ограничении rank(????
????
) =
????, то оказывается, что наилучшая такая матрица ????
????
получается из сингулярного раз- ложения матрицы ???? по формуле:
????
????
= ???? Σ
????
????
*
,
где Σ
????
– матрица Σ, в которой заменили нулями все диагональные элементы, кроме ????
наибольших элементов.
Σ = diag(????
1
, ????
2
, . . . , ????
????
, 0, . . . , 0)
Если элементы матрицы Σ упорядочены по невозрастанию, то выражение для мат- рицы ????
????
можно переписать в такой форме:
????
????
= ????
????
Σ
????
????
*
????
где матрицы ????
????
, Σ
????
и ????
????
получаются из соответствующих матриц в сингулярном раз- ложении матрицы ???? обрезанием до ровно ???? первых столбцов.
Таким образом видно, что приближая матрицу ???? матрицей меньшего ранга, мы выполняем своего рода сжатие информации, содержащейся в ???? : матрица ???? размера
????×???? заменяется меньшими матрицами размеров ????×???? и ????×???? и диагональной матрицей с ???? элементами. При этом сжатие происходит с потерями — в приближении сохраняется лишь наиболее существенная часть матрицы ???? .
9