nicht angemeldet
Ähnlichkeiten von Gruppen bestehend aus zum Teil gleichen Mitgliedern erkennen
Rolf bHallo,
meine Frage bezieht sich nicht auf eine spezielle Programmiersprache, sondern auf die geeignete "Methode", Technik.
Beispiel:
Es gibt eine Tabelle mit Mitgliedern bestehend aus ID, Vorname, Name, Geburtsdatum. Es werden verschiedene Gruppen erstellt, wie z.B. Hobbies: Fussball, XBox, Laufen, Kochen, Tiere usw. Jedes Mitglied kann in mehreren Gruppen vorkommen.
Mein Ziel ist es, die Ähnlichkeit dieser Gruppen in einem Wert zu erfassen, um zu erkennen wie ähnlich die Gruppen sich anhand ihrer Mitglieder sind.
Wären in jeder Gruppe 1000 Mitglieder und in Gruppe Fussball und Laufen sind jeweils 999 gleiche Mitglieder wäre die Ähnlichkeit bei fast 100%. Wäre nur 1 Mitglied identisch in beiden Gruppen, läge die Ähnlichkeit der Gruppen bei 0,1%.
Die ID kennzeichnet jedes Mitglied mit einer einzigartigen Zahl. Die ID´s jeder Gruppe einfach zu addieren würde aber kein wirklich guten Wert ergeben, der die Ähnlichkeit zeigt. Ein Hashwert z.B. wäre ein eindeutiger Fingerabruck je Mitglied.
Nur kenne ich leider keine "Methode" oder Technik, wie ich aus den einzelnen Hashwerten einer Gruppe einen Wert erzeugen kann und auch die Ähnlichkeit mit den anderen Gruppen anhand dessen berechne.
Weiß jemand, wie man so was umsetzen kann. Ein Fachbegriff oder Stichwort was ich dann weiter recherchieren kann, würde auch schon helfen.
Gruß ebody
-
Guten Morgen ebody,
Du hast eine Merkwürdigkeit in deiner Ähnlichkeitsdefinition. Wenn S(i,j) die Ähnlichkeit der Gruppen i und j bezeichnet, würde ich erwarten, dass S symmetrisch ist, also stehs S(i,j) = S(j,i) gilt. Das ist bei Dir aber nicht der Fall. Beispiel:
Gruppe 1 hat 70 Mitglieder.
Gruppe 2 hat 350 Mitglieder.
Gruppe 1 und Gruppe 2 haben 35 gemeinsame Mitglieder.Wie groß ist jetzt die Ähnlichkeit? Teile ich 35 durch 70 oder durch 350? Habe ich 50% oder 10% Ähnlichkeit? Ist S(i,j) die Ähnlichkeit zwischen i und j aus Sicht von i? Dann wäre S(1,2) = 50% und S(2,1) = 10%. Willst Du das?
Wenn Du eine symmetrische Ähnlichkeit willst, musst Du den Divisor normieren. Ich würde dafür das arithmetische Mittel der Gruppengrößen vorschlagen. Damit stellst Du sicher, dass du keine Ähnlichkeit über 100% bekommst, und dass du die Ähnlichkeiten von Gruppenpaaren mit kleinen Mitgliederzahlen mit der von großen Mitgliederzahlen vergleichen kannst. Alternativ zum Mittelwert kannst du auch das Maximum nehmen.
Die weitere Überlegung hängt davon ab, ob Du etwas programmieren willst oder eine SQL Abfrage brauchst (ja, das geht per SQL). Wo und wie sind deine Gruppen und Mitglieder gespeichert?
Rolf
-
Hallo zusammen und erstmal vielen Dank für eure Antworten.
Die Gruppen hätten immer jeweils eine gleiche Anzahl an Mitgliedern. Am liebsten wäre es mir, wenn ich es mit Excel umsetzen könnte. Notfalls würde es aber auch per SQL oder Script gehen.
Mir geht es aber auch in erster Linie darum zu verstehen, wie man so etwas überhaupt angeht, so dass ich dann auch selbst schauen kann, wie ich es für mich am einfachsten umsetzen kann.
Eure Antworten haben mich schon etwas abgeschreckt, da ich einige Begriffe nie zuvor gehört habe ;-)
Mit Begriffen wie "Schnittmenge" oder "Vereinigungsmenge" bin ich auf einem falschen Weg oder könnte das auch eine Lösung sein?
Gruß ebody
-
-
Wären in jeder Gruppe 1000 Mitglieder und in Gruppe Fussball und Laufen sind jeweils 999 gleiche Mitglieder wäre die Ähnlichkeit bei fast 100%. Wäre nur 1 Mitglied identisch in beiden Gruppen, läge die Ähnlichkeit der Gruppen bei 0,1%.
Das Vorgehen entspricht der Berechnung der Hamming-Distanz. Wie Rolf b schon erklärt hat, führt das zu Problemen, wenn die Gruppen verschiedene Mitgliederzahlen haben.
Stattdessen könntest du die Anzahl der Operationen (Mitglied hinzufügen/entfernen/ersetzen), die nötig sind, um eine Gruppe in die andere zu überführen, als Maß nehmen. Das entspricht dann der Damerau-Levenshtein-Distanz.
In den beiden Artikeln findest du auch diverse Links zu weiteren Distanz-Funktionen.
-
Interessanter Ansatz, wäre ich jetzt nicht drauf gekommen. Aber nützt das hier?
Sei mal ObdA angenommen, dass die IDs der Mitglieder von 1 bis M fortlaufend wären. Dann müsste man pro Gruppe einen String der Länge M betrachten, der an jeder Position i eine 1 oder 0 hat, je nach dem, ob das Mitglied mit der ID i Gruppenmitglied ist oder nicht.
Wenn zwei Gruppen identische Mitglieder haben, ist die Hammingdistanz zwischen den Gruppen 0. Das müsste man als 100% ansehen. Wenn g 70 Mitglieder hat und h 350, und die Gruppen keine gemeinsamen Mitglieder haben, ist die Hammingdistanz 420. Aber wenn die Gruppen p und q je 40 Mitglieder haben und ebenfalls disjunkt sind, beträgt ihre Hammingdistanz 80. Beide Gruppen sind komplett unähnlich, aber die Hammingdistanz ist verschieden. Man muss die Distanz also normieren.
Dafür könnte man z.B. durch die Summe der Gruppengrößen teilen. Bei disjunkten Gruppen bekommt man dann 1 - das müsste man als 0% ansehen. Mit G(i)=Größe der Gruppe i wäre die Ähnlichkeit also
S(i,j) = 1 - (H(i,j) / (G(i) + G(j))Bei 35 gemeinsamen Mitgliedern wäre die Hammingdistanz (70-35)+(420-35)=350, teilt man das durch die Summe der Gruppengrößen ergibt sich 16,7% und damit wären wir wieder bei meinem Mittelwertansatz von oben :)
Man bräuchte jetzt noch einen Hamming-Algorithmus, der für lange Strings funktioniert und schneller als in O(n²) läuft, um meinen naiven Ansatz von oben zu ersetzen. :)
Rolf
-