Kendall Tau 距离

Goat_Yang2025/12/3约 392 字大约 1 分钟

1. 概念概述

Kendall tau 距离（Kendall tau distance）用于衡量两个排序（permutations）之间相对顺序的不一致程度。
它统计所有顺序相反的成对元素数量，也称为 discordant pairs。

给定两个排序 $\sigma$ 和 $\pi$ （元素相同但顺序可能不同），定义 Kendall tau 距离为：

K(\sigma,\pi)=|\{(i,j): i<j,\ (\sigma(i)-\sigma(j))(\pi(i)-\pi(j))<0\}|

更直观解释：
比较所有 $\frac{n(n-1)}{2}$ 对元素，只要 $\sigma$ 和 $\pi$ 中的相对顺序相反，就计一次距离。

设两个排序：

不一致的仅是 $(2,3)$ ：

因此：

K(\sigma,\pi) = 1

最大距离发生在完全逆序时：

0 \le K(\sigma,\pi) \le \binom{n}{2}

Kendall $\tau$ 相关性定义为：

\tau = 1 - \frac{2K}{\binom{n}{2}}

距离越大，相关性越小。

比较所有成对元素。

可将一个排序映射到另一个的序号序列，然后统计逆序对数，即为 Kendall tau 距离。