In dieser Arbeit wird eine flexible, erweiterbare und doma¨nenunbha¨ngige Integration von Online-RecSys-Funktionen in ein Datenstrommanagementsystem (DSMS) vorgestellt. Dazu werden neue logische Operatoren eingefu¨hrt, mit der Nutzer eines DSMS auf einer abstrakten Ebene RecSys-Funktionen nutzen ko¨nnen. Des Weiteren wird eine beispielhafte Realisierung durch physische Operatoren vorgestellt, wie sie aus den logischen Operatoren durch Transformationsregeln erzeugt werden kann. Durch dieses Konzept ko¨nnen Benutzer ein RecSys mit Hilfe einer Anfragesprache auf die doma¨nenspezifischen Bedu¨rfnisse anpassen und mit anderen Funktionen eines DSMS kombinieren. Des Weiteren bringt ein DSMS einige Eigenschaften (z. B. Anfrageplanoptimierung, Fragmentierung, Scheduling etc.) mit, von denen ein Online-RecSys profitieren kann. Die Flexibilita¨t eines DSMS ermo¨glicht den Vergleich und die Evaluation verschiedener RecSys-Algorithmen durch den Benutzer.
Recommender-Systeme (RecSys) haben das Ziel, das Interesse eines Benutzers an einem bestimmten Objekt zu scha¨tzen, um dem Benutzer aus einer großen Menge an Objekten die subjektiv interessantesten Objekte zu empfehlen. Eine ga¨ngige Methode ist das modellbasierte, kollaborative Filtern (CF), bei dem aufgrund von bekannten Objektbewertungen verschiedener Benutzer (z. B. Produktbewertungen) ein Modell angelernt wird, mit dem gescha¨tzt werden kann, wie ein Benutzer unbekannte Objekte bewerten wu¨rde. Durch die Entwicklung von Online-Algorithmen fu¨r das CF ko¨nnen neue Bewertungen von Benutzern in die Modelle integriert werden, ohne dass das Modell von Grund auf neu gelernt werden muss. Das ermo¨glicht eine neue Betrachtung des RecSys-Problems: Wa¨hrend bisherige Methoden das RecSys-Problem als periodisches Anlernen eines Modells basierend auf einen statischen und endlichen Datensatz betrachten, kann durch Online-Algorithmen das Problem als Verarbeitung von Bewertungs-Ereignissen eines kontinuierlichen und potenziell unendlichen Datenstroms betrachtet werden. Das hat den Vorteil, dass durch die sofortige Integration neuer Bewertungsinformationen nicht nur das grundsa¨tzliche Interesse, sondern auch das aktuelle Interesse des Benutzers beru¨cksichtigt werden kann.
Zur Konzeption eines datenstrombasierten RecSys schlagen wir vor, auf ein anwendungsunabha¨ngiges und generisches Datenstrommanagementsystem (DSMS) aufzubauen. Die Eingabedaten werden als kontinuierlich auftretende, zeitannotierte Ereignisse eines potenziell unendlichen Datenstroms betrachtet. Das DSMS berechnet mit Hilfe von Datenstrom-Operatoren und Anfragepla¨nen kontinuierlich ein RecSys-Modell. Dieser Ansatz hat folgende Vorteile: (1) Die Modellierung der Daten als Datenstro¨me kommt dem realen Einsatz eines RecSys na¨her als die Verwendung von statischen Datensa¨tzen.
(2) Ein DSMS bringt als Grundlage fu¨r ein RecSys bereits Konzepte und Operatoren zur effizienten Verarbeitung von Datenstro¨men mit temporal koha¨renten Ereignissen mit.
(3) In einem DSMS kann ein RecSys in logische Teile zerlegt werden, welche jeweils durch einen Operator repra¨sentiert werden. Das ermo¨glicht eine flexible und auf die konkrete Anwendung angepasste Komposition von RecSys-Operatoren mit Standardoperatoren, z. B. fu¨r die Datenvor- bzw. -nachbearbeitung, Kontextmodellierung etc.
(4) Eine Aufgabe, zum Beispiel das Modelllernen, kann durch austauschbare Operatoren mit gleicher Semantik aber unterschiedlicher Implementierung realisiert werden. Das ermo¨glicht den Vergleich sowie den bedarfsgerechten Einsatz von verschiedenen Lernalgorithmen.
Ziel der Arbeit ist die Einfu¨hrung eines generischen Konzepts zur Integration von RecSys-Funktionen in ein DSMS. Dazu fu¨hren wir im folgenden Abschnitt zuna¨chst die Grundlagen ein und stellen in Abschnitt 3 verwandte Arbeiten vor. Danach beschreiben wir die logischen Operatoren fu¨r die Umsetzung eines RecSys (Abschnitt 4) und stellen eine Transformation in physische Operatoren vor (Abschnitt 5). In Abschnitt 6 diskutieren wir anschließend einige Entscheidungen unseres Konzepts und stellen Alternativen vor. Zum Schluss pra¨sentieren wir in Abschnitt 7 unsere prototypische Implementierung in ein Open-Source-DSMS und zeigen die Machbarkeit durch eine Evaluation, bevor wir mit einer Zusammenfassung und einem Ausblick die Arbeit beenden.
Ein RecSys hat die Aufgabe einem aktiven Benutzer u0 ∈ U eine Menge an Objekten aus I (Menge aller Objekte) zu empfehlen, fu¨r die dieser sich interessiert (Empfehlungsmenge). Dazu scha¨tzt das RecSys fu¨r jedes zur Empfehlung infrage kommende Objekt eine Bewertung rˆ ∈ R, welche das Interesse des Benutzers an dem Objekt quantifiziert. Die Menge der infrage kommenden Objekte wird als Menge der Empfehlungskandidaten bezeichnet. Die Empfehlungsmenge wird durch die K Objekte der Empfehlungskandidaten gebildet, die die ho¨chsten Bewertungen haben (Top-K-Menge). Um die Bewertung eines Objekts fu¨r einen Benutzer bestimmen zu ko¨nnen, ermittelt das RecSys (z. B. mit der MatrixFaktorisierung) eine Anna¨herung fˆR an eine wahre aber unbekannte Bewertungsfunktion fR : U × I → R.
Seit den 1970er/1980er Jahren sind relationale Datenbankmanagementsysteme (DBMS) die bedeutendste Technik, Daten dauerhaft zu speichern. Ein DBMS abstrahiert von der Komplexita¨t der Datenspeicherung und sorgt fu¨r eine effiziente Verarbeitung von komplexen Anfragen, um Daten zu speichern, zu lesen, zu aktualisieren und zu lo¨schen. DBMS sind allerdings nicht mit dem Ziel entwickelt worden, kontinuierlich erzeugte Daten zu verarbeiten. Diese Lu¨cke schließen DSMS, die auf die fortlaufende Verarbeitung von Datenstro¨men ausgelegt sind.
Wa¨hrend ein DBMS wahlfreien Zugriff auf gespeicherte
Daten hat, erha¨lt ein DSMS die Daten von einem
kontinuierlichen Datenstrom (potenziell unendliche Sequenz von
Datenstromelementen). Die Datenstromelemente werden von
einer aktiven Quelle erzeugt und an das DSMS u¨bertragen.
Ein DSMS hat keine Kontrolle u¨ber die Reihenfolge, in der
die Datenstromelemente von der Quelle gesendet werden –
weder innerhalb eines Datenstroms, noch zwischen
verschiedenen Datenstro¨men. Sobald ein Element verarbeitet ist,
wird es verworfen oder archiviert. Das DSMS kann nicht
erneut auf bereits verarbeitete Elemente zugreifen, es sei denn,
sie werden explizit im Arbeitsspeicher gehalten (one-pass
paradigma). Dies kann allerdings nur fu¨r einen begrenzten Teil
der Datenstromelemente geschehen, da der Speicher im
Gegensatz zum Datenstrom in der Gro¨ße begrenzt ist [
Die Verarbeitung der Daten in einem DBMS erfolgt
u¨blicherweise mit Hilfe von Einmal-Anfragen. Diese werden
einmalig auf aktuellem Datenbestand ausgefu¨hrt und der
anfragende DBMS-Benutzer erha¨lt einmalig eine Antwort. Bei
der Verarbeitung von kontinuierlichen Datenstro¨men stellt
der Benutzer eine kontinuierliche Anfrage. Diese wird
einmalig dem DSMS u¨bergeben und produziert kontinuierlich
Ergebnisse [
Eine Anfrage wird von einem DSMS in einen
Anfrageplan u¨bersetzt. Dieser besteht aus Operatoren, die durch
Warteschlangen miteinander verbunden sind. Ein
Anfrageplan kann als gerichteter Graph interpretiert werden,
dessen Knoten die Operatoren und Kanten die Warteschlangen
darstellen. Die Ausfu¨hrung der Operatoren koordiniert ein
Scheduler [
Verschiedene Vero¨ffentlichungen u¨ber inkrementelle oder
online Algorithmen fu¨r CF (z. B. [
Einige Vero¨ffentlichungen nutzen Frameworks zur
Implementierung eines RecSys, die bei der Entwicklung von
datenstrombasierten Systemen unterstu¨tzen. Zum Beispiel setzt
Ali et al. [
Mit StreamRec stellen Chandramouli et al. [
Betrachtet man die Ein- und Ausgabedaten eines RecSys, so kann man diese als folgende Datenstro¨me auffassen: Erstens u¨bertra¨gt die Benutzeranwendung BenutzerObjekt-Bewertungs-Tripel (u, i, r) fu¨r jede Bewertung, die ein Benutzer vornimmt. Zweitens werden von einem Benutzer u Empfehlungen angefordert (z. B. dann, wenn ein Benutzer die Empfehlungsseite der Benutzeranwendung o¨ffnet; im folgenden Empfehlungsanforderungen – engl. Request for Recommendations, RfR – genannt). Drittens sendet das RecSys eine Empfehlungsmenge zuru¨ck an die Benutzeranwendung. Des Weiteren ko¨nnen die Eingabedaten
Learning
Requests for Recommendations Learning Data Updated Models Window
Updated Models Recommending
Candidates
Abbildung 1: Logische Sicht auf die Operatoren eines DSMS-basierten RecSys um ein Benutzerfeedback erga¨nzt werden. Im folgenden erwarten wir das Benutzerfeedback in der selben Form wie neue Bewertungen (u-i-r-Tripel). Mo¨chte man das RecSys kontinuierlich evaluieren, so erha¨lt man einen zusa¨tzlichen Ausgabedatenstrom mit Fehlerwerten, der den Modellfehler angibt.
Zwischen den Ein- und Ausgabedatenstro¨men verarbeiten Datenstromoperatoren einer oder mehrerer Anfragen die Daten. Um ein RecSys mit Hilfe eines DSMS zu realisieren, muss mit Hilfe einer Anfrage aus den Eingabedatenstro¨men (u-i-r-Tripel und Empfehlungsanforderungen) als Antwort ein Datenstrom an Empfehlungsmengen erzeugt werden, der fu¨r jede Empfehlungsanforderung eine aktuelle und personalisierte Liste an Empfehlungen entha¨lt.
Die Anfrage fu¨r ein RecSys haben wir in logische Operatoren zerlegt, die jeweils einen Teil der RecSys-Funktionalita¨t u¨bernehmen. Diese Operatoren bilden eine Abstraktionsebene, sodass der DSMS-Benutzer diese in der Anfrage nutzen kann, ohne die genaue Umsetzung durch physische Operatoren kennen zu mu¨ssen. Wo dies mo¨glich ist, werden diese Operatoren bei der Transformation zu physischen Operatoren durch vorhandene Operatoren ersetzt.
Abbildung 1 zeigt eine U¨ bersicht u¨ber die logischen Operatoren und wie diese in einer Beispielanfrage zusammenha¨ngen. Auf der linken Seite sehen wir die Eingabedatenstro¨me und auf der rechten Seite die Ausgabedatenstro¨me.
Die dazwischenliegenden Operatoren ko¨nnen in drei Kategorien eingeteilt werden: Operatoren zum Lernen des RecSysModells (mittig), zum Empfehlen von Objekten (unten) und zum Evaluieren (oben).
Die Anfrage besteht aus folgenden logischen Operatoren: Window: Ein zeitbasiertes Fenster (umgesetzt durch einen WINDOW-Operator) ermo¨glicht, die Gu¨ltigkeit der Bewertungsdaten zu beschra¨nken. Das kann sinnvoll sein, um ein Modell anzulernen, welches sich auf die neuesten Daten beschra¨nkt und a¨ltere Daten verwirft (z. B. um Concept Drifts zu beru¨cksichtigen). Zusa¨tzlich beschra¨nkt es die Menge der Bewertungsdaten, die im Speicher gehalten werden mu¨ssen.
Sollen alle Daten fu¨r immer behalten werden, so kann dieser Operator entfernt werden.
Train RecSys Model: Dieser Operator lernt aus den Bewertungsdaten ein Modell an. Wenn neue Daten hinzugefu¨gt werden gibt es ein aktualisiertes Modell aus. Das Modell ist fu¨r eine bestimmte Zeitspanne gu¨ltig, sodass zu jedem Zeitpunkt genau ein Modell fu¨r die Vorhersage der Bewertung zusta¨ndig ist.
Recomm. Candidates: Fu¨r jede Empfehlungsanforderung bestimmt dieser Operator die Empfehlungskandidaten. Diese sind in der Regel alle Objekte, die von dem anfordernden Benutzer noch nicht bewertet wurden.
Predict Rating: Dieser Operator wird sowohl fu¨r die Bestimmung der Empfehlungsmenge als auch fu¨r die Evaluation genutzt. Er scha¨tzt die Bewertung des Benutzers fu¨r jeden Empfehlungskandidaten bzw. fu¨r jedes Testtupel ab.
Mit diesem Operator wird sichergestellt, dass genau das Model genutzt wird, welches zum gleichen Zeitpunkt wie die Empfehlungsanforderung bzw. das Testtupel gu¨ltig ist. Das stellt eine deterministische Verarbeitung der Daten sicher, was insbesondere fu¨r die Evaluation von Vorteil ist.
Recommend: Aus den bewerteten Empfehlungskandidaten werden die Objekte ausgewa¨hlt, die dem Benutzer empfohlen werden sollen. Das sind in der Regel die K Objekte mit den ho¨chsten, gescha¨tzten Bewertungen (Top-K-Menge). Eine weitere Mo¨glichkeit besteht darin, nur Elemente mit einer minimalen Bewertung zu beru¨cksichtigen.
Extract Test Data: Um das RecSys zu evaluieren, gibt dieser Operator neben den Lerndaten auch Testdaten aus. Eine mo¨gliche Implementierung filtert 10 % der Bewertungsdaten als Testdaten aus und leitet die restlichen Daten als Lerndaten an den Modelllerner weiter.
Test Prediction: Dieser Operator implementiert eine Evaluationsmetrik, z. B. Root Mean Square Error (RMSE). Dabei vergleicht er die wahren Bewertungen aus den Testdaten mit den gescha¨tzten Bewertungen zu den Testdaten oder die wahre Position in einem Ranking mit der Position aufgrund der gescha¨tzten Bewertungen. Der daraus resultierende Modellfehler wird zu einem gleitenden Durchschnittswert oder einem gesamten Durchschnittswert aggregiert.
Die logischen Operatoren werden durch Transformationsregeln in physische Operatoren u¨berfu¨hrt. Abbildung 2 zeigt ein Beispiel fu¨r einen physischen Anfrageplan, der aus einer Anfrage generiert wird, der die logischen Operatoren nutzt. Die linke Spalte entha¨lt die Operatoren fu¨r die Evaluation (entspricht dem oberen Teil von Abbildung 1), die mittlere Spalte die Operatoren fu¨r das Lernen des Modells (mittlerer Teil von Abbildung 1) und die rechte Spalte die Operatoren fu¨r die Berechnung der Empfehlungsmenge (unterer Teil von Abbildung 1). Dabei sind die Operatoren, die zu einem logischen Operator aus Abbildung 1 geho¨ren, durch ein gestricheltes Ka¨stchen zusammengefasst. Wo es mo¨glich ist,
Test Prediction
Predict Rating Extract
Test Data Bind
Input Stream send RMSE map aggregate time window map predict rating cross product ITTT access ratings str.
Train RecSys Model
BRISMF time window
Window
Abbildung 2: Physischer Operatorplan
werden die logischen Operatoren durch vorhandene
physische Basisoperatoren (Operatoren mit durchgezogener
Linie) implementiert. Neue, speziell fu¨r die RecSys-Funktion
implementierte physische Operatoren (mit gestrichelter,
dicker Linie) sind:
– ITTT: Impl. der Evaluationsmethode ITTT [
Im folgenden wird die Verarbeitung der Datenstromelemente anhand des physischen Anfrageplans aus Abbildung 2 na¨her erla¨utert. Dazu werden die drei Teilgraphen Lernen des Modells, Bestimmung der Empfehlungsmenge und Berechnung des Modellfehlers in jeweils einem Abschnitt behandelt.
Der ACCESS-Operator ist fu¨r die Anbindung von Datenstro¨men zusta¨ndig. Mit ihm werden das Transportprotokoll sowie das Datenformat festgelegt. Aus jedem ankommenden Datenstromelement wird ein Tupel in der Form (u, i, r) erzeugt, das die Benutzer-ID u, die Objekt-ID i sowie die Bewertung r des Benutzers u fu¨r das Objekt i entha¨lt. Außerdem wird der Gu¨ltigkeitszeitraum des Datenstromelements festgelegt. Gibt die Datenquelle einen Zeitstempel mit, so kann dieser als Startzeitpunkt des Gu¨ltigkeitsintervalls genutzt werden. Andernfalls wird der aktuelle Zeitpunkt als Startzeitpunkt genutzt. Bewertungsdaten sind initial unendlich gu¨ltig und erhalten somit als Endzeitpunkt des Gu¨ltigkeitsintervals den Wert ∞.
Der Operator ITTT implementiert die Evaluationsmethode Interleaved Test-Than-Train (ITTT), die aus den Bewertungsdaten Tupel als Lern- und Testdaten erzeugt. Als Lerndaten werden alle Bewertungsdaten ohne A¨ nderung weitergeleitet. Auf die Erzeugung der Testdaten wird spa¨ter bei der Beschreibung der Evaluation na¨her eingegangen.
Ein TIME-WINDOW-Operator beschra¨nkt die Gu¨ltigkeit der Lerndaten. So kann zum Beispiel festgelegt werden, dass die Lerndaten in dem BRISMF-Operator nur fu¨r 30 Tage lang send recomm set top K select predict rating cross product recomm cand cross product time window access RfR stream Recommend Predict Rating Recomm.
Candidates
Bind
Input
Stream
beru¨cksichtigt werden sollen. Der BRISMF-Operator
implementiert den Lernalgorithmus BRISMF [
Zu jeder Empfehlungsanforderung eines Benutzers u soll eine Menge an Empfehlungen ermittelt werden. Dazu bindet ein ACCESS-Operator den Eingabedatenstrom mit den Anforderungen und ein TIME-WINDOW-Operator setzt deren Gu¨ltigkeit. Das Gu¨ltigkeitsintervall wird so gesetzt, dass diese nur zum Zeitpunkt der Empfehlungsanforderung gu¨ltig sind und nach Verarbeitung direkt verworfen werden.
Zur Bestimmung der Empfehlungskandidaten werden der Datenstrom der Empfehlungsanforderungen und der Datenstrom der Modelle, der von dem BRISMF-Operator erzeugt wird, mit einem Kreuzprodukt-Operator zusammengefu¨hrt. Dieser Operator beru¨cksichtigt die Gu¨ltigkeitsintervalle, sodass nur Datenstromelemente mit u¨berlappenden Intervallen zusammengefu¨hrt werden. Da der BRISMF-Operator Modelle in der Art erzeugt, so dass zu jedem Zeitpunkt genau ein Modell gu¨ltig ist, wird jeder Empfehlungsanforderung genau ein Modell zugeordnet. Der RECOMM-CAND-Operator bekommt anschließend die Anforderungen mit den passenden Modellen und erzeugt einen Datenstrom, der fu¨r jedes in dem Modell nicht bewertete Objekt i des Benutzers u ein Tupel (u, i) mit dem anfordernden Benutzer und dem nicht bewerteten Objekt entha¨lt.
Im na¨chsten Schritt wird fu¨r jeden Empfehlungskandidaten eine Bewertung gescha¨tzt. Dazu wird mit einem Kreuzprodukt-Operator zu jedem Empfehlungskandidaten das temporal passende Modell zugeordnet. Der PREDICT-RATINGOperator nutzt nun das jeweilige Modell zu Bestimmung der Scha¨tzung und gibt zu jedem Empfehlungskandidaten ein Tupel (u, i, rˆ) aus, welches den Benutzer u, den Empfehlungskandidaten i und die gescha¨tzte Bewertung rˆ entha¨lt.
Anschließend werden aus den bewerteten Empfehlungskandidaten die Objekte fu¨r die Empfehlungsmenge ausgewa¨hlt. In der Beispielanfrage in Abbildung 2 werden dazu mit einem SELECT-Operator die Kandidaten entfernt, deren gescha¨tzte Bewertung kleiner als ein bestimmter Schwellwert ist (z. B. 3,5). Von den verbleibenden Kandidaten werden mit dem TOP-K-Operator die K Objekte mit den gro¨ßten Bewertungen ausgewa¨hlt (z. B. K = 8) und an den Ausgabedatenstrom u¨bergeben.
Fu¨r die Evaluation werden vom ITTT-Operator Testdaten erzeugt. Ein Testdatum (u, i, r) wird als ein Empfehlungskandidat i fu¨r einen anfragenden Benutzer u betrachtet und vom PREDICT-RATING-Operator um eine gescha¨tzte Bewertung rˆ erweitert. Die PREDICT-RATING-Operatoren fu¨r die Berechnung der Empfehlungen und fu¨r die Evaluation haben die gleiche Implementierung: Sie erhalten vom vorgelagerten CROSS-PRODUCT-Operator ein Tupel, welches einen Benutzer u, ein Objekt i, ein Modell fˆ und evtl. beliebig weitere Attribute besitzt. Die Ausgabe ist in beiden Fa¨llen ein Tupel mit dem Benutzer u, dem Objekt i, der gescha¨tzten Bewertung rˆ durch Anwendung des Modells rˆ = fˆ(u, i) und alle weiteren Attribute des Eingabetupels (ohne das Modell fˆ, welches nach der Berechnung von rˆ im folgenden Verlauf nicht mehr beno¨tigt wird). Fu¨r die Evaluation za¨hlt zu den weiteren Attributen des Eingabetupels insbesondere die wahre Bewertung r, die auch im Ausgabetupel enthalten ist. Somit gibt der PREDICT-RATING-Operator fu¨r die Evaluation ein Tupel (u, i, r, rˆ) aus.
Im nachfolgenden Verlauf wird nun ein Fehlerwert berechnet. In unserer Beispielanfrage wird dazu ein gleitender RMSE berechnet. Dazu berechnet zuerst ein MAP-Operator den quadratischen Fehler se = (r − rˆ)2 der Scha¨tzung. Anschließend wird mit einem TIME-WINDOW-Operator die gleitende Zeitspanne festgelegt, u¨ber die der Fehlerwert aggregiert werden soll (z. B. die letzten 24 Stunden). Der nachfolgende AGGREGATE-Operator berechnet das arithmetische Mittel der quadratischen Fehler, die sich in einem Aggregationsfenster befinden (z. B. alle Werte der letzten 24 Stunden). Abschließend berechnet der letzte MAP-Operator die Quadratwurzel aus dem aggregierten Fehlerwert, welches dem RMSE u¨ber das Aggregationsfenster entspricht. Diese Werte werden an den Ausgabedatenstrom u¨bergeben.
Fu¨r die Evaluation ist es wichtig, dass zum Testen des
Modells das zu testende Datum nicht im Modell enthalten ist.
Eine einfache Mo¨glichkeit dies sicherzustellen ist die
Trennung von Test- und Lerndaten. Dies kann durch einen
ROUTE-Operator realisiert werden, der zufa¨llig 10 % der Daten
als Testdaten und die restlichen Daten als Lerndaten
weiterleitet. Der hier vorgestellte Operator implementiert
stattdessen die Evaluationsmethode Interleaved Test-Than-Train
[
Um sicherzustellen, dass zur Scha¨tzung der Bewertung eines jeden Testdatums ein Modell genutzt wird, dass nicht das Testdatum, aber ansonsten so viele Lerndaten wie mo¨glich entha¨lt, wird das Gu¨ltigkeitsintervall des Testdatums vom ITTT-Operator angepasst. Ist ein Lerndatum im Gu¨ltigkeitsintervall [ts, te) mit dem Startzeitpunkt ts und dem Endzeitpunkt te gu¨ltig, so wird die Gu¨ltigkeit des Testdatums so gesetzt, dass dieses ungu¨ltig wird, gerade bevor das ¨aquivalente Lerndatum gu¨ltig wird. Bei einem Lerndatum von einem Gu¨ltigkeitsintervall [45, ∞) erha¨lt das Testdatum das Gu¨ltigkeitsintervall [44, 45). Es ist genau wie die Empfehlungsanforderungen nur ein Zeitpunkt gu¨ltig: zum Zeitpunkt t1 = 44 ist es gu¨ltig und zum Zeitpunkt t2 = 45 bereits ungu¨ltig (wegen des halboffenes Intervalls). Wie bereits weiter oben gefordert, soll ein Modell genau alle Lerndaten enthalten, welche im Gu¨ltigkeitsintervall des Modells ebenfalls gu¨ltig sind. Der BRISMF-Operator erzeugt also ein Modell mit dem Lerndatum, welches ab t2 = 45 gu¨ltig ist und das vorherige Modell wird somit zum Zeitpunkt t2 = 45 ungu¨ltig. Der CROSS-PRODUCT-Operator vor dem PREDICT-RATING-Operator der Evaluation fu¨hrt nun unter Beru¨cksichtigung der Gu¨ltigkeitsintervalle Testdatum und MoWindow
Train RecSys Model Recomm. Candidates dell zusammen. Da sich die Gu¨ltigkeitsintervalle des Testdatums und des Modells, welches das zum Testdatum a¨quivalente Lerndatum entha¨lt, nicht u¨berschneiden, werden diese nicht zusammengefu¨hrt. Dafu¨r u¨berschneidet sich das vorherige Modell mit dem Testdatum und wird somit, wie bei der ITTT-Methode gefordert, zur Bewertungsscha¨tzung genutzt. 6.
Bei dem hier vorgestellten Konzept haben wir das RecSysProblem der Scha¨tzung von Bewertungen im Wesentlichen auf drei Operatoren aufgeteilt: TRAIN RECSYS MODEL, RECOMM. CANDIDATES und PREDICT RATING. Das hat den Nachteil, das eine Kopie des gelerntes Modells vom TRAINRECSYS-MODEL-Operator an die anderen beiden Operatoren als Datenstromelement u¨bertragen werden muss. Das fu¨hrt, insbesondere bei großen Modellen, zu einem zusa¨tzlichen Aufwand. Eine Alternative wa¨re, alle drei Operatoren zu einem Operator zu vereinen (vgl. Abbildung 3). Dies ha¨tte folgende Nachteile:
Durch die Aufteilung in drei Operatoren kann jeder Operator fu¨r sich verschiedene Implementierungen (physische Operatoren) haben. Zum Beispiel kann man sich ein RecSys fu¨r Filme vorstellen, bei dem der Benutzer angeben kann, dass er z. B. eine Komo¨die und keinen Actionfilm sehen mo¨chte. Dies wu¨rde die Empfehlungsanforderung um eine Genre-Angabe erweitern. Ein fu¨r diese Anwendung angepasster RECOMM-CAND-Operator kann von vornherein als Empfehlungskandidaten nur die Objekte beru¨cksichtigen, die unter die Kategorie Komo¨die fallen. Alternativ ko¨nnte man zwischen RECOMM CAND und PREDICT RATING einen Selektionsoperator einfu¨gen, der alle Kandidaten, die nicht unter Komo¨die fallen, herausfiltert. Die anderen Operatoren bleiben davon unberu¨hrt. Die Aufteilung sorgt somit fu¨r klare Zusta¨ndigkeiten der Operatoren und ermo¨glicht eine einfachere Erweiterung der Anfrage.
Der TRAIN-RECSYS-MODEL-Operator bestimmt die Gu¨ltigkeit eines Modells, so dass zu jeden Zeitpunkt genau ein Modell gu¨ltig ist. Durch die Zusammenfu¨hrung von Modell und Empfehlungsanforderung durch einen Kreuzprodukt-Operator findet eine deterministische, temporale Zuordnung statt. Diese Zuordnung basiert alleine auf den Gu¨ltigkeitsintervallen und ist nicht davon abha¨ngig, ob aufgrund der Steuerung des Schedulers oder anderer Latenzen zuerst das Lerndatum oder die Empfehlungsanforderung den Operator erreicht. Das Zeitmodell des DSMS sorgt dafu¨r, dass genau das zusta¨ndige Modell reproduzierbar fu¨r die Vorhersage genutzt wird. Des Weiteren kann der TRAIN-RECSYSMODEL-Operator das Modell fu¨r den Gu¨ltigkeitszeitraum anpassen, z. B. um temporale Verzerrungen aufgrund von Concept Drift zu beru¨cksichtigen.
Der RECOMM-CAND-Operator gibt fu¨r jeden Empfehlungskandidaten einer Empfehlungsanforderung ein Datenstromelement aus. Eine Alternative wa¨re die Ausgabe eines Datenstromelements je Empfehlungsanforderung, welches eine Liste von Empfehlungskandidaten entha¨lt. Das ha¨tte den Nachteil, dass der PREDICT-RATING-Operator fu¨r die Bestimmung der Empfehlungen und fu¨r die Evaluation andere Eingabedaten verarbeiten ko¨nnen mu¨sste: im ersten Fall eine Liste von Benutzer-Objekt-Paaren, im zweiten Fall einzelne Benutzer-Objekt-Paare.
Der RECOMM-CAND-Operator gibt nur die Empfehlungskandidaten ohne Modell aus. Dieser Operator ko¨nnte auch das Modell den Empfehlungskandidaten beifu¨gen, so ko¨nnte man auf den CROSS-PRODUCT-Operator vor PREDICT RATING verzichten. Das hier vorgestellte Konzept hat den Vorteil, dass BRISMF an RECOMM CAND und PREDICT RATING unterschiedliche Modelle u¨bergeben kann. Wenn zum Beispiel aus dem Modell fu¨r die Scha¨tzung der Bewertung gar nicht hervorgeht, welche Objekte ein Benutzer nicht bewertet hat (und somit zu den Empfehlungskandidaten geho¨rt), so kann an RECOMM CAND ein Modell u¨bergeben werden, dass die Zuordnung von Benutzer zu unbewerteten Objekten ermo¨glicht, dafu¨r aber keine Scha¨tzung der Bewertung vornehmen kann (z. B. ein einfaches Mapping u 7→ unbewertete Objekte).
Das vorgestellte Konzept haben wir mit dem
erweiterbaren Open-Source-DSMS Odysseus1 [
Die Machbarkeit des Konzepts und die korrekte
Implementierung konnten wir durch den Vergleich der
Evaluationsergebnisse mit MOA und dem MovieLens-Datensatz
nachweisen. Dazu haben wir als BRISMF-Operator die
MOAImplementierung des BRISMF-Algorithmus’ [
In dieser Arbeit haben wir ein Konzept fu¨r die Umsetzung eines modellbasierten und kollaborativen RecSys mit einem auf Operatoren basierten DSMS vorgestellt. Dazu haben wir logische Operatoren definiert, die fu¨r Teilaufgaben eines RecSys zusta¨ndig sind. Zu einem Beispiel eines logischen Anfrageplans fu¨r ein RecSys haben wir eine beispielhafte Umsetzung durch einen physischen Anfrageplan gezeigt und die Umsetzung und deren Alternativen diskutiert. Unser Konzept haben wir durch eine Implementierung in dem DSMS Odysseus und dem Vergleich der Evaluationsergebnisse mit MOA validiert.
Um die Praxistauglichkeit nachzuweisen, soll das Konzept
in Zukunft unter realen Bedingungen, z. B. in einem Living
Lab wie Newsreel2 [