Utilisateur:Chlyah.elwassifi.eilco/Brouillon

{{?|date=février 2019}} {{intro|date=février 2019}} {{wikifier|date=février 2019}} {{à déjargoniser|date=février 2019}} {{sources secondaires|date=février 2019}} De nos jours, l’apprentissage automatique est appliqué à de nombreux ensembles de données volumineuses collectées dans différents domaines. L’un des majeurs défis de l’application des méthodes d’apprentissage automatique sur ces données consiste à savoir comment utiliser d’une manière efficace les différents moyens de calculs disponibles lors de l’implémentation des modèles prédictifs et inférentiels, tout en utilisant d’une manière statistiquement optimale ces multiples ressources. Afin de pouvoir traiter et analyser la quantité importante de ces données collectées, il existe une approche qui met en avant la création des système d’informations distribués et des algorithmes d’apprentissage distribués. Cependant, la haute disponibilité de ces systèmes peut potentiellement être une problématique. De plus, leur coût peut peut être beaucoup plus élevé que ce que l’on peut se permettre, ce qui rend l'apprentissage distribué inadapté à tous les scénarios. Par exemple, il existe de nombreux algorithmes d’optimisation pour les problème de minimisation des risques empiriques^[1], avec une convergence manifestement rapide et un faible coût de calcul par itération^[2]. Il convient de souligner à ce stade que la rapidité de ces méthodes d’optimisation dépend fortement du nombre de conditions du problème en question, ce qui n’est pas approprié à de nombreuses problématiques du monde réel.

Le sketching ^[3] s’est imposé comme méthode d’analyse de données volumineuses. l’idée derrière celle ci est de se rapprocher de la solution du problème initial en résolvant un autre à plus petite échelle. Par exemple, le sketching a été utilisée pour résoudre approximativement divers problèmes à grande importance, allant de la régression des moindres carrés à l’approximation de rang faible et à la décomposition en valeurs singulières. Cependant, l’un des principaux inconvénients de la méthode du sketching est qu’elle ne convient pas dans les cas où on cherche des solutions précise. Afin d’obtenir une solution avec une erreur d’approximation plus petite, nous avons souvent besoin d’augmenter la dimension du sketching de façon exponentielle.

Des travaux récents qui portait sur le sketching itératif ont amélioré la situation. Ces méthodes sont capables d’affiner la précision de leur solution en résolvant itérativement des problèmes réduits à petite échelle. des méthodes d'échantillonnages tel que "Iterative Hessian sketch” ont été conçus pour réduire la taille de l’échantillon du problème original. tandis que d’autres méthodes ont été conçus pour réduire la dimensionnalité des données.

Dans ce présent document,la partie de “réduction non supervisée de la dimensionnalité”, qui s’inscrit dans le cadre de la réduction de la dimension. Par exemple, si le nombre de caractéristiques est élevé, il peut être utile de le réduire avec en se basant sur des techniques non supervisées pour ensuite passer aux méthodes supervisées. Pour cela plusieurs méthodes d’apprentissage non supervisées ont été mises en oeuvre tel que “l’analyse en composantes principales” et “projection randomisé”. Ces derniers vont être présentés ci-dessous.

Historique[modifier | modifier le code]

L'algèbre linéaire a une longue histoire dans l'analyse de données statistiques à grande échelle (selon les normes de l'époque).

Méthode des moindres carrés : indépendamment élaborée par Gauss et Legendre, elle a été utilisée au début des années 1800 afin d’ajuster des équations linéaires dans le but de déterminer les orbites planétaires.
Analyse en composantes principales (ACP) et approximations de rang faible : élaborée par Pearson et Hotelling, elle a été utilisée au début des années 1900 pour l’analyse exploratoire des données et l’analyse prédictive.

Ces méthodes ainsi que les méthodes connexes sont intéressantes puisque, par exemple., s’il y a du bruit ou du caractère aléatoire dans les données, les principaux composants ont tendance à capter le signal et à éliminer le bruit.

Avènement de l’ordinateur numérique dans les années 1950 :

Proto informatique et les premières applications de l’algèbre linéaire axées sur les problèmes informatiques (où le calcul était un outil essentiel)
Même pour les problèmes "bien posés", de nombreux algorithmes rencontraient des problème en présence de la précision finie.
Les travaux de Turing, von Neumann et d'autres ont jeté les bases du calcul scientifique et de l’algèbre linéaire numérique : cela a conduit à des mesures de complexité spécifiques aux problèmes (par exemple, le nombre de conditions) qui caractérisent le comportement d'une entrée pour une classe spécifique d'algorithmes (par exemple, les algorithmes itératifs).

Mais pour diverses raisons techniques et non techniques, il s'est alors produit une bifurcation dans le domaine naissant de l'informatique :

L'algèbre linéaire continue est devenue le domaine des mathématiques appliquées.
La théorie et la pratique de l'informatique sont devenues discrètes et combinatoires.

L'algèbre linéaire est devenu le domaine des mathématiques appliquées continues ; et il s'est concentré sur les applications scientifiques.

Presque tous les travaux dans le domaine du calcul scientifique et de l’algèbre linéaire numérique ont été déterministes, ce qui a conduit à l'élaboration de codes de haute qualité dans les années 1980-1990, par exemple LAPACK.
La plupart des travaux ont porté sur l'optimisation des matrices FLOPS - le vecteur matrice se multiplie sur des matrices denses - dans des environnements de mémoire partagée sur des matrices qui apparaissent dans des applications informatiques scientifiques structurées.
Ce code est maintenant largement utilisé dans l’algèbre linéaire numérique et le calcul scientifique ainsi que dans l'apprentissage automatique, les statistiques, l'analyse de données, etc.

L'informatique est devenue discrète et combinatoire et s'est concentrée sur les applications commerciales et d'affaires.

Turing, Church, et d'autres études de calcul étudié en soi.
Des approches apparemment différentes (théorie de la récursivité, le calcul λ et les machines de Turing) ont défini la même classe de fonctions.
Il est apparu que le concept de calculabilité est formellement appréhendé de manière qualitative et robuste par ces trois processus équivalents, indépendants des données d'entrée.
La randomisation (où le caractère aléatoire est à l'intérieur de l'algorithme, et l'algorithme est appliqué à des données arbitraires ou au pire des cas) a été introduite et exploitée comme une puissante ressource informatique.

Récemment, une convergence de ces deux perspectives très différentes.

Motivé par des applications scientifiques, Internet, les médias sociaux, financiers, etc.
Le calcul en soi est nécessaire mais très insuffisant
La plupart des gens veulent obtenir un aperçu et/ou faire des prédictions à partir des données qu'ils génèrent pour faire des affirmations en aval sur le monde.

Au cœur de ces développements, l’algèbre linéaire numérique randomisée inclut :

Caractère aléatoire des données par rapport au caractère aléatoire de l'algorithme
Continu (mathématiques) ou discret (informatique).
Algorithmes du pire des cas par rapport à des mesures de complexité propres à un problème particulier
Applications scientifiques par opposition aux applications d'affaires ou de commerce.

Bon "atome d'hydrogène" pour considérer les bases algorithmiques et statistiques de l'analyse moderne de données à grande échelle.

ACP[modifier | modifier le code]

L’analyse en composante principale ^[4] est une technique de projection qui vise à réduire la complexité de données ayant une grande dimension. Elle consiste à projeter les données sur un espace de dimension réduite. Les axes de cet espace sont appelés les composantes principales. Ces composantes sont définies de façon à ce que les distances et les similarités entre les données soient préservées.

Méthode[modifier | modifier le code]

Nous avons un échantillon de p variables $X_{1},X_{2},...,Xp$ observées sur n individus qu'on place dans une matrice X.

${\begin{bmatrix}X_{11}&..&X_{1p}\\.&&.\\.&&.\\X_{n1}&..&X_{np}\end{bmatrix}}$

Ces variables peuvent être liées entre elles.

L’objectif de cette méthode est d’extraire de nouvelles variables indépendantes (composantes principales) qui représentent au mieux les données sans perte d’information^[5].

La première composante est déterminée de manière à maximiser la variance des données une fois projetées sur son axe. Autrement dit, cette composante explique au mieux la variabilité des données. Ce qui est également équivalent à minimiser la distance entre les données et leur projection sur l’axe de la composante principale. Le reste des composantes sont également déterminées sur le même critère et doivent être orthogonales aux composantes précédentes.

Etapes pour obtenir les composantes principales[modifier | modifier le code]

Centrer et Réduire les données[modifier | modifier le code]

De chaque colonne i de X, soustrait la moyenne ${\overline {X_{i}}}$ de la variable $X_{i}$ . On obtient une nouvelle matrice X. ${\begin{bmatrix}X_{11}-{\overline {X_{1}}}&..&X_{1p}-{\overline {X_{p}}}\\.&&.\\.&&.\\X_{n1}-{\overline {X_{1}}}&..&X_{np}-{\overline {X_{p}}}\end{bmatrix}}$ Quand les données ne sont pas homogènes ou n’ont pas les même unités, on réduit les données on divise chaque colonne i par l’écart type de la variable $X_{i}$ .

Calculer la matrice de covariance[modifier | modifier le code]

$C=(c_{ij})$ tel que $\forall i,j$ $c_{ij}=Cov(X_{i},X_{j})$

Calculer les vecteurs propres et les valeurs propres de C[modifier | modifier le code]

Un vecteur propre d’une matrice A est un vecteur v qui vérifie $A.v=\lambda .v$ . On appelle $\lambda$ la valeur propre associée à v. Les vecteurs et valeurs propres peuvent être calculées en décomposant la matrice C sous la forme $PDP^{-}1$ , où $P$ est une matrice (matrice des vecteurs propres), $P^{-}1$ est son inverse et (matrice des valeurs propres) est une matrice diagonale. Chaque colonne i de $P$ est un vecteur propre de $C$ et la valeur diagonale qui se trouve sur la colonne i de $D$ et sa valeur propre associée. La matrice de covariance peut être décomposée de cette manière car elle est symétrique. Après avoir calculé les vecteurs et valeurs propres, on les ordonne par ordre décroissant des valeurs propres; le vecteur propre ayant la plus grande valeur propre est l’axe de la première composante principale, l’axe de la deuxième composante est celle associée à la deuxième plus grande valeur propre et ainsi de suite. C’est ainsi qu’on obtient une nouvelle base orthogonale où les données peuvent être représentées. Les vecteurs et valeurs propres peuvent être calculées en décomposant la matrice C sous la forme $PDP^{-1}$ , où P est une matrice (matrice des vecteurs propres), $P^{-1}$ est son inverse et D(matrice des valeurs propres) est une matrice diagonale. Chaque colonne i de P est un vecteur propre de C et la valeur diagonale qui se trouve sur la colonne i de $D$ est sa valeur propre associée.

Projeter les données sur le nouveau repère[modifier | modifier le code]

Soit $P'$ la matrice des vecteurs propres triée à partir de $P$ comme expliqué précédemment. La matrice suivante $X'=XP$ représente le même échantillon $X$ de départ (centré) mais en fonction des nouvelles variables qui sont les composantes principales.

Justification On suppose que les données de l’échantillon $X$ sont centrées. On considère $w$ le vecteur unitaire qui représente l’axe de la première composante principale. Comme mentionné précédemment, la projection des données de $X$ sur cet axe (qui correspond également à la composante principale) doit avoir une variance maximale. Ce qui signifie que $1/n\sum _{i}t_{i}^{2}$ doit être maximale, avec $t_{i}$ la cordonnée de chaque ligne i de $X$ sur $w$ : ${\begin{bmatrix}t_{1}\\.\\.\\t_{n}\end{bmatrix}}$ Nous avons $1/n\sum _{i}t_{i}^{2}=(X.W)^{T}.(X.W)$ .

Donc $w$ doit être tel que cette quantité, qu’on appelle $v$ , soit maximale. $V=(X.w)^{T}.(X.w)=w^{T}.X^{T}X.w=w^{T}.C.w$ ( $C$ est la matrice de covariance associée à $X$ car $X$ est centrée)

Puisque C est diagonalisable, $V=w^{T}.P^{T}DP.w=(w.P)^{T}D(P.w)$ Le vecteur $w$ qui maximise $V$ est le vecteur propre de $C$ associé à la plus grande valeur propre.

Déterminer le nombre des composantes principales[modifier | modifier le code]

Il est possible de fixer une dimension jugée convenable au cas étudié. Par exemple, on peut choisir de garder deux dimensions pour pouvoir représenter les données visuellement. On peut également se baser sur la variance capturée par les composantes principales. Si on garde les k premières composantes, la variance capturée est égale à $(\lambda _{1}+...+\lambda _{k})/(\lambda _{1}+...+\lambda _{p})$ . Donc si par exemple on veut capturer 90% de la variance, on détermine le plus petit k qui permette d’atteindre ce pourcentage. Il peut aussi être intéressant, pour ne pas avoir à fixer un pourcentage, de représenter la variance capturée en fonction de la dimension k. On peut donc choisir de s’arrêter à la dimension à partir de laquelle on constate une baisse significative de variance capturée.

Implémentation en langage R[modifier | modifier le code]

Nous utiliserons dans cet exemple une base de données décrivant les caractéristiques de différents types de plantes ^[6]. Nous chargeons donc le fichier

>data <- read.csv("iris.csv", header=TRUE)

Nous affichons le nombre de variables et le nombre d’observation contenu dans la base de données.

''>str(data)''<br>

'data.frame':	150 obs. of  6 variables:

$ Id           : int  1 2 3 4 5 6 7 8 9 10 ...
$ SepalLengthCm: num  5.1 4.9 4.7 4.6 5 5.4 4.6 5 4.4 4.9 ...
$ SepalWidthCm : num  3.5 3 3.2 3.1 3.6 3.9 3.4 3.4 2.9 3.1 ...
$ PetalLengthCm: num  1.4 1.4 1.3 1.5 1.4 1.7 1.4 1.5 1.4 1.5 ...
$ PetalWidthCm : num  0.2 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 ...
$ Species      : Factor w/ 3 levels "Iris-setosa",..: 1 1 1 1 1 1 1 1 1 1 ...

Nous avons donc 6 colonnes dont 4 variables qui caractérisent la plante et 150 observation/individu qui se divisent en 3 espèces: setosa ,vesicular et virginica.

Nous pouvons afficher les premières lignes de la base de données.

>head(data)

Sepal.Length Sepal.Width Petal.Length Petal.Width Species

5.1             3.5         1.4         0.2        setosa

4.9             3.0         1.4         0.2        setosa

4.7             3.2         1.3         0.2        setosa

4.6             3.1         1.5         0.2        setosa

5.0             3.6         1.4         0.2        setosa

5.4             3.9         1.7         0.4        setosa

L’enjeu est de pouvoir trouver des éléments pour savoir faire la différence entre ces espèces.

Pour implémenter l’ACP nous on peut utiliser la méthode pcomp sur notre jeu de données
```
>pca = prcomp(data[,1:4])
```

Afficher les composantes principales il faut utiliser l’attribut rotation.

>pca$rotation
                       PC1         PC2          PC3          PC4
Id             0.999256341 -0.03775685 -0.007003269  0.003484093
SepalLengthCm  0.013658550  0.52195396 -0.534544609  0.664559677
SepalWidthCm  -0.003967352 -0.01641807 -0.785395638 -0.618763605
PetalLengthCm  0.035839488  0.85197942  0.312036387 -0.418903207

les écarts-types

> pca$sdev
[1] 2.0554417 0.4921825 0.2802212 0.1538929

La variance pour chaque composante

> 100 * pca$sdev^2 / sum(pca$sdev^2)
[1] 92.4616207  5.3015568  1.7185140  0.518308

La variance totale

> sum(100 * (pca$sdev^2)[1:2] / sum(pca$sdev^2))
[1] 97.76318

Graphe de variables ^[7]

> res.pca <- PCA(data[,2:5])

[figure variables]

Interprétation du graphe

Ici nous n’avons affiché que les variables, dans cette partie nous pouvons déjà avoir quelque constatation.

Quand deux variables vont dans le même sens on peut dire qu’ils sont corrélés comme dans ce cas avec la longueur et la largeur des pétales.

On peut donc dire que plus la langueur des pétales augmentent plus leurs largeurs augmente aussi.

A l’inverse si deux variables partent chacune au sens opposé de l’autre, nous dirons que les variables sont corrélés négativement.

Le dernier cas c’est quand deux variables sont a peut prés perpendiculaires nous dirons que les deux variables ne sont pas corrélés.

Graphe des individus
```
>plot(pca$x[,1:2], col=iris[,5])
```

[figure individus]

Nous avons donc tracé notre graphe d’individu en utilisant les deux premiers axes de l’ACP qui contiennent le plus d’informations.

Projection randomisée[modifier | modifier le code]

La méthode de projection randomisée implémente un moyen simple et efficace de réduction de la dimensionnalité des données en échangeant une quantité contrôlée de précision (comme la variance supplémentaire) pour des temps de traitement plus rapides et des modèles de plus petite taille. Cette méthode met en oeuvre deux types de matrices aléatoire non structurée :

Matrice aléatoire gaussienne qui réduit la dimensionnalité en projetant l'espace d'entrée d'origine sur une matrice générée aléatoirement où les composants sont tirés de la distribution suivante $N(0,{\frac {1}{nComposants}})$
Matrice aléatoire uniformément distribuée est une alternative à la matrice de projection aléatoire gaussienne dense qui garantit une qualité d'intégration similaire tout en étant beaucoup plus efficace en mémoire et en permettant un calcul plus rapide des données projetées.

Si l'on définit s = 1 / densité, les éléments de la matrice aléatoire sont tirés de ${\begin{cases}-{\sqrt {\frac {s}{nComposants}}}&1/2s\\0&1-1/s\\+{\sqrt {\frac {s}{nComposants}}}&1/2s\end{cases}}$ où nComposants est la taille du sous-espace projeté. Par défaut, la densité des éléments non zéro est fixée à la densité minimale recommandée par Ping Li et al. ${\frac {1}{\sqrt {nCaracteristiques}}}$

Les dimensions et la distribution des matrices de projections aléatoires sont contrôlées de manière à préserver les distances par paires entre deux échantillons du jeu de données. La projection aléatoire est donc une technique d'approximation appropriée pour la méthode basée sur la distance.

Le principal résultat théorique derrière l'efficacité de la projection aléatoire est le théorème “Johnson-Lindenstrauss lemma”. Ne connaissant que le nombre d'échantillons, il estime avec prudence la taille minimale du sous-espace aléatoire pour garantir une distorsion limitée introduite par la projection aléatoire.

Johnson-Lindenstrauss lemma[modifier | modifier le code]

Le théorème Johnson-Lindenstrauss lemma indique que tout ensemble de données de grande dimension peut être projeté aléatoirement dans un espace euclidien de dimension inférieure tout en contrôlant la distorsion dans les distances en paires.

Théorie[modifier | modifier le code]

La distorsion introduite par une projection aléatoire p est affirmée par le fait que p définit un eps-embedding avec une bonne probabilité telle que définie par :

$\left(1+eps\right)\parallel u-v\parallel ^{2}<\parallel p(u)-p(v)\parallel ^{2}<(1+eps)\parallel u-v\parallel ^{2}$

où u et v sont les lignes prises à partir d'un ensemble de données de forme[n_échantillons, n_caractéristiques] et p est une projection par une matrice gaussienne aléatoire N(0, 1) sous la forme[n_composants, n_caractéristiques] (ou une matrice d'Achlioptas éparse).

Le nombre minimum de composants pour garantir l'intégration eps est donné par :

$nComposants>=4\log(nEchantillons)/(eps^{2}/2-eps^{3}/3)$

Une implémentation en Python de ce théorème a été réalisée par scikit-learn. Ci-dessous, le script utilisé pour modéliser ce théorème.

print(__doc__)

import sys
from time import time
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from distutils.version import LooseVersion
from sklearn.random_projection import johnson_lindenstrauss_min_dim
from sklearn.random_projection import SparseRandomProjection
from sklearn.datasets import fetch_20newsgroups_vectorized
from sklearn.datasets import load_digits
from sklearn.metrics.pairwise import euclidean_distances

# `normed` is being deprecated in favor of `density` in histograms
if LooseVersion(matplotlib.__version__) >= '2.1':
    density_param = {'density': True}
else:
    density_param = {'normed': True}

# Part 1: plot the theoretical dependency between n_components_min and
# n_samples

# range of admissible distortions
eps_range = np.linspace(0.1, 0.99, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range)))

# range of number of samples (observation) to embed
n_samples_range = np.logspace(1, 9, 9)

plt.figure()
for eps, color in zip(eps_range, colors):
    min_n_components = johnson_lindenstrauss_min_dim(n_samples_range, eps=eps)
    plt.loglog(n_samples_range, min_n_components, color=color)

plt.legend(["eps = %0.1f" % eps for eps in eps_range], loc="lower right")
plt.xlabel("Number of observations to eps-embed")
plt.ylabel("Minimum number of dimensions")
plt.title("Johnson-Lindenstrauss bounds:\nn_samples vs n_components")

# range of admissible distortions
eps_range = np.linspace(0.01, 0.99, 100)

# range of number of samples (observation) to embed
n_samples_range = np.logspace(2, 6, 5)
colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(n_samples_range)))

plt.figure()
for n_samples, color in zip(n_samples_range, colors):
    min_n_components = johnson_lindenstrauss_min_dim(n_samples, eps=eps_range)
    plt.semilogy(eps_range, min_n_components, color=color)

plt.legend(["n_samples = %d" % n for n in n_samples_range], loc="upper right")
plt.xlabel("Distortion eps")
plt.ylabel("Minimum number of dimensions")
plt.title("Johnson-Lindenstrauss bounds:\nn_components vs eps")

# Part 2: perform sparse random projection of some digits images which are
# quite low dimensional and dense or documents of the 20 newsgroups dataset
# which is both high dimensional and sparse

if '--twenty-newsgroups' in sys.argv:
    # Need an internet connection hence not enabled by default
    data = fetch_20newsgroups_vectorized().data[:500]
else:
    data = load_digits().data[:500]

n_samples, n_features = data.shape
print("Embedding %d samples with dim %d using various random projections"
      % (n_samples, n_features))

n_components_range = np.array([300, 1000, 10000])
dists = euclidean_distances(data, squared=True).ravel()

# select only non-identical samples pairs
nonzero = dists != 0
dists = dists[nonzero]

for n_components in n_components_range:
    t0 = time()
    rp = SparseRandomProjection(n_components=n_components)
    projected_data = rp.fit_transform(data)
    print("Projected %d samples from %d to %d in %0.3fs"
          % (n_samples, n_features, n_components, time() - t0))
    if hasattr(rp, 'components_'):
        n_bytes = rp.components_.data.nbytes
        n_bytes += rp.components_.indices.nbytes
        print("Random matrix with size: %0.3fMB" % (n_bytes / 1e6))

    projected_dists = euclidean_distances(
        projected_data, squared=True).ravel()[nonzero]

    plt.figure()
    plt.hexbin(dists, projected_dists, gridsize=100, cmap=plt.cm.PuBu)
    plt.xlabel("Pairwise squared distances in original space")
    plt.ylabel("Pairwise squared distances in projected space")
    plt.title("Pairwise distances distribution for n_components=%d" %
              n_components)
    cb = plt.colorbar()
    cb.set_label('Sample pairs counts')

    rates = projected_dists / dists
    print("Mean distances rate: %0.2f (%0.2f)"
          % (np.mean(rates), np.std(rates)))

    plt.figure()
    plt.hist(rates, bins=50, range=(0., 2.), edgecolor='k', **density_param)
    plt.xlabel("Squared distances rate: projected / original")
    plt.ylabel("Distribution of samples pairs")
    plt.title("Histogram of pairwise distance rates for n_components=%d" %
              n_components)

    # TODO: compute the expected value of eps and add them to the previous plot
    # as vertical lines / region

plt.show()

La première figure [voir la figure] montre qu'avec un nombre croissant d'échantillons n_échantillons, le nombre minimal de dimensions n_composants augmente logarithmiquement afin de garantir une intégration eps.

La seconde figure [voir la figure] montre qu'une augmentation de la distorsion eps admissible permet de réduire drastiquement le nombre minimal de dimensions n_composants pour un nombre donné d'échantillons n_échantillons

Validation[modifier | modifier le code]

Nous validons les limites ci-dessus sur l'ensemble de données numériques ou sur l'ensemble de données du document texte des 20 groupes de discussion (fréquences de mots TF-IDF) :

pour l'ensemble de données numériques, quelques données de pixels de niveau de gris 8x8 pour 500 images numériques manuscrites sont projetées au hasard dans des espaces pour un plus grand nombre de dimensions n_composants.
pour les 20 groupes de discussion, environ 500 documents de 100 000 caractéristiques au total sont projetés à l'aide d'une matrice aléatoire clairsemée dans des espaces euclidiens plus petits avec différentes valeurs pour le nombre cible de dimensions n_composants.

L'ensemble de données par défaut est l'ensemble de données numériques. Pour exécuter l'exemple sur l'ensemble de données des vingt newsgroups, passez l'argument de ligne de commande - twenty-newsgroups à ce script.

Pour chaque valeur de n_composants, nous traçons un graphique :

Répartition 2D des paires d'échantillons avec des distances par paires dans les espaces d'origine et les espaces projetés en axes x et y respectivement.
Histogramme 1D du rapport de ces distances (projeté / original).

Voir les figures (3 à 8) dans les liens ci-dessous:

Nous pouvons voir que pour des valeurs faibles de n_composants la distribution est large avec de nombreuses paires déformées et une distribution asymétrique (due à la limite stricte du rapport zéro à gauche car les distances sont toujours positives) alors que pour des valeurs plus grandes de n_composants la distorsion est contrôlée et les distances sont bien préservées par la projection aléatoire.

Remarque[modifier | modifier le code]

Selon le théorème de Johnson-Lindenstrauss lemma, projeter 500 échantillons sans trop de distorsion nécessitera au moins plusieurs milliers de dimensions, quel que soit le nombre de caractéristiques de l'ensemble de données original.

Par conséquent, l'utilisation de projections aléatoires sur l'ensemble de données numériques qui n'a que 64 caractéristiques dans l'espace d'entrée n'a pas de sens : elle ne permet pas de réduire la dimensionnalité dans ce cas.

Sur les vingt groupes de discussion d'autre part, la dimensionnalité peut être réduite de 56436 à 10000 tout en préservant raisonnablement les distances par paires.

SRHT (Subsampled Randomized Hadamard Transform)[modifier | modifier le code]

SRHT est est une méthode de projection qui permet la réduction rapide des dimensions d’une matrice basée sur la matrice de Walsh-Hadamard. SRHT qui a été introduit par Woolf Liberty, Rohkin et Tygert.

Théorie[modifier | modifier le code]

Dans la méthode de projection Gaussienne, la matrice de projection utilisée est une matrice aléatoire non structurée ^[8]. Ce qui peut induire un coût élevé lorsqu’elle est multipliée par la matrice de départ. SRHT (subsampled randomized Hadamard transform) vient résoudre ce problème en utilisant une distribution structurée pour obtenir la matrice aléatoire, ce qui permet une multiplication plus rapide. La complexité de cette multiplication est de l’ordre de $O(mn\log(l))$ (où $m*n$ est la taille de la matrice de départ et la taille de la matrice de projection), contre $O(mnl)$ avec une matrice Gaussienne.

Implémentation matlab[modifier | modifier le code]

^[9]

function [C] = srht(A, s)
n =size(A, 2);
sgn = randi(2, [1, n]) * 2 - 3; % le contenu forme une moitié de valeurs à 1 et une autre à -1
A= bsxfun(@times,A, sgn); % inverser les signes pour toutes les colonnes
n = 2^(ceil(log2(n)));
C =(fwht(A' , n))';
idx = sort(randsmaple(n, s)); % trasformation de Wlash-Hadamard
C = C(:, idx); % sous-echantillonnage
C = C * (n / sqrt(s));

Cette méthode de projection est équivalente à la méthode SFRT (subsampled random Fourier transform) qui utilise la matrice de transformation de Fourier à la place de la matrice Walsh–Hadamard. Il est montré dans l’article^[10] que cette méthode de projection préserve les distances.

[1] ttp://helios.mi.parisdescartes.fr/~bouzy/Doc/AA1/RisqueReel.pdf

[2] ttp://www1.se.cuhk.edu.hk/~manchoso/papers/nucnorm_eb-nips13.pdf

[3] ttps://web.stanford.edu/~hastie/Papers/Ping/sketch_tr.pdf

[4] ttps://fr.wikipedia.org/wiki/Analyse_en_composantes_principales

[5] ttp://www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf?fbclid=IwAR0SEKOb7SwQKI2pPEl5SuwVHSwklZe--oEknLpMz2Jo59qp50m1wOSkYMM

[6] ttps://bioinfo-fr.net/lanalyse-en-composantes-principales-avec-r

[7] ttps://www.rdocumentation.org/packages/FactoMineR/versions/1.41/topics/PCA

[8] ttps://bioinfo-fr.net/lanalyse-en-composantes-principales-avec-r

[9] ttps://arxiv.org/pdf/1505.07570.pdf

[10] ttp://users.cms.caltech.edu/~jtropp/papers/HMT11-Finding-Structure-SIREV.pdf

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]