Changeset 9423 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarity.cs

Timestamp:

05/02/13 13:48:38 (12 years ago)

Author:

bburlacu

Message:

#1772: Implemented GeneticItem-based similarity measure. Renamed ISymbolicExpressionTreeNodeComparer to ISymbolicExpressionTreeNodeSimilarityComparer.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic

Files:

• . (modified) (1 prop)
• 3.4/SymbolicDataAnalysisExpressionTreeSimilarity.cs (modified) (5 diffs)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarity.cs

@@ -20 +20 @@
 #endregion
 
-
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -69 +69 @@
     public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }
 
+    public Dictionary<ISymbolicExpressionTree, SymbolicDataAnalysisExpressionTreeSimilarity.GeneticItem[]> GeneticItems;
+
+    public int MaximumTreeDepth { get; set; }
+
     protected SymbolicDataAnalysisExpressionTreeSimilarityCalculator(SymbolicDataAnalysisExpressionTreeSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
     public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionTreeSimilarityCalculator(this, cloner); }
@@ -87 +91 @@
       var trees = SymbolicExpressionTreeParameter.ActualValue;
 
-      bool found = false;
       double similarity = 0.0;
       var current = CurrentSymbolicExpressionTree;
 
+      bool found = false;
       foreach (var tree in trees) {
-        if (tree == current) { found = true; }
-        if (!found) continue;
-
-        similarity += SymbolicDataAnalysisExpressionTreeSimilarity.MaxCommonSubtreeSimilarity(current, tree, SimilarityComparer);
-      }
+        if (tree == current) {
+          found = true;
+          continue;
+        }
+
+        if (found) {
+          similarity += SymbolicDataAnalysisExpressionTreeSimilarity.MaxCommonSubtreeSimilarity(current, tree, SimilarityComparer);
+          //          similarity += SymbolicDataAnalysisExpressionTreeSimilarity.GeneticItemSimilarity(GeneticItems[current], GeneticItems[tree], MaximumTreeDepth);
+        }
+      }
+
       lock (SimilarityParameter.ActualValue) {
         SimilarityParameter.ActualValue.Value += similarity;
@@ -104 +114 @@
   }
 
-
-
   public static class SymbolicDataAnalysisExpressionTreeSimilarity {
-    /// <summary>
-    /// Returns a similarity value based on the size of the maximum common subtree according to the given equality comparison.
-    /// </summary>
-    /// <param name="a"></param>
-    /// <param name="b"></param>
-    /// <param name="comparer"></param>
-    /// <returns>Similarity degree between the two trees, scaled between [0,1], where 1 = similar, 0 = non-similar</returns>
+    private static double CalculateSimilarity(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+      return 2.0 * SymbolicExpressionTreeMatching.Match(a, b, comp) / (a.GetLength() + b.GetLength());
+    }
+
     public static double MaxCommonSubtreeSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
       double max = 0;
-      foreach (var aa in a.Root.GetSubtree(0).GetSubtree(0).IterateNodesBreadth()) {
+      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 b.Root.GetSubtree(0).GetSubtree(0).IterateNodesBreadth()) {
+        foreach (var bb in rootB.IterateNodesBreadth()) {
           int lenB = bb.GetLength();
           if (lenB <= max) continue;
@@ -126 +133 @@
         }
       }
-      return max / Math.Max(a.Length, b.Length);
-    }
-
-    private static double CalculateSimilarity(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
-      return (double)SymbolicExpressionTreeMatching.Match(a, b, comp) / Math.Max(a.GetLength(), b.GetLength());
-    }
-
-    public static double CalculateCompoundSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
+      return 2.0 * max / (rootA.GetLength() + rootB.GetLength());
+    }
+
+    public static double GeneticItemSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int maximumTreeHeight, bool preventMultipleContribution = true) {
+      const int minLevelDelta = 1;
+      const int maxLevelDelta = 4;
+
+      var itemsA = a.GetGeneticItems(minLevelDelta, maxLevelDelta).ToArray();
+      var itemsB = b.GetGeneticItems(minLevelDelta, maxLevelDelta).ToArray();
+
+      return GeneticItemSimilarity(itemsA, itemsB, maximumTreeHeight);
+    }
+
+    public static double GeneticItemSimilarity(GeneticItem[] itemsA, GeneticItem[] itemsB, int maximumTreeHeight, bool preventMultipleContribution = true) {
+      double similarity = 0.0;
+      if (itemsA.Length == 0 || itemsB.Length == 0) return similarity;
+
+      var flagsB = new bool[itemsB.Length];
+
+      for (int i = 0; i != itemsA.Length; ++i) {
+        double simMax = 0.0;
+        int index = -1;
+        for (int j = 0; j != itemsB.Length; ++j) {
+          if (flagsB[j]) continue;
+          double sim = StructuralSimilarity(itemsA[i], itemsB[j], maximumTreeHeight);
+          if (sim > simMax) {
+            simMax = sim;
+            index = j;
+          }
+          if (preventMultipleContribution && index > -1) {
+            flagsB[index] = true;
+          }
+        }
+        similarity += simMax;
+      }
+      return similarity / itemsA.Length;
+    }
+
+    public static double AdditiveSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
       var nA = a.Root.GetSubtree(0).GetSubtree(0);
       var nB = b.Root.GetSubtree(0).GetSubtree(0);
 
-      var itemsA = nA.IterateNodesBreadth().Where(n => n.SubtreeCount > 0).Select(n => new MatchItem { Node = n, Matched = false }).ToArray();
-      var itemsB = nB.IterateNodesBreadth().Where(n => n.SubtreeCount > 0).Select(n => new MatchItem { Node = n, Matched = false }).ToArray();
-
-
-      double similaritySum = 0;
-
-      foreach (var ia in itemsA) {
-        foreach (var ib in itemsB) {
-          similaritySum += CalculateSimilarity(ia.Node, ib.Node, comparer);
-        }
-      }
-      return similaritySum / (itemsA.Length * itemsB.Length);
-    }
-  }
-
-  class MatchItem {
-    public ISymbolicExpressionTreeNode Node;
-    public bool Matched;
+      var nodesA = nA.IterateNodesBreadth().ToArray();
+      var nodesB = nB.IterateNodesBreadth().ToArray();
+
+      var similarities = nodesA.SelectMany(ia => nodesB, (ia, ib) => CalculateSimilarity(ia, ib, comparer)).Where(s => !s.IsAlmost(0.0)).ToList();
+
+      double average = similarities.Count > 0 ? similarities.Average() : 0;
+      if (average > 1.0) throw new Exception("Similarity average should be less than 1.0");
+      if (average < 0.0) throw new Exception("Similarity average should be greater than 0.0");
+      return average;
+    }
+
+    private static double StructuralSimilarity(GeneticItem g1, GeneticItem g2, int heightMax) {
+      if (!(SameType(g1.Ascendant, g2.Ascendant) && SameType(g1.Descendant, g2.Descendant))) return 0.0;
+
+      double s1 = 1.0 - Math.Abs(g1.LevelDelta - g2.LevelDelta) / heightMax;
+      double s2 = g1.Index == g2.Index ? 1.0 : 0.0;
+      double s3 = g1.ParamA.Variant.Name.Equals(g2.ParamA.Variant.Name) ? 1.0 : 0.0;
+      double s4 = g1.ParamB.Variant.Name.Equals(g2.ParamB.Variant.Name) ? 1.0 : 0.0;
+
+      double deltaCa = Math.Abs(g1.ParamA.Coeff - g2.ParamA.Coeff);
+      double deltaCb = Math.Abs(g1.ParamB.Coeff - g2.ParamB.Coeff);
+      double s5 = 0.0;
+      double s6 = 0.0;
+      // no time offsets so we hardcode s7 = s8 = 0.0
+      double s7 = 0.0;
+      double s8 = 0.0;
+      // variable indexes
+      double s9 = 0.0;
+      double s10 = 0.0;
+
+      // same type with g2.Ascendant so we only do one check
+      if (g1.Ascendant is VariableTreeNode) {
+        s5 = deltaCa / (((Variable)g1.Ascendant.Symbol).WeightManipulatorSigma * 4);
+        s9 = g1.ParamA.VariableIndex.Equals(g2.ParamA.VariableIndex) ? 1.0 : 0.0;
+      }
+      if (g1.Descendant is VariableTreeNode) {
+        s6 = deltaCb / (((Variable)g1.Descendant.Symbol).WeightManipulatorSigma * 4);
+        s10 = g1.ParamB.VariableIndex.Equals(g2.ParamB.VariableIndex) ? 1.0 : 0.0;
+      }
+
+      double similarity = 1.0;
+
+      double[] constributors = new double[10] { s1, s2, s3, s4, s5, s6, s7, s8, s9, s10 }; // s1...s10
+      double[] coefficients = new double[10] { 0.8, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2 }; // c1...c10
+
+      for (int i = 0; i != 10; ++i) {
+        similarity *= (1 - (1 - constributors[i]) * coefficients[i]);
+      }
+      return double.IsNaN(similarity) ? 0 : similarity;
+    }
+
+    // genetic items for computing tree similarity (S. Winkler)
+    public class GeneticItem {
+      public ISymbolicExpressionTreeNode Ascendant;
+      public ISymbolicExpressionTreeNode Descendant;
+      public int LevelDelta;
+      public int Index;
+      public double[] Coefficients; // c_i = 0.2, i=1,...,10, d_1 = 0.8
+      // parameters for the Ascendant and Descendant
+      public GeneticItemParameters ParamA;
+      public GeneticItemParameters ParamB;
+    }
+
+    public class GeneticItemParameters {
+      public Symbol Variant; // the variant of functions
+      public double Coeff; // the coefficient of terminals
+      public int TimeOffset; // the time offset of terminals
+      public int VariableIndex; // the variable index (of terminals)
+    }
+    // get genetic items
+    public static List<GeneticItem> GetGeneticItems(this ISymbolicExpressionTree tree, int minLevelDelta, int maxLevelDelta) {
+      return GetGeneticItems(tree.Root.GetSubtree(0).GetSubtree(0), minLevelDelta, maxLevelDelta).ToList();
+    }
+
+    private static double Coefficient(this ISymbolicExpressionTreeNode node) {
+      var variable = node as VariableTreeNode;
+      if (variable != null)
+        return variable.Weight;
+      var constant = node as ConstantTreeNode;
+      if (constant != null)
+        return constant.Value;
+      //      return double.NaN;
+      return 0.0;
+    }
+
+    private static int VariableIndex(this ISymbolicExpressionTreeNode node) {
+      var variable = node as VariableTreeNode;
+      if (variable != null)
+        return variable.Symbol.AllVariableNames.ToList().IndexOf(variable.VariableName);
+      return -1;
+    }
+
+    private static IEnumerable<GeneticItem> GetGeneticItems(ISymbolicExpressionTreeNode node, int minimumLevelDelta, int maximumLevelDelta) {
+      var descendants = node.IterateNodesBreadth().Skip(1).ToArray();
+      for (int i = 0; i != descendants.Length; ++i) {
+        var descendant = descendants[i];
+        var levelDelta = node.GetBranchLevel(descendant);
+        if (!(minimumLevelDelta <= levelDelta && levelDelta <= maximumLevelDelta)) continue;
+        var p = descendant;
+        while (p.Parent != node && p.Parent != null)
+          p = p.Parent;
+        if (p.Parent == null) throw new Exception("The child is not a descendant of node");
+        var geneticItem = new GeneticItem {
+          Ascendant = node, Descendant = descendant, LevelDelta = levelDelta, Index = node.IndexOfSubtree(p),
+          ParamA = new GeneticItemParameters {
+            Coeff = node.Coefficient(), TimeOffset = 0, VariableIndex = node.VariableIndex(), Variant = (Symbol)node.Symbol
+          },
+          ParamB = new GeneticItemParameters {
+            Coeff = descendant.Coefficient(), TimeOffset = 0, VariableIndex = descendant.VariableIndex(), Variant = (Symbol)descendant.Symbol
+          }
+        };
+        yield return geneticItem;
+      }
+    }
+
+    // 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;
+    }
   }
 }