1

これは ScalaでのKendall タウ距離の正しい実装ですか?

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 タウ距離アルゴリズムの 3 つの実装ができました。そのうちの 2 つ (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 に答える