Data Mining - ausführliche Zusammenfassung PDF

Preview

Summary

Data MiningAttributwerte ● Nominale Attribute: auf der jeweiligen Wertemenge existiert keine bedeutsame Ordnung ○ Bsp: Namen, Beschreibungen, ID ● Binäre Attribute ● Ordinale Attribute: durch eine vorhandene Ordnung / Rangfolge in seinem Wertebereich gekennzeichnet ○ Bsp: Kreditwürdigkeit (hervorrag...

Description

Data Mining Attributwerte ● Nominale Attribute: auf der jeweiligen Wertemenge existiert keine bedeutsame Ordnung ○ Bsp: Namen, Beschreibungen, ID ● Binäre Attribute ● Ordinale Attribute: durch eine vorhandene Ordnung / Rangfolge in seinem Wertebereich gekennzeichnet ○ Bsp: Kreditwürdigkeit (hervorragend, passabel, zweifelhaft, schlecht) ● Numerische Attribute: quantitative Angabe ○ Bsp: Gehalt ● Zeitreihen: Folge von Werten, die in bestimmten Zeitabstanden gemessen wurden ○ zwei Attributarten: ■ Kontextattribut: für Zeitreihen ist das die Zeit; andere Datentypen können mehrere Kontextattribute haben ■ Verhaltensattribut: der Messwert ● diskrete Folge: ○ Folge von Werten mit genau einem Kontextattribut (wie bei Zeitreihen auch), z.B. einem Zähler ○ einziger Unterschied: die Werte sind logisch voneinander getrennt; zwischen den Werten liegt kein weiterer Wert ○ Beispiel: Folge von Kundeneinkäufe im Supermarkt

Statistische Grundbegriffe Lageparameter → für sortierte Folgen ●

arithmetisches Mittel:

●

gewichtetes arithmetisches Mittel:

●

Median / Mittelwert: (Hälfte des Maximums)

●

Modus

(z.B. Uhrzeit & Wochentag)

●

●

Quartil: teilt sortierten Folge ○ erstes Quartil: Q(1/4) - Stelle bei 0,25 ○ zweites Quartil: Q(1/2) - Stelle bei 0,5 ○ drittes Quartil: Q(3/4) - Stelle bei 0,75 Quartilsabstand: Q(3/4) - Q(1/4)

Streuungsmaße ● Varianz:

●

Standardabweichung: Wurzel der Variants

Abstand- und Ähnlichkeitsmaße ●

Distanzmatrix ○ zur Berechnung der Ähnlichkeit von Datensätze ⇾ immer Obj1.x vergleichen mit Obj2.x, Obj3.x, Obj4.x … und Obj1.y vergleiche mit Obj2.y, Obj3.y, Obj4.y ○ benötigt eine Datenmatrix ■ enthält pro Zeile alle Attribute eines Objektes ○ nun wird mit Hilfe einer Distanzfunktion dist() der Abstand zwischen Attributwerten berechnet: ■ Werte aus Datenmatrix vergleichen: immer Attribut der Ziel-Zelle vergleichen mit dem Wert der Diagonalen

Da eine Distanzfunktion symmetrisch ist, muss nur das linke Dreieck der Matrix ausgefüllt werden; Diagonale ist 0

Abstandsmaße für binäre Attribute q - Anzahl Attribute, die beide Wert = 1 haben s - Anzahl Attribute, die beide mit Wert = 0 r - Anzahl Attribute mit ungleichen Werten p - Gesamtanzahl der Attribute ●

symmetrische binäre Distanz:

●

asymmetrische binäre Distanz:

Abstandsmaße für numerische Attribute → Vergleich zweier Folgen von Zahlen Bsp:

●

Abstand zwischen zweidimensionalen Punkten x = (2.3, 2.9) y = (2.6, 2.3) euklidische Distanz:

(geometrisch ist dies die Länge der kürzesten Geraden zwischen zwei Punkten) Bsp: ⇾ dist(x, y) ≈ 0,67 ●

Manhatten-Distanz: (Summe der Einzelabstände zwischen den Attributen)

Bsp: ⇾ dist(x, y) = 0,9

●

Minkowski-Distanz:

●

Maximum-Distanz:

Bsp: ⇾ dist(x, y) = 0,6

KE2:

Datenbereinigung Korrektur von Ausreißern und Inkonsistenzen 1. Binning → alle Ausprägungen eines Attributes aufsteigend sortieren und anschließend in gleichgroße Behälter einteilen 2. Glätten 3 Varianten: ■ ■ ■

nach Mittelwert: nach Median: nach Grenzen:

Jeden Wert durch arith. Mittel teilen Jeden Wert durch Median teilen Jeden Wert durch Minimum oder Maximum des Behälters ersetzen (zu dem der Abstand geringer ist)

bei Zeitreihen kommen häufig Ausreißer vor → abgewandelte Form des Binnings verwenden: ● Zeitreihe wird in k Behälter unterteilt (ohne zu sortieren) ● für jeden Behälter wird der Mittelwert (oder Median) berechnet → diese Mittelwerte stellen die geglättete Folge dar ● → je größer das k, desdo stärker der Glättungseffekt (und damit auch der Datenverlust) Reduzierung des Datenverlusts durch Glätten mit gleitendem Mittelwert ● Behälter überschneiden sich: erster Behälter [t1, tk], zweiter Behälter [t2, tk+1], ... … Exponentielles Glätten

y - geglätteter Wert 𝛼 - wird vorgegeben

! EA 2.5

Ähnlichkeitsmaße für Zeitreihen → diese müssen zunächst normiert werden

Methode zur Normierung: Dynamic Time Warping (DTW) warping - verziehen, wöben ● Vereinheitlichung der Länge beider Zeitreihen durch Wiederholung bestimmter Werte ● Vorgehen: parallel durch beide Liste laufen und jeweils nur einen der beiden Indizes hochzählen, nämlich den der die kleinste Differenz beider Werte verursacht ● Bsp: x =

y =

Abstand dieser Zeitreihen: DTWi,j( x, y) = dist(xi, yj) + min(DTWi,j-1 ( x, y ), DTWi-1,j ( x,  y), DTWi-1,j-1 ( x,  y))  * Funktion dist() wird vorgegeben, z.B. dist(xi, yj) = |xi - yj| Nun kann DTW schrittweise berechnet werden; i und j sind die Positionen in den Zeitreihen; i läuft hier von 1-6 und j von 1-2; damit die min-Funktion immer die benötigten Vorgänger hat, wird DTW initialisiert: DTW0,0 = 0 DTWi,0 = ∞ (i ist 1-6) DTW0,j = ∞ (j ist 1-2) DTW1,1( x, y) = dist(26, 19) + min{∞,∞, 0} = 7 DTW1,2( x, y) = dist(26, 7) + min{7,∞,∞} = 26 DTW2,1( x, y) = dist(13, 19) + min{∞, 7,∞} = 13 DTW2,2( x, y) = dist(13, 7) + min{13, 26, 7} = 13 DTW3,1( x, y) = dist(2, 19) + min{∞, 13,∞} = 30 DTW3,2( x, y) = dist(2, 7) + min{30, 13, 13} = 18 DTW4,1( x, y) = dist(28, 19) + min{∞, 30,∞} = 39 DTW4,2( x, y) = dist(28, 7) + min{39, 18, 30} = 39 DTW5,1( x, y) = dist(11, 19) + min{∞, 39,∞} = 47 DTW5,2( x, y) = dist(11, 7) + min{47, 39, 39} = 43 DTW6,1( x, y) = dist(18, 19) + min{∞, 47,∞} = 48 DTW6,2( x, y) = dist(18, 7) + min{48, 43, 47} = 54 => Der Abstand dieser Zeitreihen ist die letzte Zahl, also 54.

Levenshteindistanz / Edit-Distanz → für diskrete Folgen * Ähnlichkeit zweier Strings kann auch als Länge ihrer längsten gemeinsamen Teilfolge (LGT) angegeben werden

Ähnlichkeit von Textdokumenten ●

Kosinus-Ähnlichkeit:

x, y sind Vektoren, der enthaltenen Worte x * y ist das Skalarprodukt x1y1 + … + xpyp → die jeweils erste Werte multipliziert + jeweils zweite Wert emultipliziert + jeweils dritte .. (aber nicht jeder mit jedem!) || x||  ist euklidische Normalform von x:

* in einem Vektor ist die Häufigkeit der im Text enthaltenen Wörter gezählt (jede Dimension ein Wort) jeweils die Normalform (Nominativ, Singular) verwenden ! Bsp-in-Übungen

Chi-Quadrat-Test (für numerische Folgen) → prüft, ob zwischen zwei Attributen eine Korrelation besteht: hier, ob die Zielgruppe mit der Wahl der Partei korreliert Bsp:

1. Für jede Zelle die erwartete Häufigkeit ei,j berechnen: e1,1 =

→ in Klammern hinter jede Zelle schreiben

2. Signifikanzniveau X berechnen:

⇒ Ergebnis ist ein sog. Signifikanzniveau; nun wird in einer gegebenen Tabelle abgelesen, ob Korrelation besteht oder nicht

Kovarianz → prüft, ob positive oder negative Korrelation zwsichen zwei Attributen besteht

E - Erwartungswert (arithm. Mittel) A*B Skalarprodukt von A und B und dann durch die Anzahl wenn ⇒ positiv, dann postive Korrelation (wenn A steigt, dann steigt auch B) ⇒ negativ, dann negative Korrelation (wenn A steigt, sinkt B) Der Betrag der Zahl hat keine Aussage - nur das Vorzeichen ist relevant

Korrelationskoeffizient → Kovarianz gibt nur die Richtung der Korrelation an, dagegen kann der Korrelationskoeffizient Stärke und Richtung angeben

●

Vorzeichen gibt Richtung an, Betrag gibt Stärke an

Datenreduktion → um handbhabbare Datenmenge zu erhalten ● der dadurch verursachte Datenverlust darf die Charakteristik der Daten nicht spürbar verändern Diskrete Wavelet-Transformation (DWT) Bsp: Zahlenfolge 152, 228, 148, 176, 192, 220, 200, 32

Schwellenwert 30

Vorgehen: 1. alle Werte in einen Vektor übernehmen, aber Werte unterhalb des Schwellenwertes 0 setzen

x =

152 228 148 176 192 220 200 32

2. Länge des Vektors auf eine 2er Potenz bringen durch Ergänzen von 0en Länge 8 → passt schon 3. Der Vektor wird durch zwei Funktionen verrechnet:

a. Glättungsfunktion b. Unterschiedfunktion Zuerst läuft f durch den Vektor jeweils mit zwei Nachbarwerte (also f(x1, x2), dann f(x3, x4) … ). Mit diesen Ergebnissen wird die erste Hälfte des nächsten Vektors aufgebaut. Dann läuft g genauso durch den Vektor. Dessen Ergebnisse werden an den nächsten Vektor angehängt (also füllt er die zweite Hälfte). x’ =

(152 + 228) / 2 (148 + 176) / 2 (192 + 220) / 2 (200 + 32) / 2 152 - 190 148 - 162 192 - 206 200 - 116

=

190 162 206 116 -38 -14 -14 84

4. Schritt 3 wird wiederholt, allerdings nur bis zur Hälfte der jeweils vorherigen Bearbeitungslänge (also nun nur bis zur Hälfte, dann Viertel, ..). x’’ =

(190 + 162) / 2 (206 + 116) / 2

=

176 161

x’’’ =

190 - 176 206 - 161 (unverändert übernehmen) (unverändert übernehmen) (unverändert übernehmen) (unverändert übernehmen)

14 45 -38 -14 -14 84

(176 + 161) / 2 = 176 - 168,5 (unverändert übernehmen) (unverändert übernehmen) (unverändert übernehmen) (unverändert übernehmen) (unverändert übernehmen) (unverändert übernehmen)

168,5 7,5 14 45 -38 -14 -14 84 → Ergebnisvektor

Achtung: Bei Differenzbildung (zweite Hälfte) als Minuent immer jeden zweiten Wert nehmen beginnend beginnend mit x1, → x1-x1’ x3-x2’ x5-x3’ x7-x4’ mittels Tabelle: 152 152+228 2

228 =

190 190+162 2

168,5

=

162 =

176 176+161 2

148+176 2

148

206+116 2

=

161 =

192+220 2

176 =

200+32 2

=

206

116

190-176 =

206-161 =

14

45

14

45

192

220

200

32

152-190 =

148-162 =

192-206 =

200-116 =

-38

-14

-14

84

-38

-14

-14

84

176-168,5 =

7,5

Rücktransformation: 168,5

7,5

168,5+7,5=

168,5-7,5=

176

161

176+14=

176-14=

161+45=

161-45=

190

162

206

116

190+(-38)=

190-(-38)=

162+(-14)=

162-(-14)=

206+(-14)=

206-(-14)=

116+84=

116-84=

152

228

148

176

192

220

200

32

Achtung: Falls ein Schwellenwert für Rücktransformation angegeben ist, müssen zunächst die Werte | vi | 0, -8 -> 0 Bsp: Schwellenwert: 10 Vektor: (3, 12, 20, -5, -14, 1, 10, 2) → (0, 12, 20, 0, -14, 0, 0, 0)

Rücktransformation mittels Haar-Wavelets: 1. Tabelle aufstellen Wavelet-Koeffizient (Ergebnisvektor)

Basisvektor (auswendig lernen)

168,5

(1, -1, 0, 0, 0, 0, 0, 0)

7,5

(0, 0, 1, -1, 0, 0, 0, 0)

14

(0, 0, 0, 0, 1, -1, 0, 0)

45

(0, 0, 0, 0, 0, 0, 1, -1)

-38

(1, 1, -1, -1, 0, 0, 0, 0)

66

(0, 0, 0, 0, 1, 1, -1, -1)

-58

(1, 1, 1, 1, -1, -1, -1, -1)

60

(1, 1, 1, 1, 1, 1, 1, 1)

2. Nun von unten nach oben schrittweise die Basisvektoren verrechnen → Faktor im Basisvektor mit linker Zahl multiplizieren und auf den aktuellen Vektor addieren, beginnend mit Vektor (0, 0, 0, 0, 0, 0, 0, 0) 60 => (0 + 60*1, 0 + 60*1, 0 + 60*1, 0 + 60*1, 0 + 60*1, 0 + 60*1, 0 + 60*1, 0 + 60*1) = (60, 60, 60, 60, 60, 60, 60, 60)

-58 => (60 + -58*1, 60 + -58*1, 60 + -58*1, 60 + -58*1, 60 + -58*-1, 60 + -58*-1, 60 + -58*-1, 60 + -58*-1) = (2, 2, 2, 2, 118, 118, 118, 118) 66 => (2 + 66*0, 2 + 66*0, 2 + 66*0, 2 + 66*0, 118 + 66*1, 118 + 66*1, 118 + 66*-1, 118 + 66*-1) = (2, 2, 2, 2, 184, 184, 52, 52) -38 => (2 + -38*1, 2 + -38*1, 2 + -38*-1, 2 + -38*-1, 184 + -38*0, 184 + -38*0, 52 + -38*0, 52 + -38*0) = (-36, -36, 40, 40, 184, 184, 52, 52) 45 => (-36 + 45*0, -36 + 45*0, 40 + 45*0, 40 + 45*0, 184 + 45*0, 184 + 45*0, 52 + 45*1, 52 + 45*-1) = (-36, -36, 40, 40, 184, 184, 97, 7) 14 => (-36 + 14*0, -36 + 14*0, 40 + 14*0, 40 + 14*0, 184 + 14*1, 184 + 14*1, 53 + 14*0, 51 + 14*0) = (-36, -36, 40, 40, 198, 170, 97, 7) 7,5 => (-36 + 7,5*0, -36 + 7,5*0, 40 + 7,5*1, 40 + 7,5*-1, 198 + 7,5*0, 170 + 7,5*0, 53 + 7,5*0, 51 + 7,5*0) = (-36, -36, 47,5, 32,5, 198, 170, 97, 7) 168,5 => (-36 + 168,5*1, -36 + 168*-1, 47,5 + 168,5*0, 32)

Auswahl wesentlicher Attribute (Feature Subset Selection) → keine Änderung an den Daten, sondern spezifische Auswahl von Attributen (nicht Attributwerte) mögliche Vorgehen / Heuristiken: ●

schrittweise Vorwärtsauswahl: beginnend mit leerer Menge schrittweise das nächstbeste Attribut hinzufügen

●

schrittweise Rückwärtseliminierung: beginnend mit Gesamtmenge schrittweise das schlechteste Attribut entfernen

●

schrittweise beidseitige Optimierung: ausgehend von einer Teilmenge wird in jedem Schritt das schlechteste enthaltene Attribut durch das beste nicht enthaltene ersetzt

●

Entscheidugsbäume: An jedem Knoten des Baums wird das beste Attribut für eine Datenpartionierung gewählt

* Bewertung: bestes/schlechtestes Attribut z.B. mittels statistischer Signifikanztests

Resevoir Sampling → Stichprobe aus einem Datenstrom ● die ersten k ankommenden Datensätze werden in die Stichprobe aufgenommen ● danach wird eine Zufallszahl z zwischen 1 und n generiert (n: bisher insgesamt eingetroffene Datensätze) ● wenn z maximal so groß wie k ist, wird der neue Datensatz an Position z der Stichprobe geschrieben Zu jeder Zeit ist die Warscheinlichkeit für einen Datensatz in der Stichprobe enthalten zu sein k/n .

Datentransformation Normalisierung: → Vereinheitlichung numerischer Attribute (aufzählbar, aber nicht zwingend Zahlen) 3 Verfahren: ● Min-Max-Normalisierung: Intervall [Il,

Ir] festlegen, indem sich die normalisierten Werte bewegen sollen, z.B. [-1,1] oder [0,1]

dann Attributwerte normalisieren mittels

A - Menge der Attributwerte

●

z-Transformation / Standardisierung: 𝐴 σA

●

- arithm. Mittel - Standardabweichung (s.o.)

Dezimalskalierung:

(Nenner entspricht der kleinsten Zehnerpotenz, die betragsmäßig größer als alle Attributwerte von A ist) ! EA 2.4

KE3

Mustersuche Grundlagen

Menge von Items; z.B. die Artikel, die Artikel eines Lebensmittelhändlers

D

Menge nichtleerer Transaktionen (z.B. alle Einkäufe bei Kaufland)

I

Itemset (ein Einkauf mit 1..n Items) → I ∈ D

anz(A)

Häufigkeit eines Itemsets A

Assoziationsregel (A,B

zwei disjunkte Itemsets)

Eine Assoziationsregel besteht aus ●

𝑎𝑛𝑧(𝐴 ∪ 𝐵) |𝐷| → Anzahl unterschiedlicher Items durch Gesamtanzahl Itemsets (/Transaktionen)

Support

supp(A ⇒ B) = P(A ∪ B)

=

! Support-Count für ein einzelnes Item: Wie oft kommt es in den Itemsets vor

●

𝑎𝑛𝑧(𝐴 ∪ 𝐵) 𝑎𝑛𝑧(𝐴) → relativer Anteil der Menge an Items, die in beiden enthalten sind (A,B) im Verhältnis zur Anzahl derer, die nur in A enthalten sind

Konfidenz

conf(A ⇒ B)

= P(B|A)

=

starke Assoziationsregel

Regel, deren Support und Konfidenz bestimmte Schwellenwerte überschreitet

k-Itemset

Itemset mit k Items

häufiges Itemset

Itemset, das einen Mindestsupport suppmin oder eine Mindestanzahl anzmin übersteigt

abgeschlossenes Itemset

Itemset, für das kein echtes Ober-Itemset in D existiert, was den gleichen Support hat (Ober-Itemset: enthält alle Items + mind. eins mehr: J ⊃ I )

maximales Itemset

Itemset, für das kein echtes Ober-Itemset in D existiert, das häufig ist

Methoden zur Bestimmung von Zusammenhängen a) Apriori-Algorithmus b) Frequent-Pattern-Growth c) vertikalen Datenformat

Apriori-Algorithmus → Berechnung der Menge häufiger Itemsets Lk+1 aus der Menge Lk * https://www.youtube.com/watch?v=LZii6N4vGDs basiert auf Apriori-Eigenschaft: eine Teilmenge eines häufigen Itemsets ist selbst auch ein häufiges Itemset Bsp:

I1 = {item1, item2, item3} I2 = [item1, item3} I3 = {item1, item4} I4 = {item2, item5, item6} suppmin= 0,5 Wenn < 1, dann relative Angabe → Umrechnen in absolute Angabe suppmin = 0,5 * 4 = 2

Vorgehen: 1. Support-Count einelementiger Itemsets ermitteln C1 = item1: 3 item2: 2 item3: 2 item4: 1 item5: 1 item6: 1 Filtern nach suppmin: L1 = item1: 3 item2: 2 item3: 2 2. Support-Count zweielementiger Itemsets (alle Kombinationen) ermitteln: C2 = {item1, item2}: 1 {item1, item3}: 2 {item2: item3}: 1 L2 = {item1, item3}

längere Kombinationen mit supp >= 2 nicht möglich, deshalb ist L3 leer. Ergebnis: L1 ∪ L2 ∪ L3 = {{item1}, {item2}, {item3}, {item1, item3}}

Starke Assoziationsregeln (bedingte Wahrscheinlichkeit oberhalb einer Grenze (confmin) aus vorherigem Beispiel aus L2 ableiten für confmin = 0,5 Assoziationsregel

Support

Confidenz

Confidenz %

item1 → item3

2

⅔ = 0,66

66 %

item3 → item1

2

2/2 = 1

100 %

* Wenn es mehr als zwei items gibt, dann:

* Berechnung Confidenz: {A, B} → C =

{A, B} → C {A, C} → B {B, C} → A {A} → {B, C} {B} → {A, C} {C} → {A, B}

𝐻ä𝑢𝑓𝑖𝑔𝑘𝑒𝑖𝑡 ({𝐴, 𝐵, 𝐶}} 𝐻ä𝑢𝑓𝑖𝑔𝑘𝑒𝑖𝑡({𝐴, 𝐵})

Da Konfidenz beider Regeln größer als confmin, sind die Ergebnis-Regeln: item1 → item3 item3 → item1 Wer item1 kauft, kauft auch item3 und wer item3 kauft, kauft auch item1.

Frequent-Pattern-Growth-Methode → gleicher Zweck, wie Apriori, aber schneller und benötigt nur suppmin

Bsp: I1 = {b, a, c, d, g, m, p} I2 = {a, b, c, f, l, m, o} I3 = {b, f, h, o} I4 = {b, k, c, p}

I5 = {a, f, c, l, p, m, n}

suppmin = 3

Vorgehen: 1. Items, die mindestens so häufig sind wie suppmin, in L1 aufnehmen L1 = {b, a, c, f, m, p} 4, 3, 4, 3, 3, 3 (Häufigkeiten) → L daraus ableiten (absteigend sortiert und als Folge statt als Menge) L = + alle Transaktionen nach absteigender Häufigkeit sortieren (hier schon geschehen): L1’ = L2’ = L3’ = L4’ = L5’ = 2. Frequent-Pattern-Tree zeichnen a. L absteigend auf die linke Seite b. Nun die Transaktionen (die Ausgangs-Itemsets) einzeichnen i. einen neuen Zweig, falls kein Zweig mit den Items des aktuellen Itemssets beginnt, ansonsten den Teilzweig nachnutzen und die Zähler um eins hochzählen c. Pfeile einzeichnen; beginned vom Array links zur ersten Nennung des Items, dann zur nächsten Nennung; immer gleich nach dem Einzeichnen einer Transaktion

3. Reduzierte Musterbasen aufstellen, für die Items des Arrays links, aufsteigend a. I’ = {f} ⇒ R({f}) = {{b, c, a, m}, {b}, {c, a, m, p}} (alle Pfade, die auf f enden, ohne f aufnehmen; Pfad mehrfach aufnehmen falls Anzahl bei f größer 1) i. häufige Items in R: keine (alle unter minsupp) → I1 = ∅

b. I’ = {p} ⇒ R({p}) = {{b, c, a, m}, {b, c}, {c, a, m}} i. häufige Items in R: c -> reduzierter FP-Baum besteht aus nur einem Knoten ii. reduzierter FP-Baum

→ l2 = {{c, p}}

wenn die verbleibenden Item...