algorithm - Kendall 距离和 Kendall tau 距离有什么区别？

Question

我现在正尝试使用 Kendall 的距离来改进基于 Borda 计数方法的排名集。

我被要求遵循特定文档的说明。在文档中指出:

“Kendall 距离将来自两个排名的项目之间的成对差异计算为:

在哪里

Kendall 距离由其最大值 C2n 归一化。肯德尔距离越小，排名之间的相似度越大。

Kendall's tau 是另一种衡量排名之间相似度的方法，容易与Kendall's distance 混淆。Kendall 的 tau 定义为:

Kendall 的 tau 是根据归一化的 Kendall 距离定义的。请注意，Kendall's tau 越大，则比较排名之间的相似度越大。在本文中，我们使用肯德尔距离而不是肯德尔 tau 距离。”

我的目标是通过使用 Kendall 的距离来提高以下排名:

    x1 x2 x3 x4
A1  4  1  3  2
A2  4  1  3  2
A3  4  3  2  1
A4  1  4  3  2
A5  1  2  4  3

在这个排名中，第i行代表根据Ai得到的排名，每一列代表相应item在每个排名中的排名位置。 (即xn代表待排序的item，Ai代表对item进行排序的人。)

尽管有文档的解释，我还是不明白这两个距离之间有什么区别。 sigma 符号下方的“(j,s), j != s”代表什么？最后，如何在上面提供的排名中实现 Kendall 的距离？

Answer 1

距离和相似度是两个相关的概念，但对于距离而言，完全相同意味着距离为0，随着事物越来越不同，它们之间的距离越来越大，没有非常明显的固定界限。良好的距离将遵守度量规则 - 请参阅 https://en.wikipedia.org/wiki/Metric_(mathematics) .对于相似度，精确恒等表示相似度为 1，相似度随着事物变大而降低，但通常不会降低到 0 以下。Kendall 的 tau 似乎是将 Kendall 的距离转化为相似度的一种方式。

"(j,s), j != s"表示考虑 j 和 s 的所有可能性，除了那些 j = s 的可能性。

您可以通过简单地对 j 不等于 s 的所有可能性求和来计算 Kendall 的距离 - 但这样做所花费的时间与项目数量的平方成正比。有一些方法可以使花费的时间仅上升为 n * log(n)，其中 n 是项目的数量 - 关于这个和 Kendall 上的许多其他内容，请参见 https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient