Am veröffentlicht

Website Optimierung mit Advanced Analytics – Teil 2: Sequential Pattern

Im ersten Teil der Blogserie wurden bereits die grundlegenden Komponenten und deren Umsetzung mittels Open-Source-Software vorgestellt. Dabei wurde auch deren generelles Zusammenspiel erläutert. Die wesentliche Arbeit der Datenanalyse übernehmen dabei Batch und Streaming Layer, aber was passiert eigentlich hinter den Kulissen und wie kann die Website auf deren Grundlage optimiert werden? Die Lösung liegt in einer Reihe teils komplexer Algorithmen, deren Einsatz exemplarisch erklärt werden soll.

Der zweite Teil der Blogserie wird seinerseits in weitere Teile unterteilt, wobei jeder einen anderen Algorithmus vorstellt. In diesem Teil werden die Möglichkeiten des Einsatzes von Sequential Pattern erläutert.

Algorithmen des Batch Layers

Noch einmal ein kurzer Rückblick auf das Aufgabengebiet des Batch Layers: Hier werden exakte Berechnungen durchgeführt und die Machine-Learning-Algorithmen trainiert. Auf Grund der Komplexität dieser Berechnungen weisen sie eine gewisse Latenz auf, weswegen sie in Intervallen ausgeführt werden. Zur plakativen Beschreibung des Anwendungsbereichs wird das Beispiel eines Online-Reiseportals aus dem ersten Teil durch einen typischen E-Commerce-Shop ersetzt.

Sequential Pattern

Sequential Pattern ist eine Form des Assoziation-Rule-Mining, das sich auf die Erkennung von hilfreichen oder auch unerwarteten Sequenzen in einem Datensatz spezialisiert. Anwendung findet sie vor allem bei Produktvorschlägen auf Grundlage des aktuellen Warenkorbs eines Kunden. Damit können Aussagen nach folgendem Schema erzeugt werden: Kunden, die ein Buch X eines bestimmten Genres kauften, kauften auch Buch Y. Aussagen dieser Kategorie werden auf Grundlage von Mustern getroffen. Dafür betrachtet man die umgesetzten Warenkörbe aller Kunden. Diese entsprechen einer Sequenz von Kaufentscheidungen. Mit Hilfe eines Algorithmus werden dann häufig auftretende Sequenzen ermittelt.

Abbildung 1: Ausgangsdaten

Die Abbildung 1 zeigt den Datensatz mit vier Sequenzen. Jede Sequenz repräsentiert die Produkte, die von einem Nutzer zu unterschiedlichen Zeitpunkten gekauft wurden. Die Sequenz stellt dabei eine geordnete Liste von Itemsets (Produkte die zusammen gekauft wurden) dar. Zum Beispiel zeigt die vierte Sequenz (SID 4), dass ein Nutzer erst b und danach f und g zusammengekauft hat.

Einen klassischen Ansatz zur Erkennung solcher Muster bietet PrefixSpan. Der Algorithmus arbeitet mit einem minimum support threshold. Darunter versteht man einen Schwellwert, ab dem eine Sequenz als relevant betrachtet wird. Der Algorithmus beginnt stets mit einer Sequenz der Länge eins. Danach wird die Sequenz so lange um weitere Items erweitert, bis die Sequenz größer oder gleich dem gewählten Schwellwert ist.

Abbildung 2: Ausschnitt der möglichen Sequenzen

Es entsteht eine Tabelle, wie in Abbildung 2 ausschnittsweise dargestellt. Die Spalte Support gibt dabei an, wie häufig ein bestimmtes Pattern auftritt. In diesem Beispiel wurde ein Schwellwert von 2 gewählt. Daher tauchen nur Pattern auf, die mindestens zweimal im Datensatz enthalten sind. Die Reihenfolge ist dabei relevant: <{a}, {c}> ist ein anderes Pattern als <{c}, {a}>. Der große Mehrwert liegt darin, ein bestimmtes Verhalten zu erkennen, das alle Nutzer vereint. In der Praxis sind im Vergleich zu diesem bewusst simplifizierten Beispiel mehrere Millionen bis Milliarden Sequenzen denkbar.

Ein besonderer Vorteil dieser Art der Analyse ist, dass keine weiteren Informationen über den Nutzer oder dessen Vorlieben benötigt werden. Sein Verhalten kann aus der Masse der Gesamtheit abgeleitet werden.

Fazit

In diesem Artikel wurde Sequential Pattern als typischer Algorithmus des Batch Layers vorgestellt. Als Teil eines Recommendation Systems ermöglicht der Algorithmus, Kunden basierend auf ihrem Warenkorb relevante Produkte anzubieten. Natürlich bieten komplexere Algorithmen weitreichende Optimierungsmöglichkeiten. Als Ausblick soll an dieser Stelle Collaborative Filtering genannt werden.
Collaborative Filtering verhält sich ähnlich wie Sequential Pattern. Der Unterschied liegt darin, dass Vorschläge auf Grundlage von Nutzern mit vergleichbaren Vorlieben/Meinungen erstellt werden. Es erweitert im Prinzip das Vorschlagswesen, indem zusätzliche Daten über den einzelnen Nutzer hinzugezogen werden.