Ankündigung

Einklappen
Keine Ankündigung bisher.

Pearson Correlation mit MySQL

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Pearson Correlation mit MySQL

    Hallo zusammen,

    ich zerbreche mir seit heute Vormittag den Kopf über einer Query und komme zu keinem Ergebnis. Es geht um Folgendes: Es gibt eine Tabelle, in der eine Pearson Correlation Matrix hinterlegt ist. Nennen wir die Tabelle einfach mal pearson; sie hat die Spalten user1, user2 und correlation. user1 und user2 sind Integer (IDs) und bilden den Primary Key, correlation ist float und enthält wie beim Pearson-Koeffizienten üblich Werte von -1 bis 1. Es gibt eine zweite Tabelle rating. Diese hat als Spalten userID, elementID, rating.*

    Es geht jetzt darum, den k-Nearest Neighbour Algorithmus anzuwenden. Für Benutzer 1 soll für jedes Item in der Datenbank berechnet werden, welche Bewertung er diesem Item mit hoher Wahrscheinlichkeit geben wird. Dafür werden jeweils die drei ähnlichsten Benutzer gesucht, die das jeweilige Item ebenfalls bewertet haben. Aus deren Bewertungen setzt sich dann anteilig die errechnete Bewertung des Benutzers 1 zusammen.

    Folgende Query löst das Problem soweit:

    Code:
    SELECT elId, SUM(partialRating) as prediction
    FROM
        (SELECT d.elementID as elId, d.rating*(pc.correlation/
          (SELECT sum(correlation)
          FROM (
            SELECT pci.correlation
            FROM pearson pci
            INNER JOIN rating d2
            ON pci.user2 = d2.userID
            WHERE pci.user1 = 1 AND pci.user2 != 1 AND d2.elementID = 1
            GROUP BY d2.elementID, pci.correlation
            ORDER BY pci.correlation DESC
            LIMIT 3
          ) as sq
          )
        ) as partialRating
        FROM pearson pc
        INNER JOIN rating d
        ON pc.user2 = d.userID
        WHERE pc.user1 = 1 AND pc.user2 != 1 AND d.elementID = 1
        GROUP BY d.elementID, d.rating, pc.correlation
        ORDER BY pc.correlation DESC
        LIMIT 3) as predictedRating
    GROUP BY elId
    Die Query berechnet die Bewertung, die Benutzer 1 dem Element 1 geben würde.

    Mein Problem ist jetzt: Ich möchte die Query gerne über ALLE Elemente laufen lassen, nicht nur über jeweils ein "hart" ins Query geschriebene Element. Das Ergebnis soll also eine Liste sein mit allen Element-IDs und der zugehörigen errechneten Bewertung. Es scheitert bei mir entweder daran, dass ich die elementID von den äußeren Querys nicht in den Subquerys benutzen darf oder daran, dass ich die Limitierung auf 3 (weil k = 3) nicht angeben kann.

    Es ginge natürlich, einfach alle möglichen Element-IDs auszulesen und in PHP darüber zu iterieren und den Query für jede ID einzeln auszuführen. Aber ich hätte gerne eine MySQL-only Lösung.

    Hat jemand eine Idee, wie ich das schaffen könnte?

    Viele Grüße
    Malte

  • #2
    Muß es denn MySQL sein? PostgreSQL hat seit etlichen Versionen den k-Nearest Neighbour Algorithmus direkt eingebaut. Indexbasiert, und damit *richtig* schnell. Wird gern bei Geo-Krams verwendet, geht aber auch in anderen Anwendungen wie bei Dir.
    PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

    Kommentar


    • #3
      Hey, ja leider muss es MySQL sein. Geht um meine Abschlussarbeit (CF mit PHP/MySQL), da käme PostgreSQL nicht so gut

      Kommentar


      • #4
        Zitat von mson Beitrag anzeigen
        Hey, ja leider muss es MySQL sein. Geht um meine Abschlussarbeit (CF mit PHP/MySQL), da käme PostgreSQL nicht so gut
        Ich würde eher das Gegenteil vermuten. Das würde zeigen, dass man sich was überlegt hat, statt irgendein 08/15 Massending zu nehmen und damit herumzuwursteln.

        Kommentar


        • #5
          Ne, es geht darum, eine möglichst simple CF-Implementation in Form eines PHP-SDKs zur Verfügung zu stellen. PHP/MySQL ist gerade im E-Commerce, wo Recommender Systems sehr gefragt sind, immer noch das Maß aller Dinge. Es gibt mittlerweile zig Drittanbieter, die für viel Geld Recommender System Funktionalitäten anbieten. Oder man muss sich selbst PredictionIO o.Ä. einrichten; das kann aber nicht jeder Shop-Betreiber, weil dafür häufig auch zusätzliche Hardware angeschafft bzw. eingerichtet werden muss. Sich ein Plugin/Modul für eine Shopsoftware installieren kann jeder. Es gibt viel Sekundärliteratur zum Thema Collaborative Filtering mit PHP/MySQL, aber es wird nie auf die Performance eingegangen - und da setz ich mit meiner Arbeit an. Sprich genau die Grenzen aufzeigen, was mit PHP & MySQL in diesem Bereich noch möglich ist. Also wie viele User, wie viele Artikel, wie viele Bewertungen darf der Shop haben und bei welcher Server-Konfiguration. Es geht NICHT darum die schnellste Technologie zu finden, mit der man Collaborative Filtering betreiben kann.

          ---------------------

          Also, falls mir noch jemand bei meiner Frage weiterhelfen kann, wäre das echt knorke ;O

          Kommentar


          • #6
            Zitat von hellbringer Beitrag anzeigen
            Ich würde eher das Gegenteil vermuten. Das würde zeigen, dass man sich was überlegt hat, statt irgendein 08/15 Massending zu nehmen und damit herumzuwursteln.
            Kann u.U. so sein, oder je nach Gemüt des Dozenten eben auch ein "Thema verfehlt". Er kann ja auch nicht einfach mit Perl anstatt PHP kommen.
            Ich finde den Einwand von akretschmer objektiv und gut angebracht, aber vorzuschlagen, die Anforderungen einer Abschlussarbeit zu verwerfen, finde ich etwas ungünstig.
            Competence-Center -> Enjoy the Informatrix
            PHProcks!Einsteiger freundliche TutorialsPreComposed Packages

            Kommentar


            • #7
              Den Subquery aus der SELECT Klausel raus und als INNER JOIN in den äußersten Query implementieren. Dein Problem nennt sich dann groupwise limit und da wirst du bei Google fündig.

              Ob der KNN Index von Postgres hier in Frage kommt bezweifle ich. Das ist n Dimensional und n ist hier die Anzahl User.

              Kommentar


              • #8
                GROUPWISE LIMIT kann PostgreSQL übrigens auch native.
                PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

                Kommentar


                • #9
                  Zitat von erc Beitrag anzeigen
                  Den Subquery aus der SELECT Klausel raus und als INNER JOIN in den äußersten Query implementieren. Dein Problem nennt sich dann groupwise limit und da wirst du bei Google fündig.

                  Ob der KNN Index von Postgres hier in Frage kommt bezweifle ich. Das ist n Dimensional und n ist hier die Anzahl User.
                  Danke für den Input! Ich hab mich noch einmal herangewagt und nun zumindest schon einmal folgendes hinbekommen:

                  Code:
                  set @prev := 0, @rownum := '';
                  
                  SELECT elementID, user2, correlation, tmp.rank
                  FROM (
                      SELECT *,
                          IF( @prev <> oq.elementID, @rownum := 1, @rownum := @rownum+1 ) AS rank,
                          @prev := oq.elementID
                      FROM (
                          SELECT d.elementID, pc.user2, pc.correlation
                          FROM rating d
                          INNER JOIN pearson pc
                          ON pc.user2 = d.userID AND pc.user1 <> pc.user2
                          WHERE pc.user1 = 1
                          ORDER BY elementID ASC, correlation DESC
                      ) oq
                  ) tmp
                  WHERE tmp.rank <= 3
                  ORDER BY elementID, correlation DESC
                  Dadurch bekomme ich eine Liste für je drei näheste Nachbarn pro Element für den Benutzer 1. Jetzt muss ich nur noch meine ursprüngliche Berechnung wieder einbringen.. mal schauen ;O

                  Danke erstmal!

                  Edit: Okay, das hat geklappt! musste zwar mehr oder weniger die gesamte Query noch einmal (doppelt) in eine Subquery packen, weil ich pro Dreier-Gruppe dennoch zusätzlich in jeder Row auch die Gesamtsumme der Korrelation gebraucht habe, sodass die Query jetzt recht riesig ist, aber sie ist dennoch verhältnismäßig "schnell". Recommendations (also errechnete, wahrscheinliche Bewertungen) für einen Benutzer für knapp 1700 Elemente in 0,29 Sekunden. Reicht eventuell nicht zur Echtzeitgenerierung der Empfehlungen (weil die ja auch meist noch weiterverarbeitet werden zu Produktempfehlungen, Artikelsortierung oder sonstiges und das auch Zeit kostet), aber zur Vorberechnung einer Empfehlungstabelle taugt es alle mal. Danke noch einmal für eure Hilfe, besonders erc!

                  Kommentar


                  • #10
                    Die Ausführungszeit sollte in der Form linear mit den Usern steigen. Das kannst du aber auch deutlich beschleunigen, indem du für jeden Nutzer die "Nachbarn" vorausberechnest und in der Datenbank speicherst. Das ist dann wahrscheinlich immer noch linear, aber flacher und von den Produkten oder eventuell nur Bewertungen abhängig. Vorteil dabei ist noch, du ersparst dir den abartigen Query...

                    Kommentar

                    Lädt...
                    X