Apprentissage Automatique

1. Évaluation du clustering

L’évaluation du clustering vise à mesurer la qualité des clusters obtenus sur un jeu de données non étiquetées.

2. Contexte

• Le clustering est un apprentissage non supervisé : pas d’étiquettes de classes disponibles.
• On partitionne un ensemble de données $\mathcal{D}$ de $n$ points en $K$ clusters $\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_K$.
• $d$ est une distance sur l’espace $\chi$.
• $k(\vec{x})$ désigne l’indice du cluster auquel le point $\vec{x}$ est assigné.
• Pas de vérité fondamentale pour comparer les résultats.

3. Critères essentiels pour évaluer un clustering

1. Homogénéité (cohésion interne) :
   Les points d’un même cluster doivent être proches/similaires.

2. Séparabilité (cohésion externe) :
   Les clusters doivent être distants les uns des autres.

4. Notions clés

5. Homogénéité (Tightness)

• Pour un cluster $\mathcal{C}_k$, l’homogénéité est la moyenne des distances des points au centroïde :

$$h(\mathcal{C}_k) = \frac{1}{|\mathcal{C}_k|} \sum_{\vec{x} \in \mathcal{C}_k} d(\vec{x}, \vec{\mu}_k)$$

• L’homogénéité globale du clustering est la moyenne des homogénéités des clusters :

$$H = \frac{1}{K} \sum_{k=1}^K h(\mathcal{C}_k)$$

• Plus $H$ est faible, plus les clusters sont compacts.

6. Séparabilité

• La séparabilité entre deux clusters $\mathcal{C}_k$ et $\mathcal{C}_l$ est la distance entre leurs centroïdes :

$$s(\mathcal{C}_k, \mathcal{C}_l) = d(\vec{\mu}_k, \vec{\mu}_l)$$

• La séparabilité globale peut être définie comme la moyenne (ou minimum) des distances inter-centroïdes.
• Plus la séparabilité est grande, mieux les clusters sont distincts.

À retenir : Un bon clustering maximise la séparabilité entre clusters tout en minimisant l’homogénéité (distance intra-cluster).

1. DBSCAN : algorithme de clustering basé sur la densité

Principe clé : DBSCAN regroupe les points en clusters selon leur densité locale, définie par le nombre de points dans un voisinage de rayon $\varepsilon$.

2. Définitions essentielles

3. Fonctionnement de DBSCAN

1. Identification des points cœur : repérer tous les points avec au moins MinPts dans leur voisinage $\varepsilon$.
2. Formation des clusters : connecter les points cœur entre eux et avec leurs points frontières.
3. Élimination du bruit : les points bruit sont exclus du clustering.

4. Propriétés et avantages

• Robustesse au bruit : DBSCAN identifie explicitement les points bruit, ce qui le rend résistant aux données aberrantes.
• Détection de clusters de forme arbitraire : contrairement aux méthodes basées sur la distance euclidienne seule, DBSCAN peut détecter des clusters non sphériques.
• Pas besoin de spécifier le nombre de clusters a priori.

À retenir : Un point est un point cœur s’il a au moins MinPts voisins dans un rayon $\varepsilon$ ; les clusters sont formés autour de ces points cœur, tandis que les points bruit sont exclus.

5. Paramètres clés

6. Résumé des étapes

1. Réduction de la dimensionalité : concepts et méthodes

La réduction de la dimensionalité consiste à transformer une représentation des données $X \in \mathbb{R}^{n \times p}$ en une représentation $X^* \in \mathbb{R}^{n \times m}$ avec $m \ll p$. L'objectif est de simplifier les données tout en conservant l'essentiel de l'information.

2. Raisons principales de réduire la dimensionnalité

3. Idée clé

Réduire la dimensionnalité permet d'améliorer l'efficacité, la compréhension et la robustesse des modèles tout en facilitant la visualisation des données.

4. Méthodes courantes (à connaître)

• Projection linéaire : Trouver un sous-espace de dimension $m$ qui conserve la variance (ex. ACP).
• Méthodes non linéaires : Capturer des structures complexes (ex. t-SNE, Isomap).
• Sélection de variables : Choisir un sous-ensemble pertinent de variables originales.

5. Exemple : Détermination des paramètres dans DBSCAN (contexte de données haute dimension)

• Pour un point, la distance à son $k$-ième plus proche voisin est utilisée pour estimer la densité locale.
• Les points dans un cluster ont des distances similaires à leur $k$-ième voisin.
• Les points de bruit ont des distances plus élevées.
• Tracer la distance triée des points au $k$-ième voisin aide à fixer le paramètre $\varepsilon$ (EPS) et $MinPts$.

Cette approche illustre l'importance de la gestion de la dimensionnalité et des distances dans les algorithmes non supervisés, notamment en haute dimension.

1. Raisons pour réduire la dimensionalité

• Visualisation et compréhension : Faciliter l’analyse de données complexes en réduisant leur dimension.
• Coût d’acquisition : Réduire le nombre de caractéristiques diminue les coûts de collecte, stockage et traitement.
• Élimination des attributs non pertinents : Supprimer les variables inutiles réduit le bruit et améliore la performance des modèles.

2. Méthodes pour réduire la dimensionalité

Deux grandes approches :

3. Sélection des variables : catégories principales

1. Méthodes de filtrage
2. Méthodes de containeur (wrapping methods)
3. Méthodes embarquées (embedded methods)

4. Méthodes de filtrage

• Évaluer la pertinence de chaque variable indépendamment par rapport à la variable cible $y$.
• Critères possibles :
  • Corrélation avec $y$
  • Test statistique (ex. test du $\chi^2$ pour classification)
  • Variance (supposer que variables à forte variance sont plus informatives)

5. Méthodes de containeur

• Objectif : trouver le meilleur sous-ensemble de variables pour un modèle donné.
• Appelée aussi sélection de sous-ensemble (subset selection).
• Deux approches principales présentées :

À retenir : La sélection de variables vise à réduire la dimension en éliminant les variables non pertinentes, ce qui améliore la performance et réduit le coût des modèles.

1. Sélection des variables

• Recherche descendante :
  Partir de l’ensemble de toutes les variables, retirer une par une celles qui améliorent le plus la performance, jusqu’à ne plus pouvoir l’améliorer.

• Méthodes embarquées :
  Apprennent simultanément avec le modèle quelles variables inclure.

  • Modèles paramétriques parcimonieux (certains coefficients nuls).
  • Variables avec coefficient nul sont éliminées.
  • Exemple clé : Lasso.
  • Exemple de méthode : Recursive Feature Elimination (RFE).

2. Extraction des variables : Analyse en Composantes Principales (ACP / PCA)

• Définition :
  Méthode d’apprentissage non supervisé qui vise à réduire la dimensionnalité des données tout en minimisant la perte d’information.

• Objectif :
  Trouver un espace de dimension réduite où la variance des données projetées est maximisée.

• Hypothèse :
  Les données sont centrées (moyenne nulle). Sinon, on centre par :

  $$X \leftarrow X - \mu$$

• Standardisation :

  • Centrer la moyenne à 0.
  • Centrer la variance à 1 (chaque variable a variance 1).

• Projection sur une direction :
  Soit $w$ un vecteur unité ($\|w\|=1$), la projection de $X$ sur $w$ est :

  $$z = X w$$

• Variance de la projection :
  La variance de $z$ est calculée en fonction de $w$ et $X$ (maximiser cette variance pour choisir $w$).

À retenir : L’ACP cherche une base orthogonale où les projections des données ont une variance maximale, ce qui permet de réduire la dimension tout en conservant l’essentiel de l’information.