Download - Fachgebiet Datenbanken und Informationssysteme

2.6 Data Mining
menhänge zulassen. Die Assoziationsanalyse [AMS+ 96] ist eine Data Mining-Methode mit der diese interessanten und signifikanten Abhängigkeiten (Assoziationen) in den Daten entdeckt werden
können. Als typisches Beispiel der Assoziationsanalyse ist die Warenkorbanalyse, die im Beispiel
angedeutet ist und die Untersuchung des Kundenverhaltens in Bezug auf die gekauften Artikel
beschreibt, zu nennen.
Die Assoziationsanalyse ist eine deskriptive Data Mining-Methode, mit dessen Hilfe Muster mit
einfacher Struktur in den Daten gefunden werden können und immer dann Anwendung findet,
wenn die Maxime gilt: „If you don’t know what you are looking for, use association analysis.“
Bei dem Prozess der Assoziationsanalyse werden interessante Assoziationen oder Korrelationen
zwischen Daten gefunden, die in Association Rules (Assoziationsregeln) ausgedrückt werden. Eine
Assoziationsregel ist eine Implikation A ⇒ B (d. h. aus A folgt B), z. B. die Assoziation zwischen
den Produkten Brot und Erdnuss-Butter wird als Brot ⇒ Erdnuss-Butter dargestellt, die besagt,
dass wenn der Artikel Brot gekauft wird, dann wird auch der Artikel Erdnuss-Butter gekauft.
Assoziationsregel: Brot ⇒ Erdnuss-Butter
Was zeichnet jedoch eine Assoziation gegenüber anderen Assoziationen aus, sind alle gleich interessant oder sind einige interessanter? Aus diesem Grund muss eine Assoziation in irgendeiner
Weise bewertet werden, um die Relevanz oder Wichtigkeit einstufen zu können. Diese Bewertung
beruht zum einen auf der Häufigkeit (auch Support genannt), z. B. in 10% der Fälle wurden Brot
und Erdnuss-Butter zusammen gekauft, und zum anderen auf dem Vertrauen einer Assoziation
(auch Confidence genannt), d. h. wie häufig trifft die Assoziation zu, z. B. in 70% der Fälle, in denen Brot gekauft wurde, wurde ebenfalls Erdnuss-Butter gekauft. Die Assoziationsregel Brot ⇒
Erdnuss-Butter lässt sich mit den Zusatzinformationen über die Relevanz beziehungsweise Wichtigkeit folgendermaßen schreiben:
Assoziationsregel: Brot ⇒ Erdnuss-Butter [Support=10%, Confidence=70%]
Die Assoziationsanalyse, die eine Data Mining-Methode für die Analyse von Abhängigkeiten in
den Daten beschreibt, lässt sich formal wie folgt definieren:
Definition (Assoziationsanalyse): Sei I eine Menge von Objekten (häufig Items genannt) und
T eine Menge von Transaktionen, wobei gilt: ∀t ∈ T : t ⊆ I. Sei weiterhin s ∈ [0%, 100%] ein
Support und smin ∈ [0%, 100%] ein benutzerdefinierter Minimal-Support, und c ∈ [0%, 100%]
eine Confidence und cmin ∈ [0%, 100%] eine benutzerdefinierte Minimal-Confidence. Bei der
Assoziationsanalyse sind alle Assoziationsregeln zu finden, die folgende Bedingungen erfüllen:
1. Form: A ⇒ B mit A ⊆ I und B ⊆ I, und A ∩ B = ∅
∪ B⊆t}|
2. Support: s( A ⇒ B) = |{t∈T:A
≥ smin
|T |
3. Confidence: c( A ⇒ B) =
s( A⇒ B)
s( A)
=
|{t∈ T:A∪ B⊆t}|
|{t∈ T:A∈t}|
≥ cmin
Die oben definierten Bedingungen drücken aus, wann eine Assoziationsregel gültig und interessant
ist. Die erste Bedingung gibt lediglich die Form vor, in der eine Assoziationsregeln dargestellt wird.
Die zweite Bedingung gibt an, dass eine gewisse Minimalhäufigkeit für die in der Assoziationsregel vorkommenden Objekte gegeben sein muss, d. h. es sind nur Assoziationsregeln interessant,
die eine bestimmte Relevanz, ausgedrückt durch die Häufigkeit des Auftretens, aufweisen können.
Schlussendlich gibt die dritte Bedingung an, dass Objekte mit einer bestimmten Häufigkeit zusammen auftreten müssen, d. h. Transaktionen t ∈ T, die die Prämisse A enthalten, müssen mindestens
einen Anteil von cmin in der Konklusion B beinhalten.
Eine Assoziationsregel, die einen Minimal-Support s ≥ smin und eine Minimal-Confidence c ≥ cmin
erfüllt, wird Strong Association Rule (starke Assoziationsregel) genannt. Die starken Assoziationsregeln sind häufig diejenigen, die später an den Benutzer weitergegeben werden, da ansonsten die
23