Réduction dimensionnelle évolutive

9

Compte tenu du nombre constant de caractéristiques, Barnes-Hut t-SNE a une complexité de , les projections aléatoires et l'ACP ont une complexité de O ( n ), ce qui les rend "abordables" pour de très grands ensembles de données.O(nlog⁡n)O(n)

En revanche, les méthodes reposant sur la mise à l'échelle multidimensionnelle ont une complexité .O(n2)

Existe-t-il d'autres techniques de réduction de dimension (en dehors de triviales, comme regarder les premières colonnes, bien sûr) dont la complexité est inférieure à O ( n log n ) ?kO(nlog⁡n)

pca dimensionality-reduction large-data multidimensional-scaling tsne RUser4512
la source

Réponses:

5

Une option intéressante serait d'explorer la réduction de la dimensionnalité basée sur les neurones. Le type de réseau le plus couramment utilisé pour la réduction de la dimensionnalité, l'autoencodeur, peut être formé au détriment de , où i représente les itérations de formation (est un hyper-paramètre indépendant des données de formation). Par conséquent, la complexité de la formation se simplifie en O ( n ) .O(i⋅n)iO(n)

Vous pouvez commencer par jeter un œil aux travaux du séminaire de 2006 de Hinton et Salakhutdinov [1]. Depuis lors, les choses ont beaucoup évolué. Maintenant, la plupart de l'attention est atteinte par les encodeurs automatiques variationnels [2], mais l'idée de base (un réseau qui reconstruit l'entrée à sa couche de sortie avec une couche de goulot d'étranglement entre les deux) reste la même. Notez que, contrairement à PCA et RP, les encodeurs automatiques effectuent une réduction de dimensionnalité non linéaire. En outre, contrairement au t-SNE, les auto-encodeurs peuvent transformer des échantillons invisibles sans avoir à recycler l'ensemble du modèle.

Sur le plan pratique, je vous recommande de jeter un coup d'œil à ce post , qui donne des détails sur la façon d'implémenter différents types d'autoencodeurs avec la merveilleuse bibliothèque Keras.

[1] Hinton, GE et Salakhutdinov, RR (2006). Réduire la dimensionnalité des données avec les réseaux de neurones. science, 313 (5786), 504-507.

[2] Kingma, DP et Welling, M. (2013). Bayes variationnels à encodage automatique. arXiv preprint arXiv: 1312.6114.

Daniel López
la source
1
techniquement, vous n'avez pas à recycler le modèle pour de nouveaux échantillons avec t-SNE en utilisant cette approche particulière: lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf
bibliolytic
Sûr. L'auteur a également suggéré de former un régresseur multivarié pour prédire l'emplacement des échantillons de données d'entrée sous forme de carte comme approche potentielle. Dans l'article que vous mentionnez, l'auteur forme un réseau de neurones pour minimiser directement la perte de t-SNE. Cependant, dans les deux cas, vous devez définir un modèle ou une fonction explicite pour mapper les points de données à l'espace résultant, il doit donc être suffisamment puissant (suffisamment de couches / neurones) pour apprendre l'incorporation, mais pas trop pour éviter un sur-ajustement ... Cela sacrifie une partie de l'utilisabilité du t-SNE standard.
Daniel López
Pas de désaccord là-bas, je pense simplement qu'il est un peu inexact de comparer les auto-encodeurs et le t-SNE comme vous le faites dans votre réponse, car le t-SNE peut être utilisé comme une perte pour la réduction de la dimensionnalité
bibliolytic
O(n)
O(m2)m