Data Mining

Beim Data Mining geht es darum, große Datenmengen nach (bisher unbekannten) Zusammenhängen zu durchsuchen. Man unterscheidet zwei Zielsetzungen bei der Auswertung der Suche:

• Klassifikation von Objekten,
• Finden von Assoziationsregeln.

Klassifikation zur Risikoabschätzung bei einer KFZ-Versicherung

Beobachtete Schadensfälle

Entscheidungsbaum

Bei der Klassifikation von Objekten (z. B: Menschen, Aktienkursen, etc.) geht es darum, Vorhersagen über das zukünftige Verhalten auf Basis bekannter Attributwerte zu machen. Abbildung 17.7 zeigt ein Beispiel aus der Versicherungswirtschaft. Für die Risikoabschätzung könnte man beispielsweise vermuten, daß Männer zwischen 35 und 50 Jahren, die ein Coupé fahren, in eine hohe Risikogruppe gehören. Diese Klassifikation wird dann anhand einer repräsentativen Datenmenge verifiziert. Die Wahl der Attribute für die Klassifikation erfolgt benutzergesteuert oder auch automatisch durch ``Ausprobieren``.

Bei der Suche nach Assoziativregeln geht es darum, Zusammenhänge bestimmter Objekte durch Implikationsregeln auszudrücken, die vom Benutzer vorgeschlagen oder vom System generiert werden. Zum Beispiel könnte eine Regel beim Kaufverhalten von Kunden folgende (informelle) Struktur haben:

Wenn jemand einen PC kauft
dann kauft er auch einen Drucker.

Bei der Verifizierung solcher Regeln wird keine 100 %-ige Einhaltung erwartet. Stattdessen geht es um zwei Kenngrößen:

• Confidence: Dieser Wert legt fest, bei welchem Prozentsatz der Datenmenge, bei der die Voraussetzung (linke Seite) erfüllt ist, die Regel (rechte Seite) auch erfüllt ist. Eine Confidence von 80% sagt aus, daß vier Fünftel der Leute, die einen PC gekauft haben, auch einen Drucker dazu genommen haben.
• Support: Dieser Wert legt fest, wieviel Datensätze überhaupt gefunden wurden, um die Gültigkeit der Regel zu verifizieren. Bei einem Support von 1% wäre also jeder Hundertste Verkauf ein PC zusammen mit einem Drucker.

TransID	Produkt
111	Drucker
111	Papier
111	PC
111	Toner
222	PC
222	Scanner
333	Drucker
333	Papier
333	Toner
444	Drucker
444	PC
555	Drucker
555	Papier
555	PC
555	Scanner
555	Toner

Frequent Itemset-Kandidat	Anzahl
{Drucker}	4
{Papier}	3
{PC}	4
{Toner}	2
{Toner}	3
{Drucker, Papier}	3
{Drucker, PC}	3
{Drucker, Scanner}
{Drucker, Toner}	3
{Papier, PC}	2
{Papier, Scanner}
{Papier, Toner}	3
{PC, Scanner}
{PC, Toner}	2
{Scanner, Toner}
{Drucker, Papier, PC}
{Drucker, Papier, Toner}	3
{Drucker, PC, Toner}
{Papier, PC, Toner}

Verkaufstransaktionen (links) und Zwischenergebnisse des A-Priori-Algorithmus (rechts)

Zur Ermittlung der Assoziationsregeln verwendet man den A-Priori-Algorithmus, welcher sogenannte frequent itemsets berechnet, also Produktgruppen, die häufig gemeinsam gekauft wurden. Tabelle 17.1 zeigt den Verlauf des Algorithmus, der aus den beobachteten Verkäufen sukzessive alle Frequent Itemsets mit mindestens 3 Items ermittelt. Aus der TransaktionsID lässt sich zunächst ermitteln, welche Produkte gemeinsam gekauft wurden. Danach werden die Frequent Itemsets der Mächtigkeit $k$ erweitert zu Frequent Itemsets der Mächtigkeit $k+1$. Zum Schluss bleibt die Kombination {Drucker, Papier, Toner } als einzige Dreier-Kombination übrig.

Sei $F$ ein Frequent Itemset. Dann gilt

$$support(F) := \frac{Anzahl~des~Vorkommens}{Gesamtzahl}$$

.

Wir betrachten alle disjunkten Zerlegungen von $F$ in $L$ und $R$.

Die Regel $L \Rightarrow R$ hat dann folgende Confidence

$$confidence(L \Rightarrow R) = \frac{support(F)}{support(R)}$$

Beispiel: Die Regel {Drucker} $\Rightarrow$ {Papier, Toner} hat

$$confidence = \frac{support(\{Drucker, Papier, Toner\})}{support(\{Drucker\})} = \frac{3/5}{4/5} = 0.75$$

Also haben 75 % der Kunden, die einen Drucker gekauft haben, auch Papier und Toner gekauft.