Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisPopulationDiversityAnalyzer.cs

    r10464 r11197  
    4949    private const string StoreHistoryParameterName = "StoreHistory";
    5050    // comparer parameters
    51     private const string MatchVariablesParameterName = "MatchVariableNames";
    52     private const string MatchVariableWeightsParameterName = "MatchVariableWeights";
    53     private const string MatchConstantValuesParameterName = "MatchConstantValues";
    5451    private const string SimilarityValuesParmeterName = "Similarity";
     52
     53    private const string DistanceCalculatorParameterName = "DistanceCalculator";
    5554
    5655    #endregion
     
    7877      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    7978    }
    80     public ValueParameter<BoolValue> MatchVariableNamesParameter {
    81       get { return (ValueParameter<BoolValue>)Parameters[MatchVariablesParameterName]; }
    82     }
    83     public ValueParameter<BoolValue> MatchVariableWeightsParameter {
    84       get { return (ValueParameter<BoolValue>)Parameters[MatchVariableWeightsParameterName]; }
    85     }
    86     public ValueParameter<BoolValue> MatchConstantValuesParameter {
    87       get { return (ValueParameter<BoolValue>)Parameters[MatchConstantValuesParameterName]; }
    88     }
    8979    public ILookupParameter<DoubleValue> SimilarityParameter {
    9080      get { return (ILookupParameter<DoubleValue>)Parameters[SimilarityValuesParmeterName]; }
     81    }
     82    public IValueParameter<IDistanceCalculator> DistanceCalculatorParameter {
     83      get { return (IValueParameter<IDistanceCalculator>)Parameters[DistanceCalculatorParameterName]; }
    9184    }
    9285    #endregion
     
    122115      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
    123116      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
    124       Parameters.Add(new ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names.", new BoolValue(true)));
    125       Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights.", new BoolValue(true)));
    126       Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values.", new BoolValue(true)));
    127117      Parameters.Add(new ValueParameter<BoolValue>(StoreHistoryParameterName, "True if the tree lengths history of the population should be stored.", new BoolValue(false)));
    128118      Parameters.Add(new LookupParameter<DoubleValue>(SimilarityValuesParmeterName, ""));
    129119      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
     120      Parameters.Add(new ValueParameter<IDistanceCalculator>(DistanceCalculatorParameterName, "The distance calculator between trees.", new BottomUpDistanceCalculator()));
    130121      UpdateCounterParameter.Hidden = true;
    131122      UpdateIntervalParameter.Hidden = true;
     
    159150        SimilarityParameter.ActualValue = new DoubleValue();
    160151
    161         var comparer = new SymbolicExpressionTreeNodeSimilarityComparer {
    162           MatchConstantValues = MatchConstantValuesParameter.Value.Value,
    163           MatchVariableNames = MatchVariableNamesParameter.Value.Value,
    164           MatchVariableWeights = MatchVariableWeightsParameter.Value.Value
    165         };
    166 
    167152        var operations = new OperationCollection { Parallel = true };
    168153        foreach (var tree in trees) {
    169           var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator {
     154          var op = new SymbolicDataAnalysisExpressionTreeSimilarityCalculator(DistanceCalculatorParameter.Value) {
    170155            CurrentSymbolicExpressionTree = tree,
    171             SimilarityComparer = comparer,
    172156            MaximumTreeDepth = MaximumSymbolicExpressionTreeDepth.Value
    173157          };
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r11015 r11197  
    189189      <SubType>Code</SubType>
    190190    </Compile>
     191    <Compile Include="Interfaces\IDistanceCalculator.cs" />
    191192    <Compile Include="Matching\SymbolicExpressionTreeCanonicalSorter.cs" />
    192193    <Compile Include="Matching\SymbolicExpressionTreeEqualityComparer.cs" />
     
    307308    <Compile Include="Tracking\SymbolicDataAnalysisExpressionTracing.cs" />
    308309    <Compile Include="TreeDistance\BottomUpDistanceCalculator.cs" />
     310    <Compile Include="TreeDistance\IsomorphicTreeDistance.cs" />
    309311    <None Include="HeuristicLab.snk" />
    310312    <None Include="Plugin.cs.frame" />
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs

    r11015 r11197  
    3939    private const string MatchConstantValuesParameterName = "MatchConstantValues";
    4040
     41    private IDistanceCalculator distanceCalculator;
     42
    4143    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
    4244      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
     
    4547      get { return (IValueParameter<ISymbolicExpressionTree>)Parameters[CurrentSymbolicExpressionTreeParameterName]; }
    4648    }
    47     public ILookupParameter<BoolValue> MatchVariableNamesParameter {
    48       get { return (ILookupParameter<BoolValue>)Parameters[MatchVariablesParameterName]; }
    49     }
    50     public ILookupParameter<BoolValue> MatchVariableWeightsParameter {
    51       get { return (ILookupParameter<BoolValue>)Parameters[MatchVariableWeightsParameterName]; }
    52     }
    53     public ILookupParameter<BoolValue> MatchConstantValuesParameter {
    54       get { return (ILookupParameter<BoolValue>)Parameters[MatchConstantValuesParameterName]; }
    55     }
     49
    5650    public ILookupParameter<DoubleValue> SimilarityParameter {
    5751      get { return (ILookupParameter<DoubleValue>)Parameters[SimilarityValuesParmeterName]; }
     
    6155      set { CurrentSymbolicExpressionTreeParameter.Value = value; }
    6256    }
    63     public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }
    6457
    6558    public int MaximumTreeDepth { get; set; }
     
    7972    }
    8073
    81     public SymbolicDataAnalysisExpressionTreeSimilarityCalculator()
     74    private SymbolicDataAnalysisExpressionTreeSimilarityCalculator() {
     75    }
     76
     77    public SymbolicDataAnalysisExpressionTreeSimilarityCalculator(IDistanceCalculator distanceCalculator)
    8278      : base() {
     79      this.distanceCalculator = distanceCalculator;
     80
    8381      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze."));
    8482      Parameters.Add(new ValueParameter<ISymbolicExpressionTree>(CurrentSymbolicExpressionTreeParameterName, ""));
     
    103101
    104102        if (found) {
    105           //          similarity += MaxCommonSubtreeSimilarity(current, tree, SimilarityComparer);
    106           var distance = BottomUpDistanceCalculator.CalculateDistance(current, tree) / (current.Length + tree.Length);
     103          var distance = distanceCalculator.CalculateDistance(current, tree);
    107104          similarity += 1 - distance;
    108105        }
     
    114111      return base.Apply();
    115112    }
    116 
    117     public static double CalculateSimilarity(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    118       return 2.0 * SymbolicExpressionTreeMatching.Match(a, b, comparer) / (a.GetLength() + b.GetLength());
    119     }
    120 
    121     /// <summary>
    122     /// 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.
    123     /// </summary>
    124     /// <param name="a"></param>
    125     /// <param name="b"></param>
    126     /// <param name="comparer"></param>
    127     /// <returns>A similarity value computed as 2.0 * MaxNumberOfMatchedPairs / (Sum of both tree sizes)</returns>
    128     public static double MaxCommonSubtreeSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    129       int max = 0;
    130       var rootA = a.Root.GetSubtree(0).GetSubtree(0);
    131       var rootB = b.Root.GetSubtree(0).GetSubtree(0);
    132       foreach (var aa in rootA.IterateNodesBreadth()) {
    133         int lenA = aa.GetLength();
    134         if (lenA <= max) continue;
    135         foreach (var bb in rootB.IterateNodesBreadth()) {
    136           int lenB = bb.GetLength();
    137           if (lenB <= max) continue;
    138           int matches = SymbolicExpressionTreeMatching.Match(aa, bb, comparer);
    139           if (max < matches) max = matches;
    140         }
    141       }
    142       return 2.0 * max / (rootA.GetLength() + rootB.GetLength());
    143     }
    144 
    145     // returns true if both nodes are variables, or both are constants, or both are functions
    146     private static bool SameType(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    147       if (a is VariableTreeNode) {
    148         return b is VariableTreeNode;
    149       }
    150       if (a is ConstantTreeNode) {
    151         return b is ConstantTreeNode;
    152       }
    153       return true;
    154     }
    155113  }
    156114}
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs

    r11165 r11197  
    2323using System.Collections.Generic;
    2424using System.Globalization;
    25 using System.IO;
    2625using System.Linq;
    2726using System.Text;
    2827using System.Text.RegularExpressions;
     28using HeuristicLab.Common;
     29using HeuristicLab.Core;
    2930using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    3031using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
    3132using HeuristicLab.EvolutionTracking;
     33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3234
    3335namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
     
    3638  /// G. Valiente, "An Efficient Bottom-up Distance Between Trees", http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.7958
    3739  /// </summary>
    38   public static class BottomUpDistanceCalculator {
     40  [StorableClass]
     41  [Item("Bottom-up distance calculator", "An operator that calculates the bottom-up distance between two symbolic expression trees.")]
     42  public class BottomUpDistanceCalculator : Item, IDistanceCalculator {
     43    public BottomUpDistanceCalculator() { }
     44
     45    protected BottomUpDistanceCalculator(BottomUpDistanceCalculator original, Cloner cloner)
     46      : base(original, cloner) {
     47    }
     48
     49    public override IDeepCloneable Clone(Cloner cloner) {
     50      return new BottomUpDistanceCalculator(this, cloner);
     51    }
     52
    3953    /// <summary>
    4054    /// Creates a compact representation of the two trees as a directed acyclic graph
     
    7791          bool found = false;
    7892          // for all nodes w in G in reverse order
    79           foreach (var w in G.Vertices.Reverse()) {
     93          var vertices = G.Vertices.Reverse();
     94          foreach (var w in vertices) {
    8095            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
    8196              break;
     
    86101            if (V.SequenceEqual(W)) {
    87102              K[v] = w;
    88               //              // merge vertices
    89               //              foreach (var a in K[v].InArcs) {
    90               //                a.Target = w;
    91               //              }
    92               //              G.RemoveVertex(K[v]);
    93 
    94103              found = true;
    95104              break;
     
    98107
    99108          if (!found) {
    100             var w = new Vertex { Content = v, Label = Label(v), Weight = Height(v) };
     109            var w = new Vertex { Content = v, Label = Label(v) };
    101110            G.AddVertex(w);
    102111            K[v] = w;
     
    115124        }
    116125      };
    117 
    118       using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "graph.dot"))) {
    119         var str = G.ExportDot();
    120         file.WriteLine(str);
    121       }
    122126
    123127      return K;
     
    158162    }
    159163
    160     public static double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
     164    // return a normalized distance measure in the interval (0,1)
     165    public double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     166      return BottomUpDistance(t1, t2) / (t1.Length + t2.Length);
     167    }
     168
     169    public static double BottomUpDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
    161170      var K = Compact(t1, t2);
    162171      var M = Mapping(t1, t2, K);
     
    177186
    178187      double distance = s * p + i * q + d * r;
    179 
    180       if (distance / (t1.Length + t2.Length) > 0.5 && M.Count > 0) {
    181         using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.tex"))) {
    182           var str = FormatMapping(t1, t2, M);
    183           file.WriteLine(str);
    184         }
    185       }
    186 
    187188      return distance;
    188189    }
     
    193194
    194195    private static int Height(IVertex v) {
    195       return (int)Math.Round(v.Weight); // use the vertex weight as height in this particular context
     196      return Height((ISymbolicExpressionTreeNode)v.Content);
    196197    }
    197198
     
    213214          var r2 = Item2.Root;
    214215
    215           var virtualRootSymbol = new StartSymbol();
    216           var virtualRootNode = virtualRootSymbol.CreateTreeNode();
    217           virtualRootNode.AddSubtree(r1);
    218           virtualRootNode.AddSubtree(r2);
    219 
    220           var nodes = virtualRootNode.IterateNodesPostfix().ToList();
    221 
    222           virtualRootNode.RemoveSubtree(0);
    223           virtualRootNode.RemoveSubtree(0);
    224 
    225           for (int i = 0; i < nodes.Count - 1; ++i) { yield return nodes[i]; }
     216          var nodes = r1.IterateNodesPostfix().Select(x => new { Node = x, Height = r1.GetBranchLevel(x) })
     217            .Concat(r2.IterateNodesPostfix().Select(x => new { Node = x, Height = r2.GetBranchLevel(x) }));
     218
     219          return nodes.OrderByDescending(x => x.Height).Select(x => x.Node);
     220
     221          //
     222          //          var p1 = r1.Parent;
     223          //          var p2 = r2.Parent;
     224          //
     225          //          var virtualRootSymbol = new StartSymbol();
     226          //          var virtualRootNode = virtualRootSymbol.CreateTreeNode();
     227          //
     228          //          virtualRootNode.AddSubtree(r1);
     229          //          virtualRootNode.AddSubtree(r2);
     230          //
     231          //          var nodes = virtualRootNode.IterateNodesPostfix().ToList();
     232          //
     233          //          virtualRootNode.RemoveSubtree(0);
     234          //          virtualRootNode.RemoveSubtree(0);
     235          //
     236          //          r1.Parent = p1;
     237          //          r2.Parent = p2;
     238          //
     239          //          for (int i = 0; i < nodes.Count - 1; ++i) { yield return nodes[i]; }
    226240        }
    227241      }
     
    257271      return sb.ToString();
    258272    }
     273
    259274  }
    260275}
Note: See TracChangeset for help on using the changeset viewer.