Assoziationsregeln
- Eingeführt von
- Agrawal, R., Imielinski, T., & Swami, A.
- Jahr
- 1993
- Typ
- Unsupervised pattern discovery
- Familie
- Machine learning
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Assoziationsregel-Lernen ist eine unüberwachte Technik, die Kookkurrenz-Muster – „wenn X, dann Y“-Implikationen – in großen Transaktionsdatensätzen aufdeckt.
Ursprünglich von Agrawal, Imielinski und Swami (1993) für die Warenkorbanalyse in Supermärkten formalisiert, wird es heute breit in der E-Commerce-Empfehlung, Gesundheitsinformatik, Bioinformatik und Verhaltensforschung angewendet.
Die Intuition hinter der Methode
Stellen Sie sich vor, Sie scannen Millionen von Kassenzetteln und fragen: Welche Produktkombinationen treten tendenziell zusammen auf? Assoziationsregel-Mining beantwortet diese Frage, indem es zählt, wie oft Itemsets zusammen auftreten (Support), wie zuverlässig ein Item ein anderes vorhersagt (Konfidenz), und ob das gemeinsame Auftreten stärker als der Zufall ist (Lift). Regeln wie „Windeln → Bier“ mit hoher Konfidenz und hohem Lift offenbaren echte Verhaltensmuster statt Zufälligkeiten, was dies zu einem mächtigen explorativen Werkzeug macht, wenn keine Zielvariable zur Überwachung vorhanden ist.
Geschichte
Das Assoziationsregel-Lernen wurde 1993 von Agrawal, Imielinski und Swami auf der ACM SIGMOD Konferenz formal eingeführt, motiviert durch die Herausforderung, Supermarkt-Transaktionsdatenbanken zu minen. Ihr nachfolgendes Papier von 1994 stellte den Apriori-Algorithmus vor, der eine effiziente Berechnungsmethode lieferte. Das Feld wuchs in den 1990er und 2000er Jahren schnell, wobei FP-growth (Han et al., 2000) später weitere Geschwindigkeitsverbesserungen bot. Assoziationsregeln bleiben eine grundlegende Technik in den Data-Mining-Lehrplänen und werden routinemäßig im Einzelhandel, Gesundheitswesen und in der Webanalyse angewendet.
Wann wird sie eingesetzt?
Verwenden Sie Assoziationsregeln, wenn Ihr Ziel die explorative Entdeckung von Kookkurrenz-Mustern in transaktionalen oder binär kodierten Daten ist – Einkaufskörbe, klinische Kookkurrenz von Diagnosen, Klickströme, Umfrage-Item-Batterien oder Genexpressionsprofile. Die Methode ist unüberwacht und erfordert kein Ergebnislabel, was sie ideal für die Hypothesengenerierung macht. Verwenden Sie sie nicht, wenn Sie eine definierte Zielvariable haben und diese vorhersagen möchten (verwenden Sie stattdessen überwachte Klassifikation oder Regression); wenn Ihre Daten kontinuierlich sind und nicht sinnvoll diskretisiert wurden; wenn die Stichprobengrößen klein sind (spärliche Itemsets ergeben unzuverlässige Support-Schätzungen); oder wenn die Regelausgabe fälschlicherweise als kausale Inferenz interpretiert wird – Assoziationsregeln sind rein korrelativ.
Grenzen und Hinweise
- Erfordert, dass Daten transaktional oder diskretisiert binär sind; kontinuierliche Merkmale müssen gebinnt werden, was willkürliche Entscheidungen mit sich bringt.
- Die Anzahl der Regeln kann enorm sein; eine nachträgliche Filterung und Rangfolge nach Lift oder anderen Interessantheitsmaßen ist zwingend erforderlich.
- Support- und Konfidenzschwellenwerte müssen vom Forscher festgelegt werden; die Ergebnisse sind empfindlich gegenüber diesen Entscheidungen.
- Regeln sind rein korrelativ – kausale Behauptungen erfordern ein zusätzliches Studiendesign (z. B. Experiment oder Quasi-Experiment).
- Rechenintensiv bei Datensätzen mit sehr großen Itemsets, selbst mit Beschneidung.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Vollständig unüberwacht: keine gelabelte Zielvariable erforderlich, was eine offene Mustererkennung ermöglicht.
- Interpretierbare Ausgabe: Jede Regel ist eine menschenlesbare WENN-DANN-Anweisung mit quantifiziertem Support, Konfidenz und Lift.
- Skaliert auf sehr große Transaktionsdatenbanken mittels Beschneidungsheuristiken (Apriori, FP-growth).
- Anwendbar in allen Domänen, wo Kookkurrenz in binär kodierten Datensätzen sinnvoll ist.
- Hypothesengenerierung: deckt unerwartete Kookkurrenzen auf, die nachfolgende Bestätigungsanalysen leiten können.
Anwendungen
- Warenkorbanalyse: Identifizierung, welche Produkte häufig zusammen gekauft werden, um die Produktplatzierung und Werbeaktionen zu steuern.
- E-Commerce-Empfehlung: Generierung von Vorschlägen wie „Kunden, die X gekauft haben, kauften auch Y“.
- Entdeckung klinischer Komorbiditäten: Auffinden von Diagnosen, Medikamenten oder Symptomen, die in Patientenakten zusammen auftreten.
- Bioinformatik: Erkennung von koexprimierten Genen oder kookkurrierenden genetischen Varianten über Proben hinweg.
- Web-Nutzungs-Mining: Aufdeckung gemeinsamer Klickstrommuster und Navigationssequenzen auf Websites.
- Umfrage- und Verhaltensforschung: Auffinden von Fragebogen-Items oder Verhaltensweisen, die bei Befragten zusammen auftreten.
So funktioniert es
So funktioniert es
Der Datensatz wird als binäre Transaktionsmatrix dargestellt: Jede Zeile ist eine Transaktion und jede Spalte ein mögliches Item, wobei eine 1 anzeigt, dass das Item vorhanden war. Diese spärliche, breite Darstellung ist das Kern-Eingabeformat; nicht-binäre oder quantitative Items müssen vor diesem Schritt diskretisiert werden.
Alle Item-Kombinationen (Itemsets), deren Häufigkeit in der Transaktionsdatenbank einen vom Benutzer festgelegten Mindest-Support-Schwellenwert erreicht, werden identifiziert. Das Apriori-Prinzip – jede Teilmenge eines häufigen Itemsets ist ebenfalls häufig – beschneidet den kombinatorischen Suchraum dramatisch, wodurch die Enumeration selbst bei großen Katalogen handhabbar wird.
Formel
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|} \geq \text{min\_sup}Für jedes häufige Itemset werden alle möglichen Antezedens-Konsequens-Splits (X → Y, wobei X und Y disjunkte nicht-leere Teilmengen sind) als Kandidatenregeln generiert. Die Anzahl der Kandidaten kann groß sein, daher ist der nachfolgende Filterschritt unerlässlich.
Formel
X \Rightarrow Y, \quad X \cap Y = \emptyset
Jede Kandidatenregel wird anhand ihrer Konfidenz bewertet: die bedingte Wahrscheinlichkeit, dass Y vorhanden ist, gegeben dass X vorhanden ist. Nur Regeln, die einen Mindest-Konfidenz-Schwellenwert überschreiten, werden beibehalten, wodurch Antezedenzien herausgefiltert werden, die die Konsequenz nur geringfügig besser als die Basisrate vorhersagen.
Formel
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}Beibehaltene Regeln werden nach Lift geordnet, dem Verhältnis des beobachteten gemeinsamen Supports zum unter Unabhängigkeit erwarteten Support. Ein Lift größer als 1 signalisiert eine echte positive Assoziation; ein Lift nahe 1 zeigt an, dass die Items nicht häufiger als zufällig zusammen auftreten; ein Lift unter 1 weist auf eine negative Assoziation hin. Das Sortieren nach Lift bringt die umsetzbarsten und nicht-trivialsten Regeln zum Vorschein.
Formel
\text{lift}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Häufige Fallstricke
- Einstellung eines zu niedrigen Mindest-Supports, was die Ausgabe mit unechten, seltenen Regeln überflutet, die nicht generalisieren.
- Ignorieren des Lifts und Berichten aller Regeln mit hoher Konfidenz, von denen viele lediglich häufige Basisraten-Items widerspiegeln können.
- Behandlung entdeckter Regeln als kausal ohne weitere Validierung (z. B. Verwechslung von „Bier und Windeln treten zusammen auf“ mit „Bier verursacht den Kauf von Windeln“).
- Anwendung von Assoziationsregeln auf kontinuierliche Daten ohne prinzipielle Diskretisierung, wodurch Regeln entstehen, die vollständig von willkürlichen Bin-Grenzen abhängen.
- Übersehen von Problemen multipler Vergleiche, wenn Tausende von Regeln generiert und selektiv hervorgehoben werden.
Häufig gestellte Fragen
Wie wähle ich die Mindest-Support- und Konfidenzschwellenwerte?
Es gibt keine universelle Regel. Beginnen Sie mit der Untersuchung der Support-Verteilung einzelner Items und setzen Sie dann den Mindest-Support niedrig genug an, um interessante Muster zu erfassen, aber hoch genug, um sicherzustellen, dass Itemsets in einer sinnvollen absoluten Anzahl von Transaktionen erscheinen. Eine Mindestkonfidenz von 0,6–0,8 ist ein üblicher Startbereich, aber Domänenwissen und eine Lift-basierte Rangfolge sollten die endgültige Auswahl leiten.
Was ist der Unterschied zwischen Konfidenz und Lift, und was sollte ich priorisieren?
Konfidenz misst, wie oft Y auf X folgt unter den Transaktionen, die X enthalten, ignoriert aber die Basisrate von Y. Lift korrigiert dies, indem es die Konfidenz durch den marginalen Support von Y teilt. Eine Regel mit hoher Konfidenz, aber einem Lift nahe 1, fügt wenig Information hinzu, außer dass Y häufig ist. Priorisieren Sie Lift, wenn Sie nach wirklich nicht-trivialen Assoziationen filtern.
Können Assoziationsregeln zur Vorhersage verwendet werden?
Sie sind primär deskriptiv und explorativ statt prädiktiv. Obwohl es möglich ist, Regeln mit einer festen Konsequenz (einem einzelnen Ziel-Item) zur Klassifikation zu verwenden – eine Technik, die als assoziative Klassifikation bezeichnet wird –, optimiert das Standard-Assoziationsregel-Mining keine prädiktive Verlustfunktion und sollte überwachte Modelle nicht ersetzen, wenn ein gelabeltes Ergebnis verfügbar ist.
Mein Datensatz enthält kontinuierliche Variablen. Kann ich trotzdem Assoziationsregeln verwenden?
Nur nach Diskretisierung. Kontinuierliche Variablen müssen in kategoriale Intervalle (z. B. Altersgruppen, Quintile) gebinnt werden, bevor sie als binäre Items kodiert werden. Die Wahl der Bin-Grenzen beeinflusst maßgeblich, welche Regeln entstehen, daher sollten Diskretisierungsentscheidungen theoretisch motiviert und transparent berichtet werden.
Wie unterscheiden sich Assoziationsregeln von der Korrelationsanalyse?
Korrelation (z. B. Pearsons r) misst die lineare Beziehung zwischen zwei kontinuierlichen Variablen. Assoziationsregeln entdecken Kookkurrenz-Muster unter Mengen binärer Items – beliebiger Kombinationsgröße – in Transaktionsdaten. Die Metriken (Support, Konfidenz, Lift) sind frequenzbasiert statt momentenbasiert, und die Ausgabe ist eine Menge menschenlesbarer WENN-DANN-Regeln statt eines einzelnen numerischen Koeffizienten.
Verwandte Methoden
Quellen
Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 207–216.
DOI-Referenz öffnenKopiert.Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.
ISBN: 978-0-13-312890-1Kopiert.