두 목록 간의 순서 차이를 평가하는 알고리즘

Question

두 시퀀스를 비교하는 알고리즘을 찾고 있습니다.

시퀀스 A -

시퀀스 B 최적 위해 정수 ID 목록 것 - 다를 수 순서로 동일한 ID 목록 것이다.

두 목록 간의 순서 차이를 감지하고 싶습니다.

그리고 이와 같이 알고리즘을 찾고 있습니다. 이것이 당신이 단지 그들이 얼마나 다른을 측정 할 경우

Answer 1

전에 해결 된 일반적인 문제 있는지 궁금하고 있지만, 차이가 발생하는 경우, 당신은 Kendall's correlation coefficient를 사용할 수 있습니다 당신은 상관하지 않습니다. 그것은 -1 점 (목록은 역순)에서 +1 점 (목록은 같은 순서 임)의 점수를줍니다.

int[] a = { 1, 2, 3, 4, 5, 6, 7, 8 }; 
int[] b = { 3, 4, 1, 8, 6, 7, 2, 5 }; 

double numer = 0; 
for (int i = 0; i < (a.Length - 1); i++) 
    for (int j = i + 1; j < a.Length; j++) 
    numer += Math.Sign(a[i] - a[j]) * Math.Sign(b[i] - b[j]); 

double tau = numer/(a.Length * (a.Length - 1)/2); 

Answer 2

줄리안 URBANO가 제안한 것처럼, 켄달 타우 상관 관계가 좋다 :

그것은 기본적으로 쌍 총 수에 의해 두 목록의 순서에있는 요소 쌍의 수와 격차를 계산 사용할 측정. Linq를 사용하여 .Net에서 구현하기로 결정했습니다. Tau-A (넥타이가없는 데이터의 경우)와 Tau-B (넥타이가 허용되는 경우)를 구현하는 코드는 다음과 같습니다. 이 코드에서는 데이터가 아직 정렬되지 않았다고 가정하므로 Measure1에 따라 Measure1에 따라 한 번 정렬하여 순위 값의 첫 번째 집합을 가져온 다음 Measure2로 정렬하여 두 번째 순위 집합을 가져옵니다. 원래 데이터가 아닌 상관 관계가있는 순위입니다. (측정 람다 함수가 변경되지 않은 원래의 객체를 돌려주는 경우, 당신은 당신이 이미 가지고있는 계급에 적용 할 수 있습니다.) 여기

using System; 
using System.Collections.Generic; 
using System.Linq; 
using static System.Math; 

namespace Statistics 
{ 
    /// <summary> 
    /// Compute the Kendall Tau Correlation of two orderings of values, a non-parametric correlation that compares the ranking 
    /// of value, not the values themselves. 
    /// 
    /// The correlation of the measures is one if all values are in the same order when sorted by two different measures. 
    /// The correlation is minus one if the second ordering is the reverse of the first. 
    /// The correlation is zero if the values are completely uncorrelated. 
    /// 
    /// Two algorithms are provided: TauA and TauB. TauB accounts properly for duplicate values (ties), unlike TauA. 
    /// </summary> 
    public class KendallTauCorrelation<T, C> where C : IComparable<C> 
    { 
     private Func<T, C> Measure1 { get; } 
     private Func<T, C> Measure2 { get; } 

     public KendallTauCorrelation(Func<T, C> measure1, Func<T, C> measure2) 
     { 
      Measure1 = measure1; 
      Measure2 = measure2; 
     } 

     /// <summary> 
     /// Compute the Tau-a rank correlation, which is suitable if there are no ties in rank. 
     /// </summary> 
     /// <returns>A value between -1 and 1. 
     /// If the measures are ranked the same by both measures, returns 1. 
     /// If the measures are ranked in exactly opposite order, return -1. 
     /// The more items that are out of sequence, the lower the score. 
     /// If the measures are completely uncorrelated, returns zero. 
     /// </returns> 
     /// <param name="data">Data to be ranked according to two measures and then correlated.</param> 
     public double TauA(IList<T> data) 
     { 
      var ranked = data 
        .OrderBy(Measure1) 
        .Select((item, index) => new { Data = item, Rank1 = index + 1}) 
        .OrderBy(pair => Measure2(pair.Data)) 
        .Select((pair, index) => new { pair.Rank1, Rank2 = index + 1 }) 
        .ToList(); 
      var numerator = 0; 

      var n = ranked.Count; 
      var denominator = n * (n - 1)/2.0; 
      for (var i = 1; i < n; i++) 
       for (var j = 0; j < i; j++) 
       { 
        numerator += Sign(ranked[i].Rank1 - ranked[j].Rank1) 
           * Sign(ranked[i].Rank2 - ranked[j].Rank2); 
       } 
      return numerator/denominator; 
     } 

     /// <summary> 
     /// Compute the Tau-b correlation, which accounts for ties. 
     /// 
     ///    n - n 
     ///    c d 
     /// τ = ----------------------- 
     /// b _____________________ 
     ///  /(n - n)(n - n) 
     ///  √ 0  1 0  2 
     /// 
     /// where: 
     ///  n0 = n(n-1)/2 
     ///    
     ///  n1 = Σ t (t - 1)/2 
     ///    i i i 
     /// 
     ///  n2 = Σ t (t - 1)/2 
     ///    j j j 
     /// 
     ///  t[i] = # of ties for the ith group according to measure 1. 
     ///  t[j] = # of ties for the jth group according to measure 2. 
     ///  nc = # of concordant pairs 
     ///  nd = # of discordant pairs 
     /// </summary> 
     /// <returns>A correlation value between -1 (perfect reverse correlation) 
     /// and +1 (perfect correlation). 
     /// Zero means uncorrelated. </returns> 
     /// <param name="data">Data.</param> 
     public double TauB(IEnumerable<T> data) 
     { 
      // Compute two Ranks by sorting first by Measure1 and then by Measure2. 
      // Group by like values of each in order to handle ties. 
      var ranked = data.Select(item => new { M1 = Measure1(item), M2 = Measure2(item) }) 
       .GroupBy(measures => new { measures.M1 }) 
       .OrderBy(@group => @group.First().M1) 
       .ThenBy(@group => @group.First().M2) 
       .AsEnumerable() 
       .Select((@group, groupIndex) => new 
       { 
        Measure1Ranked = @group.Select((measure, index) => new { measure.M1, measure.M2 }), 
        Rank = ++groupIndex 
       }) 
       .SelectMany(v => v.Measure1Ranked, (s, i) => new 
       { 
        i.M1, 
        i.M2, 
        DenseRank1 = s.Rank 
       }) 
       .GroupBy(measures => new { measures.M2 }) 
       .OrderBy(@group => @group.First().M2) 
       .ThenBy(@group => @group.First().M1) 
       .AsEnumerable() 
       .Select((@group, groupIndex) => new 
       { 
        Measure2Ranked = @group.Select((measure, index) => new { measure.M1, measure.M2, measure.DenseRank1 }), 
        Rank = ++groupIndex 
       }) 
       .SelectMany(v => v.Measure2Ranked, (s, i) => new { i.M1, i.M2, i.DenseRank1, DenseRank2 = s.Rank })       
       .ToArray(); 
      if (ranked.Length <= 1) 
       return 0; // No data or one data point. Impossible to establish correlation. 

      // Now that we have ranked the data, compute the correlation. 
      var n = ranked.Count(); 
      var n0 = n * (n - 1)/2; 
      var n1 = 0; 
      var n2 = 0; 
      var numerator = 0; // Stores nc - nd as a single value, rather than computing them separately. 
      for (var i = 1; i < n; i++) 
       for (var j = 0; j < i; j++) 
       { 
        var iRanked = ranked[i]; 
        var jRanked = ranked[j]; 
        numerator += Sign(iRanked.DenseRank1 - jRanked.DenseRank1) 
           * Sign(iRanked.DenseRank2 - jRanked.DenseRank2); 
        // Keep track of ties. Because we are running the indices in a triangle, 
        // we automatically get this for n1 and n2: ties * (ties - 1)/2 
        if (iRanked.M1.CompareTo(jRanked.M1) == 0) 
         n1++; 
        if (iRanked.M2.CompareTo(jRanked.M2) == 0) 
         n2++; 
       } 
      if (n0 == n1 || n0 == n2) 
       return 0; // All ties, so everything as the same rank. 
      // Observe that if n1 = n2 = 0, that this formula is identical to Tau-a. 
      return numerator/Sqrt((double)(n0 - n1)*(n0 - n2)); 
     } 
    } 
} 

이 NUnit과에 단위 테스트입니다

using System; 
using NUnit.Framework; 
using static System.Math; // New C# 6.0 feature that allows one to import static methods and call them without their class name. 

namespace Statistics 
{ 

    [TestFixture] 
    public class KendallTauCorrelationTests 
    { 
     public static int[] OneToTen = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 

     #region Tau-a 

     [Test] 
     public void TauA_SameOrder() 
     { 
      var kendall = new KendallTauCorrelation<int, int>(
       (int value) => value, 
       (int value) => value * 10 
      ); 
      Assert.AreEqual(
       1.0, 
       kendall.TauA(OneToTen), 
       "Numbers that sort in the same order should be perfectly correlated." 
      ); 
     } 

     [Test] 
     public void TauA_ReverseOrder() 
     { 
      var kendall = new KendallTauCorrelation<int, int>(
       (int value) => value, 
       (int value) => value * -10 
      ); 
      Assert.AreEqual(
       -1.0, 
       kendall.TauA(OneToTen), 
       "Numbers that sort in reverse order should be perfectly anti-correlated." 
      ); 
     } 

     [Test] 
     public void TauA_OneSwap() 
     { 
      var reordered = new[] { 1, 2, 3, 5, 4, 6, 7, 8, 9, 10 }; 
      var kendall = new KendallTauCorrelation<int, int>(
       (int value) => value, 
       (int value) => reordered[value - 1] 
      ); 
      Assert.AreEqual(
       43.0/45.0, 
       kendall.TauA(OneToTen), 
       0.00001, 
       "If a single number is out of place the sequences should be almost perfectly correlated." 
      ); 
     } 

     #endregion 

     #region Tau-b 

     [Test] 
     public void TauB_SameOrder() 
     { 
      var kendall = new KendallTauCorrelation<int,int>(
       (int value) => value, 
       (int value) => value * 10 
      ); 
      Assert.AreEqual(
       1.0, 
       kendall.TauB(OneToTen), 
       "Numbers that sort in the same order should be perfectly correlated." 
      ); 
     } 

     [Test] 
     public void TauB_ReverseOrder() 
     { 
      var kendall = new KendallTauCorrelation<int, int>(
       (int value) => value, 
       (int value) => value * -10 
      ); 
      Assert.AreEqual(
       -1.0, 
       kendall.TauB(OneToTen), 
       "Numbers that sort in reverse order should be perfectly anti-correlated." 
      ); 
     } 

     [Test] 
     public void TauB_OneSwap_NoTies() 
     { 
      var reordered = new[] { 1,2,3,5,4,6,7,8,9,10 }; 
      var kendall = new KendallTauCorrelation<int, int>(
       (int value) => value, 
       (int value) => reordered[value-1] 
      ); 
      Assert.AreEqual(
       43.0/45.0, 
       kendall.TauB(OneToTen), 
       0.00001, 
       "If a single number is out of place the sequences should be almost perfectly correlated." 
      ); 
     } 

     [Test] 
     public void TauB_Ties() 
     { 
      var reordered = new[] { 1, 1, 1, 4, 5, 6, 7, 8, 9, 10 }; 
      var kendall = new KendallTauCorrelation<int, int>(
       (int value) => value, 
       (int value) => reordered[value - 1] 
      ); 
      Assert.AreEqual(
       42.0/Sqrt(42.0*45.0), 
       kendall.TauB(OneToTen), 
       0.00001, 
       "Adding a few ties should be almost perfectly correlated." 
      ); 
     } 

     #endregion 
    } 
} 

참고 :이를 O (N^2) 알고리즘을 사용합니다. 이미 언급 한 N Log N이라는 수정 된 mergesort를 사용하는 것이 더 효율적인 방법이지만, 어떻게 완료되었는지는 알지 못합니다.

참고 :이 일반 클래스는 두 측정 값이 모두 동일한 데이터 형식을 반환한다고 가정합니다. 클래스에 두 가지 일반 측정 유형이있는 것은 쉬운 변경입니다. 그들은 IComparables 일 필요가 있습니다. 그들은 서로 비교할 필요가 없습니다.