I have a set of data objects defined by 20 dimensions rated from 1 to 10 with no decimal. There is no hierarchy between dimensions.

I am able to calculate the similarity between objects but I do not want to compare a new object to the whole set of existing objects every time a new one is inserted. Machine learning seems to be the right solution for this task. I ve read some interesting stuff basing my research on this https://en.wikipedia.org/wiki/Similarity_learning

Do you have an idea on which machine learning algorithm would suit the best to my needs ?

  • 1
    $\begingroup$ Well, what are your needs? Are you looking for most-similar objects under some similarity function without doing the full pairwise comparison? If so, what similarity function? Are you looking to define a new one to better represent the similarity between these objects? If so, do you have any data about what should be similar and what shouldn't, or some label you can try to predict that would give some useful information about the similarity? $\endgroup$ – Dougal Aug 20 '15 at 16:07
  • $\begingroup$ let's assume I have two objects rated 1 to 10 on 5 dimensions. object A : 1 4 10 5 7 object B : 4 4 9 6 10 object C : 7 2 1 1 3 similarity a <-> b = |1-4|+|4-4|+|10-9|+|5-6|+|7-10| = 3 + 0 + 1 + 1 + 3 = 8 similarity a <-> c = |1-7|+|4-2|+|10-1|+|5-1|+|7-3| = 25 similarity b <-> c = |4-7|+|4-2|+|9-1|+|6-1|+|10-3| = 27 so the highest the result is, the less similar objects are. if 0, objects are identical. back to my 20 dimensions project : My idea is to find a way to put the points on a 20-dimension space, and find a way to find its nearest neighbors when a new points shows up. $\endgroup$ – Ben Aug 20 '15 at 18:15

Your distance function is known as $L_1$ distance, also called "Manhattan distance" and various other names. Similarity learning is not what you need here.

The problem you seem to be looking for is called nearest neighbor search; you can use methods like k-d trees, but 20 dimensions is high enough that it's probably only going to be useful if you have at least hundreds of thousands of points.

There are approximate nearest neighbor methods, which return nearby points but may miss some neighbors; many of these work for $L_1$. Some examples are locality sensitive hashing, ensembles of k-d trees built on subsets of the dimensions, or some other options. FLANN is a pretty good library implementing several of these.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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