Apriori-Algorithmus

Verfahren zur Assoziationsanalyse, einem Bereich des Data-Mining

Der Apriori-Algorithmus ist ein Verfahren zur Assoziationsanalyse, einem Bereich des Data-Mining. Er dient der Auffindung sinnvoller und nützlicher Zusammenhänge in transaktionsbasierten Datenbasen, die in Form sogenannter 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 durch den Algorithmus erzeugten Assoziationsregeln haben die Form . Dabei sind und Mengen von Items und die Regel ist so zu interpretieren, dass Transaktionen, in denen die Itemmenge vorkommt, häufig auch die Itemmenge enthalten.

Voraussetzungen

Bearbeiten

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

  •   ist eine Menge möglicher Items
  •   ist die Datenbasis, bestehend aus Transaktionen  
  • eine Transaktion   fasst eine Menge von Items zusammen

Typischerweise werden sehr viele Transaktionen – oft mehr als 500.000 – gleichzeitig 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   Dimensionen betrachten.

Eine Assoziationsregel besitzt formal ausgedrückt nun die Form

 

wobei gilt

 ,   und  

Bewertung von Regeln

Bearbeiten

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

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

Sei   Itemmenge.

 

Der Support einer Assoziationsregel  , mit   und  , ist definiert als

 

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

Bearbeiten

Sei   eine Assoziationsregel, mit   und  .

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

 

also

 

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   vorkommt, auch   vorkommt. Zur Berechnung der Konfidenz wird die Anzahl aller regelerfüllenden Transaktionen (also der Support) durch die Anzahl der Transaktionen, die   enthalten, geteilt.

Der Algorithmus

Bearbeiten

Der Apriori-Algorithmus erhält als Eingaben

  • Die Datenbasis  
  • Den Minimal-Support  
  • Die minimale Konfidenz  

und gibt eine Menge von Assoziationsregeln aus, die sowohl   als auch   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

Finden häufiger Itemmengen

Bearbeiten

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  -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 >  :  .
  2. Für  .
    1. Berechne Menge von Kandidaten   aus   mittels Apriori-Gen.
    2. Berechne den tatsächlichen Support von allen Mengen aus  .
    3. Nimm die Mengen mit genügend Support   in   auf.
    4. Ist  , brich ab.
  3. Gib   zurück.

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

Apriori-Gen

Bearbeiten

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 bereits gefundener häufiger Mengen eine Menge von Kandidaten zur weiteren Überprüfung generiert.

Die Routine erhält als Eingabe eine Menge häufiger  -Itemmengen ( ) und gibt eine Menge von  -Itemmengen ( ) 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  -Itemmengen durch Verschmelzung von je zwei  -Itemmengen, die je   Items gemein haben und füge sie   hinzu. Dieser Schritt garantiert, dass immer nur jeweils ein Element zur neuen Menge hinzukommt.
  2. Überprüfe für jede Menge   in  , ob alle  -Teilmengen in   enthalten sind. Falls nicht, entferne   aus  .

Beispiel

Bearbeiten

Die Eingabe zu Apriori-Gen sei:

 

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

 

Schritt 2 entfernt die Mengen   und   wieder aus  , da   und   nicht in   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

 

Generierung von Assoziationsregeln

Bearbeiten

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   ausgeführt:

  1. Für jede Itemmenge Z: berechne Assoziationsregeln der Form   mit   und   mit  .
  2. Erzeuge   mit Itemmengen bestehend aus je einer gefundenen Konklusion.
  3.  
    1. Erzeuge   durch Apriori-Gen.
    2. Für jede Konklusion   überprüfe   von  . Falls   nicht erfüllt ist, entferne   aus  .
    3. Wenn  , brich ab.
  4. Gib   zurück.

Die erzeugten Regeln erfüllen alle   und  .

Literatur

Bearbeiten
  • Rakesh Agrawal, Tomasz Imieliński, Arun Swami: Mining Association Rules between Sets of Items in Large Databases. In: Peter Buneman; Sushil Jajodia (Hrsg.): Proceedings of the 1993 ACM SIGMOD international conference on Management of data (= SIGMOD Record. Bd. 22, Nr. 2, Juni 1993). ACM, New York NY 1993, ISBN 0-89791-592-5, S. 207–216, doi:10.1145/170035.170072
  • Rakesh Agrawal, Ramakrishnan Srikant: Fast Algorithms for Mining Association Rules. In: Jorge Bocca, Matthias Jarke, Carlo Zaniolo (Hrsg.): Very large data bases. Proceedings of the 20th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc., Hove u. a. 1994, ISBN 1-55860-153-8, S. 487–499, online (PDF; 282 kB).
  • Jean-Marc Adamo: Data Mining for Association Rules and Sequential Patterns. Sequential and Parallel Algorithms. Springer, New York NY u. a. 2001, ISBN 0-387-95048-6 (englisch).
  • Christoph Beierle, Gabriele Kern-Isberner: Methoden wissensbasierter Systeme: Grundlagen, Algorithmen, Anwendungen., 4. Aufl. Vieweg+Teubner Verlag, 2008, S. 147ff. ISBN 3-8348-0504-1
Bearbeiten