Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 3 down vote favorite

Basically, right now I am trying to do some nearest-neighbour searching on an approach where I don't have points in Euclidean space. To do a nearest-neighbour search currently, I take the query and compare it (with a special similarity function) to each model in the database to find the most similar one.

With this similarity function, I can compute pairwise distances between all points in my database, and I'm interested in whether it's possible to learn a projection into Euclidean space such that any new query can just be projected and nearest neighbour searches can then be performed in that Euclidean space.

Does such a method exist, or am I hoping for a holy grail that hasn't been solved?

share|improve this question

1 Answer

up vote 4 down vote accepted

Use Laplacian Eigenmaps, Locally Linear Embedding or Local Tangent Space Alignment. These methods map the distances in a low-dimensional space non-linearly, thereby preserving the local neighborhood/ local geometry. A very preliminary technique would be classical metric multidimensional scaling- but this would be a linear projection, and hence it is fairly possible that the local neighborhood is not preserved accurately, unless the intrinsic dimensionality of the data is low (one way of interpreting this is- the data can be represented as a kernel gram matrix, which has a low-error low rank approximation).

share|improve this answer
Thanks for this, but I`m either misunderstanding your response or you misunderstood the question. These give us a projection based on a matrix of pairwise distances. I can project my initial database into the space fine with this. However, a new, unseen data point cannot be projected without comparing against the entire database with these methods, can it? I want to avoid having to compare against the whole database for each unseen point – water Aug 15 '12 at 19:36
No. We are in the right direction. These methods have, what is called a "Out-of-Sample" embedding. Which allow for out-of-sample(new) data to be mapped, without requiring to map the entire, updated dataset all again. – Praneeth Vepakomma Aug 15 '12 at 19:38
1  
Amazing. I`ll have to do some more reading then, thank you – water Aug 15 '12 at 20:25
Sorry for bugging you, just one quick question :) I'm trying to find a suitable LLE algorithm, and am reading "Truly Incremental Locally Linear Embedding", however, this still requires a full comparison of a new data point against all existing points for each new data point. Do you have a recommended method or resource? Thank you – water Aug 16 '12 at 12:32
Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering- (NIPS)- Eqns 8 to eqns 12 and section 4. – Praneeth Vepakomma Aug 16 '12 at 13:17
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.