PCA

https://www.coursera.org/course/ml

После линейной регрессии была логистическая регрессия. А потом начались нейросети — Neural Networks. Потом нас учили правильно применять изученные алгоритмы (Advice for Applying Machine Learning). А потом нам рассказали про Support Vector Machines (SVMs) и Kernels.

А потом была неделя посвященная темам Clustering (K-Means) и Dimensionality Reduction (PCA).

Сегодня разберем тему снижения размерности.

Dimensionality Reduction — штука довольно занятная в контексте Machine Learning, ибо, в отличие от предсказания злокачественности опухоли с помощью нейросети, к примеру, не несет непосредственной пользы. А вот опосредованно вполне может пригодится.

Одно из применений снижения размерности — сжатие данных. Было в вашем наборе данных две характеристики, а мы оставим одну — сжали данные вдвое.

Другое применение — ускорение обучения машины. Вместо обработки матриц 10000х100500000 можно обрабатывать матрицы 1000х100500000, это будет заметно быстрее.

А еще можно применить снижение размерности для визуализации данных. Если трехмерный график мы еще можем усвоить, то тысячемерный — увольте.

Метод снижения размерности называется Principal Component Analysis (PCA).

Этот метод заключается в нахождении такой редуцированной поверхности в многомерном пространстве (линии на двумерной плоскости, к примеру), для которой сумма квадратов расстояний от поверхности до точек датасета минимальна.

Задача может показаться похожей на линейную регрессию, но это не так. И Cost Function другая и в датасете нет деления на переменные и цель/значение (X, Y). Все фичи датасета – это X. Таким образом, снижение размерности относится к разряду Unsupervised Learning, в отличие от линейной регрессии, относящейся к Supervised Learning.

Что делает PCA?

PCA для нас находит по исходному датасету векторы уменьшенной размерности и вычисляет новые фичи для этой новой размерности.

Математически это делается так:

найти для датасета Covariance Matrix (ковариантную матрицу) — матрица n,n из суммы произведений фич;

найти Eigenvectors (эйгенвекторы) aka «singular value decomposition» этой матрицы.

Первые K векторов из матрицы U в полученных эйгенвекторах — это и будут искомые векторы уменьшенной размерности.

Умножив транспонированную матрицу из этих векторов на данные датасета, мы получим новый, сжатый датасет, что и требовалось.

Нихрена неясно, зато математически кратко выражено.

Ну и в завершение — а какую бы нам выбрать новую, маленькую, хорошую размерность? Для визуализации данных это не вопрос, тут либо 2, либо 3. А вот для сжатия данных надо выбирать новую размерность осторожно, обдуманно.

Новая размерность K это параметр алгоритма PCA, один из. Как выбрать желаемую новую размерность?

Как обычно, заценив получаемую ошибку. Надо искать наименьший K такой, который дает ошибку меньше допустимой.

Ошибка вычисляется как сумма квадратов X - Xapprox поделенная на сумму квадратов X. Ну, не совсем X, конечно, там проекции и длины векторов, см.картинки.

Но для такого вычисления нам надо уметь «восстанавливать» исходное значение Х — разжимать данные обратно, получая Xapprox.

Но есть способ проще. В найденных ранее ейгенвекторах есть матрица S. Используя ее, можно заменить операции по вычислению ошибки на простые операции с элементами этой матрицы – суммирование и деление сумм. И не надо вычислять (здесь, во всяком случае) аппроксимированное значение Xapprox.

Вот и все уменьшение размерности методом PCA. Ковариантная матрица, ейгенвекторы и перемножение пары матриц — математическая запись очень лаконична. А что под капотом — нам не объясняли.

Чуть не забыл. В практическом упражнении мы применили PCA для сжатия данных. На входе был набор картинок 32х32 пикселя — изображения лиц людей. А на выходе мы, определив 36 pricipal components, получили картинки 6х6 пикселей. Только это уже как бы и не картинки, это именно наиболее важные области картинок, отвечающие на наибольшую вариативность — чем лица отличаются одно от другого.

А потом, определив 100 PC, получили картинки 10х10, разжав которые обратно получили ошеломляющий результат — см.иллюстрацию.

original post http://vasnake.blogspot.com/2014/06/pca.html