Algorithmus - Eclat-Algorithmus

• Involvierte Definitionen:
  • Transaktionsdatensatz
  • Häufiges Itemset
  • Apriori-Eigenschaft (Obermengen)
• Veranstaltung: DM
• Referenz: @valdes2025 (p. 112 f.)

⠀

Algorithmus: Eclat-Algorithmus

Sei eine Itemmenge.
Sei ein Transaktionsdatensatz über .

Als Eclat-Algorithmus (kurz für Equivalence Class Transformation) bezeichnen wir einen Algorithmus zur Berechnung von häufigen Itemsets.

Wir bilden zunächst das sogenannte vertikale Datenformat, indem wir für jedes Item in diejenigen Transaktionen auflisten, in denen enthalten ist.

Die Menge der Transaktionen ist dann das vertikale Datenformat für .

Anschließend prüfen wir, ob in mindestens Transaktionen enthalten ist. Falls nein, schließen wir aus. Falls ja, ist eine häufige Menge.

Anschließend fahren wir mit den Schnittmengen der häufigen Items fort. Wir bilden wieder das vertikale Datenformat für die Schnittmengen und schließen diejenigen Mengen aus, die nicht genügen.

Anschließend fahren wir, wie beim FreqItems-Algorithmus, mit den Schnittmengen der häufigen Items des letzten Schrittes fort.

Diejenigen Mengen, von denen Teilmengen nicht-häufig sind, können wir dabei bereits nach dem Apriori-Prinzip ausschließen.

Für die verbleibenden Kandidaten bilden wir das vertikale Datenformat. Alle Mengen, die genügen, erhalten wir als Ergebnis für den nächsten Schritt.