source: branches/2988_ModelsOfModels2/HeuristicLab.Algorithms.EMM/KMeansClusterizationAlgorithm.cs @ 17134

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2019 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 HeuristicLab.Core;
using System;
using System.Collections.Generic;

namespace HeuristicLab.Algorithms.EvolvmentModelsOfModels {
  public class KMeansClusterizationAlgorithm {
    public int K { get; private set; }
    public KMeansClusterizationAlgorithm() {
    }
    public KMeansClusterizationAlgorithm(int k) {
      K = k;
    }
    public KMeansClusterizationAlgorithm(KMeansClusterizationAlgorithm old) {
      this.K = old.K;
    }
    public int Apply(IRandom random, double[,] distances, List<int> numberCluster) {

      K = ApplyClusteringAlgorithm(random, distances, numberCluster, K);
      return K;
    }

    public static int ApplyClusteringAlgorithm(IRandom random, double[,] distances, List<int> numberCluster, int k) {
      int mapSize = distances.GetLength(0);
      List<int> centroids = new List<int>(); // capacity is equal K
      List<double> averageClusterDistance = new List<double>();
      List<List<int>> clusters = new List<List<int>>(); // capacity is equal K
      CentroidsRandomSetUp(random, centroids, mapSize, k);
      if (numberCluster.Count == 0) {
        for (int i = 0; i < mapSize; i++) {
          numberCluster.Add(0);
        }
      }
      bool flag = true;
      int count = 0;
      while (flag&&(count<1000)) {
        clusters.Clear();
        for (int i = 0; i < k; i++) {
          clusters.Add(new List<int>());

        }
        for (int i = 0; i < mapSize; i++) {
          numberCluster[i] = LookCloseCentroid(centroids, distances, i, k);
          clusters[numberCluster[i]].Add(i);
        }
        k = NullSizeClusterDelete(centroids, clusters, mapSize, numberCluster, k);
        flag = false;
        for (int i = 0; i < k; i++) {
          AverageClusterDistanceCalculation(averageClusterDistance, distances, numberCluster, mapSize, i);
          var newCentroid = clusters[i][HelpFunctions.ChooseMinElementIndex(averageClusterDistance)];
          if (newCentroid != centroids[i]) {
            flag = true;
            centroids[i] = newCentroid;
          }
          averageClusterDistance.Clear();
        }
        count++;
      }
      return k;
    }
    private static void CentroidsRandomSetUp(IRandom random, List<int> centroids, int size, int k) {
      for (int i = 0; i < k; i++) {
        centroids.Add(random.Next(size));
      }
    }
    private static int LookCloseCentroid(List<int> centroids, double[,] distances, int currentNumber, int k) {
      double minDistanse = distances[currentNumber, centroids[0]];
      int clusterNum = 0;
      for (int i = 1; i < k; i++) {
        if (minDistanse > distances[currentNumber, centroids[i]]) {
          minDistanse = distances[currentNumber, centroids[i]];
          clusterNum = i;
        }
      }
      return clusterNum;
    }
    private static int NullSizeClusterDelete(List<int> centroids, List<List<int>> clusters, int mapSize, List<int> numberCluster, int k) {
      int iter = 0;
      for (int i = 0; i < k; i++) {
        if (clusters[i - iter].Count == 0) {
          for (int j = 0; j < mapSize; j++) {
            if (numberCluster[j] > (i - iter))
              numberCluster[j]--;
          }

          for (int j = 0; j < k - iter; j++) {
            if (j != i - iter) {
              for (int m = 0; m < clusters[j].Count; m++)
                if (clusters[j][m] > (i - iter))
                  (clusters[j][m])--;
            }
          }
          clusters.Remove(clusters[i - iter]);
          centroids.Remove(centroids[i - iter]);
          iter++;
        }
      }
      k -= iter;
      return k;
    }
    public static void AverageClusterDistanceCalculation(List<double> averageClusterDistance, double[,] distances, List<int> numberCluster, int MapSize, int currentClusterNumber) {
      int m = 0;
      for (int i = 0; i < MapSize; i++) {
        if (numberCluster[i] == currentClusterNumber) {
          averageClusterDistance.Add(0);
          for (int j = 0; j < MapSize; j++) {
            if (numberCluster[j] == currentClusterNumber)
              averageClusterDistance[m] += Math.Abs(distances[i, j]);
          }
          m++;
        }
      }
    }


  }
}