schlauste Art ähnliche Wörter zusammenzufassen(python)?
Hallo, ich habe die Aufgabe bekommen Kopierrechte, hier als BSP. copyR1-20, zusammenzufassen. Wenn ich mit meiner "Ähnlichkeitsfunktion" über die Liste gehe gibt diese mir die Liste für das entsprechende Kopierrecht zurück von 100, genau gleich bis 0 absolut verschieden. Nehmen wir also mal an meine Ähnlichkeitsfunktion macht Sinn und es kommen logische Werte raus. Gibt es hier ein Statistisches Verfahren um die ähnlichsten Kopierrechte in einer Gruppe zusammenzufassen?
Bislang schaue ich einfach Kopierrecht1 an, nehme alle Kopierrechte über mein Limit 86 hinzu und nenne das meine Gruppe. Das Führt jedoch zu Problemen, wenn z.B. Kopierrecht1 ähnlich zu Kopierrecht 2 und 3 ist, Kopierrecht 4 aber nur ähnlich zu Kopierrecht 2 ist. Hier weiß ich nicht wie ich die Gruppen bilden soll.
Also zu meiner Frage:
Ich soll das in Python implementieren.
Gibt es eine systematische Möglichkeit durch z.B. einen Clusteralgorithmus die besten Gruppen hier zu bilden? (Die Tabelle ist nicht ausgefüllt, sie geht natürlich noch weiter)
Vielen Dank im Vorraus
1 Antwort
Ich weiß nicht, wonach Du genau suchst. Wann sind denn zwei Kopierrechte „ähnlich“?
Wenn Du ein festes Limit hast, definiert das einen Graphen, dessen Kanten dieses Limit überschreiten.
- Du kannst im Graph nach maximalen Cliquen (=vollständige Teilgraphen) suchen. Kopierrechte einer Clique sind sich paarweise ähnlich, aber sie können sich beim Vergleich zu anderen Cliquen unterschiedlich verhalten. Maximale Cliquen können sich überlappen.
- Du kannst den Graph in (disjunkte) Zusammenhangskomponenten zerlegen. Kopierrechte verschiedener Komponenten sind sich nicht ähnlich, aber innerhalb einer Komponente können sie ähnlich sein.
Ich habe den Eindruck, dass Du Dir Zusammenhangskomponenten als maximale Cliquen wünschst. Das wird im Allgemeinen nicht funktionieren.
Also als Knoten die Copyrights, als kannten die "Ähnlichkeit" und dann alle Kannten kleiner 87 löschen
Genau so! Ich sehe es aber eher so, dass eine Kante existiert, wenn der Tabellenwert groß genug ist.
und die größten Zusammenhangskomponenten nehmen
Streich das „größte“. Entweder zerfällt der Graph in Einzelteile oder nicht.
Du kannst höchstens mit dem Limit spielen, um mehr oder weniger Teilgraphen zu bekommen. Bei ≥0 ist der Graph sicher nur ein Monolith. Bei 100 wirst Du viele einelementige Komponenten bekommen.
Das ist wie bei einer Inselgruppe: Je höher der Wasserstand (=Limit), desto mehr Inseln wirst Du sehen.
also ich habe mich jetzt nochmal genauer damit auseinander gesetzt. Zusammenhangskomponenten machen ja an sich auch wenig sinn, da es zu einer Verkettung führen kann bei dem der letzte Knoten der Kette absolut verschieden zu dem ersten Knoten ist.
Ich habe mir das jetzt so überlegt:
ich fange mit dem ersten Knoten an, speichere jeden umliegenden Knoten mit ner Kantenlänge größer 86, dann bei der zweiten Iteration muss das schon größer 92 sein, bei der dritten 95 und so weiter, damit es nicht vorkommt dass lauter "87er" aneinander hängen, die am ende unterschiedlich sind. Das kann man doch mit BFS lösen, also nach jeder Iteration das Limit der Kantenlänge erhöhen. Die besuchten Knoten speicher ich ab und werden nicht weiter berücksichtigt.
Das Problem was mir dabei aufgefallen ist ist aber, dass das Ergebnis sich verändert je nachdem bei welchem Knoten ich beginne. Also dass dann meine Gruppen anders gewählt werden. Gibt es da vielleicht eine Möglichkeit die global "beste" Version zu finden, also wo z.b. die spannweite zwischen dem ersten Knoten und dem letzten Knoten in der Gruppe im Mittel am Kleinsten ist? Oder die Lösung wo insgesamt am meisten Gruppen gebildet wird. Das klingt jetzt wie wildes überlegen, aber es fühlt sich einfach falsch an einen Algorithmus zu schreiben bei dem die Reihenfolge der Knoten das Ergebnis ändert.
Hoffe man hat verstanden was ich meine :)
Zusammenhangskomponenten machen ja an sich auch wenig sinn, da es zu einer Verkettung führen kann
Äh nein. Der Witz dabei ist, dass Knoten aus verschiedenen Komponenten sicher nicht ähnlich sind. Auch wenn Du ähnliche Knoten irgendwie gruppieren willst, liegt jede Gruppe ganz sicher in nur einer Zusammenhangskomponente. Damit zerlegst Du also Dein Problem in kleinere Teilprobleme.
Das Problem beim Finden ähnlicher Knoten ist inhärent. Prinzipiell hat jeder Knoten eine Menge von Nachbarn, die ähnlich genug zu ihm sind. Dazu reicht eine direkte Kante (>Limit). Es gibt keinen Grund, die Nachbarn der Nachbarn zu untersuchen, denn wenn sie relevant sind, haben sie ja auch eine direkte Kante zum Knoten.
Diese Nachbarschaftsmengen überlappen sich gegenseitig. Nur wenn zufällig irgendwo eine „Insel“ existiert, haben deren Bewohner alle dieselben Nachbarmengen und bilden eine maximale Clique, die gleichzeitig auch eine Zusammenhangskomponente ist.
Du kannst das nicht durch einen Algorithmus erzwingen. Entweder hat der Graph diese Struktur oder eben nicht.
Mir ist immer noch nicht klar, was Du mit der Zerlegung erreichen willst. Es klingt so, als wolltest Du Gruppen, deren Mitglieder alle untereinander möglichst ähnlich sind, und die zu allen anderen Gruppen möglichst verschieden sind. Ich glaube, das geht nicht:
A B C
A 100 100 0
B 100 100 100
C 0 100 100
Wie soll das gruppiert werden?
(Wenn Dir die Zahlen zu ünrealistisch vorkommen, nimm 70 und 90 statt 0 und 100)
A B C
A 100 90 70
B 90 100 90
C 70 90 100
wenn ich jetzt davon ausgehe, dann würde ich sagen bilden A,B und C eine Gruppe. Das macht jetzt erstmal wenig Sinn, weil A und C ja nur zu 70% übereinstimmen, aber irgendwie ist uns aufgefallen, dass unsere "Ähnlichkeitsfunktion", die btw auf den levenshtein algorithmus aufbaut, für das menschliche Auge sehr inkonsistente Ergebnisse auswirft. Also Ergebnisse mit 70% übereinstimmung müssen nicht zwangsweise sehr verschieden sein, aber Ergebnisse mit 90% übereinstimmung sind meistens schon sehr ähnlich.
Als Beispiel sollten diese Kopierrechte zu einem zusammengefasst werden:
1)Copyright (c) 1996 Herbert Mälzer Marius Mälzer
2)Copyright (c) 1996 Herbert Mälzer<rj@thp.uni-hanne.de Marius Mälzer <mc@thp.uni-hanne.de
3)Copyright (c) 1996 Herbert Mälzer <rj@thp.uni-hanne.de
4)Copyright (c) 1996 Herbert Mälzer <rj@thp.uni-hanne.de <mc@thp.uni-hanne.de
Von Copyright1 ausgehend als Knoten würde die Funktion sagen es sei ähnlich zu 2 und 3,(höher 86) aber verschieden zu 4 (76), aber von Copyright 2 ausgehend sagt die Funktion es ist zu 95% gleich wie Copyright4.
Deshalb dachte ich es lohnt sich nicht nur die Nachbarknoten zu betrachten.
Danke erstmal für die Nachricht, ich glaube ich habe das einigermaßen verstanden. Also so wie ich mir das bisher angeschaut habe würde ich behaupten ab dem Wert >86 ist ein Copyright ähnlich zu einem anderen.
So wie ich das jetzt verstanden haben machen Cliquen keinen Sinn bei meiner Betrachtung, da diese gemeinsame Teilmengen der Copyrights enthalten können. (Glaub "nicht disjunkt" heißt der Fachbegriff😅)
Die Zusammenhangskomponenten machen da ja schon mehr Sinn, da sie zwar nicht so "weit zusammengefasst" sind aber zumindest nicht doppelte Einträge verrechnen.
Für mich gilt lieber zu wenig zusammenzufassen als zu viel.
Hoffe soweit hab ich das verstanden. kannst du noch was du dem Graphen selbst sagen? Also als Knoten die Copyrights, als kannten die "Ähnlichkeit" und dann alle Kannten kleiner 87 löschen und die größten Zusammenhangskomponenten nehmen oder wie genau funktioniert das?
Mit Graphen bin ich halbwegs vertraut aber Zusammenhangskomponenten habe ich ewig nicht mehr benutzt.