Free cookie consent management tool by TermsFeed Policy Generator

source: branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNE.cs @ 14783

Last change on this file since 14783 was 14783, checked in by gkronber, 7 years ago

#2700 renamed EuclideanDistance and added some comments

File size: 14.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Drawing;
25using System.Linq;
26using System.Threading;
27using HeuristicLab.Analysis;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Data;
31using HeuristicLab.Encodings.RealVectorEncoding;
32using HeuristicLab.Optimization;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
35using HeuristicLab.Problems.DataAnalysis;
36using HeuristicLab.Random;
37
38namespace HeuristicLab.Algorithms.DataAnalysis {
39  /// <summary>
40  /// t-distributed stochastic neighbourhood embedding (TSNE) projects the data in a low dimensional
41  /// space to allow visual cluster identification.
42  /// </summary>
43  [Item("TSNE", "t-distributed stochastic neighbourhood embedding projects the data in a low " +
44                "dimensional space to allow visual cluster identification.")]
45  [Creatable(CreatableAttribute.Categories.DataAnalysis, Priority = 100)]
46  [StorableClass]
47  public sealed class TSNEAnalysis : BasicAlgorithm {
48    public override bool SupportsPause {
49      get { return false; }
50    }
51    public override Type ProblemType {
52      get { return typeof(IDataAnalysisProblem); }
53    }
54    public new IDataAnalysisProblem Problem {
55      get { return (IDataAnalysisProblem)base.Problem; }
56      set { base.Problem = value; }
57    }
58
59    #region Parameternames
60    private const string DistanceParameterName = "DistanceFunction";
61    private const string PerplexityParameterName = "Perplexity";
62    private const string ThetaParameterName = "Theta";
63    private const string NewDimensionsParameterName = "Dimensions";
64    private const string MaxIterationsParameterName = "MaxIterations";
65    private const string StopLyingIterationParameterName = "StopLyingIteration";
66    private const string MomentumSwitchIterationParameterName = "MomentumSwitchIteration";
67    private const string InitialMomentumParameterName = "InitialMomentum";
68    private const string FinalMomentumParameterName = "FinalMomentum";
69    private const string EtaParameterName = "Eta";
70    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
71    private const string SeedParameterName = "Seed";
72    private const string ClassesParameterName = "ClassNames";
73    private const string NormalizationParameterName = "Normalization";
74    #endregion
75
76    #region Parameterproperties
77    public IFixedValueParameter<DoubleValue> PerplexityParameter {
78      get { return Parameters[PerplexityParameterName] as IFixedValueParameter<DoubleValue>; }
79    }
80    public OptionalValueParameter<DoubleValue> ThetaParameter {
81      get { return Parameters[ThetaParameterName] as OptionalValueParameter<DoubleValue>; }
82    }
83    public IFixedValueParameter<IntValue> NewDimensionsParameter {
84      get { return Parameters[NewDimensionsParameterName] as IFixedValueParameter<IntValue>; }
85    }
86    public IValueParameter<IDistance<RealVector>> DistanceParameter {
87      get { return Parameters[DistanceParameterName] as IValueParameter<IDistance<RealVector>>; }
88    }
89    public IFixedValueParameter<IntValue> MaxIterationsParameter {
90      get { return Parameters[MaxIterationsParameterName] as IFixedValueParameter<IntValue>; }
91    }
92    public IFixedValueParameter<IntValue> StopLyingIterationParameter {
93      get { return Parameters[StopLyingIterationParameterName] as IFixedValueParameter<IntValue>; }
94    }
95    public IFixedValueParameter<IntValue> MomentumSwitchIterationParameter {
96      get { return Parameters[MomentumSwitchIterationParameterName] as IFixedValueParameter<IntValue>; }
97    }
98    public IFixedValueParameter<DoubleValue> InitialMomentumParameter {
99      get { return Parameters[InitialMomentumParameterName] as IFixedValueParameter<DoubleValue>; }
100    }
101    public IFixedValueParameter<DoubleValue> FinalMomentumParameter {
102      get { return Parameters[FinalMomentumParameterName] as IFixedValueParameter<DoubleValue>; }
103    }
104    public IFixedValueParameter<DoubleValue> EtaParameter {
105      get { return Parameters[EtaParameterName] as IFixedValueParameter<DoubleValue>; }
106    }
107    public IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
108      get { return Parameters[SetSeedRandomlyParameterName] as IFixedValueParameter<BoolValue>; }
109    }
110    public IFixedValueParameter<IntValue> SeedParameter {
111      get { return Parameters[SeedParameterName] as IFixedValueParameter<IntValue>; }
112    }
113    public IFixedValueParameter<StringValue> ClassesParameter {
114      get { return Parameters[ClassesParameterName] as IFixedValueParameter<StringValue>; }
115    }
116    public IFixedValueParameter<BoolValue> NormalizationParameter {
117      get { return Parameters[NormalizationParameterName] as IFixedValueParameter<BoolValue>; }
118    }
119    #endregion
120
121    #region  Properties
122    public IDistance<RealVector> Distance {
123      get { return DistanceParameter.Value; }
124    }
125    public double Perplexity {
126      get { return PerplexityParameter.Value.Value; }
127    }
128    public double Theta {
129      get { return ThetaParameter.Value == null ? 0 : ThetaParameter.Value.Value; }
130    }
131    public int NewDimensions {
132      get { return NewDimensionsParameter.Value.Value; }
133    }
134    public int MaxIterations {
135      get { return MaxIterationsParameter.Value.Value; }
136    }
137    public int StopLyingIteration {
138      get { return StopLyingIterationParameter.Value.Value; }
139    }
140    public int MomentumSwitchIteration {
141      get { return MomentumSwitchIterationParameter.Value.Value; }
142    }
143    public double InitialMomentum {
144      get { return InitialMomentumParameter.Value.Value; }
145    }
146    public double FinalMomentum {
147      get { return FinalMomentumParameter.Value.Value; }
148    }
149    public double Eta {
150      get {
151        return EtaParameter.Value == null ? 0 : EtaParameter.Value.Value;
152      }
153    }
154    public bool SetSeedRandomly {
155      get { return SetSeedRandomlyParameter.Value.Value; }
156    }
157    public uint Seed {
158      get { return (uint)SeedParameter.Value.Value; }
159    }
160    public string Classes {
161      get { return ClassesParameter.Value.Value; }
162    }
163    public bool Normalization {
164      get { return NormalizationParameter.Value.Value; }
165    }
166    [Storable]
167    public TSNE<RealVector> tsne;
168    #endregion
169
170    #region Constructors & Cloning
171    [StorableConstructor]
172    private TSNEAnalysis(bool deserializing) : base(deserializing) { }
173    private TSNEAnalysis(TSNEAnalysis original, Cloner cloner) : base(original, cloner) { }
174    public override IDeepCloneable Clone(Cloner cloner) { return new TSNEAnalysis(this, cloner); }
175    public TSNEAnalysis() {
176      Problem = new RegressionProblem();
177      Parameters.Add(new ValueParameter<IDistance<RealVector>>(DistanceParameterName, "The distance function used to differentiate similar from non-similar points", new EuclideanDistance()));
178      Parameters.Add(new FixedValueParameter<DoubleValue>(PerplexityParameterName, "Perplexity-Parameter of TSNE. Comparable to k in a k-nearest neighbour algorithm. Recommended Value is Floor(number of points /3) or lower", new DoubleValue(25)));
179      Parameters.Add(new OptionalValueParameter<DoubleValue>(ThetaParameterName, "Value describing how much appoximated gradients my differ from exact gradients. Set to 0 for exact calculation and in [0,1] otherwise \n CAUTION: exact calculation of forces requires building a non-sparse N*N matrix where N is the number of data points\n This may exceed memory limitations", new DoubleValue(0.1)));
180      Parameters.Add(new FixedValueParameter<IntValue>(NewDimensionsParameterName, "Dimensionality of projected space (usually 2 for easy visual analysis", new IntValue(2)));
181      Parameters.Add(new FixedValueParameter<IntValue>(MaxIterationsParameterName, "Maximum number of iterations for gradient descent", new IntValue(1000)));
182      Parameters.Add(new FixedValueParameter<IntValue>(StopLyingIterationParameterName, "Number of iterations after which p is no longer approximated", new IntValue(0)));
183      Parameters.Add(new FixedValueParameter<IntValue>(MomentumSwitchIterationParameterName, "Number of iterations after which the momentum in the gradient descent is switched", new IntValue(0)));
184      Parameters.Add(new FixedValueParameter<DoubleValue>(InitialMomentumParameterName, "The initial momentum in the gradient descent", new DoubleValue(0.5)));
185      Parameters.Add(new FixedValueParameter<DoubleValue>(FinalMomentumParameterName, "The final momentum", new DoubleValue(0.8)));
186      Parameters.Add(new FixedValueParameter<DoubleValue>(EtaParameterName, "Gradient Descent learning rate", new DoubleValue(200)));
187      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "If the seed should be random", new BoolValue(true)));
188      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The seed used if it should not be random", new IntValue(0)));
189      Parameters.Add(new FixedValueParameter<StringValue>(ClassesParameterName, "name of the column specifying the class lables of each data point. \n if the lable column can not be found Training/Test is used as labels", new StringValue("none")));
190      Parameters.Add(new FixedValueParameter<BoolValue>(NormalizationParameterName, "Wether the data should be zero centered and have variance of 1 for each variable, so different scalings are ignored", new BoolValue(true)));
191
192      MomentumSwitchIterationParameter.Hidden = true;
193      InitialMomentumParameter.Hidden = true;
194      FinalMomentumParameter.Hidden = true;
195      StopLyingIterationParameter.Hidden = true;
196      EtaParameter.Hidden = true;
197    }
198    #endregion
199
200    public override void Stop() {
201      base.Stop();
202      if(tsne != null) tsne.Running = false;
203    }
204
205    protected override void Run(CancellationToken cancellationToken) {
206      var dataRowNames = new Dictionary<string, List<int>>();
207      var rows = new Dictionary<string, ScatterPlotDataRow>();
208      var problemData = Problem.ProblemData;
209
210      //color datapoints acording to Classes-Variable (be it double or string)
211      if(problemData.Dataset.VariableNames.Contains(Classes)) {
212        if((problemData.Dataset as Dataset).VariableHasType<string>(Classes)) {
213          var classes = problemData.Dataset.GetStringValues(Classes).ToArray();
214          for(var i = 0; i < classes.Length; i++) {
215            if(!dataRowNames.ContainsKey(classes[i])) dataRowNames.Add(classes[i], new List<int>());
216            dataRowNames[classes[i]].Add(i);
217          }
218        } else if((problemData.Dataset as Dataset).VariableHasType<double>(Classes)) {
219          var classValues = problemData.Dataset.GetDoubleValues(Classes).ToArray();
220          var max = classValues.Max() + 0.1;
221          var min = classValues.Min() - 0.1;
222          const int contours = 8;
223          for(var i = 0; i < contours; i++) {
224            var contourname = GetContourName(i, min, max, contours);
225            dataRowNames.Add(contourname, new List<int>());
226            rows.Add(contourname, new ScatterPlotDataRow(contourname, "", new List<Point2D<double>>()));
227            rows[contourname].VisualProperties.Color = GetHeatMapColor(i, contours);
228            rows[contourname].VisualProperties.PointSize = i + 3;
229          }
230          for(var i = 0; i < classValues.Length; i++) {
231            dataRowNames[GetContourName(classValues[i], min, max, contours)].Add(i);
232          }
233        }
234      } else {
235        dataRowNames.Add("Training", problemData.TrainingIndices.ToList());
236        dataRowNames.Add("Test", problemData.TestIndices.ToList());
237      }
238
239      //Set up and run TSNE
240      if(SetSeedRandomly) SeedParameter.Value.Value = new System.Random().Next();
241      var random = new MersenneTwister(Seed);
242      tsne = new TSNE<RealVector>(Distance, random, Results, MaxIterations, StopLyingIteration, MomentumSwitchIteration, InitialMomentum, FinalMomentum, Eta, dataRowNames, rows);
243      var dataset = problemData.Dataset;
244      var allowedInputVariables = problemData.AllowedInputVariables.ToArray();
245      var data = new RealVector[dataset.Rows];
246      for(var row = 0; row < dataset.Rows; row++) data[row] = new RealVector(allowedInputVariables.Select(col => dataset.GetDoubleValue(col, row)).ToArray());
247      if(Normalization) data = NormalizeData(data);
248      tsne.Run(data, NewDimensions, Perplexity, Theta);
249    }
250
251    private static RealVector[] NormalizeData(IReadOnlyList<RealVector> data) {
252      var n = data[0].Length;
253      var mean = new double[n];
254      var sd = new double[n];
255      var nData = new RealVector[data.Count];
256      for(var i = 0; i < n; i++) {
257        var i1 = i;
258        sd[i] = Enumerable.Range(0, data.Count).Select(x => data[x][i1]).StandardDeviation();
259        mean[i] = Enumerable.Range(0, data.Count).Select(x => data[x][i1]).Average();
260      }
261      for(var i = 0; i < data.Count; i++) {
262        nData[i] = new RealVector(n);
263        for(var j = 0; j < n; j++) nData[i][j] = (data[i][j] - mean[j]) / sd[j];
264      }
265      return nData;
266    }
267    private static Color GetHeatMapColor(int contourNr, int noContours) {
268      var q = (double)contourNr / noContours;  // q in [0,1]
269      var c = q < 0.5 ? Color.FromArgb((int)(q * 2 * 255), 255, 0) : Color.FromArgb(255, (int)((1 - q) * 2 * 255), 0);
270      return c;
271    }
272    private static string GetContourName(double value, double min, double max, int noContours) {
273      var size = (max - min) / noContours;
274      var contourNr = (int)((value - min) / size);
275      return GetContourName(contourNr, min, max, noContours);
276    }
277    private static string GetContourName(int i, double min, double max, int noContours) {
278      var size = (max - min) / noContours;
279      return "[" + (min + i * size) + ";" + (min + (i + 1) * size) + ")";
280    }
281  }
282}
Note: See TracBrowser for help on using the repository browser.