Apriori-Algorithmus im Data Mining: Implementierung mit Beispielen

apriori algorithm data mining

Ausführliches Tutorial zum Apriori-Algorithmus zum Herausfinden häufiger Itemsets im Data Mining. Dieses Tutorial erklärt die Schritte in Apriori und wie es funktioniert:

In diesem Data Mining-Lernserie Wir haben uns das angeschaut Entscheidungsbaum-Algorithmus in unserem vorherigen Tutorial.

Für Data Mining gibt es verschiedene Methoden wie Zuordnung, Korrelation, Klassifizierung und Clustering.

Was ist die beste App zum Herunterladen von YouTube-Videos

Dieses Tutorial konzentriert sich hauptsächlich auf das Mining mithilfe von Zuordnungsregeln. Anhand von Zuordnungsregeln identifizieren wir die Gruppe von Elementen oder Attributen, die zusammen in einer Tabelle vorkommen.

Was du lernen wirst:

• Was ist ein Itemset?
  • Was ist ein häufiges Itemset?
  • Frequent Pattern Mining (FPM)
  • Assoziationsregeln
• Warum häufiges Itemset Mining?
  • Apriori-Algorithmus - Häufige Musteralgorithmen
    • Schritte in Apriori
    • Vorteile
    • Nachteile
• Methoden zur Verbesserung der Apriori-Effizienz
• Anwendungen des Apriori-Algorithmus
• Fazit
  • Literatur-Empfehlungen

Was ist ein Itemset?

Eine Reihe von Elementen zusammen wird als Elementmenge bezeichnet. Wenn ein Itemset k-Items enthält, wird es als k-Itemset bezeichnet. Ein Itemset besteht aus zwei oder mehr Items. Eine häufig vorkommende Elementmenge wird als häufige Elementmenge bezeichnet. Daher ist häufiges Item-Set-Mining eine Data-Mining-Technik, um die Elemente zu identifizieren, die häufig zusammen auftreten.

Zum Beispiel , Brot und Butter, Laptop- und Antivirensoftware usw.

Was ist ein häufiges Itemset?

Eine Reihe von Elementen wird als häufig bezeichnet, wenn sie einen Mindestschwellenwert für Unterstützung und Vertrauen erfüllt. Der Support zeigt Transaktionen mit Artikeln an, die zusammen in einer einzigen Transaktion gekauft wurden. Vertrauen zeigt Transaktionen an, bei denen die Artikel nacheinander gekauft werden.

Bei der häufigen Item-Set-Mining-Methode werden nur die Transaktionen berücksichtigt, die die Mindestanforderungen für die Unterstützung und das Vertrauen erfüllen. Die Erkenntnisse aus diesen Mining-Algorithmen bieten viele Vorteile, Kostensenkungen und einen verbesserten Wettbewerbsvorteil.

Es wird eine Kompromisszeit benötigt, um Daten abzubauen, und das Datenvolumen für häufiges Mining. Der häufige Mining-Algorithmus ist ein effizienter Algorithmus, um die verborgenen Muster von Objektgruppen innerhalb kurzer Zeit und mit geringerem Speicherverbrauch abzubauen.

Frequent Pattern Mining (FPM)

Der häufige Pattern-Mining-Algorithmus ist eine der wichtigsten Techniken des Data Mining, um Beziehungen zwischen verschiedenen Elementen in einem Dataset zu ermitteln. Diese Beziehungen werden in Form von Assoziationsregeln dargestellt. Es hilft, die Unregelmäßigkeiten in Daten zu finden.

FPM hat viele Anwendungen im Bereich Datenanalyse, Softwarefehler, Cross-Marketing, Verkaufskampagnenanalyse, Warenkorbanalyse usw.

Häufige Objektgruppen, die über Apriori entdeckt wurden, haben viele Anwendungen für Data Mining-Aufgaben. Aufgaben wie das Auffinden interessanter Muster in der Datenbank, das Herausfinden der Reihenfolge und das Mining von Assoziationsregeln sind die wichtigsten.

Zu Supermarkttransaktionsdaten gelten Assoziationsregeln, dh um das Kundenverhalten in Bezug auf die gekauften Produkte zu untersuchen. Zuordnungsregeln beschreiben, wie oft die Artikel zusammen gekauft werden.

Assoziationsregeln

Association Rule Mining ist definiert als:

'Sei I = {...} eine Menge von 'n' binären Attributen, die als Elemente bezeichnet werden. Sei D = {….} Eine Transaktion namens Datenbank. Jede Transaktion in D hat eine eindeutige Transaktions-ID und enthält eine Teilmenge der Elemente in I. Eine Regel wird als Implikation der Form X-> Y definiert, wobei X, Y? I und X? Y =?. Die Menge der Elemente X und Y wird als Antezedenz bzw. Konsequenz der Regel bezeichnet. “

Das Erlernen von Assoziationsregeln wird verwendet, um Beziehungen zwischen Attributen in großen Datenbanken zu finden. Eine Zuordnungsregel, A => B, hat die Form 'Für eine Reihe von Transaktionen bestimmt ein Wert von Artikelgruppe A die Werte von Artikelgruppe B unter der Bedingung, dass minimale Unterstützung und Vertrauen erfüllt werden'.

Unterstützung und Vertrauen können durch das folgende Beispiel dargestellt werden:

Die obige Anweisung ist ein Beispiel für eine Zuordnungsregel. Dies bedeutet, dass es eine 2% -Transaktion gibt, bei der Brot und Butter zusammen gekauft wurden, und dass 60% der Kunden Brot und Butter gekauft haben.

Unterstützung und Vertrauen für Punkt A und B werden durch folgende Formeln dargestellt:

Das Assoziationsregel-Mining besteht aus zwei Schritten:

1. Hier finden Sie alle häufigen Artikelgruppen.
2. Generieren Sie Zuordnungsregeln aus den oben genannten häufigen Elementmengen.

Warum häufiges Itemset Mining?

Häufiges Itemset- oder Pattern-Mining wird aufgrund seiner breiten Anwendung in Mining-Assoziationsregeln, Korrelationen und Einschränkungen für Diagrammmuster, die auf häufigen Mustern, sequentiellen Mustern und vielen anderen Data-Mining-Aufgaben basieren, häufig verwendet.

Apriori-Algorithmus - Häufige Musteralgorithmen

Der Apriori-Algorithmus war der erste Algorithmus, der für häufiges Item-Set-Mining vorgeschlagen wurde. Es wurde später von R Agarwal und R Srikant verbessert und wurde als Apriori bekannt. Dieser Algorithmus verwendet zwei Schritte: 'Verbinden' und 'Beschneiden', um den Suchraum zu verringern. Es ist ein iterativer Ansatz, um die häufigsten Itemsets zu ermitteln.

Apriori sagt:

Die Wahrscheinlichkeit, dass Artikel I nicht häufig ist, ist, wenn:

• PI)
• P (I + A)
• Wenn ein Itemset-Set einen Wert hat, der unter der Mindestunterstützung liegt, fallen alle Supersets ebenfalls unter die Mindestunterstützung und können daher ignoriert werden. Diese Eigenschaft wird als Antimonotone-Eigenschaft bezeichnet.

Die im Apriori-Algorithmus des Data Mining beschriebenen Schritte sind:

1. Schritt beitreten : Dieser Schritt generiert (K + 1) Itemset aus K-Itemsets, indem jedes Item mit sich selbst verbunden wird.
2. Schritt beschneiden : In diesem Schritt wird die Anzahl der Elemente in der Datenbank überprüft. Wenn das Kandidatenelement nicht die Mindestunterstützung erfüllt, wird es als selten angesehen und daher entfernt. Dieser Schritt wird ausgeführt, um die Größe der Kandidaten-Item-Sets zu reduzieren.

Schritte in Apriori

Der Apriori-Algorithmus ist eine Folge von Schritten, die ausgeführt werden müssen, um die häufigste Elementmenge in der angegebenen Datenbank zu finden. Diese Data Mining-Technik folgt iterativ den Verknüpfungs- und Bereinigungsschritten, bis die häufigste Elementmenge erreicht ist. Ein Mindestunterstützungsschwellenwert ist im Problem angegeben oder wird vom Benutzer angenommen.

# 1) In der ersten Iteration des Algorithmus wird jedes Element als Kandidat für 1 Elementelemente verwendet. Der Algorithmus zählt die Vorkommen jedes Elements.

#zwei) Lassen Sie es eine minimale Unterstützung geben, min_sup (zB 2). Die Menge von 1 - Itemsets, deren Auftreten die min sup erfüllt, wird bestimmt. Nur diejenigen Kandidaten, die mehr als oder gleich min_sup zählen, werden für die nächste Iteration übernommen und die anderen werden beschnitten.

#3) Als nächstes werden häufige Elemente mit 2 Elementen und min_sup erkannt. Dazu wird im Join-Schritt das 2-Itemset durch Bilden einer 2er-Gruppe durch Kombinieren von Items mit sich selbst generiert.

# 4) Die Kandidaten mit 2 Itemsets werden unter Verwendung des Min-Sup-Schwellenwerts beschnitten. Jetzt hat die Tabelle nur 2 -Elemente mit min-sup.

# 5) Die nächste Iteration bildet 3-Item-Sets mit dem Join- und Prune-Schritt. Diese Iteration folgt der Antimonoton-Eigenschaft, bei der die Teilmengen von 3-Elementmengen, dh die 2-Elementmengen-Teilmengen jeder Gruppe, in min_sup fallen. Wenn alle Teilmengen mit zwei Elementen häufig sind, ist die Obermenge häufig, andernfalls wird sie beschnitten.

# 6) Der nächste Schritt folgt dem Erstellen einer 4-Elemente-Gruppe, indem die 3-Elemente-Gruppe mit sich selbst verbunden und beschnitten wird, wenn die Teilmenge die min_sup-Kriterien nicht erfüllt. Der Algorithmus wird gestoppt, wenn die häufigste Elementmenge erreicht ist.

(Bild Quelle ))

Beispiel für Apriori:Unterstützungsschwelle = 50%, Vertrauen = 60%

TABELLE 1

Lösung:

Unterstützungsschwelle = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Anzahl jedes Artikels

TABELLE 2

2. Schritt beschneiden: TABELLE 2 zeigt, dass das I5-Element nicht min_sup = 3 erfüllt, daher wird es gelöscht, nur I1, I2, I3, I4 erfüllen min_sup count.

TISCH 3

3. Schritt beitreten: Formular 2-Itemset. Von TABELLE 1 Finden Sie das Vorkommen von 2-Itemset heraus.

Tabelle 4

Vier. Schritt beschneiden: TABELLE -4 zeigt, dass die Objektgruppe {I1, I4} und {I3, I4} min_sup nicht erfüllt und daher gelöscht wird.

Tabelle 5

5. Schritt verbinden und beschneiden: Form 3-Itemset. Von dem TABELLE 1 Finden Sie das Vorkommen von 3-Itemset heraus. Von Tabelle 5 Finden Sie die 2-Itemset-Teilmengen heraus, die min_sup unterstützen.

Wir können sehen, dass für die Teilmenge {I1, I2, I3} Teilmengen {I1, I2}, {I1, I3}, {I2, I3} in vorkommen Tabelle 5 daher ist {I1, I2, I3} häufig.

Wir können für Itemset {I1, I2, I4} Teilmengen sehen, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} sind nicht häufig, da sie in nicht vorkommen Tabelle 5 daher ist {I1, I2, I4} nicht häufig, daher wird es gelöscht.

Tabelle 6

Nur {I1, I2, I3} ist häufig .

6. Assoziationsregeln generieren: Aus dem oben entdeckten häufigen Itemset könnte die Assoziation stammen:

{I1, I2} => {I3}

Vertrauen = Unterstützung {I1, I2, I3} / Unterstützung {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Vertrauen = Unterstützung {I1, I2, I3} / Unterstützung {I1, I3} = (3/3) * 100 = 100%

Arten von Funktionen in c ++

{I2, I3} => {I1}

Vertrauen = Unterstützung {I1, I2, I3} / Unterstützung {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Vertrauen = Unterstützung {I1, I2, I3} / Unterstützung {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Vertrauen = Unterstützung {I1, I2, I3} / Unterstützung {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Vertrauen = Unterstützung {I1, I2, I3} / Unterstützung {I3} = (3/4) * 100 = 75%

Dies zeigt, dass alle oben genannten Zuordnungsregeln stark sind, wenn der Mindestvertrauensschwellenwert 60% beträgt.

Der Apriori-Algorithmus: Pseudocode

C: Kandidatensatz der Größe k

L: Häufige Artikelmenge der Größe k

(Bild Quelle ))

Vorteile

1. Einfach zu verstehender Algorithmus
2. Join- und Prune-Schritte lassen sich problemlos für große Objektgruppen in großen Datenbanken implementieren

Nachteile

1. Es erfordert eine hohe Berechnung, wenn die Itemsets sehr groß sind und die minimale Unterstützung sehr gering gehalten wird.
2. Die gesamte Datenbank muss gescannt werden.

Methoden zur Verbesserung der Apriori-Effizienz

Es stehen viele Methoden zur Verfügung, um die Effizienz des Algorithmus zu verbessern.

1. Hash-basierte Technik: Diese Methode verwendet eine Hash-basierte Struktur, die als Hash-Tabelle bezeichnet wird, um die k-Itemsets und ihre entsprechende Anzahl zu generieren. Es verwendet eine Hash-Funktion zum Generieren der Tabelle.
2. Transaktionsreduzierung: Diese Methode reduziert die Anzahl der in Iterationen gescannten Transaktionen. Die Transaktionen, die keine häufigen Artikel enthalten, werden markiert oder entfernt.
3. Partitionierung: Diese Methode erfordert nur zwei Datenbank-Scans, um die häufigen Objektgruppen abzubauen. Es heißt, dass jede Elementmenge, die möglicherweise häufig in der Datenbank vorkommt, in mindestens einer der Partitionen der Datenbank häufig sein sollte.
4. Probenahme: Diese Methode wählt eine Zufallsstichprobe S aus Datenbank D aus und sucht dann in S nach häufigen Itemsets. Es kann möglich sein, ein globales häufiges Itemset zu verlieren. Dies kann durch Absenken von min_sup reduziert werden.
5. Dynamische Itemset-Zählung: Diese Technik kann an jedem markierten Startpunkt der Datenbank während des Scannens der Datenbank neue Kandidaten-Item-Sets hinzufügen.

Anwendungen des Apriori-Algorithmus

Einige Felder, in denen Apriori verwendet wird:

1. Im Bildungsbereich: Extrahieren von Assoziationsregeln beim Data Mining zugelassener Studenten anhand von Merkmalen und Besonderheiten.
2. Im medizinischen Bereich: Zum Beispiel Analyse der Patientendatenbank.
3. In der Forstwirtschaft: Analyse der Wahrscheinlichkeit und Intensität von Waldbränden mit den Waldbranddaten.
4. Apriori wird von vielen Firmen wie Amazon in der USA verwendet Empfehlungssystem und von Google für die automatische Vervollständigung.

Fazit

Der Apriori-Algorithmus ist ein effizienter Algorithmus, der die Datenbank nur einmal durchsucht.

Es reduziert die Größe der Itemsets in der Datenbank erheblich und bietet eine gute Leistung. Somit hilft Data Mining Verbrauchern und Branchen, Entscheidungen besser zu treffen.

In unserem nächsten Tutorial erfahren Sie mehr über den Algorithmus für häufiges Musterwachstum!

PREV Tutorial | NÄCHSTES Tutorial

Literatur-Empfehlungen

• Data Mining-Techniken: Algorithmus, Methoden und Top-Data Mining-Tools
• Data Mining: Prozesse, Techniken und wichtige Probleme bei der Datenanalyse
• Data Mining-Beispiele: Häufigste Anwendungen von Data Mining 2021
• Beispiele für Entscheidungsbaumalgorithmen im Data Mining
• Data Mining-Prozess: Modelle, Prozessschritte und Herausforderungen
• Data Mining gegen maschinelles Lernen gegen künstliche Intelligenz gegen tiefes Lernen
• Top 15 der besten kostenlosen Data Mining-Tools: Die umfassendste Liste
• JMeter-Datenparametrierung mit benutzerdefinierten Variablen