05 Assoziationsanalyse

Was brauchst du als Basiswissen?

Du brauchst etwas Vorwissen aus der Wahrscheinlichkeitsrechnung, also die bedingten Wahrscheinliochkeiten.

Worum geht es?

Die Assoziationsanalyse ist eine Methode im maschinellen Lernen, die darauf abzielt, Zusammenhänge oder Muster in Daten zu finden. Einfach ausgedrückt, versucht sie, herauszufinden, welche Dinge häufig zusammen auftreten. Das Prinzip wird oft in Einkaufskorb-Analysen verwendet, aber es kann auf viele andere Bereiche angewendet werden.

Auf gut deutsch: Wer A kauft, kauft bestimmt auch B oder wer oft C hört, dem gefällt sicher auch D.

Was ist das Ziel?

Du sollst diesen Algorithmus nachvollziehen und an einfachen Beispielen anwenden können.

Auf zum Algorithmus!

Du bekommst eine Liste mit Einkäufen:

Einkäufe.txt

Ziel ist es, herauszubekommen, was Käufer von Orangensaft sonst gern kaufen. Dann kann man diesen Angebote unterbreiten. Du kennst die bedingte Wahrscheinlichkeit. Zeichne ein Baumdiagramm, dass zuerst nach Orangensaftkäufern (O) unterscheidet und dann nach Bananenkäufern (B).

• Wo findet man P(O)?
• Wo findet man P(B)?
• Wo findet man P(B∩O)?
• Was ist die Wahrscheinlochkeit, dass ein Orangensaftkäufer auch Bananen kauft im Baumdiagramm?

Wir wollen zuerst nur wissen, mit welcher Wahrscheinlichkeit Orangensaftkäufer auch Bananen kaufen.

• In wie viel Prozent aller Warenkörbe ist Orangensaft?
• Wie groß ist also die relative Häufigkeit einen Orangensaftkäufer unter allen Einkäufern zu finden?
• In wie viel Prozent aller Warenkörbe sind Bananen und Orangensaft?
• Wie groß ist nun die Wahrscheinlichkeit, dass ein Orangensaftkäufer auch Bananen kauft?

Man könnte das auch umdrehen. Wie groß ist wohl die Wahrscheinlichkeit, dass Bananenkäufer auch Orangensaft kaufen?

• In wie vielen Warenkörben sind Bananen?
• Wie groß ist die relative Häufigkeit, einen Bananenkäufer zu treffen?
• Alle anderen daten hast du. Berechne nun die Wahrscheinlichkeit, dass ein Orangensaftkäufer auch ein Bananenkäufer war.

• Erstelle für dich eine Tabelle mit allen Produkten und allen Häufigkeiten. Zur Kontrolle, es sind 10 verschiedene Produkte und insgesamt 77 Artikel in den Einkaufskörben. Gib die Artikel mit ihren Häufigkeiten hier an.
• Eine Mindesthäufigkeit, die betrachtet werden soll, heißt hier Support. Wir betrachten also nur Artikel, die oft gekauft werden. Bei seltenen Artikeln werden die Voraussagen oft ungenau, weil man zu wenig Daten hat. Wir legen 10% (Anteil an den verkauften Artikeln) fest. Welche Artikel betrachten wir also nicht mehr? (Hinweis: Käse kommt mit einer Wahrscheinlichkeit von 7/77=9% vor.)
• Für welches Produkt sollte man werben, wenn nur die pure Verkaufsmenge interessiert?
• Nun muss man Paare bilden, also schauen, welche Artikel mit anderen wie oft im Warenkorb liegen. Suche zuerst alle Artikel, die mit Bananen im Warenkorb liegen. Zähle nun, wie oft diese vor mit Bananen vorkommen. Gib dies für jeden Artikel an. Insgesamt müssten es 23 Artikel sein.
• Nun kann man aus Gründen der Effizienz wieder seltene Kombinationen aussortieren (das ist für unseren Algorithmus aber nicht wesentlich). Wir legen wieder willkürlich 10% als Grenze fest. Welche Kombinationen fliegen raus?
• Nun haben wir eine bereinigte Datenbasis. Du hast 20 Warenkörbe untersucht. Du weißt, in welchem Bananen sind. Wie groß ist P(Banane)?
• Du weißt, in wie vielen der 20 Warenkörbe Bananen und Orangensaft sind. Wie groß ist P(Banane^Orangensaft)?
• Berechne mit dieser Hilfe P(Orangensaft|Banane). Bei Problemen: Zeichne ein Baumdiagramm, das zuerst nach Banane (und "nicht Banane") und dann nach Orangensaft (und "nicht Orangensaft") verzweigt. Bezeichne P(Banane), P(Orangensaft|Banane) und P(Orangensaft^Banane).
• Nun geht es um Eier. Vermute, ob die Verbindung zwischen Eiern und Bananen größer, gleich oder kleiner ist als die zwischen Orangensaft und Bananen.
• Berechne P(Eier^Bananen).
• Berechne P(Eier|Bananen). Zeichne, wenn du die Hilfe brauchst, ein Baumdiagramm.
• Prüfe folgende Aussage: Die Menschen kaufen viel mehr Orangensaft als Eier. Als kauft auch eine Person, die Bananen kauft, mehr Orangensaft als Eier.
• Nun hat eine Person Bananen gekauft. Für welche drei Produkte machen wir Werbung?

Hinweis: Diese bedingte Wahrscheinlichkeit ist nun unser Ergebnis. Man sagt auch Confidence dazu.

Der Algorithmus selbst

Bringe folgende Bestandteile des Algorithmus in die richtige Reihenfolge.

Wenn man die am stärksten assoziierten Dinge zu einem Element (z.B. Artikel) sucht, dann macht das wie folgt: 1 Das Ergebnis sind die Elemente mit der höchsten bedingten Wahrscheinlichkeit (Confidence) oder alle oberhalb einer Grenze. 2 Sortiere dies Wahrscheinlichkeiten der Größe nach. 3 Sammle alle Datensätze, sodass man sieht, welche Daten gemeinsam vorgekommen sind. 4 Suche alle Datensätze, wo dein zu beachtendes Element drin ist. 5 Berechne die bedingten Wahrscheinlichkeiten P(anderes Element | zu beachtendes Element). 6 Zähle die anderen Artikel, die in diesen Datensätzen vorkommen. Gib für jeden Artikel die Häufigkeit an.

Was muss man wissen/können?

Du musst wissen,

• dass man in Mathe auch mal was Sinnvolles lernt,
• was eine bedingte Wahrscheinlichkeit ist und
• dass die Frage, wer kauft was, wenn er auch schon was anders gekauft hat, eine Frage nach der bedingten Wahrscheinlichkeit ist.

Du kannst

• Datensätze erkennen und sammeln,
• aus diesen die wichtigten auswählen und
• mit denen die bedingte Wahrscheinlichkeit für eine Frage ausrechnen.

Den Aspekt des maschinellen Lernens erkennst du als Sammeln von Daten, Lernen (bedingte Wahrscheinlichkeiten) und Arbeiten mit diesem Wissen ("Pass auf, gleich kauft er noch Ketchup für seine Nudeln!").

Warum Mathe in Informatik? Nun, manchmal sagt man, Informatik sei die technische Seite der Mathematik. Wenn du wirklich alle Einkäufe eines Tages in einem Supermarkt ausrechnen willst, dann machst du das nicht mit Zettel und Stift.

Was können anschließende Themen sein?

Für die Assoziationsanalyse gibt es noch eine Prüfung, ob das Ganze sinnvoll ist, A und B also gemeinsam auftreten. Das machen wir noch ganz schnell.