Eigene Liste mit anderen Listen vergleichen



  • Hallo.

    Ich suche ein Verfahren um Listen auf Ähnlichkeit zu analysieren und einen Wert zu erhalten der die Ähnlichkeit darstellt.

    Ich habe eine eigene Liste:
    Eintrag A 70%
    Eintrag B 10%
    Eintrag C 30%
    Eintrag D 100%

    Jetzt hat wer anderes ebenfalls eine Liste:
    Eintrag A 60%
    Eintrag C 100%
    Eintrag E 22%
    Eintrag F 12%

    In der Praxis sieht es so aus, dass der Benutzer sich eine Liste mit Titeln zusammenstellt und einen Prozentwert vergibt, wie sehr er diesen Titel mag. Damit gestaltet er sich seine Lieblingsliste. Diese Möglichkeit haben alle und schön wäre es jetzt wenn man darüber bei anderen Benutzern Titel finden könnte, die eine hohe Übereinstimmung mit der eigenen Titelliste haben. So könnte man die Liste des Benutzers ein blicken und gegebenenfalls Titel finden die einen selbst dann gefallen könnten, da der Benutzer eine hohe allgemeine Übereinstimmung hatte.

    Ich hoffe das kam etwas verständlich rüber. 🙂
    Hat jemand eine Idee wie man das lösen kann?

    Es handelt sich hierbei um PHP und MySQL als Datenbank. Die Datenbank hat ca 1.000.0000 Einträge von ca 50.000 Benutzern. Es muss daher ein Verfahren sein das möglichst schnell erlaubt Übereinstimmungen zu finden, ansonsten würde es den Webserver lahm legen und wäre damit unbrauchbar.

    Da es hier um ein mathematisches Problem geht, denke ich das es ins Mathematik Forum gehört. Der Schwerpunkt liegt hier an der Optimierung auf Geschwindigkeit.

    Ich würde mich sehr über Idee freuen. 🙂



  • einfach nach prozenten sortieren, wobei ich hier werte von 1 bis 100 als zuviel empfinde.
    die einteilung in schulnoten von 1 bis 4 sollte doch reichen? 😕
    wer titel mit empfundenen schulnoten 5 oder 6 in seiner liste hat, ist halt selber schuld. 😃
    wie auch immer du die einteilung machst, wenn die einträge sortiert sind, lassen sich schnell übereinstimmungen finden.



  • Das ist ein guter Ansatz. Man kann natürlich das System vereinfachen und in (alte) Schulnoten 1-5 machen. Wobei dann nur 1 und 2 wirklich interessieren sollten, der Rest ist eher für so etwas uninteressant.

    Das Problem besteht jedoch weiterhin. Ich habe nun meine 100 Titel mit 1er oder 2er Bewertung und suche nun andere Benutzer die einen Großteil meiner so gut bewerteten Titel ebenfalls gut bewertet haben, damit man sehr ähnliche Benutzer finden. Eine reine Sortierung nach Note bringt da nicht das gewünschte Ergebnis. Damit findet man einfach nur gut bewertete Titel, es geht hier aber um möglichst hohe Ähnlichkeit zu meiner Liste. 🙂


  • Mod

    Wenn es um vielleicht 1000 User oder weniger geht, könntest du für jedes Paar von Usern die Ähnlichkeit ausrechnen und dann die mit den besten Werten nehmen. Wie genau du "Ähnlichkeit" misst, ist ein reines Modellierungsproblem, würde ich sagen. Du musst dir klar werden, was "ähnlich" bedeuten soll.



  • der nächste schritt wäre wohl, den großteil näher zu definieren, z.b. 60%.
    dann wäre die anzahl der einser oder zweier zu zählen und zu prüfen, ob die anzahl der einser oder zweier >= 60% ausmacht. wenn nicht, kann man diesen benutzer schonmal fallen lassen und mit dem nächsten fortfahren. das kann eine menge abfragen sparen.
    hat ein benutzer eine anzahl mit einem anteil >= 60% muss man konkret die titel suchen und zählen. das kann man am schnellsten verwirklichen, wenn man ein array so groß wählen kann, wie die anzahl der einträge.
    user1 hat u1 einser user2 hat u2 einser. u2/u1*100 >= 60%
    die konkrete suche nach titeln kann so aussehen:

    struct user
    {
    	int titel;
    	int note;
    };
    user user1[100]={0};
    user user2[100]={0};
    // Listen aufbauen ...
    
    // Listen wurden sortiert. user2 hat >=60% einser im verhältnis zu user1
    // Es gilt zu prüfen, ob auch die anzahl der titel >= 60% ausmacht.
    int n = 0, i = 0;
    while ( i < u2 && i < u1 )
    {
        if ( user1[user2[i].titel].titel == 0 )  
            continue; // Diesen Titel hat user1 nicht gelistet.
        if ( user1[user2[i].titel].note == user2[i.note] )
            n++;
    }
    if ( (double)n/u1 >= 0.6 )
    // die Ähnlichkeit ist gegeben.
    ...
    else
    // keine Ähnlichkeit
    ...
    


  • Es gibt Leute die haben 3000 Titel in ihrer Liste. Unwahrscheinlich das dort über die Hälfte 1 oder 2 bekommen hat. Deinen ersten Sätzen zu folge würden diese Benutzer alle raus fallen?

    Für kleinere Vergleiche würde ich deinen Code als optimal ansehen, aber wir reden hier von ca. 50.000 Benutzern und weit mehr als 1.000.000 Einträgen. Nicht jeder Benutzer wird eine Titelliste haben und ich schätze mal ohne nachzuschauen das davon vermutlich (Gefühl) so zu ca 35% der Titel eine 1-2 vergeben haben. Das wären aber immerhin noch 350.000 Titel bei sicherlich über 25.000 Benutzern.

    Es gibt ja den simplen weg 1 + 2 + 4 + 8 + 16 um dann mit eigenen Wert 4 & 7 abzufragen ob 4 in der Liste(7) vorkommt. Gibt es Mittel oder Wege so etwas sinnvoll zu übertragen um eine Art Checksumme von der eigenen Liste zu generieren und mit einer anderen Checksumme auf Ähnlichkeit zu prüfen? Ich kann es mir nicht vorstellen, aber ich denke mit so etwas wäre ein Vergleich recht einfach.

    Meine Liste durch alle anderen Listen laufen zu lassen ist für einen Webserver und dem Datenbestand jedenfalls kaum eine Option.



  • ~webi schrieb:

    Es gibt Leute die haben 3000 Titel in ihrer Liste. Unwahrscheinlich das dort über die Hälfte 1 oder 2 bekommen hat. Deinen ersten Sätzen zu folge würden diese Benutzer alle raus fallen?

    nein, so war das nicht gemeint. das war doch nur ein beispielvergleich zwischen zwei benutzern.
    aber das wirft eine neue frage auf. angenommen, ein user hat 3000 titel, davon 1000 mit 1 bewertet, ein anderer hat 20 titel, davon 10 mit 1 bewertet. wie definierst du nun die ähnlichkeit?

    ~webi schrieb:

    Für kleinere Vergleiche würde ich deinen Code als optimal ansehen, aber wir reden hier von ca. 50.000 Benutzern und weit mehr als 1.000.000 Einträgen. Nicht jeder Benutzer wird eine Titelliste haben und ich schätze mal ohne nachzuschauen das davon vermutlich (Gefühl) so zu ca 35% der Titel eine 1-2 vergeben haben. Das wären aber immerhin noch 350.000 Titel bei sicherlich über 25.000 Benutzern.

    heutzutage hat man ram kapazitäten im gigabyte bereich, deine angaben sind demgegenüber peanuts.

    ~webi schrieb:

    Es gibt ja den simplen weg 1 + 2 + 4 + 8 + 16 um dann mit eigenen Wert 4 & 7 abzufragen ob 4 in der Liste(7) vorkommt. Gibt es Mittel oder Wege so etwas sinnvoll zu übertragen um eine Art Checksumme von der eigenen Liste zu generieren und mit einer anderen Checksumme auf Ähnlichkeit zu prüfen? Ich kann es mir nicht vorstellen, aber ich denke mit so etwas wäre ein Vergleich recht einfach.

    du meinst also, ein & ist billiger als ein == ?
    bei listen bis zu 64 einträgen auf nem 64bit system mag man sich da noch sowas zusammenfriemeln, und die übriggeblibenen bits nach der & verknüpfung zählen.
    aber bei größeren listen artet das in unangenehme bitfrickeleien aus, weil du mehrere variable zu 'bitlisten' zusammensetzen musst.
    um deine übereinstimmungen, deine ähnlichkeit rauszufinden, bleibt doch nichts anderes übrig, als zu zählen und zu vergleichen. solch eine magic checksum dürfte schwer zu finden sein.

    ~webi schrieb:

    Meine Liste durch alle anderen Listen laufen zu lassen ist für einen Webserver und dem Datenbestand jedenfalls kaum eine Option.

    wenn alle user in millisekunden intervallen auf den server zugreifen, könnte es eng werden, sonst sehe ich da keine probleme. z.b. kann man die listen auch im voraus generieren, in den zeiten in denen der server leerlauf hat.



  • Ja wie definiert man Ähnlichkeit. Es gibt da sicherlich viele Möglichkeiten. Ich wüsste da jetzt auch nicht wirklich welche davon die optimale Regel ist. Ich würde denken wenn 10 Titel sich in beiden Listen befinden und mit 1-2 bewertet wurden, dann hat man zumindest eine kleine gemeinsame Basis.

    Das Auslesen von 500.000 Datensätzen mit dem Filter nur 1-2 Bewertung dauert über 1s auf einem schnellen Server. Bei 1Mio mit Filter wohl über 2s. Das nur reines auslesen und Rückgabe von einem einzigen Wert. Mehr Werte und das PHP drumherum würde das nochmal erhöhen. Ich sehe 500ms schon als langsam an. Da kann ich deiner Aussage mit "peanuts" nicht ganz folgen.

    Jetzt rechne ich mal pauschal von 50.0000 Benutzer machen 5% diese Abfrage am Tag. Das sind 2500 Benutzer.. Abfrage dauert sagen wir mal 3s, wobei ich glaube das es letztendlich eher bei 10 oder mehr liegen wird, durch die vielen Listen. Die Leute sind dann auch nicht über den Tag verteilt online. Real wird das zwischen 18 und 22Uhr sein. Allein die Listenabfrage sind schon bei 3s pro Benutzer über 2h reine Rechenzeit. Wenn hintereinander, wenn mehrere in selben Zeitrahmen kann das schon problematisch werden, so das sich die Seite für die restlichen Besucher verlangsamt. Es ist ja nicht nur die CPU sondern auch der mySQL Server und PHP die hier Ressourcen und RAM schlucken.

    Deshalb meinte ich das es ziemlich cool wäre, wenn jemand seine Titel-Liste pflegt, eine "magische Checksumme" davon erzeugt. Das wäre in unbedeutender Zeit fertig und man dann anhand dieser einfach einen Vergleich oder so macht. Wüsste aber auch nicht das so was geht.


Anmelden zum Antworten