Detailansicht
Approximative Linear t-SNE using k-Means
Sonja Biedermann
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Informatik
Betreuer*in
Claudia Plant
DOI
10.25365/thesis.69604
URN
urn:nbn:at:at-ubw:1-11098.71252.103985-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Unter Dimensionsreduktion versteht man die Transformation von hochdimensionalen
Daten in einen niedrigdimensionalen Raum, ohne die wesentlichen Merkmale der Daten
zu verlieren. Idealerweise gibt das niedrigdimensionale sogenannte Embedding seine
Struktur leichter Preis als sein hochdimensionales Gegenstück.
Es gibt viele unterschiedliche Ansätze zur Dimensionsreduktion. Die häufigste Unterscheidungsmethode
ist zwischen linearer Dimensionsreduktion und nonlinearer Dimensionsreduktion. Lineare
Dimensionsreduktionsmethoden transformieren die Daten in einen niedrigdimensionalen Raum
nur unter Verwendung von linearen Transformationen, wohingehen nonlineare Methoden die
Daten jegliche Art von Transformation anwenden dürfen.
In dieser Thesis beschäftigen wir uns mit einer nonlinearen Methode namens t-SNE, die
eine Variante von Stochastic Neighbor Embedding (SNE) unter Verwendung der Student-t Verteilung
darstellt. $t$-SNE ist beliebt aufgrund der visuell ansprechenden Embeddings, die Clusterings
ähneln, die es produziert. Allerdings ist sie auch stochastisch, nonparametrisch, verfügt
über eine schwierig zu optimierende Zielfunktion und hat zudem noch eine hohe Laufzeitkomplexität
von O(n^2).
Wir implementieren und evaluieren einer variante von t-SNE namens kt-SNE,
die den Clusteringalgorithmus k-Means und Locality Sensitive Hashing
verwendet. Wir erreichen eine Laufzeitkomplexität von O(n). Wir
evaluieren unsere Methode gründlich und vergleichen sie mit drei vergleichbaren
Methoden. Unsere Methode erreicht Resultate die zumeist innerhalb von 10% der
besten Methode auf realen Daten liegen und läuft signifikant schneller als
Barnes-Hut t-SNE.
Abstract
(Englisch)
Dimensionality reduction is the transformation of high-dimensional
data into a lower dimensional space while keeping the interesting parts
of the data intact. Ideally, the low-dimensional so-called embedding
reveals structure that would have been much more difficult to detect
in the high-dimensional space.
There are many different approaches to dimensionality reduction, and the most
common taxonomy separates them into linear and non-linear methods. Linear
methods transform the high-dimensional data solely by applying linear
transformations, such as PCA, while non-linear methods are essentially
free to transform the data by any means.
In this thesis, we will be focusing on a non-linear method called t-SNE,
which is a variant of Stochastic Neighborhood Embedding using the Student-t
distribution. t-SNE has become popular due to the visual properties of the
embeddings it produces: well-separated clusters consisting of similar items.
It is, however, a stochastic method, non-parametric in its original form, possesses
a difficult to optimize non-convex objective function and also has a prohibitively
high runtime complexity of O(n^2).
We implement and evaluate a variant of t-SNE named kt-SNE utilizing k-Means
and locality sensitive hashing. We achieve an overall runtime complexity of O(n).
We thoroughly evaluate our method and put it to the test against three competing
methods. Our method achieves results that are mostly within 10% of the best result of the
competing methods on real data and runs significantly faster than Barnes-Hut t-SNE.
Schlagwörter
Schlagwörter
(Englisch)
dimensionality reduction t-SNE visualization k-Means approximation
Schlagwörter
(Deutsch)
Dimensionsreduktion t-SNE Visualisierung k-Means Approximation
Autor*innen
Sonja Biedermann
Haupttitel (Englisch)
Approximative Linear t-SNE using k-Means
Paralleltitel (Deutsch)
Approximatives Lineares t-SNE mit k-Means
Publikationsjahr
2021
Umfangsangabe
vi, 69 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*in
Claudia Plant
Klassifikation
54 Informatik > 54.00 Informatik: Allgemeines
AC Nummer
AC16427064
Utheses ID
59085
Studienkennzahl
UA | 066 | 921 | |