Ignore:
Timestamp:
01/08/19 15:39:49 (3 years ago)
Author:
pfleck
Message:

#2947 merged trunk into branch

Location:
branches/2947_ConfigurableIndexedDataTable
Files:
19 edited
14 copied

Legend:

Unmodified
Added
Removed
  • branches/2947_ConfigurableIndexedDataTable

  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic

  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/LinearModelToTreeConverter.cs

    r15583 r16520  
    3737      string[] variableNames, double[] coefficients,
    3838      double @const = 0) {
     39
    3940      if (factorCoefficients.Length == 0 && coefficients.Length == 0) throw new ArgumentException();
    40       ISymbolicExpressionTree p1 = null;
     41
     42      // Create tree for double variables
     43      ISymbolicExpressionTree tree = null;     
    4144      if (coefficients.Length > 0) {
    42         p1 = CreateTree(variableNames, new int[variableNames.Length], coefficients, @const);
    43         if (factorCoefficients.Length == 0)
    44           return p1;
     45        tree = CreateTree(variableNames, new int[variableNames.Length], coefficients, @const);
     46        if (factorCoefficients.Length == 0) return tree;
    4547      }
     48
     49      // Create tree for string variables
     50      ISymbolicExpressionTree factorTree = null;     
    4651      if (factorCoefficients.Length > 0) {
    47         var p2 = CreateTree(factors, factorCoefficients);
    48         if (p1 == null) return p2;
     52        factorTree = CreateTree(factors, factorCoefficients, @const);
     53        if (tree == null) return factorTree; 
     54      }
    4955
    50         // combine
    51         ISymbolicExpressionTreeNode add = p1.Root.GetSubtree(0).GetSubtree(0);
    52         foreach (var binFactorNode in p2.IterateNodesPrefix().OfType<BinaryFactorVariableTreeNode>())
    53           add.AddSubtree(binFactorNode);
    54         return p1;
    55       }
     56      // Combine both trees
     57      ISymbolicExpressionTreeNode add = tree.Root.GetSubtree(0).GetSubtree(0);
     58      foreach (var binFactorNode in factorTree.IterateNodesPrefix().OfType<BinaryFactorVariableTreeNode>())
     59        add.InsertSubtree(add.SubtreeCount - 1, binFactorNode);
     60      return tree;
     61
    5662      throw new ArgumentException();
    5763    }
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs

    r15583 r16520  
    3737    private static readonly Division divSymbol = new Division();
    3838    private static readonly Constant constSymbol = new Constant();
     39    private static readonly Absolute absSymbol = new Absolute();
    3940    private static readonly Logarithm logSymbol = new Logarithm();
    4041    private static readonly Exponential expSymbol = new Exponential();
     
    4243    private static readonly Square sqrSymbol = new Square();
    4344    private static readonly SquareRoot sqrtSymbol = new SquareRoot();
     45    private static readonly AnalyticQuotient aqSymbol = new AnalyticQuotient();
     46    private static readonly Cube cubeSymbol = new Cube();
     47    private static readonly CubeRoot cubeRootSymbol = new CubeRoot();
    4448    private static readonly Power powSymbol = new Power();
    4549    private static readonly Sine sineSymbol = new Sine();
     
    131135    }
    132136
     137    private static bool IsAbsolute(ISymbolicExpressionTreeNode node) {
     138      return node.Symbol is Absolute;
     139    }
     140
    133141    // exponential
    134142    private static bool IsLog(ISymbolicExpressionTreeNode node) {
     
    152160    }
    153161
     162    private static bool IsCube(ISymbolicExpressionTreeNode node) {
     163      return node.Symbol is Cube;
     164    }
     165
     166    private static bool IsCubeRoot(ISymbolicExpressionTreeNode node) {
     167      return node.Symbol is CubeRoot;
     168    }
     169
    154170    private static bool IsPower(ISymbolicExpressionTreeNode node) {
    155171      return node.Symbol is Power;
     
    167183    private static bool IsTangent(ISymbolicExpressionTreeNode node) {
    168184      return node.Symbol is Tangent;
     185    }
     186
     187    private static bool IsAnalyticalQuotient(ISymbolicExpressionTreeNode node) {
     188      return node.Symbol is AnalyticQuotient;
    169189    }
    170190
     
    243263      if (IsConstant(original) || IsVariableBase(original)) {
    244264        return (ISymbolicExpressionTreeNode)original.Clone();
     265      } else if (IsAbsolute(original)) {
     266        return SimplifyAbsolute(original);
    245267      } else if (IsAddition(original)) {
    246268        return SimplifyAddition(original);
     
    261283      } else if (IsSquareRoot(original)) {
    262284        return SimplifySquareRoot(original);
     285      } else if (IsCube(original)) {
     286        return SimplifyCube(original);
     287      } else if (IsCubeRoot(original)) {
     288        return SimplifyCubeRoot(original);
    263289      } else if (IsPower(original)) {
    264290        return SimplifyPower(original);
     
    271297      } else if (IsTangent(original)) {
    272298        return SimplifyTangent(original);
     299      } else if (IsAnalyticalQuotient(original)) {
     300        return SimplifyAnalyticalQuotient(original);
    273301      } else if (IsIfThenElse(original)) {
    274302        return SimplifyIfThenElse(original);
     
    380408    }
    381409
     410    private static ISymbolicExpressionTreeNode SimplifyAbsolute(ISymbolicExpressionTreeNode original) {
     411      return MakeAbs(GetSimplifiedTree(original.GetSubtree(0)));
     412    }
     413
    382414    private static ISymbolicExpressionTreeNode SimplifyNot(ISymbolicExpressionTreeNode original) {
    383415      return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
     
    432464      return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
    433465    }
     466    private static ISymbolicExpressionTreeNode SimplifyCube(ISymbolicExpressionTreeNode original) {
     467      return MakeCube(GetSimplifiedTree(original.GetSubtree(0)));
     468    }
     469
     470    private static ISymbolicExpressionTreeNode SimplifyCubeRoot(ISymbolicExpressionTreeNode original) {
     471      return MakeCubeRoot(GetSimplifiedTree(original.GetSubtree(0)));
     472    }
    434473
    435474    private static ISymbolicExpressionTreeNode SimplifyLog(ISymbolicExpressionTreeNode original) {
     
    443482    private static ISymbolicExpressionTreeNode SimplifyPower(ISymbolicExpressionTreeNode original) {
    444483      return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
     484    }
     485
     486    private static ISymbolicExpressionTreeNode SimplifyAnalyticalQuotient(ISymbolicExpressionTreeNode original) {
     487      return MakeAnalyticalQuotient(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
    445488    }
    446489
     
    730773      } else if (IsSquareRoot(node)) {
    731774        return node.GetSubtree(0);
     775      } else if (IsMultiplication(node)) {
     776        // sqr( x * y ) = sqr(x) * sqr(y)
     777        var mulNode = mulSymbol.CreateTreeNode();
     778        foreach (var subtree in node.Subtrees) {
     779          mulNode.AddSubtree(MakeSquare(subtree));
     780        }
     781        return mulNode;
     782      } else if (IsAbsolute(node)) {
     783        return MakeSquare(node.GetSubtree(0)); // sqr(abs(x)) = sqr(x)
     784      } else if (IsExp(node)) {
     785        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(2.0))); // sqr(exp(x)) = exp(2x)
     786      } else if (IsCube(node)) {
     787        return MakePower(node.GetSubtree(0), MakeConstant(6));
    732788      } else {
    733789        var sqrNode = sqrSymbol.CreateTreeNode();
    734790        sqrNode.AddSubtree(node);
    735791        return sqrNode;
     792      }
     793    }
     794
     795    private static ISymbolicExpressionTreeNode MakeCube(ISymbolicExpressionTreeNode node) {
     796      if (IsConstant(node)) {
     797        var constT = node as ConstantTreeNode;
     798        return MakeConstant(constT.Value * constT.Value * constT.Value);
     799      } else if (IsFactor(node)) {
     800        var factNode = node as FactorVariableTreeNode;
     801        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w * w));
     802      } else if (IsBinFactor(node)) {
     803        var binFactor = node as BinaryFactorVariableTreeNode;
     804        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight * binFactor.Weight);
     805      } else if (IsCubeRoot(node)) {
     806        return node.GetSubtree(0); // NOTE: not really accurate because cuberoot(x) with negative x is evaluated to NaN and after this simplification we evaluate as x
     807      } else if (IsExp(node)) {
     808        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(3)));
     809      } else if (IsSquare(node)) {
     810        return MakePower(node.GetSubtree(0), MakeConstant(6));
     811      } else {
     812        var cubeNode = cubeSymbol.CreateTreeNode();
     813        cubeNode.AddSubtree(node);
     814        return cubeNode;
     815      }
     816    }
     817
     818    private static ISymbolicExpressionTreeNode MakeAbs(ISymbolicExpressionTreeNode node) {
     819      if (IsConstant(node)) {
     820        var constT = node as ConstantTreeNode;
     821        return MakeConstant(Math.Abs(constT.Value));
     822      } else if (IsFactor(node)) {
     823        var factNode = node as FactorVariableTreeNode;
     824        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Abs(w)));
     825      } else if (IsBinFactor(node)) {
     826        var binFactor = node as BinaryFactorVariableTreeNode;
     827        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Abs(binFactor.Weight));
     828      } else if (IsSquare(node) || IsExp(node) || IsSquareRoot(node) || IsCubeRoot(node)) {
     829        return node; // abs(sqr(x)) = sqr(x), abs(exp(x)) = exp(x) ...
     830      } else if (IsMultiplication(node)) {
     831        var mul = mulSymbol.CreateTreeNode();
     832        foreach (var st in node.Subtrees) {
     833          mul.AddSubtree(MakeAbs(st));
     834        }
     835        return mul;
     836      } else if (IsDivision(node)) {
     837        var div = divSymbol.CreateTreeNode();
     838        foreach (var st in node.Subtrees) {
     839          div.AddSubtree(MakeAbs(st));
     840        }
     841        return div;
     842      } else {
     843        var absNode = absSymbol.CreateTreeNode();
     844        absNode.AddSubtree(node);
     845        return absNode;
     846      }
     847    }
     848
     849    // constant folding only
     850    private static ISymbolicExpressionTreeNode MakeAnalyticalQuotient(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
     851      if (IsConstant(b)) {
     852        var c = b as ConstantTreeNode;
     853        return MakeFraction(a, MakeConstant(Math.Sqrt(1.0 + c.Value * c.Value)));
     854      } else if (IsFactor(b)) {
     855        var factNode = b as FactorVariableTreeNode;
     856        return MakeFraction(a, MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(1.0 + w * w))));
     857      } else if (IsBinFactor(b)) {
     858        var binFactor = b as BinaryFactorVariableTreeNode;
     859        return MakeFraction(a, MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(1.0 + binFactor.Weight * binFactor.Weight)));
     860      } else {
     861        var aqNode = aqSymbol.CreateTreeNode();
     862        aqNode.AddSubtree(a);
     863        aqNode.AddSubtree(b);
     864        return aqNode;
    736865      }
    737866    }
     
    748877        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(binFactor.Weight));
    749878      } else if (IsSquare(node)) {
    750         return node.GetSubtree(0);
     879        return node.GetSubtree(0); // NOTE: not really accurate because sqrt(x) with negative x is evaluated to NaN and after this simplification we evaluate as x
    751880      } else {
    752881        var sqrtNode = sqrtSymbol.CreateTreeNode();
    753882        sqrtNode.AddSubtree(node);
    754883        return sqrtNode;
     884      }
     885    }
     886
     887    private static ISymbolicExpressionTreeNode MakeCubeRoot(ISymbolicExpressionTreeNode node) {
     888      if (IsConstant(node)) {
     889        var constT = node as ConstantTreeNode;
     890        return MakeConstant(Math.Pow(constT.Value, 1.0 / 3.0));
     891      } else if (IsFactor(node)) {
     892        var factNode = node as FactorVariableTreeNode;
     893        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, 1.0 / 3.0)));
     894      } else if (IsBinFactor(node)) {
     895        var binFactor = node as BinaryFactorVariableTreeNode;
     896        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(Math.Pow(binFactor.Weight, 1.0 / 3.0)));
     897      } else if (IsCube(node)) {
     898        return node.GetSubtree(0);
     899      } else {
     900        var cubeRootNode = cubeRootSymbol.CreateTreeNode();
     901        cubeRootNode.AddSubtree(node);
     902        return cubeRootNode;
    755903      }
    756904    }
     
    9271075        // a / (b1 / b2) => (a * b2) / b1
    9281076        return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
     1077      } else if (IsAnalyticalQuotient(a)) {
     1078        return MakeAnalyticalQuotient(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
    9291079      } else {
    9301080        var div = divSymbol.CreateTreeNode();
     
    11211271        // $ * 1.0 => $
    11221272        return a;
     1273      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
     1274        return MakeConstant(0);
    11231275      } else if (IsConstant(b) && IsVariableBase(a)) {
    11241276        // multiply constants into variables weights
     
    11531305        MergeVariablesAndConstantsInProduct(a);
    11541306        return a;
     1307      } else if (IsAbsolute(a) && IsAbsolute(b)) {
     1308        return MakeAbs(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)));
     1309      } else if (IsAbsolute(a) && IsConstant(b)) {
     1310        var constNode = b as ConstantTreeNode;
     1311        var posF = Math.Abs(constNode.Value);
     1312        if (constNode.Value > 0) {
     1313          return MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF)));
     1314        } else {
     1315          var mul = mulSymbol.CreateTreeNode();
     1316          mul.AddSubtree(MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF))));
     1317          mul.AddSubtree(MakeConstant(-1.0));
     1318          return mul;
     1319        }
     1320      } else if (IsAnalyticalQuotient(a)) {
     1321        return MakeAnalyticalQuotient(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
    11551322      } else {
    11561323        var mul = mulSymbol.CreateTreeNode();
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeToAutoDiffTermConverter.cs

    r15583 r16520  
    8585      diff: x => -(Math.Exp(-(x * x)) * Math.Sqrt(Math.Exp(x * x)) * x) / Math.Sqrt(2 * Math.PI));
    8686
     87    private static readonly Func<Term, UnaryFunc> abs = UnaryFunc.Factory(
     88      eval: Math.Abs,
     89      diff: x => Math.Sign(x)
     90      );
     91
    8792    #endregion
    8893
     
    213218        else return terms.Aggregate((a, b) => new AutoDiff.Product(a, 1.0 / b));
    214219      }
     220      if (node.Symbol is Absolute) {
     221        var x1 = ConvertToAutoDiff(node.GetSubtree(0));
     222        return abs(x1);
     223      }
     224      if (node.Symbol is AnalyticQuotient) {
     225        var x1 = ConvertToAutoDiff(node.GetSubtree(0));
     226        var x2 = ConvertToAutoDiff(node.GetSubtree(1));
     227        return x1 / (TermBuilder.Power(1 + x2 * x2, 0.5));
     228      }
    215229      if (node.Symbol is Logarithm) {
    216230        return AutoDiff.TermBuilder.Log(
     
    228242        return AutoDiff.TermBuilder.Power(
    229243          ConvertToAutoDiff(node.GetSubtree(0)), 0.5);
     244      }
     245      if (node.Symbol is Cube) {
     246        return AutoDiff.TermBuilder.Power(
     247          ConvertToAutoDiff(node.GetSubtree(0)), 3.0);
     248      }
     249      if (node.Symbol is CubeRoot) {
     250        return AutoDiff.TermBuilder.Power(
     251          ConvertToAutoDiff(node.GetSubtree(0)), 1.0/3.0);
    230252      }
    231253      if (node.Symbol is Sine) {
     
    301323          !(n.Symbol is Erf) &&
    302324          !(n.Symbol is Norm) &&
    303           !(n.Symbol is StartSymbol)
     325          !(n.Symbol is StartSymbol) &&
     326          !(n.Symbol is Absolute) &&
     327          !(n.Symbol is AnalyticQuotient) &&
     328          !(n.Symbol is Cube) &&
     329          !(n.Symbol is CubeRoot)
    304330        select n).Any();
    305331      return !containsUnknownSymbol;
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Formatters/InfixExpressionFormatter.cs

    r15583 r16520  
    6262      if (node.SubtreeCount > 1) {
    6363        var token = GetToken(node.Symbol);
    64         if (token == "+" || token == "-" || token == "OR" || token == "XOR") {
    65           strBuilder.Append("(");
    66           FormatRecursively(node.Subtrees.First(), strBuilder);
    67 
    68           foreach (var subtree in node.Subtrees.Skip(1)) {
    69             strBuilder.Append(" ").Append(token).Append(" ");
    70             FormatRecursively(subtree, strBuilder);
    71           }
    72           strBuilder.Append(")");
    73 
    74         } else if (token == "*" || token == "/" || token == "AND") {
     64        // operators
     65        if (token == "+" || token == "-" || token == "OR" || token == "XOR" ||
     66            token == "*" || token == "/" || token == "AND" ||
     67            token == "^") {
    7568          strBuilder.Append("(");
    7669          FormatRecursively(node.Subtrees.First(), strBuilder);
     
    184177
    185178    private string GetToken(ISymbol symbol) {
    186       var tok = InfixExpressionParser.knownSymbols.GetBySecond(symbol).SingleOrDefault();
     179      var tok = InfixExpressionParser.knownSymbols.GetBySecond(symbol).FirstOrDefault();
    187180      if (tok == null)
    188181        throw new ArgumentException(string.Format("Unknown symbol {0} found.", symbol.Name));
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Grammars/FullFunctionalExpressionGrammar.cs

    r15583 r16520  
    4848      var mul = new Multiplication();
    4949      var div = new Division();
     50      var aq = new AnalyticQuotient();
    5051      var mean = new Average();
    5152      var sin = new Sine();
     
    5354      var tan = new Tangent();
    5455      var log = new Logarithm();
     56      var abs = new Absolute();
    5557      var pow = new Power();
    5658      pow.InitialFrequency = 0.0;
    5759      var square = new Square();
    5860      square.InitialFrequency = 0.0;
     61      var cube = new Cube();
     62      cube.InitialFrequency = 0.0;
    5963      var root = new Root();
    6064      root.InitialFrequency = 0.0;
    6165      var sqrt = new SquareRoot();
    6266      sqrt.InitialFrequency = 0.0;
     67      var cubeRoot = new CubeRoot();
     68      cubeRoot.InitialFrequency = 0.0;
    6369      var airyA = new AiryA();
    6470      airyA.InitialFrequency = 0.0;
     
    123129      autoregressiveVariable.Enabled = false;
    124130
    125       var allSymbols = new List<Symbol>() { add, sub, mul, div, mean, sin, cos, tan, log, square, pow, sqrt, root, exp,
     131      var allSymbols = new List<Symbol>() { add, sub, mul, div, aq, mean, abs, sin, cos, tan, log, square, cube, pow, sqrt, cubeRoot, root, exp,
    126132        airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi, fresnelCosineIntegral, fresnelSineIntegral, gamma, hypCosineIntegral, hypSineIntegral, norm, psi, sineIntegral,
    127133        @if, gt, lt, and, or, not,xor, timeLag, integral, derivative, constant, variableSymbol, binFactorVariable, factorVariable, laggedVariable,autoregressiveVariable, variableCondition };
    128       var unaryFunctionSymbols = new List<Symbol>() { square, sqrt, sin, cos, tan, log, exp, not, timeLag, integral, derivative,
     134      var unaryFunctionSymbols = new List<Symbol>() { abs, square, sqrt, cube, cubeRoot, sin, cos, tan, log, exp, not, timeLag, integral, derivative,
    129135        airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi, fresnelCosineIntegral, fresnelSineIntegral, gamma, hypCosineIntegral, hypSineIntegral, norm, psi, sineIntegral
    130136      };
    131137
    132       var binaryFunctionSymbols = new List<Symbol>() { pow, root, gt, lt, variableCondition };
     138      var binaryFunctionSymbols = new List<Symbol>() { pow, root, gt, lt, aq, variableCondition };
    133139      var ternarySymbols = new List<Symbol>() { add, sub, mul, div, mean, and, or, xor };
    134140      var terminalSymbols = new List<Symbol>() { variableSymbol, binFactorVariable, factorVariable, constant, laggedVariable, autoregressiveVariable };
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Grammars/TypeCoherentExpressionGrammar.cs

    r15583 r16520  
    6969      var root = new Root();
    7070      var sqrt = new SquareRoot();
     71      var cube = new Cube();
     72      var cubeRoot = new CubeRoot();
    7173      var exp = new Exponential();
     74      var abs = new Absolute();
    7275
    7376      var airyA = new AiryA();
     
    8689      var psi = new Psi();
    8790      var sineIntegral = new SineIntegral();
     91      var analyticalQuotient = new AnalyticQuotient();
    8892
    8993      var @if = new IfThenElse();
     
    114118      var trigonometricSymbols = new GroupSymbol(TrigonometricFunctionsName, new List<ISymbol>() { sin, cos, tan });
    115119      var exponentialAndLogarithmicSymbols = new GroupSymbol(ExponentialFunctionsName, new List<ISymbol> { exp, log });
    116       var specialFunctions = new GroupSymbol(SpecialFunctionsName, new List<ISymbol> { airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi,
    117         fresnelCosineIntegral,fresnelSineIntegral,gamma,hypCosineIntegral,hypSineIntegral,norm, psi, sineIntegral});
     120      var specialFunctions = new GroupSymbol(SpecialFunctionsName, new List<ISymbol> { abs, airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi,
     121        fresnelCosineIntegral,fresnelSineIntegral,gamma,hypCosineIntegral,hypSineIntegral,norm, psi, sineIntegral, analyticalQuotient});
    118122      var terminalSymbols = new GroupSymbol(TerminalsName, new List<ISymbol> { constant, variableSymbol, binFactorVariable, factorVariable });
    119123      var realValuedSymbols = new GroupSymbol(RealValuedSymbolsName, new List<ISymbol>() { arithmeticSymbols, trigonometricSymbols, exponentialAndLogarithmicSymbols, specialFunctions, terminalSymbols });
    120124
    121       var powerSymbols = new GroupSymbol(PowerFunctionsName, new List<ISymbol> { square, pow, sqrt, root });
     125      var powerSymbols = new GroupSymbol(PowerFunctionsName, new List<ISymbol> { square, pow, sqrt, root, cube, cubeRoot });
    122126
    123127      var conditionSymbols = new GroupSymbol(ConditionsName, new List<ISymbol> { @if, variableCondition });
     
    140144      SetSubtreeCount(root, 2, 2);
    141145      SetSubtreeCount(square, 1, 1);
     146      SetSubtreeCount(cube, 1, 1);
    142147      SetSubtreeCount(sqrt, 1, 1);
     148      SetSubtreeCount(cubeRoot, 1, 1);
    143149      SetSubtreeCount(exponentialAndLogarithmicSymbols, 1, 1);
    144       SetSubtreeCount(specialFunctions, 1, 1);
     150      foreach(var sy in specialFunctions.Symbols.Except(new[] { analyticalQuotient})) {
     151        SetSubtreeCount(sy, 1, 1);
     152      }
     153      SetSubtreeCount(analyticalQuotient, 2, 2);
     154
    145155      SetSubtreeCount(terminalSymbols, 0, 0);
    146156
     
    231241    public void ConfigureAsDefaultRegressionGrammar() {
    232242      Symbols.First(s => s is Average).Enabled = false;
     243      Symbols.First(s => s is Absolute).Enabled = false;
    233244      Symbols.First(s => s.Name == TrigonometricFunctionsName).Enabled = false;
    234245      Symbols.First(s => s.Name == PowerFunctionsName).Enabled = false;
     
    242253      Symbols.First(s => s is VariableCondition).Enabled = false;
    243254      Symbols.First(s => s is Xor).Enabled = false;
     255      Symbols.First(s => s is Absolute).Enabled = false;
    244256      Symbols.First(s => s.Name == TrigonometricFunctionsName).Enabled = false;
    245257      Symbols.First(s => s.Name == ExponentialFunctionsName).Enabled = false;
     
    251263    public void ConfigureAsDefaultTimeSeriesPrognosisGrammar() {
    252264      Symbols.First(s => s is Average).Enabled = false;
     265      Symbols.First(s => s is Absolute).Enabled = false;
    253266      Symbols.First(s => s.Name == TrigonometricFunctionsName).Enabled = false;
    254267      Symbols.First(s => s.Name == PowerFunctionsName).Enabled = false;
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r15902 r16520  
    107107      <Private>False</Private>
    108108    </Reference>
     109    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1, Version=0.0.0.1, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     110      <SpecificVersion>False</SpecificVersion>
     111      <HintPath>..\..\bin\HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1.dll</HintPath>
     112      <Private>False</Private>
     113    </Reference>
    109114    <Reference Include="System" />
    110115    <Reference Include="System.Core">
     
    123128  <ItemGroup>
    124129    <Compile Include="Analyzers\SymbolicDataAnalysisBottomUpDiversityAnalyzer.cs" />
     130    <Compile Include="Analyzers\SymbolicDataAnalysisBuildingBlockAnalyzer.cs" />
    125131    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
    126132    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />
     
    139145    <Compile Include="Converters\LinearModelToTreeConverter.cs" />
    140146    <Compile Include="Converters\TreeSimplifier.cs" />
     147    <Compile Include="Converters\DerivativeCalculator.cs" />
    141148    <Compile Include="Converters\TreeToAutoDiffTermConverter.cs" />
     149    <Compile Include="Crossovers\SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs" />
    142150    <Compile Include="Formatters\InfixExpressionFormatter.cs" />
    143151    <Compile Include="Formatters\TSQLExpressionFormatter.cs" />
    144152    <Compile Include="Formatters\SymbolicDataAnalysisExpressionMathematicaFormatter.cs" />
    145153    <Compile Include="Formatters\SymbolicDataAnalysisExpressionCSharpFormatter.cs" />
     154    <Compile Include="Hashing\HashExtensions.cs" />
     155    <Compile Include="Hashing\HashUtil.cs" />
     156    <Compile Include="Hashing\SymbolicExpressionTreeHash.cs" />
    146157    <Compile Include="Importer\InfixExpressionParser.cs" />
    147158    <Compile Include="Importer\SymbolicExpressionImporter.cs" />
     
    150161    <Compile Include="Interfaces\IVariableTreeNode.cs" />
    151162    <Compile Include="Interfaces\IVariableSymbol.cs" />
     163    <Compile Include="Interpreter\BatchInstruction.cs" />
     164    <Compile Include="Interpreter\BatchOperations.cs" />
     165    <Compile Include="Interpreter\IntervalInterpreter.cs" />
    152166    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs" />
     167    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs" />
     168    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs" />
    153169    <Compile Include="SymbolicDataAnalysisExpressionTreeSimplificationOperator.cs" />
    154170    <Compile Include="SymbolicDataAnalysisModelComplexityCalculator.cs" />
     
    198214    <Compile Include="SymbolicDataAnalysisSolutionImpactValuesCalculator.cs" />
    199215    <Compile Include="Symbols\Addition.cs" />
     216    <Compile Include="Symbols\AnalyticQuotient.cs" />
    200217    <Compile Include="Symbols\And.cs" />
    201218    <Compile Include="Symbols\AutoregressiveVariable.cs" />
     
    208225    <Compile Include="Symbols\BinaryFactorVariable.cs" />
    209226    <Compile Include="Symbols\BinaryFactorVariableTreeNode.cs" />
     227    <Compile Include="Symbols\Cube.cs" />
    210228    <Compile Include="Symbols\FactorVariableTreeNode.cs" />
    211229    <Compile Include="Symbols\FactorVariable.cs" />
     230    <Compile Include="Symbols\Absolute.cs" />
     231    <Compile Include="Symbols\CubeRoot.cs" />
    212232    <Compile Include="Symbols\VariableBase.cs" />
    213233    <Compile Include="Symbols\VariableTreeNodeBase.cs" />
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/InfixExpressionParser.cs

    r15583 r16520  
    4242  /// Expr          = ['-' | '+'] Term { '+' Term | '-' Term }
    4343  /// Term          = Fact { '*' Fact | '/' Fact }
    44   /// Fact          = '(' Expr ')'
    45   ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
    46   ///                 | funcId '(' ArgList ')'
    47   ///                 | VarExpr | number
     44  /// Fact          = SimpleFact [ '^' SimpleFact ]
     45  /// SimpleFact    = '(' Expr ')'
     46  ///                 | '{' Expr '}'
     47  ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')
     48  ///                 | funcId '(' ArgList ')'
     49  ///                 | VarExpr
     50  ///                 | number
    4851  /// ArgList       = Expr { ',' Expr }
    4952  /// VarExpr       = varId OptFactorPart
     
    9598        { "*", new Multiplication()},
    9699        { "-", new Subtraction()},
     100        { "^", new Power() },
     101        { "ABS", new Absolute() },
    97102        { "EXP", new Exponential()},
    98103        { "LOG", new Logarithm()},
    99         { "POW", new Power()},
     104        { "POW", new Power() },
    100105        { "ROOT", new Root()},
    101106        { "SQR", new Square() },
    102107        { "SQRT", new SquareRoot() },
     108        { "CUBE", new Cube() },
     109        { "CUBEROOT", new CubeRoot() },
    103110        { "SIN",new Sine()},
    104111        { "COS", new Cosine()},
     
    119126        { "DAWSON", new Dawson()},
    120127        { "EXPINT", new ExponentialIntegralEi()},
     128        { "AQ", new AnalyticQuotient() },
    121129        { "MEAN", new Average()},
    122130        { "IF", new IfThenElse()},
     
    167175            && str[pos] != '*'
    168176            && str[pos] != '/'
     177            && str[pos] != '^'
    169178            && str[pos] != ')'
    170179            && str[pos] != ']'
     180            && str[pos] != '}'
    171181            && str[pos] != ',') {
    172182            sb.Append(str[pos]);
     
    227237          pos++;
    228238          yield return new Token { TokenType = TokenType.Operator, strVal = "*" };
     239        } else if (str[pos] == '^') {
     240          pos++;
     241          yield return new Token { TokenType = TokenType.Operator, strVal = "^" };
    229242        } else if (str[pos] == '(') {
    230243          pos++;
     
    239252          pos++;
    240253          yield return new Token { TokenType = TokenType.RightBracket, strVal = "]" };
     254        } else if (str[pos] == '{') {
     255          pos++;
     256          yield return new Token { TokenType = TokenType.LeftPar, strVal = "{" };
     257        } else if (str[pos] == '}') {
     258          pos++;
     259          yield return new Token { TokenType = TokenType.RightPar, strVal = "}" };
    241260        } else if (str[pos] == '=') {
    242261          pos++;
     
    360379    }
    361380
    362     /// Fact          = '(' Expr ')'
    363     ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
    364     ///                 | funcId '(' ArgList ')'
    365     ///                 | VarExpr | number
     381    // Fact = SimpleFact ['^' SimpleFact]
     382    private ISymbolicExpressionTreeNode ParseFact(Queue<Token> tokens) {
     383      var expr = ParseSimpleFact(tokens);
     384      var next = tokens.Peek();
     385      if (next.TokenType == TokenType.Operator && next.strVal == "^") {
     386        tokens.Dequeue(); // skip;
     387
     388        var p = GetSymbol("^").CreateTreeNode();
     389        p.AddSubtree(expr);
     390        p.AddSubtree(ParseSimpleFact(tokens));
     391        expr = p;
     392      }
     393      return expr;
     394    }
     395
     396
     397    /// SimpleFact   = '(' Expr ')'
     398    ///                 | '{' Expr '}'
     399    ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
     400    ///                 | funcId '(' ArgList ')
     401    ///                 | VarExpr
     402    ///                 | number
    366403    /// ArgList       = Expr { ',' Expr }
    367404    /// VarExpr       = varId OptFactorPart
     
    370407    /// varVal        =  ident | ' ident ' | " ident "
    371408    /// ident         =  '_' | letter { '_' | letter | digit }
    372     private ISymbolicExpressionTreeNode ParseFact(Queue<Token> tokens) {
     409    private ISymbolicExpressionTreeNode ParseSimpleFact(Queue<Token> tokens) {
    373410      var next = tokens.Peek();
    374411      if (next.TokenType == TokenType.LeftPar) {
    375         tokens.Dequeue();
     412        var initPar = tokens.Dequeue(); // match par type
    376413        var expr = ParseExpr(tokens);
    377414        var rPar = tokens.Dequeue();
    378415        if (rPar.TokenType != TokenType.RightPar)
    379           throw new ArgumentException("expected )");
     416          throw new ArgumentException("expected closing parenthesis");
     417        if (initPar.strVal == "(" && rPar.strVal == "}")
     418          throw new ArgumentException("expected closing )");
     419        if (initPar.strVal == "{" && rPar.strVal == ")")
     420          throw new ArgumentException("expected closing }");
    380421        return expr;
    381422      } else if (next.TokenType == TokenType.Identifier) {
     
    424465          if (rPar.TokenType != TokenType.RightPar)
    425466            throw new ArgumentException("expected )");
     467
    426468
    427469          return funcNode;
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/SymbolicExpressionImporter.cs

    r15583 r16520  
    4141        {"*", new Multiplication()},
    4242        {"-", new Subtraction()},
     43        {"ABS", new Absolute() },
    4344        {"EXP", new Exponential()},
    4445        {"LOG", new Logarithm()},
     
    4748        {"SQR", new Square()},
    4849        {"SQRT", new SquareRoot()},
     50        {"CUBE", new Cube()},
     51        {"CUBEROOT", new CubeRoot()},
    4952        {"SIN",new Sine()},
    5053        {"COS", new Cosine()},
     
    6568        {"DAWSON", new Dawson()},
    6669        {"EXPINT", new ExponentialIntegralEi()},
     70        {"AQ", new AnalyticQuotient() },
    6771        {"MEAN", new Average()},
    6872        {"IF", new IfThenElse()},
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/OpCodes.cs

    r15583 r16520  
    4646    public const byte OR = 14;
    4747    public const byte NOT = 15;
    48     public const byte XOR = 45;
    4948
    5049
     
    8382    public const byte Erf = 43;
    8483    public const byte Bessel = 44;
     84    public const byte XOR = 45;
    8585    public const byte FactorVariable = 46;
    8686    public const byte BinaryFactorVariable = 47;
     87    public const byte Absolute = 48;
     88    public const byte AnalyticQuotient = 49;
     89    public const byte Cube = 50;
     90    public const byte CubeRoot = 51;
    8791
    8892
     
    113117      { typeof(Power),OpCodes.Power},
    114118      { typeof(Root),OpCodes.Root},
    115       { typeof(TimeLag), OpCodes.TimeLag}, 
     119      { typeof(TimeLag), OpCodes.TimeLag},
    116120      { typeof(Integral), OpCodes.Integral},
    117121      { typeof(Derivative), OpCodes.Derivative},
     
    135139      { typeof(Bessel), OpCodes.Bessel},
    136140      { typeof(FactorVariable), OpCodes.FactorVariable },
    137       { typeof(BinaryFactorVariable), OpCodes.BinaryFactorVariable }
     141      { typeof(BinaryFactorVariable), OpCodes.BinaryFactorVariable },
     142      { typeof(Absolute), OpCodes.Absolute },
     143      { typeof(AnalyticQuotient), OpCodes.AnalyticQuotient },
     144      { typeof(Cube), OpCodes.Cube },
     145      { typeof(CubeRoot), OpCodes.CubeRoot }
    138146    };
    139147
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs

    r15583 r16520  
    4141
    4242    #region method info for the commonly called functions
     43    private static readonly MethodInfo Abs = typeof(Math).GetMethod("Abs", new[] { typeof(double) });
    4344    private static readonly MethodInfo Sin = typeof(Math).GetMethod("Sin", new[] { typeof(double) });
    4445    private static readonly MethodInfo Cos = typeof(Math).GetMethod("Cos", new[] { typeof(double) });
     
    207208            return Expression.Divide(result, Expression.Constant((double)node.SubtreeCount));
    208209          }
     210        case OpCodes.Absolute: {
     211            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
     212            return Expression.Call(Abs, arg);
     213          }
    209214        case OpCodes.Cos: {
    210215            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
     
    222227            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
    223228            return Expression.Power(arg, Expression.Constant(2.0));
     229          }
     230        case OpCodes.Cube: {
     231            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
     232            return Expression.Power(arg, Expression.Constant(3.0));
    224233          }
    225234        case OpCodes.Power: {
     
    231240            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
    232241            return Expression.Call(Sqrt, arg);
     242          }
     243        case OpCodes.CubeRoot: {
     244            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
     245            return Expression.Power(arg, Expression.Constant(1.0 / 3.0));
    233246          }
    234247        case OpCodes.Root: {
     
    493506                Expression.Assign(result, Expression.Call(Bessel, arg))),
    494507              result);
     508          }
     509        case OpCodes.AnalyticQuotient: {
     510            var x1 = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
     511            var x2 = MakeExpr(node.GetSubtree(1), variableIndices, row, columns);
     512            return Expression.Divide(x1,
     513              Expression.Call(Sqrt,
     514              Expression.Add(
     515                Expression.Constant(1.0),
     516                Expression.Multiply(x2, x2))));
    495517          }
    496518        case OpCodes.IfThenElse: {
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeILEmittingInterpreter.cs

    r15583 r16520  
    5050    private static MethodInfo round = typeof(Math).GetMethod("Round", new Type[] { typeof(double) });
    5151    private static MethodInfo sqrt = typeof(Math).GetMethod("Sqrt", new Type[] { typeof(double) });
     52    private static MethodInfo abs = typeof(Math).GetMethod("Abs", new Type[] { typeof(double) });
    5253
    5354    private static MethodInfo airyA = thisType.GetMethod("AiryA", new Type[] { typeof(double) });
     
    264265            return;
    265266          }
     267        case OpCodes.Absolute: {
     268            CompileInstructions(il, state, ds);
     269            il.Emit(System.Reflection.Emit.OpCodes.Call, abs);
     270            return;
     271          }
    266272        case OpCodes.Cos: {
    267273            CompileInstructions(il, state, ds);
     
    311317            return;
    312318          }
     319        case OpCodes.Cube: {
     320            CompileInstructions(il, state, ds);
     321            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, 3.0);
     322            il.Emit(System.Reflection.Emit.OpCodes.Call, power);
     323            return;
     324          }
    313325        case OpCodes.SquareRoot: {
    314326            CompileInstructions(il, state, ds);
     
    316328            return;
    317329          }
     330        case OpCodes.CubeRoot: {
     331            CompileInstructions(il, state, ds);
     332            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, 1.0 / 3.0);
     333            il.Emit(System.Reflection.Emit.OpCodes.Call, power);
     334            return;
     335          }
    318336        case OpCodes.AiryA: {
    319337            CompileInstructions(il, state, ds);
     
    389407            CompileInstructions(il, state, ds);
    390408            il.Emit(System.Reflection.Emit.OpCodes.Call, sinIntegral);
     409            return;
     410          }
     411        case OpCodes.AnalyticQuotient: {
     412            CompileInstructions(il, state, ds); // x1
     413            CompileInstructions(il, state, ds); // x2
     414
     415            il.Emit(System.Reflection.Emit.OpCodes.Dup);
     416            il.Emit(System.Reflection.Emit.OpCodes.Mul); // x2*x2
     417            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, 1.0);
     418            il.Emit(System.Reflection.Emit.OpCodes.Mul); // 1+x2*x2
     419            il.Emit(System.Reflection.Emit.OpCodes.Call, sqrt);
     420            il.Emit(System.Reflection.Emit.OpCodes.Div);
    391421            return;
    392422          }
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeInterpreter.cs

    r15583 r16520  
    203203            return sum / currentInstr.nArguments;
    204204          }
     205        case OpCodes.Absolute: {
     206            return Math.Abs(Evaluate(dataset, ref row, state));
     207          }
    205208        case OpCodes.Cos: {
    206209            return Math.Cos(Evaluate(dataset, ref row, state));
     
    214217        case OpCodes.Square: {
    215218            return Math.Pow(Evaluate(dataset, ref row, state), 2);
     219          }
     220        case OpCodes.Cube: {
     221            return Math.Pow(Evaluate(dataset, ref row, state), 3);
    216222          }
    217223        case OpCodes.Power: {
     
    223229            return Math.Sqrt(Evaluate(dataset, ref row, state));
    224230          }
     231        case OpCodes.CubeRoot: {
     232            return Math.Pow(Evaluate(dataset, ref row, state), 1.0 / 3.0);
     233          }
    225234        case OpCodes.Root: {
    226235            double x = Evaluate(dataset, ref row, state);
     
    340349            if (double.IsNaN(x)) return double.NaN;
    341350            else return alglib.besseli0(x);
     351          }
     352
     353        case OpCodes.AnalyticQuotient: {
     354            var x1 = Evaluate(dataset, ref row, state);
     355            var x2 = Evaluate(dataset, ref row, state);
     356            return x1 / Math.Pow(1 + x2 * x2, 0.5);
    342357          }
    343358        case OpCodes.IfThenElse: {
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeLinearInterpreter.cs

    r15583 r16520  
    215215          if (instr.nArguments == 1) p = 1.0 / p;
    216216          instr.value = p;
     217        } else if (instr.opCode == OpCodes.AnalyticQuotient) {
     218          var x1 = code[instr.childIndex].value;
     219          var x2 = code[instr.childIndex + 1].value;
     220          instr.value = x1 / Math.Sqrt(1 + x2 * x2);
    217221        } else if (instr.opCode == OpCodes.Average) {
    218222          double s = code[instr.childIndex].value;
     
    221225          }
    222226          instr.value = s / instr.nArguments;
     227        } else if (instr.opCode == OpCodes.Absolute) {
     228          instr.value = Math.Abs(code[instr.childIndex].value);
    223229        } else if (instr.opCode == OpCodes.Cos) {
    224230          instr.value = Math.Cos(code[instr.childIndex].value);
     
    229235        } else if (instr.opCode == OpCodes.Square) {
    230236          instr.value = Math.Pow(code[instr.childIndex].value, 2);
     237        } else if (instr.opCode == OpCodes.Cube) {
     238          instr.value = Math.Pow(code[instr.childIndex].value, 3);
    231239        } else if (instr.opCode == OpCodes.Power) {
    232240          double x = code[instr.childIndex].value;
     
    235243        } else if (instr.opCode == OpCodes.SquareRoot) {
    236244          instr.value = Math.Sqrt(code[instr.childIndex].value);
     245        } else if (instr.opCode == OpCodes.CubeRoot) {
     246          instr.value = Math.Pow(code[instr.childIndex].value, 1.0 / 3.0);
    237247        } else if (instr.opCode == OpCodes.Root) {
    238248          double x = code[instr.childIndex].value;
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Plugin.cs.frame

    r15589 r16520  
    3737  [PluginDependency("HeuristicLab.Data", "3.3")]
    3838  [PluginDependency("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding", "3.4")]
     39  [PluginDependency("HeuristicLab.NativeInterpreter", "0.1")]
    3940  [PluginDependency("HeuristicLab.Operators", "3.3")]
    4041  [PluginDependency("HeuristicLab.Optimization", "3.3")]
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisModel.cs

    r15583 r16520  
    3434  /// </summary>
    3535  [StorableClass]
    36   public abstract class SymbolicDataAnalysisModel : NamedItem, ISymbolicDataAnalysisModel {
     36  public abstract class SymbolicDataAnalysisModel : DataAnalysisModel, ISymbolicDataAnalysisModel {
    3737    public static new Image StaticItemImage {
    3838      get { return HeuristicLab.Common.Resources.VSImageLibrary.Function; }
     
    5959    }
    6060
    61     public IEnumerable<string> VariablesUsedForPrediction {
     61    public override IEnumerable<string> VariablesUsedForPrediction {
    6262      get {
    6363        var variables =
     
    118118      ConstantTreeNode alphaTreeNode = null;
    119119      ConstantTreeNode betaTreeNode = null;
    120       // check if model has been scaled previously by analyzing the structure of the tree
     120      // check if model has a structure that can be re-used for scaling
    121121      var startNode = SymbolicExpressionTree.Root.GetSubtree(0);
    122       if (startNode.GetSubtree(0).Symbol is Addition) {
    123         var addNode = startNode.GetSubtree(0);
    124         if (addNode.SubtreeCount == 2 && addNode.GetSubtree(0).Symbol is Multiplication && addNode.GetSubtree(1).Symbol is Constant) {
    125           alphaTreeNode = addNode.GetSubtree(1) as ConstantTreeNode;
    126           var mulNode = addNode.GetSubtree(0);
    127           if (mulNode.SubtreeCount == 2 && mulNode.GetSubtree(1).Symbol is Constant) {
    128             betaTreeNode = mulNode.GetSubtree(1) as ConstantTreeNode;
    129           }
     122      var addNode = startNode.GetSubtree(0);
     123      if (addNode.Symbol is Addition && addNode.SubtreeCount == 2) {
     124        alphaTreeNode = (ConstantTreeNode)addNode.Subtrees.LastOrDefault(n => n is ConstantTreeNode);
     125        var mulNode = addNode.Subtrees.FirstOrDefault(n => n.Symbol is Multiplication);
     126        if (mulNode != null) {
     127          betaTreeNode = (ConstantTreeNode)mulNode.Subtrees.LastOrDefault(n => n is ConstantTreeNode);
    130128        }
    131129      }
  • branches/2947_ConfigurableIndexedDataTable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs

    r15583 r16520  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Diagnostics;
    2524using System.Globalization;
    2625using System.Linq;
     
    3130using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3231
     32using NodeMap = System.Collections.Generic.Dictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;
     33
    3334namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    3435  [StorableClass]
     
    4041    protected override bool IsCommutative { get { return true; } }
    4142
     43    public bool MatchConstantValues { get; set; }
     44    public bool MatchVariableWeights { get; set; }
     45
    4246    [StorableConstructor]
    4347    protected SymbolicExpressionTreeBottomUpSimilarityCalculator(bool deserializing)
     
    5357    }
    5458
     59    #region static methods
     60    private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) {
     61      return tree.Root.GetSubtree(0).GetSubtree(0);
     62    }
     63
     64    public static double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
     65      return CalculateSimilarity(ActualRoot(t1), ActualRoot(t2), strict);
     66    }
     67
     68    public static double CalculateSimilarity(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
     69      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
     70      return CalculateSimilarity(n1, n2, strict);
     71    }
     72
     73    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
     74      return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2), strict);
     75    }
     76
     77    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
     78      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
     79      return calculator.ComputeBottomUpMapping(n1, n2);
     80    }
     81    #endregion
     82
    5583    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
    56       if (t1 == t2)
     84      return CalculateSimilarity(t1, t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map);
     85    }
     86
     87    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out NodeMap map) {
     88      if (t1 == t2) {
     89        map = null;
    5790        return 1;
    58 
    59       var map = ComputeBottomUpMapping(t1.Root, t2.Root);
    60       return 2.0 * map.Count / (t1.Length + t2.Length);
     91      }
     92      map = ComputeBottomUpMapping(t1, t2);
     93      return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees
    6194    }
    6295
     
    78111    }
    79112
     113    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     114      return ComputeBottomUpMapping(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0));
     115    }
     116
    80117    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
    81       var comparer = new SymbolicExpressionTreeNodeComparer(); // use a node comparer because it's faster than calling node.ToString() (strings are expensive) and comparing strings
    82118      var compactedGraph = Compact(n1, n2);
    83119
    84       var forwardMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
    85       var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
    86 
    87       // visit nodes in order of decreasing height to ensure correct mapping
    88       var nodes1 = n1.IterateNodesPrefix().OrderByDescending(x => x.GetDepth()).ToList();
    89       var nodes2 = n2.IterateNodesPrefix().ToList();
    90       for (int i = 0; i < nodes1.Count; ++i) {
    91         var v = nodes1[i];
    92         if (forwardMap.ContainsKey(v))
     120      IEnumerable<ISymbolicExpressionTreeNode> Subtrees(ISymbolicExpressionTreeNode node, bool commutative) {
     121        var subtrees = node.IterateNodesPrefix();
     122        return commutative ? subtrees.OrderBy(x => compactedGraph[x].Hash) : subtrees;
     123      }
     124
     125      var nodes1 = n1.IterateNodesPostfix().OrderByDescending(x => x.GetLength()); // by descending length so that largest subtrees are mapped first
     126      var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPostfix();
     127
     128      var forward = new NodeMap();
     129      var reverse = new NodeMap();
     130
     131      foreach (ISymbolicExpressionTreeNode v in nodes1) {
     132        if (forward.ContainsKey(v))
    93133          continue;
     134
    94135        var kv = compactedGraph[v];
    95         ISymbolicExpressionTreeNode w = null;
    96         for (int j = 0; j < nodes2.Count; ++j) {
    97           var t = nodes2[j];
    98           if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
     136        var commutative = v.SubtreeCount > 1 && commutativeSymbols.Contains(kv.Label);
     137
     138        foreach (ISymbolicExpressionTreeNode w in nodes2) {
     139          if (w.GetLength() != kv.Length || w.GetDepth() != kv.Depth || reverse.ContainsKey(w) || compactedGraph[w] != kv)
    99140            continue;
    100           w = t;
     141
     142          // map one whole subtree to the other
     143          foreach (var t in Subtrees(v, commutative).Zip(Subtrees(w, commutative), Tuple.Create)) {
     144            forward[t.Item1] = t.Item2;
     145            reverse[t.Item2] = t.Item1;
     146          }
     147
    101148          break;
    102149        }
    103         if (w == null) continue;
    104 
    105         // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly
    106         // (as in the paper) because the trees are unordered (subtree order might differ). the solution is
    107         // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!)
    108         // while iterating over the two subtrees
    109         var vv = IterateBreadthOrdered(v, comparer).ToList();
    110         var ww = IterateBreadthOrdered(w, comparer).ToList();
    111         int len = Math.Min(vv.Count, ww.Count);
    112         for (int j = 0; j < len; ++j) {
    113           var s = vv[j];
    114           var t = ww[j];
    115           Debug.Assert(!reverseMap.ContainsKey(t));
    116 
    117           forwardMap[s] = t;
    118           reverseMap[t] = s;
    119         }
    120       }
    121 
    122       return forwardMap;
     150      }
     151
     152      return forward;
    123153    }
    124154
     
    132162      var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
    133163      var labelMap = new Dictionary<string, GraphNode>(); // L
    134       var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
    135164
    136165      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
    137       var list = new List<GraphNode>();
    138       var queue = new Queue<ISymbolicExpressionTreeNode>();
    139 
    140       foreach (var n in nodes) {
    141         if (n.SubtreeCount == 0) {
    142           var label = GetLabel(n);
     166      var graph = new List<GraphNode>();
     167
     168      IEnumerable<GraphNode> Subtrees(GraphNode g, bool commutative) {
     169        var subtrees = g.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
     170        return commutative ? subtrees.OrderBy(x => x.Hash) : subtrees;
     171      }
     172
     173      foreach (var node in nodes) {
     174        var label = GetLabel(node);
     175
     176        if (node.SubtreeCount == 0) {
    143177          if (!labelMap.ContainsKey(label)) {
    144             var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
    145             labelMap[z.Label] = z;
    146           }
    147           nodeMap[n] = labelMap[label];
    148           queue.Enqueue(n);
     178            labelMap[label] = new GraphNode(node, label);
     179          }
     180          nodeMap[node] = labelMap[label];
    149181        } else {
    150           childrenCount[n] = n.SubtreeCount;
    151         }
    152       }
    153       while (queue.Any()) {
    154         var n = queue.Dequeue();
    155         if (n.SubtreeCount > 0) {
     182          var v = new GraphNode(node, label);
    156183          bool found = false;
    157           var label = n.Symbol.Name;
    158           var depth = n.GetDepth();
    159 
    160           bool sort = n.SubtreeCount > 1 && commutativeSymbols.Contains(label);
    161           var nSubtrees = n.Subtrees.Select(x => nodeMap[x]).ToList();
    162           if (sort) nSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    163 
    164           for (int i = list.Count - 1; i >= 0; --i) {
    165             var w = list[i];
    166             if (!(n.SubtreeCount == w.SubtreeCount && label == w.Label && depth == w.Depth))
     184          var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label);
     185
     186          var vv = Subtrees(v, commutative);
     187
     188          foreach (var w in graph) {
     189            if (v.Depth != w.Depth || v.SubtreeCount != w.SubtreeCount || v.Length != w.Length || v.Label != w.Label) {
    167190              continue;
    168 
    169             // sort V and W when the symbol is commutative because we are dealing with unordered trees
    170             var m = w.SymbolicExpressionTreeNode;
    171             var mSubtrees = m.Subtrees.Select(x => nodeMap[x]).ToList();
    172             if (sort) mSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    173 
    174             found = nSubtrees.SequenceEqual(mSubtrees);
     191            }
     192
     193            var ww = Subtrees(w, commutative);
     194            found = vv.SequenceEqual(ww);
     195
    175196            if (found) {
    176               nodeMap[n] = w;
     197              nodeMap[node] = w;
    177198              break;
    178199            }
    179200          }
    180 
    181201          if (!found) {
    182             var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth };
    183             list.Add(w);
    184             nodeMap[n] = w;
     202            nodeMap[node] = v;
     203            graph.Add(v);
    185204          }
    186205        }
    187 
    188         if (n == n1 || n == n2)
    189           continue;
    190 
    191         var p = n.Parent;
    192         if (p == null)
    193           continue;
    194 
    195         childrenCount[p]--;
    196 
    197         if (childrenCount[p] == 0)
    198           queue.Enqueue(p);
    199       }
    200 
     206      }
    201207      return nodeMap;
    202208    }
    203209
    204     private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) {
    205       var list = new List<ISymbolicExpressionTreeNode> { node };
    206       int i = 0;
    207       while (i < list.Count) {
    208         var n = list[i];
    209         if (n.SubtreeCount > 0) {
    210           var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees;
    211           list.AddRange(subtrees);
    212         }
    213         i++;
    214       }
    215       return list;
    216     }
    217 
    218     private static string GetLabel(ISymbolicExpressionTreeNode node) {
     210    private string GetLabel(ISymbolicExpressionTreeNode node) {
    219211      if (node.SubtreeCount > 0)
    220212        return node.Symbol.Name;
    221213
    222       var constant = node as ConstantTreeNode;
    223       if (constant != null)
    224         return constant.Value.ToString(CultureInfo.InvariantCulture);
    225 
    226       var variable = node as VariableTreeNode;
    227       if (variable != null)
    228         return variable.Weight + variable.VariableName;
     214      if (node is ConstantTreeNode constant)
     215        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
     216
     217      if (node is VariableTreeNode variable)
     218        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
    229219
    230220      return node.ToString();
     
    232222
    233223    private class GraphNode {
    234       public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
    235       public string Label;
    236       public int Depth;
     224      private GraphNode() { }
     225
     226      public GraphNode(ISymbolicExpressionTreeNode node, string label) {
     227        SymbolicExpressionTreeNode = node;
     228        Label = label;
     229        Hash = GetHashCode();
     230        Depth = node.GetDepth();
     231        Length = node.GetLength();
     232      }
     233
     234      public int Hash { get; }
     235      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; }
     236      public string Label { get; }
     237      public int Depth { get; }
    237238      public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
     239      public int Length { get; }
    238240    }
    239241  }
Note: See TracChangeset for help on using the changeset viewer.