source: branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/InformationAnalysis.cs

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;

namespace HeuristicLab.Analysis.FitnessLandscape {

  public class InformationAnalysis {

    public class Peak {
      public double QualityDelta { get; private set; }
      public double Value { get; private set; }
      public Peak(double qualityDelta, double value) {
        QualityDelta = qualityDelta;
        Value = value;
      }
    }

    public List<double> InformationContent { get; private set; }
    public List<double> SymmetricInformationContent { get; private set; }
    public List<double> PartialInformationContent { get; private set; }
    public List<double> DensityBasinInformation { get; private set; }
    public List<double> SymmetricDensityBasinInformation { get; private set; }
    public List<double> TotalEntropy { get; private set; }
    public List<double> SymmetricTotalEntropy { get; private set; }
    public List<double> QualityDelta { get; private set; }
    public double InformationStability { get; private set; }
    public double Regularity { get; private set; }
    public double Diversity { get; private set; }
    public Peak PeakInformationContent { get; private set; }
    public Peak PeakSymmetricInformationContent { get; private set; }
    public Peak PeakDensityBasinInformation { get; private set; }
    public Peak PeakSymmetricDensityBasinInformation { get; private set; }
    public Peak PeakTotalEntropy { get; private set; }
    public Peak PeakSymmetricTotalEntropy { get; private set; }

    public InformationAnalysis(IList<double> qualities, int nQuantiles = 20) {
      InformationContent = new List<double>(nQuantiles);
      SymmetricInformationContent = new List<double>(nQuantiles);
      PartialInformationContent = new List<double>(nQuantiles);
      DensityBasinInformation = new List<double>(nQuantiles);
      SymmetricDensityBasinInformation = new List<double>(nQuantiles);
      TotalEntropy = new List<double>(nQuantiles);
      SymmetricTotalEntropy = new List<double>(nQuantiles);
      QualityDelta = new List<double>(nQuantiles);
      if (qualities.Count > 1)
        PerformAnalysis(qualities, nQuantiles);
    }

    private void PerformAnalysis(IList<double> qualities, int nQuantiles) {
      var differences = Differences(qualities).ToList();
      InformationStability = differences.Select(Math.Abs).Max();
      Regularity = new HashSet<double>(differences).Count / (double)differences.Count;
      Diversity = new HashSet<double>(qualities).Count / (double)qualities.Count;
      var absDifferences = differences.Select(Math.Abs).OrderBy(d => d).ToList();
      nQuantiles = Math.Min(nQuantiles, absDifferences.Count);
      var thresholds = (nQuantiles == 0
                         ? absDifferences
                         : UniqueThresholdCalculator.DetermineThresholds(differences, nQuantiles)).ToList();
      foreach (var eps in thresholds) {
        if (QualityDelta.Count > 0 && QualityDelta.Last() == eps) {
          QualityDelta.DuplicateLast();
          InformationContent.DuplicateLast();
          DensityBasinInformation.DuplicateLast();
          TotalEntropy.DuplicateLast();
          PartialInformationContent.DuplicateLast();
        } else {
          var slopes = ToSlopes(eps, differences).ToList();
          var shapes = ToShapes(slopes).ToList();
          var symmetricShapes = shapes.Select(x => Shape.GetSymmetric(x)).ToList();

          var shapeFreqs = GetFrequencies(shapes);
          var symShapeFreqs = GetFrequencies(symmetricShapes);

          foreach (var symShape in Shape.Symmetric.Where(x => x.Sum > 0)) {
            if (symShapeFreqs.TryGetValue(symShape, out var freq)) {
              symShapeFreqs[symShape] = freq / 2;
            }
          }
          QualityDelta.Add(eps);

          InformationContent.Add(CalculateEntropy(shapeFreqs, Shape.NonUniform.ToList(), shapes.Count));
          SymmetricInformationContent.Add(CalculateEntropy(symShapeFreqs, Shape.SymmetricNonUniform.ToList(), symmetricShapes.Count));

          DensityBasinInformation.Add(CalculateEntropy(shapeFreqs, Shape.Uniform.ToList(), shapes.Count));
          SymmetricDensityBasinInformation.Add(CalculateEntropy(symShapeFreqs, Shape.SymmetricUniform.ToList(), symmetricShapes.Count));

          TotalEntropy.Add(CalculateEntropy(shapeFreqs, Shape.All.ToList(), shapes.Count));
          SymmetricTotalEntropy.Add(CalculateEntropy(symShapeFreqs, Shape.Symmetric.ToList(), symmetricShapes.Count));

          PartialInformationContent.Add(CalculatePartialInformationContent(eps, differences));
        }
      }
      PeakInformationContent = GetPeak(QualityDelta, InformationContent);
      PeakSymmetricInformationContent = GetPeak(QualityDelta, SymmetricInformationContent);
      PeakDensityBasinInformation = GetPeak(QualityDelta, DensityBasinInformation);
      PeakSymmetricDensityBasinInformation = GetPeak(QualityDelta, SymmetricDensityBasinInformation);
      PeakTotalEntropy = GetPeak(QualityDelta, TotalEntropy);
      PeakSymmetricTotalEntropy = GetPeak(QualityDelta, SymmetricTotalEntropy);
    }

    public IEnumerable<Tuple<string, object>> GetFeatures() {
      yield return Tuple.Create("InformationContent", (object)InformationContent[0]);
      yield return Tuple.Create("DensityBasinInformation", (object)DensityBasinInformation[0]);
      yield return Tuple.Create("PartialInformationContent", (object)PartialInformationContent[0]);
      yield return Tuple.Create("TotalEntropy", (object)TotalEntropy[0]);
      yield return Tuple.Create("InformationStability", (object)InformationStability);
      yield return Tuple.Create("Regularity", (object)Regularity);
      yield return Tuple.Create("Diversity", (object)Diversity);
      yield return Tuple.Create("SymmetricInformationContent", (object)SymmetricInformationContent[0]);
      yield return Tuple.Create("SymmetricDensityBasinInformation", (object)SymmetricDensityBasinInformation[0]);
      yield return Tuple.Create("SymmetricTotalEntropy", (object)SymmetricTotalEntropy[0]);
      yield return Tuple.Create("PeakInformationContent", (object)PeakInformationContent.Value);
      yield return Tuple.Create("PeakDensityBasinInformation", (object)PeakDensityBasinInformation.Value);
      yield return Tuple.Create("PeakTotalEntropy", (object)PeakTotalEntropy.Value);
      yield return Tuple.Create("PeakSymmetricInformationContent", (object)PeakSymmetricInformationContent.Value);
      yield return Tuple.Create("PeakSymmetricDensityBasinInformation", (object)PeakSymmetricDensityBasinInformation.Value);
      yield return Tuple.Create("PeakSymmetricTotalEntropy", (object)PeakSymmetricTotalEntropy.Value);
    }

    public static Peak GetPeak(IEnumerable<double> indexes, IEnumerable<double> values) {
      var max = indexes.Zip(values, (i, v) => new { i, v }).OrderByDescending(p => p.v).First();
      return new Peak(max.i, max.v);
    }

    public enum Slope {
      Up = 1,
      Flat = 0,
      Down = -1
    }

    public class Shape {
      private static readonly Shape[] s = new Shape[] {
        new Shape() { First = Slope.Down, Second = Slope.Down }, // 0
        new Shape() { First = Slope.Down, Second = Slope.Flat }, // 1
        new Shape() { First = Slope.Down, Second = Slope.Up   }, // 2
        new Shape() { First = Slope.Flat, Second = Slope.Down }, // 3
        new Shape() { First = Slope.Flat, Second = Slope.Flat }, // 4
        new Shape() { First = Slope.Flat, Second = Slope.Up   }, // 5
        new Shape() { First = Slope.Up,   Second = Slope.Down }, // 6
        new Shape() { First = Slope.Up,   Second = Slope.Flat }, // 7
        new Shape() { First = Slope.Up,   Second = Slope.Up   }, // 8
      };
      public static IEnumerable<Shape> All { get { return s; } }
      public static IEnumerable<Shape> Uniform { get { return All.Where(x => x.First == x.Second); } }
      public static IEnumerable<Shape> NonUniform { get { return All.Where(x => x.First != x.Second); } }
      public static IEnumerable<Shape> Symmetric { get { return All.Where(x => x.Sum >= 0); } }
      public static IEnumerable<Shape> SymmetricUniform { get { return Uniform.Where(x => x.First != Slope.Down); } }
      public static IEnumerable<Shape> SymmetricNonUniform { get { return NonUniform.Where(x => x.Sum >= 0); } }

      public Slope First { get; private set; }
      public Slope Second { get; private set; }

      internal int Sum { get { return (int)First + (int)Second; } }

      public IEnumerable<Slope> Slopes {
        get {
          yield return First;
          yield return Second;
        }
      }

      private Shape() {

      }

      public static Shape Get(Slope first, Slope second) {
        var a = 1 + (int)first; var b = 1 + (int)second;
        return s[a * 3 + b];
      }

      public static Shape GetSymmetric(Shape shape) {
        if (shape.Sum >= 0) return shape;
        if (shape.Sum == -2) return s[8]; // both are Slope.Down
        if (shape.First == Slope.Down) return s[5];
        return s[7]; // shape.Second == Slope.Down
      }

      public override string ToString() {
        return string.Join("", Slopes.Select(s => (s == Slope.Down ? "\\" : (s == Slope.Up ? "/" : "-"))));
      }
    }

    

    private static IEnumerable<Slope> ToSlopes(double eps, IEnumerable<double> differences) {
      return differences.Select(d => (d > eps ? Slope.Up : (d < -eps ? Slope.Down : Slope.Flat)));
    }

    private static IEnumerable<Shape> ToShapes(IEnumerable<Slope> slopes) {
      var iter = slopes.GetEnumerator();
      if (!iter.MoveNext()) yield break;
      var prev = iter.Current;
      while (iter.MoveNext()) {
        var cur = iter.Current;
        yield return Shape.Get(prev, cur);
        prev = cur;
      }
    }

    private static double CalculateEntropy(Dictionary<Shape, int> shapeCounts, ICollection<Shape> shapeTypes, int totalShapes) {
      return shapeTypes.Where(x => shapeCounts.ContainsKey(x))
        .Aggregate(0.0, (current, s) => current - Entropy(shapeCounts[s], totalShapes, shapeTypes.Count));
    }

    private static double CalculatePartialInformationContent(double eps, ICollection<double> differences) {
      var iter = differences.GetEnumerator();
      if (!iter.MoveNext()) return 0;

      var slope = iter.Current < -eps ? -1 : (iter.Current > eps ? 1 : 0);
      var nPeaks = Math.Abs(slope);
      var count = 1;
      while (iter.MoveNext()) {
        var d = iter.Current;
        if (d > eps) {
          if (slope < 0) nPeaks++;
          slope = +1;
        } else if (d < -eps) {
          if (slope > 0) nPeaks++;
          slope = -1;
        }
        count++;
      }
      return nPeaks / (double)count;
    }

    private static Dictionary<Shape, int> GetFrequencies(IEnumerable<Shape> shapes) {
      return shapes.GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count());
    }

    private static double Entropy(int count, int total, int nCases) {
      if (count == 0) return 0;
      var freq = 1.0 * count / total;
      return freq * Math.Log(freq, nCases);
    }

    private static IEnumerable<double> Differences(IEnumerable<double> values) {
      return values.Delta((x, y) => y - x);
    }

  }
}