K-means Algorytm o wielu parametrach

Question

Mam zestaw punktów na mapie. Próbuję tworzyć klastry. Wraz z odległością rozważam maksymalny koszt (jako inny parametr) każdego klastra.

Proszę znaleźć poniższy fragment kodu.

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); 
     } 
    } 
} 

Jeśli spróbuję utworzyć klastry, będzie to nieskończona pętla. Alternatywnie dwa punkty na mapie są przypisywane do dwóch różnych klastrów. W każdej iteracji zmieniają się centroidy tych dwóch klastrów. Proszę zasugerować mi, Jak mogę to osiągnąć?

edytuje

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 
} 

mam na myśli ten link podstawowej Kmeans algorytmu: http://www.dataonfocus.com/k-means-clustering-java-code/

Answer 1

Zwykle można pokazać, że algorytm może nigdy nie powtórzyć przypisania węzłów do klastrów z poprzedniej iteracji.

Być może jest to możliwe w twoim przypadku, ze względu na dodatkowe ograniczenie kosztów, które tradycyjnie nie występuje, gdy używasz K -móż, ale może nadal nie jest, nie jestem pewien.

Zastanawiam się, w jaki sposób używasz tej metody assignCluster(), dla której podałeś kod. Czy masz wokół niego kolejną pętlę, która wywołuje assignCluster() z finalClusters = listą ostatnich przydziałów klastrów i clusterNodes = listą wszystkich węzłów i utrzymuje w pętli, aż kończy się przypisaniem, które jest równe poprzedniej?

Jeśli tak, czy jesteś pewien, że cluster.addClusterNode() poprawnie usuwa węzeł z jego poprzedniego klastra (jak przypuszczam, powinien to zrobić, jeśli zaimplementowałeś go tak, jak opisano powyżej?). Kolejną rzeczą, na którą warto spojrzeć, może być obliczenie (cluster.getTotalDemand() + node.getCost()). Podejrzewam, że jeśli patrzysz na klaster, w którym znajduje się ten węzeł, możesz nie chcieć uwzględniać w tych obliczeniach wartości node.getCost(), ponieważ będzie ona policzona jako podwójna, jeśli jest to , a także zawarta w cluster.getTotalDemand().

Musiałem przyjąć pewne założenia co do tego, co dokładnie ma kodować, lub jak zaimplementować inne metody, dla których kod nie jest wyświetlany ... więc będziesz musiał wskazać, czy są jakieś błędy w moje założenia.

Answer 2

Patrząc na kod podany w pytaniu i przez łącze, nie widzę powodu dla nieskończonej pętli (zakładając, że poprawnie zaszyfrowałeś kod) z wyjątkiem możliwości, że całkowita liczba klastrów pomnożona przez maksymalny koszt na klaster jest mniejszy niż całkowity koszt wszystkich węzłów łącznie. Można to sprawdzić, wykonując iteracje po wszystkich węzłach przed wejściem do pętli.

Innym problemem może być, że zapomniałeś zresetować totalCost na grupę w swojej metodzie clearClusters(), ale myślę, że nie doprowadziłoby to do nieskończonej pętli.

Dlaczego twój centroid klasy typu Point2D nie jest obiektem z twojej własnej klasy Point?