#region License Information /* HeuristicLab * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using System.Drawing; using System.Linq; using System.Threading; using HeuristicLab.Analysis; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Problems.DataAnalysis; using HeuristicLab.Random; namespace HeuristicLab.Algorithms.DataAnalysis { /// /// t-distributed stochastic neighbourhood embedding (tSNE) projects the data in a low dimensional /// space to allow visual cluster identification. /// [Item("tSNE", "t-distributed stochastic neighbourhood embedding projects the data in a low " + "dimensional space to allow visual cluster identification.")] [Creatable(CreatableAttribute.Categories.DataAnalysis, Priority = 100)] [StorableClass] public sealed class TSNEAlgorithm : BasicAlgorithm { public override bool SupportsPause { get { return false; } } public override Type ProblemType { get { return typeof(IDataAnalysisProblem); } } public new IDataAnalysisProblem Problem { get { return (IDataAnalysisProblem)base.Problem; } set { base.Problem = value; } } #region parameter names private const string DistanceParameterName = "DistanceFunction"; private const string PerplexityParameterName = "Perplexity"; private const string ThetaParameterName = "Theta"; private const string NewDimensionsParameterName = "Dimensions"; private const string MaxIterationsParameterName = "MaxIterations"; private const string StopLyingIterationParameterName = "StopLyingIteration"; private const string MomentumSwitchIterationParameterName = "MomentumSwitchIteration"; private const string InitialMomentumParameterName = "InitialMomentum"; private const string FinalMomentumParameterName = "FinalMomentum"; private const string EtaParameterName = "Eta"; private const string SetSeedRandomlyParameterName = "SetSeedRandomly"; private const string SeedParameterName = "Seed"; private const string ClassesParameterName = "ClassNames"; private const string NormalizationParameterName = "Normalization"; #endregion #region result names private const string IterationResultName = "Iteration"; private const string ErrorResultName = "Error"; private const string ErrorPlotResultName = "Error plot"; private const string ScatterPlotResultName = "Scatterplot"; private const string DataResultName = "Projected data"; #endregion #region parameter properties public IFixedValueParameter PerplexityParameter { get { return Parameters[PerplexityParameterName] as IFixedValueParameter; } } public IFixedValueParameter ThetaParameter { get { return Parameters[ThetaParameterName] as IFixedValueParameter; } } public IFixedValueParameter NewDimensionsParameter { get { return Parameters[NewDimensionsParameterName] as IFixedValueParameter; } } public IValueParameter> DistanceParameter { get { return Parameters[DistanceParameterName] as IValueParameter>; } } public IFixedValueParameter MaxIterationsParameter { get { return Parameters[MaxIterationsParameterName] as IFixedValueParameter; } } public IFixedValueParameter StopLyingIterationParameter { get { return Parameters[StopLyingIterationParameterName] as IFixedValueParameter; } } public IFixedValueParameter MomentumSwitchIterationParameter { get { return Parameters[MomentumSwitchIterationParameterName] as IFixedValueParameter; } } public IFixedValueParameter InitialMomentumParameter { get { return Parameters[InitialMomentumParameterName] as IFixedValueParameter; } } public IFixedValueParameter FinalMomentumParameter { get { return Parameters[FinalMomentumParameterName] as IFixedValueParameter; } } public IFixedValueParameter EtaParameter { get { return Parameters[EtaParameterName] as IFixedValueParameter; } } public IFixedValueParameter SetSeedRandomlyParameter { get { return Parameters[SetSeedRandomlyParameterName] as IFixedValueParameter; } } public IFixedValueParameter SeedParameter { get { return Parameters[SeedParameterName] as IFixedValueParameter; } } public IFixedValueParameter ClassesParameter { get { return Parameters[ClassesParameterName] as IFixedValueParameter; } } public IFixedValueParameter NormalizationParameter { get { return Parameters[NormalizationParameterName] as IFixedValueParameter; } } #endregion #region Properties public IDistance Distance { get { return DistanceParameter.Value; } } public double Perplexity { get { return PerplexityParameter.Value.Value; } set { PerplexityParameter.Value.Value = value; } } public double Theta { get { return ThetaParameter.Value.Value; } set { ThetaParameter.Value.Value = value; } } public int NewDimensions { get { return NewDimensionsParameter.Value.Value; } set { NewDimensionsParameter.Value.Value = value; } } public int MaxIterations { get { return MaxIterationsParameter.Value.Value; } set { MaxIterationsParameter.Value.Value = value; } } public int StopLyingIteration { get { return StopLyingIterationParameter.Value.Value; } set { StopLyingIterationParameter.Value.Value = value; } } public int MomentumSwitchIteration { get { return MomentumSwitchIterationParameter.Value.Value; } set { MomentumSwitchIterationParameter.Value.Value = value; } } public double InitialMomentum { get { return InitialMomentumParameter.Value.Value; } set { InitialMomentumParameter.Value.Value = value; } } public double FinalMomentum { get { return FinalMomentumParameter.Value.Value; } set { FinalMomentumParameter.Value.Value = value; } } public double Eta { get { return EtaParameter.Value.Value; } set { EtaParameter.Value.Value = value; } } public bool SetSeedRandomly { get { return SetSeedRandomlyParameter.Value.Value; } set { SetSeedRandomlyParameter.Value.Value = value; } } public int Seed { get { return SeedParameter.Value.Value; } set { SeedParameter.Value.Value = value; } } public string Classes { get { return ClassesParameter.Value.Value; } set { ClassesParameter.Value.Value = value; } } public bool Normalization { get { return NormalizationParameter.Value.Value; } set { NormalizationParameter.Value.Value = value; } } [Storable] public TSNE tsne; #endregion #region Constructors & Cloning [StorableConstructor] private TSNEAlgorithm(bool deserializing) : base(deserializing) { } private TSNEAlgorithm(TSNEAlgorithm original, Cloner cloner) : base(original, cloner) { } public override IDeepCloneable Clone(Cloner cloner) { return new TSNEAlgorithm(this, cloner); } public TSNEAlgorithm() { Problem = new RegressionProblem(); Parameters.Add(new ValueParameter>(DistanceParameterName, "The distance function used to differentiate similar from non-similar points", new EuclideanDistance())); Parameters.Add(new FixedValueParameter(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))); Parameters.Add(new FixedValueParameter(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))); Parameters.Add(new FixedValueParameter(NewDimensionsParameterName, "Dimensionality of projected space (usually 2 for easy visual analysis)", new IntValue(2))); Parameters.Add(new FixedValueParameter(MaxIterationsParameterName, "Maximum number of iterations for gradient descent", new IntValue(1000))); Parameters.Add(new FixedValueParameter(StopLyingIterationParameterName, "Number of iterations after which p is no longer approximated", new IntValue(0))); Parameters.Add(new FixedValueParameter(MomentumSwitchIterationParameterName, "Number of iterations after which the momentum in the gradient descent is switched", new IntValue(0))); Parameters.Add(new FixedValueParameter(InitialMomentumParameterName, "The initial momentum in the gradient descent", new DoubleValue(0.5))); Parameters.Add(new FixedValueParameter(FinalMomentumParameterName, "The final momentum", new DoubleValue(0.8))); Parameters.Add(new FixedValueParameter(EtaParameterName, "Gradient descent learning rate", new DoubleValue(200))); Parameters.Add(new FixedValueParameter(SetSeedRandomlyParameterName, "If the seed should be random", new BoolValue(true))); Parameters.Add(new FixedValueParameter(SeedParameterName, "The seed used if it should not be random", new IntValue(0))); Parameters.Add(new FixedValueParameter(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"))); Parameters.Add(new FixedValueParameter(NormalizationParameterName, "Whether the data should be zero centered and have variance of 1 for each variable, so different scalings are ignored", new BoolValue(true))); MomentumSwitchIterationParameter.Hidden = true; InitialMomentumParameter.Hidden = true; FinalMomentumParameter.Hidden = true; StopLyingIterationParameter.Hidden = true; EtaParameter.Hidden = true; } #endregion [Storable] private Dictionary> dataRowNames; // TODO [Storable] private Dictionary dataRows; // TODO protected override void Run(CancellationToken cancellationToken) { var problemData = Problem.ProblemData; // set up and run tSNE if (SetSeedRandomly) Seed = new System.Random().Next(); var random = new MersenneTwister((uint)Seed); var dataset = problemData.Dataset; var allowedInputVariables = problemData.AllowedInputVariables.ToArray(); var data = new double[dataset.Rows][]; for (var row = 0; row < dataset.Rows; row++) data[row] = allowedInputVariables.Select(col => dataset.GetDoubleValue(col, row)).ToArray(); if (Normalization) data = NormalizeData(data); var tsneState = TSNE.CreateState(data, Distance, random, NewDimensions, Perplexity, Theta, StopLyingIteration, MomentumSwitchIteration, InitialMomentum, FinalMomentum, Eta); SetUpResults(data); for (int iter = 0; iter < MaxIterations && !cancellationToken.IsCancellationRequested; iter++) { TSNE.Iterate(tsneState); Analyze(tsneState); } } private void SetUpResults(IReadOnlyCollection data) { if (Results == null) return; var results = Results; dataRowNames = new Dictionary>(); dataRows = new Dictionary(); var problemData = Problem.ProblemData; //color datapoints acording to classes variable (be it double or string) if (problemData.Dataset.VariableNames.Contains(Classes)) { if ((problemData.Dataset as Dataset).VariableHasType(Classes)) { var classes = problemData.Dataset.GetStringValues(Classes).ToArray(); for (var i = 0; i < classes.Length; i++) { if (!dataRowNames.ContainsKey(classes[i])) dataRowNames.Add(classes[i], new List()); dataRowNames[classes[i]].Add(i); } } else if ((problemData.Dataset as Dataset).VariableHasType(Classes)) { var classValues = problemData.Dataset.GetDoubleValues(Classes).ToArray(); var max = classValues.Max() + 0.1; // TODO consts var min = classValues.Min() - 0.1; const int contours = 8; for (var i = 0; i < contours; i++) { var contourname = GetContourName(i, min, max, contours); dataRowNames.Add(contourname, new List()); dataRows.Add(contourname, new ScatterPlotDataRow(contourname, "", new List>())); dataRows[contourname].VisualProperties.Color = GetHeatMapColor(i, contours); dataRows[contourname].VisualProperties.PointSize = i + 3; } for (var i = 0; i < classValues.Length; i++) { dataRowNames[GetContourName(classValues[i], min, max, contours)].Add(i); } } } else { dataRowNames.Add("Training", problemData.TrainingIndices.ToList()); dataRowNames.Add("Test", problemData.TestIndices.ToList()); } if (!results.ContainsKey(IterationResultName)) results.Add(new Result(IterationResultName, new IntValue(0))); else ((IntValue)results[IterationResultName].Value).Value = 0; if (!results.ContainsKey(ErrorResultName)) results.Add(new Result(ErrorResultName, new DoubleValue(0))); else ((DoubleValue)results[ErrorResultName].Value).Value = 0; if (!results.ContainsKey(ErrorPlotResultName)) results.Add(new Result(ErrorPlotResultName, new DataTable(ErrorPlotResultName, "Development of errors during gradient descent"))); else results[ErrorPlotResultName].Value = new DataTable(ErrorPlotResultName, "Development of errors during gradient descent"); var plot = results[ErrorPlotResultName].Value as DataTable; if (plot == null) throw new ArgumentException("could not create/access error data table in results collection"); if (!plot.Rows.ContainsKey("errors")) plot.Rows.Add(new DataRow("errors")); plot.Rows["errors"].Values.Clear(); results.Add(new Result(ScatterPlotResultName, "Plot of the projected data", new ScatterPlot(DataResultName, ""))); results.Add(new Result(DataResultName, "Projected Data", new DoubleMatrix())); } private void Analyze(TSNE.TSNEState tsneState) { if (Results == null) return; var results = Results; var plot = results[ErrorPlotResultName].Value as DataTable; if (plot == null) throw new ArgumentException("Could not create/access error data table in results collection."); var errors = plot.Rows["errors"].Values; var c = tsneState.EvaluateError(); errors.Add(c); ((IntValue)results[IterationResultName].Value).Value = tsneState.iter + 1; ((DoubleValue)results[ErrorResultName].Value).Value = errors.Last(); var ndata = Normalize(tsneState.newData); results[DataResultName].Value = new DoubleMatrix(ndata); var splot = results[ScatterPlotResultName].Value as ScatterPlot; FillScatterPlot(ndata, splot); } private void FillScatterPlot(double[,] lowDimData, ScatterPlot plot) { foreach (var rowName in dataRowNames.Keys) { if (!plot.Rows.ContainsKey(rowName)) plot.Rows.Add(dataRows.ContainsKey(rowName) ? dataRows[rowName] : new ScatterPlotDataRow(rowName, "", new List>())); plot.Rows[rowName].Points.Replace(dataRowNames[rowName].Select(i => new Point2D(lowDimData[i, 0], lowDimData[i, 1]))); } } private static double[,] Normalize(double[,] data) { var max = new double[data.GetLength(1)]; var min = new double[data.GetLength(1)]; var res = new double[data.GetLength(0), data.GetLength(1)]; for (var i = 0; i < max.Length; i++) max[i] = min[i] = data[0, i]; for (var i = 0; i < data.GetLength(0); i++) for (var j = 0; j < data.GetLength(1); j++) { var v = data[i, j]; max[j] = Math.Max(max[j], v); min[j] = Math.Min(min[j], v); } for (var i = 0; i < data.GetLength(0); i++) { for (var j = 0; j < data.GetLength(1); j++) { res[i, j] = (data[i, j] - (max[j] + min[j]) / 2) / (max[j] - min[j]); } } return res; } private static double[][] NormalizeData(IReadOnlyList data) { var n = data[0].Length; var mean = new double[n]; var sd = new double[n]; var nData = new double[data.Count][]; for (var i = 0; i < n; i++) { var i1 = i; sd[i] = Enumerable.Range(0, data.Count).Select(x => data[x][i1]).StandardDeviation(); mean[i] = Enumerable.Range(0, data.Count).Select(x => data[x][i1]).Average(); } for (var i = 0; i < data.Count; i++) { nData[i] = new double[n]; for (var j = 0; j < n; j++) nData[i][j] = (data[i][j] - mean[j]) / sd[j]; } return nData; } private static Color GetHeatMapColor(int contourNr, int noContours) { var q = (double)contourNr / noContours; // q in [0,1] var c = q < 0.5 ? Color.FromArgb((int)(q * 2 * 255), 255, 0) : Color.FromArgb(255, (int)((1 - q) * 2 * 255), 0); return c; } private static string GetContourName(double value, double min, double max, int noContours) { var size = (max - min) / noContours; var contourNr = (int)((value - min) / size); return GetContourName(contourNr, min, max, noContours); } private static string GetContourName(int i, double min, double max, int noContours) { var size = (max - min) / noContours; return "[" + (min + i * size) + ";" + (min + (i + 1) * size) + ")"; } } }