Как сделать SVD и PCA с большими данными?

Question

У меня есть большой набор данных (около 8 ГБ).Я хотел бы использовать машинное обучение для его анализа.Итак, я думаю, что мне следует использовать SVD, а затем PCA, чтобы уменьшить размерность данных для повышения эффективности.Однако MATLAB и Octave не могут загрузить такой большой набор данных.

Какие инструменты я могу использовать для создания SVD с таким большим объемом данных?

Answer 1

Прежде всего, уменьшение размерности используется, когда у вас есть множество ковариационных измерений и хотите уменьшить размер задачи, переведя точки данных в новый ортогональный базис и взяв только оси с наибольшей дисперсией.С 8 переменными (столбцами) ваше пространство уже маломерно, дальнейшее уменьшение количества переменных вряд ли решит технические проблемы с объемом памяти, но может сильно повлиять на качество набора данных.В вашем конкретном случае более перспективно взглянуть на онлайн-обучение методы.Грубо говоря, вместо того, чтобы работать со всем набором данных, эти методы берут небольшую их часть (часто называемую "мини-пакетами") за раз и строят модель постепенно.(Лично мне нравится интерпретировать слово "онлайн" как ссылку на какой-то бесконечно длинный источник данных из Интернета, такой как лента Twitter, где вы просто не можете загрузить весь набор данных сразу).

Но что, если вы действительно хотите применить метод уменьшения размерности, такой как PCA, к набору данных, который не помещается в память?Обычно набор данных представляется в виде матрицы данных X размера n x m, где n - количество наблюдений (строк) и m представляет собой ряд переменных (столбцов).Обычно проблемы с памятью возникают только из-за одного из этих двух чисел.

Слишком много наблюдений (n >> m)

Когда у вас есть слишком много наблюдений, но количество переменных от малого до умеренного, вы можете постройте ковариационную матрицу постепенно.Действительно, типичный PCA состоит из построения ковариационной матрицы размера m x m и применяя к нему разложение по сингулярным значениям.С m= 1000 переменных типа float64, ковариационная матрица имеет размер 1000*1000*8 ~ 8 МБ, который легко помещается в память и может использоваться с SVD.Таким образом, вам нужно только построить ковариационную матрицу без загрузки всего набора данных в память - довольно выполнимая задача.

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

Слишком много переменных (n << м)

С другой стороны, иногда, когда у вас есть слишком много переменных, сама ковариационная матрица не поместится в память.Например.если вы работаете с изображениями размером 640x480, каждое наблюдение содержит 640 * 480 = 307200 переменных, что приводит к ковариационной матрице объемом 703 Гб!Это определенно не то, что вы хотели бы сохранить в памяти вашего компьютера или даже в памяти вашего кластера.Таким образом, нам нужно уменьшить размеры, вообще не создавая ковариационную матрицу.

Мой любимый метод для этого - Случайная проекция.Короче говоря, если у вас есть набор данных X размера n x m, вы можете умножить его на некоторую разреженную случайную матрицу R размера m x k (с k << m) и получить новую матрицу X' гораздо меньшего размера n x k с примерно те же свойства как и в оригинале.Почему это работает?Что ж, вы должны знать, что PCA стремится найти набор ортогональных осей (основных компонентов) и сначала спроецировать ваши данные k из них.Оказывается, что разреженные случайные векторы являются почти ортогональный и, таким образом, также может быть использован в качестве новой основы.

И, конечно же, вам не нужно умножать весь набор данных X Автор: R - вы можете перевести каждое наблюдение x на новую основу отдельно или мини-партиями.

Существует также несколько похожий алгоритм, называемый Случайный SVD.У меня нет никакого реального опыта работы с этим, но вы можете найти пример кода с пояснениями здесь.

---

В качестве итога, вот краткий контрольный список для уменьшения размерности больших наборов данных:

1. Если у вас не так много измерений (переменных), просто используйте алгоритмы онлайн-обучения.
2. Если имеется много наблюдений, но умеренное количество переменных (ковариационная матрица умещается в памяти), постройте матрицу постепенно и используйте обычный SVD.
3. Если количество переменных слишком велико, используйте инкрементные алгоритмы.

Answer 2

Не беспокойтесь.

Первое правило программирования, которое также применяется к науке о данных: заставьте все работать над небольшой проблемой теста.

Так что возьмите случайную выборку ваших данных, скажем, 100 000 строк. Попробуйте разные алгоритмы и т. Д. Как только вы получите все, что работает для вашего удовлетворения, вы можете попробовать большие (и большие) наборы данных - и посмотреть, как уменьшается ошибка тестирования при добавлении большего количества данных.

Кроме того, вы не хотите применять SVD только к 8 столбцам: вы применяете его, когда у вас много столбцов.

Answer 3

PCA обычно реализуется путем вычисления SVD на ковариационной матрице.

Вычисление ковариационной матрицы - это смущающе параллельно задача, так что это масштабируется линейный с количеством записей, и это тривиально распространять на несколько машин!

Просто сделайте одну передачу ваших данных, чтобы вычислить средства. Затем второй проход, чтобы вычислить ковариационную матрицу. Это может быть сделано с помощью Map -Reduce легко - по сути, это то же самое, что снова вычисление средств. Условия суммы, как и в ковариации, тривиализируют параллелизирование! Вам может потребоваться обратить внимание на численность только при суммировании множества значений одинаковой величины.

Все по -другому, когда у вас есть огромное количество переменные. Анкет Но в системе 8 ГБ вы сможете запустить PCA в размере до 20 000 измерений в памяти с библиотеками BLAS. Но тогда вы можете столкнуться с проблемой, что PCA больше не так надежна, потому что у него слишком много степени свободы. Другими словами: это легко переполняет. Я видел рекомендацию иметь не менее 10*D*D записи (или это было D^3). Таким образом, для 10000 измерений у вас должно быть не менее миллиардов записей (из 10000 измерений ... это много!), Чтобы результат был статистически надежным.

Answer 4

Хотя вы, вероятно, можете найти некоторые инструменты, которые позволят вам сделать это на одной машине, вы попадаете в диапазон, где имеет смысл рассмотреть инструменты «больших данных», такие как Spark, особенно если вы думаете, что ваш набор данных может расти. Spark имеет компонент под названием Mllib, который поддерживает PCA и SVD. В документации есть примеры.

Answer 5

Мы реализовали SVD в более крупный набор данных с помощью Pyspark. Мы также сравнили согласованность в разных пакетах. Здесь ссылка на сайт.

Answer 6

Я бы рекомендовал Python, если бы вы лениво оценили файл, у вас будет минимальная площадь памяти, а Numpy/Scipy даст вам доступ ко всем инструментам, которые Octave/Matlab.