K-means Algorithm with multiple parameters

Question

I have a set of points on the map. I'm trying to create clusters. Along with the distance, I'm considering the maximum cost (as another parameter) of the each cluster.

Please find the below code snippet.

private void assignCluster(List<Cluster> finalClusters, List<Node> clusterNodes, int maxCostLimit) {
    double max = Double.MAX_VALUE;
    double min = max;
    int clusterIndex = 0;
    double distance = 0.0;

    for (Node node : clusterNodes) {
        min = max;
        for (int i = 0; i < finalClusters.size(); i++) {
            Cluster cluster = finalClusters.get(i);
            distance = Point.getDistanceBetweenPoints(node.getPoint(), cluster.getPoint());
            if (distance < min && (cluster.getTotalCost() + node.getCost()) <= maxCostLimit) {
                min = distance;
                clusterIndex = i;
            }
        }
        if (min != max) {
            Cluster cluster = finalClusters.get(clusterIndex);
            cluster.setTotalCost(cluster.getTotalCost() + node.getCost());
            cluster.addClusterNode(node);
        }
    }
}

If I try to create clusters, it is going to infinite loop. Alternatively, two points on the map are getting assigned to the two different clusters. In each iteration, the centroids of these two clusters are changing. Please suggest me, How can I achieve this?

EDITS

Cluster.java

public class Cluster{
    private List<Node> clusterNodes = new ArrayList<Node>();
    private Integer totalCost = 0;
    private Point2D point;

         //getters and setters
}

Point.java

public class Point{
    private double x = 0;
    private double y = 0;

        // getters and setters

       //method to find the distance between 2 points
}

I'm referring this link for basic Kmeans Algorithm : http://www.dataonfocus.com/k-means-clustering-java-code/

Answer 1

Normally, the K-means algorithm can be shown to never repeat an assignment of nodes to clusters from a previous iteration.

Maybe this is possible in your case, due to the extra constraint of costs that you have introduced that is traditionally not present when using K-means, but maybe it still isn't, I'm not sure.

I am wondering about how you are using this assignCluster() method for which you have provided the code. Do you have another loop around it which keeps calling assignCluster() with finalClusters = a list of the latest assignments of clusters, and clusterNodes = a list of all nodes, and keeps looping until it ends up with an assignment that is equal to the previous one?

If so, are you sure that cluster.addClusterNode() correctly removes the node from its' previous cluster (as I assume it should if you implemented it as described above?). Another thing to look at may be the (cluster.getTotalDemand() + node.getCost()) calculation. I suspect that, if you happen to be looking at the cluster that this node is already in, you may not want to include node.getCost() in that calculation, since it'll be counted double if it's also included in cluster.getTotalDemand().

I had to make some assumptions about what exactly you want the code to do, or how you implemented other methods for which the code is not shown... so you'll have to point out if there are any errors in my assumptions.

Answer 2

Looking at the the code you provided with your question and through the link, I cannot see any reason for an infinite loop (assuming that you adapted the code correctly) except of the possibility, that the total number of clusters multiplied with the maximum cost per cluster is smaller than the total cost of all nodes together. You could check that by iterating over all nodes before entering the loop.

Another problem could be, that you forgot to reset the totalCost per cluster in your clearClusters() method, but I think that would not lead to an infinite loop.

Why is your centroid of class-type Point2D and not an object of your own Point class?