Analyse de données vectorielles et recherche de similarité
Note
La multiplication des données numériques (textes, images, vidéos, données issues de capteurs ou d’applications métiers) pose un défi majeur : comment représenter ces données pour les comparer et les analyser efficacement ?
La solution la plus utilisée consiste à projeter ces données dans un espace vectoriel : chaque objet est représenté par un vecteur de nombres réels.
Cela permet d’utiliser les outils de l’algèbre linéaire et de la statistique pour :
- rechercher des objets similaires,
- regrouper ou classifier des individus,
- identifier des anomalies, fraudes ou défauts de fabrication (vecteurs très éloignés).
Aujourd’hui, ces méthodes sont utilisées partout : moteur de recherche, recommandation Netflix/Spotify, détection de fraude bancaire, IA générative (ChatGPT encode les phrases en vecteurs pour raisonner dessus).
Fondements mathématiques
Vecteurs et espaces vectoriels
Un vecteur est une suite ordonnée de nombres réels :
\vec{v} = [v_1, v_2, \dots, v_n] \in \mathbb{R}^n
Un espace vectoriel est un ensemble de vecteurs où s’appliquent deux opérations :
- addition de vecteurs,
- multiplication par un scalaire.
Exemple :
- Un produit alimentaire décrit par (protéines, sucres, graisses, sel, fibres) est un vecteur à 5 dimensions.
- Une image de 28×28 pixels peut être représentée par un vecteur de dimension 784.
Normes
En géométrie, la norme est une extension de la valeur absolue des nombres aux vecteurs. Elle permet de mesurer la longueur commune à toutes les représentations d'un vecteur dans un espace affine.
Elle définit aussi une distance entre deux vecteurs, invariante par translation et compatible avec la multiplication externe.
Norme L_2 (euclidienne)
Dans le plan, si le vecteur \vec{v} a pour coordonnées (x , y), sa norme s'écrit :
||\vec{v}|| = \sqrt{x^2 + y^2}
par extension à n dimensions
||\vec{v}||_2 = \sqrt{\sum_{i=1}^n v_i^2}
Norme L_1 (Manhattan)
||\vec{v}||_1 = \sum_{i=1}^n |v_i|
Distances
À partir d’une norme, on définit une distance entre vecteurs \vec{u} et \vec{v}.
La distance euclidienne :
d(\vec{u},\vec{v}) = ||\vec{u}-\vec{v}||_2
Produit scalaire et similarité cosinus
Le produit scalaire (inner product ou dot product en anglais) est une opération qui prend deux vecteurs et donne un scalaire (nombre).
\vec{u} \cdot \vec{v} = \sum_{i=1}^n u_i v_i
ou
\vec{u} \cdot \vec{v} = ||\vec{u}|| \cdot ||\vec{v}|| \cdot cos(\theta)
Le produit scalaire relie longueurs et angles. Il permet d'exploiter les notions de la géométrie euclidienne traditionnelle : longueurs, angles, orthogonalité en deux, trois ou plus de dimensions.
La similarité cosinus est donnée par :
\cos(\theta) = \frac{\vec{u} \cdot \vec{v}}{||\vec{u}|| \cdot ||\vec{v}||}
Elle est utilisée pour comparer deux vecteurs indépendamment de leur taille (ex. documents textuels).
Si = 0 soit θ = 90°, les vecteurs sont orthogonaux (perpendiculaires) Il n'y a aucune similarité.
Si = 1 les vecteurs pointent exactement dans la même direction (très similaires).
Si = -1 les vecteurs pointent dans des directions opposées (complètement dissemblables).
Statistique multivariée
Moyenne, variance et covariance
Pour une variable X :
Moyenne : \mu = \frac{1}{n}\sum x_i
Variance : \sigma^2 = \frac{1}{n}\sum (x_i - \mu)^2
Pour deux variable X et Y
Covariance : \text{Cov}(X,Y) = E[(X-\mu_X)(Y-\mu_Y)]
La covariance mesure comment deux variables X et Y varient ensemble.
E est l'esperance (ou moyenne théorique). En statistique pratique, on remplace E[X] par la moyenne empirique
D'où de manière empirique
\widehat{\mathrm{Cov}}(X,Y) = \frac{1}{n} \sum_{i=1}^n (x_i - \bar{x})(y_i - \bar{y})
Si X et Y sont corrélés alors la covariance est positive. Si la covariance est nulle il n'y a pas de lien. Si la covariance est négative alors la probabilité est trés faible.
Corrélation est la covariance normalisée sur une échelle de -1 à 1.
\rho(X,Y) = \frac{\mathrm{Cov}(X,Y)}{\sigma_X \sigma_Y}
Ces mesures servent à comprendre la dispersion et les corrélations.
Normalisation des données
Avant de comparer des vecteurs, il faut rendre les dimensions comparables en grandeur.
Min-Max scaling :
x' = \frac{x - \min}{\max - \min}
Standardisation (z-score) :
x' = \frac{x - \mu}{\sigma}
Réduction de dimension
Lorsqu’une base de données contient de nombreuses variables (ou dimensions), il devient difficile d’analyser efficacement les données. On parle alors de malédiction de la dimensionnalité : plus il y a de dimensions, plus les calculs sont coûteux, et plus il est difficile de visualiser ou d’interpréter les résultats.
La réduction des dimensions vise donc à simplifier l’espace de représentation en conservant l’information la plus pertinente.
- Alléger les données : diminuer la taille et la complexité des tables.
- Améliorer les performances : réduire le temps de calcul dans les requêtes analytiques et les algorithmes.
- Faciliter la visualisation : rendre possible une représentation graphique (2D, 3D).
- Éliminer le bruit : supprimer les variables redondantes ou peu informatives.
Il existe deux grandes familles d’approches
Sélection de variables (feature selection) : On conserve uniquement les dimensions les plus pertinentes :
- Analyse de corrélation : suppression d'une des variables fortement corrélées.
- Méthodes statistiques (tests d’hypothèses, chi², ANOVA) pour éliminer les variables peu discriminantes.
- Méthodes incrémentales : ajout ou retrait progressif de variables en fonction de critères de qualité (erreur de prédiction, pouvoir explicatif)
Extraction de nouvelles dimensions (feature extraction)
On crée de nouvelles variables synthétiques à partir des variables initiales :
-
ACP (Analyse en Composantes Principales, PCA)
- Transforme les données en un nouvel espace en combinant linéairement les variables.
- Les premières composantes expliquent la plus grande partie de la variance.
- Très utilisée en statistique et en apprentissage automatique.
-
Analyse factorielle : Identifie des facteurs latents expliquant les corrélations entre variables.
-
t-SNE, UMAP (méthodes modernes) : Plus adaptées pour la visualisation et la détection de structures non linéaires dans des données complexes.
Théorie de la similarité
Problème des plus proches voisins
Pour un vecteur \vec{q}, trouver les k vecteurs les plus proches parmi une base de données.
Méthode naïve : comparer q avec tous les vecteurs un par un.
Mais quand la dimension n augmente, les distances entre points tendent à se ressembler,
PostgreSQL
<->Distance L2<+>Distance L1<#>Produit scalaire<=>Similarité cosinus
Exercice
- Construire une base de produits avec vecteurs nutritionnels.
- Normaliser les données par z-score.
- Créer un index HNSW.
- Classer un produit inconnu avec k-NN.
- Détecter les produits extrêmes.