source: branches/2988_ModelsOfModels2/HeuristicLab.Algorithms.EMM/EMMClustering.cs @ 16760

#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.Collections.Generic;
using System.Linq;

namespace HeuristicLab.Algorithms.EvolvmentModelsOfModels {
  public class EMModelsClusterizationAlgorithm {
    public int K { get; private set; }
    public EMModelsClusterizationAlgorithm() {
    }
    public EMModelsClusterizationAlgorithm(int k) {
      K = k;
    }
    public EMModelsClusterizationAlgorithm(EMModelsClusterizationAlgorithm 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 void ApplyFullConectedMapCreationAlgorithm(IRandom random, double[,] distances, List<List<int>> map, int k, int neghboorNumber = 10) {
      int mapSize = distances.GetLength(0);
      List<double> currentList = new List<double>();
      for (int i = 0; i < mapSize; i++) {
        map.Add(new List<int>());
        for (int j = 0; j < mapSize; j++) {
          currentList.Add(distances[i, j]);
        }
        map[i].Add(ChooseMinElement(currentList));
        while (map[i].Count < neghboorNumber) {
          map[i].Add(ChooseMinElement(currentList, i, map[i]));
        }
        currentList.Clear();
      }
    }
    private static bool CheckNumberIsInList(int number, List<int> priviousNumber) {
      foreach (var pNum in priviousNumber) {
        if (number == pNum)
          return true;
      }
      return false;
    }
    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;

      while (flag) {
        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, mapSize, distances, i, k);
          clusters[numberCluster[i]].Add(numberCluster[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][ChooseMinElement(averageClusterDistance)];
          if (newCentroid != centroids[i]) {
            flag = true;
            centroids[i] = newCentroid;
          }
          averageClusterDistance.Clear();
        }
      }
      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, int MapSize, 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(i - iter);
          iter++;
        }
      }
      k -= iter;
      return k;
    }
    private 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] += distances[i, j];
          }
          m++;
        }
      }
    }
    private static int ChooseMinElement(List<double> averageClusterDistance) {
      double minValue = averageClusterDistance[0];
      int minElementNumber = 0;
      for (int i = 1; i < averageClusterDistance.Count(); i++) {
        if (averageClusterDistance[i] < minValue) {
          minValue = averageClusterDistance[i];
          minElementNumber = i;
        }
      }
      return minElementNumber;
    }
    private static int ChooseMinElement(List<double> distances, int currentElement, List<int> previousNumbers) {
      double minValue = 100;
      int minElementNumber = 0;
      int temp = 0, i = 0;
      while (temp == 0) {
        if ((currentElement != i) && (!CheckNumberIsInList(i, previousNumbers))) {
          minValue = distances[i];
          minElementNumber = i;
          temp = i;
        }
        i++;
      }
      for (i = 0; i < distances.Count(); i++) {
        if ((distances[i] < minValue) && (currentElement != i) && (!CheckNumberIsInList(i, previousNumbers))) {
          minValue = distances[i];
          minElementNumber = i;
        }
      }
      return minElementNumber;
    }
  }
}