тау Кендалла расстояние в Scala

Question

Является ли это правильное выполнение Kendall tau distance в Scala

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 rank correlation coefficient, что связано, но разные животные. Может быть, я мог бы каким-то образом получить один от другого?

На данный момент предположим, что производительность не важна.

UPDATE

Итак, теперь у меня есть три реализации алгоритма тау Кендалла расстояния. Два из них (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 

Answer 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) 
    } 
} 

Answer 2

Так, Википедия определяет 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 функция выше, так как эта функция предполагает, что все элементы уникальны (и так потерпит неудачу, если последовательности имеют дубликаты), в то время как эта работает непосредственно в рядах.

Работа с комбинаторными функциями - это hard иногда, и этого часто бывает недостаточно, чтобы пройти единичные тесты.