Assoziationsregeln im Data Mining

Assoziationsregeln sind “Wenn-dann”-Aussagen, die helfen, die Wahrscheinlichkeit von Beziehungen zwischen Datenelementen innerhalb großer Datensätze in verschiedenen Arten von Datenbanken aufzuzeigen. Das Mining von Assoziationsregeln hat eine Reihe von Anwendungen und wird häufig eingesetzt, um Zusammenhänge zwischen Verkäufen in Transaktionsdaten oder in medizinischen Datensätzen zu entdecken.

Anwendungsfälle für Assoziationsregeln

In der Datenwissenschaft werden Assoziationsregeln verwendet, um Korrelationen und gemeinsame Vorkommen zwischen Datensätzen zu finden. Sie werden idealerweise verwendet, um Muster in Daten aus scheinbar unabhängigen Informationsbeständen wie relationalen Datenbanken und Transaktionsdatenbanken zu erklären. Die Verwendung von Assoziationsregeln wird manchmal auch als “Assoziationsregel-Mining” oder “Mining von Assoziationen” bezeichnet.

Im Folgenden finden Sie einige praktische Anwendungsfälle für Assoziationsregeln:

  • Medizin. Ärzte können Assoziationsregeln verwenden, um Patienten zu diagnostizieren. Bei der Diagnosestellung sind viele Variablen zu berücksichtigen, da viele Krankheiten die gleichen Symptome aufweisen. Mithilfe von Assoziationsregeln und einer auf maschinellem Lernen basierenden Datenanalyse können Ärzte die bedingte Wahrscheinlichkeit einer bestimmten Krankheit bestimmen, indem sie Symptombeziehungen in den Daten vergangener Fälle vergleichen. Wenn neue Diagnosen gestellt werden, kann das maschinelle Lernmodell die Regeln anpassen, um die aktualisierten Daten zu berücksichtigen.
  • Einzelhandel. Einzelhändler können Daten über Einkaufsmuster sammeln, indem sie Kaufdaten aufzeichnen, wenn die Strichcodes der Artikel von Kassensystemen gescannt werden. Modelle für maschinelles Lernen können in diesen Daten nach Übereinstimmungen suchen, um festzustellen, welche Produkte am wahrscheinlichsten zusammen gekauft werden. Der Einzelhändler kann dann seine Marketing- und Verkaufsstrategie anpassen, um von diesen Informationen zu profitieren.
  • Gestaltung der Benutzererfahrung (UX). Entwickler können Daten darüber sammeln, wie Verbraucher eine von ihnen erstellte Website nutzen. Sie können dann die Assoziationen in den Daten nutzen, um die Benutzeroberfläche der Website zu optimieren, indem sie z. B. analysieren, wo die Benutzer am ehesten klicken und was die Wahrscheinlichkeit maximiert, dass sie einer Aufforderung zum Handeln nachkommen.
  • Unterhaltung. Dienste wie Netflix und Spotify können Assoziationsregeln nutzen, um ihre Inhaltsempfehlungssysteme zu optimieren. Modelle für maschinelles Lernen analysieren Daten zum früheren Nutzerverhalten auf häufige Muster, entwickeln Assoziationsregeln und verwenden diese Regeln, um Inhalte zu empfehlen, mit denen ein Nutzer wahrscheinlich etwas anfangen kann, oder um Inhalte so zu organisieren, dass die interessantesten Inhalte für einen bestimmten Nutzer an erster Stelle stehen.

Wie Assoziationsregeln funktionieren

Bei der Suche nach Assoziationsregeln werden grundsätzlich Modelle des maschinellen Lernens eingesetzt, um Daten nach Mustern oder gemeinsamen Vorkommnissen in einer Datenbank zu analysieren. Dabei werden häufige Wenn-Dann-Verknüpfungen identifiziert, die ihrerseits Assoziationsregeln darstellen.

Eine Assoziationsregel besteht aus zwei Teilen: einem Antezedens (wenn) und einem Konsekutivum (dann). Ein Antezedens ist ein Element, das in den Daten gefunden wird. Eine Konsequenz ist ein Element, das in Kombination mit dem Antezedens gefunden wird.

Assoziationsregeln werden erstellt, indem die Daten nach häufigen Wenn-Dann-Mustern durchsucht werden und die Kriterien Unterstützung und Konfidenz verwendet werden, um die wichtigsten Beziehungen zu ermitteln. Die Unterstützung ist ein Hinweis darauf, wie häufig die Elemente in den Daten vorkommen. Die Konfidenz gibt an, wie oft die Wenn-Dann-Aussagen als wahr befunden werden. Eine dritte Metrik, der so genannte Lift, kann verwendet werden, um die Konfidenz mit der erwarteten Konfidenz zu vergleichen, d. h. wie oft eine Wenn-dann-Aussage erwartungsgemäß als wahr gefunden wird.

Assoziationsregeln werden aus Item-Sets berechnet, die aus zwei oder mehr Items bestehen. Wenn Regeln aus der Analyse aller möglichen Itemsets erstellt werden, könnte es so viele Regeln geben, dass die Regeln wenig Aussagekraft haben. Aus diesem Grund werden Assoziationsregeln in der Regel aus Regeln erstellt, die in den Daten gut repräsentiert sind.

Maße für die Wirksamkeit von Assoziationsregeln

Die Stärke einer bestimmten Assoziationsregel wird durch zwei Hauptparameter gemessen: Unterstützung und Konfidenz. Die Unterstützung bezieht sich darauf, wie oft eine bestimmte Regel in der zu untersuchenden Datenbank vorkommt. Die Konfidenz bezieht sich auf die Häufigkeit, mit der sich eine bestimmte Regel in der Praxis als wahr herausstellt. Eine Regel kann in einem Datensatz eine starke Korrelation aufweisen, weil sie sehr häufig vorkommt, aber in der Praxis weit weniger häufig angewendet wird. Dies wäre ein Fall von hoher Unterstützung, aber geringem Vertrauen.

Umgekehrt kann eine Regel in einem Datensatz nicht besonders auffallen, aber eine weitere Analyse zeigt, dass sie sehr häufig auftritt. Dies wäre ein Fall von hohem Vertrauen und geringer Unterstützung. Die Verwendung dieser Maße hilft Analysten, Kausalität von Korrelation zu trennen, und ermöglicht ihnen, eine bestimmte Regel richtig zu bewerten.

Ein dritter Wertparameter, der so genannte Lift-Wert, ist das Verhältnis von Konfidenz zu Unterstützung. Wenn der Lift-Wert negativ ist, besteht eine negative Korrelation zwischen den Datenpunkten. Ist der Wert positiv, besteht eine positive Korrelation, und wenn das Verhältnis gleich 1 ist, besteht keine Korrelation.

Algorithmen für Assoziationsregeln

Beliebte Algorithmen, die Assoziationsregeln verwenden, sind AIS, SETM, Apriori und Variationen der letzteren.

Mit dem AIS-Algorithmus werden beim Durchsuchen der Daten Item-Sets erzeugt und gezählt. In Transaktionsdaten bestimmt der AIS-Algorithmus, welche großen Itemsets eine Transaktion enthielten, und neue Kandidaten-Itemsets werden erstellt, indem die großen Itemsets mit anderen Items in den Transaktionsdaten erweitert werden.

Der SETM-Algorithmus erzeugt ebenfalls Kandidaten-Itemsets, während er eine Datenbank durchsucht, aber dieser Algorithmus berücksichtigt die Itemsets am Ende seiner Suche. Neue Kandidaten-Itemsets werden auf die gleiche Weise wie beim AIS-Algorithmus erzeugt, aber die Transaktions-ID der erzeugenden Transaktion wird zusammen mit dem Kandidaten-Itemset in einer sequentiellen Datenstruktur gespeichert. Am Ende des Durchlaufs wird die Unterstützungszahl der Kandidaten-Itemsets durch Aggregation der sequentiellen Struktur erstellt. Der Nachteil sowohl des AIS- als auch des SETM-Algorithmus besteht darin, dass jeder Algorithmus viele kleine Kandidaten-Itemsets erzeugen und zählen kann, wie aus den Veröffentlichungen von Dr. Saed Sayad, dem Autor von Real Time Data Mining, hervorgeht.

Beim Apriori-Algorithmus werden die Kandidaten-Itemsets nur aus den großen Itemsets des vorherigen Durchgangs generiert. Das große Itemset des vorherigen Durchgangs wird mit sich selbst verbunden, um alle Itemsets zu erzeugen, deren Größe um eins größer ist. Jedes generierte Itemset mit einer Teilmenge, die nicht groß ist, wird dann gelöscht. Die verbleibenden Teilmengen sind die Kandidaten. Der Apriori-Algorithmus betrachtet jede Teilmenge eines häufigen Itemsets auch als häufiges Itemset. Mit diesem Ansatz reduziert der Algorithmus die Anzahl der in Frage kommenden Kandidaten, indem er nur die Itemsets untersucht, deren Unterstützungsgrad größer als der minimale Unterstützungsgrad ist, so Sayad.

Verwendung von Assoziationsregeln im Data Mining

Beim Data Mining sind Assoziationsregeln nützlich, um das Kundenverhalten zu analysieren und vorherzusagen. Sie spielen eine wichtige Rolle bei der Kundenanalyse, der Warenkorbanalyse, dem Clustering von Produkten, der Kataloggestaltung und dem Ladenlayout.

Programmierer verwenden Assoziationsregeln, um Programme zu erstellen, die maschinelles Lernen beherrschen. Maschinelles Lernen ist eine Form der künstlichen Intelligenz (KI), die darauf abzielt, Programme mit der Fähigkeit zu entwickeln, effizienter zu werden, ohne explizit programmiert zu werden.

Beispiele für Assoziationsregeln im Data Mining

Ein klassisches Beispiel für Assoziationsregeln bezieht sich auf eine Beziehung zwischen Windeln und Bier. In dem scheinbar fiktiven Beispiel wird behauptet, dass Männer, die in ein Geschäft gehen, um Windeln zu kaufen, wahrscheinlich auch Bier kaufen. Daten, die darauf hindeuten würden, könnten wie folgt aussehen:

Ein Supermarkt hat 200.000 Kundentransaktionen. Etwa 4.000 Transaktionen, also etwa 2 % der Gesamtzahl der Transaktionen, beinhalten den Kauf von Windeln. Etwa 5.500 Transaktionen (2,75 %) beinhalten den Kauf von Bier. Davon beinhalten etwa 3.500 Transaktionen (1,75 %) sowohl den Kauf von Windeln als auch von Bier. Ausgehend von den Prozentsätzen müsste diese hohe Zahl viel niedriger sein. Die Tatsache, dass etwa 87,5 % der Windelkäufe mit dem Kauf von Bier einhergehen, deutet jedoch auf einen Zusammenhang zwischen Windeln und Bier hin.

Geschichte

Die Konzepte hinter den Assoziationsregeln lassen sich zwar schon früher zurückverfolgen, doch wurde das Assoziationsregel-Mining in den 1990er Jahren definiert, als die Informatiker Rakesh Agrawal, Tomasz Imieliński und Arun Swami eine auf Algorithmen basierende Methode entwickelten, um Beziehungen zwischen Artikeln in POS-Systemen (Point-of-Sale) zu finden. Durch die Anwendung der Algorithmen auf Supermärkte konnten die Wissenschaftler Verbindungen zwischen verschiedenen gekauften Artikeln, so genannte Assoziationsregeln, aufdecken und diese Informationen schließlich nutzen, um die Wahrscheinlichkeit vorherzusagen, dass verschiedene Produkte zusammen gekauft werden.

Für Einzelhändler bot das Assoziationsregel-Mining eine Möglichkeit, das Kaufverhalten der Kunden besser zu verstehen. Aufgrund seiner Ursprünge im Einzelhandel wird das Assoziationsregel-Mining oft auch als Warenkorbanalyse bezeichnet.

Mit den Fortschritten in der Datenwissenschaft, der künstlichen Intelligenz und dem maschinellen Lernen, die seit dem ursprünglichen Anwendungsfall für Assoziationsregeln erzielt wurden, und mit der zunehmenden Zahl von Geräten, die Daten generieren, können Assoziationsregeln in einem breiteren Spektrum von Anwendungsfällen eingesetzt werden. Es werden mehr Daten generiert, was mehr Anwendungen für Assoziationsregeln bedeutet. KI und maschinelles Lernen ermöglichen es, größere und komplexere Datensätze zu analysieren und nach Assoziationsregeln zu durchsuchen.