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

3
SVM
В данной работе для решения задачи классификации был применён метод опорных векторов (SVM). Была использована реализация из библиотки libsvm языка Python 2.7.
3.1
Бинарная классификация
Зазор
Опорный вектор
Опорный вектор
Разделяющая
гиперплоскость
Рис. 2: Разделяющая гиперплоскость
Метод опорных векторов основан на поиске разделяющей гиперплоскости с наи- большим зазором [13]. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей наши классы. Разделяющей гиперплоскостью будет ги- перплоскость, максимизирующая расстояние до двух параллельных гиперплоскостей.
Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классифи- катора.
3.2
Случай линейной неразделимости
Рис. 3: Преобразование пространства с помощью ядра
Не всегда данные бывают линейно разделимы. Поэтому часто используется пре- образование пространства с помощью ядра. Используя такое преобразование, можно получить новое пространство, в котором данные будут линейно разделимы. В данной работе использовалось ядро ???????????? :
????(????, ????
′
) = ????
−
‖
????−????′
‖
2 2
2????2
,
где ‖???? − ????
′
‖
2 2
— евклидова норма, а ???? — параметр.
10

3.3
Мультиклассификация
Для решения задачи мультиклассфикации применяют сведение её к задаче бинар- ной классификации. Для этого существует два основных метода: один-против-всех и каждый-против-каждого [14]. В первом случае строятся классификаторы, которые от- личают объекты своего класса от всех остальных. Для классификации произвольного объекта нужно выбрать классификатор с максимальным результатом. Во втором слу- чае же строится по классификатору для каждой пары классов. Для классификации произвольного объекта все классификаторы голосуют за один из классов, после чего выбирается класс, набравший наибольшее число голосов.
11

4
Сравнения
4.1
Методика тестирования
Все описанные выше алгоритмы уменьшения размерности были реализованы на языке Python 2.7 с использованием библиотек numpy, scipy. В качестве задачи класси- фикации было выбрано распознавание рукописных цифр из базы MNIST [15], которая состоит из 60 000 изображений в тренировочной выборке и 10 000 изображений в те- стовой выборке. Каждое изображение имеет одну компоненту цвета и размер 28 × 28
пикселей (всего 784 признака). Для тестирования был использован компьютер с про- цессором Intel Core i7 с тактовой частотой 2.9 ГГц и 8 ГБ оперативной памяти.
В качестве метрики точности была использована оценка ????
1
[16]:
????
1
= 2 ·
precision · recall precision + recall
,
где precision — отношение количества верно распознанных объектов заданного класса к количеству объектов распознанных как заданный класс, а recall — отношение коли- чества верно распознанных объектов заданного класса к общему количеству объектов этого класса.
4.2
Результаты
0 50 100 150 200 250 300 350 400 0.94 0.96 0.98
количество компонент
F1
Score
PCA
ICA
SVD
None
Рис. 4: Точность
На рисунке 4 показано изменение оценки ????
1
в зависимости от получившейся после преобразования размерности данных. Видно, что все алгоритмы показывают наиболь- шую точность при достаточно маленьком количестве оставшихся компонент, поряд- ка 10%. С увеличением количества компонент точность после применения алгоритмов
PCA и SVD практически не изменяется, а после применения ICA начинает линейно падать. Это связано с тем, что FastICA не может выделить такое большое количество независимых компонент и перестаёт сходиться, из-за чего данные становятся линейно неразделимыми. Серой линией показана точность классификации без использования алгоритмов предварительной обработки данных. PCA также помогает немного увели- чить точность.
12

0 100 200 300 400 0
200 400 600 800
количество компонент время,
сек
PCA
ICA
SVD
Рис. 5: Время работы
0 100 200 300 400 0
200 400 600 800
количество компонент время,
сек
PCA
ICA
SVD
None
Рис. 6: Время обучения
0 100 200 300 400 0
50 100 150
количество компонент время,
сек
PCA
ICA
SVD
None
Рис. 7: Время классификации
0 100 200 300 400 0
500 1,000 1,500
количество компонент время,
сек
PCA
ICA
SVD
None
Рис. 8: Суммарное время работы
Время работы PCA не зависит от количества получившихся компонент, только от размера исходных данных. Время работы SVD растёт линейно, как и время работы SVM
после его применения. В отличие от них время работы FastICA растёт нелинейно. Более того, начиная с некоторого момента SVM после FastICA начинает работать дольше, чем без него. Это связано, опять же, с тем, что FastICA не может выделить необходимое число независимых компонент.
13

Заключение
В данной работе были реализованы алгоритмы PCA, FastICA и SVD, было рас- смотрено применение SVM для решения задачи классификации. Была исследована их эффективность при решении задачи классификации в зависимости от количества ком- понент, оставшихся после уменьшения размерности пространства данных. Было обна- ружено, что алгоритм FastICA деградирует с увеличением количества компонент, при- чем нелинейно. PCA же способен немного повысить точность классификации. Точность же, полученная после применения алгоритмов PCA и SVD, практически не зависит от количества компонент, а время их работы растёт линейно. Поэтому оптимальным вы- бором для новой размерности данных будет небольшое количество компонент, порядка
10% от первоначального, когда все рассмотренные алгоритмы показывают наилучшие результаты.
14

Список литературы
[1] I. T. Jolliffe. Principal Component Analysis, Second Edition. Springer, 2002.
[2] H. Hotelling. Analysis of a complex of statistical variables into components. Journal of
Educational Psychology, 1933.
[3] C. Chatfield and A.J. Collins. Introduction to Multivariate Analysis. Chapman and
Hall, 1980.
[4] C.K.I. Williams. On a connection between Kernel PCA and metric multidimensional scaling. Machine Learning, 2002.
[5] M. Turk and A. Pentland. Face recognition using eigenfaces. Computer Vision and
Pattern Recognition, 1991.
[6] Yehuda Koren and Liran Carmel.
Visualization of labeled data using linear transformations. IEEE Computer Society, 2003.
[7] A. Hyv¨
arinen and E. Oja.
Independent Component Analysis: Algorithms and
Applications. Cambridge University Press, 1991.
[8] P. C. Hansen.
Numerical Recipes in C. 2nd edition, chapter Singular Value
Decomposition. BIT, 1987.
[9] P. C. Hansen. The Truncated SVD as a method for regularization. BIT, 1987.
[10] L. van der Maaten and E. Postma. Dimensionality reduction: A Comparative Review.
TiCC TR, 2009.
[11] R. Ohbuchi, J. Kobayashi, A. Yamamoto, and T. Shimizu. Comparison of dimension reduction methods for database-adaptive 3D model retrieval. AMR, 2007.
[12] L.J. Cao, K.S. Chua, W.K. Chong, H.P. Lee, and Q.M. Gu.
A comparison of
PCA, KPCA and ICA for dimensionality reduction in support vector machine.
Neurocomputing, 2003.
[13] Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000.
[14] J. Milgram, M. Cheriet, and R. Sabourin. "one against one"or “one against all” fo:
Which One is Better for Handwriting Recognition with SVMs. Tenth International
Workshop on Frontiers in Handwriting Recognition, 2006.
[15] Набор данных MNIST.
http://yann.lecun.com/exdb/mnist/ (Дата обращения
20 мая 2014).
[16] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Sch¨
utze. Introduction to
Information Retrieval. Cambridge University Press, New York, NY, USA, 2008.
15