Kumar R., Vassilvitskii S. Generalized distances between rankings. WWW, 2010.
概
有些时候, 我们会有比较两组 ranking 的相似度, 比如:
\[\bm{x} = [x_1, x_2, \ldots, x_i, \ldots, x_j, \ldots, x_n], \\
\bm{y} = [y_1, y_2, \ldots, y_i, \ldots, y_j, \ldots, y_n]. \\
\]
其中 \((x_i, y_i)\) 表示的实例 \(i\) 的两个不同的 score, 我们想知道这两组 scores 的一致性, 相似度.
Kendall rank correlation coefficient
Kendall rank correlation coefficient-wiki
-
称 \((i, j), i \not = j\) 为 concordant 的若
\[x_i < x_j \leftrightarrow y_i < y_j \text{ or } x_i > x_j \leftrightarrow y_i > y_j, \]否则称 \((i, j)\) 为 discordant 的.
-
Kendall's \(\tau\) coefficient 是一个描述序的统计量. 它定义为:
\[\tag{1} \tau = \frac{N_c - N_d}{N} = 1 - \frac{2 N_d}{N}, \]其中 \(N_c\) 为 concordant pairs 的数量, \(N_d\) 为 discordant pairs 的数量, \(N = n(n-1) / 2\).
-
该统计量有如下的性质:
- \(\tau \in [-1, 1]\), 且 \(\tau=-1\) 表示 \(\bm{x}, \bm{y}\) 的序是反的 (最不相似的情况), \(\tau = 1\) 则是表示 \(\bm{x}, \bm{y}\) 完全一致的情况.
- 如果 \(X, Y\) 是独立的, 则 \(\tau=0\).
- (1) 式还可以表示为:\[\tau = \frac{2}{n(n-1)} \sum_{i < j} \text{sgn}(x_i - x_j)\text{sgn}(y_i - y_j). \]
Spearman’s footrule
-
Spearman's footrule 衡量的是从 \(\bm{x}\) 到 \(\bm{y}\) 所需要最小编辑距离:
\[F = \sum_i |i - \sigma(i; \bm{x}, \bm{y})|, \]其中 \(j=\sigma(i; \bm{x}; \bm{y})\) 返回 和 \(x_i\) 在 \(\bm{x}\) 相同序的 \(y_j\) 在 \(\bm{y}\) 中的位置 \(j\).
-
\(F\) 越大, 说明根据 \(\bm{x}, \bm{y}\) 得到的序越不一致.