K-means¶

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

using System;
using System.IO;
using System.Globalization;
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][];;
            clusters = new string[nbObservations];
            for (int o = 0; o < nbObservations; o++)
            {
                splittedLine = input.ReadLine().Split();
                M[o] = new double[nbVariables];
                for (int v = 0; v < nbVariables; v++)
                {
                    M[o][v] = double.Parse(splittedLine[v], CultureInfo.InvariantCulture);
                    mini[v] = Math.Min(M[o][v], mini[v]);
                    maxi[v] = Math.Max(M[o][v], maxi[v]);
                }
                clusters[o] = splittedLine[nbVariables];
            }
        }
    }

    public void Dispose()
    {
        if (localsolver != null)
            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][];
        for (int o = 0; o < k; o++)
        {
            x[o] = new LSExpression[nbVariables];
            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]");
            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);
            }
        }
    }
}