Effiziente Auffindung von Empfehlungen in einem Matrixfaktorisierungsrahmen

Niedrigrangige Matrixfaktorisierung (MF)-Methoden bieten einen der einfachsten und effektivsten Ansätze für kollaboratives Filtern. Dieses Papier ist das erste, das das Problem der effizienten Auffindung von Empfehlungen in einem MF-Rahmen untersucht. Wir reduzieren die Auffindung in einem MF-Modell auf eine scheinbar einfache Aufgabe, das Maximum des Skalarprodukts für den Benutzervektor über die Menge von Itemvektoren zu finden. Soweit wir wissen, wurde das Problem, das Maximum des Skalarprodukts im allgemeinen Fall effizient zu finden, noch nie untersucht. Zu diesem Zweck schlagen wir zwei Techniken für die effiziente Suche vor – (i) Wir indexieren die Itemvektoren in einem binären, räumlich partitionierten Metrikbaum und verwenden einen einfachen Branch-and-Bound-Algorithmus mit einem neuartigen Begrenzungsschema, um effizient exakte Lösungen zu erhalten. (ii) Wir verwenden sphärische Clusterbildung, um die Benutzer basierend auf ihren Vorlieben zu indexieren und berechnen Empfehlungen nur für den repräsentativen Benutzer jedes Clusters im Voraus, um extrem effiziente ungefähre Lösungen zu erlangen. Wir erhalten eine theoretische Fehlergrenze, die die Qualität jedes ungefähren Ergebnisses bestimmt, und verwenden sie zur Kontrolle der Approximation. Beide diese einfachen Techniken sind weitgehend unabhängig voneinander und können daher leicht kombiniert werden, um die Effizienz der Empfehlungsabruf zu verbessern. Wir bewerten unsere Algorithmen an realen Datensätzen für kollaboratives Filtern und zeigen mehr als ×7 Beschleunigung (im Vergleich zur naiven linearen Suche) für die exakte Lösung und über ×250 Beschleunigung für ungefähre Lösungen durch die Kombination beider Techniken.