Explorative Datenanalyse mit t-SNE

Motivation

Das heutige Zeitalter ist gekennzeichnet von einer wahren Flut von Daten; nie war es einfacher, Daten in großem Maße und automatisiert zu erheben und abzuspeichern. Gleichzeitig wird es immer schwieriger, Relevanz von Daten einzuschätzen, Zusammenhänge zwischen Datensätzen zu erkennen und diese geeignet zu analysieren. Insbesondere ist eine Vorauswahl von Attributen für die weitere Analyse notwendig, um viele Verfahren überhaupt sinnvoll anwenden zu können.

Klassischerweise kommen hier Verfahren wie Korrelationsanalysen, PCA/ICA oder auch neuronale Netze zum Zuge. Nachteil der ersten beiden genannten Verfahren ist, dass ihr Anwendungsbereich sich im Wesentlichen in linearen Zusammenhängen erschöpft. Während neuronale Netze dieser Beschränkung nicht unterliegen, ist ihr Einsatz aufwändig und die benötigten Datenmengen enorm.
T-SNE (t-distributed stochastic neighbour embedding) stellt eine relativ simple und auf schwächeren Annahmen basierende Alternative zu oben genannten Verfahren dar und soll daher in diesem Blogeintrag näher beleuchtet werden – insbesondere soll eine mögliche Vorgehensweise bei einer solchen Analyse vorgestellt werden.

 

Ansatz

Bei einer Analyse mit t-SNE beginnt der Analyst mit einem hochdimensionalen Datensatz D; beispielsweise kann es sich hierbei um eine Tabelle mit zu klassifizierenden Kunden handeln. Die Anzahl der verfügbaren Attribute ist – insbesondere beispielsweise falls es sich um einen Analytical Base Table handelt – sehr groß.

Zwischen jeweils zwei Datensätzen wird vom Analyst nun eine Entfernung definiert – dabei kann es sich um bekannte Maße wie im euklidischen Raum handeln, aber durchaus auch um selbstdefinierte Maße. Für geeignete Ergebnisse empfiehlt es sich, die Attribute zu normalisieren und anschließend zu gewichten, sodass die Entfernung zweier Datensätze nicht von der Größenordnung der numerischen Differenz abhängt, sondern von qualitativ begründeten Unterschieden. Kategorische Attribute müssen in diesem Zuge in numerische Attribute transformiert werden.

Anschließend sucht t-SNE per Gradient Descent eine Abbildung dieser Objekte auf einen niedrigdimensionalen Raum (üblicherweise in den \(\mathbb{R}^2\) oder \(\mathbb{R}^3\)), sodass die Abstände zwischen den Objekten bestmöglich erhalten werden.

 

Definition

Nach der Überführung der Objekte in Vektoren und anschließender Normalisierung erhalten wir also einen Datensatz \(x_1, \dots, x_N \in \mathbb{N}^p\) für gewisse \(n, p \in \mathbb{N}\). Die Ähnlichkeit zweier Punkte \(x_i, x_j\) wird nun definiert als

\(
p_{ij} = \frac{p_{j\mid i} + p_{i\mid j}}{2N}
\)

wobei

\(
p_{j\mid i} = \frac{\exp(-\lVert\mathbf{x}_i – \mathbf{x}_j\rVert^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-\lVert\mathbf{x}_i – \mathbf{x}_k\rVert^2 / 2\sigma_i^2)},
\)

Anschaulich wird also die Ähnlichkeit zweier Punkte \(x_i, x_j\) als die Wahrscheinlichkeit definiert, mit der ein Punkt \(x_j\), ausgehend von einem Punkt \(x_i\), gewichtet mithilfe der Dichte einer Normalverteilung der Varianz \(\sigma_i\) zentriert in \(x_i\), gezogen wird. Gesucht werden nun korrespondierende Punkte \(y_1, \dots, y_n \in \mathbb{R}^2\), s.d.

\(
q_{ij} = \frac{(1 + \lVert \mathbf{y}_i – \mathbf{y}_j\rVert^2)^{-1}}{\sum_{k \neq i} (1 + \lVert \mathbf{y}_i – \mathbf{y}_k\rVert^2)^{-1}}
\)

der ursprünglichen Verteilung möglichst ähnlich ist. Ähnlichkeit der Verteilungen wird hier mit der sog. Kullback-Leibler-Divergence (abgekürzt KLD) quantifiziert, die gewissermaßen Entfernungen zwischen Verteilungen misst.

Die niedrigdimensionalen Daten erlauben dann eine direkte Darstellung in Form einer Grafik; häufig lassen sich hier Strukturen durch visuelle Inspektion erkennen.
Insbesondere liefern reine Clustering-Verfahren zwar Cluster von Daten, es ist aber alles andere als trivial, die Beziehungen zwischen Clustern grafisch darzustellen bzw. zu analysieren. In diesem Kontext bietet sich t-SNE ebenfalls als nachgeordneter Bearbeitungsschritt an, um durch andere Algorithmen gefundene Cluster grafisch darzustellen.

Je nach Datensatz findet t-SNE häufig intuitiv sinnvolle Strukturen und stellt diese grafisch dar. In der unten gezeigten Projektion werden beispielsweise die verschiedenen Buchstaben in natürlicher Weise zu Clustern verbunden – man beachte, wie t-SNE eindrucksvoll ”5”, ”6”, ”3” und ”8” intuitiv sinnvollerweise nebeneinander angeordnet hat.

t-SNE Darstellung vom MNIST Datensatz von https://lvdmaaten.github.io/tsne/

Praxisbeispiel

Exemplarisch soll hier der Datensatz “Statlog (German Credit Data) Data Set” des UCI Machine Learning Repositories mithilfe der t-SNE Implementierung von sklearn analysiert werden. Nach einer einfachen Normalisierung der Daten ergibt t-SNE das folgende Mapping:

t-SNE Datenpunkte in R^2; ‘1’ bedeutet, dass der Kunde als ”unzuverlässig” klassifiziert wird; 0 als zuverlässig.

Etwa mittig ist eine Ansammlung von zuverlässigen Kunden zu erkennen; im Folgenden soll diese Intuition bestätigt werden und nach Besonderheiten dieser Gruppe gesucht werden. Zu diesem Zwecke wird die in folgender Grafik durch das Rechteck eingegrenzte Gruppe analysiert.

Bei der Auswahl der Attribute, in denen sich die ausgewählte Gruppe von der Gesamtheit signifikant unterscheidet, stützen wir uns wieder auf die KLD wie unterer Grafik dargestellt. Dieses Verfahren erlaubt uns, zeitsparend interessante Attribute zu finden, ohne manuell Vergleiche anstellen zu müssen. Auch diese Vorgehensweise hat Allgemeingültigkeit, lässt sich also völlig unabhängig von t-SNE einsetzen.

 

KLD zwischen den Verteilungen in den Attributen zwischen ausgewählter Gruppe und ihrem Komplement; die Attribute sind von 1-19 aufsteigend durchnummeriert, nicht alle Werte sind wohldefiniert.

Eine manuelle Analyse ergibt, dass die in unserer Gruppe erfassen Kunden im Vergleich zur Gesamtheit

  • lange wohnhaft sind
  • seit langem ihrer jetzigen Beschäftigung nachgehen
  • Rücklagen haben
  • eine Telefonnummer angegeben haben

In diesem speziellen Fall sollten diese Eigenschaften nicht überraschen; allerdings rufen wir uns in Erinnerung, dass t-SNE keine a prior Informationen zur Abbildung der Kunden verwendet hat. Insbesondere stand t-SNE die Klassifizierung der Kunden in (un)zuverlässige Kunden nicht zur Verfügung. Nichtsdestotrotz hat t-SNE für uns interessante Kunden – ebenfalls ohne Kenntnis der qualitativen Bedeutung der Attribute – nah beieinander gruppiert.

Zu guter Letzt überzeugen wir uns davon, dass die von uns analysierte Gruppe von zuverlässigen Kunden sich von allgemein zuverlässigen Kunden unterscheidet. Das ist insbesondere dafür notwendig, um uns davon zu überzeugen, dass wir eine zusätzliche Struktur entdeckt haben und die oben genannten Eigenschaften nicht einfach nur zuverlässige Kunden an sich charakterisieren.

Dazu lässt sich beispielsweise die KLD unserer Gruppe zu zuverlässigen Kunden im Allgemeinen und zu allen Kunden vergleichen; befinden sich beide Abstände zumindest in der gleichen Größenordnung, so ist dies ein Indikator dafür, dass es sich in der Tat um eine Untergruppe der zuverlässigen Kunden handelt. Die KLD dieses Vergleiches sowie die Sampling-Verteilung (engl. sampling distribution) der maximalen KLD zwischen der einer zufällig gezogenen Teilgruppe aller guten Kunden (derselben Größe wie die oben ausgewählte Gruppe) und der Menge aller Kunden finden sich in nachstehenden Grafiken:

Im Vergleich zu anderen im Projekt berechneten KLDs sind die Unterschiede hier vernachlässigbar
max. KLD zwischen allen Kunden und einer Gruppe, gezogen von allen “guten” Kunden; besagte Gruppe hat dieselbe Größe wie die Referenzgruppe. Die rote Linie markiert die tatsächlich beobachtete KLD.

 

 

 

 

 

 

 

 

Im ursprünglichen Scatterplot ist in der rechten unteren Ecke deutlich ein Cluster zu erkennen. Eine ähnlich geartete Analyse ergibt, dass sich auch dieser Cluster signifikant von dem Hauptcluster unterscheidet – allerdings ist diese Erkenntnis nicht für den hier vorgestellten Use Case relevant. Es gilt also, die gefundenen Strukturen auf Relevanz für den jeweiligen Use Case zu analysieren.

 

Zusammenfassung

t-SNE erlaubt es häufig, sich einen Überblick von Strukturen hochdimensionaler Daten zu verschaffen. Dabei definiert t-SNE im Vergleich zu alternativen Algorithmen keine explizite Abbildung, wodurch Nichtlinearität und Genügsamkeit bzgl. der Datenmenge erreicht wird. Damit spannt t-SNE einen Bogen zwischen klassischen Algorithmen wie PCA/ICA und sehr datenhungrigen Alternativen wie neuronalen Netzen.

Die Relevanz von gefundenen Strukturen hängt stark von der Definition der initialen Entfernung ab; je mehr a priori Information eingeht, desto wahrscheinlicher sind die Strukturen relevant für den definierten Use-Case.

t-SNE ist ein sehr genügsamer und simplistischer Ansatz, der für schnelles Prototyping und schneller Eingrenzung von Attributen interessant ist. Somit bietet es sich beispielsweise als vorgelagerter Schritt zu einer statistischen Analyse oder zu einem anspruchsvolleren Algorithmus an.