7.3 A Priori Algorithmus
Wie bereits erwähnt, gibt es bei Items insgesamt mögliche Item-Mengen (Potenzmenge).
Abbildung 7.2: Potenzmenge von vier Items A,B,C,D
In Abbildung 7.2 sind alle möglichen Kombinationen einer Grundgesamtheit von vier Items dargestellt (inklusive der leeren Menge). Möchte man die Häufigkeit von Item-Mengen und die Konfidenz von Regeln bei einer Grundgesamtheit von Items bestimmen, hat man also ein exponentielles Problem, das mit einem naiven Ansatz nicht lösbar ist. Die erste Lösung fand Agrawal 1993 mit dem A Priori-Verfahren (Agrawal, Imielinski, and Swami 1993), das auch heute noch eines der Standardverfahren der Assoziationsanalyse ist.
Die Aufgabe lautet also: Bestimme alle Assoziationsregeln in einer Datenbank mit N Transaktionen mit und . Das A Priori Verfahren teilt das Problem in 2 Schritte auf:
- Schritt 1: Bestimmung aller häufigen Item-Mengen mit .
- Schritt 2: Für jede häufige Item-Menge: Generierung aller Assoziationsregeln mit .
7.3.1 Bestimmung der häufigen Item-Mengen
Ziel: Aus der Datenbank sollen alle häufigen Item-Mengen mit bestimmt werden. Vorgehen:
- Bestimme zunächst alle häufigen 1-Item-Mengen.
- Betrachte dann die 2-Item-Mengen. Nutze dabei folgende Eigenschaft: Ist eine Teilmenge mit Elementen nicht häufig, dann sind auch alle größeren Mengen, die diese Teilmenge enthalten, nicht häufig. Was das bedeutet, kann man sich mit der Betrachtung der Potenzmenge veranschaulichen: Ermittelt man beispielsweise, dass die 1-Item-Menge A nicht häufig ist, dann sind auch alle Kombinationen mit A nicht häufig, müssen also nicht mehr betrachtet werden. Ist die 2-Item-Menge CD nicht häufig, so müssen auch die Kombinationen ACD, BCD und ABCD nicht mehr betrachtet werden (vgl. Abbildung 7.3).
Abbildung 7.3: A Priori Verfahren: Mengen, die eine nicht häufige Teilmenge enthalten, sind ebenfalls nicht häufig
\begin{algorithm}
\caption{A Priori Schritt 1: Bestimmung der häufigen Item-Mengen}
\begin{algorithmic}
\INPUT Datenbank mit Transaktionen, $minSupport $
\OUTPUT Häufige Item-Mengen
\STATE $(k=1)$
\STATE Erzeuge häufige k-Item-Mengen $(k=1)$
\REPEAT
\STATE Erzeuge Kandidatenmenge ($(k+1)$-Item-Mengen) aus den häufigen $k$-Item-Mengen
\STATE Entferne aus der Kandidatenmenge alle Mengen, die als Teilmenge eine nicht häufige $k$-Item-Menge haben
\STATE Berechne den Support aller Elemente der Kandidatenmenge
\STATE Entferne alle nicht häufigen Item-Mengen aus der Kandidatenmenge
\STATE $k = k + 1$
\UNTIL{ keine neuen häufigen Item-Mengen gefunden werden }
\end{algorithmic}
\end{algorithm}
Führen wir die Bestimmung der häufigen Item-Mengen mit dem Beispiel aus Tabelle 7.2 durch. Sei . Zunächst werden die 1-Item-Mengen betrachtet:
| ItemMenge | Support |
|---|---|
| {Windeln} | 4/5 |
| {Milch} | 4/5 |
| {Bier} | 4/5 |
| {Brot} | 3/5 |
| {Butter} | 2/5 |
| {Käse} | 1/5 |
Butter und Käse sind also nicht häufig, da . Damit müssen auch alle Kombinationen mit Butter und mit Käse nicht mehr betrachtet werden. Jetzt werden aus den häufigen 1-Item-Mengen die 2-Item-Mengen erzeugt und der Support berechnet:
| ItemMenge | Support |
|---|---|
| {Windeln, Milch} | 3/5 |
| {Windeln, Bier} | 3/5 |
| {Windeln, Brot} | 2/5 |
| {Milch, Bier} | 3/5 |
| {Milch, Brot} | 3/5 |
| {Bier, Brot} | 2/5 |
Somit können Kombinationen mit Windeln und Brot sowie mit Bier und Brot wieder von der weiteren Betrachtung ausgeschlossen werden. Es werden die 3-Item-Mengen aus den häufigen 2-Item-Mengen gebildet. Es bleibt nur noch eine mögliche Kombination übrig, die aber nicht häufig ist:
| ItemMenge | Support |
|---|---|
| {Windeln, Milch, Bier} | 2/5 |
Im Ergebnis dieses Schrittes des A Priori Verfahrens liegen also alle häufigen Item-Mengen vor:
| ItemMenge |
|---|
| {Windeln} |
| {Milch} |
| {Bier} |
| {Brot} |
| {Windeln, Milch} |
| {Windeln, Bier} |
| {Milch, Bier} |
7.3.2 Bestimmung der Assoziationsregeln
Im zweiten Schritt werden die Assoziationsregeln für die häufigen Item-Mengen generiert. Dabei wird wieder ein ähnlicher Bottom-Up-Ansatz wie in Schritt 1 gewählt: Man beginnt mit 1-elementigen Konklusionen (rechter Teil der Regel). Für jede Regel wird die Konfidenz bestimmt. Die Regel wird verworfen, wenn . Für jede häufige Item-Menge wird dann sukzessive die Anzahl der Items im Konklusionsteil der Regel erhöht. Dabei wird ausgenutzt dass die Konfidenz mit wachsendem Konklusionsteil nicht mehr zunehmen kann: Sei die Item-Menge . Dann gilt: Wenn also z.B. , dann muss die Regel ${A}{B,C,D$ nicht mehr betrachtet werden.
\begin{algorithm}
\caption{A Priori Schritt 2: Bestimmung der Assoziationsregeln}
\begin{algorithmic}
\INPUT Eine häufige Item-Menge $ L $, $minKonfidenz $
\OUTPUT Assoziationsregeln für die Item-Menge $ L $
\STATE $ i = 1 $
\STATE $ m = $ Anzahl der Items in $ L $
\STATE Mögliche 1-elementige Konklusionen $ Y_1 = $ Item-Menge $ L $
\REPEAT
\FORALL{ Mögliche i-elementigen Konklusionen $y_i \in Y_i$ }
\STATE $konf = $ \CALL{Support}{$L$} $\div$ \CALL{Support}{$y_i$}
\IF{ $konf \geq minKonfidenz$ }
\STATE Prämisse $x = L y_i$
\STATE Speichere Regel $ x \rightarrow y_i $ mit Konfidenz $ = konf$ und Support = \CALL{Support}{$ L $}
\ELSE
\STATE Entferne $ y_i $ aus den i-elementigen Konklusionen $ Y_i $
\ENDIF
\ENDFOR
\STATE Generiere aus den verbliebenen i-elementigen Konklusionen $Y_i$ alle möglichen $ (i+1) $-elementigen Konklusionen $Y_{i+1}$
\STATE $i = i + 1$
\UNTIL{ $i = m$ \OR $Y_{i+1} = \varnothing $ }
\end{algorithmic}
\end{algorithm}
7.3.3 Datenformat
Wenn man Assoziationsanalysen praktisch z.B. mit KNIME durchführt, ist es wichtig dass die Daten im “richtigen” Format vorliegen. Ein Listenformat, entsprechend der Tabelle 7.7 ist für viele Machine Learning Algorithmen ungeeignet. In vielen Datenbanken wie in ERP-Systemen werden die Daten in einem sogenannten Transaktionsformat gespeichert (7.8). Dabei wird pro Position der Transaktion ein Datensatz verwendet. Der Schlüssel ist typischerweise eine Transaktions-ID (zum Beispiel die Auftragsnummer) und eine Positionsnummer. Die Tabelle hat also nur wenige Spalten aber viele Zeilen. Die Ausprägung der Items ist bspw. über eine Artikelnummer codiert.
Für Assoziationsanalysen werden die Daten meist in einer Form benötigt, in der pro Transaktion nur eine Zeile vorliegt. Dies erhält man beispielsweise durch das im Kapitel 2 (Abschnitt 2.4.2) vorgestellte One-Hot Encoding. Die Tabelle 7.9 zeigt die transformierte Struktur der Daten. Man sieht, dass die One-Hot transformierte Tabelle einen deutlich größeren Speicherverbrauch verursacht, weil für jede Ausprägung eines Artikels eine Spalte erzeugt werden muss. Die dadurch erzeugte Matrix kann also sehr groß werden. Außerdem ist diese Matrix im Wesentlichen leer, weil ein typischer Warenkorb nur sehr wenige Artikel enthält.
Welche Struktur schlussendlich zu verwenden ist, legt das genutzte Machine Learning Framework fest.
| Warenkorb | Artikel |
|---|---|
| 1 | {Windel, Bier) |
| 2 | {Windel, Milch, Brot, Käse} |
| 3 | {Bier, Milch, Käse, Brot} |
| 4 | {Windel, Bier, Milch, Brot} |
| 5 | {Windel, Milch, Bier, Butter} |
| Warenkorb | Artikel |
|---|---|
| 1 | Windel |
| 1 | Bier |
| 2 | Windel |
| 2 | Milch |
| 2 | Brot |
| … | … |
| Warenkorb | A.Bier | A.Brot | A.Butter | A.Käse | A.Milch | A.Windel |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 | 1 | 1 | 1 |
| 3 | 1 | 1 | 0 | 1 | 1 | 0 |
| 4 | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | 1 | 0 | 1 | 0 | 1 | 1 |
References
Agrawal, Rakesh, Tomasz Imielinski, and Arun Swami. 1993. “Mining Association Rules Between Sets of Items in Large Databases.” In Proceedings of the 1993 Acm Sigmod International Conference on Management of Data, 207–16. SIGMOD ’93. New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/170035.170072.