FP-Wachstumsalgorithmus (Frequent Pattern) im Data Mining

frequent pattern growth algorithm data mining

Ausführliches Tutorial zum Algorithmus für häufiges Musterwachstum, der die Datenbank in Form eines FP-Baums darstellt. Beinhaltet FP-Wachstum gegen Apriori-Vergleich:

Apriori-Algorithmus wurde in unserem vorherigen Tutorial ausführlich erklärt. In diesem Tutorial erfahren Sie mehr über häufiges Musterwachstum - FP-Wachstum ist eine Methode zum Mining häufiger Objektgruppen.

wie man eine ausführbare JAR-Datei öffnet

Wie wir alle wissen, ist Apriori ein Algorithmus für häufiges Pattern-Mining, der sich darauf konzentriert, Elementmengen zu generieren und die häufigste Elementmenge zu ermitteln. Es reduziert die Größe des Itemset in der Datenbank erheblich, Apriori hat jedoch auch seine eigenen Mängel.

Lesen Sie unsere Ganze Data Mining-Schulungsreihe für eine vollständige Kenntnis des Konzepts.

Was du lernen wirst:

• Mängel des Apriori-Algorithmus
• Algorithmus für häufiges Musterwachstum
• FP-Baum
• Häufige Schritte des Musteralgorithmus
• Beispiel eines FP-Wachstumsalgorithmus
• Vorteile des FP-Wachstumsalgorithmus
• Nachteile des FP-Wachstumsalgorithmus
• FP Wachstum gegen Apriori
• EKLAT
• Fazit
• Literatur-Empfehlungen

Mängel des Apriori-Algorithmus

1. Die Verwendung von Apriori erfordert eine Generation von Kandidaten-Itemsets. Diese Itemsets können eine große Anzahl sein, wenn das Itemset in der Datenbank sehr groß ist.
2. Apriori benötigt mehrere Scans der Datenbank, um die Unterstützung jedes generierten Itemsets zu überprüfen. Dies führt zu hohen Kosten.

Diese Mängel können mit dem FP-Wachstumsalgorithmus behoben werden.

Algorithmus für häufiges Musterwachstum

Dieser Algorithmus ist eine Verbesserung der Apriori-Methode. Ein häufiges Muster wird erzeugt, ohne dass eine Kandidatengenerierung erforderlich ist. Der FP-Wachstumsalgorithmus repräsentiert die Datenbank in Form eines Baums, der als häufiger Musterbaum oder FP-Baum bezeichnet wird.

Diese Baumstruktur behält die Zuordnung zwischen den Elementmengen bei. Die Datenbank ist mit einem häufigen Element fragmentiert. Dieser fragmentierte Teil wird als 'Musterfragment' bezeichnet. Die Itemsets dieser fragmentierten Muster werden analysiert. Somit wird mit dieser Methode die Suche nach häufigen Itemsets vergleichsweise reduziert.

FP-Baum

Frequent Pattern Tree ist eine baumartige Struktur, die mit den anfänglichen Elementmengen der Datenbank erstellt wird. Der Zweck des FP-Baums besteht darin, das häufigste Muster abzubauen. Jeder Knoten des FP-Baums repräsentiert ein Element der Elementmenge.

Der Wurzelknoten repräsentiert Null, während die unteren Knoten die Itemsets repräsentieren. Die Zuordnung der Knoten zu den unteren Knoten, dh die Elementmengen mit den anderen Elementmengen, wird beim Bilden des Baums beibehalten.

Häufige Schritte des Musteralgorithmus

Mit der Methode des häufigen Musterwachstums können wir das häufige Muster ohne Kandidatengenerierung finden.

Sehen wir uns die Schritte an, mit denen das häufige Muster mithilfe des Algorithmus für häufiges Musterwachstum ermittelt wird:

# 1) Der erste Schritt besteht darin, die Datenbank zu scannen, um das Vorkommen der Objektgruppen in der Datenbank zu ermitteln. Dieser Schritt ist der gleiche wie der erste Schritt von Apriori. Die Anzahl der 1-Itemsets in der Datenbank wird als Support-Count oder Häufigkeit der 1-Itemsets bezeichnet.

#zwei) Der zweite Schritt besteht darin, den FP-Baum zu erstellen. Erstellen Sie dazu die Wurzel des Baumes. Die Wurzel wird durch null dargestellt.

#3) Der nächste Schritt besteht darin, die Datenbank erneut zu scannen und die Transaktionen zu untersuchen. Untersuchen Sie die erste Transaktion und finden Sie die darin enthaltene Artikelgruppe heraus. Das Itemset mit der maximalen Anzahl wird oben genommen, das nächste Itemset mit der niedrigeren Anzahl und so weiter. Dies bedeutet, dass der Zweig des Baums mit Transaktionselementmengen in absteigender Reihenfolge der Anzahl erstellt wird.

# 4) Die nächste Transaktion in der Datenbank wird geprüft. Die Artikelgruppen sind in absteigender Reihenfolge der Anzahl sortiert. Wenn eine Elementmenge dieser Transaktion bereits in einem anderen Zweig vorhanden ist (z. B. in der ersten Transaktion), hat dieser Transaktionszweig ein gemeinsames Präfix für den Stamm.

Dies bedeutet, dass die allgemeine Artikelgruppe mit dem neuen Knoten einer anderen Artikelgruppe in dieser Transaktion verknüpft ist.

# 5) Außerdem wird die Anzahl der Artikelgruppen erhöht, wenn sie in den Transaktionen auftreten. Sowohl die Anzahl der gemeinsamen Knoten als auch der Anzahl neuer Knoten wird um 1 erhöht, wenn sie gemäß Transaktionen erstellt und verknüpft werden.

# 6) Der nächste Schritt besteht darin, den erstellten FP-Baum abzubauen. Dazu wird zunächst der unterste Knoten zusammen mit den Verknüpfungen der untersten Knoten untersucht. Der unterste Knoten repräsentiert die Frequenzmusterlänge 1. Überqueren Sie von dort aus den Pfad im FP-Baum. Dieser Pfad oder diese Pfade werden als bedingte Musterbasis bezeichnet.

Die bedingte Musterbasis ist eine Unterdatenbank, die aus Präfixpfaden im FP-Baum besteht, die mit dem niedrigsten Knoten (Suffix) auftreten.

# 7) Erstellen Sie einen bedingten FP-Baum, der aus einer Anzahl von Elementmengen im Pfad besteht. Die Itemsets, die die Schwellenwertunterstützung erfüllen, werden im bedingten FP-Baum berücksichtigt.

Implementieren Sie einen binären Suchbaum in Java

# 8) Häufige Muster werden aus dem bedingten FP-Baum generiert.

Beispiel eines FP-Wachstumsalgorithmus

Unterstützungsschwelle = 50%, Vertrauen = 60%

Tabelle 1

Lösung:

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

1. Anzahl der einzelnen Elemente

Tabelle 2

2. Sortieren Sie die Artikelgruppe in absteigender Reihenfolge.

Tisch 3

3. Erstellen Sie den FP-Baum

1. Betrachtet man den Wurzelknoten null.
2. Der erste Scan der Transaktion T1: I1, I2, I3 enthält drei Elemente {I1: 1}, {I2: 1}, {I3: 1}, wobei I2 als untergeordnetes Element mit root verknüpft ist und I1 mit I2 und I3 verknüpft ist ist mit I1 verbunden.
3. T2: I2, I3, I4 enthält I2, I3 und I4, wobei I2 mit root verknüpft ist, I3 mit I2 verknüpft ist und I4 mit I3 verknüpft ist. Dieser Zweig würde jedoch den I2-Knoten so gemeinsam nutzen, wie er bereits in T1 verwendet wird.
4. Erhöhen Sie die Anzahl von I2 um 1 und I3 ist als Kind mit I2 verknüpft, I4 ist als Kind mit I3 verknüpft. Die Anzahl beträgt {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. Ebenso wird ein neuer Zweig mit I5 mit I4 verknüpft, wenn ein untergeordnetes Element erstellt wird.
6. T4: I1, I2, I4. Die Sequenz ist I2, I1 und I4. I2 ist bereits mit dem Wurzelknoten verbunden, daher wird es um 1 erhöht. Ebenso wird I1 um 1 erhöht, da es bereits mit I2 in T1 verbunden ist, also {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. Die Sequenz ist I2, I1, I3 und I5. Also {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. Die Sequenz ist I2, I1, I3 und I4. Also {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. Das Mining des FP-Baums ist unten zusammengefasst:

1. Das niedrigste Knotenelement I5 wird nicht berücksichtigt, da es keine minimale Unterstützungsanzahl hat, daher wird es gelöscht.
2. Der nächst niedrigere Knoten ist I4. I4 tritt in zwei Zweigen auf: {I2, I1, I3 :, I41}, {I2, I3, I4: 1}. Wenn Sie also I4 als Suffix betrachten, lauten die Präfixpfade {I2, I1, I3: 1}, {I2, I3: 1}. Dies bildet die bedingte Musterbasis.
3. Die bedingte Musterbasis wird als Transaktionsdatenbank betrachtet, ein FP-Baum wird erstellt. Dies enthält {I2: 2, I3: 2}, I1 wird nicht berücksichtigt, da es die minimale Unterstützungsanzahl nicht erfüllt.
4. Dieser Pfad generiert alle Kombinationen häufiger Muster: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Für I3 wäre der Präfixpfad: {I2, I1: 3}, {I2: 1}, dies erzeugt einen FP-Baum mit 2 Knoten: {I2: 4, I1: 3} und es werden häufige Muster erzeugt: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Für I1 wäre der Präfixpfad: {I2: 4} Dies erzeugt einen FP-Baum mit einem einzelnen Knoten: {I2: 4} und häufige Muster werden generiert: {I2, I1: 4}.

Das folgende Diagramm zeigt den bedingten FP-Baum, der dem bedingten Knoten I3 zugeordnet ist.

Vorteile des FP-Wachstumsalgorithmus

1. Dieser Algorithmus muss die Datenbank im Vergleich zu Apriori, das die Transaktionen für jede Iteration scannt, nur zweimal scannen.
2. Das Pairing von Elementen wird in diesem Algorithmus nicht durchgeführt, wodurch es schneller wird.
3. Die Datenbank wird in einer kompakten Version im Speicher gespeichert.
4. Es ist effizient und skalierbar, um sowohl lange als auch kurze häufige Muster abzubauen.

Nachteile des FP-Wachstumsalgorithmus

1. FP Tree ist umständlicher und schwieriger zu bauen als Apriori.
2. Es kann teuer sein.
3. Wenn die Datenbank groß ist, passt der Algorithmus möglicherweise nicht in den gemeinsam genutzten Speicher.

FP Wachstum gegen Apriori

EKLAT

Die obige Methode, Apriori- und FP-Wachstum, fördert häufige Objektmengen im horizontalen Datenformat. ECLAT ist eine Methode zum Mining häufiger Objektgruppen im vertikalen Datenformat. Die Daten im horizontalen Datenformat werden in das vertikale Format umgewandelt.

Zum Beispiel,Apriori und FP Wachstum verwenden:

Die ECLAT hat das Format der Tabelle wie folgt:

Fragen zum Selen-Interview für 8 Jahre Erfahrung

Diese Methode bildet 2-Itemsets, 3 Itemsets und k Itemsets im vertikalen Datenformat. Dieser Prozess mit k wird um 1 erhöht, bis keine Kandidaten-Itemsets mehr gefunden werden. Einige Optimierungstechniken wie Diffset werden zusammen mit Apriori verwendet.

Diese Methode hat gegenüber Apriori einen Vorteil, da die Datenbank nicht gescannt werden muss, um die Unterstützung von k + 1-Objektgruppen zu finden. Dies liegt daran, dass der Transaktionssatz die Anzahl der Vorkommen jedes Elements in der Transaktion enthält (Support). Der Engpass tritt auf, wenn viele Transaktionen viel Speicher und Rechenzeit benötigen, um die Mengen zu schneiden.

Fazit

Der Apriori-Algorithmus wird für Mining-Assoziationsregeln verwendet. Es funktioniert nach dem Prinzip, dass „die nicht leeren Teilmengen häufiger Objektmengen auch häufig sein müssen“. Es bildet k-Itemset-Kandidaten aus (k-1) Itemsets und durchsucht die Datenbank nach den häufigen Itemsets.

Der Algorithmus für häufiges Musterwachstum ist die Methode zum Auffinden häufiger Muster ohne Kandidatengenerierung. Es erstellt einen FP-Baum, anstatt die Generierungs- und Teststrategie von Apriori zu verwenden. Der Fokus des FP-Wachstumsalgorithmus liegt auf der Fragmentierung der Pfade der Elemente und dem Mining häufiger Muster.

Wir hoffen, dass diese Tutorials in der Data Mining-Reihe Ihr Wissen über Data Mining erweitert haben !!

PREV Tutorial | ERSTES Tutorial

Literatur-Empfehlungen

• Data Mining-Techniken: Algorithmus, Methoden und Top-Data Mining-Tools
• Apriori-Algorithmus im Data Mining: Implementierung mit Beispielen
• Beispiele für Entscheidungsbaumalgorithmen im Data Mining
• Data Mining-Beispiele: Häufigste Anwendungen von Data Mining 2021
• Data Mining: Prozesse, Techniken und wichtige Probleme bei der Datenanalyse
• Data Mining-Prozess: Modelle, Prozessschritte und Herausforderungen
• CSTE Software Testing Zertifizierungsprüfung Fragenmuster
• Data Mining gegen maschinelles Lernen gegen künstliche Intelligenz gegen tiefes Lernen