1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2017 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 |
|
---|
22 | using System;
|
---|
23 | using System.Collections.Generic;
|
---|
24 | using System.Linq;
|
---|
25 | using HeuristicLab.Common;
|
---|
26 |
|
---|
27 | namespace HeuristicLab.Algorithms.DataAnalysis {
|
---|
28 | /// <summary>
|
---|
29 | /// Helper class for incremental impurity calculation.
|
---|
30 | /// Used while moving a potential Split along the ordered training Instances
|
---|
31 | /// </summary>
|
---|
32 | internal class OrderImpurityCalculator : IImpurityCalculator {
|
---|
33 | #region Properties
|
---|
34 | private double SqSumLeft { get; set; }
|
---|
35 | private double SqSumRight { get; set; }
|
---|
36 | private double VarLeft { get; set; }
|
---|
37 | private double VarRight { get; set; }
|
---|
38 | private double Order { get; set; }
|
---|
39 | private double VarTotal { get; set; }
|
---|
40 | private int NoInstances { get; set; }
|
---|
41 |
|
---|
42 | private double NoLeft { get; set; }
|
---|
43 | private double NoRight { get; set; }
|
---|
44 | private double SumLeft { get; set; }
|
---|
45 | private double SumRight { get; set; }
|
---|
46 | public double Impurity { get; private set; }
|
---|
47 | #endregion
|
---|
48 |
|
---|
49 | #region Constructors
|
---|
50 | public OrderImpurityCalculator(int partition, IReadOnlyCollection<double> data, double order) {
|
---|
51 | var values = data;
|
---|
52 | NoInstances = data.Count;
|
---|
53 | VarTotal = values.VariancePop();
|
---|
54 |
|
---|
55 | values = data.Take(partition).ToArray();
|
---|
56 | NoLeft = partition;
|
---|
57 | SumLeft = values.Sum();
|
---|
58 | SqSumLeft = values.Sum(x => x * x);
|
---|
59 |
|
---|
60 | values = data.Skip(partition).ToArray();
|
---|
61 | NoRight = NoInstances - NoLeft;
|
---|
62 | SumRight = values.Sum();
|
---|
63 | SqSumRight = values.Sum(x => x * x);
|
---|
64 |
|
---|
65 | Order = order;
|
---|
66 | Increment(0.0, IncrementType.None);
|
---|
67 | }
|
---|
68 | #endregion
|
---|
69 |
|
---|
70 | #region IImpurityCalculator
|
---|
71 | public void Increment(double value, IncrementType type) {
|
---|
72 | double y, yl, yr;
|
---|
73 | var valSq = value * value;
|
---|
74 |
|
---|
75 | switch (type) {
|
---|
76 | case IncrementType.Left:
|
---|
77 | NoLeft++;
|
---|
78 | NoRight--;
|
---|
79 | SumLeft += value;
|
---|
80 | SumRight -= value;
|
---|
81 | SqSumLeft += valSq;
|
---|
82 | SqSumRight -= valSq;
|
---|
83 | break;
|
---|
84 | case IncrementType.Right:
|
---|
85 | NoLeft--;
|
---|
86 | NoRight++;
|
---|
87 | SumLeft -= value;
|
---|
88 | SumRight += value;
|
---|
89 | SqSumLeft -= valSq;
|
---|
90 | SqSumRight += valSq;
|
---|
91 | break;
|
---|
92 | case IncrementType.None:
|
---|
93 | break;
|
---|
94 | default:
|
---|
95 | throw new ArgumentOutOfRangeException(type.ToString(), type, null);
|
---|
96 | }
|
---|
97 |
|
---|
98 | VarLeft = NoLeft <= 0 ? 0 : Math.Abs(NoLeft * SqSumLeft - SumLeft * SumLeft) / (NoLeft * NoLeft);
|
---|
99 | VarRight = NoRight <= 0 ? 0 : Math.Abs(NoRight * SqSumRight - SumRight * SumRight) / (NoRight * NoRight);
|
---|
100 |
|
---|
101 | if (Order <= 0) throw new ArgumentException("Impurity order must be larger than 0");
|
---|
102 | if (Order.IsAlmost(1)) {
|
---|
103 | y = VarTotal;
|
---|
104 | yl = VarLeft;
|
---|
105 | yr = VarRight;
|
---|
106 | }
|
---|
107 | else {
|
---|
108 | y = Math.Pow(VarTotal, 1.0 / Order);
|
---|
109 | yl = Math.Pow(VarLeft, 1.0 / Order);
|
---|
110 | yr = Math.Pow(VarRight, 1.0 / Order);
|
---|
111 | }
|
---|
112 | var t = NoRight + NoLeft;
|
---|
113 | if (NoLeft <= 0.0 || NoRight <= 0.0) Impurity = double.MinValue; //Impurity = 0;
|
---|
114 | else Impurity = y - NoLeft / t * yl - NoRight / t * yr; // Impurity = y - NoLeft / NoRight * yl - NoRight / NoLeft * yr
|
---|
115 | }
|
---|
116 | #endregion
|
---|
117 | }
|
---|
118 | } |
---|