Changeset 8744


Ignore:
Timestamp:
10/05/12 12:36:25 (10 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:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/InformationAnalysis.cs

    r8725 r8744  
    2929    public Peak PeakTotalEntropy { get; private set; }
    3030
    31     public InformationAnalysis(IList<double> qualities, int nQuantiles) {
     31    public InformationAnalysis(IList<double> qualities, int nQuantiles, int shapeSize) {
    3232      InformationContent = new List<double>();
    3333      PartialInformationContent = new List<double>();
     
    3535      TotalEntropy = new List<double>();
    3636      QualityDelta = new List<double>();
    37       PerformAnalysis(qualities, nQuantiles);
    38     }
    39 
    40     private void PerformAnalysis(IList<double> qualities, int nQuantiles) {
     37      if (shapeSize < 1)
     38        throw new ArgumentException("Shape size must be at least 1 (better 2)");
     39      if (qualities.Count > 1)
     40        PerformAnalysis(qualities, nQuantiles, shapeSize);
     41    }
     42
     43    private void PerformAnalysis(IList<double> qualities, int nQuantiles, int shapeSize) {
    4144      var differences = Differences(qualities).ToList();
    42       InformationStability = differences.Select(d => Math.Abs(d)).Max();
     45      InformationStability = differences.Select(Math.Abs).Max();
    4346      Regularity = new HashSet<double>(differences).Count;
    4447      Diversity = new HashSet<double>(qualities).Count;
    45       //var thresholds = UniqueThresholdCalculator.DetermineThresholds(differences, nQuantiles).ToList();
    46       var thresholds = differences.Select(d => Math.Abs(d)).OrderBy(d => d);
     48      var thresholds = (nQuantiles == 0
     49                         ? differences.Select(Math.Abs).OrderBy(d => d)
     50                         : UniqueThresholdCalculator.DetermineThresholds(differences, nQuantiles)).ToList();
    4751      foreach (var eps in thresholds) {
    48         var shapes = Shapes(eps, differences).ToList();
    49         int[] shapeCounts = CountShapes(shapes);
    50         QualityDelta.Add(eps);
    51         InformationContent.Add(CalculateInformationContent(shapeCounts, shapes.Count));
    52         PartialInformationContent.Add(CalculatePartialInformationContent(eps, differences));
    53         DensityBasinInformation.Add(CalculateDensityBasinInformation(shapeCounts, shapes.Count));
    54         TotalEntropy.Add(CalculateTotalEntropy(shapeCounts, shapes.Count));
     52        if (QualityDelta.Count > 0 && QualityDelta.Last() == eps) {
     53          QualityDelta.DuplicateLast();
     54          InformationContent.DuplicateLast();
     55          DensityBasinInformation.DuplicateLast();
     56          TotalEntropy.DuplicateLast();
     57          PartialInformationContent.DuplicateLast();
     58        } else {
     59          var slopes = Slopes(eps, differences).ToList();
     60          var shapes = Shapes(shapeSize, slopes).ToList();
     61          var shapeCounts = CountShapes(shapes);
     62          QualityDelta.Add(eps);
     63          InformationContent.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.NonUni), shapeCounts, shapes.Count));
     64          DensityBasinInformation.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.Uni), shapeCounts, shapes.Count));
     65          TotalEntropy.Add(CalculateEntropy(Shape.GetAll(shapeSize, Shape.Form.Any), shapeCounts, shapes.Count));
     66          PartialInformationContent.Add(CalculatePartialInformationContent(eps, differences));
     67        }
    5568      }
    5669      PeakInformationContent = GetPeak(QualityDelta, InformationContent);
     
    6578    }
    6679
    67     public enum Shape {
    68       DecDec = -4,
    69       EquDec = -3,
    70       IncDec = -2,
    71       DecEqu = -1,
    72       EquEqu = 0,
    73       IncEqu = 1,
    74       DecInc = 2,
    75       EquInc = 3,
    76       IncInc = 4
    77     }
    78 
    79     private static IEnumerable<Shape> Shapes(double eps, IEnumerable<double> differences) {
    80       return Utils.Delta(differences, (x, y) =>
    81         (Shape)
    82           ((x > eps ? 1 : (x < -eps ? -1 : 0)) +
    83            (y > eps ? 3 : (y < -eps ? -3 : 0))));
    84     }
    85 
    86     private static double CalculateInformationContent(int[] shapeCounts, int totalNShapes) {
    87       return
    88         -Entropy(shapeCounts[(int)Shape.EquDec + 4], totalNShapes, 6)
    89         - Entropy(shapeCounts[(int)Shape.IncDec + 4], totalNShapes, 6)
    90         - Entropy(shapeCounts[(int)Shape.DecEqu + 4], totalNShapes, 6)
    91         - Entropy(shapeCounts[(int)Shape.IncEqu + 4], totalNShapes, 6)
    92         - Entropy(shapeCounts[(int)Shape.DecInc + 4], totalNShapes, 6)
    93         - Entropy(shapeCounts[(int)Shape.EquInc + 4], totalNShapes, 6);
    94     }
    95 
    96     private static double CalculateDensityBasinInformation(int[] shapeCounts, int totalNShapes) {
    97       return
    98         -Entropy(shapeCounts[(int)Shape.DecDec + 4], totalNShapes, 3)
    99         - Entropy(shapeCounts[(int)Shape.EquEqu + 4], totalNShapes, 3)
    100         - Entropy(shapeCounts[(int)Shape.IncInc + 4], totalNShapes, 3);
    101     }
    102 
    103     private static double CalculateTotalEntropy(int[] shapeCounts, int totalNShapes) {
    104       return shapeCounts.Aggregate(0.0, (current, t) => current - Entropy(t, totalNShapes, 9));
     80    public enum Slope {
     81      Up = 1,
     82      Flat = 0,
     83      Down = -1
     84    }
     85
     86    public class Shape : IEnumerable<Slope>, IComparable<Shape> {
     87
     88      #region types, fields and properties
     89      public enum Form {Uni, NonUni, Any}
     90
     91      private readonly Slope[] slopes;
     92
     93      private static readonly Dictionary<Tuple<Form, int>, IList<Shape>> SHAPES =
     94        new Dictionary<Tuple<Form,int>,IList<Shape>>();
     95      #endregion
     96
     97      public Shape(IEnumerable<Slope> slopes) {
     98        this.slopes = slopes.ToArray();
     99      }
     100
     101      #region static methods
     102
     103      public static Shape Get(params Slope[] slopes) {
     104        return new Shape(slopes);
     105      }
     106
     107      public static IList<Shape> GetAll(int size, Form type) {
     108        var key = Tuple.Create(type, size);
     109        IList<Shape> allShapes;
     110        if (!SHAPES.TryGetValue(key, out allShapes)) {
     111          allShapes = CreateAll(size, type).ToList();
     112          SHAPES[key] = allShapes;
     113        }
     114        return allShapes;
     115      }
     116
     117      private static IEnumerable<Shape> CreateAll(int size, Form type) {
     118        if (size == 0) {
     119          yield return Get();
     120        } else {
     121          foreach (var s in CreateAll(size - 1, type)) {
     122            foreach (var s2 in s.ExtendAll(type))
     123              yield return s2;
     124          }
     125        }
     126      }
     127      #endregion
     128
     129      private Shape Extend(Slope s) {
     130        return new Shape(slopes.Concat(new[] {s}));
     131      }
     132
     133      private IEnumerable<Shape> ExtendAll(Form t) {
     134        if (Length == 0 || t == Form.Any) {
     135          yield return Extend(Slope.Up);
     136          yield return Extend(Slope.Flat);
     137          yield return Extend(Slope.Down);
     138        } else if (t == Form.Uni) {
     139          yield return Extend(slopes[0]);
     140        } else if (t == Form.NonUni) {
     141          if (slopes.Last() != Slope.Up) yield return Extend(Slope.Up);
     142          if (slopes.Last() != Slope.Flat) yield return Extend(Slope.Flat);
     143          if (slopes.Last() != Slope.Down) yield return Extend(Slope.Down);
     144        }
     145      }
     146
     147      public int Length {
     148        get { return slopes.Length; }
     149      }
     150
     151      public Slope this[int i] {
     152        get { return slopes[i]; }
     153      }
     154
     155      #region IEnumerable Members
     156      public IEnumerator<Slope> GetEnumerator() {
     157        return (IEnumerator<Slope>) slopes.GetEnumerator();
     158      }
     159      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
     160        return GetEnumerator();
     161      }
     162      #endregion
     163
     164      #region IComparable Members
     165
     166      public int CompareTo(Shape other) {
     167        if (other.Length < Length)
     168          return -1;
     169        if (other.Length > Length)
     170          return 1;
     171        for (var i = 0; i<Length; i++) {
     172          var d = slopes[i].CompareTo(other.slopes[i]);
     173          if (d != 0)
     174            return d;
     175        }
     176        return 0;
     177      }
     178      public override bool Equals(object obj) {
     179        var s = obj as Shape;
     180        if (s == null) return false;
     181        return CompareTo(s) == 0;
     182      }
     183      public override int GetHashCode() {
     184        return slopes.Aggregate(0, (a, s) => a*3 + ((int) s + 1)).GetHashCode();
     185      }
     186
     187      #endregion
     188
     189      private string asString;
     190      public override string ToString() {
     191        return asString ?? (asString = string.Join("", slopes.Select(s => (s == Slope.Down ? "v" : (s == Slope.Up ? "^" : "-")))));
     192      }
     193    }
     194
     195    private static IEnumerable<Slope> Slopes(double eps, IEnumerable<double> differences) {
     196      return differences.Select(d => (d > eps ? Slope.Up : (d < -eps ? Slope.Down : 0)));
     197    } 
     198
     199    private static IEnumerable<Shape> Shapes(int size, IEnumerable<Slope> slopes) {
     200      var q = new Queue<Slope>();
     201      foreach (var s in slopes) {
     202        q.Enqueue(s);
     203        if (q.Count < size) continue;
     204        yield return new Shape(q);
     205        q.Dequeue();
     206      }
     207    }
     208
     209    private static double CalculateEntropy(IList<Shape> shapes, Dictionary<Shape, int> shapeCounts, int totalNShapes) {
     210      return shapes.Aggregate(0.0, (current, s) => current - Entropy(shapeCounts.GetValueOrDefault(s, 0), totalNShapes, shapes.Count));
    105211    }
    106212
     
    120226    }
    121227
    122     private static int[] CountShapes(IEnumerable<Shape> shapes) {
    123       int[] shapeCounts = new int[9];
    124       foreach (var s in shapes) {
    125         shapeCounts[(int)s + 4]++;
    126       }
     228    private static Dictionary<Shape, int> CountShapes(IEnumerable<Shape> shapes) {
     229      var shapeCounts = new Dictionary<Shape, int>();
     230      foreach (var group in shapes.GroupBy(s => s))
     231        shapeCounts[group.Key] = group.Count();
    127232      return shapeCounts;
    128233    }
  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/InformationAnalysisCalculator.cs

    r8725 r8744  
    1818    public ValueLookupParameter<IntValue> NQuantilesParameter {
    1919      get { return (ValueLookupParameter<IntValue>)Parameters["NQuantiles"]; }
     20    }
     21    public ValueLookupParameter<IntValue> ShapeSizeParameter {
     22      get { return (ValueLookupParameter<IntValue>) Parameters["ShapeSize"]; }
    2023    }
    2124    public LookupParameter<DoubleValue> InformationStabilityParameter {
     
    5053    public InformationAnalysisCalculator() {
    5154      Parameters.Add(new LookupParameter<DataTable>("QualityTrail", "Historical quality trail of a walk over a fitness landscape."));
     55
    5256      Parameters.Add(new ValueLookupParameter<IntValue>("NQuantiles", "Number of epsilon quantiles to calculate information analysis."));
     57      Parameters.Add(new ValueLookupParameter<IntValue>("ShapeSize", "The number of consecutive slopes to consider as shape.", new IntValue(2)));
     58
    5359      Parameters.Add(new LookupParameter<DoubleValue>("InformationStability"));
    5460      Parameters.Add(new LookupParameter<IntValue>("Regularity"));
     
    7177      var analysis = new InformationAnalysis(
    7278        QualityTrailParameter.ActualValue.Rows.First().Values,
    73         NQuantilesParameter.ActualValue.Value);
     79        NQuantilesParameter.ActualValue.Value,
     80        ShapeSizeParameter.ActualValue.Value);
    7481      RegularityParameter.ActualValue = new IntValue(analysis.Regularity);
    7582      DiversityParameter.ActualValue = new IntValue(analysis.Diversity);
  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/InformationAnalyzer.cs

    r8725 r8744  
    5353      get { return (ValueLookupParameter<IntValue>)Parameters["NQuantiles"]; }
    5454    }
     55    public ValueLookupParameter<IntValue> ShapeSizeParameter {
     56      get { return (ValueLookupParameter<IntValue>)Parameters["ShapeSize"]; }
     57    }
    5558    public LookupParameter<DoubleValue> InformationContentValueParameter {
    5659      get { return (LookupParameter<DoubleValue>)Parameters["InformationContentValue"]; }
     
    122125      Parameters.Add(new LookupParameter<InformationAnalysisTable>("Information", "A data table that information theoretic fitness landscape characteristics"));
    123126      Parameters.Add(new LookupParameter<VariableCollection>("Results", "The collection of all results of this algorithm"));
     127
    124128      Parameters.Add(new ValueLookupParameter<IntValue>("NQuantiles", "The number of delta quantiles to display", new IntValue(20)));
     129      Parameters.Add(new ValueLookupParameter<IntValue>("ShapeSize", "The number of slopes to consider as shapes.", new IntValue(2)));
     130
    125131      Parameters.Add(new LookupParameter<DoubleValue>("InformationContentValue", "The information content H(0) at eps = 0"));
    126132      Parameters.Add(new LookupParameter<DoubleValue>("PartialInformationContentValue", "Partial information content M(0) at eps = 0"));
     
    170176    private void AnalyseInformation() {
    171177      int nQuantiles = NQuantilesParameter.ActualValue.Value;
     178      int shapeSize = ShapeSizeParameter.ActualValue.Value;
    172179      var qualities = QualityTrailParameter.ActualValue.Rows.First().Values.ToList();
    173180      if (qualities.Count > nQuantiles) {
     
    178185        var totalEntropy = informationTable.Rows["Total Entropy"].Values;
    179186        var qualityDelta = informationTable.Rows["Quality Delta"].Values;
    180         var analysis = new InformationAnalysis(qualities, nQuantiles);
     187        var analysis = new InformationAnalysis(qualities, nQuantiles, shapeSize);
    181188        InformationStability.Rows["Regularity"].Values.Add(analysis.Regularity);
    182189        InformationStability.Rows["Diversity"].Values.Add(analysis.Diversity);
    183         InformationStability.Rows["Relative Regularity"].Values.Add(1.0 * analysis.Regularity / qualities.Count);
    184         InformationStability.Rows["Relative Diversity"].Values.Add(1.0 * analysis.Diversity / qualities.Count);
     190        InformationStability.Rows["Relative Regularity"].Values.Add(1.0*analysis.Regularity/qualities.Count);
     191        InformationStability.Rows["Relative Diversity"].Values.Add(1.0*analysis.Diversity/qualities.Count);
    185192        InformationStability.Rows["Information Stability"].Values.Add(analysis.InformationStability);
    186193        informationContent.Clear();
     
    200207        RegularityValueParameter.ActualValue = new IntValue(analysis.Regularity);
    201208        DiversityValueParameter.ActualValue = new IntValue(analysis.Diversity);
    202         PeakInformationContentParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.Value);
    203         PeakDensityBasinInformationParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.Value);
    204         PeakInformationContentQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.QualityDelta);
    205         PeakDensityBasinInformationQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.QualityDelta);
     209        if (analysis.PeakInformationContent != null) {
     210          PeakInformationContentParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.Value);
     211          PeakInformationContentQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakInformationContent.QualityDelta);
     212        }
     213        if (analysis.PeakDensityBasinInformation != null) {
     214          PeakDensityBasinInformationParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.Value);
     215          PeakDensityBasinInformationQualityDeltaParameter.ActualValue = new DoubleValue(analysis.PeakDensityBasinInformation.QualityDelta);
     216        }
    206217      }
    207218    }
  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/HeuristicLab.Analysis.FitnessLandscape.csproj

    r8627 r8744  
    212212    <Compile Include="BoxChart\BitmapItem.cs" />
    213213    <Compile Include="ColorGradient.cs" />
     214    <Compile Include="DictionaryExtensions.cs" />
    214215    <Compile Include="DistanceCalculators\BinaryVectorDistanceCalculator.cs" />
    215216    <Compile Include="DistanceCalculators\PermutationDistanceCalculator.cs" />
    216217    <Compile Include="DistanceCalculators\IItemDistanceCalculator.cs" />
    217218    <Compile Include="IListExtensions.cs" />
     219    <Compile Include="ListExtensions.cs" />
    218220    <Compile Include="NeutralSelector.cs" />
    219221    <Compile Include="DataTables\AutoCorrelationTable.cs" />
Note: See TracChangeset for help on using the changeset viewer.