2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 PCA для большого объема данных
Сообщение12.11.2012, 10:01 


20/04/12
114
Есть ли в природе реализации PCA (Principal Component Analysis) параллельные\на GPU\для больших объемов данных(т.е. всё сразу не влезает в память)?
Вроде как есть не один способ вычислять PCA, опять же вроде как PCA связано плотно с SVD(т.е. тогда уже получается вопрос относится к SVD и матричным операциям) и еще есть Iterative PCA(если нужны не все собственные векторы, а k первых, что вроде как быстрее считается).



побочные вопросы:
1. опять же тут такой вопрос например матлаб пишет out of memory, разве система не должна делать сброс на жесткий диск при нехватке памяти?
2. что такое manifold learning? (это просто способ для Nonlinear dimensionality reduction т.е. PCA линейный, а это не линейный? но что то кажется, что за этим скрывается некий матан)
3. возможно есть какие то форумы по data mining специализированные и туда обратится?

 Профиль  
                  
 
 Re: PCA для большого объема данных
Сообщение14.11.2012, 08:05 


05/12/11
18
да, их полно: например в mahout или graphlab. Стохастические методы, например как в redsvd, тоже могут экономить память.

1. возможно, кончилась виртуальная память
2. Если точки из данных лежат на гранях многомерного куба, на сфере или на спирали какой-нибудь, pca не уменьшит размерность. Manifold learning - это целый набор методов для уменьшения размерности в такого рода задачах.
3. англоязычных много, про русскоязычные я не в курсе

 Профиль  
                  
 
 Re: PCA для большого объема данных
Сообщение14.11.2012, 09:16 


20/04/12
114
Цитата:
Если точки из данных лежат на гранях многомерного куба, на сфере или на спирали какой-нибудь, pca не уменьшит размерность.

а возможно как то проанализировать данные чтобы понять какой метод применять?

Не знаете еще, что из этого вами вышеперечисленного набора библиотек легко подключается к матлабу?

Еще такой вопрос про PCA.

Допустим у нас есть выборка из 1000 сэмплов(каждый вектор длиной N) и для 1001 надо найти скажем K ближайших соседей, можно было бы перебрать все по порядку используя например просто евклидову метрику для вектора длиной N и потом отсортировать и взять K ближайших сэмплов.
Но вроде бы такой подход никуда не годится, ибо при больших N это плохо работает. (в математическом обосновании я не очень уверен).
Значит применяем PCA потом проецируем 1000 сэмлов на новый базис и 1001 тоже и так же ищем K ближайших только для размерности векторов например 100, а не N.

Можно так же применить не просто линейный поиск, а сделать дерево из 1000 элементов и всё будет искаться быстрее.
Но тут возникает проблема, по мере наполнения сэмплов в базу, получается что при каждом добавлении нового элемента в базу требуется перестраивать индекс дерева, а так же если мы используем PCA пересчитывать базис.

Какое решение такой проблемы можно предложить?
мне пока только пришло в голову делать это не для каждого элемента, а для группы элементов или вообще ничего не делать до того как не наберем полную базу.
Возможно можно сформировать какой то критерий насыщения базы, т.е. добавление новых сэмплов в базу уже мало повлияет на нашу текущую "популяцию"? т.е. для новых приходящих элементов чтобы получить K ближайших соседей и посмотреть на что они похожи можно использовать уже этот состоявшийся базис.

 Профиль  
                  
 
 Re: PCA для большого объема данных
Сообщение14.11.2012, 21:25 


05/12/11
18
Цитата:
а возможно как то проанализировать данные чтобы понять какой метод применять?


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

Цитата:
Какое решение такой проблемы можно предложить?

одна из техник, которую используют в этом случае, locality sensitive hashing (LSH) и\или random projection trees, помогает найти соседей с заданной наперед вероятностью.

вы задаете правильные вопросы: вам очень поможет книга или лекции на тему large scale data mining. вот, например, неплохой ресурс:

http://www.stanford.edu/class/cs246/cs2 ... douts.html

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group