5.2 Assoziationsregeln · KI ePortfolio

Worum geht’s

Eine Supermarktkasse erzeugt täglich Zehntausende Belege — und jeder Beleg ist eine winzige, ehrliche Aussage darüber, was Menschen gemeinsam kaufen. Die Warenkorbanalyse versucht, aus dieser Masse von Belegen Regeln der Form „wer A kauft, kauft auch B” zu destillieren. Das ist ungerichtetes Lernen im reinsten Sinne: Es gibt kein Label, keine Zielgröße, die man vorhersagen will — nur die rohen Mengen, und die Frage, welche Artikel verdächtig oft zusammen auftauchen.

Mich reizt an diesem Thema, wie wenig Maschinerie nötig ist, um etwas Nichttriviales zu finden, und wie schnell die Sache trotzdem an einer kombinatorischen Wand zerschellt: Bei $m$ Artikeln gibt es $2^m$ mögliche Itemsets, und naiv müsste man sie alle zählen. Der Foliensatz rechnet das plastisch vor — schon $4$ Attribute erlauben $50$ verschiedene Assoziationsregeln, bei $100$ Attributen sind es astronomische $5{,}15 \cdot 10^{47}$ . Das berühmte Apriori-Prinzip ist genau die eine clevere Beobachtung, die diesen exponentiellen Raum auf das Handhabbare zusammenstreicht — ein schönes Beispiel dafür, wie eine einzige Monotonie-Eigenschaft einen ganzen Algorithmus trägt. Und das Lehrbuchresultat „Windeln und Bier” zeigt nebenbei, dass solche Regeln nützlich und leicht fehlinterpretierbar sind.

Kernkonzepte

Transaktionen, Items, Itemsets

Gegeben ist eine Menge von Transaktionen (Warenkörbe), jede eine Teilmenge des Artikelsortiments $I$ . Eine beliebige Teilmenge $X \subseteq I$ heißt Itemset. Die zentrale Kennzahl ist der Support — der Anteil der Transaktionen, die $X$ ganz enthalten:

\operatorname{supp}(X) = \frac{|\{t : X \subseteq t\}|}{N},

bei $N$ Transaktionen. Ein Itemset heißt häufig, wenn sein Support eine gewählte Schwelle $\sigma$ überschreitet.

DefinitionAssoziationsregel und ihre Maße

Eine Assoziationsregel $A \Rightarrow B$ (mit disjunkten Itemsets $A, B$ ) wird durch drei Maße bewertet:

\operatorname{supp}(A \Rightarrow B) = \operatorname{supp}(A \cup B), \qquad \operatorname{conf}(A \Rightarrow B) = \frac{\operatorname{supp}(A \cup B)}{\operatorname{supp}(A)}.

\operatorname{lift}(A \Rightarrow B) = \frac{\operatorname{conf}(A \Rightarrow B)}{\operatorname{supp}(B)} = \frac{\operatorname{supp}(A \cup B)}{\operatorname{supp}(A)\,\operatorname{supp}(B)}.

Support misst, wie oft die Regel überhaupt zutrifft; Konfidenz die bedingte Wahrscheinlichkeit $P(B \mid A)$ ; Lift vergleicht diese mit dem Zufall: $\operatorname{lift} > 1$ bedeutet positive Kopplung, $= 1$ Unabhängigkeit, $< 1$ gegenseitiges Verdrängen. Der Foliensatz schreibt den Nenner $\operatorname{supp}(B)$ als Expected Confidence von $B$ und nennt als Synonyme noch Coverage für Support und Accuracy für Konfidenz.

Die Konfidenz allein täuscht leicht: Ist $B$ ohnehin in fast jedem Korb (z.B. Brot), wird $\operatorname{conf}(A \Rightarrow B)$ hoch, ohne dass $A$ irgendetwas über $B$ aussagt. Genau das korrigiert der Lift — er normiert die Konfidenz auf die Grundhäufigkeit von $B$ und ist daher das ehrlichere Maß für eine echte Kopplung.

Das Apriori-Prinzip

Der Engpass ist das Finden der häufigen Itemsets, nicht das anschließende Bilden der Regeln. Hier greift die entscheidende Beobachtung:

Daraus baut Apriori (Agrawal & Srikant, 1994) ein ebenenweises Verfahren: Man bestimmt die häufigen 1-Itemsets, verschmilzt sie zu 2-Kandidaten, prüft deren Support, und so fort. Der Trick ist das Pruning: Ein $k$ -Kandidat wird gar nicht erst gezählt, wenn auch nur eine seiner $(k-1)$ -Teilmengen unter der Schwelle lag — denn dann kann er nach dem Theorem unmöglich häufig sein. Das spart den Großteil der $2^m$ möglichen Itemsets.

Aus jedem häufigen Itemset $Z$ werden anschließend Regeln $A \Rightarrow Z \setminus A$ für alle nichtleeren echten Teilmengen $A$ gebildet und nach Konfidenz (und sinnvollerweise Lift) gefiltert. Der Foliensatz beschränkt die Suche dazu auf Regeln mit $\operatorname{supp} > \texttt{min\_support}$ und $\operatorname{conf} > \texttt{min\_confidence}$ (Beispielbereiche etwa $[0{,}05,\,1{,}0]$ bzw. $[0{,}9,\,1{,}0]$ ) und hält fest: Die Interpretation der gefundenen Regeln ist die eigentliche Hauptarbeit. Apriori durchläuft die Datenbank pro Ebene einmal; bei sehr vielen häufigen Itemsets wird das teuer. FP-Growth (Han et al., 2000) umgeht das, indem es die Transaktionen in einen kompakten Präfixbaum (FP-Tree) presst und häufige Muster ohne explizite Kandidatengenerierung direkt aus diesem Baum herauszieht — meist deutlich schneller, aber konzeptuell aufwendiger.

Praxis

Um das Apriori-Prinzip nicht nur zu glauben, habe ich häufige Itemsets und Regelgenerierung in reinem NumPy/pandas nachgebaut (bewusst ohne mlxtend o.ä.) und auf einen fest kodierten Warenkorb mit 15 Transaktionen losgelassen — das „Windeln/Bier”-Beispiel ist absichtlich eingebaut. Das Pruning aus dem Theorem ist genau die eine Zeile, die einen $k$ -Kandidaten nur durchlässt, wenn alle seine $(k-1)$ -Teilmengen schon häufig sind:

def apriori(M, min_support):
    haeufig = {}
    ebene = [frozenset([a]) for a in M.columns
             if _support(frozenset([a]), M) >= min_support]
    for iset in ebene:
        haeufig[iset] = _support(iset, M)
    while ebene:
        kandidaten = set()
        for a, b in combinations(ebene, 2):
            verein = a | b
            if len(verein) != len(next(iter(ebene))) + 1:
                continue
            # Downward Closure: alle (k-1)-Teilmengen müssen häufig sein
            if all(frozenset(s) in haeufig
                   for s in combinations(verein, len(verein) - 1)):
                kandidaten.add(verein)
        ebene = [c for c in kandidaten if _support(c, M) >= min_support]
        for iset in ebene:
            haeufig[iset] = _support(iset, M)
    return haeufig

Das vollständige Skript (Datensatz, Regelmaße, Plots) liegt in python/src/eport_figures/praxis/p_5_2_assoziation.py. Seine Ausgabe:

Warenkorb: 15 Transaktionen, 7 Artikel (Bier, Brot, Butter, Cola, Eier, Milch, Windeln).
Schwellen: min_support = 0.20 (>= 3 Körbe), min_konfidenz = 0.60.

Häufige Itemsets je Größe (Apriori, mit Downward-Closure-Pruning):
  k = 1: 7 Itemsets
  k = 2: 10 Itemsets
  k = 3: 4 Itemsets
  gesamt: 21 häufige Itemsets.

Regeln mit Konfidenz >= 0.60: 18 Stück.
Stärkste Regeln nach Lift:

                    Regel Support Konfidenz Lift
       {Cola} → {Windeln}    0.20      1.00 1.88
       {Windeln} → {Bier}    0.47      0.88 1.64
       {Bier} → {Windeln}    0.47      0.88 1.64
          {Eier} → {Brot}    0.20      1.00 1.50
{Milch, Windeln} → {Bier}    0.27      0.80 1.50
{Bier, Milch} → {Windeln}    0.27      0.80 1.50
 {Brot, Windeln} → {Bier}    0.20      0.75 1.41
 {Bier, Brot} → {Windeln}    0.20      0.75 1.41

Lehrbuchregel: {Windeln} → {Bier}  —  Support 0.47, Konfidenz 0.88, Lift 1.64.
  Lift > 1 heißt: Windeln und Bier treten gemeinsam häufiger auf, als es bei Unabhängigkeit zu erwarten wäre.

Das Ergebnis liest sich lehrbuchhaft: $\{\text{Windeln}\} \Rightarrow \{\text{Bier}\}$ hat einen Lift von $1{,}64$ — Windeln und Bier landen zusammen deutlich häufiger im Korb, als es bei Unabhängigkeit zu erwarten wäre. Bemerkenswert ist die noch höhere Spitze $\{\text{Cola}\} \Rightarrow \{\text{Windeln}\}$ mit Lift $1{,}88$ : Sie zeigt die Tücke kleiner Stichproben, denn ihr Support ist mit $0{,}20$ gerade an der Schwelle — drei Körbe genügen, um einen hohen Lift vorzutäuschen. Das unterstreicht, warum man Regeln nie nach einem Maß allein bewertet.

Streudiagramm der Regeln über Support und Konfidenz, eingefärbt nach Lift — Jede Regel als Punkt im Support-Konfidenz-Raum; Farbe und Größe kodieren den Lift. Interessant sind die Punkte oben (hohe Konfidenz) *mit* kräftiger Farbe (hoher Lift) — hohe Konfidenz bei blassem Punkt verrät eine Regel, deren Konklusion ohnehin häufig ist.

Balkendiagramm der sechs liftstärksten Regeln — Die sechs liftstärksten Regeln. Die gestrichelte Linie bei Lift $= 1$ markiert Unabhängigkeit; alle gezeigten Regeln liegen klar darüber, koppeln also positiv.

Querbezüge

5.1 (Clustering): Beides ist unüberwachtes Data Mining — kein Label, nur Struktur. Wo Clustering Zeilen (Objekte) nach Ähnlichkeit gruppiert, sucht die Assoziationsanalyse Muster zwischen Spalten (Merkmalen/Artikeln). Sie sind gewissermaßen die zwei orthogonalen Blickrichtungen auf dieselbe Datenmatrix.
3.2 (Klassifikation): Eine Assoziationsregel $A \Rightarrow B$ sieht aus wie eine Entscheidungsregel aus einem Baum oder Regelsatz — nur wird sie hier nicht auf eine feste Zielklasse hin gelernt, sondern jedes Item kann sowohl Prämisse als auch Konklusion sein. Konfidenz entspricht der Reinheit eines Regel-Zweigs.
Datenbanken: Die Warenkorbanalyse stammt direkt aus dem Transaktions- und Data-Warehouse-Umfeld; Support-Zählung ist letztlich ein GROUP BY … HAVING COUNT(*) >= σ über Itemset-Vorkommen.
Empfehlungssysteme: „Kunden, die X kauften, kauften auch Y” ist die direkte kommerzielle Anwendung — Assoziationsregeln sind ein einfacher, erklärbarer Vorläufer der späteren kollaborativen Filter.
Andere Module: Das Apriori-Prunen ist algorithmisch eine Branch-and-Bound- Idee (Algorithmen & Datenstrukturen): Eine Monotonie schneidet ganze Teilbäume des Suchraums ab. Support, Konfidenz und Lift sind unmittelbar wahrscheinlichkeitstheoretisch ( $P(B \mid A)$ bzw. $P(A \cap B)/(P(A)P(B))$ , Stochastik).

Quellen

Foliensatz _420_DM_Assoc.pdf — Grundlage für die Notation (Support, Konfidenz, Expected Confidence, Lift), das Pampers/Bier-Beispiel und die Nennung von Apriori als Standardalgorithmus samt min_support/min_confidence- Schwellen. Die Folien führen das Verfahren am Warenkorb ein; ich habe daraus die Definitionen übernommen und das Beispiel mit eigenem Datensatz nachgerechnet, statt es abzuschreiben.
Den genauen Apriori-Mechanismus (Antimonotonie / Downward Closure, Pruning) und FP-Growth nennen die Folien nicht aus; dafür habe ich Agrawal & Srikant, Fast Algorithms for Mining Association Rules (VLDB 1994) sowie Han, Pei & Yin, Mining Frequent Patterns without Candidate Generation (SIGMOD 2000) herangezogen.
Russell & Norvig, AIMA — ordnet die Assoziationsanalyse in das unüberwachte Lernen ein; nutzte ich, um den Bezug zu Clustering sauber abzugrenzen.
SPMF und Weka (in den Folien genannt) habe ich als etablierte Werkzeuge zur Kenntnis genommen; meine eigene Implementierung diente bewusst dem Verständnis des Mechanismus, nicht der Skalierung.

Worum geht’s#

Kernkonzepte#

Transaktionen, Items, Itemsets#

Das Apriori-Prinzip#

Praxis#

Querbezüge#

Quellen#