Narses - Mo 04.08.08 12:39
Titel: Mengen-Visualisierung als Baum - Algorithmus-Ansatz gesucht

---

Moin!

Ich hab da aktuell ein Problem, an dem ich schon etwas länger rätsele, aber es will sich keine so richtig praktikable Lösung abzeichnen... :( Also, vielleicht finden wir ja zusammen was, wozu hat man eine Community. ;) :beer:

Es geht um Mengen [http://de.wikipedia.org/wiki/Menge_%28Mathematik%29], die ich visualisieren möchte. Erstmal ein paar Voraussetzungen:

• die Mengen enthalten unterschiedlich viele Elemente (im Beispiel sind das einfach nur Zahlen)
  
• es gibt keine Duplikate in der Mengeliste (jede Menge ist ein Unikat)
  
• jede Menge enthält min. 1 Element (die Leere Menge fehlt)

Ich möchte nun in einer Baumstruktur visualisieren, wie sich die Verteilung der Elemente in den Mengen aufschlüsseln lässt (sofern es denn möglich ist; was aber idR der Fall ist). Mal ein Beispiel, sonst kapiert man das schlecht:
Könnte so als Baum (oder Graph) visualisiert werden:Das ist jetzt natürlich ein sehr einfaches Beispiel für den Vorgang, den ich abbilden möchte. Wer sich mal an einem realen Beispiel versuchen will, findet eines im Anhang. ;)
//EDIT1: Wobei mir gerade auffällt, dass es hier auch noch eine weitere Variante gibt, die nur mit 9 Knoten auskommt und deshalb besser ist! :idea:
//EDIT2: Gausi hat´s natürlich sofort gesehen, der rechte Baum war fehlerhaft, somit sind beide Bäume gleichwertig.
//EDIT3: Die Bäume waren nicht korrekt abgebildet; ich habe das jetzt auf einen Baum reduziert (der 2. war eh falsch :oops:) und eine Optimierung ist auch OK: wenn die Ausgangsmenge sich auf einem (ununterbrochenen) Teilpfad wiederfindet, ist das auch gültig (Beispiel: 1-2-5).

Jeder Pfad von der Wurzel bis zu den Blättern muss dabei als Summe der besuchten Teilmengen eine der Ausgangsmengen liefern. Die Gesamtheit aller Pfadmengen entspricht demnach wieder den Ausgangsmengen. Die Partitionierung sollte aber so gewählt werden, dass eine maximale Zusammenfassung erreicht wird. :mahn:

Tja, hat jemand Vorschläge, wie ich die Mengen entsprechend analysiert/verarbeitet bekomme? :nixweiss: Danke schonmal für euren Einsatz. :zustimm:

cu
Narses

Gausi - Mo 04.08.08 14:58

---

Einen echten Ansatz habe ich auf Anhieb nicht, aber der rechte Baum in dem Beispiel ist imho falsch - es gibt kein Blatt für die Menge D = 1,2,5.

Wenn man die Mengen vorher sortiert, dann erinnert mich das so ein bißchen an Suffix-Trees, Suffix-Tries, DAWGs und Aho-Corasick-Automaten, die bei der Organisation von Strings eine Rolle spielen - und dann vor allem bei der Suche nach so organisierten Strings.

Ob man das modifizieren kann, um die Knotenzahl in dem Baum zu mimimieren, weiß ich nicht. Ich weiß aber auch nicht, ob das sinnvoll ist - denn das Minimum wäre ja einfach ein Wurzelknoten mit einem Blatt für jede Menge.

Narses - Mo 04.08.08 19:55

---

Moin!

Gausi hat folgendes geschrieben:

der rechte Baum in dem Beispiel ist imho falsch - es gibt kein Blatt für die Menge D = 1,2,5.

Jup :oops: korrigiert.

Gausi hat folgendes geschrieben:

Wenn man die Mengen vorher sortiert,

Da kann ich jetzt noch nicht auf Anhieb folgen :gruebel:

Gausi hat folgendes geschrieben:

dann erinnert mich das so ein bißchen an Suffix-Trees, Suffix-Tries, DAWGs und Aho-Corasick-Automaten

Danke, spannende Stichwörter! :)

Gausi hat folgendes geschrieben:

denn das Minimum wäre ja einfach ein Wurzelknoten mit einem Blatt für jede Menge.

Der hätte aber nicht die minimal mögliche Anzahl Knoten (wenn man voraussetzt, dass es min. 1 gemeinsamen Teilweg gibt; was aber ganz sicher immer der Fall ist). :nixweiss:

Ich habe durch deine Tipps auf jeden Fall eine (weitere) Idee, die ich mal ausprobieren werde. :idea: Soll aber niemanden davon abhalten, hier weiteren Input für mich abzuliefern. :D

cu
Narses

BenBE - Mo 04.08.08 21:32

---

Könnte man nicht auch in deinem linken Beispiel das leere Blatt ('') zulassen? In dem Fall ließen sich die Zweige 5 und 8-5 zusammenfassen und die Erstellung würde auf ein Sortieren der Mengen hinauslaufen, wobei du IMMER sortiert arbeiten könntest; was in deinem gezeigten Beispiel derzeit nicht geht.

Außerdem ist mir deine Variante, wie du Blätte\Äste\Knoten zählst noch nicht ganz klar.

delfiphan - Mo 04.08.08 21:38

---

Vielleicht hilft es, wenn man weiss, wie die Daten generiert wurden.
Um das Optimum zu finden entweder Brute-Force für kleine Datensätze. Für grössere Datensätze kannst du versuchen eine Heuristik zu verwenden (z.B. ein Greedy-Algorithmus, der die grössten Untermengen rauszieht)

Delete - Mo 04.08.08 21:44

---

wenn ich mir dein problem so durchlese, scheint es mir verblüffende ähnlichkeit mit dem "minimalen spannbaum problem" (minimal spaning tree) zu haben. dort wird genau so etwas versucht aus einer menge den minimalen spanning tree zu erstellen.

<HTH> GG

Narses - Mo 04.08.08 22:14

---

Moin!

BenBE hat folgendes geschrieben:

Könnte man nicht auch in deinem linken Beispiel das leere Blatt ('') zulassen?

Nein, das geht leider nicht.

BenBE hat folgendes geschrieben:

In dem Fall ließen sich die Zweige 5 und 8-5 zusammenfassen und die Erstellung würde auf ein Sortieren der Mengen hinauslaufen, wobei du IMMER sortiert arbeiten könntest; was in deinem gezeigten Beispiel derzeit nicht geht.

Langsam, lasst euch nicht von den aufsteigenden Zahlen in die Irre führen; ich kann mit einer Sortierung (wie schon bei Gausis Vorschlag) da keinen Vorteil entdecken... :nixweiss: Einfach mal das Real-Beispiel ansehen, da nutzt eine Sortierung auch nicht wirklich was (IMHO).

BenBE hat folgendes geschrieben:

Außerdem ist mir deine Variante, wie du Blätte\Äste\Knoten zählst noch nicht ganz klar.

Blätter = Knoten ohne Unterknoten, Knoten-Wert = 1, Äste egal (möglichst wenige eben).

delfiphan hat folgendes geschrieben:

Vielleicht hilft es, wenn man weiss, wie die Daten generiert wurden.

Hm, sie werden nicht generiert, sondern "abgelesen" bzw. als gegeben angesehen. Darauf habe ich keinen Einfluss.

delfiphan hat folgendes geschrieben:

Um das Optimum zu finden entweder Brute-Force für kleine Datensätze.

OK, aber was soll ich da brute-forcen? Die Obermenge der Elemente bilden und als Baumerstellungsreihenfolge alle Permutationen davon verwenden? Dann die Knoten zählen und die Lösung mit min. Knotenanzahl verwenden? Schonmal in das Real-Beispiel geschaut... ? :?

delfiphan hat folgendes geschrieben:

Für grössere Datensätze kannst du versuchen eine Heuristik zu verwenden (z.B. ein Greedy-Algorithmus, der die grössten Untermengen rauszieht)

Wie sollte das algorithmisch aussehen?

Grenzgaenger hat folgendes geschrieben:

wenn ich mir dein problem so durchlese, scheint es mir verblüffende ähnlichkeit mit dem "minimalen spannbaum problem" (minimal spaning tree) zu haben. dort wird genau so etwas versucht aus einer menge den minimalen spanning tree zu erstellen.

Da bin ich auch schon drüber gestolpert ;) allerdings: ich habe kein Kantengewicht (bzw. es ist egal), wenn ich den Kruskal-Algo so betrachte, scheint mir das aber nicht gänzlich unwichtig zu sein, oder? :nixweiss:

Danke für eure Unterstützung! :)

cu
Narses

Delete - Mo 04.08.08 22:18

---

dein kantengewicht wäre entweder 1 oder deine selbst definierte :-) . z.b. die entfernung vom root knoten :-) . es ist eigentlich egal, wie du es definierst, es gibt nur die kosten an (z. b. in kilometer, tickets, benzinverbrauch, etc. pp.). würd ich mir an deiner stelle noch mal näher ansehen .. :-)

---Moderiert von Narses: Beiträge zusammengefasst---

ps: kannte den kruksal algo nicht. aber sieh dir mal das an: http://en.wikipedia.org/wiki/Minimum_spanning_tree

delfiphan - Mo 04.08.08 22:33

---

Naja, Brute-Force ist hier nicht wirklich praktikabel. Da müsstest du für jede Untermenge alle Permutationen durchprobieren und die Möglichkeiten der Untemengen vermutlich auch noch untereinander kombinieren. Das kommt wohl nicht in Frage.
Ein Greedy-Algorithmus zu entwerfen ist nicht so schwer. Er geht einfach der Reihe nach und nimmt jeweils immer den naheliegendsten Schritt. Eine optimale Lösung ist natürlich überhaupt nicht garantiert.

Was stellen die Mengen den genau dar?

Delete - Mo 04.08.08 22:42

---

hier wäre dann auch die dynamische programmierung zu nennen, die das selbe leistet, jedoch mit einer definierbaren laufzeit :-)

Narses - Di 05.08.08 23:26

---

Moin!

Grenzgaenger hat folgendes geschrieben:

würd ich mir an deiner stelle noch mal näher ansehen

Hab ich gemacht, eine Test-Anwendung, die den Spanning-Tree bestimmen kann, ist angehangen.

Damit habe ich diese beiden STs bestimmt (auf/absteigendes Kantengewicht, passend zu dem Graphen der durch die Vereinigung aller Mengen gebildet wird, s.o., Element 9 hab ich allerdings weggelassen, ist eh aussen vor):
Allerdings :gruebel: was soll mir der Spanning-Tree nun bei der Baum-Bildung helfen bzw. welche Erkenntnis kann ich für die Mengenpartitionierung daraus gewinnen... :nixweiss:

cu
Narses

Horst_H - Mi 06.08.08 18:11

---

Hallo,

suchst Du nicht einfach einen "trie" oder patricia tree?
http://www.asv.informatik.uni-leipzig.de/opencms/export/sites/default/asv/downloads/Lehrmaterial/2007/ADS1Vorl12.pdf oder http://www.dvs.tu-darmstadt.de/teaching/inf2/2001/skript/gdi3-ws2001-skript-kapitel8.pdf

Die Daten in den patricia tree einfügern und dann kann man den Baum abklappern und sobald mehrere Nachfolger vorhanden sind, entsprechend den Anschauungsbaum aufteilen. Das müßte rekursiv machbar sein.

Gruß Horst

Delete - Mi 06.08.08 21:19

---

Meinst du nicht, dass der Rest nur noch eine Darstellungssache ist?




Zwischen den jeweiligen knoten kannst ja die Kosten variieren oder auch gleich schalten ...

<HTH> GG

PS: wenn ich deinen algo richtig interpretiere (nach: minimal spaning tree), dann sind jeweils die knoten (2:3) zwischen dem ":" (kante) verbunden. somit brauchst du nur noch die kannten auflösen und deinen baum zeichnen :-)

PPS: deine mengen zeichen ja immer nur einen weg vom startknoten bis zu den entknoten. Bei der mengennotation sollte es auch egal sein, in welche richtung deine graphen zeigen...

Narses - Sa 09.08.08 17:00

---

Moin!

Horst_H hat folgendes geschrieben:

suchst Du nicht einfach einen "trie" oder patricia tree?

Danke für die Tipps und die Info-Links. Ich habe mir das mal sehr ausführlich angesehen und durch den Kopf gehen lassen. :les: Allerdings stoße ich immer wieder auf das Problem, dass die Reihenfolge der Elemente in einer Menge keine Rolle spielen, allerdings bei einem Trie oder PATRICIA-Tree Schlüssel verarbeitet werden, bei denen die Reihenfolge sehr wohl eine Rolle spielt. :? Es geht mir ja nicht darum, eine Datenstruktur für eine möglichst effiziente Schlüsselsuche zu implementieren (dafür sind die beiden Ansätze hervorragend geeignet), sondern die Element-Verteilung in den Mengen (also Untergruppen) zu visualisieren. Und da kann die "richtige" Reihenfolge der Elemente in den Gruppen schon große Unterschiede für den Anschauungsbaum bedeuten. :nixweiss: Mein Fazit bisher: damit komme ich hier nicht weiter. :( Habe ich evtl. was nicht richtig verstanden? :gruebel:

Grenzgaenger hat folgendes geschrieben:

Meinst du nicht, dass der Rest nur noch eine Darstellungssache ist?

Nein, denn der Spannbaum löst (völlig korrekt) den Kreis 2-5-8 auf. Da kann ich dann einige Mengen nicht mehr als Pfad im Baum ablaufen (so gesehen ist der Anschauungs-Baum ja ein gerichteter Graph). Insgesamt war der SpanningTree sicher eine gute kleine Übung, aber momentan sehe ich keinen Vorteil in diesem Ansatz. :nixweiss:


Beim Lesen der Links und weiterführender Literatur bin ich aber über einen Algorithmus zur Bildung eines Huffman-Baums im Zusammenhang mit Dateisystemen gestolpert. Das hat mich auf folgenden Ansatz gebracht:

• die Gesamthäufigkeit jedes Elementes diesem als "Gewicht" zuordnen
  
• das "Mengengewicht" sei die Summe der Element-Gewichte in der Menge
  
• "Blätter" erzeugen, die je eine Menge enthalten
  
• paarweise Schnittmengen der Blätter bilden und die Schnittmenge mit dem größten Mengengewicht im folgenden betrachten, gibt es mehrere gleich große Schnittmengengewichte, das bevorzugen, das die kleinsten Differenzmengen hinterlässt:
  
• aus der Schnittmenge einen Knoten machen und die Differenzmengen als Kinder anhängen; im Folgenden nur noch die Schnittmenge im Knoten als Repräsentant für den Teilbaum betrachten
  
• wieder paarweise Schnittmengen bilden...

Was meint ihr? Hat das Chancen? ;)

cu
Narses

BenBE - Sa 09.08.08 19:35

---

Der Ansatz mit dem Huffmann-Baum könnte durchaus EINE Lösung darstellen, gerade, wenn es darum geht, mit möglichst wenigen Teilmengen (Knoten) hinzukommen.

ggf. kann man ja am Ende noch schauen, ob man eine einfache Heuristik über das Ergebnis laufen lässt, die ggf. die Höhe des Huffmann-Baums reduziert, sollte es da erkennbare typische Muster gibt, die durch dieses Verfahren hinterlassen werden.

Narses - So 10.08.08 00:09

---

Moin!

Es ist gelöst. :D Der Huffman-Baum liefert eine Mengenpartitionierung, mit der ich was anfangen kann. :dance2:

Hier also der Algorithmus:

• gegeben sei eine duplikat- und teilmengenfreie Liste von Mengen
  
• die Gesamthäufigkeit eines Elementes wird diesem als "Gewicht" zugeordnet
  
• das "Mengengewicht" sei die Summe der Element-Gewichte in der Menge
  
• flachen Baum erzeugen (nur "Blätter"), jeder Knoten enthält je eine Menge der Liste
  
• wiederhole
  
• paarweise Schnittmengen der Knoten bilden und die nicht-leere Schnittmenge mit dem größten Mengengewicht auswählen:
  
• aus der Schnittmenge einen (neuen) Knoten machen und die Differenzmengen als Kinder anhängen (hierbei kann es zu Knoten mit leeren Mengen kommen; in diesem Fall einfach den leeren Knoten löschen und dessen Kinder zu Kindern des neuen Knoten machen); im Folgenden nur noch den neuen Schnittmengen-Knoten als Repräsentant für den Teilbaum betrachten
  
• bis nur noch ein Knoten in der Liste der zu bearbeitenden Knoten ist oder nur noch leere Schnittmengen vorliegen

Die Implementation sei dem geneigten Leser als Hausaufgabe überlassen. 8) ;)

cu
Narses

Delete - So 10.08.08 00:16

---

wunderbar NARSES, dass es denn doch geklappt hat :-)

was ich mich frage ist, was willst du mit den mengenbaum eigentlich darstellen (mir fällt aktuell keine anwendung hierzu ein), oder ist es nur eine akademische übung ... :-)

Narses - So 10.08.08 00:29

---

Moin!

Grenzgaenger hat folgendes geschrieben:

was ich mich frage ist, was willst du mit den mengenbaum eigentlich darstellen (mir fällt aktuell keine anwendung hierzu ein)

Stell dir vor, du bist Netzwerk-Admin und möchtest dir mal einen Überblick verschaffen, wie denn die Zuordnung von Usern in Gruppen in der Domäne so aussieht... 8) mal so als Gedanke... ;)

Grenzgaenger hat folgendes geschrieben:

oder ist es nur eine akademische übung ... :-)

Das war´s auch :D wenn man in den Alltagstrott auf der Arbeit verfallen ist (was früher oder später in jedem Job passiert :|), dann macht es schon Spaß, mal wieder etwas in "akademischen Gefilden" zu schwimmen... :P

cu
Narses

Delete - So 10.08.08 07:10

---

Narses hat folgendes geschrieben:

Grenzgaenger hat folgendes geschrieben: was ich mich frage ist, was willst du mit den mengenbaum eigentlich darstellen (mir fällt aktuell keine anwendung hierzu ein) Stell dir vor, du bist Netzwerk-Admin und möchtest dir mal einen Überblick verschaffen, wie denn die Zuordnung von Usern in Gruppen in der Domäne so aussieht... 8) mal so als Gedanke... ;)

:-) stimmt, das hat ja nicht grad viel mit dem minimal spanning tree zu tun...

was mich wundert ist, dass es mit dem "Huffman-Baum" funktioniert, welcher ja auch nur eine spezialisierung des spanning trees ist...

aber sei's drum. hauptsache, es klappt :-) :beer:

noch ein schönes weekend
Grenzgänger

Horst_H - So 10.08.08 08:26

---

Hallo,

@Narses:
der geneigte Leser hätte das gern mal auf deine Datei angewendet gesehen.

Gruß Horst

Narses - Mo 11.08.08 00:04

---

Moin!

Horst_H hat folgendes geschrieben:

der geneigte Leser hätte das gern mal auf deine Datei angewendet gesehen.

Gerne ;) ich habe einen Ergebnis-Viewer angehangen (ist halt nur in einem TreeView sinnvoll betrachtbar - wobei man eigentlich mit der "Lösung" nix anfangen kann, wenn man es mit den anonymisierten Daten sieht... :gruebel: noch dazu weiß ich nicht, ob die dieser Auswertung zugrundeliegende Datenmenge noch der Beispielliste oben entspricht... :? :nixweiss:)

cu
Narses

uall@ogc - Mo 11.08.08 13:01

---

Zwei Anmerkungen / Fragen:
Der obige Beispiel-Baum kann doch gar nicht korrekt sein? Und mit Huffman kann dieser auch gar nicht dargestellt werden denn:

1) Huffman ist doch ein Binärbaum, demnach kann man A/B/C mit 1/2/3 nicht wirklich darstellen (jedenalls wie du es in dem Beispiel gemacht hast) 9 gehört ja eben nicht zur Menge #1
2) Die 8 kommt doppelt vor -> Huffman hat jeden Wert jedoch nur einmal -> Der Beispiel-Baum (auch wenn ich es mir nicht genauer angeschaut habe) muss falsch sein.

Edit: hab jetzt erst die Darstellung verstanden :P
Trotzdem braucht man für A=1, B=2, C=3 3-Äste

Moderiert von Narses: Smily repariert ;)

Narses - Mo 11.08.08 13:27

---

Moin!

uall@ogc hat folgendes geschrieben:

Huffman ist doch ein Binärbaum

OK, es mag kein Huffman-Baum sein, ich bin lediglich beim Betrachten eines Bildungsbeispiels auf diesen Ansatz "ala Huffman" gekommen. ;)

Wenn du den korrekten Namen für diesen Ansatz kennst, immer her damit. :)

cu
Narses

Thorsten83 - Sa 30.08.08 15:45

---

Hey,

kann das sein dass ihr mit Kanonen auf Spatzen schießt?
Du hast also eine Menge von Mengen, und wenn's um Zahlen, IP's oder sonstwas geht kann man darauf ja eine Ordnung definieren.
Also baust du dir einen verwurzelten Baum auf, an den linken von der Wurzel ausgehenden Ast hängst du alle Mengen, die (z.B.) die 1 nicht enthalten, an den rechten alle, die die 1 enthalten, usw. usf.
Rekonstruieren kannst du eine Menge dann über die Vereinigung der Elemente von einem Blatt aus hoch zur Wurzel.
Die Laufzeit zum Aufbauen eines solchen Baumes wäre dann durch n*m begrenzt, mit n als die Anzahl der Mengen und m als die Mächtigkeit der Menge, die bei der Vereinigung der Teilmengen entsteht.

Allerdings würde ich dabei die leere Menge als Krücke mit reinnehmen ;)

alzaimar - Sa 30.08.08 16:39

---

Hallo Thorsten, besonders kompakt ist der Baum dann allerdings nicht, oder?

Narses - Mo 01.09.08 11:18

---

Moin!

Thorsten83 hat folgendes geschrieben:

kann das sein dass ihr mit Kanonen auf Spatzen schießt?

Nein, ich denke nicht. :) Ich "arbeite" inzwischen mit dem Ansatz und es hat sich gezeigt, dass es für meinen Zweck geeignet ist. ;)

Thorsten83 hat folgendes geschrieben:

Du hast also eine Menge von Mengen, und wenn's um Zahlen, IP's oder sonstwas geht kann man darauf ja eine Ordnung definieren. Also baust du dir einen verwurzelten Baum auf, an den linken von der Wurzel ausgehenden Ast hängst du alle Mengen, die (z.B.) die 1 nicht enthalten, an den rechten alle, die die 1 enthalten, usw. usf. Rekonstruieren kannst du eine Menge

Wohlgemerkt: es geht nicht darum, einen Schlüssel effizient aufzufinden, sondern darum, Mengen "sinnvoll" (klar, das ist dann Ansichtssache und zweckabhängig) zusammenzufassen!

Wie alzaimar so schön treffend erkannt hat:

alzaimar hat folgendes geschrieben:

besonders kompakt ist der Baum dann allerdings nicht, oder?

ist das leider wahr, und damit für meinen Zweck unbrauchbar. Aber trotzdem Danke für deinen Vorschlag. ;)

cu
Narses

Thorsten83 - Mo 01.09.08 19:36

---

hmm ok, war wohl ein bißchen voreilig... ;)
Hab das so mal programmiert, richtig schön sind die Bäume wirklich nicht :(

Falls sich jemand das Trauerspiel angucken will: so wie's momentan programmiert ist muss die Mengenbeispiel.txt im gleichen Verzeichnis wie die .exe sein.