=Paper=
{{Paper
|id=Vol-1366/paper18.pdf
|storemode=property
|title=Flexible Online-Recommender-Systeme durch die
Integration in ein Datenstrommanagementsystem
|pdfUrl=https://ceur-ws.org/Vol-1366/paper18.pdf
|volume=Vol-1366
|dblpUrl=https://dblp.org/rec/conf/gvd/LudmannGA15
}}
==Flexible Online-Recommender-Systeme durch die
Integration in ein Datenstrommanagementsystem==
https://ceur-ws.org/Vol-1366/paper18.pdf
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