Index: /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj
===================================================================
--- /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 5650)
+++ /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 5651)
@@ -113,4 +113,8 @@
     <Compile Include="FixedDataAnalysisAlgorithm.cs" />
     <Compile Include="Interfaces\IDataAnalysisAlgorithm.cs" />
+    <Compile Include="kMeans\KMeansClustering.cs" />
+    <Compile Include="kMeans\KMeansClusteringModel.cs" />
+    <Compile Include="kMeans\KMeansClusteringSolution.cs" />
+    <Compile Include="kMeans\KMeansClusteringUtil.cs" />
     <Compile Include="Linear\LinearRegression.cs">
       <SubType>Code</SubType>
Index: /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClustering.cs
===================================================================
--- /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClustering.cs	(revision 5651)
+++ /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClustering.cs	(revision 5651)
@@ -0,0 +1,105 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2011 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 <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Linq;
+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.Encodings.SymbolicExpressionTreeEncoding;
+using System.Collections.Generic;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  /// <summary>
+  /// k-Means clustering algorithm data analysis algorithm.
+  /// </summary>
+  [Item("k-Means", "The k-Means clustering algorithm.")]
+  [Creatable("Data Analysis")]
+  [StorableClass]
+  public sealed class KMeansClustering : FixedDataAnalysisAlgorithm<IClusteringProblem> {
+    private const string KParameterName = "k";
+    private const string RestartsParameterName = "Restarts";
+    private const string KMeansSolutionResultName = "k-Means clustering solution";
+    #region parameter properties
+    public IValueParameter<IntValue> KParameter {
+      get { return (IValueParameter<IntValue>)Parameters[KParameterName]; }
+    }
+    public IValueParameter<IntValue> RestartsParameter {
+      get { return (IValueParameter<IntValue>)Parameters[RestartsParameterName]; }
+    }
+    #endregion
+    #region properties
+    public IntValue K {
+      get { return KParameter.Value; }
+    }
+    public IntValue Restarts {
+      get { return RestartsParameter.Value; }
+    }
+    #endregion
+    [StorableConstructor]
+    private KMeansClustering(bool deserializing) : base(deserializing) { }
+    private KMeansClustering(KMeansClustering original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public KMeansClustering()
+      : base() {
+      Parameters.Add(new ValueParameter<IntValue>(KParameterName, "The number of clusters.", new IntValue(3)));
+      Parameters.Add(new ValueParameter<IntValue>(RestartsParameterName, "The number of restarts.", new IntValue(0)));
+      Problem = new ClusteringProblem();
+    }
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() { }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new KMeansClustering(this, cloner);
+    }
+
+    #region k-Means clustering
+    protected override void Run() {
+      var solution = CreateKMeansSolution(Problem.ProblemData, K.Value, Restarts.Value);
+      Results.Add(new Result(KMeansSolutionResultName, "The linear regression solution.", solution));
+    }
+
+    public static KMeansClusteringSolution CreateKMeansSolution(IClusteringProblemData problemData, int k, int restarts) {
+      Dataset dataset = problemData.Dataset;
+      IEnumerable<string> allowedInputVariables = problemData.AllowedInputVariables;
+      int start = problemData.TrainingPartitionStart.Value;
+      int end = problemData.TrainingPartitionEnd.Value;
+      IEnumerable<int> rows = Enumerable.Range(start, end - start);
+      int info;
+      double[,] centers;
+      int[] xyc;
+      double[,] inputMatrix = KMeansClusteringUtil.PrepareInputMatrix(dataset, allowedInputVariables, rows);
+      alglib.kmeansgenerate(inputMatrix, inputMatrix.GetLength(0), inputMatrix.GetLength(1), k, restarts + 1, out info, out centers, out xyc);
+      if (info != 1) throw new ArgumentException("Error in calculation of k-Means clustering solution");
+
+      KMeansClusteringSolution solution = new KMeansClusteringSolution(new KMeansClusteringModel(centers, allowedInputVariables), problemData);
+      return solution;
+    }
+    #endregion
+  }
+}
Index: /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringModel.cs
===================================================================
--- /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringModel.cs	(revision 5651)
+++ /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringModel.cs	(revision 5651)
@@ -0,0 +1,89 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2011 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 <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.IO;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using SVM;
+using HeuristicLab.Problems.DataAnalysis;
+using System.Drawing;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  /// <summary>
+  /// Represents a k-Means clustering model.
+  /// </summary>
+  [StorableClass]
+  [Item("KMeansClusteringModel", "Represents a k-Means clustering model.")]
+  public sealed class KMeansClusteringModel : NamedItem, IClusteringModel {
+    public override Image ItemImage {
+      get { return HeuristicLab.Common.Resources.VSImageLibrary.Function; }
+    }
+
+    [Storable]
+    private string[] allowedInputVariables;
+    public IEnumerable<string> AllowedInputVariables {
+      get { return allowedInputVariables; }
+    }
+    [Storable]
+    private List<double[]> centers;
+    public IEnumerable<double[]> Centers {
+      get {
+        return centers.Select(x => (double[])x.Clone());
+      }
+    }
+    [StorableConstructor]
+    private KMeansClusteringModel(bool deserializing) : base(deserializing) { }
+    private KMeansClusteringModel(KMeansClusteringModel original, Cloner cloner)
+      : base(original, cloner) {
+      this.allowedInputVariables = (string[])original.allowedInputVariables.Clone();
+      this.centers = new List<double[]>(original.Centers);
+    }
+    public KMeansClusteringModel(double[,] centers, IEnumerable<string> allowedInputVariables)
+      : base() {
+      // disect center matrix into list of double[]
+      // centers are given as double matrix where number of rows = dimensions and number of columns = clusters
+      // each column is a cluster center
+      this.centers = new List<double[]>();
+      for (int i = 0; i < centers.GetLength(1); i++) {
+        double[] c = new double[centers.GetLength(0)];
+        for (int j = 0; j < c.Length; j++) {
+          c[j] = centers[j, i];
+        }
+        this.centers.Add(c);
+      }
+      this.allowedInputVariables = allowedInputVariables.ToArray();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new KMeansClusteringModel(this, cloner);
+    }
+
+
+    public IEnumerable<int> GetClusterValues(Dataset dataset, IEnumerable<int> rows) {
+      return KMeansClusteringUtil.FindClosestCenters(centers, dataset, allowedInputVariables, rows);
+    }
+  }
+}
Index: /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringSolution.cs
===================================================================
--- /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringSolution.cs	(revision 5651)
+++ /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringSolution.cs	(revision 5651)
@@ -0,0 +1,63 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2011 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 <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Drawing;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Optimization;
+using HeuristicLab.Data;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  /// <summary>
+  /// Represents a k-Means clustering solution for a clustering problem which can be visualized in the GUI.
+  /// </summary>
+  [Item("k-Means clustering solution", "Represents a k-Means solution for a clustering problem which can be visualized in the GUI.")]
+  [StorableClass]
+  public sealed class KMeansClusteringSolution : ClusteringSolution {
+    private const string TrainingIntraClusterSumOfSquaresResultName = "Intra-cluster sum of squares (training)";
+    private const string TestIntraClusterSumOfSquaresResultName = "Intra-cluster sum of squares (test)";
+    public new KMeansClusteringModel Model {
+      get { return (KMeansClusteringModel)base.Model; }
+    }
+
+    [StorableConstructor]
+    private KMeansClusteringSolution(bool deserializing) : base(deserializing) { }
+    private KMeansClusteringSolution(KMeansClusteringSolution original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public KMeansClusteringSolution(KMeansClusteringModel model, IClusteringProblemData problemData)
+      : base(model, problemData) {
+      double trainingIntraClusterSumOfSquares = KMeansClusteringUtil.CalculateIntraClusterSumOfSquares(model, problemData.Dataset, problemData.TrainingIndizes);
+      double testIntraClusterSumOfSquares = KMeansClusteringUtil.CalculateIntraClusterSumOfSquares(model, problemData.Dataset, problemData.TestIndizes);
+      this.Add(new Result(TrainingIntraClusterSumOfSquaresResultName, "The sum of squared distances of points of the training partition to the cluster center (is minimized by k-Means).", new DoubleValue(trainingIntraClusterSumOfSquares)));
+      this.Add(new Result(TestIntraClusterSumOfSquaresResultName, "The sum of squared distances of points of the test partition to the cluster center (is minimized by k-Means).", new DoubleValue(testIntraClusterSumOfSquares)));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new KMeansClusteringSolution(this, cloner);
+    }
+  }
+}
Index: /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringUtil.cs
===================================================================
--- /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringUtil.cs	(revision 5651)
+++ /branches/DataAnalysis Refactoring/HeuristicLab.Algorithms.DataAnalysis/3.4/kMeans/KMeansClusteringUtil.cs	(revision 5651)
@@ -0,0 +1,136 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2011 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 <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Problems.DataAnalysis;
+using System;
+
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  public static class KMeansClusteringUtil {
+    public static double[,] PrepareInputMatrix(Dataset dataset, IEnumerable<string> allowedInputVariables, IEnumerable<int> rows) {
+      List<int> allowedRows = CalculateAllowedRows(dataset, allowedInputVariables, rows).ToList();
+
+      double[,] matrix = new double[allowedRows.Count, allowedInputVariables.Count()];
+      for (int row = 0; row < allowedRows.Count; row++) {
+        int col = 0;
+        foreach (string column in allowedInputVariables) {
+          matrix[row, col] = dataset[column, row];
+          col++;
+        }
+      }
+      return matrix;
+    }
+
+    private static IEnumerable<int> CalculateAllowedRows(Dataset dataset, IEnumerable<string> allowedInputVariables, IEnumerable<int> rows) {
+      // return only rows that contain no infinity or NaN values
+      return from row in rows
+             where (from inputVariable in allowedInputVariables
+                    let x = dataset[inputVariable, row]
+                    where double.IsInfinity(x) || double.IsNaN(x)
+                    select 1)
+                    .Any() == false
+             select row;
+    }
+
+    public static IEnumerable<int> FindClosestCenters(IEnumerable<double[]> centers, Dataset dataset, IEnumerable<string> allowedInputVariables, IEnumerable<int> rows) {
+      int nRows = rows.Count();
+      int nCols = allowedInputVariables.Count();
+      int[] closestCenter = new int[nRows];
+      double[] bestCenterDistance = Enumerable.Repeat(double.MaxValue, nRows).ToArray();
+      int centerIndex = 1;
+
+      foreach (double[] center in centers) {
+        if (nCols != center.Length) throw new ArgumentException();
+        int rowIndex = 0;
+        foreach (var row in rows) {
+          // calc euclidian distance of point to center
+          double centerDistance = 0;
+          int col = 0;
+          foreach (var inputVariable in allowedInputVariables) {
+            double d = center[col++] - dataset[inputVariable, row];
+            d = d * d; // square;
+            centerDistance += d;
+            if (centerDistance > bestCenterDistance[rowIndex]) break;
+          }
+          if (centerDistance < bestCenterDistance[rowIndex]) {
+            bestCenterDistance[rowIndex] = centerDistance;
+            closestCenter[rowIndex] = centerIndex;
+          }
+          rowIndex++;
+        }
+        centerIndex++;
+      }
+      return closestCenter;
+    }
+
+    public static double CalculateIntraClusterSumOfSquares(KMeansClusteringModel model, Dataset dataset, IEnumerable<int> rows) {
+      List<int> clusterValues = model.GetClusterValues(dataset, rows).ToList();
+      List<string> allowedInputVariables = model.AllowedInputVariables.ToList();
+      int nCols = allowedInputVariables.Count;
+      Dictionary<int, List<double[]>> clusterPoints = new Dictionary<int, List<double[]>>();
+      Dictionary<int, double[]> clusterMeans = new Dictionary<int, double[]>();
+      foreach (var clusterValue in clusterValues.Distinct()) {
+        clusterPoints.Add(clusterValue, new List<double[]>());
+      }
+
+      // collect points of clusters
+      int clusterValueIndex = 0;
+      foreach (var row in rows) {
+        double[] p = new double[allowedInputVariables.Count];
+        for (int i = 0; i < nCols; i++) {
+          p[i] = dataset[allowedInputVariables[i], row];
+        }
+        clusterPoints[clusterValues[clusterValueIndex++]].Add(p);
+      }
+      // calculate cluster means
+      foreach (var pair in clusterPoints) {
+        double[] mean = new double[nCols];
+        foreach (var p in pair.Value) {
+          for (int i = 0; i < nCols; i++) {
+            mean[i] += p[i];
+          }
+        }
+        for (int i = 0; i < nCols; i++) {
+          mean[i] /= pair.Value.Count;
+        }
+        clusterMeans[pair.Key] = mean;
+      }
+      // calculate distances
+      double allCenterDistances = 0;
+      foreach (var pair in clusterMeans) {
+        double[] mean = pair.Value;
+        double centerDistances = 0;
+        foreach (var clusterPoint in clusterPoints[pair.Key]) {
+          double centerDistance = 0;
+          for (int i = 0; i < nCols; i++) {
+            double d = mean[i] - clusterPoint[i];
+            d = d * d;
+            centerDistance += d;
+          }
+          centerDistances += centerDistance;
+        }
+        allCenterDistances += centerDistances;
+      }
+      return allCenterDistances;
+    }
+  }
+}
