Changeset 8744 for branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/InformationAnalysis.cs

Timestamp:

10/05/12 12:36:25 (12 years ago)

Author:

epitzer

Message:

Improve Information Analyzer #1696

• Configurable discretized or full quantile analysis
• Configurable shape size
• Include peak information values and deltas in results

File:

• branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/InformationAnalysis.cs (modified) (4 diffs)

branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/InformationAnalysis.cs

@@ -29 +29 @@
     public Peak PeakTotalEntropy { get; private set; }
 
-    public InformationAnalysis(IList<double> qualities, int nQuantiles) {
+    public InformationAnalysis(IList<double> qualities, int nQuantiles, int shapeSize) {
       InformationContent = new List<double>();
       PartialInformationContent = new List<double>();
@@ -35 +35 @@
       TotalEntropy = new List<double>();
       QualityDelta = new List<double>();
-      PerformAnalysis(qualities, nQuantiles);
-    }
-
-    private void PerformAnalysis(IList<double> qualities, int nQuantiles) {
+      if (shapeSize < 1)
+        throw new ArgumentException("Shape size must be at least 1 (better 2)");
+      if (qualities.Count > 1)
+        PerformAnalysis(qualities, nQuantiles, shapeSize);
+    }
+
+    private void PerformAnalysis(IList<double> qualities, int nQuantiles, int shapeSize) {
       var differences = Differences(qualities).ToList();
-      InformationStability = differences.Select(d => Math.Abs(d)).Max();
+      InformationStability = differences.Select(Math.Abs).Max();
       Regularity = new HashSet<double>(differences).Count;
       Diversity = new HashSet<double>(qualities).Count;
-      //var thresholds = UniqueThresholdCalculator.DetermineThresholds(differences, nQuantiles).ToList();
-      var thresholds = differences.Select(d => Math.Abs(d)).OrderBy(d => d);
+      var thresholds = (nQuantiles == 0
+                         ? differences.Select(Math.Abs).OrderBy(d => d)
+                         : UniqueThresholdCalculator.DetermineThresholds(differences, nQuantiles)).ToList();
       foreach (var eps in thresholds) {
-        var shapes = Shapes(eps, differences).ToList();
-        int[] shapeCounts = CountShapes(shapes);
-        QualityDelta.Add(eps);
-        InformationContent.Add(CalculateInformationContent(shapeCounts, shapes.Count));
-        PartialInformationContent.Add(CalculatePartialInformationContent(eps, differences));
-        DensityBasinInformation.Add(CalculateDensityBasinInformation(shapeCounts, shapes.Count));
-        TotalEntropy.Add(CalculateTotalEntropy(shapeCounts, shapes.Count));
+        if (QualityDelta.Count > 0 && QualityDelta.Last() == eps) {
+          QualityDelta.DuplicateLast();
+          InformationContent.DuplicateLast();
+          DensityBasinInformation.DuplicateLast();
+          TotalEntropy.DuplicateLast();
+          PartialInformationContent.DuplicateLast();
+        } else {
+          var slopes = Slopes(eps, differences).ToList();
+          var shapes = Shapes(shapeSize, slopes).ToList();
+          var shapeCounts = CountShapes(shapes);
+          QualityDelta.Add(eps);
+          InformationContent.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.NonUni), shapeCounts, shapes.Count));
+          DensityBasinInformation.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.Uni), shapeCounts, shapes.Count));
+          TotalEntropy.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.Any), shapeCounts, shapes.Count));
+          PartialInformationContent.Add(CalculatePartialInformationContent(eps, differences));
+        }
       }
       PeakInformationContent = GetPeak(QualityDelta, InformationContent);
@@ -65 +78 @@
     }
 
-    public enum Shape {
-      DecDec = -4,
-      EquDec = -3,
-      IncDec = -2,
-      DecEqu = -1,
-      EquEqu = 0,
-      IncEqu = 1,
-      DecInc = 2,
-      EquInc = 3,
-      IncInc = 4
-    }
-
-    private static IEnumerable<Shape> Shapes(double eps, IEnumerable<double> differences) {
-      return Utils.Delta(differences, (x, y) =>
-        (Shape)
-          ((x > eps ? 1 : (x < -eps ? -1 : 0)) +
-           (y > eps ? 3 : (y < -eps ? -3 : 0))));
-    }
-
-    private static double CalculateInformationContent(int[] shapeCounts, int totalNShapes) {
-      return
-        -Entropy(shapeCounts[(int)Shape.EquDec + 4], totalNShapes, 6)
-        - Entropy(shapeCounts[(int)Shape.IncDec + 4], totalNShapes, 6)
-        - Entropy(shapeCounts[(int)Shape.DecEqu + 4], totalNShapes, 6)
-        - Entropy(shapeCounts[(int)Shape.IncEqu + 4], totalNShapes, 6)
-        - Entropy(shapeCounts[(int)Shape.DecInc + 4], totalNShapes, 6)
-        - Entropy(shapeCounts[(int)Shape.EquInc + 4], totalNShapes, 6);
-    }
-
-    private static double CalculateDensityBasinInformation(int[] shapeCounts, int totalNShapes) {
-      return
-        -Entropy(shapeCounts[(int)Shape.DecDec + 4], totalNShapes, 3)
-        - Entropy(shapeCounts[(int)Shape.EquEqu + 4], totalNShapes, 3)
-        - Entropy(shapeCounts[(int)Shape.IncInc + 4], totalNShapes, 3);
-    }
-
-    private static double CalculateTotalEntropy(int[] shapeCounts, int totalNShapes) {
-      return shapeCounts.Aggregate(0.0, (current, t) => current - Entropy(t, totalNShapes, 9));
+    public enum Slope {
+      Up = 1,
+      Flat = 0,
+      Down = -1
+    }
+
+    public class Shape : IEnumerable<Slope>, IComparable<Shape> {
+
+      #region types, fields and properties
+      public enum Form {Uni, NonUni, Any}
+
+      private readonly Slope[] slopes;
+
+      private static readonly Dictionary<Tuple<Form, int>, IList<Shape>> SHAPES =
+        new Dictionary<Tuple<Form,int>,IList<Shape>>();
+      #endregion
+
+      public Shape(IEnumerable<Slope> slopes) {
+        this.slopes = slopes.ToArray();
+      }
+
+      #region static methods
+
+      public static Shape Get(params Slope[] slopes) {
+        return new Shape(slopes);
+      }
+
+      public static IList<Shape> GetAll(int size, Form type) {
+        var key = Tuple.Create(type, size);
+        IList<Shape> allShapes;
+        if (!SHAPES.TryGetValue(key, out allShapes)) {
+          allShapes = CreateAll(size, type).ToList();
+          SHAPES[key] = allShapes;
+        }
+        return allShapes;
+      }
+
+      private static IEnumerable<Shape> CreateAll(int size, Form type) {
+        if (size == 0) {
+          yield return Get();
+        } else {
+          foreach (var s in CreateAll(size - 1, type)) {
+            foreach (var s2 in s.ExtendAll(type))
+              yield return s2;
+          }
+        }
+      }
+      #endregion
+
+      private Shape Extend(Slope s) {
+        return new Shape(slopes.Concat(new[] {s}));
+      }
+
+      private IEnumerable<Shape> ExtendAll(Form t) {
+        if (Length == 0 || t == Form.Any) {
+          yield return Extend(Slope.Up);
+          yield return Extend(Slope.Flat);
+          yield return Extend(Slope.Down);
+        } else if (t == Form.Uni) {
+          yield return Extend(slopes[0]);
+        } else if (t == Form.NonUni) {
+          if (slopes.Last() != Slope.Up) yield return Extend(Slope.Up);
+          if (slopes.Last() != Slope.Flat) yield return Extend(Slope.Flat);
+          if (slopes.Last() != Slope.Down) yield return Extend(Slope.Down);
+        }
+      }
+
+      public int Length {
+        get { return slopes.Length; }
+      }
+
+      public Slope this[int i] {
+        get { return slopes[i]; }
+      }
+
+      #region IEnumerable Members
+      public IEnumerator<Slope> GetEnumerator() {
+        return (IEnumerator<Slope>) slopes.GetEnumerator();
+      }
+      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
+        return GetEnumerator();
+      }
+      #endregion
+
+      #region IComparable Members
+
+      public int CompareTo(Shape other) {
+        if (other.Length < Length)
+          return -1;
+        if (other.Length > Length)
+          return 1;
+        for (var i = 0; i<Length; i++) {
+          var d = slopes[i].CompareTo(other.slopes[i]);
+          if (d != 0)
+            return d;
+        }
+        return 0;
+      }
+      public override bool Equals(object obj) {
+        var s = obj as Shape;
+        if (s == null) return false;
+        return CompareTo(s) == 0;
+      }
+      public override int GetHashCode() {
+        return slopes.Aggregate(0, (a, s) => a*3 + ((int) s + 1)).GetHashCode();
+      }
+
+      #endregion
+
+      private string asString;
+      public override string ToString() {
+        return asString ?? (asString = string.Join("", slopes.Select(s => (s == Slope.Down ? "v" : (s == Slope.Up ? "^" : "-")))));
+      }
+    }
+
+    private static IEnumerable<Slope> Slopes(double eps, IEnumerable<double> differences) {
+      return differences.Select(d => (d > eps ? Slope.Up : (d < -eps ? Slope.Down : 0)));
+    }  
+
+    private static IEnumerable<Shape> Shapes(int size, IEnumerable<Slope> slopes) {
+      var q = new Queue<Slope>();
+      foreach (var s in slopes) {
+        q.Enqueue(s);
+        if (q.Count < size) continue;
+        yield return new Shape(q);
+        q.Dequeue();
+      }
+    }
+
+    private static double CalculateEntropy(IList<Shape> shapes, Dictionary<Shape, int> shapeCounts, int totalNShapes) {
+      return shapes.Aggregate(0.0, (current, s) => current - Entropy(shapeCounts.GetValueOrDefault(s, 0), totalNShapes, shapes.Count));
     }
 
@@ -120 +226 @@
     }
 
-    private static int[] CountShapes(IEnumerable<Shape> shapes) {
-      int[] shapeCounts = new int[9];
-      foreach (var s in shapes) {
-        shapeCounts[(int)s + 4]++;
-      }
+    private static Dictionary<Shape, int> CountShapes(IEnumerable<Shape> shapes) {
+      var shapeCounts = new Dictionary<Shape, int>();
+      foreach (var group in shapes.GroupBy(s => s))
+        shapeCounts[group.Key] = group.Count();
       return shapeCounts;
     }