import java.applet.Applet; import java.util.*; import java.awt.*; /** * Dieses Applet implementiert das k-means Verfahren. Dieses ist ein unüberwachtes * 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ält alle Merkmalsvektoren */ Vector Centroids; /** Enthält die Schwerpunkte der Cluster */ Choice SubsetChoice; /** Steuerelement */ Button StartButton,RestartButton,ResetButton,RunButton,DrawGButton; /** Buttons*/ Checkbox history; /** Checkbox */ Thread Go; /** Thread für 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; } /** Überprüfung, 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ür 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; i0) { changes += Point.distance(p.x,p.y,m.x/Count, m.y/Count); Point pt = new Point(); pt.x = p.x; pt.y = p.y; p.History.addElement(pt); p.x = m.x / Count; p.y = m.y / Count; } } if (changes<0.1) abort = true; step = 3; } } /** Enthält Informationen der Clusterschwerpunkte, wie Position und Color, aber * auch eine Draw-Methode zum Zeichnen der Schwerpunkte. * Außerdem werden die Schwerpunkte aus jedem Schleifendurchlauf gespeichert, um * den Weg, den die Clusterschwerpunkte von Iteration zu Iteration zurücklegen, * darstellen zu können. */ class Quad { static public final int shapeRadius = 12; Color color; Vector History; int x; int y; boolean hist; void draw(Graphics g) { if ((hist==true) && (History.size()>0)) { Point p1,p2; g.setColor(Color.black); for (int i = 0;i