# Assessing quality of similarity measure

I'll try to compute different similarity measures on some data. The result is always a similarity matrix on the data.

I want to evaluate the quality of the matrix by checking if the values for positive and negative similarities have a wide spread so that one can set an threshold which is very general to all data. Means, postive and negative similarities should not be close to each other. I have no way to check precision and recall because I'm not in the postition to select threshold yet. I first want to check the optimal similarity measure.

Is there a standard procedure for such a task?

• Similarity measure is selected mostly on the basis of theoretical/logical rationale, not empirically. Is it that you fail to work out the rationale that you go for distributional properties in order to select among measures? Dec 12, 2011 at 10:12
• No i selected differnt similarities that fit the matching idea logically. My problem is to sub-select attributes from the data that fully determine their class (Its a word distribution where only a few words have high probability and the rest i a low probability long tail). Hence i subselect differnt amounts of those words and compare the outcomes of the similarity measure. The target would be an optimal seperation between matches and non matches. In the moment i only look at how the values spread and the optimisation target is to max this spread Dec 12, 2011 at 10:18
• @Andreas, do you want Feature selection / feature elimination ? If so, see RFE in scikit-learn plot_rfe_digits (I recommend linear_model.SGDClassifier). Dec 12, 2011 at 17:39

The common way of evaluating a similarity measure seems to be by using the similarity for a particular task, e.g. information retrieval or kNN classification, and then computing precision$@k$ or the area under the roc curve (ROC AUC).

There is also some literature on calibrating such scores. One should however note that a well calibrated score is not necessarily better; for example a weather prediction that constantly gives the year average as chance of rain is well calibrated, will actually be correct quite often, but is not very useful on a particular day (only in the year average).

In my opinion, there is nothing wrong with evaluating a similarity/distance measure for a single, particular task. There are tons of examples for such measures that - just like feature extraction - work well for one task, but not for another. Dynamic time warping distance, for example, just fails badly when you look at sine curves of different frequencies.

Have a look at for example:

• Houle, Kriegel, Kröger, Schubert, Zimek
"Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?" Scientific and Statistical Database Management SSDBM 2010.

• Bernecker, Houle, Kriegel, Kröger, Renz, Schubert, Zimek
"Quality of Similarity Rankings in Time Series". Advances in Spatial and Temporal Databases SSTD 2011.

This pair of publications seem to do a similar task as you are doing: evaluating whether or not shared-neighbor similarities improve over existing distance measures. IIRC correctly, they also look at the contrast provided by the distance measures, but I'm not sure if they measured this contrast numerically.

If you cannot select the treshold yet, a classic ROC curve might do the trick for you. The area under the ROC curve gives you a good estimation of how well a treshold can work. There is a probabilistic interpretation of ROC curves that is as follows: taken two examples, one positive and one negative: the AUC value is the likelyhood that the two examples will be ranked in the correct order. An AUC of 100% means that they are always right; a value of 0% is they are always wrong, and 50% is the outcome of a randomized ranking. (I do however not have a reference or proof for this interpretation, and it might be numerically off. I do remember having read this somewhere, though, that the ROC AUC equals this statistic)

On the other hand, the ROC AUC does not take the actual values into account, only the ranking. So it does not tell you whether or not it is easy to select the threshold. The publications by Houle et al. above had some pretty nice histogram plots for this, where you could visually tell that for the SNN distances they could just choose 0.5 as threshold, while for other distances there was just no working threshold at all (and the distances were numerically essentially unbounded, while SNN was 0 to 1)