Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | sonje-laudon |
View: | 109 times |
Download: | 0 times |
Berechnung von Association Rules
Vortrag inData Warehouse und Mining
Association Rules 2
Inhalt
Einleitung: Entstehung, NomenklaturApriori: grundlegender AlgorithmusHierarchische ItemsMengenwertige ItemsAusblick
Association Rules 3
Einleitung
Entstehung grössere Datenbestände genauere Datenbestände bessere Hardware-Resourcen
Wunsch auf Erkennung von interessanten Regeln in diesen grossen Datenbeständen
EinleitungApriori
HierarchieQuantität
Association Rules 4
Nomenklatur
Transaktion: Aktion auf Datenbank (Einkauf,...)
Item: Teil einer Transaktion (Milch,...) Itemset: Menge von Items Association Rule: X Y (wenn Transaktion X
enthält, dann enthält sie auch Y) Confidence c: c % der Transaktionen befolgen die
Association Rules (minconf: untere Schranke für Algorithmus)
Support s: s % der Transaktionen enthalten X und Y (minsup: untere Schranke für Algorithmus)
EinleitungApriori
HierarchieQuantität
Association Rules 5
Beispiel
T1 {Zahnpasta, Schokolade, Milch}T2 {Schokolade, Milch}T3 {Brot, Käse}T4 {Zahnpasta, Milch, Käse}T5 {Milch, Brot, Käse}
Confidence SupportBrot Käse 100% 40%Käse Milch 66.6% 40%Zahnpasta Schokolade 50% 20%
EinleitungApriori
HierarchieQuantität
Association Rules 6
Motivation
Wunsch auf maschinelles Erkennen dieser Association Rules: Algorithmus ‚Apriori‘
Manche Items besitzen grundlegende Abhängigkeit, hierarchische Abstammung (Milch Vollmilch)
Gewisse Association Rules brauchen mengenwertige Items (2 Autos 2 Kinder über 18)
EinleitungApriori
HierarchieQuantität
Association Rules 7
Algorithmus Apriori
Entdecken von Association Rules in zwei Probleme unterteilbar. Finden aller Itemsets mit minimalem
Support Benutzung dieser Itemsets zum
Ermitteln der Association Rules
EinleitungApriori
HierarchieQuantität
Association Rules 8
Itemsets finden
Finden aller Itemsets mit minimalen Support Beginn mit einelementigen Sets (1-sets)
-> einfaches „Zählen“ Vereinigen der ermittelten (k-1)-Sets zu
neuen k-Sets Join-Step: Herstellung der KandidatenPrune-Step: Löschen aller Kandidaten, die
eine „falsche“ Untermenge besitzen
EinleitungApriori
HierarchieQuantität
Association Rules 9
Beispiel: Itemsets
Beispiel:
{1 2 3}
{1 2 4}
{1 3 4}
{1 3 5}
{2 3 4}
{1 2 3 4}{1 3 4 5}
Join
3-sets Kandidaten für 4-sets
{1 2 3 4}
4-setsPrune
EinleitungApriori
HierarchieQuantität
Association Rules 10
Generierung
Generierung der Association Rules
Untersuchung aller Subsets a eines Itemsets I
a (I - a), wenn
EinleitungApriori
HierarchieQuantität
Support(I)Support(a)>= minconf
Association Rules 11
minconf=75%
Beispiel: Generierung
I={2,3,4} [40%] Subsets:{2,3} {2,4} {3,4} {2} {3} {4}
50% 70% 60% 80% 50% 70%
{2,3} {4}Support(I) = 40%Support(a)= 50% Confidence = 80 % OK!
{2} {3,4}Support(I) = 40%Support(a) = 80% Confidence = 50 % NO!
EinleitungApriori
HierarchieQuantität
Association Rules 12
Einleitung
Bisher:Milch Brot [80%]
wäre viel informativer, wennDiätmilch Weissbrot [75%]
Wunsch auf Hierarchie
EinleitungApriori
HierarchieQuantität
Association Rules 13
Beispiel
Esswaren
Milch Brot ...
Diät ... Voll Weiss Vollkorn ...
Je tiefer ein Item in der Hierarchie ist, umso kleiner sollte der geforderte Support sein
EinleitungApriori
HierarchieQuantität
Association Rules 14
Codierung
Erweiterung von Apriori: Codierung der verschiedenen Produkte
Milch 1 Diätmilch 11Vollmilch 12
Brot 2 Weissbrot 21Vollkornbrot 22
T1: {11,21,22,32}T2: {21,22,31}...
Transaktionstabelle:
EinleitungApriori
HierarchieQuantität
Association Rules 15
Erste Itemsets
Zuerst auf oberster Stufe Suche der Itemsets:
Berechnung der Association Rules und Filterung der Transaktions-Tabelle
{1*} 30%{2*} 40%
{1*,2*} 30%
T1: {11,21,22}T2: {21,22}
EinleitungApriori
HierarchieQuantität
Association Rules 16
Iteration
Iteration: Suche der nächsten Itemsets auf gefilterter Tabelle (bis Tabelle leer oder am Ende der Hierarchie)
Berechnung der Association Rules und Filterung der Transaktions-Tabelle
{11} 20%{21} 30%{22} 30%
{11,21} 20%{11,22} 20%
EinleitungApriori
HierarchieQuantität
Association Rules 17
Einleitung
Bisher: nur „binäre“ Association Rulesz.B. Brot Milch
Ausweitung auf „quantitative“ Association Rules, z.B. {Alter:30..39, verheiratet=ja} {Autos:
2} {Autos: 0..1} {verheiratet=nein}
EinleitungApriori
HierarchieQuantität
Association Rules 18
Probleme
Triviale Umwandlung von Wertemenge auf binäre Tabelle, ABER: Itemanzahl
explodiert(Ausführungszeit!)
Anzahl der Regeln explodiert
ID Alter Verh. Autos
100 23 Nein 1
200 25 Ja 1
300 29 Nein 0
400 34 Ja 2
500 38 Ja 2
EinleitungApriori
HierarchieQuantität
Association Rules 19
Intervalle
Modifizierter Algorithmus:
Für jedes Mengenattribut wird ein Intervall ausgewählt
ID Alter Verh. Autos
100 20..24 Nein 1
200 25..29 Ja 1
300 25..29 Nein 0
400 30..34 Ja 2
500 35..39 Ja 2
EinleitungApriori
HierarchieQuantität
Association Rules 20
Intervalle wählen
Problem bei der Intervallwahl: viel zu viele Kombinationen von
Intervallen
Einführung der Partial Completeness:Mass für den Informationsverlust bei einer Generalisierung eines Intervalls
EinleitungApriori
HierarchieQuantität
Association Rules 21
Partial Completeness
k-Partial-Completeness: Für die Generalisierung eines Itemsets
darf der Support nicht um mehr als Faktor k zunehmen
EinleitungApriori
HierarchieQuantität
<Alter 20..30> 5%<Alter 20..40> 6%<Alter 20..50> 8%<Autos 1..2> 5%<Autos 1..3> 6%
<Alter 20..40> 6%<Alter 20..50> 8%<Autos 1..3> 6%
1.5-Partial-Complete:
Association Rules 22
Verringerung der AR
Streichung der „erwarteten“ Association Rules
{Alter:20..30} 12x{Alter:20..25} 3x
{Alter:20..30} -> {Autos:1..2}8% Support, 70% Confidence
{Alter:20..25} -> {Autos:1..2}2% Support, 70% Confidence
Streichbar, da keine neueErkenntnis
EinleitungApriori
HierarchieQuantität
Association Rules 23
Ausblick
Algorithmus ‚Apriori‘:optimierte Versionen mit schnellerer Laufzeit oder mit geringerem Speicherbedarf
hierarchische Items:nicht nur Association Rules in der gleichen Ebene finden, sondern auch über verschiedene Ebenen
AprioriHierarchieQuantitätAusblick