eine spezielle wahl des abstandbegriffes wäre nur nötig, wenn die punkte relativ gleichmäßig verteilt wären. das scheint hier aber nicht der fall. deshalb geht die mahalanobis-distanz erst mal am problem vorbei. man könnte sich das aber noch mal anschauen, wenn man die gruppen schon mal erkannt hat, und ihnen dann einen möglichst sinnvollen mittelpunkt zuordnen will (der muss ja nicht unbedingt der schwerpunkt der punkte sein, das ist ne frage der aufgabenstellung)
ja, wenn man die punkte ungünstig erwischt hat man erst mal ein problem.
es gibt ne methode die wohl gut funktioniert, aber lange rechnet (was bedeutungslos wäre, wenn es um relativ wenige punkte (<100) geht):
1- nimm den ersten punkt
2- berechne die abstände aller anderen punkte zu diesem und sortiere die punkte nach diesem abstand
3- nimm die ersten (incl. dem ausgangspunkt) n/m punkte in der sortierten liste als erste gruppe
4- mach mit den restlichen punkten bei 1- weiter bis du alle gruppen hast
problem: wenn zwei gruppen dicht benachbart sind, und du erwischst als ersten punkt einen der in der mitte zwischen den beiden gruppen liegt, dann bekommst du eine gruppe im zentrum dieses gruppenhaufens und eine weitere die nicht mehr zusammenhängend ist und sozusagen die erste gruppe umschließt. das könnte man aber erkennen, da die mittelpunkte dieser beiden gruppen dann dicht beieinander sind und insbesondere jeweils innerhalb der anderen gruppe liegen. dann kann man diese beiden problemgruppen einfach wieder zusammenwerfen und neu trennen.
vermutlich wird man am ende ohnehin bei einem algorithmus landen, der ne erste lösung bestimmt, diese verifiziert und gegebenenfalls verbessert.
in nem Buch bin ich auf den begriff "zuordnungsproblem" gestoßen. das scheint unserer sache ziemlich nahe zu kommen. kannst ja mal weiter in diese richtung recherchieren.
ich würde vermutlich eher die zweite von mir angedeutete methode weiter verfolgen. etwas in der art: raster verfeinern und geometrisch nachbarn suchen. das kommt unserem auge wohl näher. schau dazu mal unter dem stichwort "bereichssuche"
ich glaube nicht das dass funktioniert, da nicht alle möglichkeiten des punktehaufens nicht besetzt sein müssen.
vl solltest du die plätze in einer gruppe nur besetzen bis der schwerpunkt einen merklichen sprung macht. ( dabei stellt sich aber die frage was ein merklicher sprung ist).
mfg clemens
Neun von zehn Stimmen in meinen Kopf sagen ich bin nicht verrückt. Die andere summt die Melodie von Tetris...
ich hab noch was gefunden:
ein minimal spannender baum hat als knoten die punkte und verbindet sie durch kanten, so dass die gesamtlänge der kanten minimal ist. daraus ergibt sich, das es zwischen zwei gruppen nur eine kante geben wird und die punkte einer gruppe im baum eng benachbart sein müssen. damit könnte man die gruppen also finden.
die berechnung erfordert NlogN zeit.
das finden der zwei dichtest benachbarten punkte kostet ebenfalls NlogN zeit.
die lösung deines problems sollte wohl etwas zwischen N^2 und NlogN zeit benötigen.
wieviele punkte hast du denn?
Moin auch!
Mal ganz was anderes: wie wäre es mit einer Dichteverteilung?
Man berechnet die Punktdichte im Raum für Punkte auf einem Raster festgelegten Abstandes.
Dabei gibt es mehrere Möglichkeiten.
1. Man berechnet die Dichte als Anzahl der Punkte pro Kugelvolumen, wobei der Radius der Kugel viel größer ist als das Raster aber viel kleiner als der Raum.
2. Man berechnet die Dichte für das unter 1 beschriebene Kugelvolumen in jedem Punkt auf dem Raster, wobei der Beitrag eines Punktes mit dem (zb) Quadrat der Entfernung abnimmt: D(x,y,z)=(1/r1²+1/r2²+...)/V mit rP<Kugelradius. (rP: Entfernung eines Rasterpunktes zum Punkt P, V: Kugelvolumen)
Ich schlage spontan Variante 2 vor. Man erhält dadurch eine Dichteverteilung, bei der es keine abrupten Spünge gibt. Dadurch sollte es möglich sein die Hochpunkte dieser Verteilung durch Berechnung der Gradienten zu bestimmen. An diesen Orten, nämlich Orten hoher Dichte lässt sich anschließend die Auflösung erhöhen, um die Gruppenmittelpunkte genauer festzulegen.
Anschließend wählt man diejenigen Punkte aus, die den höchsten Beitrag zur Dichte in den Hochpunkten gegeben haben, wobei man eine "schwammige" Grenze der Mitgliederanzahl ziehen kann, weil man die Punktzahl durch die Anzahl der gefundenen Gruppen teilen kann.
Erhält man Orte überdurchschnittlich hoher Dichte, ist dies ein Hinweis darauf, dass 2 Gruppen dicht beieinander liegen.
Es ist sicherlich möglich, Verfahren zur Abschätzung des Mindestrastermaßes und des Kugelradius zu definieren, aber das wäre mir im Moment zu viel.
Gruß
@fumir, naja hat schon was mit Statistik zu tun, das andere Beispiel oben kommt auch aus der Statistik. Kann, und will mich jetzt nicht viel damit beschäftigen, aber wollt einfach einen Tip geben, wo die Lösung zu suchen ist. Du kannst ja wie beim vorigen Beispiel einen Raster machen, für jeden Punkt einen Wert ermitteln, der die Dichte der Punkte beschreibt(Funktion vom Abstand) und dann die Mittelpunkte der Gruppen als jene Punkte mit den 4 höchsten Dichten festlegen. Dann musst du nur noch die Punkte zuteilen, indem du den Abstand der Punkte zu deinen Gruppenmittelpunkten vergleichst und dann aufteilst. Das wird wahrscheinlich für Dich ausreichen.
Wenn du dann Punkte hast, die eigentlich möglicherweise zu keiner Gruppe gehören, kannst du jene Punkte mit einer Mehrfachen Standardabweichung vom Mittelpunkt aussortieren. Irgendwie auf die Art.
Viel Glück beim Umsetzen. mfg
Pro Berechnung: je 9 die in 4 Gruppen eingeteilt werden müssen (bzw. allgemein eben eher wenige Punkte)wieviele punkte hast du denn?
Insgesamt: unterschiedlich, im Normalfall jedoch mehrere tausend
Das Problem, das ich bei allen vorgestellten Verfahren (außer dem ersten) sehe, liegt in k_min und k_max...
Die Gruppen dürfen ja nicht mehr als 3 Punkte enthalten, aber auch nicht weniger als 2.
Gibt es nicht...Wenn du dann Punkte hast, die eigentlich möglicherweise zu keiner Gruppe gehören
jeder Punkt muss in eine der Gruppen sortiert werden
So viele Treppen und so wenig Zeit!
@user529 verstehe nicht ganz was du meinst. möglicherweise hast du auch mich falsch verstanden
3- nimm die ersten (incl. dem ausgangspunkt) n/m punkte in der sortierten liste als erste gruppe.
aber in der gruppe sind drei plätze, bei 4 gruppen und maximal 3 plätzen heißt dass dass die letzte gruppe durch die finger schaut. oder ich habe dich wirklich falsch verstanden.
Neun von zehn Stimmen in meinen Kopf sagen ich bin nicht verrückt. Die andere summt die Melodie von Tetris...
@gock
@shakespaer
die vorschläge zum thema dichte gehen in die selbe richtung wie mein zweiter lösungsvorschlag. da kann man sich natürlich diverse varianten vorstellen.
prinzipiell würde ich aber nach möglichkeit fließkommaberechnungen vermeiden.
deshalb auch mein vorschlag für die definition des abstandsbegriffs mittels max.
wer will schon ständig irgend ne wurzel für den euklidschen abstand berechnen!
wenn man mit solchen dichten rumrechnet, wird man aber ne menge rechnen müssen.
@user529
ach so.
ich bin nicht von ner festen anzahl von plätzen ausgegangen, sondern hab erst mal eine lösung für das allgemeinere problem gesucht (viele punkte, viele gruppen, viele punkte je gruppe) da felix eine allgemeine lösung des problems bevorzugt (siehe ganz oben)
das spezielle problem ist auf jeden fall viel einfacher als der allgemeine fall.
ich würde erst mal nen beliebigen punkt weglassen, und die restlichen 8 punkte zu paaren gruppieren, dann den 9ten punkt zur nächstgelegenen gruppe hinzufügen. bei so wenigen punkten braucht man sich auch kaum gedanken zur performance zu machen.
das problem 8 punkte auf 4 gruppen zu verteilen ist ein zuordungsproblem (wie oben schon erwähnt) für das es fertige algorithmen in entsprechenden büchern zu finden gibt.
allerdings gehts da eigentlich um graphen, d.h. die geometrische seite unseres problems würde dabei ziemlich unter den tisch fallen (und nur als kantengewichtung entsprechend dem abstand der punkte eingehen). damit wird man auf diese weise wohl keinen optimalen algorithmus bekommen.
Berechtigungen
Zitieren
Lesezeichen