KMeans.hpp

Go to the documentation of this file.

#ifndef MACHINE_LEARNING_KMEANS_HPP
#define MACHINE_LEARNING_KMEANS_HPP

#include "../include/matrix/Matrix.hpp"
#include "Metrics.hpp"
#include "../include/mersenne_twister/MersenneTwister.hpp"

class KMeans {
 public:
  enum InitializationMethod { RANDOM, SAMPLE };
 private:
  MatrixD X, y, centroids;
  unsigned int k, totalIterations;
  double distance, sse;
  InitializationMethod initMethod;

  double SSE() {
    return Metrics::euclidean(X, centroids, false).sum();
  }

 public:
  KMeans() {}

  MatrixD predict(MatrixD data) {
    if (centroids.nCols() != data.nCols())
      throw invalid_argument("Data elements and cluster centroids don't have the same number of dimensions.");

    MatrixD distances = Metrics::minkowski(data, centroids, distance, false);
    MatrixD results = MatrixD::zeros(data.nRows(), 1);

    for (size_t i = 0; i < distances.nRows(); i++) {
      for (size_t j = 1; j < distances.nCols(); j++) {
        double current_c = results(i, 0);
        double current_d = distances(i, current_c);
        double new_c = j;
        double new_d = distances(i, new_c);
        if (new_d < current_d)
          results(i, 0) = new_c;
      }
    }

    return results;
  }

  void fit(MatrixD data,
           unsigned int k,
           unsigned int iters = 100,
           unsigned int inits = 100,
           double distance = 2,
           InitializationMethod initMethod = SAMPLE, bool verbose = false) {
    this->X = data.standardize();
    this->k = k;
    this->initMethod = initMethod;
    this->distance = distance;
    this->totalIterations = 0;
    MersenneTwister twister;
    double minSSE;

    for (int currentInit = 0; currentInit < inits; currentInit++) {

      if (initMethod == RANDOM) {
        centroids = MatrixD(k, X.nCols());
        for (size_t i = 0; i < centroids.nRows(); i++)
          for (size_t j = 0; j < centroids.nCols(); j++)
            centroids(i, j) = twister.d_random(X.getColumn(j).min(),
                                               X.getColumn(j).max());
      } else {
        vector<int> sample = twister.randomValues(X.nRows(), k, false);
        centroids = MatrixD();
        for (int i = 0; i < sample.size(); i++)
          centroids.addRow(X.getRow(sample[i]));
      }

      MatrixD yPrev;

      for (int currentIteration = 0; currentIteration < iters; currentIteration++) {
        if (verbose)
          cout << currentInit << '/' << inits + 1 << '\t'
               << currentIteration << '/' << iters + 1 << '\t'
               << SSE() << endl;

        MatrixD yCurr = predict(X); // assignment

        if (yCurr == yPrev)
          break;

        yPrev = yCurr;
        centroids = X.mean(yCurr); // centroid update
      }
      if (currentInit == 0 or SSE() < minSSE) {
        minSSE = SSE();
        y = yPrev;
      }
    }
    this->sse = minSSE;
  }

  const MatrixD &getY() const {
    return y;
  }

  const MatrixD &getCentroids() const {
    return centroids;
  }

  unsigned int getK() const {
    return k;
  }

  unsigned int getTotalIterations() const {
    return totalIterations;
  }

  double getDistance() const {
    return distance;
  }

  double getSse() const {
    return sse;
  }

};

#endif //MACHINE_LEARNING_KMEANS_HPP