Changeset 11197 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic

Timestamp:

07/16/14 16:32:48 (10 years ago)

Author:

bburlacu

Message:

#1772: Separated tree distance calculations in different classes which implement a new interface called IDistanceCalculator. The isomorphic tree distance calculates the distance based on the maximum common subtree between two symbolic expression trees, and the bottom-up tree distance returns a value based on the number of matching pairs of nodes in a bottom-up mapping. Introduced the distance calculator as a parameter in the SimilarityCalculator operator so that the diversity analyzer can use either of the two distances.

Location:

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Files:

• Analyzers/SymbolicDataAnalysisPopulationDiversityAnalyzer.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (2 diffs)
• Interfaces/IDistanceCalculator.cs (added)
• SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs (modified) (6 diffs)
• TreeDistance/BottomUpDistanceCalculator.cs (modified) (11 diffs)
• TreeDistance/IsomorphicTreeDistance.cs (added)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisPopulationDiversityAnalyzer.cs

@@ -49 +49 @@
     private const string StoreHistoryParameterName = "StoreHistory";
     // comparer parameters
-    private const string MatchVariablesParameterName = "MatchVariableNames";
-    private const string MatchVariableWeightsParameterName = "MatchVariableWeights";
-    private const string MatchConstantValuesParameterName = "MatchConstantValues";
     private const string SimilarityValuesParmeterName = "Similarity";
+
+    private const string DistanceCalculatorParameterName = "DistanceCalculator";
 
     #endregion
@@ -78 +77 @@
       get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
     }
-    public ValueParameter<BoolValue> MatchVariableNamesParameter {
-      get { return (ValueParameter<BoolValue>)Parameters[MatchVariablesParameterName]; }
-    }
-    public ValueParameter<BoolValue> MatchVariableWeightsParameter {
-      get { return (ValueParameter<BoolValue>)Parameters[MatchVariableWeightsParameterName]; }
-    }
-    public ValueParameter<BoolValue> MatchConstantValuesParameter {
-      get { return (ValueParameter<BoolValue>)Parameters[MatchConstantValuesParameterName]; }
-    }
     public ILookupParameter<DoubleValue> SimilarityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters[SimilarityValuesParmeterName]; }
+    }
+    public IValueParameter<IDistanceCalculator> DistanceCalculatorParameter {
+      get { return (IValueParameter<IDistanceCalculator>)Parameters[DistanceCalculatorParameterName]; }
     }
     #endregion
@@ -122 +115 @@
       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 ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names.", new BoolValue(true)));
-      Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights.", new BoolValue(true)));
-      Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values.", new BoolValue(true)));
       Parameters.Add(new ValueParameter<BoolValue>(StoreHistoryParameterName, "True if the tree lengths history of the population should be stored.", new BoolValue(false)));
       Parameters.Add(new LookupParameter<DoubleValue>(SimilarityValuesParmeterName, ""));
       Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
+      Parameters.Add(new ValueParameter<IDistanceCalculator>(DistanceCalculatorParameterName, "The distance calculator between trees.", new BottomUpDistanceCalculator()));
       UpdateCounterParameter.Hidden = true;
       UpdateIntervalParameter.Hidden = true;
@@ -159 +150 @@
         SimilarityParameter.ActualValue = new DoubleValue();
 
-        var comparer = new SymbolicExpressionTreeNodeSimilarityComparer {
-          MatchConstantValues = MatchConstantValuesParameter.Value.Value,
-          MatchVariableNames = MatchVariableNamesParameter.Value.Value,
-          MatchVariableWeights = MatchVariableWeightsParameter.Value.Value
-        };
-
         var operations = new OperationCollection { Parallel = true };
         foreach (var tree in trees) {
-          var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator {
+          var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator(DistanceCalculatorParameter.Value) {
             CurrentSymbolicExpressionTree = tree,
-            SimilarityComparer = comparer,
             MaximumTreeDepth = MaximumSymbolicExpressionTreeDepth.Value
           };

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -189 +189 @@
       <SubType>Code</SubType>
     </Compile>
+    <Compile Include="Interfaces\IDistanceCalculator.cs" />
     <Compile Include="Matching\SymbolicExpressionTreeCanonicalSorter.cs" />
     <Compile Include="Matching\SymbolicExpressionTreeEqualityComparer.cs" />
@@ -307 +308 @@
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionTracing.cs" />
     <Compile Include="TreeDistance\BottomUpDistanceCalculator.cs" />
+    <Compile Include="TreeDistance\IsomorphicTreeDistance.cs" />
     <None Include="HeuristicLab.snk" />
     <None Include="Plugin.cs.frame" />

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs

@@ -39 +39 @@
     private const string MatchConstantValuesParameterName = "MatchConstantValues";
 
+    private IDistanceCalculator distanceCalculator;
+
     public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
       get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
@@ -45 +47 @@
       get { return (IValueParameter<ISymbolicExpressionTree>)Parameters[CurrentSymbolicExpressionTreeParameterName]; }
     }
-    public ILookupParameter<BoolValue> MatchVariableNamesParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters[MatchVariablesParameterName]; }
-    }
-    public ILookupParameter<BoolValue> MatchVariableWeightsParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters[MatchVariableWeightsParameterName]; }
-    }
-    public ILookupParameter<BoolValue> MatchConstantValuesParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters[MatchConstantValuesParameterName]; }
-    }
+
     public ILookupParameter<DoubleValue> SimilarityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters[SimilarityValuesParmeterName]; }
@@ -61 +55 @@
       set { CurrentSymbolicExpressionTreeParameter.Value = value; }
     }
-    public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }
 
     public int MaximumTreeDepth { get; set; }
@@ -79 +72 @@
     }
 
-    public SymbolicDataAnalysisExpressionTreeSimilarityCalculator()
+    private SymbolicDataAnalysisExpressionTreeSimilarityCalculator() {
+    }
+
+    public SymbolicDataAnalysisExpressionTreeSimilarityCalculator(IDistanceCalculator distanceCalculator)
       : base() {
+      this.distanceCalculator = distanceCalculator;
+
       Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze."));
       Parameters.Add(new ValueParameter<ISymbolicExpressionTree>(CurrentSymbolicExpressionTreeParameterName, ""));
@@ -103 +101 @@
 
         if (found) {
-          //          similarity += MaxCommonSubtreeSimilarity(current, tree, SimilarityComparer);
-          var distance = BottomUpDistanceCalculator.CalculateDistance(current, tree) / (current.Length + tree.Length);
+          var distance = distanceCalculator.CalculateDistance(current, tree);
           similarity += 1 - distance;
         }
@@ -114 +111 @@
       return base.Apply();
     }
-
-    public static double CalculateSimilarity(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
-      return 2.0 * SymbolicExpressionTreeMatching.Match(a, b, comparer) / (a.GetLength() + b.GetLength());
-    }
-
-    /// <summary>
-    /// Try to match each pair of nodes from trees a and b and return a similarity value based on the maximum number of matched node pairs.
-    /// </summary>
-    /// <param name="a"></param>
-    /// <param name="b"></param>
-    /// <param name="comparer"></param>
-    /// <returns>A similarity value computed as 2.0 * MaxNumberOfMatchedPairs / (Sum of both tree sizes)</returns>
-    public static double MaxCommonSubtreeSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
-      int max = 0;
-      var rootA = a.Root.GetSubtree(0).GetSubtree(0);
-      var rootB = b.Root.GetSubtree(0).GetSubtree(0);
-      foreach (var aa in rootA.IterateNodesBreadth()) {
-        int lenA = aa.GetLength();
-        if (lenA <= max) continue;
-        foreach (var bb in rootB.IterateNodesBreadth()) {
-          int lenB = bb.GetLength();
-          if (lenB <= max) continue;
-          int matches = SymbolicExpressionTreeMatching.Match(aa, bb, comparer);
-          if (max < matches) max = matches;
-        }
-      }
-      return 2.0 * max / (rootA.GetLength() + rootB.GetLength());
-    }
-
-    // returns true if both nodes are variables, or both are constants, or both are functions
-    private static bool SameType(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (a is VariableTreeNode) {
-        return b is VariableTreeNode;
-      }
-      if (a is ConstantTreeNode) {
-        return b is ConstantTreeNode;
-      }
-      return true;
-    }
   }
 }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Globalization;
-using System.IO;
 using System.Linq;
 using System.Text;
 using System.Text.RegularExpressions;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
 using HeuristicLab.EvolutionTracking;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
@@ -36 +38 @@
   /// G. Valiente, "An Efficient Bottom-up Distance Between Trees", http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.7958
   /// </summary>
-  public static class BottomUpDistanceCalculator {
+  [StorableClass]
+  [Item("Bottom-up distance calculator", "An operator that calculates the bottom-up distance between two symbolic expression trees.")]
+  public class BottomUpDistanceCalculator : Item, IDistanceCalculator {
+    public BottomUpDistanceCalculator() { }
+
+    protected BottomUpDistanceCalculator(BottomUpDistanceCalculator original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BottomUpDistanceCalculator(this, cloner);
+    }
+
     /// <summary>
     /// Creates a compact representation of the two trees as a directed acyclic graph
@@ -77 +91 @@
           bool found = false;
           // for all nodes w in G in reverse order
-          foreach (var w in G.Vertices.Reverse()) {
+          var vertices = G.Vertices.Reverse();
+          foreach (var w in vertices) {
             if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
               break;
@@ -86 +101 @@
             if (V.SequenceEqual(W)) {
               K[v] = w;
-              //              // merge vertices
-              //              foreach (var a in K[v].InArcs) {
-              //                a.Target = w;
-              //              }
-              //              G.RemoveVertex(K[v]);
-
               found = true;
               break;
@@ -98 +107 @@
 
           if (!found) {
-            var w = new Vertex { Content = v, Label = Label(v), Weight = Height(v) };
+            var w = new Vertex { Content = v, Label = Label(v) };
             G.AddVertex(w);
             K[v] = w;
@@ -115 +124 @@
         }
       };
-
-      using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "graph.dot"))) {
-        var str = G.ExportDot();
-        file.WriteLine(str);
-      }
 
       return K;
@@ -158 +162 @@
     }
 
-    public static double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
+    // return a normalized distance measure in the interval (0,1)
+    public double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      return BottomUpDistance(t1, t2) / (t1.Length + t2.Length);
+    }
+
+    public static double BottomUpDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
       var K = Compact(t1, t2);
       var M = Mapping(t1, t2, K);
@@ -177 +186 @@
 
       double distance = s * p + i * q + d * r;
-
-      if (distance / (t1.Length + t2.Length) > 0.5 && M.Count > 0) {
-        using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.tex"))) {
-          var str = FormatMapping(t1, t2, M);
-          file.WriteLine(str);
-        }
-      }
-
       return distance;
     }
@@ -193 +194 @@
 
     private static int Height(IVertex v) {
-      return (int)Math.Round(v.Weight); // use the vertex weight as height in this particular context
+      return Height((ISymbolicExpressionTreeNode)v.Content);
     }
 
@@ -213 +214 @@
           var r2 = Item2.Root;
 
-          var virtualRootSymbol = new StartSymbol();
-          var virtualRootNode = virtualRootSymbol.CreateTreeNode();
-          virtualRootNode.AddSubtree(r1);
-          virtualRootNode.AddSubtree(r2);
-
-          var nodes = virtualRootNode.IterateNodesPostfix().ToList();
-
-          virtualRootNode.RemoveSubtree(0);
-          virtualRootNode.RemoveSubtree(0);
-
-          for (int i = 0; i < nodes.Count - 1; ++i) { yield return nodes[i]; }
+          var nodes = r1.IterateNodesPostfix().Select(x => new { Node = x, Height = r1.GetBranchLevel(x) })
+            .Concat(r2.IterateNodesPostfix().Select(x => new { Node = x, Height = r2.GetBranchLevel(x) }));
+
+          return nodes.OrderByDescending(x => x.Height).Select(x => x.Node);
+
+          //
+          //          var p1 = r1.Parent;
+          //          var p2 = r2.Parent;
+          //
+          //          var virtualRootSymbol = new StartSymbol();
+          //          var virtualRootNode = virtualRootSymbol.CreateTreeNode();
+          //
+          //          virtualRootNode.AddSubtree(r1);
+          //          virtualRootNode.AddSubtree(r2);
+          //
+          //          var nodes = virtualRootNode.IterateNodesPostfix().ToList();
+          //
+          //          virtualRootNode.RemoveSubtree(0);
+          //          virtualRootNode.RemoveSubtree(0);
+          //
+          //          r1.Parent = p1;
+          //          r2.Parent = p2;
+          //
+          //          for (int i = 0; i < nodes.Count - 1; ++i) { yield return nodes[i]; }
         }
       }
@@ -257 +271 @@
       return sb.ToString();
     }
+
   }
 }