Was ist der Apriori-Algorithmus?

Der Name „Apriori“ wurde 1994 von Rakesh Agrawal und Ramakrishnan Srikant eingeführt und bestätigt das Vorwissen über häufige Elementmengen, die der Algorithmus bei der Berechnung verwendet. Der Algorithmus führt Iterationen über die Daten aus, um k-Itemsets zu identifizieren, d. h. k Elemente, die häufig zusammen auftreten. Anschließend werden die k-Itemsets verwendet, um die k+1-Itemsets zu identifizieren. Der Apriori-Algorithmus beruht auf der Erkenntnis, dass das Hinzufügen von Elementen zu einer häufig gekauften Gruppe diese nur in ihrer Häufigkeit verringern kann, nicht erhöhen. Der Prozess beruht auf der Apriori-Eigenschaft, die besagt, dass, wenn ein Itemset häufig in einem Datensatz vorkommt, auch alle seine Teilmengen häufig vorkommen müssen. Umgekehrt gilt: Wenn ein Itemset als selten identifiziert wird, werden alle seine Obermengen als selten betrachtet.

Der Apriori-Algorithmus ist auf alle Arten von Datensätzen anwendbar, insbesondere auf solche, die von Transaktionsdatenbanken generiert werden. Er wird häufig für die Warenkorbanalyse zur Unterstützung von Empfehlungssystemen verwendet. Nehmen wir zum Beispiel eine E-Commerce-Plattform, die Kleidung und Schuhe verkauft. Ein Käufer sucht nach Schuhen und entscheidet sich, ein Paar schwarze Anzugschuhe in seinen Warenkorb zu legen. Der Käufer bemerkt dann, dass die Benutzeroberfläche weitere Artikel zum Kauf empfiehlt, wie z. B. Socken. Dieses Empfehlungssystem funktioniert unter anderem so, dass es die Kaufmuster der Kunden lernt und Artikel miteinander verknüpft, die in der Vergangenheit wahrscheinlich zusammen gekauft wurden.

Einer der größten Vorteile des Apriori-Algorithmus ist seine Einfachheit und Anpassungsfähigkeit. Allerdings sind Apriori-Algorithmen bei der Verarbeitung großer Datensätze nicht so effizient. Der mehrfache Iterationsprozess der Generierung von Itemset-Kandidaten kann rechen- und speicherintensiv werden. Apriori wird oft mit anderen Techniken kombiniert, um diese Probleme zu mildern.

Die Apriori-Funktion ist in viele gängige Programmiersprachen wie Python, Java und R integriert, sodass sich die Generierung hochwertiger Assoziationsregeln zusammen mit Frequent Itemsets einfach in bestehende Anwendungen oder Systeme integrieren lässt.

Jeder der wichtigsten Schritte im Apriori-Algorithmus besteht darin, Itemsets und alle ihre möglichen Supersets zu identifizieren und nach den häufigsten zu suchen, um die Assoziationsregeln zu erstellen.

Der Algorithmus identifiziert zunächst die eindeutigen Elemente, die manchmal auch als 1-Itemsets bezeichnet werden, im Datensatz zusammen mit ihren Häufigkeiten. Anschließend werden die Elemente, die zusammen mit einer Wahrscheinlichkeit über einem bestimmten Schwellenwert auftreten, zu Kandidaten-Itemsets zusammengefasst und die seltenen Itemsets (Infrequent Itemsets) herausgefiltert, sodass die Rechenkosten in weiteren Schritten reduziert werden können. Dieser Prozess, der als „Frequent Itemset Mining“ bekannt ist, sucht nur nach Itemsets mit aussagekräftigen Häufigkeiten.

Unter Verwendung der Apriori-Eigenschaft kombiniert der Algorithmus häufige Itemsets weiter, um größere Itemsets zu bilden. Die größeren Itemset-Kombinationen mit einer geringeren Wahrscheinlichkeit werden entfernt. Dadurch wird der Suchraum weiter reduziert und die Berechnung effizienter gestaltet.

Der Algorithmus wiederholt die Schritte 1 und 2, bis alle Frequent Itemsets, die die festgelegte Schwellenwahrscheinlichkeit erfüllen, erschöpfend generiert sind. Jede Iteration erzeugt komplexere und umfassendere Zuordnungen in den Itemsets.

Sobald Apriori die Itemsets erstellt hat, kann die Stärke der generierten Zuordnungen und Beziehungen untersucht werden.

Der Apriori-Algorithmus verwendet die Metriken Support, Konfidenz und Lift, um seine Betriebskriterien zu definieren und die Leistungseffizienz zu verbessern.

Support wird definiert als das Verhältnis der Anzahl der Vorkommen eines Elements in den Transaktionen zur Gesamtzahl der Transaktionen. Diese Metrik definiert somit die Wahrscheinlichkeit des Auftretens jedes einzelnen Elements in den Transaktionen. Die gleiche Logik kann auf Itemsets erweitert werden.

$S\left(I_A\right)=\frac{Occ\left(I_A\right)}{TotalTransactions}$

wobei I_A Element A ist, Occ(I_A) die Anzahl des Auftretens von Element A ist und S(I_A) = Support von Element A

In einem Einzelhandelsgeschäft beispielsweise könnte es sein, dass von 2000 Transaktionen an einem Tag 250 den Kauf von Äpfeln beinhalten. Mit der Formel:

$S\left(I_{Apples}\right)=\frac{250}{2000}=0.125$

Dieses Ergebnis impliziert, dass eine 12,5-prozentige Wahrscheinlichkeit besteht, dass an diesem Tag Äpfel gekauft wurden.

Sie können bei der Anwendung des Apriori-Algorithmus einen erforderlichen Mindestunterstützungsschwellenwert angeben. Dies bedeutet, dass jedes Element oder Itemset mit einem Support, der unter dem angegebenen Mindestsupport liegt, als selten betrachtet wird.

Die Konfidenzmetrik gibt die Wahrscheinlichkeit an, dass Elemente oder Itemsets in den Itemsets zusammen auftreten. Wenn es beispielsweise bei einer Transaktion zwei Elemente gibt, wird davon ausgegangen, dass die Existenz eines Elements zum anderen führt. Das erste Element oder Itemset ist das Antezedens und das zweite ist das Sukzedens. Die Konfidenz wird somit definiert als das Verhältnis der Anzahl der Transaktionen, die sowohl das Antezedens als auch das Sukzedens aufweisen, zur Anzahl der Transaktionen, die nur das Antezedens aufweisen. Dieses Szenario wird wie folgt dargestellt:

$C(A,B)=\frac{Occ(A\cap B)}{Occ\left(A\right)}$

wobei A das Antezedens, B das Sukzedens und C(A,B) die Konfidenz ist, dass A zu B führt.

In Erweiterung des vorherigen Beispiels nehmen wir an, dass es 150 Transaktionen gibt, bei denen Äpfel und Bananen zusammen gekauft wurden. Die Konfidenz wird wie folgt berechnet:

$C(Apples,Bananas)=\frac{150}{250}=0.6$

Dieses Ergebnis deutet darauf hin, dass eine 60-prozentige Wahrscheinlichkeit besteht, dass ein Apfelkauf zu einem Bananenkauf führt.Ähnlich verhält es sich bei insgesamt 500 Transaktionen für Bananen. Dann wird die Konfidenz, dass ein Bananenkauf zu einem Apfelkauf führt, wie folgt berechnet:

$C(Bananas,Apples)=\frac{150}{500}=0.3$

Hier besteht nur eine 30-prozentige Wahrscheinlichkeit, dass der Kauf einer Banane zum Kauf eines Apfels führt.

Obwohl das Konfidenzniveau ein guter Maßstab für die Wahrscheinlichkeit ist, ist es keine Garantie für einen eindeutigen Zusammenhang zwischen den Elementen. Der Wert der Konfidenz kann auch aus anderen Gründen hoch sein. Aus diesem Grund wird beim Mining mit Assoziationsregeln eine minimale Konfidenzschwelle angewendet, um schwach wahrscheinliche Assoziationen herauszufiltern.

Der Lift-Faktor ist der Faktor, mit dem die Wahrscheinlichkeit, dass Element A zu Element B führt, höher ist als die Wahrscheinlichkeit von Element A. Diese Metrik quantifiziert die Stärke der Assoziation zwischen A und B. Sie kann dabei helfen, festzustellen, ob es eine echte Beziehung zwischen den Elementen im Itemset gibt oder ob sie zufällig gruppiert wurden. 

$L(A,B)=\frac{C(A,B)}{S\left(A\right)}$ 


Dabei gilt: L_A,B ist der Lift für Element A, der zu Element B führt, C_A,B ist die Konfidenz, dass Element A zu Element B führt, S_A ist der Support für Element A.

Für das obige Beispiel ergibt sich: 

$L(Apples,Bananas)=\frac{0.6}{0.125}=4.8$

Der hohe Lift-Wert zeigt an, dass die Wahrscheinlichkeit, dass Äpfel und Bananen zusammen gekauft werden, 4,8-mal höher ist als die Wahrscheinlichkeit, dass Äpfel allein gekauft werden. Außerdem kann Folgendes beobachtet werden: 

$L(Bananas,Apples)=\frac{0.3}{0.25}=1.2$

Der niedrige Lift-Wert deutet hier darauf hin, dass ein Bananenkauf, der zu einem Apfelkauf führt, nur ein Zufall sein könnte.

In vielen Fällen kann die Verwendung eines Brute-Force-Ansatzes, um die Support- und Konfidenzschwellen für jede Regel zu berechnen und dann Regeln zu streichen, die einen Schwellenwert nicht erfüllen, rechnerisch zu aufwändig sein. Um die Anwendung des Apriori-Algorithmus effizienter zu gestalten, wird er oft mit anderen Techniken zur Gewinnung von Zuordnungsregeln kombiniert. Zwei der gebräuchlichsten sind der FP-Growth-Algorithmus und seine Variante FP-Max zur Reduzierung von Speicher- und Rechenbeschränkungen. Der Apriori-Algorithmus kann auch mit Decision Trees kombiniert werden, wobei der Apriori-Algorithmus das häufige Itemset identifiziert und die Decision-Tree-Technik dabei hilft, die Zuordnungsregeln zu identifizieren.

Eine weitere beliebte Variante des Apriori-Algorithmus ist Dynamic Itemset Counting (DIC), das frühzeitig mit dem Zählen potenzieller Itemsets beginnt, ohne darauf zu warten, dass alle Transaktionen aufgezeichnet sind. DIC unterteilt den Datensatz in kleinere Segmente und verarbeitet jedes Segment separat. Diese Segmentierung ermöglicht ein frühzeitiges Anhalten, wenn der Algorithmus keine häufigen Itemsets identifizieren kann, aber die Partitionierung der Daten trägt auch dazu bei, die Rechenkosten erheblich zu senken.

Apriori-Algorithmen können auch in unüberwachten, lernbasierten Anwendungen der künstlichen Intelligenz wie Clustering-Algorithmen nützlich sein, wenn die Daten dies unterstützen. Damit lassen sich Beziehungen und Zusammenhänge zwischen scheinbar unabhängigen Elementen erkennen und diese in mögliche Cluster gruppieren.

Das Erkennen und Gruppieren von Itemsets hat mehrere Anwendungsmöglichkeiten und der Apriori-Algorithmus wird aufgrund seiner Vielseitigkeit manchmal als das erste genannt, was Data Miner versuchen. Wir betrachten einige gängige Anwendungsfälle in verschiedenen Branchen.

Eine der häufigsten Anwendungen des Apriori-Algorithmus ist die Durchführung von Warenkorbanalysen. Einzelhändler analysieren die Kaufhistorie ihrer Kunden und optimieren die Anordnung des Sortiments in den Geschäften, indem sie häufig gekaufte Artikel in der Nähe voneinander oder im selben Regal platzieren. E-Commerce-Plattformen verwenden Apriori-Algorithmen, um produktbasierte Beziehungen auf der Grundlage von Benutzerpräferenzen und Analysen von Kaufmustern zu untersuchen und so effiziente Kundenempfehlungssysteme zu erstellen. Die gleiche Art von Analyse kann verwendet werden, um den Einkauf von Services zu optimieren, z. B. bei der Auswahl von Schulungen aus einem Katalog oder bei der Empfehlung anderer Deckungstypen bei der Auswahl von Versicherungen.

Der Apriori-Algorithmus kann verwendet werden, um starke Zuordnungsregeln zwischen Symptomen und Krankheiten zu finden, um die Effizienz der Diagnose zu verbessern und gezielte Behandlungspläne zu erstellen. Zum Beispiel, welche Patienten wahrscheinlich an Diabetes erkranken oder welche Rolle die Ernährung oder der Lebensstil bei der Krankheit spielen. Außerdem können damit Faktoren ermittelt werden, die mit unerwünschten Arzneimittelwirkungen in Zusammenhang stehen.

Apriori-Algorithmen sind auch in nicht-transaktionalen Datenbanken anwendbar. Datenanalysten verwenden Apriori häufig für das Web Usage Mining, zur Analyse von Clickstream-Daten und zur Interpretation des Benutzerverhaltens.

Eine weitere häufige Anwendung des Apriori-Algorithmus ist die Identifizierung betrügerischer Muster bei Finanztransaktionen. Wenn ein Finanzinstitut bestimmte Kaufmuster als möglicherweise betrügerisch identifiziert, kann es schnell handeln, um Transaktionen auszusetzen oder einen Kontoinhaber zu kontaktieren.