Berechnen des geometrischen Medians von 2D-Punkten

Question

Ich berechne Geometric median von einigen (x,y) Punkten in Java. Um Geometric median zu berechnen, berechne ich zuerst centroid aller Punkte, dann centroid wird verwendet, um Geometric median zu berechnen. Mein Code funktioniert gut, aber manchmal geht es in eine Endlosschleife (denke ich.). Das Problem ist mit meinem while Zustand. Dieser while Zustand sollte sich entsprechend den Eingabepunkten ändern, aber ich weiß nicht wie. Darunter lege ich den kompletten Code ab.

import java.util.ArrayList; 

public class GeometricMedian { 

    private static ArrayList<Point> points = new ArrayList<Point>(); 

    private class Point { 
     private double x; 
     private double y; 

     Point(double a, double b) { 
      x = a; 
      y = b; 
     } 
    } 

    public static void main(String[] args) { 
     GeometricMedian gm = new GeometricMedian(); 
     gm.addPoints(); 
     Point centroid = gm.getCentroid(); 
     Point geoMedian = gm.getGeoMedian(centroid); 
     System.out.println("GeometricMedian= {" + (float) geoMedian.x + ", " 
       + (float) geoMedian.y + "}"); 
    } 

    public void addPoints() { 
     points.add(new Point(0, 1)); 
     points.add(new Point(2, 5)); 
     points.add(new Point(3, 1)); 
     points.add(new Point(4, 0)); 
    } 

    public Point getCentroid() { 
     double cx = 0.0D; 
     double cy = 0.0D; 
     for (int i = 0; i < points.size(); i++) { 
      Point pt = points.get(i); 
      cx += pt.x; 
      cy += pt.y; 
     } 
     return new Point(cx/points.size(), cy/points.size()); 
    } 

    public Point getGeoMedian(Point start) { 
     double cx = 0; 
     double cy = 0; 

     double centroidx = start.x; 
     double centroidy = start.y; 
     do { 
      double totalWeight = 0; 
      for (int i = 0; i < points.size(); i++) { 
       Point pt = points.get(i); 
       double weight = 1/distance(pt.x, pt.y, centroidx, centroidy); 
       cx += pt.x * weight; 
       cy += pt.y * weight; 
       totalWeight += weight; 
      } 
      cx /= totalWeight; 
      cy /= totalWeight; 
     } while (Math.abs(cx - centroidx) > 0.5 
       || Math.abs(cy - centroidy) > 0.5);// Probably this condition 
                // needs to change 

     return new Point(cx, cy); 
    } 

    private static double distance(double x1, double y1, double x2, double y2) { 
     x1 -= x2; 
     y1 -= y2; 
     return Math.sqrt(x1 * x1 + y1 * y1); 
    } 
} 

Bitte helfen Sie mir den Fehler zu beheben, auch wenn es einen besseren Weg exitis Geometric median einiger 2D-Punkte zu berechnen, hier schreiben. Vielen Dank.

Answer 1

Ich sehe nicht, warum Sie zwei Schleifen benötigen. Sie brauchen nur die Schleife über alle Punkte. Was ist Ihrer Meinung nach der Grund für den anderen?

Answer 2

Eine Möglichkeit, dies zu lösen, ist eine bestimmte Anzahl von Wiederholungen. Dies ähnelt der K-Means-Methode, bei der es entweder an einen bestimmten Schwellenwert konvergiert oder nach einer vordefinierten Anzahl von Iterationen stoppt.