Changeset 8355

Timestamp:

07/30/12 11:08:14 (12 years ago)

Author:

gkronber

Message:

#1292: fixed bugs in HoeffdingsDependenceCalculator, added test cases for HoeffdingsDependenceCalculator

Location:

trunk/sources

Files:

• HeuristicLab.Problems.DataAnalysis/3.4/OnlineCalculators/HoeffdingsDependenceCalculator.cs (modified) (2 diffs)
• HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis-3.4/StatisticCalculatorsTest.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Problems.DataAnalysis/3.4/OnlineCalculators/HoeffdingsDependenceCalculator.cs

@@ -103 +103 @@
 
     /// <summary>
-    /// Calculates midranks. Source: Numerical Recipes in C.
+    /// Calculates midranks. Source: Numerical Recipes in C. p 642
     /// </summary>
     /// <param name="w">Sorted array of elements, replaces the elements by their rank, including midranking of ties</param>
@@ -117 +117 @@
         } else {
           int j;
-          for (j = i + 1; j < n && w[j] <= w[i]; j++) ; // how far does it go (<= effectively means == as w must be sorted)
-          double rank = 0.5 * (i + j - 1);
+          for (j = i + 1; j < n && w[j] <= w[i]; j++) ; // how far does it go (<= effectively means == as w must be sorted, side-step equality for double values)
+          double rank = 1 + 0.5 * (i + j - 1);
           int k;
-          for (k = i; k < j - 1; k++) w[k] = rank; // set the rank for all tied entries
+          for (k = i; k < j; k++) w[k] = rank; // set the rank for all tied entries
           i = j;
         }
       }
 
-      if (i == n - 1) w[n - 1] = n - 1;   // if the last element was not tied, this is its rank
+      if (i == n - 1) w[n - 1] = n;   // if the last element was not tied, this is its rank
     }
   }

trunk/sources/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis-3.4/StatisticCalculatorsTest.cs

@@ -139 +139 @@
       }
     }
+
+    [TestMethod]
+    public void CalculateHoeffdingsDTest() {
+      OnlineCalculatorError error;
+      // direct perfect dependency
+      var xs = new double[] { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0 };
+      var ys = new double[] { 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0 };
+      var d = HoeffdingsDependenceCalculator.Calculate(xs, ys, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, 1.0, 1E-5);
+
+      // perfect negative dependency
+      ys = xs.Select(x => -x).ToArray();
+      d = HoeffdingsDependenceCalculator.Calculate(xs, ys, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, 1.0, 1E-5);
+
+      // ties
+      xs = new double[] { 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0, 5.0, 5.0, 5.0 };
+      ys = new double[] { 2.0, 2.0, 3.0, 3.0, 4.0, 4.0, 5.0, 5.0, 6.0, 6.0, 6.0 };
+      d = HoeffdingsDependenceCalculator.Calculate(xs, ys, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, 0.6783, 1E-5);
+
+      // ties
+      xs = new double[] { 1.0, 1.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 6.0, 6.0 };
+      ys = xs.Select(x => x * x).ToArray();
+      d = HoeffdingsDependenceCalculator.Calculate(xs, ys, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, 0.75, 1E-5);
+
+      // degenerate
+      xs = new double[] { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 };
+      ys = new double[] { 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0 };
+      d = HoeffdingsDependenceCalculator.Calculate(xs, ys, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, -0.3516, 1E-4);
+
+
+      var normal = new HeuristicLab.Random.NormalDistributedRandom(new HeuristicLab.Random.MersenneTwister(31415), 0, 1);
+
+      xs = Enumerable.Range(0, 1000).Select(i => normal.NextDouble()).ToArray();
+      ys = Enumerable.Range(0, 1000).Select(i => normal.NextDouble()).ToArray();
+
+      // independent
+      d = HoeffdingsDependenceCalculator.Calculate(xs, ys, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, -0.00023, 1E-5);
+
+
+      xs = Enumerable.Range(0, 1000).Select(i => normal.NextDouble()).ToArray();
+      ys = xs.Select(x => x * x).ToArray();
+
+      d = HoeffdingsDependenceCalculator.Calculate(xs, ys, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, 0.25071, 1E-5);
+
+      // symmetric?
+      d = HoeffdingsDependenceCalculator.Calculate(ys, xs, out error);
+      Assert.AreEqual(error, OnlineCalculatorError.None);
+      Assert.AreEqual(d, 0.25071, 1E-5);
+
+    }
   }
 }