Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs @ 10464

Last change on this file since 10464 was 10464, checked in by bburlacu, 10 years ago

#1772: Maintenance commit, removed some misplaced files, updated license header.

File size: 6.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 HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
26using HeuristicLab.Operators;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
31  [StorableClass]
32  public class SymbolicDataAnalysisExpressionTreeSimilarityCalculator : SingleSuccessorOperator {
33    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
34    private const string CurrentSymbolicExpressionTreeParameterName = "CurrentSymbolicExpressionTree";
35    private const string SimilarityValuesParmeterName = "Similarity";
36    // comparer parameters
37    private const string MatchVariablesParameterName = "MatchVariableNames";
38    private const string MatchVariableWeightsParameterName = "MatchVariableWeights";
39    private const string MatchConstantValuesParameterName = "MatchConstantValues";
40
41    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
42      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
43    }
44    public IValueParameter<ISymbolicExpressionTree> CurrentSymbolicExpressionTreeParameter {
45      get { return (IValueParameter<ISymbolicExpressionTree>)Parameters[CurrentSymbolicExpressionTreeParameterName]; }
46    }
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    }
56    public ILookupParameter<DoubleValue> SimilarityParameter {
57      get { return (ILookupParameter<DoubleValue>)Parameters[SimilarityValuesParmeterName]; }
58    }
59    public ISymbolicExpressionTree CurrentSymbolicExpressionTree {
60      get { return CurrentSymbolicExpressionTreeParameter.Value; }
61      set { CurrentSymbolicExpressionTreeParameter.Value = value; }
62    }
63    public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }
64
65    public int MaximumTreeDepth { get; set; }
66
67    protected SymbolicDataAnalysisExpressionTreeSimilarityCalculator(
68      SymbolicDataAnalysisExpressionTreeSimilarityCalculator original, Cloner cloner)
69      : base(original, cloner) {
70    }
71
72    public override IDeepCloneable Clone(Cloner cloner) {
73      return new SymbolicDataAnalysisExpressionTreeSimilarityCalculator(this, cloner);
74    }
75
76    [StorableConstructor]
77    protected SymbolicDataAnalysisExpressionTreeSimilarityCalculator(bool deserializing)
78      : base(deserializing) {
79    }
80
81    public SymbolicDataAnalysisExpressionTreeSimilarityCalculator()
82      : base() {
83      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze."));
84      Parameters.Add(new ValueParameter<ISymbolicExpressionTree>(CurrentSymbolicExpressionTreeParameterName, ""));
85      Parameters.Add(new LookupParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names."));
86      Parameters.Add(new LookupParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights."));
87      Parameters.Add(new LookupParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values."));
88      Parameters.Add(new LookupParameter<DoubleValue>(SimilarityValuesParmeterName, ""));
89    }
90
91    public override IOperation Apply() {
92      var trees = SymbolicExpressionTreeParameter.ActualValue;
93
94      double similarity = 0.0;
95      var current = CurrentSymbolicExpressionTree;
96
97      bool found = false;
98      foreach (var tree in trees) {
99        if (tree == current) {
100          found = true;
101          continue;
102        }
103
104        if (found) {
105          similarity += MaxCommonSubtreeSimilarity(current, tree, SimilarityComparer);
106        }
107      }
108
109      lock (SimilarityParameter.ActualValue) {
110        SimilarityParameter.ActualValue.Value += similarity;
111      }
112      return base.Apply();
113    }
114
115    public static double CalculateSimilarity(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b,
116      SymbolicExpressionTreeNodeSimilarityComparer comp) {
117      return 2.0 * SymbolicExpressionTreeMatching.Match(a, b, comp) / (a.GetLength() + b.GetLength());
118    }
119
120    public static double MaxCommonSubtreeSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b,
121      SymbolicExpressionTreeNodeSimilarityComparer comparer) {
122      double max = 0;
123      var rootA = a.Root.GetSubtree(0).GetSubtree(0);
124      var rootB = b.Root.GetSubtree(0).GetSubtree(0);
125      foreach (var aa in rootA.IterateNodesBreadth()) {
126        int lenA = aa.GetLength();
127        if (lenA <= max) continue;
128        foreach (var bb in rootB.IterateNodesBreadth()) {
129          int lenB = bb.GetLength();
130          if (lenB <= max) continue;
131          int matches = SymbolicExpressionTreeMatching.Match(aa, bb, comparer);
132          if (max < matches) max = matches;
133        }
134      }
135      return 2.0 * max / (rootA.GetLength() + rootB.GetLength());
136    }
137
138    // returns true if both nodes are variables, or both are constants, or both are functions
139    private static bool SameType(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
140      if (a is VariableTreeNode) {
141        return b is VariableTreeNode;
142      }
143      if (a is ConstantTreeNode) {
144        return b is ConstantTreeNode;
145      }
146      return true;
147    }
148  }
149}
Note: See TracBrowser for help on using the repository browser.