# Data Mining
###### tags: `5. Data Mining - Lösungsansätze`

**Klausur WiSe 2018/19**
### 5 Data Mining (8 Punkte)
Sie sind Data Mining-Experte und erhalten von einem Online-Shop für trendige Bekleidung (Frauen,Männer) zwei Dateien. Die eine Datei enthält Datensätze mit detaillierten Informationen zu einzelnen Kunden (Kunden-ID, Alter, Einkommen, Geschlecht, Wohnort, Geburtsort- und Land, Beziehungsstatus, Facebook-Profil (ja/nein), Instagram-Profil (ja/nein)). Die zweite Datei enthält alle Verkaufsvorgänge zu den einzelnen Kunden (Kunden-ID, Bestell-ID, Produkt-ID, Produkt-Menge, Kaufzeitpunkt (Tag der Bestellung), Referrer-ID). **Das Unternehmen ist daran interessiert, ob es interessante Untergruppen in Ihrem Kundenstamm auch bzgl. der gekauften Produkte gibt.**
- Bitte beschreiben Sie, welchen Data Mining-Aufgabentyp und welches Verfahren Sie für diese Fragestellung einsetzen würden.

- Theoretisch gibt es hier kein Falsch : mögliche Ansätze sind
1. Klassifikation/Regression
- Entscheidungsbaum
- Regressionsanalyse
- Neuronale Netze
2. Segmentierung
- Neuronale Netze
- Clusterverfahren
3. Abweichungs/Änderungsanalyse (kommt nicht vor in weil Unterlagen nicht vorhanden)
- Neuronale Netze
- Statistische Verfahren
4. Abhängigkeitsanalyse
- Sequenzmuster
- Assoziationsregeln
- Begründen Sie Ihre Auswahl.
- Clusteringverfahren, wenn Cluster vorhanden sein unklar ist
- Entscheidungsbaum, wenn Vorhersage statt finden soll zu etwas einzuschätzen, wie z.b. Risiko-> gering oder hoch

- Erläutern Sie in Ihrer Begründung auch, welche Informationen Sie aus dem beiden Dateien in Ihrem Verfahren verwenden würden.
- Wie würde ein mögliches Ergebnis aussehen bei der von Ihnen gewählten Vorgehensweise?
(8 Pkt.)
### Lösungsansatz
- Im Bereich der Segmentierung würde ich mich für den DM-Aufgabentyp Clustering entscheiden. Das würde ich deshalb machen, da ich nicht weiß, ob, und wieviele Cluster es gibt.
- Nutzen würde ich alle Datensätze aus der Kundentabelle (bis auf KundenID) und aus der 2. Datei alle Datensätze, welche mir die Produkte und deren Anzahl sowie deren KaufZeitpunkt gibt. Ziel dabei wäre es, evtl sogar ein Cluster aufzubauen, welcher feststellt, in welchem Zeitraum was am meisten gekauft wurde. Genauso kann festgestellt werden, welches Kundenattribut überhaupt eine Wichtigkeit bildet zu gewissen Artikeln (daher alle KundenInformationen berücksichtigen). Ein mögliches Ergebnis könnte z.b. sein, das es eine Untergruppe Frauen gibt, die hauptsächlich Kleider kaufen, und kaum/keine Männer, die Kleider kaufen. Genauso könnte festgestellt werden, dass alle Instagram-Besitzer die trendigste Saisonware kaufen, um es dort zu präsentieren.

Überblick -> vorhandene Dateninformationen
| Datei 1 - Datensätze | Datei 2 - Verkaufsvorgänge |
| -------------------- |:--------------------------------- |
| Kunden-ID | Kunden-ID |
| Alter | Bestell-ID |
| Einkommen | Produkt-ID |
| Geschlecht | Produkt-Menge |
| Geburtsort | Kaufzeitpunkt(Tag der Bestellung) |
| Geburtsland | Referrer-ID |
| Beziehungsstatus | |
| Facebook-ProfilText | |
| Instagaram-Profil | |

Vorlesung 10, ab Seite 15 werden unterschiedliche Verfahren beschrieben

Man unterscheidet 4 Aufgabentypen im Bereich des Data Mining (mit ihren jeweiligen Verfahren):
1. Klassifikation/Regression
- Entscheidungsbaum
- Regressionsanalyse
- Neuronale Netze
2. Segmentierung
- Neuronale Netze
- Clusterverfahren
3. Abweichungs/Änderungsanalyse
- Neuronale Netze
- Statistische Verfahren
4. Abhängigkeitsanalyse
- Sequenzmuster
- Assoziationsregeln

### zu 1.) Klassifikation
ist eine *Abbildung* die die Zuordnung zu *vorgegebenen Klassen* beschreibt
Grundlage bildet Datenbestand, dessen Datenobjekte in vorgegebenen Klassen zugeordnet sind -> Verfahren des überwachtes Lernens
zugeordnetes Verfahren:
#### Entscheidungsbaum
**Vorgehen: Aufbau eines Baums**
- Knoten entspricht Entscheidungskriterium
- Blatt entspricht Entscheidung

**Vorteile:**
- Ergebnis leicht interpretierbar
- übersetzbar in Regelsystem

#### Entscheidung welches Splitattribut via **GINI-Index**
1-p(A)^2^-p(B)^2^
minimum = 0 --> alle Objekte aus einer Klasse = Maximale Homogenität
maximum = 0,5 --> Objekte 2er Klassen gleich häufig = Maximale Heterogenität

**Split Geschlecht: 1-p(G)^2^-p(H)^2^**
W|M: GGGGGGG | HHHHGH
**Gini Index**
W: 1-(7/7)^2^-(0/7)^2^ = 1 - 1 = 0,0
M: 1-(1/6)^2^-(5/6)^2^ = 5/18 = 0,2778
Mittelwert = 7/13 * 0,0 + 6/13*0,2778
= 0 + 0,128 = **0,128**

**Split Autotyp 1-p(G)^2^-p(H)^2^**
Van|Coupe: GGGHHG|GHGGHHG
**Gini Index**
Van: 1-(4/6)^2^-(2/6)^2^ = 4/9 = 0,444
Coupe: 1- (4/7)^2^-(3/7)^2^ = 24/49 = 0,49
Mittelwert = 6/13*0,444 + 7/13*0,49 = 128/273 **= 0,469**

**Split Alter nicht gut** :S man müsste frage Stellen wie "<40 bzw 39?" um eine einfache Berechnung in 2 Parts zu haben(man kann auch jedes Alter für sich berechnen, aber das wäre dann eher sehr geringes Ergebnis, wäre ein Super Ergebnis, aber leider zu weit gestreut)
je nach wahl der Zahl verschiebt sich der Index, da Frauen dann mit eingeordnet werden, die immer gering sind

ZIEL IMMER KLEINEN INDEX FÜR MAXIMALE HOMOGENITÄT
Daher ist in diesem Beispiel Geschlecht das bessere Attribut (0,128<0,469)

#### zu 2.) Segmentierung - Clusterverfahren
Cluster sind Mengen von Datensätzen, wobei Daten innerhalb Cluster möglichst ähnlich (homogen) und Datensätze aus unterschdiedlichen Clustern möglichst unähnlich sind Bsp
Vorgehen
- partionierende Verfahren
versuchen, ausgehend von einer vorgegebenen Gruppeneinteilung, durch den iterativen Austausch der Datenobjekte zwischen den einzelnen Klassen die Gesamtlösung zu optimieren
Bsp k-Means
Vorgehen hier: zufällige Startpunkte.
Dann nimm von jedem Objekt die Distanz zu allen zufälligen Startpunkten und ordne jedem den am nächsten gelegenen Startpunkt zu. wenn alle zugeordnet, neue Clusterzentren Berechnen und das ganze von vorne. ändert sich die objektzuordnung zum vorherigem Durchgang nicht -> fertig
nachteile -> abhängig von Startpunkten, sehr anfällig für Ausreißer, dadurch bilden ausreißer schnell ein eigenen cluster

- agglomerativ-hierarchische Verfahren:
verfolgen einen Bottom-Up-Ansatz und gehen bei der Gruppierung von der kleinsten Partition aus. Jedes Datenobjekt repräsentiert zunächst einen Cluster und wird sukzessiv neuen, größeren Gruppen zugeteilt
- divisiv-hierarchische Verfahren:
starten mit der gröbsten Partition. Diesem Top-down-Ansatz zufolge befinden sich alle Datenobjekte zunächst in einem einzigen Cluster. Anschließend erfolgt die Aufspaltung der Datenobjekte in homogenere Teilgruppen.

### zu 3.) Abweichungs/Änderungsanalyse
keine weiteren Angaben in seinen Unterlagen

### zu 4.) Abhängigkeitsanalyse
Assoziationsregeln
Items können Elemente von Mengen oder einzelnen Attributwerten sein, eine Menge von Items wurd als ItemSet oder auch Itemmenge
Bsp Items = Artikel; ItemSet = Warenkorb(Artikel A, Artikel B)
Vorraussetzung, vorhanden sein einer Datenbasis besehend aus einzelnen Transaktionen (z.b. Menge an Kassenbons)
Ergebnis: Regeln der Form WENN Item x DANN Item y (x -> y)
Wenn Artikel a und b gekauft werden, dann wird auch c gekauft
{Milch, Windeln} -> {Bier}

**Metriken** zur Bewertung der Regeln **r = (x->y)**
**support s** Anteil der Datensätze (Itemsets) die sowohl X als auch Y enthalten im Verhältnis zu allen Datensätzen
**confidence c** Verhältnis der Datensätze für die r = (x->y) gilt im Verhältnis zu den Datensätzen, die den Tegelteil(x) enthalten
Bsp Für die Regel {milk, Diaper} -> Beer
s = 2/5 (nämlich set 3 und 4) = 0,4
c = 2/3 (nämlich set 3,4 aber nicht 5) = 0,666
Bewertung -> niedriger support : Spezailregel, geringe Aussagekraft
niedrige confidence: "Falsche" Regel

𝑳𝒊𝒇𝒕 = (𝒔𝒖𝒑𝒑 𝑿 ∪ 𝒀) / (𝒔𝒖𝒑𝒑 (𝑿) ∗ 𝒔𝒖𝒑𝒑(𝒀))

~~{milk, Diaper, Beer } / {milk, diapeer} * {beer} = {milk, Diaper, Beer } / {{milk, beer},{diaper,beer}}~~

X={Milk, Diaper}
Y={Beer}
X ∪ Y = {Milk, Diaper, Beer}

s(X ∪ Y)= 2/ 5 = 0,4
s(x)= 3/5 = 0,6
s(y)= 3/5 = 0,6
-> Lift = 0,4 / (0,6 * 0,6)
= 0,4/0,36
= 1,111111111 usw (1 1/9)
-> Wert über 1 = werden auffallend oft zusammengekauft
(1 = zufällig ob beides zusammengekauft wird)
(<1 = eher selten das die beiden Produkte zusammengekauft werden
)
**Übung**
Saft -> Cola
s = 4/6 = 0,6666666666 usw
c = 4/5 = 0,8
gute regel, mit viel aussagekraft(*c*) und betrifft eine Menge Transaktionen(s)

A-Priori-Algorithmus
Ziel: Komplette Liste aller Möglichkeiten von zusammen gekauften artikel und deren support/confidence
bei Zehn Artikel 10^23^ (2^10^-1) mögliche Kombinationen
Prinzip:
- wenn kombi von Artikel häufig vorkommt -> dannauch jede Teilmenge häufig
- wenn kombi selten, dann jede obermenge auch selten
Interpetierbarkeit -> riesige Regelmängen möglich, die auch irreführend sein können
60% spielen Fußbal, 75% essen Schokolade, 40% beides
r = fußball -> schokolade Konfidenz 67%
true -> isst schokolade Konfidenz 75%
Fußbal + schokoriegel negativ korreliert -> daher Regel hohe Konfidenz

### Lift Metrik
Lift gibt an, wie hoch der Konfidenzwert für die Regel den Erwartungswert übertrifft
- Sind Itemsets X und Y nicht korreliert, ist der Erwartungswert supp(X Y) = supp(X) * supp(Y)
- Ein einfaches Maß für die Abweichung von der zufällig erwarteten Häufigkeit ist dann (odds-score, Lift)
𝑳𝒊𝒇𝒕 = (𝒔𝒖𝒑𝒑 𝑿 ∪ 𝒀) / (𝒔𝒖𝒑𝒑 (𝑿) ∗ 𝒔𝒖𝒑𝒑(𝒀))

Interpretation:
- Lift() = 1: Häufigkeit ist per Zufall erwartet
- Lift() < 1: X und Y werden auffallend selten zusammen gekauft
- Lift() > 1: X und Y werden auffallend häufig zusammen gekauft

### Abweichungsanalyse Outlier Detection
Analyse zur Erkennung von Wertabweichung eines merkmals von zuvor gemesenen oder mormativen Werten und Erklärung der Abweichungen durch andere Attribute/Zusammenhänge

BSP DBSCAN -> Dichtverbundene Lusterverfahren erkennt gebiete mit hoher Datenpunktdichte als cluster und kann sehr gut rauschen umgehen

Dichte: die *epsilon*-Umgebung von p besteh aus allen Punkten, die höchstens *epsilon* zu p besitzt
Anzahl der Punkte in *epsilon*-Umgebung von p=dichte
Bestimmung von *epsilon* im vorfeld der Analyse von zentraler bedeutung

MinPts legt fest, wieviele Punkte in *epsilon*-Umgebung von einem punkt p liegen müssen, damit p zu einem cluster gehört

Kernpunkt: Anzahl mindestens minpts
randpunkt -> kein kernpunkt, aber in *epsilon*-Umgebung eines Kernpunktes (ist als dichte erreichbar)
Rauschpunkt -> alle anderen

*In eigenen Worten: Nimm ein beliebigen Punkt, der mindestens x weitere Punkte in seiner nähe hat. ist dies der fall, handelt es sich um ein Kernpunkt. von dem aus verbinde einfach alle punkte, die in seiner reichweite sind. hat der nachbar auch "genug" Punkte in der nähe -> ebenso kernpunkt. Hat ein Punkt zu wenige punkte, so handelt es sich um ein Randpunkt. Alles außerhalb von dem "cluster" ist rauschen, außer man stellt fest, das noch ein weiterer Kernpunkt vorhanden ist, dann dort ebenso verbinden, da weiteres cluster. Das solange wiederholen, bis alle Punkte zugeordnet sind in kern rand oder rauschpunkt

Vorgehen
1. Bennene Datenpunkte als Kern Rand oder Rauschpunkte
2. lösche alle rauschpunkte
3. verbinde Kernpunkte innerhalb einer *epsilon*-Kugel liegend durch kante
4. Menge verbundener Kernpunkte bilden seperates cluster
5. weise jeden randpunkt dem cluster eines benachbarten punktes zu

---
**Klausur SoSe 2019**
### 5 Data Mining (16 Punkte)
- a. Sie sind Data Mining-Experte und erhalten zwei Dateien von einem Händler für Outdoor-Bedarf mit 128 Filialen in Deutschland. Die eine Datei enthält Datensätze mit detaillierten Informationen zu einzelnen Kunden (Kunden-ID, Alter, Einkommen, Geschlecht, Wohnort, Geburtsort- und Land, Beziehungsstatus, bevorzugte Reiseart (Rucksack, Adventure, Extreme). Die zweite Datei enthält alle Verkaufsvorgänge zu den einzelnen Kunden (Kunden-ID, Kassenbon-ID, Produkt-Menge, Kaufzeitpunkt (Tag des Einkaufs), Filial-ID). **Das Unternehmen ist daran interessiert, seinen Kundenstamm in Gruppen einzuteilen, um für die Gruppen gezielte/ stärker personalisierte Werbemaßnahmen konzipieren zu können.**
Beschreiben Sie, welchen Data Mining-Aufgabentyp und welches Verfahren Sie für diese Fragestellung einsetzen würden. Begründen Sie Ihre Auswahl. Erläutern Sie in Ihrer Begründung auch, welche Informationen Sie aus dem beiden Dateien in Ihrem Verfahren verwenden würden. Wie würde ein mögliches Ergebnis aussehen bei der von Ihnen gewählten Vorgehensweise? (8 Pkt.)
- b. In einem früheren Data Mining-Projekt haben Sie einen Entscheidungsbaum erstellt, der ein Zielattribut mit den Ausprägungen TG und TH vorhersagen soll. Die Validierung anhand eines Test-Datensatzes ergibt folgende Confusion Matrix.
Berechnen Sie anhand dieser Matrix die Kennzahlen Accuracy, Precision und Recall. (6 Pkt.)
Bewerten Sie die Güte des Entscheidungsbaums (2 Pkt.).

| | True TG | True TH | Class Precision |
| ------------ | ------- | ------- | --------------- |
| Predicted TG | 590 | 120 | 83,1% |
| Predicted TH | 75 | 280 | 73,21% |
| Class Recall | 88,7% | 70,0% | |

Accuracy = (590+280) / ((590+280)+(120+75)) = 710/905 = 78,45%

Recall True TG -> 590:(590+75) = 88,7%
Recall True TH -> 280:(280+120) = 78,87%
Recall = wieviel % wurden vom Testdatensatz sind auch nach dem algorithmus richtig vorhergesagt -> also wiehäufig wurden die daten vom testdatensatz richtig recalled (sprich 590 von 665 wurden)

Precision 590:(590+120) -> 83,1%
Precision 280:(75+280) - 1 -> 73,2%
Precision = (richtig vorhergesagt RV)/(RV+Falsch vorhergesagt)
Wie häufig waren meine vorhersagen für ein Attribut richtig, also hier, insgesamt wurden 590 mal richtig TG vorhergesagt, aber auch 120 mal vorhergesagt, was falsch war, also war die precision 590/710 = 83,1

Ein Wert über 80% ist ein recht aussagekräftiger Wert.
- Im Bereich Recall für G zu 87,2% wiedergegeben wurde aus den Test-Datensatz,für H nur 57,2%, was bedeutet, das eine Menge Vorhersagen H bewertet wurden, obwohl sie es nicht waren.
- Im Bereich Class Precision wurden zu 79,66% G richtig vorhergesagt und im Bereich H zu 73,21%, was ein solider Wert ist.
- Bei einer Accuracy von 78,45% sagt, das wir allgemein einen recht soliden Aussagebaum haben mit Verbesserungsmöglichkeiten nach oben.

---
**Klausur Wintersemester 2019/20**
### 5 Data Mining (14 Punkte)
Bei einem Data Mining-Projekt in einer Bank wurde folgender Entscheidungsbaum erstellt. Die betrachteten Attribute der **Kunden** waren **Alter**, **Geschlecht (F, M)** sowie der **Beruf (Angestellter, Beamter).** Als Zielvariable wurde der bisherige Profit **(Low, High)** ausgewählt, den die Bank mit dem jeweiligen Kunden erzielt hat.


Der Projektleiter möchte jetzt gerne die **Güte des Entscheidungsbaums** bewerten. Hierzu stellt er Ihnen folgende Testdatensätze zur Verfügung.


a. Erstellen Sie die Confusion Matrix zu den obigen Testdatensätzen (6 Minunten).

### Lösungsansatz
VorabInfo:
Siehe Foliensatz 10 ab seite 28 Video ab 1h44
| | true High | true Low | class precision |
| ------------ | ----------------------------- | ----------------------------- | --------------- |
| pred High | beides stimmt / True Positive | pred falsch / False Positive | |
| pred Low | pred falsch / false Negative | beides stimmt / True Negative | |
| class recall | | | |

**precision:** Anteil korret als positiv klassifizierte Objekte an der Gesamtheit der als positiv klassifizierten Objekte
beides stimmt / (beides stimmt + die falschen)
oder auch anders wieviele von allen positiv ausgegeben sind das (Zeilenweise) = TP/(TP+FP)

**Recall:** Anteil der korrekt als positiv klassifizierten Objekte an der Gesamtheit der tatsächlich positiven Objekte
(spaltenweise) = TP/(TP+TN)

**Accuracy:** Anteil aller korrekt klassifizierten Objekte
(TP+TN) /(TP+TN+FP+FN)

**Vorgehen:**
1. Wo ist der EBaum immer Falsch, dafür einzeln durchgehen und FP suchen
Bedeutet 3/10 wären falsch predicted

| | true High | true Low | Precision |
| --------- | --------- | -------- | --------- |
| pred High | TH 4 | FH 2 | 66,66% |
| pred Low | FN 1 | TL 3 | 75% |
| recall | 80% | 60% | |

Accuracy = 7/10 = 70%
recall = richtig positiv/high klassifiziert an gesamtheit positiven Objekten
gemäß Test-Datensatz haben wir 6 echte highs, von denen aber nur 4 vorhergesagt wurden, also wären das ja dann 4/6 = 66,666/ und nicht 80 :S
recall gibt aber auch an, wieviele man von den echten erwischt hat, und wieviele man verpasst hat, weil nicht richtig gefunden.
Dann hätten wir bei der generierten Liste 5 mal high stehen, und davon wäre ja 1 falsch, also waärend as dann 80 % (so ist das wohl auch hier zu verstehen, siehe Video Dataminig ab 1h53m)

Das Wort Recall wörtlich nehmen, um wieviel % wurde alles aus der echten Datensatz wiedergegeben, wieviele haben wir bei unserer autogenerierten verpasst

Precision gibt wiederum an, wieviele haben wir falsch angegeben in der autogenerierten, also wieviel "Fehlalarm" haben wir ausgelöst, weil der wert doch nicht so war in den Stammdaten (TP wollen wir alle mitbekommen, wenn wir alles TP wiedergeben, dann hätten wir nen coolen 100% recall, aber leider ne miese Precision, da wir ne menge negativ als positiv ausgegeben haben)

b. Berechnen Sie anhand der unter Aufgabe a. erstellten Confusion Matrix die Kennzahlen **Accuracy, Precision** und **Recall** (6 Pkt.).
Bewerten Sie die Güte des Entscheidungsbaums (2 Minunten).
Hinweis: Falls sie a nicht lösen können, denken Sie sich eine Confusion Matrix aus und berechnen Sie für die ausgedachte Matrix die Kennzahlen.

>[name=Dennis]
>Das ist rein Übungszwecke hier
>
>Was ist das bessere Splitt-Attribut?
>- Berechnung via Gini Index: 1-p(A)^2^-p(B)^2
>
>Attribut A: 1-p(G)^2^-p(H)^2
>A1|A2: HHHGG | GHHG
>A1: 1-(2/5)^2^-(3/5)^2^ = 12/25 = 0,48
>A2: 1-(2/4)^2^-(2/4)^2^ = 0,5
>GiniIndex - Mittelwert Attribut A:
>5/9 * 0,48 + 4/9 * 0,5 = 22/45 = 0,489
>
>Attribut B: 1-p(G)^2^-p(H)^2
>B1|B2: HHHGGG | GHH
>B1: 1-(3/6)^2^-(3/6)^2^ = 0,5
>B2: 1-(1/3)^2-(2/3)^2^ = 0,44444
>Gini Index Mittelwert Attribut B:
>6/9 * 0,5 + 3/9 * 0,4444 = 0,4814
>
>B(0,4814)<A(0,489), daher ist B das bessere Split-Attribut