Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs @ 11482

Last change on this file since 11482 was 11482, checked in by bburlacu, 8 years ago

#1772: Added the ability to ignore variable weights or constant values to the BottomUpSimilarityCalculator and added parameters to the SymbolicDataAnalysisBottomUpDiversityAnalyzer. Added separate methods in the MaxCommonSubtreeSimilarityCalculator for performing matching with full subtrees (including all leaves) or without (like the old - and better - behavior).

File size: 8.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Diagnostics;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
33  [StorableClass]
34  [Item("BottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
35  public class BottomUpSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator, ISymbolicDataAnalysisExpressionSimilarityCalculator {
36    private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" };
37    public bool MatchVariableWeights { get; set; }
38    public bool MatchConstantValues { get; set; }
39
40    public BottomUpSimilarityCalculator() { }
41
42    protected BottomUpSimilarityCalculator(BottomUpSimilarityCalculator original, Cloner cloner)
43      : base(original, cloner) {
44    }
45
46    public override IDeepCloneable Clone(Cloner cloner) {
47      return new BottomUpSimilarityCalculator(this, cloner);
48    }
49
50    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
51      if (t1 == t2)
52        return 1;
53
54      var map = ComputeBottomUpMapping(t1.Root, t2.Root);
55      return 2.0 * map.Count / (t1.Length + t2.Length);
56    }
57
58    public override double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution) {
59      var t1 = leftSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree;
60      var t2 = rightSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree;
61
62      if (t1 == null || t2 == null)
63        throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");
64
65      var similarity = CalculateSimilarity(t1, t2);
66      if (similarity > 1.0)
67        throw new Exception("Similarity value cannot be greater than 1");
68
69      return similarity;
70    }
71
72    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
73      var compactedGraph = Compact(n1, n2);
74
75      var forwardMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
76      var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
77
78      // visit nodes in order of decreasing height to ensure correct mapping
79      foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Depth)) {
80        if (forwardMap.ContainsKey(v))
81          continue;
82        var kv = compactedGraph[v];
83        ISymbolicExpressionTreeNode w = null;
84        foreach (var t in n2.IterateNodesPrefix()) {
85          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
86            continue;
87          w = t;
88          break;
89        }
90        if (w == null) continue;
91
92        // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly (as in the paper) because the trees are unordered (subtree order might differ)
93        // the solution is to sort subtrees by label using IterateBreadthOrdered (this will work because the subtrees are isomorphic!) and simultaneously iterate over the two subtrees
94        var eV = IterateBreadthOrdered(v).GetEnumerator();
95        var eW = IterateBreadthOrdered(w).GetEnumerator();
96
97        while (eV.MoveNext() && eW.MoveNext()) {
98          var s = eV.Current;
99          var t = eW.Current;
100
101          Debug.Assert(!reverseMap.ContainsKey(t));
102
103          forwardMap[s] = t;
104          reverseMap[t] = s;
105        }
106      }
107
108      return forwardMap;
109    }
110
111    /// <summary>
112    /// Creates a compact representation of the two trees as a directed acyclic graph
113    /// </summary>
114    /// <param name="n1">The root of the first tree</param>
115    /// <param name="n2">The root of the second tree</param>
116    /// <returns>The compacted DAG representing the two trees</returns>
117    private Dictionary<ISymbolicExpressionTreeNode, GraphNode> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
118      var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
119      var labelMap = new Dictionary<string, GraphNode>(); // L
120      var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
121
122      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
123      var list = new List<GraphNode>();
124      var queue = new Queue<ISymbolicExpressionTreeNode>();
125
126      foreach (var n in nodes) {
127        if (n.SubtreeCount == 0) {
128          var label = Label(n);
129          if (!labelMap.ContainsKey(label)) {
130            var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
131            labelMap[z.Label] = z;
132            list.Add(z);
133          }
134          nodeMap[n] = labelMap[label];
135          queue.Enqueue(n);
136        } else {
137          childrenCount[n] = n.SubtreeCount;
138        }
139      }
140      while (queue.Any()) {
141        var n = queue.Dequeue();
142
143        if (n.SubtreeCount > 0) {
144          var label = n.Symbol.Name;
145          bool found = false;
146          var depth = n.GetDepth();
147
148          bool sort = commutativeSymbols.Contains(label);
149          var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
150          if (sort) nNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
151
152          for (int i = list.Count - 1; i >= 0; --i) {
153            var w = list[i];
154
155            if (!(n.SubtreeCount == w.ChildrenCount && label == w.Label && depth == w.Depth))
156              continue;
157
158            // sort V and W when the symbol is commutative because we are dealing with unordered trees
159            var m = w.SymbolicExpressionTreeNode;
160            var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
161            if (sort) mNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
162
163            if (nNodes.SequenceEqual(mNodes)) {
164              nodeMap[n] = w;
165              found = true;
166              break;
167            }
168          }
169
170          if (!found) {
171            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth, ChildrenCount = n.SubtreeCount };
172            list.Add(w);
173            nodeMap[n] = w;
174          }
175        }
176
177        if (n == n1 || n == n2)
178          continue;
179
180        var p = n.Parent;
181        if (p == null)
182          continue;
183
184        childrenCount[p]--;
185
186        if (childrenCount[p] == 0)
187          queue.Enqueue(p);
188      }
189
190      return nodeMap;
191    }
192
193    private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) {
194      var list = new List<ISymbolicExpressionTreeNode> { node };
195      int i = 0;
196      while (i < list.Count) {
197        var n = list[i];
198        if (n.SubtreeCount > 0) {
199          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x.ToString(), StringComparer.Ordinal) : n.Subtrees;
200          list.AddRange(subtrees);
201        }
202        i++;
203      }
204      return list;
205    }
206
207    private string Label(ISymbolicExpressionTreeNode node) {
208      var constant = node as ConstantTreeNode;
209      if (constant != null && !MatchConstantValues)
210        return constant.Symbol.Name;
211      var variable = node as VariableTreeNode;
212      if (variable != null && !MatchVariableWeights) {
213        return variable.VariableName;
214      }
215      return node.ToString();
216    }
217
218    private class GraphNode {
219      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
220      public string Label;
221      public int Depth;
222      public int ChildrenCount;
223    }
224  }
225}
Note: See TracBrowser for help on using the repository browser.