Suche Clustering Verfahren

Hallo,

ich suche nach einem Clustering Verfahren für den folgenden Fall:

Gegeben sind Punkte im 3D (etwa 40 Stück).
Ich weiß, dass es zwei cluster (eigentlich 3 aber dazu gleich mehr) gibt.
Es gibt also Punkte die zum Cluster C1 gehören. Punkte die zum Cluster C2 gehören aber auch Punkte die zu keinem der beiden Cluster gehören. (Dies könnte als 3. Cluster bezeichnet werden)

Ich kenne die Verteilung der Punkte in die Cluster nicht, noch kenne ich die Clustergrößen. Ich kann aber sicher sein, dass die beiden Cluster nicht leer sind.

Mit welchem Verfahren könnte ich die Punkte zuordnen und die beiden Cluster finden? (Alle 40 Punkte stehen gleichzeitig zur Verfügung)

SeppJ

Nur um sicher zu sein: Cluster zeichnen sich dadurch aus, dass man von jedem Punkt des Clusters zu einem anderen Punkt des Clusters kommen kann, indem man auf einem Weg von Clusterpunkt zu Clusterpunkt springt und dabei eine gewisse Höchstsprunglänge nie überschreiten muss?

Ein Standardverfahren ist wohl
http://de.wikipedia.org/wiki/K-Means-Algorithmus
( google weiß alles )

Wie du die "nicht zugehörigen" Punkte behandelst, scheint das schwerste Problem. Möglicherweise könnte es auch nützlich sein, diese nicht nur als einen dritten, sondern als mehrere zusätzliche Cluster zu behandeln.

Angenommen, du hättest deine Punktwolke schon in drei Teile zerlegt. Wie erkennst du denn, welches der "überflüssige" Cluster ist?

Aus Neugier habe ich gerade mal etwas weiter geschaut:
http://de.wikipedia.org/wiki/DBSCAN
Falls deine "zusätzlichen Punkt" irgendeine Form von Rauschen sind, könnte das auch interessant sein.

Mups schrieb:

Aus Neugier habe ich gerade mal etwas weiter geschaut:
http://de.wikipedia.org/wiki/DBSCAN
Falls deine "zusätzlichen Punkt" irgendeine Form von Rauschen sind, könnte das auch interessant sein.

Danke, dass sieht doch schon mal vielversprechend aus.

Nur um sicher zu sein: Cluster zeichnen sich dadurch aus, dass man von jedem Punkt des Clusters zu einem anderen Punkt des Clusters kommen kann, indem man auf einem Weg von Clusterpunkt zu Clusterpunkt springt und dabei eine gewisse Höchstsprunglänge nie überschreiten muss?

Ja schon, diese Höchstsprunglänge kann dann der räumliche Abstand der Punkte zueinander sein. Aber ich weiß nicht wie "dicht" die Punkte im Cluster sind.
Sonst könnte ich ja einen Scghwellwertoperator verwenden und den Abstand der Punkte zueinander. Aber wenn ich den Schwellwert für den Abstand zu klein wähle sind die beiden Cluster fast leer und das Cluster mit den "nicht zugehörigen Punkten" voll. Bei einem zu großen Schwellwert sind zu viele der eigentllich "nicht zugehörigen Punkte" in den Clustern.

Wenn man sich ein Bild mit den Punkten ansieht ist für einen Menschen die Einteilung in die Cluster total trivial. Aber das so zu berechnen, wie es ein Mensch intuitiv gemacht hätte ist wirklich schwer.