Assoziationsanalyse

Einfache Sprache

Bei der Assoziationsanalyse wird nach in einem Datensatz (Datenbasis) nach Regel gesucht, die Korrelationen zwischen gemeinsam auftretenden Dingen (Items) beschreiben. Ein Regel impliziert also eine Wenn-Dann-Beziehung zwischen dem Auftreten zweier Items.

Def. Assoziationsanalyse

Ziel der Assoziationsanalyse ist es, alle Assoziationsregeln zu finden, die eine bestimme mindest Support und Konfidenz erfüllen. Dafür wird zuerst beim Frequent Itemset Mining (FIM) der Support aller Teilmengen berechnet. Das Ergebnis wird dann bei dem Association Rule Mining (ARM) verwendet um alle Assoziationsregeln zu finden, die bestimmte Kriterien erfüllen.

Frequent Itemset Mining

Gegeben ist eine Menge $\mathcal I$ möglicher Items und eine Datenbasis $\mathcal D = \{t_1,t_2,\ldots,t_n\}$, wobei $t_x\subset\mathcal D$ eine Transaktion ist. $\mathcal D$ ist also eine Menge aus Teilmengen aus $\mathcal I$. Ein Itemset ist eine Teilmenge von $\mathcal I$. Eine $k$-Itemset ist eine Itemset der Größe $k$, also mit $k$ Items.

Def. Support

Sei $X\subset \mathcal I$. Der Support von $X$ ist definiert als

$$\textrm{support}(X)=\frac{|\left\{t\in\mathcal D\mid X\subseteq t\right\}|}{|\mathcal D|}\;.$$

Def. Frequent Itemset.

Sei ein Minimal-Support $s\in\mathcal R_+$. $X\subset\mathcal I$ ist frequent g.d.w.

$$\textrm{support}(X)\geq s\;.$$

Satz. Apriori Eigenschaft

Der Satz zur Apriori Eigenschaft besagt dass, wenn $X$ ein frequentes Itemset ist, dann sind auch alle Teilmengen $Y\subseteq X$ frequent.

Aus der Apriori Eigenschaft folgt durch Kontraposition: Ist $X$ nicht frequent, dann sind auch alle Obermengen (Obermenge) von $X$ nicht frequent.

Def. Frequent Itemset Mining (FIM) Problem

Gegeben eine mögliche Itemmenge $\mathcal I$, eine Datenbasis $\mathcal D$ und ein Minimal-Support $s$. Gesucht ist die Menge aller Itemsets, deren Support größer als $s$ ist. Also die Menge

$$\{X\subseteq \mathcal I\mid \textrm{support}(X)\geq s\}\;.$$

Folgende Algorithmen lösen das FIM Problem:

• FPGrowth-Algorithmus
• Apriori-Algorithmus

Association Rule Mining

Gegeben sind zwei Itemsets $X,Y\subseteq \mathcal I$ mit $X\cap Y=\emptyset$. Eine Assoziationsregel hat die Form $X\to Y$. In diesem Kontext wird $X$ Voraussetzung und $Y$ Konsequenz genannt. Der Support einer Regel, ist als der Support der Vereinigung der Voraussetzung und der Konsequenz definiert. Also

Die Konfidenz einer Regel ist als Verhältnis zwischen der Anzahl an Transaktionen aus der Datenbasis $\mathcal D$ die $X\cup Y$ enthalten und der Anzahl aller Transaktionen die $X$ enthalten. Also

Def. Association Rule Mining (ARM) Problem

Gegeben eine mögliche Itemmenge $\mathcal I$, eine Datenbasis $\mathcal D$ und ein Minimal-Support $s$ und eine minimale Konfidenz $c$. Gesucht ist die Menge alle starken Assoziationsregel $X\to Y$ deren Support größer ist als $s$ und deren Konfidenz größer ist als $c$. Also die Menge definiert durch

$$\{X\to Y\mid X,Y\subseteq\mathcal I \land X\cap Y \not=\emptyset \land \textrm{support}(X\to Y)\geq s \land \textrm{confidence}(X\to Y)\geq c\}\;.$$

Zur Lösung des ARM Problems wird zunächst der Support aller Itemsets berechnet die Minimal-Support erfüllen berechnet. Siehe mehr bei Frequent Itemset Mining.