Zum Inhalt springen
Zurück zu den Suchergebnissen

ECLAT Frequent-Itemset Mining

Eingeführt von
Mohammed J. Zaki
Jahr
2000
Typ
Frequent-itemset mining algorithm (vertical format)
Familie
Pattern mining

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

ECLAT, eingeführt von Mohammed Zaki im Jahr 2000, extrahiert häufige Itemsets mithilfe einer vertikalen Datenrepräsentation: Anstatt Transaktionen zu scannen, speichert es für jeden Artikel die Menge der Transaktions-IDs (ein Tidset), die ihn enthalten, und berechnet die Unterstützung (Support) jedes Itemsets durch die Schnittmenge von Tidsets.

Dieser tiefensuchende, schnittmengenbasierte Ansatz ist schnell und speichereffizient und stellt eine Alternative zu den horizontalen Scans von Apriori und dem Baum von FP-Growth dar.

Die Intuition hinter der Methode

Die meisten Itemset-Miner denken zeilenweise: Welche Artikel sind in welcher Transaktion? ECLAT dreht den Spieß um. Für jeden Artikel speichert es eine Liste der Transaktionen, die ihn enthalten. Nun ist die Unterstützung eines Artikelpaares einfach die Größe der Überlappung ihrer beiden Listen – eine einfache Mengenoperation (Schnittmenge) – und Sie müssen die Datenbank nie wieder scannen. Um längere häufige Itemsets zu finden, schneiden Sie die Listen kürzerer Itemsets miteinander. Das Durchlaufen dieser Tiefensuche und das Beschneiden, wann immer eine Schnittmenge zu klein wird, enumeriert effizient alle häufigen Itemsets.

Geschichte

Mohammed Zaki führte ECLAT und das vertikale Mining-Paradigma in Arbeiten ein, die in seiner IEEE TKDE-Arbeit von 2000 über skalierbares Assoziations-Mining gipfelten, und verfeinerte es später mit Diffsets (dECLAT). Es schloss sich Apriori (1994, horizontale Kandidatengenerierung) und FP-Growth (2000, baumbasiert) als eine der drei kanonischen Familien von Algorithmen für häufige Itemsets an, wobei jede Scans, Speicher und Datendichte unterschiedlich abwägt. ECLAT bleibt eine Standardoption in Data-Mining-Toolkits.

Wann wird sie eingesetzt?

Verwenden Sie ECLAT für die Extraktion häufiger Itemsets, wenn ein vertikaler, schnittmengenbasierter Ansatz zu den Daten passt – er ist oft sehr schnell auf dichten Datensätzen und vermeidet wiederholte Datenbankscans, was ihn zu einer starken Alternative zu Apriori und einem ebenbürtigen Verfahren zu FP-Growth macht. Er glänzt, wenn Tidsets moderat groß sind und in den Speicher passen, und die Diffset-Variante verarbeitet dichte Daten gut. Seine Kosten: Tidsets für häufige Artikel können auf großen spärlichen Datensätzen groß und speicherintensiv sein, zwischenzeitliche Schnittmengen verursachen zusätzlichen Aufwand, und wie alle unterstützungsbasierten Mining-Verfahren ist er empfindlich gegenüber dem Mindestunterstützungsschwellenwert. Wie immer sind häufige Itemsets nur die erste Stufe; Assoziationsregeln mit Konfidenz/Lift werden anschließend generiert. Wählen Sie zwischen ECLAT, FP-Growth und Apriori basierend auf Datendichte und Speicher.

Grenzen und Hinweise

  • Tidsets für häufige Artikel können groß sein und kosten Speicher auf großen Datensätzen.
  • Zwischenzeitliche Schnittmengen-Ergebnisse verursachen Speicher-/Zeit-Overhead.
  • Weniger intuitiv als horizontale (Apriori) Darstellungen.
  • Empfindlich gegenüber dem Mindestunterstützungsschwellenwert, wie bei allen Itemset-Mining-Verfahren.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Unterstützung, berechnet durch schnelle Tidset-Schnittmengen – keine wiederholten Datenbankscans.
  • Tiefensuche mit Präfix-Äquivalenzklassen wiederverwendet Arbeit und lokalisiert den Speicher.
  • Oft sehr effizient auf dichten Datensätzen, konkurrenzfähig mit FP-Growth.
  • Die Diffset-Optimierung reduziert Speicher- und Schnittkosten weiter.

Anwendungen

  • Marktwarenkorb- und Einzelhandels-Assoziations-Mining.
  • Web- und Clickstream-Kookkurrenz-Analyse.
  • Entdeckung häufiger Kookkurrenzen in der Bioinformatik.
  • Jede Aufgabe zur Extraktion häufiger Itemsets, die einen vertikalen, schnittmengenbasierten Ansatz bevorzugt.
  • Dichte transaktionale Datensätze, bei denen Diffset ECLAT glänzt.

So funktioniert es

So funktioniert es

1

Die Datenbank wird einmal in ein vertikales Format umgewandelt: Jeder Artikel wird auf sein Tidset abgebildet, die Menge der Transaktions-IDs, in denen er vorkommt. Dies ist die zentrale Datenstruktur – alle nachfolgenden Arbeiten sind Mengenoperationen auf Tidsets, nicht Durchläufe über die ursprünglichen Transaktionen.

Formel
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

Die Unterstützung eines Itemsets ist die Kardinalität der Schnittmenge der Tidsets seiner Artikel – die Anzahl der Transaktionen, die alle diese Artikel enthalten. Das Zählen wird zum Schneiden von Mengen, was schnell geht, und häufige einzelne Artikel (diejenigen, deren Tidset groß genug ist) leiten die Suche ein.

Formel
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

Itemsets werden durch Schneiden von Tidsets erweitert: Das Tidset von X ∪ {y} ist die Schnittmenge der Tidsets von X und {y}. ECLAT durchsucht das Itemset-Gitter tiefensuchend innerhalb von Äquivalenzklassen (Itemsets mit gleichem Präfix), sodass Schnittmengen wiederverwendet werden und die Suche lokal bleibt.

Formel
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

Eine Erweiterung wird nur beibehalten, wenn ihr Tidset (und damit ihre Unterstützung) den Mindestunterstützungsschwellenwert erfüllt; andernfalls wird dieser Zweig beschnitten (anti-monotonisch: kein Obermenge kann häufig sein). Diffsets – die nur die Unterschiede zwischen Tidsets speichern – sind eine gängige Optimierung, die den Speicher und die Schnittkosten weiter reduziert.

Formel
\text{keep extensions with } \text{support} \ge \text{minsup}

Häufige Fallstricke

  • Mining sehr großer spärlicher Daten, bei denen Tidsets den Speicher sprengen – erwägen Sie Diffsets oder FP-Growth.
  • Festlegen eines zu niedrigen Mindestunterstützungswertes, was zu einer unüberschaubaren Anzahl von Itemsets führt.
  • Verwechslung von häufigen Itemsets mit Assoziationsregeln (Regeln sind ein separater Schritt).
  • Ignorieren der Diffset-Variante bei dichten Daten, wo sie erheblich hilft.

Häufig gestellte Fragen

Wie unterscheidet sich ECLAT von Apriori und FP-Growth?

Alle drei finden häufige Itemsets. Apriori verwendet ein horizontales Format mit Kandidatengenerierung und vielen Scans; FP-Growth komprimiert Daten in einen Baum und minet rekursiv; ECLAT verwendet ein vertikales Tidset-Format und berechnet die Unterstützung durch Tiefensuche von Transaktions-ID-Listen-Schnittmengen. ECLAT und FP-Growth vermeiden die wiederholten Scans von Apriori.

Was ist ein Tidset?

Ein Tidset (Transaktions-ID-Set) ist die Liste der Transaktionen, die einen gegebenen Artikel oder ein gegebenes Itemset enthalten. ECLAT speichert diese vertikal und berechnet die Unterstützung eines Itemsets als Größe der Schnittmenge der Tidsets seiner Artikel, wodurch das Zählen zu einer Mengenoperation wird.

Was sind Diffsets?

Diffsets speichern nur die Differenz zwischen dem Tidset eines Itemsets und dem seines Elternteils, anstatt des vollständigen Tidsets. Bei dichten Daten reduziert dies den Speicher- und Schnittkosten erheblich und verleiht der dECLAT-Variante einen erheblichen Effizienzvorteil.

Verwandte Methoden

Quellen

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    DOI-Referenz öffnen
    Kopiert.