K-means¶

/********** kmeans.cs **********/

using System;
using System.IO;
using localsolver;

public class Kmeans : IDisposable
{
    /* Data properties */
    int nbObservations;
    int nbVariables;
    int k;

    double[,] M;
    string[] clusters;

    // mini[v] and maxi[v] are respectively the minimum and maximum of the vth variable
    double[] mini;
    double[] maxi;

    /* Solver. */
    LocalSolver localsolver;

    /* Decisions. */
    LSExpression[,] x;

    /* Objective. */
    LSExpression obj;

    public Kmeans(int k)
    {
        localsolver = new LocalSolver();
        this.k = k;
    }

    /* Reads instance data */
    public void ReadInstance (string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {       
            string[] splittedLine = input.ReadLine().Split();

            nbObservations = int.Parse(splittedLine[0]);
            nbVariables = int.Parse(splittedLine[1]);

            mini = new double[nbVariables];
            maxi = new double[nbVariables];
            for (int v = 0; v < nbVariables; v++)
            {
                mini[v] = double.PositiveInfinity;
                maxi[v] = double.NegativeInfinity;
            }
            M = new double[nbObservations,nbVariables];
            clusters = new string[nbObservations];
            for (int o = 0; o < nbObservations; o++) 
            {
                splittedLine = input.ReadLine().Split();
                for (int v = 0; v < nbVariables; v++)
                {
                    M[o,v] = double.Parse(splittedLine[v]);
                    if (M[o,v] < mini[v]) mini[v] = M[o,v];
                    if (M[o,v] > maxi[v]) maxi[v] = M[o,v];
                }
                clusters[o] = splittedLine[nbVariables];
            }
        }
    }

    public void Dispose ()
    {
        localsolver.Dispose();
    }

    public void Solve(int limit)
    {
        /* Declares the optimization model */
        LSModel model = localsolver.GetModel();

        // x[c][v] is the coordinate for the center of gravity of the cluster c along the variable v
        x = new LSExpression[k,nbVariables];
        for (int o = 0; o < k; o++) 
        {
            for (int v = 0; v < nbVariables; v++)
            {
                x[o,v] = model.Float(mini[v] ,maxi[v]);
            }
        }

        // d[o] is the distance between observation o and the nearest cluster (its center of gravity)
        LSExpression[] d = new LSExpression[nbObservations];
        for (int o = 0; o < nbObservations; o++)
        {
            d[o] = model.Min();
            for (int c = 0; c < k; c++)
            {
                LSExpression distanceCluster = model.Sum();
                for (int v = 0; v < nbVariables; v++)
                {
                    distanceCluster.AddOperand(model.Pow(x[c, v] - M[o, v], 2));
                }
                d[o].AddOperand(distanceCluster);
            }
        }

        // Minimize the total distance
        obj = model.Sum(d);
        model.Minimize(obj);

        model.Close();

        /* Parameterizes the solver. */
        LSPhase phase = localsolver.CreatePhase();
        phase.SetTimeLimit(limit);

        localsolver.Solve();  
    }

    /* Writes the solution in a file in the following format:
     *  - objective value
     *  - k
     *  - for each cluster, the coordinates along each variable
     */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(obj.GetDoubleValue());
            output.WriteLine(k);
            for (int c = 0; c < k; c++)
            {
                for (int v = 0; v < nbVariables; v++)
                {
                    output.Write(x[c, v].GetDoubleValue() + " ");
                }
                output.WriteLine();
            }
            output.Close();
        }
    }
    
    public static void Main(string[] args)
    {
          if (args.Length < 1)
        {
            Console.WriteLine("Usage: Kmeans inputFile [outputFile] [timeLimit] [k value]");
            System.Environment.Exit(1);
        }

        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "5";
        string k = args.Length > 3 ? args[3] : "2";
        using (Kmeans model = new Kmeans(int.Parse(k)))
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if(outputFile != null)
            {
                model.WriteSolution(outputFile);
            }
        }
    }
}