PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: 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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

• 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.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

Verfahrem 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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

Lineare Dimensionalitätsreduktion

Lineare Dimensionalitätsreduktion transformiert die ursprünglichen m Dateninstanzen {x_i}^m in nieder dimensionalere Ausdrücke {z_i}^m 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.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

Zentrierung von Daten

• Verschiebung der Daten in Richtung "Koordinatenursprung"

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

4

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

• 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 bestimmmt 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})$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

• 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.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

• 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!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

• 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.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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 []
} [];

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

3. Rekonstruktion der Datentabelle aus der reduzierten Tabelle

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

PCA Beispiel

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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.$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

Dichtebasiertes Clustering

• kNN kann ebenso als ein ML Clusterer mit Inferenz auf unbekannten 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)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

Algorithmische Schritte für DBSCAN Clustering

• Der Algorithmus iteriert über alle Punkte indem er willkürlich einen Punkt im Datensatz aufnimmt (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)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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 aus der Dimension des Datensatzes *D abgeleitet werden, so dass minPts ≥ D + 1.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

ε

Der Wert für ε kann dann unter Verwendung eines k-Rntfernungsgraphen 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 ε zeigt dieses Diagramm einen "Ellenbogen": 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 befindet.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

Beispiel DBSCAN

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul G: Daten- und Dimensionalitätsreduktion

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ä zu reduzieren (Reduktion der Datenvariablen und Ersatz mit transformierten)

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