Java Punktwolke aufteilen

[CPU]

Hallo,

ich habe eine Menge von Punkten (siehe Anhang). Wenn man die Punke in einem Koordinatensystem aufträgt, so kann man drei Konzentrationen der Punkte erkennen.

Wie kann ich die Punkte diesen drei Konzentrationen zuordnen? D.h. ich habe am Ende z.B. drei Arrays für die drei Punktwolken mit den Punkten (über eine geeignete Datenstruktur lässt sich streiten ...).

Der KMeans-Algorithmus scheint mir am besten geeignet zu sein, doch ich finde über Google keine passende Implementierung, wo ich die Punkte reingebe und ein sinnvolles Ergebnis bekomme.
Ich habe lediglich diese Implementierung gefunden, doch da ist immer die zweite Menge leer.

Vielleicht bin ich ja auf dem falschen Dampfer

CPU :-(

 

[Limit]

Wieso implementierst du den Algo nicht selbst? Er gehört ja nicht unbedingt zu den kompliziertesten.

Ich hatte gerade nichts zu tun und wollte meine Javakentnisse ein wenig aufpolieren. Daher habe ich das ganze mal implementiert. Es ist in keinster Weise optimiert und ich habe mir das Ergebnis auch nur mal grob angesehen. Bei ungünstig gewählten Startpunkten kommt halt kein so schönes Ergebnis heraus, was bei meiner Implementierung noch verstärkt wird, da er einfach die ersten 3 Punkte als Startpunkte nimmt.

Nunja, hier also die 3 Klassen...

public class Punkt {
	public double x;
	public double y;
	
	public Punkt(double x, double y) {
		this.x = x;
		this.y = y;
	}
	
	public double berechneAbstand(Punkt pkt) {
		double diffX = this.x - pkt.x;
		double diffY = this.y - pkt.y;
		return Math.sqrt(Math.pow(diffX, 2) + Math.pow(diffY, 2));
	}
	
	public String toString() {
		return "(" + x + "," + y + ")";
	}
}

import java.util.*;

public class Wolke {
	public Set<Punkt> punkte;
	
	public Wolke(Punkt p) {
		this.punkte = new HashSet<Punkt>();
		this.punkte.add(p);
	}
	
	
	public Punkt berechneSchwerpunkt() {
		double sumX = 0;
		double sumY = 0;
		int anzPkte = this.punkte.size();
		
		for (Iterator<Punkt> it = this.punkte.iterator(); it.hasNext(); ) {
			Punkt p = it.next();
			sumX += p.x;
			sumY += p.y;
		}
		
		return new Punkt((sumX / anzPkte), (sumY / anzPkte));
	}
}

import java.io.*;
import java.util.*;

public class Test {
	
	public static Set<Punkt> Punkte;
	public static List<Wolke> Wolken;
	
	public static void sucheNächstenPunkt(Wolke wolke) {
		Punkt minP = null;
		Punkt schwerpunkt = wolke.berechneSchwerpunkt();
		double minAbstand = Double.MAX_VALUE;
		
		for (Iterator<Punkt> it = Punkte.iterator(); it.hasNext(); ) {
			Punkt p = it.next();
			double abstand = p.berechneAbstand(schwerpunkt);
			
			if (minAbstand > abstand) {
				minP = p;
				minAbstand = abstand;
			}
		}
		Punkte.remove(minP);
		wolke.punkte.add(minP);
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		
		// Parameter parsen
		String dateiname = args[0];
		int anzahlWolken = Integer.parseInt(args[1]);
		
		// Datenstrukturen anlegen
		Test.Punkte = new HashSet<Punkt>();
		Test.Wolken = new ArrayList<Wolke>();
		
		// Punktliste einlesen
		int x, y;
		Scanner scanner = new Scanner(new File(dateiname)); 
		while (scanner.hasNextInt()) {
			x = scanner.nextInt();
			
			if (scanner.hasNextInt()) 
				y = scanner.nextInt();
			else
				break;
			
			Punkte.add(new Punkt(x,y));
		}

		// Wolken initialiseren
		Iterator<Punkt> punktIterator = Punkte.iterator();
		for (int i = 0; i < anzahlWolken; i++)
			Wolken.add(new Wolke(punktIterator.next()));
	
		// füge Punkte zu Wolken hinzu
		int i = 0;
		while (!Punkte.isEmpty()) {
			sucheNächstenPunkt(Wolken.get(i));
			i = (i + 1) % anzahlWolken;
		}
		
		// Ausgabe
		for (i = 0; i < anzahlWolken; i++) {
			System.out.println("\n\nWolke #" + i);
			for (Iterator<Punkt> it = Wolken.get(i).punkte.iterator();
				 it.hasNext(); )
				System.out.println(it.next());
		}
	}

}

Die Test Klasse übernimmt als 1. Parameter einen Dateinamen mit den Punkten (z.B. die, die du hochgeladen hast) und als 2. Parameter die Zahl der Wolken.

 

[CPU]

Echt suuuper

Eigentlich traue ich mich ja nicht zu fragen, weil Du Dir schon so viel Arbeit gemacht hast ... aber lässt sich dieser Algorithmus noch in der Geschwindigkeit verbessern?

Vielen Dank!!!
CPU

 

[BerniG]

Das ist doch eh schon recht fix, wozu brauchst du das denn noch zusätzlich optimiert? Sicherlich kann man immer was machen aber bei mir läuft das mit den Daten grad mal ne Sekunde...

Zum Tuning könnte man an den eingesetzten Datenstrukturen arbeiten, das Erzeugen von Objekten verhindern (Iteratoren) und Funktionen inlinen (also Funktionsaufrufe verhindern indem man den Code fest einbaut). Schöner wird das Programm dadurch aber natürlich nicht

Evtl. bräuchte man das Hashset auch gar nicht (das Iterieren darüber ist nicht gerade effizient), bin mir da wegen den Algo aber ned ganz sicher. Außerdem sollte man glaub ich beim Punkt das Comparable-Interface implementieren (wobei es dadurch eher langsamer als schneller wird) um korrekte Vergleiche sicherzustellen (momentan wird auf gleiche Referenz verglichen).

 

[Limit]

Bei der Berechnung des Schwerpunkts könnt man die komplette Schleife raushauen. Statt jedesmal die ganzen Werte neu aufaddieren, speichert man irgendwo den Schwerpunkt. Wenn man dann ein neuen Punkt zur Wolke hinzufügt, rechnet man einfach

neuerSchwerpunkt.x = (alterSchwerpunkt.x * anzPkte + neuerPunkt.x) / (anzPkte + 1)

Entsprechend auch für y. Das sollte ein bisschen was rausholen. Ansonsten gibt es halt viel Finetuning, von dem BerniG ja ein paar Punkte angesprochen hat. Falls ich morgen Zeit/Lust habe, schau ich es mir nochmal an.

Ob man Referenzen vergleicht oder den Inhalt kommt drauf an, was gewollt ist. Evtl. soll es ja "aufeinander liegende" Punkte geben.

 

[BerniG]

Weitere Optimierungsmöglichkeiten:
- Berechnung in der berechneAbstand() mit long statt double. Allerdings ist dann die Wertemenge des Inputs bisschen eingeschränkt (man sprengt sonst den Wertebereich).
- Es ist in der berechneAbstand() unnötig, den genauen Abstand zu wissen sondern man will ja nur vergleichen. Man kann sich das Math.sqrt hier also völlig sparen. Ein Math.pow ist beim Quadrieren im Allgemeinen langsamer als eine normale Multiplikation. Zum Vergleichen also einfach nur "(diffX*diffx) + (diffY*diffY)" zurückgeben. Dies sollte einiges bringen; kam hier grad testweise nur durch diese Änderung auf 250ms statt 1s.

Was mir grad auffiel: Funktioniert das mit mehreren Durchläufen wirklich? Ich glaube fast dass das nicht ganz K-Means ist, denn eigtl. müssten die Wolken ja neu erzeugt werden aber das fehlt hier irgendwie?
Ich hätte mir ne maximaleffiziente Variante jetzt so gedacht:
- Ein Punkt speichert die Nummer der Wolke in der er ist
- Alle Punkte sind in einem Array
- die Schleife: Der boolean-Wert "changed" wird auf false gesetzt. Dann berechnet man das Zentrum so ähnlich wie bisher. Dann geht man das ganze Array durch und berechnet die Abstände zu den 3 Zentren. Ist das bisherige Zentrum ungleich dem neuen, so wird es neu gesetzt und der boolean-Wert "changed" auf true gesetzt. Die Schleife bricht ab sobald changed = false ist.

Edit: Ok habs mal gecoded. Ist ungetestet und kann Logikfehler enthalten. Hat eigtl. wenig mit Java zu tun und ist nicht wirklich schön, sollte aber recht effizient sein.
Hier mal die Test.java

package test;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;

public class Test {
	public static Punkt[] pkt;
	public static Wolke[] wlk;
	
	public static void main(String[] args) throws FileNotFoundException {
		// Parameter
		String dateiname = "punkte.txt";
		int anzahlWolken = 50;
		
		init(dateiname, anzahlWolken);
		long start = System.nanoTime();
		berechne();
		long time = (System.nanoTime() - start) / 1000000;
		System.out.println("Time taken: " + time + " ms");
		ausgabe();
	}
	
	public static void init(String dateiname, int anzahlWolken) throws FileNotFoundException{
		int x, y;
		Random rn = new Random();
		HashSet<Punkt> randomPoints = new HashSet<Punkt>();
		Punkt tmp;
		
		// Datenstrukturen anlegen (werden nur temporär genutzt
		ArrayList<Punkt> Punkte = new ArrayList<Punkt>();
		ArrayList<Wolke> Wolken = new ArrayList<Wolke>();		
		
		// Punktliste einlesen		
		Scanner scanner = new Scanner(new File(dateiname)); 
		while (scanner.hasNextInt()) {
			x = scanner.nextInt();
			
			if (scanner.hasNextInt()) y = scanner.nextInt();
			else break;
			
			Punkte.add(new Punkt(x,y));
		}		
		pkt = Punkte.toArray(new Punkt[0]);		// in Array wandeln
		
		// Wolkenzentrum zufällig setzen, Hashset nutzen damit kein Punkt doppelt als Zentrum gewählt wird
		if (anzahlWolken > pkt.length) anzahlWolken = pkt.length;		// mehr Wolken als Punkte machen keinen Sinn
		while(randomPoints.size() < anzahlWolken){
			randomPoints.add(pkt[rn.nextInt(pkt.length)]);
		}
		for (Iterator<Punkt> it = randomPoints.iterator(); it.hasNext(); ) {
			tmp = it.next();
			Wolken.add(new Wolke(tmp.x, tmp.y));
		}		
		wlk = Wolken.toArray(new Wolke[0]);		// in Array wandeln				
	}
	
	public static void berechne(){
		double minAbstand, abstand, diffX, diffY;
		int j, i, minP;
		// Berechnungsarrays for Wolken vorbereiten
		double sumX[] = new double[wlk.length];
		double sumY[] = new double[wlk.length];
		int cnt[] = new int[wlk.length];		
		
		// Objekte auf Wolken verteilen
		for (i = 0; i < pkt.length; ++i) {
			minAbstand = Double.MAX_VALUE;
			minP = 0;
			for (j = 0; j < wlk.length; ++j) {
				diffX = pkt[i].x - wlk[j].x;
				diffY = pkt[i].y - wlk[j].y;
				abstand = (diffX*diffX) + (diffY*diffY);
				
				if (minAbstand > abstand) {
					minP = j;
					minAbstand = abstand;
				}
			}
			pkt[i].wolke = minP;
		}
		
		boolean changed = true;
		while(changed){
			changed = false;
			
			// Wolkenzentren neu berechnen
			for (j = 0; j < wlk.length; ++j) {
				sumX[j] = 0;
				sumY[j] = 0;
				cnt[j] = 0;
			}
			for (i = 0; i < pkt.length; ++i) {
				sumX[pkt[i].wolke] += pkt[i].x;
				sumY[pkt[i].wolke] += pkt[i].y;
				++cnt[pkt[i].wolke];
			}
			for (j = 0; j < wlk.length; ++j) {
				// hier sollte man noch abfangen wenn cnt = 0...weiß aber nicht was man dann tut
				wlk[j].x = sumX[j] / cnt[j];
				wlk[j].y = sumY[j] / cnt[j];
			}
			
			// Objekte neu auf Wolken verteilen
			for (i = 0; i < pkt.length; ++i) {
				minAbstand = Double.MAX_VALUE;
				minP = 0;
				for (j = 0; j < wlk.length; ++j) {
					diffX = pkt[i].x - wlk[j].x;
					diffY = pkt[i].y - wlk[j].y;
					abstand = (diffX*diffX) + (diffY*diffY);
					
					if (minAbstand > abstand) {
						minP = j;
						minAbstand = abstand;
					}
				}
				if(pkt[i].wolke != minP){
					changed = true;
					pkt[i].wolke = minP;
				}
			}
		}
	}
	
	public static void ausgabe(){
		int i, j;
		for (j = 0; j < wlk.length; ++j) {
			System.out.println("\n\nWolke #" + j + " @ (" + wlk[j].x + "," + wlk[j].y + ")");
			for (i = 0; i < pkt.length; ++i) {
				if(pkt[i].wolke == j) System.out.println("(" + pkt[i].x + "," + pkt[i].y + ")");
			}
		}		
	}
}

Punkt.java

package test;
public class Punkt {
	public double x, y;
	public int wolke = 0;
	
	public Punkt(double x, double y) {
		this.x = x;
		this.y = y;
	}
}

Wolke.java:

package test;
public class Wolke {
	public double x, y;
	
	public Wolke(double x, double y) {
		this.x = x;
		this.y = y;
	}
}