Assoziationsanalyse – Funktion, Algorithmen und Anwendung

Längst sind Daten zu einer der wertvollsten Ressourcen unserer Zeit geworden. Allerdings entsteht dieser Wert erst dann, wenn man die oftmals versteckten Zusammenhänge erkennt und daraus die richtigen Schlüsse zieht. Weil das ein durchaus vielschichtiges Unterfangen ist, hat sich dafür ein interdisziplinäres Untersuchungsfeld der Informatik und Statistik gebildet: Data Mining nutzt eine Vielzahl computergestützter Verfahren, um die Geheimnisse des Datenschatzes zu entschlüsseln. Besonders erfolgreich ist dabei die sogenannte Assoziationsanalyse, die sich zum Teil verblüffend einfache Prinzipien zunutze macht.

Was ist eine Assoziationsanalyse?

Die Assoziationsanalyse ist eine Data Mining Methode zur Identifikation von Zusammenhängen zwischen Objekten innerhalb einer Datenbasis. Anhand von Häufigkeiten lässt sich damit feststellen, ob zu einer bestimmten Wahrscheinlichkeit verschiedene Kombinationen auftreten. Ziel ist letztlich das Aufstellen von Assoziationsregeln, die sich typischerweise durch simple Wenn-Dann-Sätze ausdrücken lassen (X → Y). Andere Verfahren wie die Abweichungsanalyse beschäftigen sich hingegen eher mit numerischen Eigenschaften und Soll-Werten. 

Die Assoziationsanalyse lässt sich durch verschiedene Algorithmen zu großen Teilen automatisieren. Da somit eine computergesteuerte Datenanalyse mit daraus abgeleiteten Entscheidungen bzw. Prognosen stattfindet, handelt es sich dabei um Machine Learning im klassischen Sinne. Ihren Ursprung hat die Technik in der Warenkorbanalyse, die Zusammenhänge zwischen Kaufentscheidungen untersucht. Das ist bis heute der gängigste Anwendungsfall und soll hier vermehrt als Beispiel dienen. Allerdings wurde das Prinzip inzwischen auch auf andere Datenstrukturen ausgeweitet.

Wichtige Grundbegriffe

Zunächst gilt es einige Grundbegriffe und Kennzahlen zu definieren. Deren mathematisch-logische Verknüpfung bildet schließlich den eigentlichen Vorgang der Assoziationsanalyse.

Items: Das sind die Objekte der Grundgesamtheit, zwischen denen die Assoziationsanalyse Beziehungen untersucht. Geht es um die Artikel eines Supermarktes, betrifft das in vielen Fällen über 10.000 Einheiten. Bei E-Commerce-Anbietern wie Amazon wird die Warenkorbanalyse mit einigen Hundert Millionen Produkten hingegen schnell zum Big Data Projekt.

Item Set: Damit ist eine Kombination aus Items gemeint – in der Regel, um auszudrücken, dass diese mit einer bestimmten Häufigkeit gemeinsam aufgetaucht sind bzw. gekauft wurden (z. B. {Milch, Brot, Butter}). Die Frequenz des Sets bestimmt mit, ob daraus eine Assoziationsregel abgeleitet werden kann.

Support: Aussagekräftiger als die absolute Häufigkeit ist deren Verhältnis zu allen Transaktionen, also die relative Häufigkeit. Für die binäre Entscheidung, ob ein Item Set als häufig betrachtet wird, kann ein entsprechender Schwellenwert des minimalen Supports gesetzt werden.

Konfidenz: Diese Kennzahl entspricht der relativen Häufigkeit, dass verschiedene Item Sets gemeinsam auftreten bzw. sich in einer Transaktion wiederfinden. Um die Konfidenz zu errechnen, teilt man bei der Assoziationsanalyse die Häufigkeit des Sets (bzw. dessen Support) durch die Häufigkeit eines einzelnen Items. Daraus ergeben sich Werte bis maximal 1 – in diesem Fall gäbe es ausschließlich gemeinsame Transaktionen.

Lift: Nicht jede Assoziationsregel hat einen hohen Informationsgehalt. Um diesen zu abzubilden, teilt man die Konfidenz einer Regel durch einen erwarteten Konfidenzwert. Daraus entsteht eine Metrik, die angibt, ob eine datenbasierte Erkenntnis von besonderer Relevanz ist. Ein Lift von 1 bedeutet, dass die Regel der statistischen Erwartung entspricht. Je weiter der Lift darüber hinausgeht, desto bedeutsamer ist der festgestellte Zusammenhang.

Assoziationsregeln herleiten

Alle dargestellten Kennzahlen dienen letztlich der Herleitung aussagekräftiger Assoziationsregeln. Diese haben die typische Form X → Y(Support, Konfidenz) und geben damit die Wahrscheinlichkeit an, dass zu Artikel X auch Artikel Y hinzu kommt. Sprachlich lässt sich das in Hypothesen à la “Wenn (Prämisse)… dann (Konsequenz)” ausdrücken. Um dieses Ziel der Assoziationsanalyse zu erreichen, sind einige Arbeitsschritte notwendig, denen ein strukturierter Datensatz aus Item Sets zugrunde liegt.

Beispiel

Aus Transaktionen in einem Supermarkt hat sich folgende Liste an Warenkörben ergeben:

Bereits eine simple Häufigkeitszählung ergibt, dass z. B. das Item Set {Brot, Milch} recht häufig erscheint, nämlich in drei von fünf Transaktionen. Als minimaler Support gilt Smin=50%.

Der Support von {Brot, Milch} S = ⅗ = 60% > 50%. Es liegt also tatsächlich eine für die Untersuchung interessante Häufigkeit vor. Daher gehen wir von der Regel Brot → Milch (60%, C%) aus. Die Konfidenz C ist noch unbekannt.

Das wollen wir ändern und teilen den Support von {Brot, Milch} durch den Support von {Bread}: C = 60% / 80% = 75%. Die vollständige Assoziationsregel lautet damit Brot → Milch (60%, 75%). Das wirkt überzeugend, schließlich gehen demnach drei Viertel der Brotkäufe auch mit Milch einher.

Um Maßnahmen zur Umsatzsteigerung zu ergreifen, wollen die Betreiber des Supermarkts nur die aussagekräftigsten Regeln berücksichtigen. Die Artikel Brot und Milch sah man schon häufiger gemeinsam über das Kassenband wandern und unterstellte eine Konfidenz von 60%. Daraus ergibt sich ein Lift L = 75% / 60% = 1,25 > 1. Zeit, das Brotregal in Richtung Milch zu verschieben.

Drei gängige Algorithmen

Die realen Anwendungsfälle sind natürlich um einiges komplexer und wohl kaum durch derart händische Rechnungen lösbar. Darum lässt man die Assoziationsanalyse in der Regel von entsprechenden Algorithmen erledigen. So sind bedeutend größere Datenmengen analysierbar, ganz zu schweigen von Zusammenhängen zwischen umfangreichen Item Sets.

Apriori

Der Apriori-Algorithmus ist einer der ersten dieser Art und findet auch heute noch häufig Anwendung. Dazu trägt besonders die einfache Handhabung und Implementierung bei. Notwendige Eingaben sind neben der Datenbasis lediglich der minimale Support und die minimale Konfidenz. Entsprechend der beschriebenen Vorgehensweise identifiziert das Programm in den Daten alle häufigen Item Sets und filtert zum Input passende Regeln heraus. Besonderheit ist hier die Berücksichtigung des sogenannten Apriori-Prinzips. Dieses besagt, dass häufige Item Sets ausschließlich häufige Items beinhalten. Ist das nicht der Fall, erfolgt eine Bereinigung durch sogenanntes Pruning, was die Auswahlqualität optimiert.

FP-Growth

Als Weiterentwicklung von Apriori ist FP-Growth in der Lage, sich den rasant wachsenden Datenmengen zu stellen und erhöht dabei Skalierbarkeit und Geschwindigkeit. Nebeneffekt ist allerdings eine kompliziertere Anwendung. Zur Strukturierung der ursprünglichen Item Sets dient ein sogenannter Frequent Pattern Tree, dessen Verbindungsknoten jeweils ein Item abbilden. Diese Komprimierung bietet Vorteile bei der Datenerfassung und -speicherung, die mit Apriori unzählige Scan-Durchläufe erfordern würde. Die übereinstimmenden Item Sets von Transaktionen erhalten als Zweige des Baums jeweils ein gemeinsames Präfix mit der Wurzel. Das hilft dem Algorithmus, letztlich alle Frequent Patterns herauszufiltern.

ECLAT

Equivalence Class Clustering and Bottom-Up Lattice Traversal ist ein weiterer moderner Algorithmus, der FP-Growth in nichts nachsteht. Er analysiert ebenfalls ein eigenständig generiertes Data Set, anstatt die ursprünglichen Daten wiederholt zu scannen. Dabei ist ein vertikales Format notwendig, das heißt tabellarisch wären links die Artikel untereinander aufgeführt und rechts die jeweiligen Transaktionen zugewiesen. Diese sogenannten Tidsets werden von ECLAT analysiert, um Item-Paare mit wiederum neuen, übereinstimmenden Tidsets zu bilden. Je mehr gemeinsame Transaktionen diese jeweils umfassen, desto wahrscheinlicher ist ein Zusammenhang zwischen den Items.

Anwendungsgebiete

Der häufigste Use Case des Verfahrens dürfte an diesem Punkt wohl kaum überraschen: Im gesamten Handel werden Assoziationsregeln zur Warenkorbanalyse eingesetzt, um damit Kaufentscheidungen zu erleichtern und Umsätze durch Cross-Selling zu steigern. Das ist allerdings längst nicht der einzige Nutzen von regelbasiertem Data Mining. Folgende Anwendungsgebiete profitieren besonders von der Assoziationsanalyse:

Medizin

Oftmals ist zunächst nicht genau bekannt, welche Merkmale Risikofaktoren oder Hinweise auf eine bestimmte Krankheit sein können. Mit Hilfe von Assoziationsregeln auf Basis von Gesundheitsdaten können Diagnostik und Prävention erleichtert werden. Unter Anwendung der dargestellten Algorithmen in Verbindung mit Natural Language Processing konnten indische Forscherinnen beispielhaft aufzeigen, wie sich solche Zusammenhänge extrahieren lassen.

UX-Design

Die User Experience ist ein zentraler Aspekt von Websites und anderen digitalen Produkten. Ziel ist es, die Anwendung und Navigation möglichst angenehm und einfach zu gestalten, sodass Nutzer genau das finden, was sie suchen. Das lässt sich durch Assoziationsanalyse auf Basis historischer Nutzungsdaten erleichtern, indem z. B. Buttons und Verlinkungen angepasst werden. Was nützt schließlich eine Warenkorbanalyse, wenn der Weg zum Online-Shop zu kompliziert ausfällt?

Lagermanagement

In großen Lagerhallen spielt die Position der Artikel eine entscheidende Rolle für die Effizienz des Unternehmens. Umfangreiche Bestellungen sollten am besten möglichst schnell abgefertigt werden, Gleiches gilt für hochfrequent angeforderte Waren und häufige Reihenfolgen. Apriori und ähnliche Algorithmen können maßgeblich dazu beitragen, die dafür notwendigen Wegstrecken zu minimieren.

Data Mining intelligent unterstützen mit Konfuzio

Die Vielseitigkeit der Anwendungsmöglichkeiten verdeutlicht, dass fast jedes Unternehmen ab einer gewissen Größe von Data Mining profitieren kann. Methoden wie die Assoziationsanalyse erfordern allerdings zunächst eine Datenbasis von hoher Strukturiertheit und Qualität. Die Ausgangslage ist oft eine andere: Bild- und Textdateien, E-Mails, PDFs etc. prägen viele Prozesse. Darum unterstützt die KI-Plattform Konfuzio Unternehmen bei allen notwendigen Schritten bis zu effektivem Erkenntnisgewinn.

1. Daten extrahieren und strukturieren

Mit allen genannten Formaten weiß Konfuzio durch unterschiedliche technische Ansätze umzugehen. Das umfasst Texterkennung, Bildverarbeitung, eine Low-Code-Integration zur E-Mail-Extraktion und mehr. Enthaltene Daten werden zielsicher extrahiert, bereinigt und in strukturierten Dateien aufbereitet. So entsteht eine wertvolle Basis für Data Mining.

2. Datenanalyse und -verarbeitung

Anschließend erlaubt Konfuzio eine hochgradig automatisierte Analyse der gewonnenen Daten, indem Konzepte von künstlicher Intelligenz und Data Mining zum Einsatz kommen. Dafür stehen diverse integrierte Modelle und Algorithmen zur Verfügung. Ebenso lassen sich die extrahierten Informationen aber auch in externe Tools migrieren, um hoch-individuelle (Assoziations-)Analysen durchzuführen.

Fazit

Mithilfe einer Assoziationsanalyse lassen sich auf einfachem Weg Zusammenhänge zwischen Objekten, Items oder Artikeln feststellen. Maßgeblich ist dafür vor allem die Häufigkeit, in der verschiedene Kombinationen auftreten. Das Data Mining Verfahren ist damit besonders gut für die Untersuchung von Einkäufen im Rahmen einer Warenkorbanalyse geeignet. Häufig angewandte Algorithmen sind Apriori, FP-Growth und ECLAT, die auch für diverse andere Anwendungsfälle auf Basis strukturierter Daten zum Einsatz kommen. Das schafft Erkenntnisse, die eine nachhaltige Ressourcenschonung oder Umsatzsteigerung begünstigen.

Möchten Sie mehr über Data Mining, den Nutzen dieser Verfahren für Unternehmen und wie Konfuzio Sie auf diesem Weg begleiten kann, erfahren? Schreiben Sie uns eine Nachricht.