Перейти к содержимому
Compvision.ru

Recommended Posts

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

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

Но вроде бы такой подход никуда не годится, ибо при больших N это плохо работает. (в математическом обосновании я не очень уверен).

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

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

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

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Если свойства рассматриваемого класса объектов не меняются во времени, то достаточно будет один раз найти базис и построить дерево.

Если меняются, то можно ввести какой-либо индикатор и по нему ориентироваться, когда нужно все перестроить.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

а будет ли сравним базис по большой выборке с с базисом по маленькой?

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

отсюда вытекает сразу же еще вопрос, ведь мы строим 1 базис по 1 большой выборке, что если построить N маленьких базисов по той же выборке и ориентирваться уже на них?

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Они характеризуют статистические свойства объектов класса, с которым Вы работаете.

При правильно сделанной выборке, достаточно большого размера (сильно зависит от размерности вектора параметров объекта), эти оси (N штук с максимальными собственными значениями), при дальнейшем увеличении выборки практически не будут менять своего направления.

Например, если мы исследовали первые 10000 объектов с 3 параметрами, и нашли собственные векторы, то для 100000 объектов, эти оси останутся практически неизменными.

Но нужно правильно делать выборку, т.е. брать равномерно из объектов разными свойствами.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

нашел еще про PCA и SVD для больших объемов.

http://arxiv.org/pdf/1007.5510.pdf

http://code.google.com/p/redsvd/

тут еще свежее

https://sites.google.com/site/igorcarron2/matrixfactorizations

тут раздел Dimensionality reduction (но там примерное решение)

http://www.cs.yale.edu/homes/el327//papers/streaming_data_mining.pdf

вот тут вроде бы решение через SVD

http://stackoverflow.com/questions/3181593/matlab-is-running-out-of-memory-but-it-should-not-be

через матлабовский eig

http://stackoverflow.com/questions/12698433/matlab-how-to-compute-pca-on-a-huge-data-set

еще похожее

http://stats.stackexchange.com/questions/2806/best-pca-algorithm-for-huge-number-of-features

некоторое объяснение

http://www.scribblethink.org/Work/PCAderivations/PCAderivations.pdf

вообщем надо попробовать на матлабе готовые решения- посмотреть по скорости и памяти и думать дальше.

с кодом на матлабе как считать через матрицу ковариации и через SVD

http://www.snl.salk.edu/~shlens/pca.pdf

сравнение обычного и randomized pca (вывод непонятен)

http://www.machinedlearnings.com/2013/10/another-random-technique.html

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Попробовал PCA на матлабе и получились странные результаты.

Тестировал на orl face db. там 40 индивидов по 10 сэмплов = 400 фото. (возможно данных мало?)

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

Еще пользовался ф-ей princomp она выдает собсвенные векторы и зачем то все данные проекцированные на все собственные векторы (я так и не понял куда это использовать, если мы всё равно берём k первых собсвенных векторов).

Пробовал так же кореляцию NNC, но она дает такие же примерно результаты, а считается дольше.

orl_label=[];

for i=1:40

    orl_label= [orl_label;ones(10,1)*i];

end


n=size(orl_data,1);

k = randperm(n);

s= round(0.25*n);


%raw pix

data_tr = orl_data(k(1:s),: );

label_tr = orl_label(k(1:s),: );

data_te = orl_data(k(s+1:end),: );

label_te = orl_label(k(s+1:end),: );


tic

[nn_ind, estimated_label] = EuclDistClassifier(data_tr,label_tr,data_te);

toc


rate = sum(estimated_label == label_te)/size(label_te,1)


tic

[nn_ind, estimated_label] = NNclassifier(data_tr,label_tr,data_te);

toc


rate = sum(estimated_label == label_te)/size(label_te,1)


%pca

tic

[pc sc]= princomp(data_tr);

toc


mean_face = mean(data_tr);

pc_n=100*20; %варьируемое кол-во

f_pc= pc(1:pc_n,: )';

data_pca_tr = (data_tr - repmat(mean_face, [s,1])) * f_pc;

data_pca_te = (data_te - repmat(mean_face, [n-s,1])) * f_pc;


tic

[nn_ind, estimated_label] = EuclDistClassifier(data_pca_tr,label_tr,data_pca_te);

toc


rate = sum(estimated_label == label_te)/size(label_te,1)


tic

[nn_ind, estimated_label] = NNclassifier(data_pca_tr,label_tr,data_pca_te);

toc


rate = sum(estimated_label == label_te)/size(label_te,1)

п.с. движок форума бьёт код матлаба, ну общий смысл понятен думаю, если надо выложу куда нибудь еще.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Онлайн PCA использовал для лиц, вроде результат более-менее адекватный:

В архиве еще пара матлабовских исходников, один тот который я переписал на С++ (Candid Covariance-free Incremental Principal Component Analysis), а другой вроде тоже из той же оперы, я пока не разобрался.

ccPCA.rar

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

и исходник откуда изначально?

сейчас сам ищу что то типа mini batch pca/online pca/iterative pca из-за проблем когда всё не влезает в оперативную память.

опять же это актуально, если делать на GPU и там какие то матричные операции, т.к. там не так много памяти.

pca планирую использовать для уменьшения размерности для ускорения knn-search.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Сравнивал с обычным PCA на той же выборке (на выборке из 5000 лиц), разница есть, но в общем похоже что итеративный метод идет правильным путем. При работе видно, что процесс сходится. Начальный исходник (матлабовский ccipca.m) там в архиве, и документ по нему тоже.

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

Матлабовский исходник скачивал здесь:

http://en.pudn.com/downloads205/sourcecode/windows/detail963565_en.html

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Архив с исходниками (преимущественно Матлаб) для уменьшения размерности данных (в основном взяты с www.pudn.com):

ManifoldLearning.rar

mani.m - видимо взято отсюда: http://www.math.ucla.edu/~wittman/mani/

Здесь много кода по теме: http://www.cse.wustl.edu/~kilian/research/manifold/manifold.html

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

всё равно непонятно как сравнивать разные методы PCA, можно конечно подавать спроецированные векторы уменьшенной размерности в какой либо классификатор и смотреть сколько правильно классифицированных(получается зависит от данных) или даже проецировать на 2D и смотреть хорошо ли разделимы классы(получается несколько субъективно, хотя может быть можно посчитать какие либо метрики для получившихся кластеров? типа широкий ли разброс и намного ли они пересекаются), еще идея это смотреть насколько отличается от оригинала изображение после восстановления при каком то кол-ве главных компонент.

и еще подумалось, что может нет большого смысла использовать PCA с большой матрицей, если только он не online\batch.

есть же RBM/autoencoder который от природы online

http://nghiaho.com/?p=1765

и по идее можно проверять работу алгоритма по реконструкции

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

решил написать PCA на python и переписать его на numpy.memmap после тестирования.

входная матрица M x N, т.е. M строк(сэмплов) и N столбцов(размерность данных).

непонятно почему должны транспонировать при передаче в np.cov?

def pca():

#M x N

xs= np.loadtxt("data_3d.txt",delimiter=" ", skiprows=1, usecols=(0,1,2))

print xs.shape

# print xs

#get mean

mean= np.mean(xs,axis=0)

# print mean.shape

# print mean

#N x M

data= (xs-mean).T # why need transpose?

print data.shape

# print data

#N x N

covData=np.cov(data)#calculate covariance matrix

print covData.shape

eigenvalues, eigenvectors = np.linalg.eig(covData)

print eigenvalues.shape # N long

print eigenvectors.shape # N x N

print eigenvalues

print eigenvectors

исходник был

http://bekoc.blogspot.ru/2013/12/implementing-principle-component.html

и опять же про проекцию и реконструкцию определенная путаница с транспонированием.

хотя по сути для проекции всего 2 варианта, т.к. всё равно мы должны получить m k.

projection

(m n) * (n k) = m k

(n m).T * (n k) = m k

reconstruction

(n k) * (m k).T = (n m)

(m k) * (n k).T = (m n)

#sort and get k largest eigenvalues

k=2

idx = eigenvalues.argsort()[-k:][::-1]

print idx

eigenvalues = eigenvalues[idx] # k long

eigenvectors = eigenvectors[:,idx] # N x k

print eigenvalues.shape

print eigenvectors.shape

print eigenvalues

print eigenvectors

#projection and reconstruction

pr= np.dot(data.T,eigenvectors) # (M N) * (N k) => (M k)

rec= np.dot(eigenvectors, pr.T) #(N k) * (k M) => (N M)

print (data-rec) # test reconstruction error

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

по идее так должно быть, смущает только транспонирование егенвекторов для реконструкции ( хотя матрица относительно небольшая зависит от размерности данных и k).

Вроде как там можно считать левые и правые векторы в зависимости что больше кол-во сэмплов или размерность.

def pca():

#M x N

xs= np.loadtxt("data_3d.txt",delimiter=" ", skiprows=1, usecols=(0,1,2))

print xs.shape

# print xs

#get mean

mean= np.mean(xs,axis=0)

# print mean.shape

# print mean

#M x N

data= (xs-mean)

print data.shape

# print data

#N x N

#calculate covariance matrix

covData=np.cov(data,rowvar=0)

print covData.shape

eigenvalues, eigenvectors = np.linalg.eig(covData)

print eigenvalues.shape # N long

print eigenvectors.shape # N x N

# print eigenvalues

# print eigenvectors

#sort and get k largest eigenvalues

k=2

idx = eigenvalues.argsort()[-k:][::-1]

print idx

eigenvalues = eigenvalues[idx] # k long

eigenvectors = eigenvectors[:,idx] # N x k

print eigenvalues.shape

print eigenvectors.shape

# print eigenvalues

# print eigenvectors

#projection

pr= np.dot(data,eigenvectors) # (M N) * (N k) = (M k)

print pr.shape

#reconstruction

rec= np.dot(pr, eigenvectors.T) #(M k) * (N k).T = (M N)

print rec.shape

print (data-rec)

p.s. основное время всё равно занимает np.linalg.eig

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

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

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×