source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFrequentPatternsAnalyzer.cs @ 9082

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 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;
using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.DataAnalysis.Symbolic;

namespace HeuristicLab.EvolutionaryTracking {
  /// <summary>
  /// An analyzer that looks at individual lineages in the genealogy graph
  /// </summary>
  [Item("SymbolicExpressionTreeFrequentPatternsAnalyzer", "An operator that tries to find frequent tree fragments in the population")]
  [StorableClass]
  public sealed class SymbolicExpressionTreeFrequentPatternsAnalyzer : SingleSuccessorOperator, IAnalyzer {
    #region Parameter names
    private const string UpdateIntervalParameterName = "UpdateInterval";
    private const string UpdateCounterParameterName = "UpdateCounter";
    private const string ResultsParameterName = "Results";
    private const string GenerationsParameterName = "Generations";
    private const string MaximumGenerationsParameterName = "MaximumGenerations";
    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    private const string RandomParameterName = "Random";
    private const string MaximumFragmentDepthParameterName = "MaximumFragmentDepth";
    private const string MaximumFragmentLengthParameterName = "MaximumFragmentLength";
    private const string NumberOfFragmentsToGenerateParameterName = "NumberOfFragmentsToGenerate";
    private const string FrequentFragmentOccurrenceThresholdParameterName = "FrequentFragmentOccurrenceThreshold";
    private const string PopulationGraphParameterName = "PopulationGraph";
    private const string CommonFragmentsParameterName = "CommonFragments";
    private const string EnforceGrammarArityParameterName = "EnforceGrammarArity";
    #endregion

    #region Parameter properties
    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters[RandomParameterName]; }
    }
    public ValueParameter<IntValue> UpdateIntervalParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
    }
    public ValueParameter<IntValue> UpdateCounterParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
    }
    public LookupParameter<ResultCollection> ResultsParameter {
      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
    }
    public LookupParameter<IntValue> GenerationsParameter {
      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
    }
    public LookupParameter<IntValue> MaximumGenerationsParameter {
      get { return (LookupParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }
    }
    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    }
    public ValueParameter<IntValue> MaximumFragmentDepthParameter {
      get { return (ValueParameter<IntValue>)Parameters[MaximumFragmentDepthParameterName]; }
    }
    public ValueParameter<IntValue> MaximumFragmentLengthParameter {
      get { return (ValueParameter<IntValue>)Parameters[MaximumFragmentLengthParameterName]; }
    }
    public ValueParameter<IntValue> NumberOfFragmentsToGenerateParameter {
      get { return (ValueParameter<IntValue>)Parameters[NumberOfFragmentsToGenerateParameterName]; }
    }
    public ValueParameter<DoubleValue> FrequentFragmentOccurrenceThresholdParameter {
      get { return (ValueParameter<DoubleValue>)Parameters[FrequentFragmentOccurrenceThresholdParameterName]; }
    }
    public ValueParameter<BoolValue> EnforceGrammarArityParameter {
      get { return (ValueParameter<BoolValue>)Parameters[EnforceGrammarArityParameterName]; }
    }
    #endregion

    #region Properties
    public bool EnabledByDefault {
      get { return true; }
    }
    public IntValue UpdateInterval {
      get { return UpdateIntervalParameter.Value; }
    }
    public IntValue UpdateCounter {
      get { return UpdateCounterParameter.Value; }
    }
    public IntValue Generations {
      get { return GenerationsParameter.ActualValue; }
    }
    public IntValue MaximumGenerations {
      get { return MaximumGenerationsParameter.ActualValue; }
    }
    public ResultCollection Results {
      get { return ResultsParameter.ActualValue; }
    }
    public IntValue MaximumFragmentDepth {
      get { return MaximumFragmentDepthParameter.Value; }
    }
    public IntValue MaximumFragmentLength {
      get { return MaximumFragmentLengthParameter.Value; }
    }
    public IntValue NumberOfFragmentsToGenerate {
      get { return NumberOfFragmentsToGenerateParameter.Value; }
    }
    public DoubleValue FrequentFragmentOccurrenceThreshold {
      get { return FrequentFragmentOccurrenceThresholdParameter.Value; }
    }
    public BoolValue EnforceGrammarArity {
      get { return EnforceGrammarArityParameter.Value; }
    }
    #endregion

    [StorableConstructor]
    private SymbolicExpressionTreeFrequentPatternsAnalyzer(bool deserializing) : base(deserializing) { }
    private SymbolicExpressionTreeFrequentPatternsAnalyzer(SymbolicExpressionTreeFrequentPatternsAnalyzer original, Cloner cloner) : base(original, cloner) { }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new SymbolicExpressionTreeFrequentPatternsAnalyzer(this, cloner);
    }
    public SymbolicExpressionTreeFrequentPatternsAnalyzer() {
      #region Add parameters
      Parameters.Add(new LookupParameter<IRandom>(RandomParameterName, "The random number generator to use."));
      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far"));
      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumGenerations", "The maximum number of generations which should be processed."));
      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze."));
      Parameters.Add(new ValueParameter<IntValue>(MaximumFragmentDepthParameterName, "The maximum allowed depth for generated fragments.", new IntValue(4)));
      Parameters.Add(new ValueParameter<IntValue>(MaximumFragmentLengthParameterName, "The maximum allowed length for generated fragments.", new IntValue(15)));
      Parameters.Add(new ValueParameter<IntValue>(NumberOfFragmentsToGenerateParameterName, "The number of fragments to generate.", new IntValue(1000)));
      Parameters.Add(new ValueParameter<DoubleValue>(FrequentFragmentOccurrenceThresholdParameterName, "Occurrence used to discriminate frequent fragments.", new DoubleValue(0.3)));
      Parameters.Add(new ValueParameter<BoolValue>(EnforceGrammarArityParameterName, "Whether to use minimum arity as defined by the grammar", new BoolValue(true)));
      #endregion
      UpdateCounterParameter.Hidden = true;
      UpdateIntervalParameter.Hidden = true;
      MaximumFragmentDepthParameter.Hidden = false;
      MaximumFragmentLengthParameter.Hidden = false;

      //this.Successor = new SymbolicExpressionTreeGenealogyGraphBuilder();
    }

    #region AfterDeserialization
    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      if (!Parameters.ContainsKey(MaximumFragmentDepthParameterName)) {
        Parameters.Add(new ValueParameter<IntValue>(MaximumFragmentDepthParameterName, "The maximum allowed depth for generated fragments.", new IntValue(4)));
      }
      if (!Parameters.ContainsKey(MaximumFragmentLengthParameterName)) {
        Parameters.Add(new ValueParameter<IntValue>(MaximumFragmentLengthParameterName, "The maximum allowed length for generated fragments.", new IntValue(15)));
      }
      if (!Parameters.ContainsKey(NumberOfFragmentsToGenerateParameterName)) {
        Parameters.Add(new ValueParameter<IntValue>(NumberOfFragmentsToGenerateParameterName, "The number of fragments to generate.", new IntValue(1000)));
      }
      if (!Parameters.ContainsKey(FrequentFragmentOccurrenceThresholdParameterName)) {
        Parameters.Add(new ValueParameter<DoubleValue>(FrequentFragmentOccurrenceThresholdParameterName, "Occurrence used to discriminate frequent fragments.", new DoubleValue(0.3)));
      }
      if (!Parameters.ContainsKey(EnforceGrammarArityParameterName)) {
        Parameters.Add(new ValueParameter<BoolValue>(EnforceGrammarArityParameterName, "Whether to use minimum arity as defined by the grammar", new BoolValue(true)));
      }
    }
    #endregion

    #region IStatefulItem members
    public override void InitializeState() {
      base.InitializeState();
      UpdateCounter.Value = 0;
    }

    public override void ClearState() {
      base.ClearState();
      UpdateCounter.Value = 0;
    }
    #endregion

    public override IOperation Apply() {
      UpdateCounter.Value++;
      if (UpdateCounter.Value == UpdateInterval.Value) {
        if (!Results.ContainsKey("SymbolGraph")) return base.Apply();

        UpdateCounter.Value = 0;

        var trees = SymbolicExpressionTreeParameter.ActualValue.ToList();
        var grammar = trees[0].Root.Grammar;

        // bring trees to a canonical form to eliminate permuted fragments
        var canonicalSorter = new SymbolicExpressionTreeCanonicalSorter();
        foreach (var t in trees)
          canonicalSorter.SortSubtrees(t);

        var graph = Results["SymbolGraph"].Value as SymbolGraph;

        var similarityComparer = new SymbolicExpressionTreeNodeSimilarityComparer { MatchVariableNames = true };
        var fragmentSimilarityComparer = new SymbolicExpressionTreeFragmentSimilarityComparer { SimilarityComparer = similarityComparer };
        // generate fragments out of the probability graph and match them against the population
        var fragments = GenerateFragments(graph, grammar, NumberOfFragmentsToGenerate.Value, MaximumFragmentDepth.Value, MaximumFragmentLength.Value).ToList();
        // subtree-sort fragments to bring them to a canonical form
        // var canonicalSorter = new SymbolicExpressionTreeCanonicalSorter();
        foreach (var fragment in fragments)
          canonicalSorter.SortSubtrees(fragment.Root);

        if (!Results.ContainsKey(CommonFragmentsParameterName)) {
          Results.Add(new Result(CommonFragmentsParameterName, new ItemDictionary<IFragment, DoubleValue>()));
        }

        var mostCommonFragmentsResult = Results[CommonFragmentsParameterName].Value as ItemDictionary<IFragment, DoubleValue>; // should never be null
        var mostCommonFragments = mostCommonFragmentsResult.Select(x => x.Key).ToList();
        mostCommonFragments.AddRange(fragments);
        mostCommonFragmentsResult.Clear();

        mostCommonFragments = mostCommonFragments.Distinct(fragmentSimilarityComparer).ToList();

        foreach (var fragment in mostCommonFragments) {
          var frequency = trees.Count(x => x.Root.ContainsFragment(fragment, similarityComparer)) / (double)trees.Count;
          if (frequency > 0) mostCommonFragmentsResult.Add(fragment, new DoubleValue(frequency));
        }

        // update fragment frequencies DataTable
        if (!Results.ContainsKey("FrequentFragments")) {
          var dt = new DataTable("Frequent Fragments");
          Results.Add(new Result("FrequentFragments", dt));
        }

        var fragmentFrequenciesTable = Results["FrequentFragments"].Value as DataTable; // should never be null
        foreach (var fragment in mostCommonFragmentsResult) {
          var prefixString = fragment.Key.Root.ToPrefixString();
          if (!fragmentFrequenciesTable.Rows.ContainsKey(prefixString)) {
            if (fragment.Value.Value > FrequentFragmentOccurrenceThreshold.Value) {
              fragmentFrequenciesTable.Rows.Add(new DataRow(prefixString) { VisualProperties = { StartIndexZero = true } });
              var row = fragmentFrequenciesTable.Rows[prefixString];
              if (!Results.ContainsKey(PopulationGraphParameterName)) {
                row.Values.AddRange(Enumerable.Repeat(0.0, Generations.Value));
              } else {
                var populationGraph = Results[PopulationGraphParameterName].Value as SymbolicExpressionTreeGenealogyGraph;
                var layers = populationGraph.Nodes.Where(n => n.Rank % 1 == 0).GroupBy(n => n.Rank).OrderBy(g => g.Key);
                var f = fragment;
                row.Values.AddRange(from g in layers
                                    select g.Count(n => n.SymbolicExpressionTree.Root.ContainsFragment(f.Key, similarityComparer)) / (double)g.Count());
              }
              fragmentFrequenciesTable.Rows[prefixString].Values.Add(fragment.Value.Value);
            }
          } else {
            fragmentFrequenciesTable.Rows[prefixString].Values.Add(fragment.Value.Value);
          }
        }
        foreach (var row in fragmentFrequenciesTable.Rows.Where(row => row.Values.Count == Generations.Value))
          row.Values.Add(0.0);

        #region Write fragment information to file

        //        using (var streamWriter = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.UserProfile), "CommonFragments.txt"))) {
        //          streamWriter.WriteLine("Median edge weight: " + medianWeight);
        //          streamWriter.WriteLine("Average edge weight: " + averageWeight);
        //          streamWriter.WriteLine("Symbol frequencies: ");
        //          double sum = graph.Nodes.Sum(node => node.Weight);
        //          foreach (var symbolNode in graph.Nodes.OrderBy(node => node.Weight)) {
        //            streamWriter.WriteLine("{0}\t{1}", symbolNode.Label, String.Format("{0:0.00}", symbolNode.Weight / sum));
        //          }
        //          streamWriter.WriteLine();
        //          streamWriter.WriteLine("Fragment root symbol frequencies:");
        //          foreach (var group in fragments.GroupBy(x => x.Root.Symbol.Name)) {
        //            streamWriter.WriteLine("{0}\t{1}", group.Key, String.Format("{0:0.00}", (double)group.Count() / NumberOfFragmentsToGenerate.Value));
        //          }
        //          streamWriter.WriteLine();
        //          foreach (var fragment in mostCommonFragments) {
        //            streamWriter.WriteLine(fragment.Key.ToPrefixString());
        //            streamWriter.WriteLine("Frequency in last generation: {0}, Contained in best individual: {1}",
        //              fragment.Value, trees[0].ContainsFragment(fragment.Key, SimilarityLevel.High) ? "YES" : "NO");
        //            SymbolicExpressionTreeMatching.RenderNode(streamWriter, fragment.Key, string.Empty);
        //            if (Results.ContainsKey(PopulationGraphParameterName)) {
        //              var populationGraph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphParameterName].Value;
        //              streamWriter.Write("Frequencies per generation: ");
        //              var groups = populationGraph.Nodes.GroupBy(n => n.Rank).OrderBy(g => g.Key);
        //              var frequencies = (from g in groups.Where(g => g.Key == (int)g.Key)
        //                                 let freq = g.Count(n => n.SymbolicExpressionTree.ContainsFragment(fragment.Key, SimilarityLevel.High))
        //                                 select freq);
        //              foreach (var freq in frequencies)
        //                streamWriter.Write(freq / count + " ");
        //              streamWriter.WriteLine();
        //            } else {
        //              streamWriter.WriteLine("Frequecy in current population: {0}", fragment.Value);
        //            }
        //            streamWriter.WriteLine("\n");
        //          }
        //          streamWriter.WriteLine("Average fragment length: {0}", avgFragmentLength);
        //          streamWriter.WriteLine("Average fragment depth: {0}", avgFragmentDepth);
        //          streamWriter.WriteLine("Percentage of unique generated fragments: {0}", distinctFragments.Count() / (double)fragments.Count);
        //        }

        #endregion
      }
      return base.Apply();
    }

    private IEnumerable<IFragment> GenerateFragments(SymbolGraph graph, ISymbolicExpressionTreeGrammar grammar, int numFragments, int maxDepth, int maxLength) {
      var fragments = new List<IFragment>();
      var random = RandomParameter.ActualValue;
      var count = SymbolicExpressionTreeParameter.ActualValue.Count();
      var threshold = count * FrequentFragmentOccurrenceThreshold.Value;
      var availableSymbols = graph.Nodes.Where(x => x.OutEdges != null && x.OutEdges.Count > 0 && x.Weight >= threshold).ToList();
      var weights = availableSymbols.Select(x => x.Weight).ToList();

      if (!(availableSymbols.Count == 0 || weights.Count == 0))
        for (int i = 0; i != numFragments; ++i) {
          var symbol = availableSymbols.SelectRandom(weights, random);
          var fragment = CreateFragment(symbol, random, grammar, threshold, maxDepth, maxLength, EnforceGrammarArity.Value);
          fragments.Add(new Fragment(fragment));
        }
      return fragments;
    }

    private static ISymbolicExpressionTreeNode CreateFragment(SymbolNode symbolNode, IRandom random, ISymbolicExpressionTreeGrammar grammar, double threshold, int depthLimit, int lengthLimit, bool enforceGrammarArity = true) {
      var node = symbolNode.Symbol.CreateTreeNode();
      if (node.HasLocalParameters) node.ResetLocalParameters(random);
      if (node is VariableTreeNode) (node as VariableTreeNode).VariableName = symbolNode.Label;

      if (symbolNode.OutEdges == null || symbolNode.OutEdges.Count == 0 || depthLimit < 0)
        return node; // node is a leaf so we just return it

      int maxCount = grammar.GetMaximumSubtreeCount(node.Symbol);
      if (maxCount > 0) {
        int minCount = grammar.GetMinimumSubtreeCount(node.Symbol);
        var arity = random.Next(enforceGrammarArity ? minCount : 1, maxCount + 1);
        var possibleChildConnections = new List<Arc>();

        if (depthLimit <= 2 || lengthLimit <= maxCount) { // if we are near the depth limit then we want to add leafs on the next level
          possibleChildConnections.AddRange(from e in symbolNode.OutEdges
                                            let n = (SymbolNode)e.Target
                                            where grammar.GetMaximumSubtreeCount(n.Symbol) == 0
                                            where n.Weight >= threshold
                                            select e);
        }
        // if there are no available connections towards leaf nodes (in case depthLimit <= 2)
        // or in case the depthLimit has not been reached yet
        if (possibleChildConnections.Count == 0)
          possibleChildConnections.AddRange(symbolNode.OutEdges.Where(a => ((SymbolNode)a.Target).Weight >= threshold)); // this will not be empty since we check above if the OutEdges are null
        var weights = new double[possibleChildConnections.Count];

        for (int i = 0; i != arity; ++i) {
          // adjust weights according to the probability a child will find itself on a certain argument position
          for (int j = 0; j != possibleChildConnections.Count; ++j) {
            var childSymbolNode = possibleChildConnections[j].Target as SymbolNode;
            double sumPos = childSymbolNode.Positions.Sum(x => x.Value);
            int v; childSymbolNode.Positions.TryGetValue(i, out v);
            weights[j] = possibleChildConnections[j].Weight * v / sumPos;
          }

          if (weights.Sum().IsAlmost(0.0)) continue;

          var selectedConnection = possibleChildConnections.SelectRandom(weights, random);
          var selectedChildSymbolNode = selectedConnection.Target as SymbolNode;
          var child = CreateFragment(selectedChildSymbolNode, random, grammar, threshold, depthLimit - 1, --lengthLimit);
          if (child == null) throw new Exception("Child cannot be null.");
          node.AddSubtree(child);
        }
      }
      return node;
    }
  }
}