Changeset 14785 for branches/TSNE

Timestamp:

03/27/17 15:15:23 (8 years ago)

Author:

gkronber

Message:

#2700: changes and while reviewing

Location:

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4

Files:

• HeuristicLab.Algorithms.DataAnalysis-3.4.csproj (modified) (2 diffs)
• Interfaces/TSNEInterfaces/ISpacePartitioningTree.cs (moved) (moved from branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/Interfaces/TSNEInterfaces/ISPTree.cs) (1 diff)
• Interfaces/TSNEInterfaces/IVantagePointTree.cs (moved) (moved from branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/Interfaces/TSNEInterfaces/IVPTree.cs) (1 diff)
• TSNE/DataPoint.cs (deleted)
• TSNE/Distances/IndexedItemDistance.cs (moved) (moved from branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/Distances/DataPointDistance.cs) (2 diffs)
• TSNE/PriorityQueue.cs (modified) (1 diff)
• TSNE/SpacePartitioningTree.cs (moved) (moved from branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/SPtree.cs) (9 diffs)
• TSNE/TSNEAlgorithm.cs (moved) (moved from branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNE.cs) (9 diffs)
• TSNE/TSNEStatic.cs (modified) (15 diffs)
• TSNE/VantagePointTree.cs (moved) (moved from branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/VPTree.cs) (4 diffs)

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj

@@ -334 +334 @@
     <Compile Include="Interfaces\TSNEInterfaces\IDataPoint.cs" />
     <Compile Include="Interfaces\TSNEInterfaces\IDistance.cs" />
-    <Compile Include="Interfaces\TSNEInterfaces\ISPTree.cs" />
-    <Compile Include="Interfaces\TSNEInterfaces\IVPTree.cs" />
+    <Compile Include="Interfaces\TSNEInterfaces\ISpacePartitioningTree.cs" />
+    <Compile Include="Interfaces\TSNEInterfaces\IVantagePointTree.cs" />
     <Compile Include="kMeans\KMeansClustering.cs" />
     <Compile Include="kMeans\KMeansClusteringModel.cs" />
@@ -419 +419 @@
     <Compile Include="TimeSeries\AutoregressiveModeling.cs" />
     <Compile Include="TSNE\Cell.cs" />
-    <Compile Include="TSNE\DataPoint.cs" />
     <Compile Include="TSNE\Distances\DistanceBase.cs" />
-    <Compile Include="TSNE\Distances\DataPointDistance.cs" />
     <Compile Include="TSNE\Distances\EuclideanDistance.cs" />
+    <Compile Include="TSNE\Distances\IndexedItemDistance.cs" />
     <Compile Include="TSNE\Distances\InnerProductDistance.cs" />
     <Compile Include="TSNE\PriorityQueue.cs" />
-    <Compile Include="TSNE\SPtree.cs" />
-    <Compile Include="TSNE\TSNE.cs" />
+    <Compile Include="TSNE\SpacePartitioningTree.cs" />
+    <Compile Include="TSNE\TSNEAlgorithm.cs" />
     <Compile Include="TSNE\TSNEStatic.cs" />
     <Compile Include="TSNE\TSNEUtils.cs" />
-    <Compile Include="TSNE\VPTree.cs" />
+    <Compile Include="TSNE\VantagePointTree.cs" />
   </ItemGroup>
   <ItemGroup>

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/Interfaces/TSNEInterfaces/ISpacePartitioningTree.cs

@@ -23 +23 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
-  public interface ISPTree : IDeepCloneable {
+  public interface ISpacePartitioningTree {
 
     double[,] Data { set; }
     int GetDepth();
-    ISPTree GetParent();
+    ISpacePartitioningTree GetParent();
     bool Insert(int newIndex);
     void Subdivide();

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/Interfaces/TSNEInterfaces/IVantagePointTree.cs

@@ -24 +24 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
-  public interface IVPTree<T> : IDeepCloneable {
-    void Create(IEnumerable<T> items);
-    void Search(T target, int k, out List<T> results, out List<double> distances);
+  public interface IVantagePointTree<T> {
+    void Search(T target, int k, out IList<T> results, out IList<double> distances);
   }
 }

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/Distances/IndexedItemDistance.cs

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Collections;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -26 +27 @@
 namespace HeuristicLab.Algorithms.DataAnalysis {
   [StorableClass]
-  [Item("DataPointDistance", "A distance wrapper for DataPoints")]
-  internal class DataPointDistance<T> : DistanceBase<IDataPoint<T>> where T : class {
-
-    #region properties
+  [Item("IndexedItemDistance", "A distance wrapper for indexed items")]
+  internal class IndexedItemDistance<T> : DistanceBase<IndexedItem<T>> {
     [Storable]
-    private IDistance<T> dist;
-    #endregion
+    private readonly IDistance<T> dist;
 
     #region HLConstructors & Cloning
     [StorableConstructor]
-    protected DataPointDistance(bool deserializing) : base(deserializing) { }
-    protected DataPointDistance(DataPointDistance<T> original, Cloner cloner) : base(original, cloner) {
+    protected IndexedItemDistance(bool deserializing) : base(deserializing) { }
+    protected IndexedItemDistance(IndexedItemDistance<T> original, Cloner cloner) : base(original, cloner) {
       dist = cloner.Clone(original.dist);
     }
-    public override IDeepCloneable Clone(Cloner cloner) { return new DataPointDistance<T>(this, cloner); }
-    public DataPointDistance(IDistance<T> distance) {
+    public override IDeepCloneable Clone(Cloner cloner) { return new IndexedItemDistance<T>(this, cloner); }
+    public IndexedItemDistance(IDistance<T> distance) {
       dist = distance;
     }
     #endregion
 
-    public override double Get(IDataPoint<T> a, IDataPoint<T> b) {
-      return dist.Get(a.X, b.X);
+    public override double Get(IndexedItem<T> a, IndexedItem<T> b) {
+      return dist.Get(a.Value, b.Value);
     }
   }

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/PriorityQueue.cs

@@ -25 +25 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
+  // TODO: move to HeuristicLab.Collections
 
   // Code Taken from branch: RoutePlanning, Heap4

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/SpacePartitioningTree.cs

@@ -62 +62 @@
 namespace HeuristicLab.Algorithms.DataAnalysis {
   /// <summary>
-  /// Space partitioning tree
+  /// Space partitioning tree (SPTree)
   /// </summary>
   [StorableClass]
-  public class SPTree : DeepCloneable, ISPTree {
+  public class SpacePartitioningTree : DeepCloneable, ISpacePartitioningTree {
     private const uint QT_NODE_CAPACITY = 1;
 
@@ -72 +72 @@
     private double[] buff;
     [Storable]
-    private ISPTree parent;
+    private SpacePartitioningTree parent;
     [Storable]
     private int dimension;
@@ -95 +95 @@
 
     // Children
-    private ISPTree[] children;
+    private SpacePartitioningTree[] children;
     [Storable]
     private uint noChildren;
@@ -102 +102 @@
     #region HLConstructors & Cloning
     [StorableConstructor]
-    protected SPTree(bool deserializing) { }
-    protected SPTree(SPTree original, Cloner cloner)
+    protected SpacePartitioningTree(bool deserializing) { }
+    protected SpacePartitioningTree(SpacePartitioningTree original, Cloner cloner)
       : base(original, cloner) {
       buff = original.buff.Select(x => x).ToArray();
@@ -121 +121 @@
       noChildren = original.noChildren;
     }
-    public override IDeepCloneable Clone(Cloner cloner) { return new SPTree(this, cloner); }
-
-    public SPTree(double[,] inpData) {
+    public override IDeepCloneable Clone(Cloner cloner) { return new SpacePartitioningTree(this, cloner); }
+
+    public SpacePartitioningTree(double[,] inpData) {
       var d = inpData.GetLength(1);
       var n = inpData.GetLength(0);
@@ -145 +145 @@
     }
 
-    public SPTree(double[,] inpData, IEnumerable<double> impCorner, IEnumerable<double> impWith) {
+    public SpacePartitioningTree(double[,] inpData, IEnumerable<double> impCorner, IEnumerable<double> impWith) {
       Init(null, inpData, impCorner, impWith);
     }
-    public SPTree(ISPTree parent, double[,] inpData, IEnumerable<double> impCorner, IEnumerable<double> impWith) {
+    public SpacePartitioningTree(SpacePartitioningTree parent, double[,] inpData, IEnumerable<double> impCorner, IEnumerable<double> impWith) {
       Init(parent, inpData, impCorner, impWith);
     }
     #endregion
 
-    public ISPTree GetParent() {
+    public ISpacePartitioningTree GetParent() {
       return parent;
     }
@@ -211 +211 @@
           div *= 2;
         }
-        children[i] = new SPTree(this, Data, newCorner, newWidth);
+        children[i] = new SpacePartitioningTree(this, Data, newCorner, newWidth);
       }
 
@@ -307 +307 @@
       for (var i = 0; i < n; i++) Insert(i);
     }
-    private void Init(ISPTree p, double[,] inpData, IEnumerable<double> inpCorner, IEnumerable<double> inpWidth) {
+    private void Init(SpacePartitioningTree p, double[,] inpData, IEnumerable<double> inpCorner, IEnumerable<double> inpWidth) {
       parent = p;
       dimension = inpData.GetLength(1);
@@ -320 +320 @@
       inpWidth.ForEach((i, x) => boundary.SetWidth(i, x));
 
-      children = new ISPTree[noChildren];
+      children = new SpacePartitioningTree[noChildren];
       centerOfMass = new double[dimension];
       buff = new double[dimension];

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNEAlgorithm.cs

@@ -38 +38 @@
 namespace HeuristicLab.Algorithms.DataAnalysis {
   /// <summary>
-  /// t-distributed stochastic neighbourhood embedding (TSNE) projects the data in a low dimensional 
+  /// t-distributed stochastic neighbourhood embedding (tSNE) projects the data in a low dimensional 
   /// space to allow visual cluster identification.
   /// </summary>
-  [Item("TSNE", "t-distributed stochastic neighbourhood embedding projects the data in a low " +
+  [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 TSNEAnalysis : BasicAlgorithm {
+  public sealed class TSNEAlgorithm : BasicAlgorithm {
     public override bool SupportsPause {
       get { return false; }
@@ -57 +57 @@
     }
 
-    #region Parameternames
+    #region parameter names
     private const string DistanceParameterName = "DistanceFunction";
     private const string PerplexityParameterName = "Perplexity";
@@ -74 +74 @@
     #endregion
 
-    #region Parameterproperties
+    #region parameter properties
     public IFixedValueParameter<DoubleValue> PerplexityParameter {
       get { return Parameters[PerplexityParameterName] as IFixedValueParameter<DoubleValue>; }
     }
-    public OptionalValueParameter<DoubleValue> ThetaParameter {
-      get { return Parameters[ThetaParameterName] as OptionalValueParameter<DoubleValue>; }
+    public IFixedValueParameter<DoubleValue> ThetaParameter {
+      get { return Parameters[ThetaParameterName] as IFixedValueParameter<DoubleValue>; }
     }
     public IFixedValueParameter<IntValue> NewDimensionsParameter {
       get { return Parameters[NewDimensionsParameterName] as IFixedValueParameter<IntValue>; }
     }
-    public IValueParameter<IDistance<RealVector>> DistanceParameter {
-      get { return Parameters[DistanceParameterName] as IValueParameter<IDistance<RealVector>>; }
+    public IValueParameter<IDistance<double[]>> DistanceParameter {
+      get { return Parameters[DistanceParameterName] as IValueParameter<IDistance<double[]>>; }
     }
     public IFixedValueParameter<IntValue> MaxIterationsParameter {
@@ -120 +120 @@
 
     #region  Properties
-    public IDistance<RealVector> Distance {
+    public IDistance<double[]> 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 == null ? 0 : ThetaParameter.Value.Value; }
+      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 == null ? 0 : EtaParameter.Value.Value;
-      }
+      get { return EtaParameter.Value.Value; }
+      set { EtaParameter.Value.Value = value; }
     }
     public bool SetSeedRandomly {
       get { return SetSeedRandomlyParameter.Value.Value; }
-    }
-    public uint Seed {
-      get { return (uint)SeedParameter.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<RealVector> tsne;
+    public TSNE<double[]> tsne;
     #endregion
 
     #region Constructors & Cloning
     [StorableConstructor]
-    private TSNEAnalysis(bool deserializing) : base(deserializing) { }
-    private TSNEAnalysis(TSNEAnalysis original, Cloner cloner) : base(original, cloner) { }
-    public override IDeepCloneable Clone(Cloner cloner) { return new TSNEAnalysis(this, cloner); }
-    public TSNEAnalysis() {
+    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<IDistance<RealVector>>(DistanceParameterName, "The distance function used to differentiate similar from non-similar points", new EuclideanDistance()));
-      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)));
-      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)));
-      Parameters.Add(new FixedValueParameter<IntValue>(NewDimensionsParameterName, "Dimensionality of projected space (usually 2 for easy visual analysis", new IntValue(2)));
+      Parameters.Add(new ValueParameter<IDistance<double[]>>(DistanceParameterName, "The distance function used to differentiate similar from non-similar points", new EuclideanDistance()));
+      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)));
+      Parameters.Add(new FixedValueParameter<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)));
+      Parameters.Add(new FixedValueParameter<IntValue>(NewDimensionsParameterName, "Dimensionality of projected space (usually 2 for easy visual analysis)", new IntValue(2)));
       Parameters.Add(new FixedValueParameter<IntValue>(MaxIterationsParameterName, "Maximum number of iterations for gradient descent", new IntValue(1000)));
       Parameters.Add(new FixedValueParameter<IntValue>(StopLyingIterationParameterName, "Number of iterations after which p is no longer approximated", new IntValue(0)));
@@ -184 +195 @@
       Parameters.Add(new FixedValueParameter<DoubleValue>(InitialMomentumParameterName, "The initial momentum in the gradient descent", new DoubleValue(0.5)));
       Parameters.Add(new FixedValueParameter<DoubleValue>(FinalMomentumParameterName, "The final momentum", new DoubleValue(0.8)));
-      Parameters.Add(new FixedValueParameter<DoubleValue>(EtaParameterName, "Gradient Descent learning rate", new DoubleValue(200)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(EtaParameterName, "Gradient descent learning rate", new DoubleValue(200)));
       Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "If the seed should be random", new BoolValue(true)));
       Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The seed used if it should not be random", new IntValue(0)));
-      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")));
-      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)));
+      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")));
+      Parameters.Add(new FixedValueParameter<BoolValue>(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;
@@ -200 +211 @@
     public override void Stop() {
       base.Stop();
-      if(tsne != null) tsne.Running = false;
+      if (tsne != null) tsne.Running = false;
     }
 
@@ -208 +219 @@
       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<string>(Classes)) {
+      //color datapoints acording to classes variable (be it double or string)
+      if (problemData.Dataset.VariableNames.Contains(Classes)) {
+        if ((problemData.Dataset as Dataset).VariableHasType<string>(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<int>());
+          for (var i = 0; i < classes.Length; i++) {
+            if (!dataRowNames.ContainsKey(classes[i])) dataRowNames.Add(classes[i], new List<int>());
             dataRowNames[classes[i]].Add(i);
           }
-        } else if((problemData.Dataset as Dataset).VariableHasType<double>(Classes)) {
+        } else if ((problemData.Dataset as Dataset).VariableHasType<double>(Classes)) {
           var classValues = problemData.Dataset.GetDoubleValues(Classes).ToArray();
-          var max = classValues.Max() + 0.1;
+          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++) {
+          for (var i = 0; i < contours; i++) {
             var contourname = GetContourName(i, min, max, contours);
             dataRowNames.Add(contourname, new List<int>());
@@ -228 +239 @@
             rows[contourname].VisualProperties.PointSize = i + 3;
           }
-          for(var i = 0; i < classValues.Length; i++) {
+          for (var i = 0; i < classValues.Length; i++) {
             dataRowNames[GetContourName(classValues[i], min, max, contours)].Add(i);
           }
@@ -237 +248 @@
       }
 
-      //Set up and run TSNE
-      if(SetSeedRandomly) SeedParameter.Value.Value = new System.Random().Next();
-      var random = new MersenneTwister(Seed);
-      tsne = new TSNE<RealVector>(Distance, random, Results, MaxIterations, StopLyingIteration, MomentumSwitchIteration, InitialMomentum, FinalMomentum, Eta, dataRowNames, rows);
+      // set up and run tSNE
+      if (SetSeedRandomly) Seed = new System.Random().Next();
+      var random = new MersenneTwister((uint)Seed);
+      tsne = new TSNE<double[]>(Distance, random, Results, MaxIterations, StopLyingIteration, MomentumSwitchIteration, InitialMomentum, FinalMomentum, Eta, dataRowNames, rows);
       var dataset = problemData.Dataset;
       var allowedInputVariables = problemData.AllowedInputVariables.ToArray();
-      var data = new RealVector[dataset.Rows];
-      for(var row = 0; row < dataset.Rows; row++) data[row] = new RealVector(allowedInputVariables.Select(col => dataset.GetDoubleValue(col, row)).ToArray());
-      if(Normalization) data = NormalizeData(data);
+      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);
       tsne.Run(data, NewDimensions, Perplexity, Theta);
     }
 
-    private static RealVector[] NormalizeData(IReadOnlyList<RealVector> data) {
+    private static double[][] NormalizeData(IReadOnlyList<double[]> data) {
       var n = data[0].Length;
       var mean = new double[n];
       var sd = new double[n];
-      var nData = new RealVector[data.Count];
-      for(var i = 0; i < n; i++) {
+      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 RealVector(n);
-        for(var j = 0; j < n; j++) nData[i][j] = (data[i][j] - mean[j]) / sd[j];
+      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;

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNEStatic.cs

@@ -58 +58 @@
 using System.Linq;
 using HeuristicLab.Analysis;
+using HeuristicLab.Collections;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -67 +68 @@
 namespace HeuristicLab.Algorithms.DataAnalysis {
   [StorableClass]
-  public class TSNE<T> : DeepCloneable where T : class, IDeepCloneable {
+  public class TSNE<T> : DeepCloneable /*where T : class, IDeepCloneable*/ {
 
     private const string IterationResultName = "Iteration";
@@ -101 +102 @@
 
     #region Stopping 
-    public volatile bool Running;
+    public volatile bool Running;      // TODO
     #endregion
 
@@ -164 +165 @@
 
       // Initialize solution (randomly)
-      for (var i = 0; i < noDatapoints; i++) for (var j = 0; j < newDimensions; j++) newData[i, j] = rand.NextDouble() * .0001;
+      for (var i = 0; i < noDatapoints; i++) for (var j = 0; j < newDimensions; j++) newData[i, j] = rand.NextDouble() * .0001;  // TODO const
 
       // Perform main training loop
       for (var iter = 0; iter < maxIter && Running; iter++) {
         if (exact) ComputeExactGradient(p, newData, noDatapoints, newDimensions, dY);
-        else ComputeGradient(rowP, colP, valP, newData, noDatapoints, newDimensions, dY, theta);
+        else ComputeApproximateGradient(rowP, colP, valP, newData, noDatapoints, newDimensions, dY, theta);
         // Update gains
         for (var i = 0; i < noDatapoints; i++) for (var j = 0; j < newDimensions; j++) gains[i, j] = Math.Sign(dY[i, j]) != Math.Sign(uY[i, j]) ? gains[i, j] + .2 : gains[i, j] * .8;
@@ -189 +190 @@
       return newData;
     }
-    public static double[,] Run<TR>(TR[] data, int newDimensions, double perplexity, double theta, IDistance<TR> distance, IRandom random) where TR : class, IDeepCloneable {
-      return new TSNE<TR>(distance, random).Run(data, newDimensions, perplexity, theta);
-    }
 
     #region helpers
@@ -205 +203 @@
       else ((DoubleValue)results[ErrorResultName].Value).Value = 0;
 
-      if (!results.ContainsKey(ErrorPlotResultName)) results.Add(new Result(ErrorPlotResultName, new DataTable(ErrorPlotResultName, "Development of errors during Gradiant descent")));
-      else results[ErrorPlotResultName].Value = new DataTable(ErrorPlotResultName, "Development of errors during Gradiant descent");
+      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-DataTable in Results-Collection");
+      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"));
@@ -224 +222 @@
       var errors = plot.Rows["errors"].Values;
       var c = exact
-        ? EvaluateError(p, newData, noDatapoints, newDimensions)
-        : EvaluateError(rowP, colP, valP, newData, theta);
+        ? EvaluateErrorExact(p, newData, noDatapoints, newDimensions)
+        : EvaluateErrorApproximate(rowP, colP, valP, newData, theta);
       errors.Add(c);
       ((IntValue)results[IterationResultName].Value).Value = iter + 1;
@@ -304 +302 @@
       for (var i = 0; i < n; i++) rowP[i + 1] = rowP[i] + k;
 
+      var objX = new List<IndexedItem<T>>();
+      for (var i = 0; i < n; i++) objX.Add(new IndexedItem<T>(i, x[i]));
+
       // Build ball tree on data set
-      var tree = new VPTree<IDataPoint<T>>(new DataPointDistance<T>(distance));
-      var objX = new List<IDataPoint<T>>();
-      for (var i = 0; i < n; i++) objX.Add(new DataPoint<T>(i, x[i]));
-      tree.Create(objX);
+      var tree = new VantagePointTree<IndexedItem<T>>(new IndexedItemDistance<T>(distance), objX);           // do we really want to re-create the tree on each call?
 
       // Loop over all points to find nearest neighbors
-      var indices = new List<IDataPoint<T>>();
-      var distances = new List<double>();
       for (var i = 0; i < n; i++) {
+        IList<IndexedItem<T>> indices;
+        IList<double> distances;
 
         // Find nearest neighbors
-        indices.Clear();
-        distances.Clear();
         tree.Search(objX[i], k + 1, out indices, out distances);
 
@@ -323 +319 @@
         var found = false;
         var beta = 1.0;
-        var minBeta = -double.MaxValue;
+        var minBeta = double.MinValue;
         var maxBeta = double.MaxValue;
-        const double tol = 1e-5;
+        const double tol = 1e-5;  // TODO: why 1e-5?
 
         // Iterate until we found a good perplexity
@@ -374 +370 @@
     }
     private void ComputeGaussianPerplexity(T[] x, int n, double[,] p, double perplexity) {
-      // Compute the squared Euclidean distance matrix
+      // Compute the distance matrix
       var dd = ComputeDistances(x);
+
       // Compute the Gaussian kernel row by row
-
       for (var i = 0; i < n; i++) {
         // Initialize some variables
@@ -389 +385 @@
         // Iterate until we found a good perplexity
         var iter = 0;
-        while (!found && iter < 200) {
+        while (!found && iter < 200) {       // TODO constant
 
           // Compute Gaussian kernel row
@@ -430 +426 @@
       }
     }
+
     private double[][] ComputeDistances(T[] x) {
       return x.Select(m => x.Select(n => distance.Get(m, n)).ToArray()).ToArray();
     }
+
     private static void ComputeExactGradient(double[,] p, double[,] y, int n, int d, double[,] dC) {
 
@@ -487 +485 @@
       }
     }
-    private static void ComputeGradient(int[] rowP, int[] colP, double[] valP, double[,] y, int n, int d, double[,] dC, double theta) {
-      var tree = new SPTree(y);
+    private static void ComputeApproximateGradient(int[] rowP, int[] colP, double[] valP, double[,] y, int n, int d, double[,] dC, double theta) {
+      var tree = new SpacePartitioningTree(y);
       double[] sumQ = { 0 };
       var posF = new double[n, d];
@@ -502 +500 @@
       for (var i = 0; i < n; i++)
         for (var j = 0; j < d; j++) {
-          dC[i, j] = posF[i, j] - negF[i, j] / sumQ[0];
-        }
-    }
-    private static double EvaluateError(double[,] p, double[,] y, int n, int d) {
+          dC[i, j] = (posF[i, j] - negF[i, j]) / sumQ[0]; // TODO: check parenthesis
+        }
+    }
+
+    private static double EvaluateErrorExact(double[,] p, double[,] y, int n, int d) {
       // Compute the squared Euclidean distance matrix
       var dd = new double[n, n];
@@ -531 +530 @@
       return c;
     }
-    private static double EvaluateError(IReadOnlyList<int> rowP, IReadOnlyList<int> colP, IReadOnlyList<double> valP, double[,] y, double theta) {
+    private static double EvaluateErrorApproximate(IReadOnlyList<int> rowP, IReadOnlyList<int> colP, IReadOnlyList<double> valP, double[,] y, double theta) {
       // Get estimate of normalization term
       var n = y.GetLength(0);
       var d = y.GetLength(1);
-      var tree = new SPTree(y);
+      var tree = new SpacePartitioningTree(y);
       var buff = new double[d];
       double[] sumQ = { 0 };

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/VantagePointTree.cs

@@ -57 +57 @@
 using System.Collections.Generic;
 using System.Linq;
+using HeuristicLab.Collections;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -72 +73 @@
   /// <typeparam name="T"></typeparam>
   [StorableClass]
-  public class VPTree<T> : DeepCloneable, IVPTree<T> where T : class, IDeepCloneable {
+  public class VantagePointTree<T> : IVantagePointTree<T> {
     #region properties
-    [Storable]
-    private List<T> items;
-    [Storable]
-    private double tau;
-    [Storable]
-    private Node root;
-    [Storable]
-    private IDistance<T> distance;
+    private readonly List<T> items;
+    private readonly Node root;
+    private readonly IDistance<T> distance;
     #endregion
 
-    #region HLConstructors & Cloning
-    [StorableConstructor]
-    protected VPTree(bool deserializing) { }
-    protected VPTree(VPTree<T> original, Cloner cloner)
-      : base(original, cloner) {
-      items = original.items.Select(cloner.Clone).ToList();
-      tau = original.tau;
-      root = cloner.Clone(original.root);
-      distance = cloner.Clone(distance);
-    }
-    public override IDeepCloneable Clone(Cloner cloner) { return new VPTree<T>(this, cloner); }
-    public VPTree(IDistance<T> distance) {
+    public VantagePointTree(IDistance<T> distance, IEnumerable<T> items) : base() {
       root = null;
       this.distance = distance;
-    }
-    #endregion
-
-    public void Create(IEnumerable<T> items) {
       this.items = items.Select(x => x).ToList();
       root = BuildFromPoints(0, this.items.Count);
     }
 
-    public void Search(T target, int k, out List<T> results, out List<double> distances) {
-      var heap = new PriorityQueue<double, HeapItem>(double.MaxValue, double.MinValue, k);
-      tau = double.MaxValue;
-      Search(root, target, k, heap);
-      results = new List<T>();
-      distances = new List<double>();
+    public void Search(T target, int k, out IList<T> results, out IList<double> distances) {
+      var heap = new PriorityQueue<double, IndexedItem<double>>(double.MaxValue, double.MinValue, k);
+      Search(root, target, k, heap, double.MaxValue);
+      var res = new List<T>();
+      var dist = new List<double>();
       while (heap.Size > 0) {
-        results.Add(items[heap.PeekMinValue().Index]);
-        distances.Add(heap.PeekMinValue().Dist);
+        res.Add(items[heap.PeekMinValue().Index]);
+        dist.Add(heap.PeekMinValue().Value);
         heap.RemoveMin();
       }
-      results.Reverse();
-      distances.Reverse();
+      res.Reverse();
+      dist.Reverse();
+      results = res;
+      distances = dist;
+    }
+
+    private void Search(Node node, T target, int k, PriorityQueue<double, IndexedItem<double>> heap, double tau = double.MaxValue) {
+      if (node == null) return;
+      var dist = distance.Get(items[node.index], target);
+      if (dist < tau) {
+        if (heap.Size == k) heap.RemoveMin();
+        heap.Insert(-dist, new IndexedItem<double>(node.index, dist));//TODO check if minheap or maxheap should be used here
+        if (heap.Size == k) tau = heap.PeekMinValue().Value;
+      }
+      if (node.left == null && node.right == null) return;
+
+      if (dist < node.threshold) {
+        if (dist - tau <= node.threshold) Search(node.left, target, k, heap, tau);   // if there can still be neighbors inside the ball, recursively search left child first
+        if (dist + tau >= node.threshold) Search(node.right, target, k, heap, tau);  // if there can still be neighbors outside the ball, recursively search right child
+      } else {
+        if (dist + tau >= node.threshold) Search(node.right, target, k, heap, tau);  // if there can still be neighbors outside the ball, recursively search right child first
+        if (dist - tau <= node.threshold) Search(node.left, target, k, heap, tau);   // if there can still be neighbors inside the ball, recursively search left child
+      }
     }
 
@@ -150 +151 @@
     }
 
-    private void Search(Node node, T target, int k, PriorityQueue<double, HeapItem> heap) {
-      if (node == null) return;
-      var dist = distance.Get(items[node.index], target);
-      if (dist < tau) {
-        if (heap.Size == k) heap.RemoveMin();
-        heap.Insert(-dist, new HeapItem(node.index, dist));//TODO check if minheap or maxheap should be used here
-        if (heap.Size == k) tau = heap.PeekMinValue().Dist;
-      }
-      if (node.left == null && node.right == null) return;
-
-      if (dist < node.threshold) {
-        if (dist - tau <= node.threshold) Search(node.left, target, k, heap);   // if there can still be neighbors inside the ball, recursively search left child first
-        if (dist + tau >= node.threshold) Search(node.right, target, k, heap);  // if there can still be neighbors outside the ball, recursively search right child
-      } else {
-        if (dist + tau >= node.threshold) Search(node.right, target, k, heap);  // if there can still be neighbors outside the ball, recursively search right child first
-        if (dist - tau <= node.threshold) Search(node.left, target, k, heap);   // if there can still be neighbors inside the ball, recursively search left child
-      }
-
-    }
-
-    [StorableClass]
-    private sealed class Node : Item {
-      [Storable]
+    private sealed class Node {
       public int index;
-      [Storable]
       public double threshold;
-      [Storable]
       public Node left;
-      [Storable]
       public Node right;
 
-      #region HLConstructors & Cloning
-      [StorableConstructor]
-      private Node(bool deserializing) : base(deserializing) { }
-      private Node(Node original, Cloner cloner) : base(original, cloner) {
-        index = original.index;
-        threshold = original.threshold;
-        left = (Node)original.left.Clone(cloner);
-        right = (Node)original.right.Clone(cloner);
-      }
       internal Node() {
         index = 0;
@@ -196 +163 @@
         right = null;
       }
-      public override IDeepCloneable Clone(Cloner cloner) {
-        return new Node(this, cloner);
-      }
-      #endregion
-    }
-
-    [StorableClass]
-    private sealed class HeapItem : Item, IComparable<HeapItem> {
-      [Storable]
-      public int Index;
-      [Storable]
-      public double Dist;
-
-      #region HLConstructors & Cloning
-      [StorableConstructor]
-      private HeapItem(bool deserializing) : base(deserializing) { }
-      private HeapItem(HeapItem original, Cloner cloner)
-      : base(original, cloner) {
-        Index = original.Index;
-        Dist = original.Dist;
-      }
-      public override IDeepCloneable Clone(Cloner cloner) { return new HeapItem(this, cloner); }
-      public HeapItem(int index, double dist) {
-        Index = index;
-        Dist = dist;
-      }
-      #endregion
-
-      public int CompareTo(HeapItem other) {
-        return Dist.CompareTo(Dist);
-      }
     }
   }