kmeans.java

kmeans算法的java实现

import java.applet.Applet;
import java.util.*;
import java.awt.*;

/**
 * Dieses Applet implementiert das k-means Verfahren. Dieses ist ein un黚erwachtes
 * Klassifikationsverfahren (auch Clustering Verfahren genannt), mit dem sich 
 * Merkmalsvektoren im Merkmalsraum in Ballungszentren bzw. Cluster aufteilen 
 * lassen. 
 * 
 * @author Jens Spehr
 *
 */

public class Kmeans extends Applet implements Runnable {
   Vector  CrossList; /** Enth鋖t alle Merkmalsvektoren */
   Vector  Centroids; /** Enth鋖t die Schwerpunkte der Cluster */
   Choice  SubsetChoice; /** Steuerelement */
   Button StartButton,RestartButton,ResetButton,RunButton,DrawGButton; /** Buttons*/
   Checkbox history; /** Checkbox */
   
   Thread Go;  /** Thread f黵 den Run-Modus. */
   int step;   /** Aktueller Schritt, in dem sich der Algorithmus befindet. */
   int subset; /** Anzahl der Cluster */ 
   Random rand; /** Zufallsvariable*/
   boolean abort; /** Abbruchkriterium */
   
   /** Erstellt das Graphic User Interface (GUI). */
   public void init() {
      rand = new Random();
      Centroids = new Vector();
    
      StartButton = new Button("Start");
      add(StartButton);
      StartButton.setEnabled(false);
      
      RestartButton = new Button("New Start");
      add(RestartButton);
      RestartButton.setEnabled(false);
      
      ResetButton = new Button("Reset");
      add(ResetButton);
      ResetButton.setEnabled(false);
      
      RunButton = new Button("Run");
      add(RunButton);
      RunButton.setEnabled(false);
      
      DrawGButton = new Button("Draw Cluster");
      add(DrawGButton);
      
      CrossList = new Vector();
      
      SubsetChoice = new Choice();
      SubsetChoice.addItem("2");
      SubsetChoice.addItem("3");
      SubsetChoice.addItem("4");
      SubsetChoice.addItem("5");
      SubsetChoice.addItem("6");
      SubsetChoice.addItem("7");
      SubsetChoice.addItem("8");
      add(SubsetChoice);
      
      history = new Checkbox("Show History");
      add(history);
      
      subset = 2;
      step = -1;
   }
   
   
   /** Zeichnet den Text, die Merkmalsvektoren und die Clusterschwerpunkte. */
   public void paint(Graphics g) 
   {
        g.setColor(Color.BLACK);
        g.drawRect(0, 50, 499, 300); 
      
        StringBuffer buffer;
        if (step == 1)    g.setColor(Color.red);
        else g.setColor(Color.black);
	buffer = new StringBuffer("Step 1: Place ranomly initial group centroids into the 2d space.");	
	g.drawString(buffer.toString(),2, 370);
        
         if (step == 2)     g.setColor(Color.red);
        else g.setColor(Color.black);
	buffer = new StringBuffer("Step 2: Assign each object to the group that has the closest centroid.");	
	g.drawString(buffer.toString(),2, 385);
        
         if (step == 3)     g.setColor(Color.red);
        else g.setColor(Color.black);
	buffer = new StringBuffer("Step 3: Recalculate the positions of the centroids. ");	
	g.drawString(buffer.toString(),2, 400);
        
        if (step == 4)     g.setColor(Color.red);
        else g.setColor(Color.black);
	buffer = new StringBuffer("Step 4: If the positions of the centroids didn't change go to the next step, else go to Step 2.");	
	g.drawString(buffer.toString(),2, 415);
                
        if (step == 5)     g.setColor(Color.red);
        else g.setColor(Color.black);
	buffer = new StringBuffer("Step 5: End.");	
	g.drawString(buffer.toString(),2, 430);
        
        // Zeichnet die Merkmalsvektoren
        Cross s;
        int numShapes = CrossList.size();
        for (int i = 0; i < numShapes; i++) 
        {
            s = (Cross) CrossList.elementAt(i); 
            s.draw(g);  
        }
        // Zeichnet die Clusterschwerpunkte
        if (step != -1) 
        {
            Quad t = new Quad();
            int numCent = Centroids.size();
            for (int i = 0; i < numCent; i++) 
            {
                t = (Quad) Centroids.elementAt(i);
                t.hist = history.getState();
          
                t.draw(g);  
            }
        }
    
   }
   
   /** Erzeugt einen neuen Merkmalsvektor durch einen Mausklick. */
   public boolean mouseUp(Event e, int x, int y) {
   
      if ((step == -1) && (allowedMousePosition(x,y)== true))
      {
          ResetButton.setEnabled(true);
          StartButton.setEnabled(true);
          RunButton.setEnabled(true);
          
          Cross s = new Cross();  
   
          s.color = Color.black;
          s.x = x;
          s.y = y;
          CrossList.addElement(s);

          repaint();
      }
      
      return true;
   }
   
   /** 躡erpr黤ung, ob die aktuelle Mausposition erlaubt ist. */
   public boolean allowedMousePosition(int x, int y)
   {
       if ((x>=5)&&(y>=55)&&(x<595)&&(y<345)) return true;
       else return false;
   }
   
   /** Automatisches Durchlaufen des k-means Verfahrens. In einem Schritt wird
    * f黵 ca. 100ms verweilt. */
   public void run() {
	while (true) {
                if      (step ==-1) this.step1();
                else if (step == 1) this.step2();
                else if (step == 2) this.step3();
                else if (step == 3) step = 4;
                else if ((step == 4) && (abort==true))
                {
                    RestartButton.setEnabled(true);
                    ResetButton.setEnabled(true);
                    step = 5;
                    repaint();
                    Go.stop();
                }
                else if ((step == 4) && (abort==false))    this.step2();   
                repaint();
		try {			// Thread erfordert Ausnahme-Handler (try-catch-Klausel)
		Thread.sleep(100);
		}
		catch (InterruptedException e) {
		}
	}
}
   
   /** Managen der Button Ereignisse. */
   public boolean action(Event event, Object eventobject)
   {				
        if ((event.target==StartButton))
        {
            StartButton.setLabel("Step");
            RestartButton.setEnabled(true);
            if      (step ==-1) this.step1();
            else if (step == 1) this.step2();
            else if (step == 2) this.step3();
            else if (step == 3) step = 4;
            else if ((step == 4) && (abort==true))
            {
                StartButton.setEnabled(false);
                RunButton.setEnabled(false);
                step = 5;
            }
            else if ((step == 4) && (abort==false))    this.step2();   
            repaint();
            return true; 
        } 
         if ((event.target==RunButton))
        {
         
            Go = new Thread(this);
            Go.start();
            StartButton.setEnabled(false);
            RestartButton.setEnabled(false);
            ResetButton.setEnabled(false);
            RunButton.setEnabled(false);
         
            return true; 
        } 
        if ((event.target==DrawGButton))
        {
            if (CrossList.size()>0)  Reset();
           
            String SubsetString = SubsetChoice.getSelectedItem();
            if (SubsetString.equals("2")) subset = 2;
            if (SubsetString.equals("3")) subset = 3;
            if (SubsetString.equals("4")) subset = 4;
            if (SubsetString.equals("5")) subset = 5;
            if (SubsetString.equals("6")) subset = 6;
            if (SubsetString.equals("7")) subset = 7;
            if (SubsetString.equals("8")) subset = 8;
              
            // Erstelle Gausverteilungen
            Vector  GaussianList;
            GaussianList = new Vector();
            for (int i = 0; i<subset;i++)
            {
                Gaussian gaus = new Gaussian();  
                // Initialisiere Erwartungswert
                gaus.mux = 50 + Math.abs(rand.nextInt() % 450);
                gaus.muy = 75 + Math.abs(rand.nextInt() % 275);
                // Initialisiere Standardabweichung
                gaus.sigma = 10 + Math.abs(30 * rand.nextDouble());
             
                GaussianList.addElement(gaus);
            }
            ResetButton.setEnabled(true);
            StartButton.setEnabled(true);
            RunButton.setEnabled(true);
      
            // Erzeuge die Merkmalsvektoren
            for (int i = 0; i<subset;i++)
            {
                // W鋒le Gausverteilung
                Gaussian gaus;
                gaus = (Gaussian) GaussianList.elementAt(i);
                // Erzeuge die Merkmalsvektoren f黵 das ausgew鋒lte Cluster
                for (int j = 0;j<2800/subset;j++)
                {
                    // Zur Performance-Steigerung wird hier keine "echte"