Untitled

                Never    
Java
       
package s26;
import java.awt.Point;
import java.util.List;
import java.util.Random;

import java.util.ArrayList;
import java.util.Arrays;
//======================================================================
@SuppressWarnings("serial")
class Cluster extends Point {
  List<Point> pts;
  // ----------------------------------------
  @Override public String toString() {
    return "["+pts.size() +" points, centered on "+x+" "+y+"]";
  }
  // ----------------------------------------
  public Cluster(Cluster a, Cluster b) {
    this(a.pts);pts.addAll(b.pts);
    recomputeCenter();
  }
  // ----------------------------------------
  public Cluster(List<Point> points) {
    pts = new ArrayList<Point>(points);
    recomputeCenter();
  }
  // ----------------------------------------
  public void addPoint(Point p) {
    pts.add(p); 
  }
  // ----------------------------------------
  public void removeAllMembers() {
    pts = new ArrayList<Point>();
  }
  // ----------------------------------------
  // RETURNS: whether the coordinates have changed 
  //          since the last call of the method
  public boolean recomputeCenter() {
    int oldX=x, oldY=y;
    x=0; y=0;
    int n = pts.size();
    for (Point p:pts) {
      x += p.x; y += p.y;
    }
    if (n!=0) {x/=n; y/=n;}
    return (oldX!=x || oldY!=y);
  } 
}
// ======================================================================
public class Clustering {
  static Random r = new Random();
  // ----------------------------------------------------------------------
  static void rndPermutation(int [] t) {
    int aux, j;
    for (int i=1; i<t.length; i++) {
      j = r.nextInt(i+1);
      aux = t[i]; t[i]=t[j]; t[j]=aux;
    }
  }
  // ----------------------------------------------------------------------
  public static List<Cluster> initKMeans(List<Point> pts, int nbOfClusters) {
    int n=pts.size();
    assert(nbOfClusters<n);
    List<Cluster> clusters = new ArrayList<Cluster>();
    int t[] = new int [n];
    for (int i=0; i<n; i++) t[i]=i;
    rndPermutation(t);
    for (int i=0; i<nbOfClusters; i++) {
      clusters.add(new Cluster(Arrays.asList(pts.get(t[i%n]))));
    }
    return clusters;
  }
  // ----------------------------------------------------------------------
  private static Cluster closestCluster(List<Cluster> clusters, Point p) {
    double closestDist=Double.POSITIVE_INFINITY;
    Cluster closest=null;
    for(Cluster c:clusters) {
      double d = p.distance(c);
      if  (d<closestDist) { closestDist=d; closest=c; }
    }
    return closest;
  }
  // ----------------------------------------------------------------------
  public static void kMeans(List<Cluster> clusters, List<Point> pts) {
    boolean stable;
    do {
      // remove all points in every cluster
      for (Cluster clust: clusters) {
        clust.removeAllMembers();
      }
      // add each point to its closest cluster
      for (Point pt: pts) {
        closestCluster(clusters,pt).addPoint(pt);
      }
      // recompute clusters centers
      boolean changed = false;
      for (Cluster clust: clusters) {
        changed|=clust.recomputeCenter();
      }
      stable = !changed;
    } while (!stable);         
  }

  // ----------------------------------------------------------------------
  public static List<Cluster> initHierarchical(List<Point> pts) {
    List<Cluster> clusters = new ArrayList<Cluster>();
    // create one cluster per point
    for (Point pt : pts) {
      ArrayList pointList = new ArrayList();
      pointList.add(pt);
      Cluster clust = new Cluster(pointList);
      clusters.add(clust);
    }
    return clusters;
  }
  // ----------------------------------------------------------------------
  public static void hierarchical(List<Cluster> clusters, int nbOfClusters) {
    while(clusters.size()>nbOfClusters){
      double closestDist = Double.POSITIVE_INFINITY;
      Cluster[] clustPair = new Cluster[2];
      for (Cluster clust:
           clusters) {
        ArrayList<Cluster> temporaryClusters = (ArrayList)((ArrayList) clusters).clone();
        temporaryClusters.remove(clust);
        Cluster pairClust = closestCluster(temporaryClusters,clust);
        if(clust.distance(pairClust)<closestDist){
          clustPair = new Cluster[]{clust,pairClust};
          closestDist = clust.distance(pairClust);
        }
      }
      clusters.remove(clustPair[0]);
      clusters.remove(clustPair[1]);
      clusters.add(new Cluster(clustPair[0],clustPair[1]));
    }
  }
}

Raw Text