Apriori-Algorithmus

Der Apriori-Algorithmus ist ein Verfahren zur Assoziationsanalyse, einem Bereich des Data-Mining. Er dient der Auffindung von sinnvollen und nützlichen Zusammenhängen in transaktionsbasierten Datenbasen, die in Form von sogenannten Assoziationsregeln dargestellt werden. Eine häufige Anwendung des Apriori-Algorithmus ist die Warenkorbanalyse. Items sind hierbei angebotene Produkte und ein Einkauf stellt eine Transaktion dar, welche die gekauften Items enthält. Der Algorithmus bestimmt nun Korrelationen der Form:

Wenn Shampoo und Rasierwasser gekauft wurden, wurde in 90% der Fälle auch Rasierschaum gekauft.

Eine passende Datenbasis besteht aus einer Tabelle von Transaktionen (Zeilen) in denen beliebige binäre Items (Spalten) zusammengefasst werden. Der Apriori-Algorithmus findet Zusammenhänge zwischen Mengen von Items, die in einem großen Teil der Transaktionen vorkommen. Die ausgegebenen Assoziationsregeln haben die Form A \rightarrow B, wobei A und B Mengen von Items sind. Eine solche Regel beschreibt, dass in einem großen Teil der Transaktionen die Itemmenge A vorkommt und in diesen Transaktion die Itemmenge B ebenfalls häufig ist.

Inhaltsverzeichnis

Voraussetzungen

Der Apriori-Algorithmus wird bei Datenbasen einer bestimmten Form angewendet. Die Form der Datenbasis muss wie folgt vorliegen:

  • \mathcal I ist eine Menge von möglichen Items
  • \mathcal D = \{ t_1, t_2, ..., t_n \} ist die Datenbasis, bestehend aus Transaktionen tx
  • eine Transaktion t_x \subseteq \mathcal I fasst eine Menge von Items zusammen

Typischerweise wird eine Menge von mehr als 500.000 Transaktionen auf einer sehr großen Item-Basis analysiert. Die Darstellung der Datenbasis erfolgt in einer de-normalisierten Datenbanktabelle, welche für jedes mögliche Item eine Spalte besitzt. Die enthaltenen Zeilen stellen jeweils eine Transaktion dar, wobei in der Transaktion enthaltene Items mit einer 1, nicht enthaltene mit einer 0 gekennzeichnet werden. Eine Transaktion lässt sich somit auch als Vektor mit \mid \mathcal I \mid Dimensionen betrachten.

Eine Assoziationsregel ist von der Form

X \rightarrow \!\, Y

wobei gilt

X \subseteq \mathcal I, Y \subseteq \mathcal I und X \cap Y = \emptyset

Bewertung von Regeln

Assoziationsregeln werden mit zwei probabilistischen Messwerten bewertet: Support und Konfidenz. Der Apriori-Algorithmus erwartet als Eingabe unter anderem die Werte minsupp und minconf, welche den minimalen Support und die minimale Konfidenz einer Regel darstellen, damit sie berücksichtigt werden.

Support

Der Support einer Itemmenge ist die Wahrscheinlichkeit, dass diese Itemmenge in einer Transaktion vorkommt.

Sei X = A1,A2,...,An Itemmenge.

\begin{align}
\operatorname{Support}(X) & = \!\, P( A_1, A_2, ..., A_n )\\
           & = \frac{\mid \{ t \in \mathcal D \mid X \subseteq t \} \mid}{\mid D \mid}
\end{align}

Der Support einer Assoziationsregel X \rightarrow Y, mit X = {A1,A2,...,An} und Y = {B1,B2,...,Bm}, ist definiert als

\begin{align}
\operatorname{Support}(X \rightarrow Y) & = \!\, \operatorname{Support}(X \cup Y)\\
                         & = \!\, P( A_1, A_2, ..., A_n, B_1, B_2, ..., B_m ) \\
                         & = \frac{\mid \{ t \in \mathcal D \mid X \cup Y \subseteq t \} \mid}{\mid D \mid}
\end{align}

Der Support einer Regel gibt also die relative Häufigkeit an, mit der die Regel in der Datenbasis vorkommt. Meist ist ein hoher Support wünschenswert, um Aussagen über Mehrheiten zu finden.

Konfidenz

Sei X \rightarrow \!\, Y eine Assoziationsregel, mit X = {A1,A2,...,An} und Y = {B1,B2,...,Bm}.

Die Konfidenz einer Regel entspricht der Wahrscheinlichkeit der Konklusion unter Bedingung der Prämisse:

\operatorname{Conf}(X \rightarrow \!\, Y) = P(B_1, B_2, ..., B_m \mid A_1, A_2, ..., A_n )

also

\begin{align}
\operatorname{Conf}(X \rightarrow Y) & = \frac{\operatorname{Support}(X \cup Y)}{\operatorname{Support}(X)}\\
                      & = \frac{\mid \{ t \in \mathcal D \mid X \cup Y \subseteq t \} \mid}{\mid \{ t \in \mathcal D \mid X \subseteq t \} \mid}
\end{align}

Die Konfidenz misst also die relative Häufigkeit des Vorkommens der Konklusion unter Bedingung der Prämisse. Auch für die Konfidenz ist ein hoher Wert wünschenswert. Oder einfacher ausgedrückt: Die Konfidenz misst für welchen Anteil der Transaktionen, in denen X vorkommt, auch Y vorkommt. Zur Berechnung der Konfidenz wird die Anzahl aller regelerfüllenden Transaktionen (also der Support) durch die Anzahl der Transaktionen, die X enthalten, geteilt.

Der Algorithmus

Der Apriori-Algorithmus erhält als Eingaben

  • Die Datenbasis \mathcal D
  • Den Minimal-Support minsupp
  • Die minimale Konfidenz minconf

und gibt eine Menge von Assoziationsregeln aus, die sowohl minsupp als auch minconf erfüllen.

Der Algorithmus arbeitet in zwei Schritten welche beide einen gemeinsamen Schritt Apriori-Gen verwenden:

  1. Findung häufiger Mengen
  2. Erzeugung von Assoziationsregeln

Findung häufiger Itemmengen

Die Suche nach häufigen Itemmengen startet mit 1-elementigen Mengen und wird iterativ mit n-elementigen Mengen fortgeführt, bis keine Itemmengen mit genügendem Support mehr gefunden werden. Dabei wird in jeder Iteration eine Menge von Kandidatenmengen mittels Apriori-Gen erzeugt und jede Menge auf die minconf-Eigenschaft hin überprüft. Können keine neuen Mengen mehr gefunden werden, stoppt der Algorithmus und gibt die gefundenen Mengen aus.

  1. Berechne alle 1-elementigen Itemmengen mit Support > minsupp: L1.
  2. Für k - 1 \rightarrow k.
    1. Berechne Menge von Kandidaten Ck aus Lk − 1 mittels Apriori-Gen.
    2. Berechne den tatsächlichen Support von allen Mengen aus Ck.
    3. Nimm die Mengen mit genügend Support in Lk auf.
    4. Ist L_k = \emptyset, brich ab.
  3. Gib \bigcup{}{L_k} zurück.

Die zurückgegebene Menge enthält alle häufigen Itemmengen.

Apriori-Gen

Die Sub-Routine Apriori-Gen wird sowohl bei der Berechnung häufiger Mengen, als auch bei der Generierung von Assoziationsregeln verwendet. Anstatt für alle möglichen Itemmengen den Support direkt zu berechnen, wird durch Apriori-Gen auf Basis von bereits gefundenen häufigen Mengen eine Menge von Kandidaten zur weiteren Überprüfung generiert.

Die Routine erhält als Eingabe eine Menge von häufigen k − 1-Itemmengen (Lk − 1) und gibt eine Menge von k-Itemmengen (Ck) als mögliche Kandidaten zurück. Sie basiert auf dem Prinzip, dass alle Teilmengen einer häufigen Itemmenge häufig sind, alle Obermengen einer nicht-häufigen Itemmenge aber auch nicht-häufig. Unnötige Support-Berechnungen werden so vermieden.

  1. Generiere k-Itemmengen durch Verschmelzung von je zwei k − 1-Itemmengen, die je k − 2 Items gemein haben und füge sie Ck hinzu.
  2. Überprüfe für jede Menge X in Ck, ob alle k − 1-Teilmengen in Lk − 1 enthalten sind. Falls nicht, entferne X aus Ck.

Beispiel

Die Eingabe zu Apriori-Gen sei:

L3 = {{a,b,c},{a,b,d},{a,b,e},{a,c,d},{b,c,d},{a,c,e}}

Schritt 1 der Apriori-Gen-Routine berechnet nun die folgende Kandidaten Menge:

C4 = {{a,b,c,d},{a,b,c,e},{a,b,d,e}}

Schritt 2 entfernt die Mengen {a,b,c,e} und {a,b,d,e} wieder aus C4, da {b,c,e} und {b,d,e} nicht in L3 enthalten sind. Beide Mengen sind also nicht häufig und Ihre Obermengen müssen nicht berücksichtigt werden.

Das Ergebnis von Apriori-Gen ist also

C4 = {{a,b,c,d}}

Generierung von Assoziationsregeln

Nur Itemmengen die bereits in sich häufig sind, müssen für diesen Schritt des Algorithmus berücksichtigt werden. Solche Itemmengen wurden von Schritt 1 des Apriori-Algorithmus berechnet. Die von Schritt 1 verwendete Routine Apriori-Gen wird bei der Generierung von Assoziationsregeln erneut verwendet.

Für jede gefundene häufige Itemmenge wird versucht, Assoziationsregeln zu erzeugen. Dabei wird mit möglichst kurzen (1-elementigen) Konklusionen begonnen, welche iterativ vergrößert werden. Der folgende Pseudocode wird für jede gefundene Itemmenge Z ausgeführt:

  1. Für jede Itemmenge Z: berechne Assoziationsregeln der Form X \rightarrow Y mit \mid Y \mid = 1 und X = ZY mit \operatorname{Conf}(X \rightarrow Y) > minconf.
  2. Erzeuge H1 mit Itemmengen bestehend aus je einer gefundenen Konklusion.
  3. H_{k - 1} \rightarrow H_k
    1. Erzeuge Hk durch Apriori-Gen.
    2. Für jede Konklusion h_k \in H_k überprüfe minconf von (Z - h_k) \rightarrow h_k. Falls minconf nicht erfüllt ist, entferne hk aus Hk.
    3. Wenn H_k = \emptyset, brich ab.
  4. Gib \bigcup H_k zurück.

Die erzeugten Regeln erfüllen alle minsupp und minconf.

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Apriori — Die lateinische Redewendung a priori (lat. „vom Früheren her“), welche von Aristoteles noch als vorausgehende Seinsursache verstanden wurde, bezeichnet ab Descartes das, was als Bedingung und Grundlage des Wissens von der Erfahrung als solcher… …   Deutsch Wikipedia

  • Assoziationsanalyse — Die Assoziationsanalyse bezeichnet die Suche nach starken Regeln. Diese daraus folgenden Assoziationsregeln beschreiben Korrelationen zwischen gemeinsam auftretenden Dingen. Der Zweck einer Assoziationsanalyse besteht also darin, Items (Elemente… …   Deutsch Wikipedia

  • Environment for DeveLoping KDD-Applications Supported by Index-Structures — ELKI 0.4 visualisiert OPTICS Ergebnis Basisdaten Maintainer …   Deutsch Wikipedia

  • A priori — Die lateinische Redewendung a priori (lat. „vom Früheren her“), welche von Aristoteles noch als vorausgehende Seinsursache verstanden wurde, bezeichnet ab Descartes das, was als Bedingung und Grundlage des Wissens von der Erfahrung als solcher… …   Deutsch Wikipedia

  • Apriorisches Wissen — Die lateinische Redewendung a priori (lat. „vom Früheren her“), welche von Aristoteles noch als vorausgehende Seinsursache verstanden wurde, bezeichnet ab Descartes das, was als Bedingung und Grundlage des Wissens von der Erfahrung als solcher… …   Deutsch Wikipedia

  • Apriorität — Die lateinische Redewendung a priori (lat. „vom Früheren her“), welche von Aristoteles noch als vorausgehende Seinsursache verstanden wurde, bezeichnet ab Descartes das, was als Bedingung und Grundlage des Wissens von der Erfahrung als solcher… …   Deutsch Wikipedia

  • Naturwissenschaft — Deckenfresko von Bartolomeo Altomonte im Stift Admont. Dargestellt sind Medizin, Arzneikunde, Anatomie, Architektur, Mathematik, Geographie, Astronomie, Geologie und Physik. Als Naturwissenschaften werden jene Wissenschaften bezeichnet, die sich… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”