5 Implizites Lernen vom Nutzer¶

5.1.1 Finden von wiederkehrenden Mustern¶

Um eine ,,Warenkorbanalyse" durchzuführen, braucht man erstmal Warenkörbe. Diese entstehen, indem man die einzelnen Songs in der Historie zeitlich gruppiert. Wächst eine Gruppe über eine Grenze (momentan \(5\)), so wird eine neue Gruppe begonnen.

Diese einzelnen Gruppen von Songs fungieren dann als Warenkörbe. Aus diesen gilt es zuerst eine Menge an Songs (im Folgenden Muster ¹ genannt) zu finden, die jeweils oft zusammen in den einzelnen Warenkörben vorkommen. Der naive Ansatz wäre, für jede Kombination der Eingabesongs, das Vorkommen derselben, im Warenkorb zu zählen. Wie man sich bereits denken kann, ist hierfür der algorithmische Aufwand enorm, denn bereits bei einer Menge von \(1000\) unterschiedlichen Songs in der Historie, müssten bereits \(2^{n}-1\) Kombinationen gebildet werden. Denn ein Warenkorb kann man als einer Menge von sich nicht wiederholender Songs sehen, bei der auch die Reihenfolge keine Rolle spielt.

Für die Lösung dieses Problems, gibt es einige etablierte Algorithmen. Der bekannteste ist vermutlich der Apriori–Algorithmus (vergleiche [9], S. 248–253). Statt alle Kombinationen zu betrachten, werden erst alle ,,Einer–Kombinationen" gebildet und die ausgefiltert, welche einen zu niedrigen Support–Count besitzen. Die Grenze legt man vorher fest. Der Support–Count \(support(A)\) ist die Anzahl der Warenkörbe, in denen die Menge von Songs \(A\) vorkommt, geteilt durch die absolute Anzahl der Warenkörbe. Danach werden mit den verbliebenen Zweier–Kombination gebildet, wieder gefiltert, dann die noch relevanten Dreier–Kombinationen und so weiter. Dadurch wird eine große Menge von Kombinationen vermieden.

Seit einiger Zeit haben sich jedoch eine Gruppe effizienterer Algorithmen etabliert. Dazu gehören der FP–Growth (siehe [9] S. 257–259, 272), Eclat (siehe [10]), sowie der hier verwendete RELIM–Algorithmus, der in [11] vorgestellt wurde.

In Tabelle 5.1 sieht man ein Beispiel aus drei Warenkörben, aus denen per Hand mit der naiven Herangehensweise alle möglichen Kombinationen samt deren Support–Count, aufgelistet worden sind.

5.1.2 Der RELIM–Algorithmus¶

Generell gilt FP–Growth als der neue Standard–Algorithmus, der laut mehrerer Quellen andere Algorithmen wie Eclat und RELIM (RE–cursive ELIM–ination) aussticht [12] [13]. In diesem Fall wird trotzdem auf RELIM zurückgegriffen, da dieser für die Zwecke des Autors ausreichend schnell ist und die Datenmenge nie mehr als wenige tausend Songs übersteigen wird. Zudem gibt es mit dem Python–Paket pymining (siehe [Link–19]) bereits eine freie, qualitativ hochwertige Implementierung, während es für FP–Growth nur qualitativ schlechte Implementierungen zu geben scheint, oder welche, die nur für Python–Versionen \(\leq 2,7\) funktionieren.

5.1.3 Ableitung von Regeln aus Mustern¶

Hat man eine Gruppe von häufig zusammen auftretenden Song–Kombinationen gefunden, so können daraus Assoziationsregeln abgeleitet werden. Eine Assoziationsregel verbindet zwei Mengen A und B von Songs mit einer gewissen Wahrscheinlichkeit miteinander. Sie besagen, dass wenn eine der beiden Mengen miteinander gehört wird, dann ist es wahrscheinlich, dass auch die andere Menge daraufhin angehört wird. Regeln werden aus dem Verhalten des Nutzers abgeleitet. Dazu wird jedes Lied, das der Nutzer anhört, in einer Historie zwischengespeichert. Um die generelle Anwendbarkeit der Regel zu beschreiben, wird für jede Regel ein Rating berechnet.

Anmerkung: Im allgemeinen Gebrauch sind Assoziationsregeln nur in eine Richtung definiert. In libmunin sind die Regeln aus Gründen der Einfacheit allerdings bidirektional. So gilt nicht nur, dass man wahrscheinlich die Menge B hört, wenn man A gehört hat (\(A \rightarrow B\)), sondern auch umgekehrt (\(A \leftrightarrow B\)). Ein natürlichsprachliches Beispiel hierfür: \(\frac{2}{3}\) der Basketballspieler essen Cornflakes (\(Basketball \Rightarrow Cornflakes\)). Diese Regel besagt, dass der größere Teil der Basketballspieler Cornflakes isst, aber nicht, dass die meisten Cornflakes–Esser Basketballspieler sind. Da bei libmunin auf beiden Seiten der Regel immer der gleiche Typ (ein oder mehrere Songs) steht und die Beziehung immer ,,werden miteinander gehört" ist, wird hier vereinfachend eine bidirektionale Assoziation angenommen. Dies erlaubt ein Anwenden der Regeln in beide Richtungen.

Um nun aus einem Muster Regeln abzuleiten, teilt man es in alle möglichen verschiedenen, disjunkten Teilmengen auf — allerdings in maximal zwei Teilmengen. Diese beiden Teilmengen nimmt man als die beiden Mengen einer Assoziationsregel an und testet, mittels verschiedener Metriken, wie zutreffend diese ist.

Als Beispiel kann man wieder die Warenkörbe aus Tabelle 5.1 nehmen. Muster mit nur einem Song können nicht weiter aufgeteilt werden, daher müssen diese nicht weiter betrachtet werden. Die Zweier–Kombination sind leicht in zwei disjunkte Teilmengen aufteilbar. Für die Dreier–Kombinationen können mehrere mögliche Teilmengen erstellt werden. Die einzelnen möglichen Regeln werden in Tabelle 5.2 aufgelistet.

Nicht jede Regel ist automatisch eine gute Regel. Ein gängiges Lehrbeispiel wäre hier die Regel \(Basketball \Rightarrow Cornflakes\), also eine Regel, die laut Tabelle 5.3 besagt, dass \(\frac{2}{3}\) aller Basketballspieler zum Frühstück Cornflakes essen. Der Anteil der Menschen die aber insgesamt Cornflakes essen liegt aber bei \(75\%\) — daher ist die Eigenschaft ,,Basketballspieler" sogar im Vergleich, zum durchschnittlichen Anteil von Cornflake–Essern, ein Gegenindiz für diese Eigenschaft.

Um solche kontraproduktiven Assoziationsregeln zu vermeiden, werden für jede Regel zwei Metriken errechnet. Die von libmunin genutzten Metriken wurden dem Buch Datamining Concepts and Techniques ([9], S. 268–271) entnommen: Die Kulczynski–Metrik und der Imbalance–Ratio.

Die Kulczynski–Metrik drückt die Güte der Regel als eine reelle Zahl im Bereich \(\lbrack 0, 1\rbrack\) aus, wobei \(1\) die beste Wertung ist. Grob ausgedrückt besagt die Metrik, wie zutreffend die Regel im Durchschnitt ist. A und B sind im Folgenden die beiden nicht–leeren Teilmengen der Regel:

Diese Metrik ist der Durchschnitt aus zwei Variationen einer anderen Metrik: Dem confidence–Measure (vergleiche [9], S. 254f.):

Diese Metrik gibt an, zu welchem Prozentsatz die Regel zutrifft. Ist der Quotient \(1\), so trifft die Regel bei jedem bekannten Warenkorb zu. Der Zähler \(support(A\cap B)\) beschreibt hier, wie oft sowohl A und B gleichzeitig in einem Warenkorb vorkommen. Bereits allein ist diese Metrik ein gutes Indiz für die Korrektheit einer Regel, die Kulczynski–Metrik prüft zusätzlich beide Seiten der Regel. Um zu zeigen wie sich die Kulczynski–Metrik berechnen lässt, können wir die obige Definition umstellen:

Diese Metrik allein reicht allerdings nicht für eine qualitative Einschätzung einer Regel. Zwar kann die Regel oft zutreffen, doch kann sie, wie im obigen Beispiel mit den Cornflakes, trotzdem kontraproduktiv sein. Daher wird mit dem Imbalance Ratio eine weitere Metrik eingeführt. Der Imbalance Ratio gibt im Bereich \(\lbrack 0, 1\rbrack\) an, wie unterschiedlich beide Seiten der Regel sind. Treten die Muster unterschiedlich oft auf, so steigt diese Metrik. Hier ist der beste Wert die \(0\), der Schlechteste eine \(1\). Er ist gegeben durch:

Sollte die Kulczynski–Metrik kleiner als \(0,\overline{6}\) sein oder der Imbalance–Ratio größer als \(0,35\), so wird die Regel fallen gelassen. Diese Grenzwerte wurden, mehr oder minder willkürlich, nach einigen Tests festgelegt. Sollte die Regel akzeptabel sein, dann werden beide Metriken in eine einzelne, leichter zu handhabende Rating–Metrik verschmolzen:

Dieses Rating wird genutzt, um die einzelnen Assoziationsregeln zu sortieren. Das finale Rating bewegt sich im Bereich \(\lbrack 0, 1\rbrack\), wobei \(1\) das höchste vergebene Rating ist.

Nach einigen Tests erwiesen sich beide Metriken aber nicht als ausreichend um schwache Regeln zu filtern. Daher wurde noch zusätzlich die Lift–Metrik eingeführt (vergleiche [9], S.266). Diese ist definiert als:

Sie vergleicht das erwartete gemeinsame Auftreten der Mengen A und B mit dem tatsächlichen Auftreten in den Warenkörben. Ist der berechnete Wert \(< 0\), so korreliert das Auftreten von B negativ mit A. In diesem Fall wird die Regel ignoriert. Werte größer oder gleich \(0\) bedeuten eine positive/neutrale Korrelation. Das Auftreten von B impliziert das wahrscheinliche Auftreten von A. Für die unter Tabelle 5.3 gezeigten Werte können nun die einzelnen Metriken angewandt werden:

Dieses Ergebnis würde zum Ausschluss der Regel führen, da \(0,6 < 0.\overline{6}\) ist. Allerdings ist dies, für diese kontraproduktive Regel, ein knappes Ergebnis, da die Grenze von \(\overline{0,6}\) willkürlich gewählt wurde.

Beim ImbalanceRatio war \(0\) der beste anzunehmende Wert. Laut dem Ergebnis von \(0,16\) wäre diese Regel also sogar gut balanciert.

Der Lift führt mit einem Ergebnis \(< 0\) zu einer definitiven Filterung der Regel.