What is the most appropriate similarity measure to choose in high dimensional spaces?

05 May 2016 4 2K Report

Every object in my dataset is described as a vector of n=20 features. All the features are integers but they have different scales. I need to choose a measure to evaluate the similarity of two objects in the dataset. I have to satisfy the following condition: Two feature vectors which are identical (i.e., they have exactly the same numbers), must have the same similarity value. I already tried different similarity measure, like dot product and cosine similarity:

Dot product does not work in my case because the similarity measure depends on the specific numbers in the feature vector. For example given these two objects a=[2, 2, 30, 4, 5], b=[2, 2, 30, 4, 5], then similarity(a, b)=949. Given these two vectors c=[2, 2, 300, 4, 5], d=[2, 2, 300, 4, 5], then similarity(c, d)=90049. I want the similarity to be the same number in both cases, i.e., similarity(a, b) = similarity(c, d);

Cosine similarity does not work in my case because it only takes into account the angle between the vectors. I also need to take into account magnitude. For example, given these two objects a=[2, 2, 30, 4, 5], b=[4, 4, 60, 8, 10] then similarity(a, b) = 1 (the maximum similarity). Since the numbers in the feature vectors are different, in my case their similarity should be not the maximum.

It is seems to me that standardizing the features and using an Euclidean distance, a Manhattan distance or in general a Minkowski distance is the most suitable solution. Can you suggest me other distance measures that are more suitable for my scenario?

Oliver Sampson

What is preventing you from normalizing the features?

Assuming you can normalize the features, as you get more and more dimensions, you'll find that Euclidean/Manhatten distance measures are subject to the Curse of Dimensionality and you'll want to use something like the Cosine similarity.

There is also some research to indicate that you can actually use an L_n norm with fractional powers for a high-number of dimensions.

See the attached link for "On the Surprising Behavior of Distance Metrics in High Dimensional Space"

http://bib.dbvis.de/uploadedFiles/155.pdf

Antonio Valerio Miceli Barone

Hi Luca,

I think that if magnitude is important in your application, then the Euclidean distance, or in general a metric induced by a norm, such as one of the Minkowski distances, may be the best choice.

Caleb Rascon

Actually the cosine similarity (which I'm guessing you mean the Pearson correlation coefficient) is basically a dot product normalized by the magnitudes of both vectors. So they are both quite related.

You are right about the problem here, since one big feature produces a big bias into the direction that feature represents, thus, all other features are "ignored" by those similarity measures. Unfortunately, this will also happen with the Euclidean distance, since a vector such as [1, 2, 30, 4] will be very close in distance to [0, 1, 30, 3], because the big feature didn't change its value much, although all the other features did change their RESPECTIVE TO THEIR MIN AND MAX VALUES.

If you know the minimum and maximum value of each feature, I would recommend normalizing the features such that they only vary between 0 and 1. Then, the Euclidean Distance or the Minkowski Distance will do the trick, having 0 the measure of exactitude between the feature vectors. I wouldn't go for the cosine similarity in this case, since two vectors of different normalized magnitudes (such as [0.25, 0.5, 0.75] and [0.05, 0.1, 0.25]) may still provide high similarity, and you require exactitude.

Just stay below a certain number of features to avoid what Oliver Sampson is saying about "Curse of Dimensionality".

https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient

Antonio Valerio Miceli Barone

Another possibility is to augment the feature vector by including the norm of the original vector as a new feature, possibly scaled by some weight. This way you can use the cosine similarity while retaining the dependency on the original magnitude.

I think this satisfies all your requirements, although it may or may not work well in practice for your problem.

How to compare two groups with only two measurements?

Binary Logistic Generalized Linear Mixed model in SPSS. Is it doable?

Enhanced Yellow Fluorescent Protein (Aequorea victoria) DNA sequence?

What kind of fluid could I use for a pitfall trap that also does not invalidate molecular testing?

What's the best way to measure growth rates in House sparrow chicks from day 2 to day 10?

Do we need to write protocol for a second study of a systematic review that has been registered and published?

How to increase a model accuracy ?

What is the production process of CaFe ferroalloys?

Do I need to do linear regression before running mediation analysis using PROCESS MACRO by Hayes ?

Sample dilution for quantitative analysis using ELISA?