Flexible Online-Recommender-Systeme durch die Integration in ein Datenstrommanagementsystem Cornelius A. Ludmann Marco Grawunder H.-Jürgen Appelrath Universität Oldenburg Universität Oldenburg Universität Oldenburg Escherweg 2 Escherweg 2 Escherweg 2 26121 Oldenburg, Germany 26121 Oldenburg, Germany 26121 Oldenburg, Germany cornelius.ludmann@uni- marco.grawunder@uni- appelrath@uni- oldenburg.de oldenburg.de oldenburg.de ZUSAMMENFASSUNG auf neu gelernt werden muss. Das ermöglicht eine neue Be- In dieser Arbeit wird eine flexible, erweiterbare und domän- trachtung des RecSys-Problems: Während bisherige Metho- enunbhängige Integration von Online-RecSys-Funktionen in den das RecSys-Problem als periodisches Anlernen eines Mo- ein Datenstrommanagementsystem (DSMS) vorgestellt. Da- dells basierend auf einen statischen und endlichen Datensatz zu werden neue logische Operatoren eingeführt, mit der Nut- betrachten, kann durch Online-Algorithmen das Problem zer eines DSMS auf einer abstrakten Ebene RecSys-Funk- als Verarbeitung von Bewertungs-Ereignissen eines kontinu- tionen nutzen können. Des Weiteren wird eine beispielhafte ierlichen und potenziell unendlichen Datenstroms betrach- Realisierung durch physische Operatoren vorgestellt, wie sie tet werden. Das hat den Vorteil, dass durch die sofortige aus den logischen Operatoren durch Transformationsregeln Integration neuer Bewertungsinformationen nicht nur das erzeugt werden kann. Durch dieses Konzept können Benut- grundsätzliche Interesse, sondern auch das aktuelle Interes- zer ein RecSys mit Hilfe einer Anfragesprache auf die do- se des Benutzers berücksichtigt werden kann. mänenspezifischen Bedürfnisse anpassen und mit anderen Zur Konzeption eines datenstrombasierten RecSys schla- Funktionen eines DSMS kombinieren. Des Weiteren bringt gen wir vor, auf ein anwendungsunabhängiges und gene- ein DSMS einige Eigenschaften (z. B. Anfrageplanoptimie- risches Datenstrommanagementsystem (DSMS) aufzubau- rung, Fragmentierung, Scheduling etc.) mit, von denen ein en. Die Eingabedaten werden als kontinuierlich auftretende, Online-RecSys profitieren kann. Die Flexibilität eines DSMS zeitannotierte Ereignisse eines potenziell unendlichen Daten- ermöglicht den Vergleich und die Evaluation verschiedener stroms betrachtet. Das DSMS berechnet mit Hilfe von Da- RecSys-Algorithmen durch den Benutzer. tenstrom-Operatoren und Anfrageplänen kontinuierlich ein RecSys-Modell. Dieser Ansatz hat folgende Vorteile: (1) Die Modellierung der Daten als Datenströme kommt Keywords dem realen Einsatz eines RecSys näher als die Verwendung recommender system, collaborative filtering, data stream ma- von statischen Datensätzen. nagement system, stream processing (2) Ein DSMS bringt als Grundlage für ein RecSys bereits Konzepte und Operatoren zur effizienten Verarbeitung von Datenströmen mit temporal kohärenten Ereignissen mit. 1. EINLEITUNG (3) In einem DSMS kann ein RecSys in logische Teile zer- Recommender-Systeme (RecSys) haben das Ziel, das In- legt werden, welche jeweils durch einen Operator repräsen- teresse eines Benutzers an einem bestimmten Objekt zu schät- tiert werden. Das ermöglicht eine flexible und auf die konkre- zen, um dem Benutzer aus einer großen Menge an Objek- te Anwendung angepasste Komposition von RecSys-Opera- ten die subjektiv interessantesten Objekte zu empfehlen. toren mit Standardoperatoren, z. B. für die Datenvor- bzw. Eine gängige Methode ist das modellbasierte, kollaborative -nachbearbeitung, Kontextmodellierung etc. Filtern (CF), bei dem aufgrund von bekannten Objektbe- (4) Eine Aufgabe, zum Beispiel das Modelllernen, kann wertungen verschiedener Benutzer (z. B. Produktbewertun- durch austauschbare Operatoren mit gleicher Semantik aber gen) ein Modell angelernt wird, mit dem geschätzt werden unterschiedlicher Implementierung realisiert werden. Das er- kann, wie ein Benutzer unbekannte Objekte bewerten wür- möglicht den Vergleich sowie den bedarfsgerechten Einsatz de. Durch die Entwicklung von Online-Algorithmen für das von verschiedenen Lernalgorithmen. CF können neue Bewertungen von Benutzern in die Mo- Ziel der Arbeit ist die Einführung eines generischen Kon- delle integriert werden, ohne dass das Modell von Grund zepts zur Integration von RecSys-Funktionen in ein DSMS. Dazu führen wir im folgenden Abschnitt zunächst die Grund- lagen ein und stellen in Abschnitt 3 verwandte Arbeiten vor. Danach beschreiben wir die logischen Operatoren fü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 Entschei- dungen unseres Konzepts und stellen Alternativen vor. Zum 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- Schluss präsentieren wir in Abschnitt 7 unsere prototypische banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Implementierung in ein Open-Source-DSMS und zeigen die Copyright is held by the author/owner(s). 96 Machbarkeit durch eine Evaluation, bevor wir mit einer Zu- geplan, bestehend aus logischen Operatoren, erzeugt. Auf sammenfassung und einem Ausblick die Arbeit beenden. einem logischen Anfrageplan können Optimierungen aus- geführt werden (z. B. Veränderung der Operatorreihenfol- 2. GRUNDLAGEN ge), ehe er in einen physischen Anfrageplan mit physischen Ein RecSys hat die Aufgabe einem aktiven Benutzer u0 ∈ Operatoren überführt wird. Physische Operatoren enthal- U eine Menge an Objekten aus I (Menge aller Objekte) zu ten konkrete Implementierungen für die Verarbeitung der empfehlen, für die dieser sich interessiert (Empfehlungsmen- Daten. Das DSMS wählt zu jedem logischen Operator ein ge). Dazu schätzt das RecSys für jedes zur Empfehlung in- oder mehrere physische Operatoren, die für die Operation frage kommende Objekt eine Bewertung r̂ ∈ R, welche das am geeignetsten sind. Interesse des Benutzers an dem Objekt quantifiziert. Die Menge der infrage kommenden Objekte wird als Menge der 3. VERWANDTE ARBEITEN Empfehlungskandidaten bezeichnet. Die Empfehlungsmenge Verschiedene Veröffentlichungen über inkrementelle oder wird durch die K Objekte der Empfehlungskandidaten gebil- online Algorithmen für CF (z. B. [10, 11]) zeigen wie neue det, die die höchsten Bewertungen haben (Top-K-Menge). Lerndaten in CF-Modelle integriert werden können, ohne Um die Bewertung eines Objekts für einen Benutzer bestim- dass das Modell komplett neu gelernt werden muss. Die- men zu können, ermittelt das RecSys (z. B. mit der Matrix- se Algorithmen bieten die Basis für eine datenstrombasier- Faktorisierung) eine Annäherung fˆR an eine wahre aber un- te Verarbeitung von Bewertungsdaten für RecSys. Die Ar- bekannte Bewertungsfunktion fR : U × I → R. beit von Diaz-Aviles et al. [7] stellt eine Methode zur da- Seit den 1970er/1980er Jahren sind relationale Datenbank- tenstrombasierten Verarbeitung von Bewertungsdaten zum managementsysteme (DBMS) die bedeutendste Technik, Da- Lernen eines Matrix-Faktorisierungs-Modells vor. Dazu wird ten dauerhaft zu speichern. Ein DBMS abstrahiert von der das Modell mit Daten aus einem Reservoir aktualisiert, wel- Komplexität der Datenspeicherung und sorgt für eine effi- ches eine Stichprobe des Datenstroms vorhält. Im Gegensatz ziente Verarbeitung von komplexen Anfragen, um Daten zu zu diesen Arbeiten stellen wir keinen neuen Algorithmus vor, speichern, zu lesen, zu aktualisieren und zu löschen. DBMS sondern setzen den Fokus auf die Komposition eines flexiblen sind allerdings nicht mit dem Ziel entwickelt worden, konti- RecSys mithilfe von Datenstromoperatoren, in denen diese nuierlich erzeugte Daten zu verarbeiten. Diese Lücke schlie- Algorithmen als Operatoren integriert werden können. ßen DSMS, die auf die fortlaufende Verarbeitung von Da- Einige Veröffentlichungen nutzen Frameworks zur Imple- tenströmen ausgelegt sind. mentierung eines RecSys, die bei der Entwicklung von daten- Während ein DBMS wahlfreien Zugriff auf gespeicherte strombasierten Systemen unterstützen. Zum Beispiel setzt Daten hat, erhält ein DSMS die Daten von einem kontinuier- Ali et al. [1] Apache Storm ein, um einen CF-Algorithmus lichen Datenstrom (potenziell unendliche Sequenz von Da- zu realisieren. Das datenstrombasierte Data-Mining-Frame- tenstromelementen). Die Datenstromelemente werden von work Massive Online Analysis (MOA) [5] ermöglicht die einer aktiven Quelle erzeugt und an das DSMS übertragen. Evaluation unter anderem von datenstrombasierten RecSys- Ein DSMS hat keine Kontrolle über die Reihenfolge, in der Algorithmen. Im Gegensatz zu unserem Konzept bieten die- die Datenstromelemente von der Quelle gesendet werden – se Arbeiten keinen anwendungsunabhängigen, erweiterbaren weder innerhalb eines Datenstroms, noch zwischen verschie- und flexiblen Ansatz, der auf die Komposition von Daten- denen Datenströmen. Sobald ein Element verarbeitet ist, stromoperatoren setzt. Unser Ansatz kann außerdem von wird es verworfen oder archiviert. Das DSMS kann nicht er- diversen DSMS-Funktionen profitieren. neut auf bereits verarbeitete Elemente zugreifen, es sei denn, Mit StreamRec stellen Chandramouli et al. [6] einen An- sie werden explizit im Arbeitsspeicher gehalten (one-pass pa- satz zur Nutzung eines DSMS für ein RecSys vor. Dort radigma). Dies kann allerdings nur für einen begrenzten Teil wird das DSMS Microsoft StreamInsight genutzt. Im Gegen- der Datenstromelemente geschehen, da der Speicher im Ge- satz zu unserem Konzept werden in StreamRec ausschließ- gensatz zum Datenstrom in der Größe begrenzt ist [4]. lich Basisoperatoren eines DSMS eingesetzt und es ist auf Die Verarbeitung der Daten in einem DBMS erfolgt übli- die Berechnung von Objektähnlichkeiten zur Bestimmung cherweise mit Hilfe von Einmal-Anfragen. Diese werden ein- der Empfehlungsmenge beschränkt. Unser Konzept verfolgt malig auf aktuellem Datenbestand ausgeführt und der an- einen generischeren Ansatz, der auch die Integration von fragende DBMS-Benutzer erhält einmalig eine Antwort. Bei modellbasierten Lernalgorithmen erlaubt und durch logische der Verarbeitung von kontinuierlichen Datenströmen stellt RecSys-Operatoren eine logische Abstraktionsebene für den der Benutzer eine kontinuierliche Anfrage. Diese wird ein- Nutzer des DSMS bietet. malig dem DSMS übergeben und produziert kontinuierlich Ergebnisse [4]. Zur Verarbeitung von relationalen Datenströ- men kann ein DSMS eine datenstrombasierte Variante der 4. LOGISCHE OPERATORSICHT relationalen Algebra einsetzen. Eine kontinuierliche Anfra- Betrachtet man die Ein- und Ausgabedaten eines Rec- ge wird, wie bei Anfragen in DBMSs, in einer Anfragespra- Sys, so kann man diese als folgende Datenströme auffas- che formuliert. Beispiele für DSMS-Anfragesprachen sind die sen: Erstens überträgt die Benutzeranwendung Benutzer- SQL-ähnliche Sprache CQL [3] und die PQL [2]. Objekt-Bewertungs-Tripel (u, i, r) für jede Bewertung, die Eine Anfrage wird von einem DSMS in einen Anfrage- ein Benutzer vornimmt. Zweitens werden von einem Be- plan übersetzt. Dieser besteht aus Operatoren, die durch nutzer u Empfehlungen angefordert (z. B. dann, wenn ein Warteschlangen miteinander verbunden sind. Ein Anfrage- Benutzer die Empfehlungsseite der Benutzeranwendung öff- plan kann als gerichteter Graph interpretiert werden, des- net; im folgenden Empfehlungsanforderungen – engl. Re- sen Knoten die Operatoren und Kanten die Warteschlangen quest for Recommendations, RfR – genannt). Drittens sen- darstellen. Die Ausführung der Operatoren koordiniert ein det das RecSys eine Empfehlungsmenge zurück an die Be- Scheduler [4]. Zu einer Anfrage wird ein logischer Anfra- nutzeranwendung. Des Weiteren können die Eingabedaten 97 Extract Test Data Predict Rating Test Prediction Test Data Predicted Model Ratings Evaluating Test Data Errors Learning Data Updated Models Window Train RecSys Model Learning Data Learning Updated Models Recomm. Candidates Predict Rating Recommend Recommend. Predicted Set of Recommending Candidates Candidates Recommend. Requests for Recommendations Feedback Abbildung 1: Logische Sicht auf die Operatoren eines DSMS-basierten RecSys um ein Benutzerfeedback ergänzt werden. Im folgenden er- Recomm. Candidates: Für jede Empfehlungsanforderung be- warten wir das Benutzerfeedback in der selben Form wie stimmt dieser Operator die Empfehlungskandidaten. Diese neue Bewertungen (u-i-r-Tripel). Möchte man das RecSys sind in der Regel alle Objekte, die von dem anfordernden kontinuierlich evaluieren, so erhält man einen zusätzlichen Benutzer noch nicht bewertet wurden. Ausgabedatenstrom mit Fehlerwerten, der den Modellfehler Predict Rating: Dieser Operator wird sowohl für die Be- angibt. stimmung der Empfehlungsmenge als auch für die Evalua- Zwischen den Ein- und Ausgabedatenströmen verarbei- tion genutzt. Er schätzt die Bewertung des Benutzers für ten Datenstromoperatoren einer oder mehrerer Anfragen die jeden Empfehlungskandidaten bzw. für jedes Testtupel ab. Daten. Um ein RecSys mit Hilfe eines DSMS zu realisieren, Mit diesem Operator wird sichergestellt, dass genau das Mo- muss mit Hilfe einer Anfrage aus den Eingabedatenströmen del genutzt wird, welches zum gleichen Zeitpunkt wie die (u-i-r-Tripel und Empfehlungsanforderungen) als Antwort Empfehlungsanforderung bzw. das Testtupel gültig ist. Das ein Datenstrom an Empfehlungsmengen erzeugt werden, der stellt eine deterministische Verarbeitung der Daten sicher, für jede Empfehlungsanforderung eine aktuelle und persona- was insbesondere für die Evaluation von Vorteil ist. lisierte Liste an Empfehlungen enthält. Recommend: Aus den bewerteten Empfehlungskandidaten Die Anfrage für ein RecSys haben wir in logische Operato- werden die Objekte ausgewählt, die dem Benutzer empfoh- ren zerlegt, die jeweils einen Teil der RecSys-Funktionalität len werden sollen. Das sind in der Regel die K Objekte mit übernehmen. Diese Operatoren bilden eine Abstraktionsebe- den höchsten, geschätzten Bewertungen (Top-K-Menge). Ei- ne, sodass der DSMS-Benutzer diese in der Anfrage nutzen ne weitere Möglichkeit besteht darin, nur Elemente mit einer kann, ohne die genaue Umsetzung durch physische Opera- minimalen Bewertung zu berücksichtigen. toren kennen zu müssen. Wo dies möglich ist, werden diese Extract Test Data: Um das RecSys zu evaluieren, gibt die- Operatoren bei der Transformation zu physischen Operato- ser Operator neben den Lerndaten auch Testdaten aus. Eine ren durch vorhandene Operatoren ersetzt. mögliche Implementierung filtert 10 % der Bewertungsdaten Abbildung 1 zeigt eine Übersicht über die logischen Ope- als Testdaten aus und leitet die restlichen Daten als Lern- ratoren und wie diese in einer Beispielanfrage zusammen- daten an den Modelllerner weiter. hängen. Auf der linken Seite sehen wir die Eingabedaten- Test Prediction: Dieser Operator implementiert eine Eva- ströme und auf der rechten Seite die Ausgabedatenströme. luationsmetrik, z. B. Root Mean Square Error (RMSE). Da- Die dazwischenliegenden Operatoren können in drei Katego- bei vergleicht er die wahren Bewertungen aus den Testdaten rien eingeteilt werden: Operatoren zum Lernen des RecSys- mit den geschätzten Bewertungen zu den Testdaten oder die Modells (mittig), zum Empfehlen von Objekten (unten) und wahre Position in einem Ranking mit der Position aufgrund zum Evaluieren (oben). der geschätzten Bewertungen. Der daraus resultierende Mo- Die Anfrage besteht aus folgenden logischen Operatoren: dellfehler wird zu einem gleitenden Durchschnittswert oder Window: Ein zeitbasiertes Fenster (umgesetzt durch einen einem gesamten Durchschnittswert aggregiert. WINDOW-Operator) ermöglicht, die Gültigkeit der Bewer- tungsdaten zu beschränken. Das kann sinnvoll sein, um ein Modell anzulernen, welches sich auf die neuesten Daten be- 5. PHYSISCHE OPERATORSICHT schränkt und ältere Daten verwirft (z. B. um Concept Drifts Die logischen Operatoren werden durch Transformations- zu berücksichtigen). Zusätzlich beschränkt es die Menge der regeln in physische Operatoren überführt. Abbildung 2 zeigt Bewertungsdaten, die im Speicher gehalten werden müssen. ein Beispiel für einen physischen Anfrageplan, der aus einer Sollen alle Daten für immer behalten werden, so kann dieser Anfrage generiert wird, der die logischen Operatoren nutzt. Operator entfernt werden. Die linke Spalte enthält die Operatoren für die Evaluation Train RecSys Model: Dieser Operator lernt aus den Bewer- (entspricht dem oberen Teil von Abbildung 1), die mittlere tungsdaten ein Modell an. Wenn neue Daten hinzugefügt Spalte die Operatoren für das Lernen des Modells (mittlerer werden gibt es ein aktualisiertes Modell aus. Das Modell ist Teil von Abbildung 1) und die rechte Spalte die Operato- für eine bestimmte Zeitspanne gültig, sodass zu jedem Zeit- ren für die Berechnung der Empfehlungsmenge (unterer Teil punkt genau ein Modell für die Vorhersage der Bewertung von Abbildung 1). Dabei sind die Operatoren, die zu einem zuständig ist. logischen Operator aus Abbildung 1 gehören, durch ein ge- stricheltes Kästchen zusammengefasst. Wo es möglich ist, 98 Bind Bind send send berücksichtigt werden sollen. Der BRISMF-Operator imple- Output Output RMSE recomm set Stream Stream mentiert den Lernalgorithmus BRISMF [11], der ein Modell map top K mit den neuen Daten aktualisiert. Er legt das Gültigkeits- intervall des Modells fest, sodass zu jedem Zeitpunkt genau Recommend ein Modell gültig ist. Der Operator muss sicherstellen, dass aggregate select alle Lerndaten berücksichtigt wurden, die im Gültigkeitsin- Test Prediction tervall des Modells gültig sind. time predict rating window Predict Rating Von Empf.-Anforderungen zu Empf.-Mengen cross map Zu jeder Empfehlungsanforderung eines Benutzers u soll ei- product ne Menge an Empfehlungen ermittelt werden. Dazu bindet predict recomm ein ACCESS-Operator den Eingabedatenstrom mit den An- rating cand Predict Train RecSys Model Recomm. forderungen und ein TIME-WINDOW-Operator setzt deren Rating Candidates cross cross Gültigkeit. Das Gültigkeitsintervall wird so gesetzt, dass die- product BRISMF product se nur zum Zeitpunkt der Empfehlungsanforderung gültig Extract time time sind und nach Verarbeitung direkt verworfen werden. Test ITTT Data window window Bind Zur Bestimmung der Empfehlungskandidaten werden der Bind Window Input Datenstrom der Empfehlungsanforderungen und der Daten- access access Stream Input ratings str. RfR stream strom der Modelle, der von dem BRISMF-Operator erzeugt Stream wird, mit einem Kreuzprodukt-Operator zusammengeführt. Dieser Operator berücksichtigt die Gültigkeitsintervalle, so- Abbildung 2: Physischer Operatorplan dass nur Datenstromelemente mit überlappenden Interval- len zusammengeführt werden. Da der BRISMF-Operator Mo- delle in der Art erzeugt, so dass zu jedem Zeitpunkt genau werden die logischen Operatoren durch vorhandene physi- ein Modell gültig ist, wird jeder Empfehlungsanforderung ge- sche Basisoperatoren (Operatoren mit durchgezogener Li- nau ein Modell zugeordnet. Der RECOMM-CAND-Operator nie) implementiert. Neue, speziell für die RecSys-Funktion bekommt anschließend die Anforderungen mit den passen- implementierte physische Operatoren (mit gestrichelter, di- den Modellen und erzeugt einen Datenstrom, der für jedes cker Linie) sind: in dem Modell nicht bewertete Objekt i des Benutzers u ein – ITTT: Impl. der Evaluationsmethode ITTT [8]. Tupel (u, i) mit dem anfordernden Benutzer und dem nicht – BRISMF: Impl. des Lernalgorithmus’ BRISMF [11]. bewerteten Objekt enthält. – RECOMM CAND: Empfehlungskandidaten. Im nächsten Schritt wird für jeden Empfehlungskandida- – PREDICT RATING: Schätzung von Bewertungen. ten eine Bewertung geschätzt. Dazu wird mit einem Kreuz- Im folgenden wird die Verarbeitung der Datenstromele- produkt-Operator zu jedem Empfehlungskandidaten das tem- mente anhand des physischen Anfrageplans aus Abbildung 2 poral passende Modell zugeordnet. Der PREDICT-RATING- näher erläutert. Dazu werden die drei Teilgraphen Lernen Operator nutzt nun das jeweilige Modell zu Bestimmung des Modells, Bestimmung der Empfehlungsmenge und Be- der Schätzung und gibt zu jedem Empfehlungskandidaten rechnung des Modellfehlers in jeweils einem Abschnitt be- ein Tupel (u, i, r̂) aus, welches den Benutzer u, den Empfeh- handelt. lungskandidaten i und die geschätzte Bewertung r̂ enthält. Anschließend werden aus den bewerteten Empfehlungs- Von Bewertungsdaten zu Modellen kandidaten die Objekte für die Empfehlungsmenge ausge- Der ACCESS-Operator ist für die Anbindung von Daten- wählt. In der Beispielanfrage in Abbildung 2 werden dazu strömen zuständig. Mit ihm werden das Transportprotokoll mit einem SELECT-Operator die Kandidaten entfernt, deren sowie das Datenformat festgelegt. Aus jedem ankommenden geschätzte Bewertung kleiner als ein bestimmter Schwellwert Datenstromelement wird ein Tupel in der Form (u, i, r) er- ist (z. B. 3,5). Von den verbleibenden Kandidaten werden zeugt, das die Benutzer-ID u, die Objekt-ID i sowie die Be- mit dem TOP-K-Operator die K Objekte mit den größten wertung r des Benutzers u für das Objekt i enthält. Außer- Bewertungen ausgewählt (z. B. K = 8) und an den Ausga- dem wird der Gültigkeitszeitraum des Datenstromelements bedatenstrom übergeben. festgelegt. Gibt die Datenquelle einen Zeitstempel mit, so kann dieser als Startzeitpunkt des Gültigkeitsintervalls ge- Von Bewertungsdaten zu Modellfehlerwerten nutzt werden. Andernfalls wird der aktuelle Zeitpunkt als Für die Evaluation werden vom ITTT-Operator Testdaten Startzeitpunkt genutzt. Bewertungsdaten sind initial unend- erzeugt. Ein Testdatum (u, i, r) wird als ein Empfehlungs- lich gültig und erhalten somit als Endzeitpunkt des Gültig- kandidat i für einen anfragenden Benutzer u betrachtet und keitsintervals den Wert ∞. vom PREDICT-RATING-Operator um eine geschätzte Be- Der Operator ITTT implementiert die Evaluationsmetho- wertung r̂ erweitert. Die PREDICT-RATING-Operatoren für de Interleaved Test-Than-Train (ITTT), die aus den Bewer- die Berechnung der Empfehlungen und für die Evaluati- tungsdaten Tupel als Lern- und Testdaten erzeugt. Als Lern- on haben die gleiche Implementierung: Sie erhalten vom daten werden alle Bewertungsdaten ohne Änderung weiter- vorgelagerten CROSS-PRODUCT-Operator ein Tupel, wel- geleitet. Auf die Erzeugung der Testdaten wird später bei ches einen Benutzer u, ein Objekt i, ein Modell fˆ und evtl. der Beschreibung der Evaluation näher eingegangen. beliebig weitere Attribute besitzt. Die Ausgabe ist in bei- Ein TIME-WINDOW-Operator beschränkt die Gültigkeit den Fällen ein Tupel mit dem Benutzer u, dem Objekt i, der Lerndaten. So kann zum Beispiel festgelegt werden, dass der geschätzten Bewertung r̂ durch Anwendung des Modells die Lerndaten in dem BRISMF-Operator nur für 30 Tage lang r̂ = fˆ(u, i) und alle weiteren Attribute des Eingabetupels 99 a) (ohne das Modell fˆ, welches nach der Berechnung von r̂ im Extract Test Data Predict Rating Test Prediction folgenden Verlauf nicht mehr benötigt wird). Für die Eva- luation zählt zu den weiteren Attributen des Eingabetupels Window Train RecSys Model insbesondere die wahre Bewertung r, die auch im Ausgabe- tupel enthalten ist. Somit gibt der PREDICT-RATING-Ope- Recomm. Candidates Predict Rating Recommend rator für die Evaluation ein Tupel (u, i, r, r̂) aus. Im nachfolgenden Verlauf wird nun ein Fehlerwert berech- b) net. In unserer Beispielanfrage wird dazu ein gleitender RM- Extract Test Data Test Prediction SE berechnet. Dazu berechnet zuerst ein MAP-Operator den quadratischen Fehler se = (r − r̂)2 der Schätzung. Anschlie- Window Train And ßend wird mit einem TIME-WINDOW-Operator die gleiten- Predict Rating de Zeitspanne festgelegt, über die der Fehlerwert aggregiert Recommend werden soll (z. B. die letzten 24 Stunden). Der nachfolgende AGGREGATE-Operator berechnet das arithmetische Mittel der quadratischen Fehler, die sich in einem Aggregations- Abbildung 3: Gegenüberstellung: Drei Operatoren fenster befinden (z. B. alle Werte der letzten 24 Stunden). vs. ein Operator für die Bewertungsschätzung Abschließend berechnet der letzte MAP-Operator die Qua- dratwurzel aus dem aggregierten Fehlerwert, welches dem RMSE über das Aggregationsfenster entspricht. Diese Wer- dell zusammen. Da sich die Gültigkeitsintervalle des Testda- te werden an den Ausgabedatenstrom übergeben. tums und des Modells, welches das zum Testdatum äquiva- Für die Evaluation ist es wichtig, dass zum Testen des Mo- lente Lerndatum enthält, nicht überschneiden, werden diese dells das zu testende Datum nicht im Modell enthalten ist. nicht zusammengeführt. Dafür überschneidet sich das vor- Eine einfache Möglichkeit dies sicherzustellen ist die Tren- herige Modell mit dem Testdatum und wird somit, wie bei nung von Test- und Lerndaten. Dies kann durch einen ROU- der ITTT-Methode gefordert, zur Bewertungsschätzung ge- TE-Operator realisiert werden, der zufällig 10 % der Daten nutzt. als Testdaten und die restlichen Daten als Lerndaten wei- terleitet. Der hier vorgestellte Operator implementiert statt- 6. DISKUSSION dessen die Evaluationsmethode Interleaved Test-Than-Train [8]. Mit dieser werden alle Daten sowohl zum Lernen als auch Die Aufteilung der Bewertungsschätzung in drei zum Testen genutzt. Dabei wird ein Testdatum zuerst zum Operatoren Testen des Modells genutzt und anschließend in das Modell Bei dem hier vorgestellten Konzept haben wir das RecSys- integriert. Das hat die Vorteile, dass mehr Testdaten genutzt Problem der Schätzung von Bewertungen im Wesentlichen werden und keine Daten für das Lernen des Modells verloren auf drei Operatoren aufgeteilt: TRAIN RECSYS MODEL, RE- gehen. Letzteres ist insbesondere wichtig, wenn ein RecSys COMM. CANDIDATES und PREDICT RATING. Das hat den im laufenden Betrieb evaluiert werden soll (in dem Fall wür- Nachteil, das eine Kopie des gelerntes Modells vom TRAIN- de das aussortieren von Daten als Testdaten die Schätzungen RECSYS-MODEL-Operator an die anderen beiden Operato- für die realen Benutzer beeinflussen) und wenn temporale ren als Datenstromelement übertragen werden muss. Das Zusammenhänge in den Daten beim Modelllernen berück- führt, insbesondere bei großen Modellen, zu einem zusätzli- sichtigt werden sollen (in dem Fall würden fehlende Daten chen Aufwand. Eine Alternative wäre, alle drei Operatoren ggf. erschweren, die temporalen Zusammenhänge zu erken- zu einem Operator zu vereinen (vgl. Abbildung 3). Dies hät- nen). te folgende Nachteile: Um sicherzustellen, dass zur Schätzung der Bewertung ei- Durch die Aufteilung in drei Operatoren kann jeder Ope- nes jeden Testdatums ein Modell genutzt wird, dass nicht rator für sich verschiedene Implementierungen (physische das Testdatum, aber ansonsten so viele Lerndaten wie mög- Operatoren) haben. Zum Beispiel kann man sich ein Rec- lich enthält, wird das Gültigkeitsintervall des Testdatums Sys für Filme vorstellen, bei dem der Benutzer angeben vom ITTT-Operator angepasst. Ist ein Lerndatum im Gül- kann, dass er z. B. eine Komödie und keinen Actionfilm se- tigkeitsintervall [ts , te ) mit dem Startzeitpunkt ts und dem hen möchte. Dies würde die Empfehlungsanforderung um Endzeitpunkt te gültig, so wird die Gültigkeit des Testda- eine Genre-Angabe erweitern. Ein für diese Anwendung an- tums so gesetzt, dass dieses ungültig wird, gerade bevor das gepasster RECOMM-CAND-Operator kann von vornherein äquivalente Lerndatum gültig wird. Bei einem Lerndatum als Empfehlungskandidaten nur die Objekte berücksichti- von einem Gültigkeitsintervall [45, ∞) erhält das Testdatum gen, die unter die Kategorie Komödie fallen. Alternativ könn- das Gültigkeitsintervall [44, 45). Es ist genau wie die Emp- te man zwischen RECOMM CAND und PREDICT RATING fehlungsanforderungen nur ein Zeitpunkt gültig: zum Zeit- einen Selektionsoperator einfügen, der alle Kandidaten, die punkt t1 = 44 ist es gültig und zum Zeitpunkt t2 = 45 nicht unter Komödie fallen, herausfiltert. Die anderen Ope- bereits ungültig (wegen des halboffenes Intervalls). Wie be- ratoren bleiben davon unberührt. Die Aufteilung sorgt somit reits weiter oben gefordert, soll ein Modell genau alle Lern- für klare Zuständigkeiten der Operatoren und ermöglicht ei- daten enthalten, welche im Gültigkeitsintervall des Modells ne einfachere Erweiterung der Anfrage. ebenfalls gültig sind. Der BRISMF-Operator erzeugt also ein Der TRAIN-RECSYS-MODEL-Operator bestimmt die Gül- Modell mit dem Lerndatum, welches ab t2 = 45 gültig ist tigkeit eines Modells, so dass zu jeden Zeitpunkt genau ein und das vorherige Modell wird somit zum Zeitpunkt t2 = 45 Modell gültig ist. Durch die Zusammenführung von Mo- ungültig. Der CROSS-PRODUCT-Operator vor dem PRE- dell und Empfehlungsanforderung durch einen Kreuzpro- DICT-RATING-Operator der Evaluation führt nun unter Be- dukt-Operator findet eine deterministische, temporale Zu- rücksichtigung der Gültigkeitsintervalle Testdatum und Mo- ordnung statt. Diese Zuordnung basiert alleine auf den Gül- 100 tigkeitsintervallen und ist nicht davon abhängig, ob aufgrund 8. ZUSAMMENFASSUNG UND AUSBLICK der Steuerung des Schedulers oder anderer Latenzen zuerst In dieser Arbeit haben wir ein Konzept für die Umset- das Lerndatum oder die Empfehlungsanforderung den Ope- zung eines modellbasierten und kollaborativen RecSys mit rator erreicht. Das Zeitmodell des DSMS sorgt dafür, dass einem auf Operatoren basierten DSMS vorgestellt. Dazu ha- genau das zuständige Modell reproduzierbar für die Vorher- ben wir logische Operatoren definiert, die für Teilaufgaben sage genutzt wird. Des Weiteren kann der TRAIN-RECSYS- eines RecSys zuständig sind. Zu einem Beispiel eines logi- MODEL-Operator das Modell für den Gültigkeitszeitraum schen Anfrageplans für ein RecSys haben wir eine beispiel- anpassen, z. B. um temporale Verzerrungen aufgrund von hafte Umsetzung durch einen physischen Anfrageplan ge- Concept Drift zu berücksichtigen. zeigt und die Umsetzung und deren Alternativen diskutiert. Unser Konzept haben wir durch eine Implementierung in Die Ausgabe der Empfehlungskandidaten dem DSMS Odysseus und dem Vergleich der Evaluationser- Der RECOMM-CAND-Operator gibt für jeden Empfehlungs- gebnisse mit MOA validiert. kandidaten einer Empfehlungsanforderung ein Datenstrom- Um die Praxistauglichkeit nachzuweisen, soll das Konzept element aus. Eine Alternative wäre die Ausgabe eines Da- in Zukunft unter realen Bedingungen, z. B. in einem Living tenstromelements je Empfehlungsanforderung, welches eine Lab wie Newsreel2 [9], evaluiert werden. Dazu stehen ins- Liste von Empfehlungskandidaten enthält. Das hätte den besondere die für den Datenstromkontext wichtige Parame- Nachteil, dass der PREDICT-RATING-Operator für die Be- ter Latenz, Durchsatz und Speicheranforderungen im Vor- stimmung der Empfehlungen und für die Evaluation andere dergrund. Des Weiteren sollen weitere Algorithmen für die Eingabedaten verarbeiten können müsste: im ersten Fall eine Empfehlungen und die Evaluation (z. B. Ranking-basierte Liste von Benutzer-Objekt-Paaren, im zweiten Fall einzelne Methoden) implementiert werden. Benutzer-Objekt-Paare. Der RECOMM-CAND-Operator gibt nur die Empfehlungs- 9. REFERENCES kandidaten ohne Modell aus. Dieser Operator könnte auch das Modell den Empfehlungskandidaten beifügen, so könnte [1] M. Ali, C. C. Johnson, and A. K. Tang. Parallel man auf den CROSS-PRODUCT-Operator vor PREDICT RA- collaborative filtering for streaming data. University of TING verzichten. Das hier vorgestellte Konzept hat den Vor- Texas Austin, Tech. Rep, 2011. teil, dass BRISMF an RECOMM CAND und PREDICT RA- [2] H.-J. Appelrath, D. Geesen, M. Grawunder, TING unterschiedliche Modelle übergeben kann. Wenn zum T. Michelsen, and D. Nicklas. Odysseus: A highly Beispiel aus dem Modell für die Schätzung der Bewertung customizable framework for creating efficient event gar nicht hervorgeht, welche Objekte ein Benutzer nicht be- stream management systems. In DEBS’12, pages wertet hat (und somit zu den Empfehlungskandidaten ge- 367–368. ACM, 2012. hört), so kann an RECOMM CAND ein Modell übergeben [3] A. Arasu, S. Babu, and J. Widom. The CQL werden, dass die Zuordnung von Benutzer zu unbewerteten continuous query language: semantic foundations and Objekten ermöglicht, dafür aber keine Schätzung der Be- query execution. VLDB Journal, 15(2):121–142, 2006. wertung vornehmen kann (z. B. ein einfaches Mapping u 7→ [4] B. Babcock, S. Babu, M. Datar, R. Motwani, and unbewertete Objekte). J. Widom. Models and issues in data stream systems. In PODS 2002, pages 1–16. ACM, 2002. 7. IMPLEMENTIERUNG UND EVALUATI- [5] A. Bifet, G. Holmes, R. Kirkby, and B. Pfahringer. MOA: Massive online analysis. The Journal of ON Machine Learning Research, 11:1601–1604, 2010. Das vorgestellte Konzept haben wir mit dem erweiterba- [6] B. Chandramouli, J. J. Levandoski, A. Eldawy, and ren Open-Source-DSMS Odysseus 1 [2] umgesetzt. Dazu ha- M. F. Mokbel. StreamRec: A Real-time Recommender ben wir Odysseus um neue Operatoren und Transformati- System. In SIGMOD’11, pages 1243–1246. ACM, 2011. onsregeln erweitert. [7] E. Diaz-Aviles, L. Drumond, L. Schmidt-Thieme, and Die Machbarkeit des Konzepts und die korrekte Imple- W. Nejdl. Real-Time Top-N Recommendation in mentierung konnten wir durch den Vergleich der Evalua- Social Streams. In ACM RecSys, pages 59–66, 2012. tionsergebnisse mit MOA und dem MovieLens-Datensatz [8] J. Gama, I. Zliobaite, A. Biefet, M. Pechenizkiy, and nachweisen. Dazu haben wir als BRISMF-Operator die MOA- A. Bouchachia. A Survey on Concept Drift Implementierung des BRISMF-Algorithmus’ [11] integriert, Adaptation. ACM Comp. Surveys, 1(1), 2013. der eine inkrementelle Matrix-Faktorisierung implementiert. [9] F. Hopfgartner, B. Kille, A. Lommatzsch, Da MOA die Gültigkeit von Lerndaten nicht begrenzt, ha- T. Plumbaum, T. Brodt, and T. Heintz. Benchmarking ben wir den WINDOW-Operator entfernt und die RMSE news recommendations in a living lab. In CLEF’14, über den gesamten Datensatz berechnet (kein gleitender RM- LNCS, pages 250–267. Springer Verlag, 09 2014. SE). Den MovieLens-Datensatz haben wir, wie MOA, zei- lenweise eingelesen um einen Datenstrom zu simulieren und [10] X. Luo, Y. Xia, and Q. Zhu. Incremental collaborative haben nach jedem getesteten Tupel den RMSE ausgegeben. filtering recommender based on regularized matrix Die RMSE-Werte stimmen dabei mit denen von MOA exakt factorization. Knowledge-Based Systems, 27:271–280, überein. Das zeigt, dass die temporale Zuordnung von Lern- 2012. und Testdaten mit den Modellen sowie die Umsetzung der [11] G. Takács, I. Pilászy, B. Németh, and D. Tikk. Evaluationsmethode korrekt funktionieren. Scalable collaborative filtering approaches for large recommender systems. The Journal of Machine Learning Research, 10:623–656, 2009. 1 2 http://odysseus.informatik.uni-oldenburg.de/ http://www.clef-newsreel.org/ 101