Changeset 8744 for branches

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

Location:

branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape

Files:

• Analysis/InformationAnalysis.cs (modified) (4 diffs)
• Analysis/InformationAnalysisCalculator.cs (modified) (3 diffs)
• Analysis/InformationAnalyzer.cs (modified) (5 diffs)
• DictionaryExtensions.cs (added)
• HeuristicLab.Analysis.FitnessLandscape.csproj (modified) (1 diff)
• ListExtensions.cs (added)

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;
     }

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

@@ -18 +18 @@
     public ValueLookupParameter<IntValue> NQuantilesParameter {
       get { return (ValueLookupParameter<IntValue>)Parameters["NQuantiles"]; }
+    }
+    public ValueLookupParameter<IntValue> ShapeSizeParameter {
+      get { return (ValueLookupParameter<IntValue>) Parameters["ShapeSize"]; }
     }
     public LookupParameter<DoubleValue> InformationStabilityParameter {
@@ -50 +53 @@
     public InformationAnalysisCalculator() {
       Parameters.Add(new LookupParameter<DataTable>("QualityTrail", "Historical quality trail of a walk over a fitness landscape."));
+
       Parameters.Add(new ValueLookupParameter<IntValue>("NQuantiles", "Number of epsilon quantiles to calculate information analysis."));
+      Parameters.Add(new ValueLookupParameter<IntValue>("ShapeSize", "The number of consecutive slopes to consider as shape.", new IntValue(2)));
+
       Parameters.Add(new LookupParameter<DoubleValue>("InformationStability"));
       Parameters.Add(new LookupParameter<IntValue>("Regularity"));
@@ -71 +77 @@
       var analysis = new InformationAnalysis(
         QualityTrailParameter.ActualValue.Rows.First().Values,
-        NQuantilesParameter.ActualValue.Value);
+        NQuantilesParameter.ActualValue.Value,
+        ShapeSizeParameter.ActualValue.Value);
       RegularityParameter.ActualValue = new IntValue(analysis.Regularity);
       DiversityParameter.ActualValue = new IntValue(analysis.Diversity);

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

@@ -53 +53 @@
       get { return (ValueLookupParameter<IntValue>)Parameters["NQuantiles"]; }
     }
+    public ValueLookupParameter<IntValue> ShapeSizeParameter {
+      get { return (ValueLookupParameter<IntValue>)Parameters["ShapeSize"]; }
+    }
     public LookupParameter<DoubleValue> InformationContentValueParameter {
       get { return (LookupParameter<DoubleValue>)Parameters["InformationContentValue"]; }
@@ -122 +125 @@
       Parameters.Add(new LookupParameter<InformationAnalysisTable>("Information", "A data table that information theoretic fitness landscape characteristics"));
       Parameters.Add(new LookupParameter<VariableCollection>("Results", "The collection of all results of this algorithm"));
+
       Parameters.Add(new ValueLookupParameter<IntValue>("NQuantiles", "The number of delta quantiles to display", new IntValue(20)));
+      Parameters.Add(new ValueLookupParameter<IntValue>("ShapeSize", "The number of slopes to consider as shapes.", new IntValue(2)));
+
       Parameters.Add(new LookupParameter<DoubleValue>("InformationContentValue", "The information content H(0) at eps = 0"));
       Parameters.Add(new LookupParameter<DoubleValue>("PartialInformationContentValue", "Partial information content M(0) at eps = 0"));
@@ -170 +176 @@
     private void AnalyseInformation() {
       int nQuantiles = NQuantilesParameter.ActualValue.Value;
+      int shapeSize = ShapeSizeParameter.ActualValue.Value;
       var qualities = QualityTrailParameter.ActualValue.Rows.First().Values.ToList();
       if (qualities.Count > nQuantiles) {
@@ -178 +185 @@
         var totalEntropy = informationTable.Rows["Total Entropy"].Values;
         var qualityDelta = informationTable.Rows["Quality Delta"].Values;
-        var analysis = new InformationAnalysis(qualities, nQuantiles);
+        var analysis = new InformationAnalysis(qualities, nQuantiles, shapeSize);
         InformationStability.Rows["Regularity"].Values.Add(analysis.Regularity);
         InformationStability.Rows["Diversity"].Values.Add(analysis.Diversity);
-        InformationStability.Rows["Relative Regularity"].Values.Add(1.0 * analysis.Regularity / qualities.Count);
-        InformationStability.Rows["Relative Diversity"].Values.Add(1.0 * analysis.Diversity / qualities.Count);
+        InformationStability.Rows["Relative Regularity"].Values.Add(1.0*analysis.Regularity/qualities.Count);
+        InformationStability.Rows["Relative Diversity"].Values.Add(1.0*analysis.Diversity/qualities.Count);
         InformationStability.Rows["Information Stability"].Values.Add(analysis.InformationStability);
         informationContent.Clear();
@@ -200 +207 @@
         RegularityValueParameter.ActualValue = new IntValue(analysis.Regularity);
         DiversityValueParameter.ActualValue = new IntValue(analysis.Diversity);
-        PeakInformationContentParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.Value);
-        PeakDensityBasinInformationParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.Value);
-        PeakInformationContentQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.QualityDelta);
-        PeakDensityBasinInformationQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.QualityDelta);
+        if (analysis.PeakInformationContent != null) {
+          PeakInformationContentParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.Value);
+          PeakInformationContentQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.QualityDelta);
+        }
+        if (analysis.PeakDensityBasinInformation != null) {
+          PeakDensityBasinInformationParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.Value);
+          PeakDensityBasinInformationQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.QualityDelta);
+        }
       }
     }

branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/HeuristicLab.Analysis.FitnessLandscape.csproj

@@ -212 +212 @@
     <Compile Include="BoxChart\BitmapItem.cs" />
     <Compile Include="ColorGradient.cs" />
+    <Compile Include="DictionaryExtensions.cs" />
     <Compile Include="DistanceCalculators\BinaryVectorDistanceCalculator.cs" />
     <Compile Include="DistanceCalculators\PermutationDistanceCalculator.cs" />
     <Compile Include="DistanceCalculators\IItemDistanceCalculator.cs" />
     <Compile Include="IListExtensions.cs" />
+    <Compile Include="ListExtensions.cs" />
     <Compile Include="NeutralSelector.cs" />
     <Compile Include="DataTables\AutoCorrelationTable.cs" />