1

这是Scala中Kendall tau 距离的正确实现吗

def distance[A : Ordering](s: Seq[A], t: Seq[A]): Int = {
  assert(s.size == t.size, "Both sequences should be of the same length")

  s.combinations(2).zip(t.combinations(2)).count { 
    case (Seq(s1, s2), Seq(t1, t2)) =>
      (s1 > s2 && t1 < t2) || (s1 < s2 && t1 > t2)
  }
}

问题是我没有足够的数据来测试算法，只有来自维基百科的几个例子。而且我对算法的理解还不够好，无法生成自己的测试数据。大多数来源是关于Kendall tau 等级相关系数，这是相关但不同的动物。也许我可以以某种方式从另一个中得出一个？

现在让我们说性能并不重要。

更新

所以，现在我有了 Kendall tau 距离算法的三个实现。其中两个 (distance1和distance3) 给出相同的结果（见下文）。那么，哪一个是正确的？

import scala.math.Ordering.Implicits._

val permutations = Random.shuffle((0 until 5).permutations).take(100)

println("s\tt\tDist1\tDist2\tDist3")
permutations.sliding(2).foreach { case Seq(s, t) =>
  println(s.mkString(",")+"\t"+t.mkString(",")+"\t"+distance1(s, t)+"\t"+distance2(s, t)+
    "\t"+distance3(s, t))
}

def distance1[A : Ordering](s: Seq[A], t: Seq[A]): Int = {
  assert(s.size == t.size, "Both sequences should be of the same length")

  s.combinations(2).zip(t.combinations(2)).count { case (Seq(s1, s2), Seq(t1, t2)) =>
    (s1 > s2 && t1 < t2) || (s1 < s2 && t1 > t2)
  }
}

def distance2[A](a: Seq[A], b: Seq[A]): Int = {
  val aMap = a.zipWithIndex.toMap // map of a items to their ranks
  val bMap = b.zipWithIndex.toMap // map of b items to their ranks

  a.combinations(2).count{case Seq(i, j) =>
    val a1 = aMap.get(i).get // rank of i in A
    val a2 = aMap.get(j).get // rank of j in A
    val b1 = bMap.get(i).get // rank of i in B
    val b2 = bMap.get(j).get // rank of j in B
    a1.compare(a2) != b1.compare(b2)
  }
}

def distance3(τ_1: Seq[Int], τ_2: Seq[Int]) =
  (0 until τ_1.size).map { i =>
    (i+1 until τ_2.size).count { j =>
      (τ_1(i) < τ_1(j) && τ_2(i) > τ_2(j)) || (τ_1(i) > τ_1(j) && τ_2(i) < τ_2(j))
    }
  }.sum

以下是一些结果：

s   t   Dist1   Dist2   Dist3
3,0,4,2,1   1,4,3,0,2   6   6   6
1,4,3,0,2   0,4,1,2,3   3   5   3
0,4,1,2,3   4,0,1,3,2   8   2   8
4,0,1,3,2   1,2,0,4,3   4   6   4
1,2,0,4,3   2,3,1,4,0   3   5   3
2,3,1,4,0   1,0,3,2,4   8   6   8
1,0,3,2,4   1,3,2,4,0   7   3   7
1,3,2,4,0   4,3,0,1,2   6   6   6
4,3,0,1,2   1,0,2,4,3   7   7   7
1,0,2,4,3   3,4,1,2,0   8   8   8
3,4,1,2,0   1,4,2,0,3   5   5   5
1,4,2,0,3   1,0,3,4,2   8   4   8
4

2 回答 2

1

我不认为这是完全正确的。这是一些快速编写的代码，强调您要比较的是序列中项目的排名（get(n).get尽管您并不真的希望将这些调用保留在代码中）。我也用过compare，我认为这是有道理的：

def tauDistance[A](a: Seq[A], b: Seq[A]) = {
  val aMap = a.zipWithIndex.toMap // map of a items to their ranks
  val bMap = b.zipWithIndex.toMap // map of b items to their ranks
  a.combinations(2).count{case Seq(i, j) =>
    val a1 = aMap.get(i).get // rank of i in A
    val a2 = aMap.get(j).get // rank of j in A
    val b1 = bMap.get(i).get // rank of i in B
    val b2 = bMap.get(j).get // rank of j in B
    a1.compare(a2) != b1.compare(b2)
  }
}
于 2014-07-08T19:42:41.843 回答
1

因此，维基百科在元素的等级上定义了 K，如下所示：

K(τ_1,τ_2) = |{(i,j): i < j, (τ_1(i) < τ_1(j) && τ_2(i) > τ_2(j)) || (τ_1(i) > τ_1(j) && τ_2(i) < τ_2(j))}|

我们可以直接在 Scala 中实现这一点，记住输入是等级序列，而不是项目本身：

def K(τ_1: Seq[Int], τ_2: Seq[Int]) = 
  (0 until τ_1.size).map{i => 
    (i+1 until τ_2.size).count{j => 
      (τ_1(i) < τ_1(j) && τ_2(i) > τ_2(j)) || (τ_1(i) > τ_1(j) && τ_2(i) < τ_2(j))
    }
  }.sum

这实际上比tauDistance上面的函数更可取，因为该函数假定所有项目都是唯一的（如果序列有重复，则会失败），而这个函数直接在等级上工作。

使用组合函数有时很困难，仅仅通过单元测试通常是不够的。

于 2014-07-09T12:37:48.307 回答