… ist der Titel einer der besten Diplom- bzw. Magisterarbeiten aller Studien der Technischen Fakultät an der Universität Klagenfurt und wurde vom Förderverein Technische Fakultät mit EUR 750,– ausgezeichnet. Der Autor und Preisträger, Herr DI Markus Aschinger und frühere Projektmitarbeiter am Institut für Angewandte Informatik, Forschungsgruppe Intelligente Systeme und Wirtschaftsinformatik, ist mittlerweile nach Oxford an die dortige Universität gewechselt um an seiner Dissertation zu arbeiten. Der Preis wurde im Rahmen der Eröffnung des akademischen Jahres 2010/2011 übergeben. Die zweite Preisträgerin stellen wir im Laufe der nächsten Woche vor, also beleiben Sie dran!
Kurzfassung:
Recommender-Systeme haben sich in den letzten Jahren zu einem fixen Bestandteil vieler E-Commerce Plattformen entwickelt und unterstützen potentielle Kunden, indem Sie ihnen personalisierte Produktvorschläge abgestimmt auf ihr Benutzer- und Anforderungsprofil unterbreiten. Ein Vorschlag beinhaltet dabei ein oder mehrere Objekte einer bestimmten Produktkategorie aus einer zumeist großen Menge an verfügbaren Produkten. In vielen E-Commerce Szenarien suchen Kunden jedoch nicht nach einem einzelnen Produkt, sondern nach einer Menge von wohlunterscheidbaren und aufeinander abgestimmten Produkten, die zusammen eine Einheit in Form eines Produktbündels bilden. Beispielsweise treffen Kunden im E-Tourismus bei einer Reiseplanung entweder eine Auswahl aus einer Reihe vordefinierter Packages oder sie kombinieren wahlweise Produkte wie Hotels, Restaurants, interessante Events oder Sehenswürdigkeiten, etc. Benutzer führen hierbei oft einen Synthesevorgang vergleichbar mit einem Konfigurationsprozess durch, wenn sie Produkte manuell zu Bündeln zusammenfügen und aufeinander abstimmen. Recommender-Systeme sind jedoch nur bedingt zur automatisierten Lösung dieser Problemstellung geeignet, da die bestgereihten Einzelprodukte nicht unbedingt das optimale Bündel ergeben müssen oder aufgrund von einzuhaltenden Restriktionen nicht miteinander kompatibel sind.
Die sich daraus ergebende Aufgabenstellung ist die automatisierte Ermittlung von Produktbündeln in Domänen wie beispielsweise dem E-Tourismus- oder dem Finanzdienstleistungssektor. Dies erfordert die Entwicklung eines intelligenten Konfigurationssystems, das einerseits die Konsistenz der Produktbündel garantiert und andererseits die Anforderungen und Präferenzen des Benutzers berücksichtigt.
Konfigurationssysteme haben sich in den letzten Jahren zu einer der erfolgreichsten Anwendungen von AI-Technologien entwickelt und erleichtern die Erstellung komplexer Produkte und Services durch die Reduktion von Fehlerraten und Durchlaufzeiten im Vergleich zu manuell gesteuerten Prozessen. Das Problem der Berechnung von Produktbündeln unterscheidet sich jedoch von traditionellen technischen Konfigurationsproblemen in der Form, dass der Suchraum durch eine geringere Anzahl an Nebenbedingungen eingeschränkt wird. Anstatt der Bildung eines neuen physischen Produktes handelt es sich hierbei um eine immaterielle Zusammensetzung bereits bestehender Produkte. Daraus folgt, dass die Anzahl an Kombinationsmöglichkeiten in der Regel weit größer ist und die Auffindung der optimalen Lösung bei Problemen dieser Art einen hohen Stellenwert hat. Bezüglich Optimalität sollte das System das Produktbündel ermitteln, das die Anforderungen und Präferenzen des Benutzers am besten erfüllt. Typische Konfiguratoren verfügen jedoch über keine bzw. unzureichende Personalisierungsmöglichkeiten, d.h. sie adaptieren ihr Berechnungsverfahren nicht aufgrund des aktuellen Benutzers.
Im Rahmen der Diplomarbeit ist ein wissensbasierter Konfigurator zur Lösung der genannten Aufgabenstellungen entwickelt worden, der durch die Kombination mit Recommender-Systemen um zusätzliche Personalisierungsfunktionalitäten erweitert wurde. Zur Sicherstellung der Konsistenz dient eine Wissensbasis, die die gültigen Produktkombinationen und die zu beachtenden Einschränkungen der Anwendungsdomäne beinhaltet. Beispielsweise sollten sich die empfohlenen Freizeitaktivitäten nach Möglichkeit in der Nähe der Unterkunft befinden oder vorgeschlagene Sehenswürdigkeiten für eine Familie explizit als für Kinder geeignet ausgewiesen sein.
In der Optimierung wird zwischen impliziten und expliziten Präferenzen unterschieden. Die Recommender ermitteln die bestgereihten Produktinstanzen für die einzelnen Leistungskategorien und ermöglichen somit durch die Vorfilterung des Problemraums die Berücksichtigung impliziter Benutzerpräferenzen, die sich aus einem Benutzermodell ableiten. Explizite Benutzerpräferenzen hingegen werden entweder in der Wissensbasis des Konfigurators abgelegt oder im Verlauf einer Interaktion vom jeweiligen Benutzer definiert. Die Reihung der ausgewählten Produktbündel wird unter Berücksichtigung der eben genannten impliziten und expliziten Präferenzen im Lösungsprozess optimiert. Der praktische Teil der Arbeit beinhaltet weiters die Umsetzung und Einbindung verschiedener Berechnungsmethoden, wie beispielsweise den Zugriff auf einen User Model Service oder auf einen System-Kontext, wodurch zusätzliche Informationen wie z.B. die Wettervorhersage in der Lösungsfindung berücksichtigt werden können.
Der gewählte Ansatz unterstützt einen mehrstufigen Interaktionsprozess während der Lösungssuche. Mehrere aufeinander aufbauende Suchvorgänge können logisch zu einer übergreifenden Session zusammengefasst werden, wobei diese auch zeitlich voneinander getrennt sein können. Die Menge der Präferenzen kann in jedem Interaktionsschritt basierend auf den vorgeschlagenen Lösungen erweitert bzw. modifiziert werden. Darüber hinaus können Teilmengen der berechneten Produktbündel in eine neue Lösungssuche übernommen werden. Man kann somit beispielsweise definieren, dass man mit dem vorgeschlagenen Hotel und den Veranstaltungen zufrieden ist, jedoch am letzten Abend in einem besseren Restaurant speisen möchte und dafür auch bereit ist, entsprechend mehr Geld auszugeben.
Die vorliegende Diplomarbeit gliedert sich in einen theoretischen und einen praktischen Teil. Beginnend mit einer Beschreibung der Problemstellung sowie des gewählten Lösungsansatzes wird anhand eines möglichen Szenarios aus dem E-Tourismus die Problemstellung näher erläutert. Anschließend wird zu den zentralen Themengebieten Constraint Programming und Konfiguration das wesentliche theoretische Hintergrundwissen aufbereitet. Konkret wird bezüglich Constraints auf Modellierungstechniken, aktuelle Lösungsverfahren und Optimierungstechniken eingegangen. Weiters werden derzeit verfügbare Constraint Programming Systeme vorgestellt und die Auswahl des für die praktische Realisierung verwendeten Tools begründet. Im Bezug auf Konfigurationssysteme erfolgt nach einer Begriffsabgrenzung und der Beschreibung möglicher Anwendungsgebiete eine Vorstellung und ein Vergleich verschiedener Wissensrepräsentationsmechanismen.
Für die konkrete Umsetzung wurde der Konfigurator in die Personalisierungsinfrastruktur ISeller eingebettet. Es erfolgt eine Beschreibung der Architektur des Gesamtframeworks sowie im speziellen des im Rahmen der Arbeit umgesetzten Konfigurators. Weiters werden die Komponenten des Frameworks vorgestellt, mit denen der Konfigurator interagiert bzw. die vom Konfigurator aufgerufen werden. Anschließend wird der verwendete Modellierungsansatz sowie die einzelnen Bestandteile des Modells vorgestellt. Darauf aufbauend erfolgt eine detaillierte Beschreibung des verwendeten Optimierungsmodells und der unterstützten Verfahren zur Lösungsermittlung. Zur Überprüfung der praktischen Einsetzbarkeit des Systems wurde eine Evaluierung auf Basis von Realdaten aus dem E-Tourismus durchgeführt. Die Evaluation hat gezeigt, dass der implementierte Ansatz in der Lage ist, Probleminstanzen von realistischer Größe in akzeptabler Zeit lösen zu können.
