Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion -

Daten- und Dimensionalitätsreduktion

Datenreduktion ist ein wichtiger Schritt in der Datenvorverarbeitung für ML

Ziel: Reduktion der Datenvariablen (Attribute) → Dimensionalitätsreduktion pro Instanz

Ziel: Reduktion der Dateninstanzen (durch kleine Anzahl von Repräsentanteninstanzen) → Datenvolumenreduktion

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Motivation für Datenreduktion

Motivation für Datenreduktion

1. Die Daten sind sowohl hinsichtlich Dimensionalität des Eingabevektors x als auch hinsichtlich der Anzahl von Dateninstanzen |D| sehr groß

2. Es gibt Redundanzen

   • a. Von Datenvariablen (lineare Abhängigkeit)
   • b. Von Dateninstanzen (Redundanz und Überlappung)
   • Aber: Reduktion bei b. kann die geforderte Datenvarianz verschlechtern!

3. Trennung von wenig aussagekräftigen (schwachen) von aussagekräftigen (starken) Variablen

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Motivation für Datenreduktion

Wenn die Dimensionalität der Eingabedaten x zunimmt, wird jedes Lernproblem immer schwieriger und rechenintensiver!

• Beispielsweise werden in regelmäßigen Abständen 5 Punkte von [0,1] abgetastet.
  • Das sammeln von Proben auf die gleiche Weise im d-dimensionalen Raum erfordert 5d-Punkte, die exponentiell in Bezug auf d wachsen.

4

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Motivation für Datenreduktion

Ein weiteres Problem bei hochdimensionalen Daten ist, dass unsere geometrische Interpretation von Daten irreführend sein kann.

• Betrachtet man zum Beispiel die ausfüllende Hypersphäre des Einheishyperwürfels im d-dimensionalen Raum
  • Wenn d = 1 ist, ist das Volumen einer eingepassten Hypersphäre 1, was dem Hyperwürfel entspricht.
  • Wenn d auf 2 und 3 erhöht wird, ist das Volumen des Hyperkubus immer noch 1, aber das Volumen der Hypersphäre ist ungefähr 0,79 bzw. 0,52.

4

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Motivation für Datenreduktion

• Unsere geometrische Intuition ist falsch,
  • da obwohl die eingepasste Hypersphäre kleiner als der Hyperwürfel ist, ist die Hypersphäre nicht extrem klein.
  • Wenn jedoch d weiter erhöht wird, ist das Volumen des Hyperkubus immer noch 1, aber das Volumen der ausfüllenden Hypersphäre neigt zu 0.
  • Dies bedeutet, dass, wenn d groß ist, die Hypersphäre fast vernachlässigbar ist.

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Verfahren und Methoden

Verfahren und Methoden

Lineare Algebra

• Bestimmung von Eigenvektoren und Hauptkomponenten mit der Principle Component Analysis
  • Abbildung des Eingabedatenraums auf einen niedrigdimensionaleren Datenraum unter Beibehaltung der Datenrepräsentation
  • Ziel: Reduktion der Attribute, Beibehaltung der Dateninstanzen

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Verfahren und Methoden

Clustering

• Bestimmung von Gruppen von Dateninstanzen (mit geometrischer Gemeinsamkeit durch "Nähe") durch dichtebasierte Clusteringverfahren (DBSCAN)

  • Ziel: Reduktion der Instanzmenge durch wenige repräsentative Instanzen; Beibehaltung der Datenvariablen

  • Repräsentative Instanzen können (aber müssen nicht) mehrheitlich die Instanzen der Gruppe mit einem bestimmten Wert der Zielvariable (sofern kategortisch oder intervallkodiert) verknüpfen

  • Hohe Zielvariablenwertdiversität in Gruppen zeigt schwache Korrelation von x mit y!

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Lineare Dimensionalitätsreduktion

Lineare Dimensionalitätsreduktion

Lineare Dimensionalitätsreduktion transformiert die ursprünglichen d-dimensionalen Dateninstanzen {x_i}ⁿ in nieder m-dimensionale Ausdrücke {z_i}ⁿ durch eine lineare Transformation T ∈ ℝ^m×d

$$z_i=\mathbf{T}x_i$$

• T ist die Transformationsmatrix, z der reduzierte Datenvektor (pro Dateninstanz i) und x der ursprüngliche Datenvektor.

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Lineare Dimensionalitätsreduktion

4 (a) Lineare Dimensionalitätsreduktion (b) Projektion von Daten auf einen linearen Subraum

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Lineare Dimensionalitätsreduktion

Zentrierung von Daten

• Verschiebung der Daten in Richtung "Koordinatenursprung"

$$x_i \leftarrow x_i - 1/n \sum_j x_j$$

4

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Unüberwachte Dimensionsreduktion

Unüberwachte Dimensionsreduktion

Hauptkomponentenanalyse (PCA)

• Reduktion der Datendimesionalität unter Beibehaltung der intrinsischen Information der Daten und der Datenstruktur

4 PCA: (a) Reduktion der Dimensionalität 3 → 2 unter Beibehaltung der ursprünglichen geometrischen Eigenschaften der Punkte zueinander (Position) und der Gruppenzugehörigkeit (b)

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Unüberwachte Dimensionsreduktion

• Das bedeutet dass z_i eine orthogonale Projektion von x_i ist

  • D.h. T T^T = I_m mit I_m als Identitätsmatrix und a^T die transponierte Matrix

• Die "Distanz" zwischen x und z kann aber (als Fehler) nicht unmittelbar bestimmt werden

  • Daher wird z wieder in den ursprünglich d-dimensionalen Datenraum durch T^T zurück transformiert

• Die euklidische Distanz ist dann gegeben durch die totale statistische Streumatrix C und der Spur einer Matrix tr:

$$\sum_j ||\mathbf{T}^T\mathbf{T}x_i-x_i ||^2=-tr(\mathbf{T}\mathbf{C}\mathbf{T}^T)+tr(\mathbf{C})$$

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Unüberwachte Dimensionsreduktion

• mit:

$$\mathbf{C}=\sum_j x_j x_j^T$$

• D.h. PCA ist ein Optimierungsproblem mit:

$$\mathop {\max }\limits_{\mathbf{T}} tr(\mathbf{T}\mathbf{C}\mathbf{T}^T)$$

• Es gibt eine globale Lösung:

$$\mathbf{T} = (\mathbf{e}_1,...,\mathbf{e}_m)^T$$

• mit e_i als Eigenvektor der Matrix C mit den Eigenwerten λ₁ ≥ λ₂ ≥ .. ≥ λ_d ≥ 0.

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Unüberwachte Dimensionsreduktion

• D.h. es gilt:

$$\mathbf{C}\mathbf{e} = \lambda \mathbf{e}$$

• Es wird "kleine" und "große" Eigenvektoren geben

Die Transformationsmatrix T der PCA ist also eine orthogonale Projektion in einen Subraum der durch die "großen" Eigenvektoren aufgespannt wird,

• Die kleinen Eigenvektoren werden daher entfernt

• Und: PCA transformierte Variablen sind unkorreliert!

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Unüberwachte Dimensionsreduktion

• PCA liefert aber i.A. keine Struktureigenschaften wie Cluster

17 Weiteres Beispiel von PCA: Die Analyse der Hauptkomponenten zentriert die Dateninstanzen und dreht dann die Achsen, um Sie mit den Richtungen der höchsten Varianz in Einklang zu bringen. Wenn die Varianz auf z₂ klein ist, kann Sie ignoriert werden und wir haben eine Dimensionalitätsreduktion von zwei auf eins.

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - ML.pca

ML.pca

• Das ML Framework stellt ein PCA Modul zur Verfügung:

• Die Daten D müssen in Matrixform vorliegen (keine Recordtabellen)

1. Eigenvektoren berechnen

ML.pca.getEigenVectors = function(data:number [][]) → {
  eigenvalue: number, vector: number []
} [];

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - ML.pca

2. Transformation der Datentabelle berechnen

ML.pca.computeAdjustedData = 
  function (data:number [][],
            eigenVector1:{},eigenVector2?:{},..)
→ { 
  adjustedData: number [][], 
  formattedAdjustedData: number [][], 
  avgData: number [][], 
  selectedVectors: number [][] 
}

• Achtung: Das Datenformat von adjustedData ist transponiert und muss für eine Tabelle rekonstruiert werden

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - ML.pca

3. Rekonstruktion der Datentabelle aus der reduzierten Tabelle

ML.pca.computeOriginalData = function(
  formattedAdjustedData,
  selectedVectors,
  avgData) → {
  formattedOriginalData,
}

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - PCA Beispiel

PCA Beispiel

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Lokalitätsbewahrende Projektion

Lokalitätsbewahrende Projektion

• Ähnlichkeit zwischen Instanzen x_i und x_j wird untersucht und mit einem Wert 0 ≤ W_i,j ≤ 1 ausgedrückt.

Ähnlichkeitsfunktionen

Gaußfunktion

$$W_{i,j}=exp(-\frac{||x_i-x_j||^2}{2t^2})$$

(t ist ein Anpassungsparameter)

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Lokalitätsbewahrende Projektion

k-Nächster Nachbar (kNN)

$${W_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1,({x_i} \in {N_k}({x_j}) \vee {x_j} \in {N_k}({x_i}))} \\ 0 \end{array}} \right.$$

• N_k(x) ist die Menge aller Nachbarschaftsinstanzen (k ist die Anzahl der Menge)

• k ist ein Anpassungsparameter der die Lokalität einstellt (Reichweite)

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Lokalitätsbewahrende Projektion

Transformation

$$\mathop {\min }\limits_T \sum\limits_{i,j} {{W_{ij}}||{\mathbf{T}}{x_i} - {\mathbf{T}}{x_j}|{|^2}}$$

• Problem: T=0 ist eine Lösung, aber nutzlos!

• Daher weitere Randbedingung für die Minimierung (Anpassung von T):

$$\mathbf{T}\mathbf{X}\mathbf{D}\mathbf{X}^T\mathbf{T}^T=\mathbf{I}_m\\ \mathbf{X} = ({x_1},..,{x_n}),{\mathbf{D}_{ij}} = \left\{ {\begin{array}{*{20}{l}} {\sum\limits_k {{W_{ik}}} ,(i = j)} \\ {0,(i \ne j)} \end{array}} \right.$$

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Dichtebasiertes Clustering

Dichtebasiertes Clustering

• kNN kann ebenso als ein ML Clusterer mit Inferenz auf unbekannten Dateninstanzen eingesetzt werden

• Dichtebasierte Clusteringmethoden können primär für die Datenreduktion eingesetzt werden

  • Reduktion von einer Menge von Dateninstanzen auf Gruppen (wobei die Instanzen erhalten bleiben, aber in jeder Gruppe reduziert werden können)

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Dichtebasiertes Clustering

DBSCAN

Dichtebasiertes Räumliches Clustering mit Rauschen (DBSCAN) ist ein Basisalgorithmus. Es kann Cluster unterschiedlicher Formen und Größen aus einer großen Datenmenge entdecken, die Rauschen und Ausreißer enthält.

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Dichtebasiertes Clustering

www.kdnuggets.com/2020/04/dbscan-clustering-algorithm-machine-learning.html

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Dichtebasiertes Clustering

Algorithmische Schritte für DBSCAN Clustering

• Der Algorithmus iteriert über alle Punkte indem er willkürlich einen Punkt im Datensatz auswählt (bis alle Punkte besucht wurden)

• Wenn es mindestens minPoint - Punkte in einem Radius von ε bis zu dem Punkt gibt, werden alle diese Punkte als Teil desselben Clusters betrachet.

• Die Cluster werden dann erweitert, indem die Nachbarschaftsberechnung für jeden Nachbarpunkt rekursiv wiederholt wird.

• Eventuell gibt es Beschränkungen bezüglich der Dimension der Dateninstanzen (typisch 2: Clustering von Bildpunkten)

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Dichtebasiertes Clustering

Wahl der Parameter

Jede Data Mining Aufgabe hat das Problem der Parameterwahl.

• Jeder Parameter beeinflusst den Algorithmus auf bestimmte Weise. Für DBSCAN werden die Parameter ε und minPts benötigt.

minPts

Das Minimum von minPts kann aus der Dimension des Datensatzes D abgeleitet werden, so dass minPts ≥ D + 1 gilt (D=|D|).

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Dichtebasiertes Clustering

ε

Der Wert für ε kann dann unter Verwendung eines k-Entfernungsgraphen ausgewählt werden, der den Abstand zum k = minPts-1 nächsten Nachbarn zeichnet, der vom größten zum kleinsten Wert geordnet ist.

• Bei guten Werten von ε gibt es eine ausgewogene Verteilung der Dateninstanzen in Gruppen
  • Wenn ε viel zu klein gewählt wird, wird ein großer Teil der Daten nicht gruppiert, während für
  • einen zu hohen Wert von ε Cluster zusammengeführt werden und sich die Mehrheit der Objekte im selben Cluster befinden.

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Dichtebasiertes Clustering

Beispiel DBSCAN

Stefan Bosse - Maschinelles Lernen - Daten- und Dimensionalitätsreduktion - Zusammenfassung

Zusammenfassung

• Datenreduktion ist ein wichtiger Schritt in der Datenvorverarbeitung

  • Datenreduktion bedeutet die Reduktion der Datenmenge und/oder ihrer Dimensionalität
  • Datenreduktion ist bereits eine Merkmalsselektion (Reduktion auf wesentliche Attribute und Werte)

• PCA ist geeignet um numerische Eingabedaten in ihrer Dimensionalität zu reduzieren (Reduktion der Datenvariablen und Ersatz mit transformierten unter Verwendung der Hauptkomponentenvektoren aus der PCA!)

• DBSCAN ist geeignet um Gruppen von Dateninstanzen zu finden um schliesslich repräsentative Instanzen daraus zu ermitteln