Kendall tau距离

Kendall tau距离

定义：Kendall tau距离衡量两个序列的相似性，距离越大，相似性越小。具体可用序列a调正次序变为序列b所花费的步骤数来量化。要求序列a和序列b的长度以及元素是一样的。

如$a=\{0,3,1,6,2,5,4\}$，$b=\{1,0,3,6,4,2,5\}$，将a调整顺序化为b的距离

首先为序列 $a$ 定义一个基准，用序列 $aIndex$ 存放 $a$ 各元素对应的索引，如下：

$a$ 和 $aIndex$ 满足： $ aIndex[a[i]] = i$ ，通过索引 $i$ 在 $a$ 中找对应的值，通过值 $a[i]$ 在 $aIndex$ 中找对应的索引。

假若从 $i=0$ 开始去遍历 $a[i]$，然后返回 $aIndex[a[i]]$， 正好可以得到一个有序的序列$\{0,1,2,3,4,5,6\}$。

如果$b==a$ ，那么从从 $i=0$ 开始去遍历 $b[i]$，然后返回 $aIndex[b[i]]$，也应是一个有序的序列。但当$b\ne a$ 时，那么 $aIndex[b[i]]$便不是一个有序的序列。

令 $ bIndex[i] = aIndex[b[i]]$ ，将 $ bIndex[i] $ 从有序变无序的距离便是Kendall tau距离，也即是 $ bIndex[i] $ 中的逆序对数量。

通过上述推导，可将求两个序列的Kendall tau距离转为求映射变换后序列的逆序对数量，可通过归并排序求逆序对。代码如下：

class KendallTau: def __init__(self): self.count = 0 def distance(self, a, b): if len(a) != len(b): return "a和b的数量不相等" n = len(a) aIndex = [0] * n for i in range(n): aIndex[a[i]] = i print(aIndex) bIndex = [0] * n for j in range(n): bIndex[j] = aIndex[b[j]] print(bIndex) return self.mergeCount(bIndex) def mergeCount(self, a): self.count = 0 self.mergeSort(a, 0, len(a) - 1) return self.count def merge(self, a, l, mid, r): i = l j = mid + 1 aux = [] while i <= mid and j <= r: if a[i] > a[j]: aux.append(a[j]) self.count += mid - i + 1 j += 1 else: aux.append(a[i]) i += 1 while i <= mid: aux.append(a[i]) i += 1 while j <= r: aux.append(a[j]) j += 1 i = l for num in aux: a[i] = num i += 1 def mergeSort(self, a, l, r): if l >= r: return mid = l + r >> 1 self.mergeSort(a, l, mid) self.mergeSort(a, mid + 1, r) self.merge(a, l, mid, r) if __name__ == '__main__': kt = KendallTau() a = [0, 3, 1, 6, 2, 5, 4] b = [1, 0, 3, 6, 4, 2, 5] res = kt.distance(a, b) print(res) # 4