Algorithmus zur Gruppieren unter der Berücksichtigung räumlicher Ausdehnung
-
Hallo,
ich benötige Hilfe bei einer Problemstellung.
Ich habe eine Reihe von Datenpunkten welche durch eine Position und eine Intensität gekennzeichnet sind.
Diese Datenpunkte möchte ich in eine maximale Anzahl von Gruppen unterteilen.
Es sollen möglichst viele Datenpunkte in Gruppen hinzugefügt werden.
Bei der Bildung der Gruppen ist wichtig das diese Gruppen(alle zusammen) eine vorgegebene räumliche Ausdehnug nicht überschreiten dürfen.
Die Gruppen dürfen unterschiedliche Ausdehnungen besitzen.
Es dürfen nur Datenpunkte gruppiert werden, die räumlich aneinander liegen.
Wenn nicht alle Datenpunkte mit den getroffenen vorgaben gruppiert werden können, ist das Kriterium möglichst viele, und diejenigen mit hohen Intensitäten zu gruppieren.
Für einen ersten Schritt könnte auch die Intensität erstmal nicht berücksichtigt werden.
Kann mit weniger als der maximalen Ausdehnung unter den Kriterien gruppiert werden sollen weniger Gruppen verwendet werden.
Leider komme ich mit dem Algorithmus seit einer Woche nicht weiter , ich finde einfach keinen guten Ansatz.
Ich wäre über Ratschläge und Ideen sehr Dankbar.
mfg Tobi
-
Google mal nach cluster analysis.
-
Das das Problem unter Cluster Analysis anzusiedeln ist weiß ich, jedoch ist es schwierig alle diese Kriterien zu vereinen das ist mein Problem ..mein erster Ansatz war ein k-means Ansatz
-
Ein bißchen mehr mußt du schon noch spezifizieren. Momentan könnte ich dir einfach jeeden Punkt in ein eigenes Cluster packen und nätte deine kriterien alle erfüllt. Hast du eine feste Clusterzahl (->Partitionierungsproblem) oder ist die zAhl variabel (->Clusteringproblem)?
-
Welche Dimension hat denn dein Raum?
-
Hallo,
die maximale Anzahl von Clustern wird vorgegeben.
Diese Vorgabe wäre mit einen einfachen k-means Ansatz zu erfüllen.
Wichtig ist aber das alle Cluster zusammen eine bestimmte räumliche Ausdehnung nicht überschreiten dürfen.
Die einzelnen Cluster dürfen unterschiedlich groß sein.
Für einen ersten Schritt hätte der Datenraum nur eine Dimension die Position.
Ziel ist es mit mit der maximalen räumlichen Ausdehnung aller Cluster möglichst viele Datenpunkte zu gruppieren.
gruß ETobi
-
klingt genau nach VQ compression, damit ergooglest du viele quellen, denk ich mir.
-
Und wieviel Koordinaten gehoeren zur Positions? ... So wie sich das anhoert willst du vielleicht eine Dichteschaetzung. Zentren deiner Cluster sind einfach die Maxima deiner Dichte. Von dort ausgehend kannst du deinen Cluster nach deinen Vorgaben wachsen lassen. MOeglichkeiten gibt es viele, ist aber von den Daten abhaengig.
edit: ja, vector quantization scheint sehr aehnlich zu sein. Die Frage ist nur, wie bestimmt man das Codewort.
PS: Nein, es bringt nichts, eine Freizeile nach jedem Satz einzufuegen. Es ist auch unschoen jeden Satz in einen eigenen Absatz zu packen.
-
Es ist ein eindimensionaler Raum und hat deswegen eine Koordinate für die Position. Ein dichtebasierter Ansatz würde nicht nach einer vorgegebenen Anzahl von Clustern arbeiten oder? Aber im Endeffekt ist das was ich möchte ähnlich. Ich möchte z.B. maximal 3 Cluster haben. Diese 3 Cluster sollen dich so ausdehnen um so viele Datenpunkte wie möglich zu erfassen. Kann mit weniger als 3 Clusters gruppiert werden, sollen weniger Cluster verwendet werden.
-
Dann probiere doch VQ aus. Beispielsweise: http://www.data-compression.com/vq.html