K-tool Algorithm with several parameters

Question

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

Please find the code snippet below.

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 will be an infinite loop. Alternatively, two points on the map are assigned to two different clusters. At each iteration, the centroids of these two clusters change. 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 refer to this link for the basic Kmeans algorithm: http://www.dataonfocus.com/k-means-clustering-java-code/

Answer 1

It can usually be shown that the K-means algorithm never repeats the assignment of nodes to clusters from the previous iteration.

Perhaps this is possible in your case due to the additional cost restriction that you introduced, which is traditionally not present when using K-funds, but perhaps this is still not the case, I'm not sure.

I am wondering how you use this assignCluster() method for which you provided the code. Do you have another loop around it that calls the assignCluster() call with finalClusters = list of the last cluster assignments and clusterNodes = list of all nodes and continues the loop until it finishes the assignment equal to the previous one?

If so, are you sure that cluster.addClusterNode() correctly removes the node from its previous cluster (I suppose it should if you implemented it as described above?). Another thing you can pay attention to is the calculation (cluster.getTotalDemand() + node.getCost()) . I suspect that if you look at the cluster that this node is already included, you may not include node.getCost() in this calculation, since it will be considered double if it is also included in cluster.getTotalDemand() .

I had to make some assumptions about what exactly you want to do for the code, or how you implemented other methods for which the code does not appear ... so you need to indicate if there are any errors in my assumption.

Answer 2

Looking at the code that you provided with your question and the link, I see no reason for an infinite loop (provided that you adapted the code correctly), except for the possibility that the total number of clusters multiplied by the maximum cost of one cluster is less total cost of all nodes together. You can verify this by iterating over all nodes before entering the loop.

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

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