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.