Noch ein mathematisches Problem

[Felix G]

Hallo Leute,

ich habe mal wieder ein mathematisches Problemchen...


Folgende Situation:
Ich habe eine Menge von n Punkten in einem dreidimensionalen Raum, welche sich an bestimmten (jedoch unbekannten) Positionen anhäufen. Sie bilden also eine Anzahl von m Gruppen (m ist bekannt), irgendwo in diesem dreidimensionalen Raum. Jede Gruppe muss dabei aus mindestens k_min und höchstens k_max Punkten bestehen.

Was ich brauche ist ein Algorithmus mit dem ich bestimmen kann welcher Punkt zu welcher Gruppe gehört.

Momentan Suche ich speziell eine Lösung für n=9, m=4, k_min=2 und k_max=3, aber eine allgemeine Lösung wäre mir natürlich lieber (ich halte es eh für unwahrscheinlich, daß es ausgerechnet für diese Werte eine Lösung gibt die ganz besonders einfach ist).


Ich weiß, daß ein derartiges Problem geradezu nach einem Neuronalen Netz schreit, aber darauf würde ich in diesem Fall gerne verzichten.

[PicNick]

Nehme an, die Position einer Gruppe ist durch ein x, y, z gegeben. Aber das mußt du ja auch erstmal haben ?
Die Einschränkung auf k_max versteh ich nicht. Da gibt es ja dann (überzählige) Punkte, die "Waisenkinder" sind ?

[Felix G]

Tja, die Positionen der Gruppen sind unbekannt, aber im wesentlichen genau das was ich am Ende als Ergebnis brauche (also die Zentren jeder Gruppe, welche sich durch den Schwerpunkt aller zugehörigen Punkte ergeben).

Um diese Ergebnisse zu erhalten muss ich also wissen, welche Punkte zu welcher Gruppe gehören.


Was k_max betrifft, das ist nicht wirklich unabhängig von den anderen Werten, sondern ergibt sich mehr oder weniger zwangsläufig aus der Anzahl der Punkte, der Anzahl der Gruppen und k_min. Bei meinem Beispiel gibt es 9 Punkte, die in 4 Gruppen eingeteilt werden sollen, dabei muss jede Gruppe mindestens 2 Punkte enthalten => 4*2=8 => es muss eine Gruppe mit 3 Punkten geben.

Allgemein ergibt sich das aus der Anforderung, daß alle Gruppen nahezu gleich viele Punkte enthalten sollten (was bei 9 Punkten aber natürlich nicht möglich ist).

[fumir]

versteh ich das richtig:
du hast n punkte (von denen du die positionen kennst)
und möchtest die in m gruppen aufteilen (deren mittelpunkt du finden willst),
so das die punkte einer gruppe möglichst dicht zusammen sind
und in jeder gruppe möglichst gleich viele punkte landen

das problem ist zunächst mal nicht eindeutig lösbar:
nimm an, 4 punkte seien an den ecken eines quadrates plaziert und du willst 2 gruppen bilden. dann gibt es schon mal 2 völlig gleichwertige lösungen.

ich würde damit beginnen die aufgabe weiter zu präzisieren.
z.b. die eigenschaften einer gruppe (mittelpunkt, radius) mathematisch festzulegen
also:
mittelpunkt: x_m=(sum_i=1..k x_i )/k ; y_m=(sum_i=1..k y_i )/k
beim radius wirds schon schwieriger: man könnte den mittleren abstand zum mittelpunkt bestimmen. oder aber den maximalen abstand vom mittelpunkt. allgemein must du also ein maß festlegen, mit dem du den radius der gruppe misst. je nach dem wie du dieses maß wählst bekommst du unter umständen unterschiedliche ergebnisse bei gleichen punktkoordinaten. auserdem wird der berechnungsaufwand unterschiedlich sein.
wenn deine punkte immer sehr stark gruppiert sind (also enge häufchen von punkten mit großen abständen zwischen den gruppen) wirds einfach, aber wenn die gruppen nicht so eindeutig plaziert sind (abstand der gruppen etwa gleich groß wie radius der gruppen) wirds schwieriger und das ergebnis weniger eindeutig.
ok - jetzt mal konkret. ich würde den radius als maximum von maximalem x-abstand und maximalem y-abstand zum zentrum definieren. das läßt sich am einfachsten berechnen und funktioniert gut, wenn die gruppen gut zu unterscheiden sind:
radius=max( max_k=1..kmax(abs(x_k-x_m)) , max_k=1..kmax(abs(y_k-y_m)) )

entscheidend für das weitere vorgehen ist nun die mutmaßliche verteilung der punkte:
also sind die punkte üblicherweise schon gruppiert (d.h. würde ich sie offensichtlich als gruppen erkennen, wenn ich sie sehe) oder sind die punkte eher gleichmäßig verteilt und die gruppen können/sollen insofern willkürlich gebildet werden?

[Felix G]

versteh ich das richtig:
du hast n punkte (von denen du die positionen kennst)
und möchtest die in m gruppen aufteilen (deren mittelpunkt du finden willst),
so das die punkte einer gruppe möglichst dicht zusammen sind
und in jeder gruppe möglichst gleich viele punkte landen

Ja, das verstehst du richtig

entscheidend für das weitere vorgehen ist nun die mutmaßliche verteilung der punkte:
also sind die punkte üblicherweise schon gruppiert (d.h. würde ich sie offensichtlich als gruppen erkennen, wenn ich sie sehe) oder sind die punkte eher gleichmäßig verteilt und die gruppen können/sollen insofern willkürlich gebildet werden?

Gleichmäßig verteilt sind sie nicht, und sie sollten im Normalfall bereits relativ gut als Gruppen zu erkennen sein. Es kann allerdings unter Umständen auch vorkommen daß mehrere Gruppen sehr dicht nebeneinander liegen, oder sogar an nahezu der gleichen Stelle im Raum. Falls dieser Fall eintritt, z.B. wenn 4 Punkte auf einem Haufen liegen, dann müssen eben je 2 davon willkürlich in eine Gruppe gesteckt werden. Das ist aber nicht so schlimm, da das Ergebnis - also die Positionen der Gruppen - dadurch ja nicht verfälscht wird.


Die Berechnung von Mittelpunkt und Radius ist soweit klar, aber wenn die zu verwendenden Formeln feststehen, bleibt ja immernoch das Problem wie ich denn die Punkte konkret sortieren kann. Irgendwo muss ich ja anfangen, und am Anfang habe ich außer einem Haufen Punkte nurnoch die Information wieviele Gruppen am Ende rauskommen sollen, und wieviele Punkte in jede Gruppe müssen

[fumir]

nur geduld, da kommen wir schon noch hin

wenn die gruppen in der regel bereits als gruppen zu erkennen ist, dann hat man folgenden konflikt: wen man die situation nach minimalem abstand optimiert wird man unter umständen nicht den wunsch nach gleichmäßiger verteilung der punkte in die gruppen erfüllen können und umgekehrt. da müßte man die prioritäten mal näher spezifizieren/quantifizieren.

wäre nicht schlecht mal den hintergrund der aufgabe noch etwas genauer zu erläutern.

so, nun mal ein erster lösungsvorschlag:
1- nimm die ersten beiden punkte und betrachte sie als jeweils eine gruppe mit einem punkt.
2- nimm den nächsten punkt dazu und ordne ihn je nach abstand einer der beiden gruppen zu
3- berechne mittelpunkt der erweiterten gruppe neu
4- weiter bei 2- bis alle punkte in eine der zwei gruppen eingeordnet sind.
5 - behandle nun jede der zwei gruppen nach schema 1-4 um vier gruppen zu erhalten
6- lass dir noch was schlaues einfallen um eine gruppenanzahl zu handhaben, die keine 2er potenz ist
dieser vorschlag ist wohl noch verbesserungsfähig, aber das prinzip teile und herrsche sollte man im auge behalten.

ein zweiter vorschlag:
1- teile das gesamtgebiet in ein raster/schachbrett auf und berechne die punktanzahl für jede teilfläche
2- such die m felder mit den meisten punkten
3- ordne diesen feldern jeweils eine gruppe zu, berechne mittelpunkt.
4- ordne restliche punkte nacheinander (nach abstand) diesen gruppen zu
auch dieser vorschlag ist nicht viel mehr als ne erste skizze.

wenn ich mal zeit habe, lass ich mir noch was besseres einfallen

[shakespear]

Geh in die nächste Bibliothek/ technische Bibliothek und borg Dir ein Buch über Statistik aus. Das könnte helfen.
Hat was mit Standardabweichung und so zu tun.

[fumir]

@shakespear
glaub ich nicht, erklär mal!

[regalbilly]

Wie wäre es mit der Verwendung des Mahalanobisabstands?
http://de.wikipedia.org/wiki/Mahalanobis-Distanz

skaleninvariant und translationsinvariant
Wer bietet mehr?

-------------
Nachtrag:
Ja, harter Stoff.
Es gibt auch einfachere Abstandsklassifikatoren, aber dann wahrscheinlich weniger invariant.

[Felix G]

Wirklich harter Stoff...

skaleninvariant und translationsinvariant

ist das bei meinem Problem überhaupt notwendig? (ok, Translationsinvarianz wäre wohl durchaus sinnvoll, aber Skaleninvarianz?)
Es geht doch nur darum eine bestimmte Anzahl an Punkten in Gruppen einzuteilen.


@fumir
Dein erster Lösungsansatz klingt schonmal recht vielversprechend, es stellt sich nur die Frage ob und welche Probleme auftauchen können.

Es ist natürlich so, daß ein einmal falsch zugeordneter Punkt nie mehr in der richtigen Gruppe landen kann, z.B. wenn man ganz am Anfang zwei Punkte wählt die eigentlich zu einer Gruppe gehören. Andererseits könnte dieses Problem wohl umgangen werden, indem man zu Beginn jedes Schrittes grundsätzlich die am weitesten voneinander entfernten Punkte als Basis für die neuen Gruppen wählt.

edit:
das Verfahren scheint mir eigentlich auch für andere Anzahlen von Gruppen geeignet zu sein. Ich meine prinzipiell geht es ja darum eine Gruppe immer weiter zu teilen, so lange bis sie nicht mehr teilbar ist (bei meinem Fall wäre das bei Gruppen mit weniger als 4 Punkten der Fall). Und dieser "atomare" Zustand kann bei den Gruppen ja durchaus zu unterschiedlichen Zeitpunkten eintreten oder?