Algorithmus zur Gruppierung nach Position unter Berücksichtung einer zugelassenen Ausdehnung

Hallo,

ich bin neu hier (auch in der C# Welt 😉) und brauche Hilfe bei einem Algorithmischen Problem.

Ich habe einen Datensatz welcher aus Datenpunkten besteht.

Jeder Datenpunkt spiegelt eine Position und einen Intensitätswert wieder.

Hierfür brauche ich einen Algorithmus der eine maximale Anzahl von n- Gruppen bildet.

Alle Gruppen zusammen dürfen eine vorgegebene Ausdehnung nicht überschreiten(damit ist die Ausdehnung über die Position gemeint).

Kann mit weniger Gruppen als der maximalen Anzahl und der vorgegebenen Ausdehnung gruppiert werden, soll dies so geschehen.

Ziel ist es so viele Punkte wie möglich zu gruppieren, welche nahe aneinanderliegen(Position).

Eigendlich könnte man auch sagen es soll mit möglich wenig und möglichst kleinen Gruppen gruppiert werden.

Wichtig ist, dass nur Punkte zu einer Gruppe zusammengefasst werden dürfen,
welche nebeneinanderliegen.

Ist es nicht möglich alle Datenpunkte mit der maximalen Anzahl und der vorgegebenen Ausdehnung (für alle Gruppen insgesamt) zu gruppieren,
soll nach den Intensitäten gewichtet gruppiert werden(es ist wichtiger einen Punkt
mit hoher Intensität zu einer Gruppe hinzuzufügen als einen mit einer kleineren).

Hierfür habe ich mal eine kleine Grafik erstellt wie ich mir das vorstelle.

von 0 bis 942000 wäre die Position
und 0 bis 1 die Intensität

Jeder Strich mit Kreis stellt einen Datenpunkt da.

In Rot habe ich mal mögliche Gruppen eingezeichnet.

Ich wäre für Hilfe bei der Lösung dieses problems sehr dankbar 😦

Ich habe leider seit einer Woche schon keinen Ansatz für dieses Problem gefunden 😦

Sind das auf der Grafik zwei Gruppen die jeweils die dichte Menge an Datenpunkten zusammenfassen oder 4 Gruppen?

Und wie hast du manuell diese Gruppierungen gesetzt? Wie bist du dabei vorgegangen? Kannst du dieses Vorgehen nicht direkt als Algorithmus umsetzen? Wenn nicht, warum nicht?

Es wären in der Grafik zwei Gruppen, die mit hoher Dichte und so viele wie möglich mit den getroffenen Vorgaben.

Das Umsetzten diese Kriterien ist genau mein Problem, ich habe leider nicht besonders Tiefgreifende kenntnisse was die Entwicklung von Algorithmen angeht.

Mir fällt es schwer einen geeigneten Ansatz zu finden.

Hallo ETobi,

schau dir mal die Vorgehensweisen in double[]-Array diskretisieren und Query zum gruppieren von Start und Endate mit Linq an, denn ich denke mit dieser Herangehensweise kannst du deine Aufgabe lösen.

mfG Gü

Erstmal vielen Dank an xxxprod und gfoidl für die schnellen Antworten,

@gfoidl: Ich werde mir die beiden Themen mal in Ruhe ansehen. Kannst du mir evtl. sagen was deine Idee dabei ist ? Denke dann würde es mir etwas leichter fallen den Lösungsansatz zu verstehen.

mfg ETobi

Hallo ETobi,

eigentlich ist es zommis Idee.

Es wird dabei ein Fenster über die Positionen verschoben, allerdings mit dem wichtigen Merkmal, dass Fenster-Beginn und Fenster-Ende unabhängig voneinander verschiebbar sind. D.h. die Fenstergröße ist nicht fix, sondern passt sich an den Daten, die den Kriterien entsprechen an, und mit den Daten im Fenster wird gruppiert.
Stell dir das Ganze verbildlicht vor, dann ist es leichter zu verstehen.

mfG Gü

Hi ETobi,

ich würde ja bei der Entwicklung des Algorithmus nicht von den Datenpunkten ausgehen, sondern von den Lücken, die sich anscheinend zwischen den Gruppen befinden. Indem man einmal durch die Datenpunkte iteriert, kann man die Größe und die Position dieser Lücken feststellen. Lücken sind dabei zusammenhängende Bereiche ohne Daten oder Daten unterhalb eines festgelegten Schwellwertes.

Wenn die maximale Anzahl von zu findenden Gruppen vorher feststeht, dann weiß man auch die Anzahl der Lücken, die man dazu benötigt. Dazu sortiert man die im ersten Schritt gefundenen Lücken nach ihrer Größe und verwendet die größten Lücken, um die restlichen Daten zu gruppieren.

Müßte doch eigentlich genau das machen, was du oben in der Grafik zeigt, oder?

Christian

Hallo ETobi,

mir sind noch andere Herangehensweisen eingefallen, da das Problem sich unter Clusteranalyse ansiedeln lässt.
Das ist mir vorher nicht so direkt aufgefallen, aber durch den vorhin genannten Weg wird (bzw. kann) eine ähnliche Vorgehensweise verfolgt (werden).

Entweder du wandelst du den K-Means-Algorithmus derart ab, dass bei der Schwerpunktsberechnung die Intensität berücksichtigt wird od. du führst eine Hierarchische Clusteranalyse durch. Beide Möglichkeiten sollten zielführend sein. Um jedoch die Anforderungen allesamt möglichst optimal zu erfüllen, würde ich zuerst per k-Means nach der max. Anzahl an Gruppen clustern und dann hierarchisch probieren ob sich Gruppen zusammenlegen lassen.

mfG Gü

Hallo MrSparkle und gfoidl,

erstmal Danke für eure Mithilfe!

Ich würde auch sagen das der Ansatz vom MrSparkle vergleichbar ist oder zumindest ähnlich mit dem Ziel, welches der K-Means Algorithmus verfolgt.

Der K-Means Algorithmus war auch einer meiner ersten Ideen, nur komme ich mit dem leider nicht weiter.

Mein Problem ist dabei noch, dass ich für den K-Means die Schwerpunkte über die Position ermittle, weil ich ja nur Punkte guppieren möchte, welche aneinander liegen.

Das mit dem Hierrachischen Custerverfahren muss ich mir erstmal anschauen da bin ich nicht so tief drin.

Eigendlich wäre eine abgeänderte version des K-Means evtl. möglich.

Was mein Problem hierbei noch ist, das K-Means eine Feste Anzahl von Clustern bildet und das immer, d.h es könnten Cluster entstehen die nah aneinander liegen, diese müsste man fusionieren.

Ein anderes Problem ist noch wie lässt man die Cluster nach der Intensität wachsen das möglichst viele und hohe intensitäten in einem Cluster zusammengefasst werden.

Die Cluster könnten ja unterschiedlich groß sein, nur alle zusammen dürfen eine vorgegebene Göße nicht überschreiten.

Hat da jemand eine Idee?

mfg ETobi

Hallo ETobi,

das K-Means eine Feste Anzahl von Clustern bildet und das immer, d.h es könnten Cluster entstehen die nah aneinander liegen, diese müsste man fusionieren.

Daher würde ich in einem 2. Schritt hierarchisch Clustern, um so nahe Cluster zusammenzufügen.

Ein anderes Problem ist noch wie lässt man die Cluster nach der Intensität wachsen das möglichst viele und hohe intensitäten in einem Cluster zusammengefasst werden.

Das ist in der Schwerpunktsberechnung beim k-Means zu berücksichtigen. Das kannst du ja beeinflussen.
Somit wirst du für den Schwerpunkt das Abstandsmaß und die Intensität berücksichtigen müssen.

die Cluster nach der Intensität wachsen das möglichst viele und hohe intensitäten in einem Cluster zusammengefasst werden

Wegen dem Wort "wachsen" ist mir noch eine Möglichkeit eingefallen. Solltest du dich mit Growing Neural Gas auskennen, so wäre das vermutlich die einfachste Möglichkeit, denn die beiden Schritte aus k-Means und anschließendem hierarchischen Clustern werden mit diesem Verfahren sozusagen vereint. Es hört sich komplizierter an als es tatsächlich ist. Der Algorithmus dazu ist in A Growing Neural Gas Network Learns Topologies beschrieben.

mfG Gü

Hallo gfoidl,

ich habe mir das mit dem Growing Neural Gas verstanden denke ich, nur ich denke nicht ,dass ich es dabei bis zu einer Implementierung schaffe weil es für mich schon sehr komplex scheint.

mit der anderen Möglichkeit bin ich im moment am rumprobieren ob ich damit mein Problem lösen kann.

mfg ETobi

Hallo zusammen,

was ich immer etwas wundert: So eine Zusammenfassung ist ja eigentlich ein Standard-Problem, vor dem man immer wieder steht. Und natürlich gibt es dafür auch Standard-Algorithmen. Diese wurden ja auch genannt/verlinkt. Allerdings sind die - oder täusche ich mich - in den Papieren nur abstrakt beschrieben. Irgendwie scheinen konkrete Implementierungen Mangelware zu sein. Warum gibt es nicht - z.B. in .NET-Komponenten und C#-Snippets - eine fertige Implementierung, der ich nur noch meine Liste mit den Daten gebe (und vielleicht noch ein paar optionale Parameter, wie z.B. der gewünschten Cluster-Anzahl oder des Mindestbreite der Lücken) und dann meine Cluster als Rückgabewert bekomme? Oder habe ich was übersehen?

herbivore

Hallo,

leider komme ich immernoch nicht richtig weiter bei meinem Problem. Im mom bin ich auch am überlegen ob es nicht eher ein kombinatorisches Problem ist. Und kein Clusterproblem. Ich habe mich jetzt auch entschieden das mit der Intensität erstmal herauszulassen.

Damit bleiben noch folgende Anforderungen:

• So viele Punkte wie möglich gruppieren
• Die maximale Anzahl der Gruppen wird vorgegeben
• Die maximale Ausdehnung (alle Gruppen zusammen) wird vorgegeben.
• Die einzelnen Gruppen können unterschiedlich groß sein.

@herbivore

Finde ich eine gute Idee, ich würde mich auch gerne an so etwas beteiligen wenn ich mein Problem gelöst habe.

mfg ETobi

Hallo ETobi,

du hast deine Anforderungen beschrieben, aber nicht, wo genau du hängst, bzw. was das Problem ist, weshalb du nicht weiterkommst, bzw. was du nun von uns erwartest. Das solltest du noch ergänzen.

herbivore

Was ich versucht habe ist ein k-means clustering. Damit bilde ich eine Anzahl von n Gruppen. Um die maximale Ausdehnung nicht zu überschreiten schrumpfe ich die einzelnen Gruppen danach. Dies mache ich so, dass ich immer die Distanz der äußeren Elemente (immer die beiden letzten Elemente am Anfang und Ende der Gruppe )einer Gruppe ermittle und mit den anderen der anderen Gruppen vergleiche.
Das äußere Element einer Gruppe mit der geringsten Distanz fliegt raus. Das mache ich so lange, bis die maximale Ausdenhung nicht mehr überschritten ist.
Ein Problem ist dabei aber, dass es vorkommen kann das der Schwerpunkt einer Gruppe ungünstig liegt.

z.B. |xxxxx--------S--------xxxxx|

Dies soll eine Gruppe darstellen. X steht für Punkte --- für Freiraum und S für den Schwerpunkt.

Wenn ich nun mit meiner Vorgehensweise minimiere entstehen nicht unbedingt optimale Ergebnisse.

Deswegen bin ich am schauen ob es vllt noch andere möglichkeiten gibt.

Gruß ETobi

was ich immer etwas wundert: So eine Zusammenfassung ist ja eigentlich ein Standard-Problem, vor dem man immer wieder steht. Und natürlich gibt es dafür auch Standard-Algorithmen. Diese wurden ja auch genannt/verlinkt. Allerdings sind die - oder täusche ich mich - in den Papieren nur abstrakt beschrieben. Irgendwie scheinen konkrete Implementierungen Mangelware zu sein. Warum gibt es nicht - z.B. in
> - eine fertige Implementierung, der ich nur noch meine Liste mit den Daten gebe (und vielleicht noch ein paar optionale Parameter, wie z.B. der gewünschten Cluster-Anzahl oder des Mindestbreite der Lücken) und dann meine Cluster als Rückgabewert bekomme? Oder habe ich was übersehen?

Cluster Algorithm Using .NET Collections
K-Means Algorithm

Wie siehts damit aus? Hier kann die Distanz eingegeben werden.
Ausprobiert hab ich es selbst noch nicht.

Der Algorithmus DBSCAN wäre vielleicht auch eine Alternative.

Relativ einfach zu implementieren und ist nicht auf kugelförmige Cluster beschränkt. Naive Implementierungen haben eine asymptotisch quadratische Laufzeit, man findet aber auch Implementierungen mit linearer Laufzeit...