Python-сообщество

Рекомендую перечитать свои посты. По ним решительно нельзя понять что именно вы делаете. Поэтому пока вы понятно не объясните суть решаемой задачи оказать вам помощь считаю невозможным.
Надеяться что есть волшебные матричные алгоритмы которые решат более или менее сложную задачу не думая над этой задачей глупо.

Для общего случая: пейджинг, кеширование. Соответственно, грамотная организация данных.

Рекомендую перечитать свои посты. По ним решительно нельзя понять что именно вы делаете. Поэтому пока вы понятно не объясните суть решаемой задачи оказать вам помощь считаю невозможным.
Надеяться что есть волшебные матричные алгоритмы которые решат более или менее сложную задачу не думая над этой задачей глупо.

Еще раз, разделим на части:

1. knn-search
   Есть набор векторов длины N(~1000), набор переодически пополняется(размер ~1kk).
   т.е. имеем матрицу ~1кк*1k и допустим ограничения железа таковы ,что в память она не влезает(или мы просто хотим, чтобы наша программа занимала например не более 1Гб памяти).
   Затем мы берем тестовый вектор и хотим найти в этом наборе k ближайших по евклидовой метрике.
   Самый простой вариант решения это загружать в память небольшое кол-во векторов за итерацию, определять k ближайших , затем загружать новую порцию, сортировать k от предыдущей и текущей итераций, брать k ближайших и так до конца набора.
   Понятное дело, что для ускорения поиска напрашивается дерево, но тут должна быть такая реализация чтобы опять же не надо было загружать весь набор в память для построения дерева(еще может быть и само дерево не будет помещаться в память?)
   + еще надо учитывать, что данные переодически добавляются, т.е. дерево придётся перестраивать.
   Сокращение размерности вектора.
   Для скорости сравнения и для того чтобы занимало меньше места.
   Самый простой способ PCA, но и тут мы имеем проблему из-за того что не можем загрузить всего в память+ если добавляются данные, то надо всё пересчитывать.
   Но тут как раз всплывают “волшебные матричные алгоритмы” (хотя изначально я имел ввиду их именно в контексте возможности работы с большими матрицами).
   Всякие mini batch/online/iterative/probabilistic PCA.
   Смысл опять же в том, что мы можем подавать данные небольшими порциями и по идее результат примерно сходится к тому как если бы мы подали матрицу целиком.
   
   
   вообщем можете рассказать как вы решали задачу
   

   есть б.д. преступников 100000 фото - сравнить новое лицо с базой.

   потому, что это частный случай того, что я описал выше.
   

Отредактировано mrgloom (Май 13, 2013 09:22:34)

Да это все просто делается. Сначала применяется алгоритм специфический для предметной области, и лица жмутся до 5 -10 числовых характеристик, потом применяется классический RTree. При необходимости задача легко раскидывается на вычислительный кластер…

Но чтобы эту задачу решили в общем виде для пространства большой размерности я не слышал, найдете обязательно напишите.

Поэтому я и написал что нужно описание предметной области. Думаю для абстрактной постановки: “есть много больших векторов ….” она просто не решаема на современной технике.

По поводу PCA - он имеет смысл только в том случае когда данные реально имеют ФИЗИЧЕСКУЮ структуру которая позволяет надеяться на эффективное сжатие (опять нужно пониманиие не на уровне вектор с 1000 компонентов, а реально что это такое, а вы упорно делаете из этого большую тайну) . Если я вам случайные вектора в алгоритм суну, то PCA вообще ничего не даст.

Почему именно RTree ? опять же вы знаете реализации которые не зависят от размера данных?

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

mrgloom
Почему именно RTree ?

он поддерживает поиск соседей.

mrgloom
которые не зависят от размера данных

- потренируйтесь Доказать: не существует алгоритма трудоемкость которого не зависит от длины векторов. Уверен легко найдете доказательство.

mrgloom
чтобы автоматически определить оптимальное кол-во собственных векторов.

Для начала надо определить критерий оптимальности, а потом можно обсуждать.

Отредактировано doza_and (Май 14, 2013 20:33:21)

mrgloom
Почему именно RTree ?

он поддерживает поиск соседей.

почему не kd-tree например?
все деревья вроде как используются для range searches and nearest neighbor searches, единственное там какие то проблемы если длина вектора большая
http://en.wikipedia.org/wiki/Curse_of_dimensionality

потренируйтесь Доказать: не существует алгоритма трудоемкость которого не зависит от длины векторов. Уверен легко найдете доказательство.

я хочу не от длины вектора, а от размера базы.
и понятное что будет зависеть, но просто если грузить всё порциями и проверять последовательно, то скорость будет зависеть прямопропорционально от размера базы, а если построить что то типа дерева, то быстрее.
Проблема в том, что я не знаю какая структура оптимальна + еще раз повторюсь я ищу готовое решение для больших баз которые не влезают в память
т.к. для обычных случаев такие варианты есть
http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
http://www.cs.umd.edu/~mount/ANN/

Для начала надо определить критерий оптимальности, а потом можно обсуждать.

допустим у меня было N сэмплов и там k классов и я взял и разбил на тестовую и обучающую выборки и влоб посчитал через евклидову метрику
по алгоритму https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
получилось какое то кол-во правильных ответов.
Затем я хочу размерность данных уменьшить через PCA чтобы считать быстрее, мне надо узнать какое мин. кол-во главных компонент взять чтобы кол-во правильных ответов не уменьшилось.

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

Отредактировано mrgloom (Май 15, 2013 09:59:29)

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

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

хотя вот вроде есть
http://blog.revolutionanalytics.com/2011/06/kmeans-big-data.html

вот вроде бы то о чем я как раз говорил
http://www.cs.cmu.edu/~epxing/Class/10701/reading/icmr2011_nvtree.pdf
http://csce.uark.edu/~jgauch/library/Video-Retrieval/Lejsek.2009.pdf


и вот еще неплохой обзор
http://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data

Отредактировано mrgloom (Май 15, 2013 11:41:11)

Очень интересные ссылки. Спасибо.
Извините я наверное неправильно понял ваши возможности.

Системы для которых предназначены NV деревья:
“The experiments in this section were run on DELL Pow-
erEdge 1850 machines running Gentoo Linux (2.6.7 kernel),
each equipped with two 3GHz Intel Pentium 4 processors,
2GB of DDR2-memory, 1MB CPU cache, and two (or more)
140GB 10Krpm SCSI disks with the ReiserFS file system.”

Вы пишете питон скрипт для кластера из 2000 машин?

mrgloom
почему не kd-tree например?

да нет разницы это примерно одно и тоже.