Let's say I have a strict ranked set of samples.

I only have a similarity measure $s$. I want to evaluate how good this similarity measure is at ranking the examples.

One approach would be to use a simplified version of d-ranking with only 3 points at a time instead of 4.

For example, I sample instance A, B, and C. Without loss of generality, A < B < C in my ranking. If s(A, B) > s(A, C) and s(B, C) > s(A, C), then the accuracy is one on this triplet. And I repeat.

Is there a better way to evaluate how good a similarity measure is, against a ranked set of samples?

One alternative would be to find the instances with the furthest distance, then use Dijkstra's algorithm to find the minimum shortest path, and then compute a spearman over that ranking. I don't love this because it assumes that the distance measure is additive. Alternately, I could greedily create edges between the nearest points, but enforce I create a path, i.e. no node has more that 2 edges. I still don't love this because it seems to do fewer evaluations than the original triplet-accuracy d-ranking method I propose.

Another alternative that I am leaning towards is this:

  • Pick the lowest rank item in the set. Order all the instances by distance from lowest. Compute spearman.
  • As before, but with the highest rank item in the set. Compute spearman.

Slightly more fancy:

  • For every point:
  • The difficulty is to know whether other points are above or below it. So pick the orientation based upon the other point's distance from min and max points.
  • Do spearman as before but over all the points.

Your Answer

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

Browse other questions tagged or ask your own question.