source: trunk/sources/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4/SymbolicExpressionTreeBottomUpSimilarityCalculatorTest.cs @ 11978

Last change on this file since 11978 was 11978, checked in by bburlacu, 7 years ago

#2313:

  • Order nodes in the first tree by decreasing depth when doing the mapping (after the two trees have already been compacted into a directed acyclic graph and the isomorphic subtrees have already been identified).
  • Update unit test with the test case that helped identify this bug
  • Minor changes: rename Label method to GetLabel and make it static, update year in license header
File size: 4.6 KB
Line 
1using System;
2using System.Diagnostics;
3using HeuristicLab.Random;
4using Microsoft.VisualStudio.TestTools.UnitTesting;
5
6namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tests {
7  [TestClass]
8  public class BottomUpSimilarityCalculatorTest {
9    private readonly SymbolicExpressionTreeBottomUpSimilarityCalculator busCalculator;
10    private readonly SymbolicExpressionImporter importer;
11
12    private const int N = 150;
13    private const int Rows = 1;
14    private const int Columns = 10;
15
16    public BottomUpSimilarityCalculatorTest() {
17      busCalculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator();
18      importer = new SymbolicExpressionImporter();
19    }
20
21    [TestMethod]
22    [TestCategory("Problems.DataAnalysis.Symbolic")]
23    [TestProperty("Time", "short")]
24    public void BottomUpTreeSimilarityCalculatorTestMapping() {
25      TestMatchedNodes("(+ 1 2)", "(+ 2 1)", 5);
26      TestMatchedNodes("(- 2 1)", "(- 1 2)", 2);
27      TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (+ (variable 1 X2) 1))", 2);
28
29      TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (variable 1 X2))", 2);
30
31      TestMatchedNodes("(+ (variable 1 a) (variable 1 b))", "(+ (variable 1 a) (variable 1 a))", 1);
32      TestMatchedNodes("(+ (+ (variable 1 a) (variable 1 b)) (variable 1 b))", "(+ (* (+ (variable 1 a) (variable 1 b)) (variable 1 b)) (+ (+ (variable 1 a) (variable 1 b)) (variable 1 b)))", 5);
33
34      TestMatchedNodes(
35        "(* (+ 2.84 (exp (+ (log (/ (variable 2.0539 X5) (variable -9.2452e-1 X6))) (/ (variable 2.0539 X5) (variable -9.2452e-1 X6))))) 2.9081)",
36        "(* (- (variable 9.581e-1 X6) (+ (- (variable 5.1491e-1 X5) 1.614e+1) (+ (/ (variable 2.0539 X5) (variable -9.2452e-1 X6)) (log (/ (variable 2.0539 X5) (variable -9.2452e-1 X6)))))) 2.9081)",
37        9);
38
39      TestMatchedNodes("(* (* (* (variable 1.68 x) (* (variable 1.68 x) (variable 2.55 x))) (variable 1.68 x)) (* (* (variable 1.68 x) (* (variable 1.68 x) (* (variable 1.68 x) (variable 2.55 x)))) (variable 2.55 x)))", "(* (variable 2.55 x) (* (variable 1.68 x) (* (variable 1.68 x) (* (variable 1.68 x) (variable 2.55 x)))))", 9);
40
41      TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ -4.3072 (variable 2.4691 X7)) (exp 2.1033)))", 6);
42      TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ (variable 2.4691 X7) -4.3072) (exp 2.1033)))", 4);
43
44      const string expr1 = "(* (- 1.2175e+1 (+ (/ (exp -1.4134e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (log 1.3011e+1))";
45      const string expr2 = "(* (- 1.2175e+1 (+ (/ (/ (+ (variable 3.0140 X9) (variable 1.3430 X8)) -1.0864e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (exp (variable 4.0899e-1 X7)))";
46
47      TestMatchedNodes(expr1, expr2, 23);
48
49    }
50
51    private void TestMatchedNodes(string expr1, string expr2, int expected) {
52      var t1 = importer.Import(expr1);
53      var t2 = importer.Import(expr2);
54
55      var mapping = busCalculator.ComputeBottomUpMapping(t1.Root, t2.Root);
56      var c = mapping.Count;
57
58      if (c != expected) {
59        throw new Exception("Match count " + c + " is different than expected value " + expected);
60      }
61    }
62
63    [TestMethod]
64    [TestCategory("Problems.DataAnalysis.Symbolic")]
65    [TestProperty("Time", "long")]
66    public void BottomUpTreeSimilarityCalculatorTestPerformance() {
67      var grammar = new TypeCoherentExpressionGrammar();
68      grammar.ConfigureAsDefaultRegressionGrammar();
69      var twister = new MersenneTwister(31415);
70      var ds = Util.CreateRandomDataset(twister, Rows, Columns);
71      var trees = Util.CreateRandomTrees(twister, ds, grammar, N, 1, 100, 0, 0);
72
73      double s = 0;
74      var sw = new Stopwatch();
75
76      sw.Start();
77      for (int i = 0; i < trees.Length - 1; ++i) {
78        for (int j = i + 1; j < trees.Length; ++j) {
79          s += busCalculator.CalculateSimilarity(trees[i], trees[j]);
80        }
81      }
82
83      sw.Stop();
84      Console.WriteLine("Elapsed time: " + sw.ElapsedMilliseconds / 1000.0 + ", Avg. similarity: " + s / (N * (N - 1) / 2));
85      Console.WriteLine(N * (N + 1) / (2 * sw.ElapsedMilliseconds / 1000.0) + " similarity calculations per second.");
86    }
87  }
88}
Note: See TracBrowser for help on using the repository browser.