Cours - Sélection de variables

Ce chapitre correspond à 1 séance de cours.

[Diapositives du cours]

(le support écrit détaillé est en cours de finalisation)

Réduction de dimension : approches

Réduction du nombre de variables d’entrée : objectifs \(n\) données dans \(\mathbb{R}^m\) \(\rightarrow\) \(n\) données dans \(\mathbb{R}^k\), \(k \ll m\)

  1. Réduire le volume de données à traiter, tout en conservant au mieux l’information « utile » \(\leftarrow\) définir ce qu’est information utile.

  2. Améliorer le rapport signal / bruit en supprimant des variables non pertinentes \(\leftarrow\) définir ce qu’est une variable non pertinente.

  3. Réduire la complexité d’un modèle décisionnel (pour améliorer sa généralisation) : le nombre de variables explicatives en est une composante.

  4. Simplifier la mise en production et la maintenabilité de la solution en réduisant le nombre de variables à recueillir pour les nouvelles observations.

  5. Améliorer la « lisibilité » des données :

    • Mettre en évidence des relations entre variables ou groupes de variables

    • Permettre la visualisation \(\leftarrow\) définir ce qu’il faut mettre en évidence

  6. Répondre à la « malédiction de la dimension » (curse of dimensionality)

\(\Rightarrow\) Objectifs différents, critères différents \(\rightarrow\) méthodes différentes

Principales approches de la réduction du nombre de variables :

  1. Réduction de dimension

    • Modélisation à partir d’un nombre plus faible de variables obtenues par construction de nouvelles variables à partir des variables initiales (par ex. combinaisons linéaires)

    • Plus de flexibilité par rapport à la sélection

    • Mais les nouvelles variables sont rarement interprétables

  2. Sélection de variables (feature selection)

    • Sélection d’un sous-ensemble de \(k\) variables parmi les \(m\) variables initiales

    • Les variables sélectionnées gardent leur signification initiale

    • Mais solution potentiellement sous-optimale car cas particulier de la construction de nouvelles variables

Rappel sur la réduction de dimension : la dépendance entre les nouvelles variables et les variables initiales peut être

  1. Linéaire : trouver un sous-espace linéaire de dimension \(k\) dans l’espace initial \(\mathbb{R}^m\)

    • Pour des exemples de méthodes voir Chapitre 2: ACP, AFD, ACM

    _images/lineaire.png

  2. Non linéaire : trouver un sous-espace non linéaire de dimension faible

    • Pour des exemples de méthodes voir Chapitre 5: t-SNE, UMAP

    _images/manifold.png

Sélection de variables : approches

Principales approches

(voir aussi [MBN02], [TAL14])

  1. Filtrage : sélection réalisée sans faire appel à un modèle prédictif (ou décisionnel) ultérieur

    • Exemples de critères de sélection : maximisation de l’information mutuelle entre une variable d’entrée et la variable à prédire, minimisation de la redondance entre variables d’entrée

    _images/selectionFilter.png

    • Coût modéré car la sélection est faite en amont de l’apprentissage de modèles prédictifs

    • Mais coopération sous-optimale avec le modèle prédictif ultérieur car celui-ci n’intervient pas dans le processus de sélection

  2. Wrapper : coopération directe avec le modèle prédictif qui emploie les variables

    • Critère de sélection typique : sélection du groupe de variables qui maximise les performances du modèle prédictif ultérieur (modèle prédictif et groupe de variables « emballés » ensemble) sur un ensemble de données de validation

    _images/selectionWrapper.png

    • Coût élevé : pour évaluer chaque groupe de variables candidat il faut construire (apprendre) un modèle prédictif.

  3. Intégration (embedding) : l’opération de sélection de variables est intégrée à la méthode de construction de modèle prédictif

    • Exemple simple : régularisation \(L_1\) dans la fonction de coût du modèle prédictif

    _images/selectionIntegrated.png

    Fig. 132 Effet de la régularisation \(L_1\) : à gauche, sans régularisation, la frontière est oblique (dépend aussi bien de \(X_1\) que de \(X_2\)) ; à droite, avec une régularisation \(L_1\) suffisante, la frontière est verticale (ne dépend plus de \(X_2\))

    • Pas de surcoût par rapport à la construction du modèle prédictif mais ne peut pas être utilisée avec tout type de modèle

Sélection de variables : exploration de l’espace de recherche

Choisir \(k\) variables parmi \(m\) \(\rightarrow\) espace de recherche \(O(C_m^k) \left(= \frac{m!}{k! (m-k)!}\right)\) \(\Rightarrow\) des solutions approximatives (sous-optimales) sont préférées (parfois indispensables) :

  1. Critère de « pertinence » exprimable par variable initiale individuelle (indépendamment des autres), puis sélection des \(k\) variables de pertinence optimale \(\Rightarrow\) complexité \(O(m)\)

  2. Critère de « pertinence » exprimable par ensemble de variables initiales (par ex. la redondance pour approche filtrage ou performance globale pour approche wrapper)

    1. Méthodes incrémentales (par cooptation) :

      • On démarre avec une seule variable (par ex. choisie avec la méthode précédente)

      • A chaque itération on ajoute une variable, celle qui forme le meilleur ensemble avec les variables déjà sélectionnées aux itérations précédentes

      • Complexité \(O(m^2)\) (dans le détail dépend du nombre de variables à ajouter)

    2. Méthodes décrémentales (par élimination) :

      • On démarre avec la totalité des variables

      • A chaque itération on teste toutes les combinaisons avec une variable en moins par rapport à l’itération précédente et on choisit celle qui est optimale (on élimine donc une variable)

      • Complexité \(O(m^2)\) (dans le détail dépend du nombre de variables à éliminer)

L’exploration de l’espace de recherche est explicite dans l’approche de filtrage et l’approche wrapper, en revanche elle est absente dans l’approche intégration (on peut considérer que dans cette approche l’exploration est implicite).

Critères de sélection

Critères de sélection de variables explicatives :

  1. Propriétés intrinsèques d’une variable (d’entrée)

    • Variance de la variable : si très faible, la variable explique une faible part de la variance des observations et est éliminée

  2. Caractérisation d’une variable d’entrée par rapport à la variable de sortie

    • Qualité de prédictionsont choisies individuellement les variables d’entrée qui « expliquent le mieux » la variable de

      sortie

  3. Caractérisation d’un groupe de variables d’entrée par rapport à la variable de sortie

    • Qualité de prédiction : est choisi le groupe qui « explique le mieux » la variable de sortie

  4. Caractérisation d’un groupe de variables d’entrée entre elles et par rapport à la variable de sortie

    • Qualité de prédiction et réduction de la redondance : est choisi le groupe qui présente le meilleur compromis entre ces deux aspects

Critère de variance

Propriété intrinsèque d’une variable, ne s’intéresse pas à la relation à une autre variable (la variable de sortie)

\(n\) observations variable \(X\) \(\Rightarrow\) moyenne et variance de l’échantillon :

\[\bar{x} = \frac{1}{n} \sum_{i=1}^n x_i, \qquad \textrm{Var}(x) = \frac{1}{n} \sum_{i=1}^n (x_i - \bar{x})^2\]

Idée : les variables de variance trop faible expliquent trop peu de la variance des observations et sont éliminées \(\leftarrow\) comme en ACP les axes associés aux valeurs propres les plus faibles de la matrice des covariances empiriques

La variance dépend de l’unité de mesure : à partir d’un même échantillon de longueurs on obtient une variance bien plus grande si les valeurs sont exprimées en mm plutôt qu’en mètres \(\rightarrow\) pour éviter l’arbitraire dans la comparaison des « dispersions » de variables différentes mieux vaut utiliser le coefficient de variation = \(\frac{\text{écart-type}}{\text{moyenne}}\) (défini pour moyenne non nulle)

Risque : une variable (très) discriminante peut être de faible variance (ou de faible coefficient de variation), comme nous l’avons déjà vu pour l’analyse discriminante

Critères de qualité prédictive individuelle

Idée : dans quelle mesure la variable d’entrée \(X\) « explique » (ou prédit bien) la variable de sortie \(Y\)?

Différents critères de qualité prédictive individuelle ou « pertinence », par exemple :

  1. Corrélation linéaire : \(r = \frac{\textrm{Cov}(X,Y)}{\sigma(X) \sigma(Y)} \in [-1, 1]\), \(\textrm{Cov}\) étant la covariance, \(\sigma\) l’écart-type

  2. Test du \(\chi^2\) d’indépendance (\(\rightarrow\) revoir Analyse des correspondances binaires)

    • \(X\) et \(Y\) variables discrètes, prenant chacune un nombre fini de valeurs

    • \(N\) observations au total: pour \(n_{ij}\) observations \(X\) prend sa \(i\)-ème valeur et \(Y\) sa \(j\)-ème valeur, on note \(n_{i\_}=\sum_j n_{ij}\), \(n_{\_j}=\sum_i n_{ij}\), \(e_{ij} = \frac{n_{i\_} n_{\_j}}{N}\)

    • Pour chaque variable \(X\) on calcule \(t_X = \sum_{i,j} \frac{(n_{ij} - e_{ij})^2}{e_{ij}}\) (écart entre la distribution conjointe de \(X,Y\) et la distribution correspondant à l’indépendance)

    • On n’applique pas le test d’indépendance mais on trie les variables \(X\) en ordre décroissant de leurs valeurs \(t_X\), puis on élimine les variables \(X\) pour lesquelles ces valeurs sont trop faibles

Relations entre deux variables: bien représentées (en haut) ou mal représentées (en bas) par la correlation linéaire (illustration issue de [VMK18]_)

Fig. 133 Relations entre deux variables: bien représentées (en haut) ou mal représentées (en bas) par la correlation linéaire (illustration issue de [VMK18])

  1. Information mutuelle (qu’apporte la connaissance de \(X\) à la connaissance de \(Y\) ?):

    • \(X\) et \(Y\) discrètes: \(I(X;Y) = \sum_{x,y} P(x,y) \log\frac{P(x,y)}{P(x) P(y)}\)

    • \(X\) et \(Y\) continues: \(I(X;Y) = \int_{\mathbb{R}}\int_{\mathbb{R}} p(x,y) \log \frac{p(x,y)}{p(x) p(y)} dx dy\)

On garde les \(k\) variables d’entrée qui sont individuellement les plus pertinentes, ou celles dont la pertinence est supérieure à un seuil, ou à la moyenne, ou on garde les \(k\) premiers déciles, etc.

Insuffisance de cette approche de sélection de \(k \ll m\) variables parmi \(m\) :

  • Les \(k\) variables sont individuellement les plus « explicatives »

  • mais souvent redondantes : certaines apportent \(\sim\) la même information que d’autres

  • Des variables individuellement moins « explicatives » mais plus complémentaires aux autres ne sont pas sélectionnées \(\Rightarrow\) il y a un potentiel d’amélioration !

Qualité prédictive de groupe

Caractériser un groupe de variables d’entrée par rapport à leur capacité à expliquer la variable de sortie

  • Comparer deux groupes quelconques : espace de recherche trop large

  • Comparer un groupe au même groupe avec une variable en plus pour caractériser l’apport de cette variable

Suivant l’approche :

  1. Wrapper :

    • Avec chaque groupe de variables candidat on développe un modèle décisionnel

    • On choisit le groupe pour lequel la performance du modèle décisionnel est meilleure

  2. Filtrage : extension au groupe de critères de qualité prédictive individuelle

    • Corrélation linéaire avec la variable de sortie : valeur moyenne entre variables du groupe

    • Information mutuelle avec la variable de sortie : valeur moyenne entre variables du groupe, ou extension à plusieurs variables de l’information mutuelle :

    (55)\[I(X^{(m)};Y) = \int_{\mathbb{R}}\cdots\int_{\mathbb{R}} p(x_1,\ldots,x_m,y) \log \frac{p(x_1,\ldots,x_m,y)}{p(x_1,\ldots,x_m) p(y)} dx_1\cdots dx_m dy\]

    (\(X^{(m)}\) étant un ensemble de \(m\) variables d’entrée)

Qualité prédictive de groupe et réduction de la redondance

Constats lors de l’extension à un groupe de variables de critères de qualité prédictive individuelle :

  1. Moyenner des corrélations, ou des informations mutuelles entre variables deux à deux, fait perdre en sélectivité \(\Rightarrow\) faibles écarts de qualité prédictive entre groupes de variables \(\Rightarrow\) sélection d’un nombre élevé de variables, entre lesquelles il y a de la redondance

  2. Calcul peu fiable de l’information mutuelle avec beaucoup de variables car nombre insuffisant d’observations (devrait croître exponentiellement avec nombre de variables)

    • Exemple simple unidimensionnel : considérons deux variables indépendantes \(X\) et \(Y\), chacune suivant une loi normale, faisons varier la taille de l’échantillon et estimons l’information mutuelle entre \(X\) et \(Y\) à partir de l’échantillon :

    \(n\):

    10

    20

    100

    1000

    image3

    image4

    image5

    image6

    \(I(X;Y)\):

    0.07

    0.025

    0.0135

    0.002

    \(\Rightarrow\) Un échantillon faible fait augmenter artificiellement l’information mutuelle \(\Rightarrow\) des variables non pertinentes semblent pertinentes et sont ainsi sélectionnées \(\Rightarrow\) sélection d’un nombre excessif de variables, entre lesquelles il y a de la redondance

Une solution est apportée par minimum Redundancy and Maximum Relevance (mRMR, [PLD05]) dont les objectifs sont :

  1. Augmenter la qualité prédictive mesurée par l’information mutuelle entre les variables explicatives sélectionnées et la variable de sortie : \(D = \frac{1}{m} \sum_i I(X_i;Y)\)

  2. Tout en réduisant la redondance des variables sélectionnées, mesurée par l’information mutuelle moyenne entre ces variables : \(R = \frac{1}{m^2} \sum_{i,j} I(X_i;X_j)\)

mRMR = sélection incrémentale avec comme critère

  • Mutual information difference (MID): \(\max_i(D-R)\), ou

  • Mutual information quotient (MIQ): \(\max_i\frac{D}{R}\)

Dans [PLD05] est montré que mRMR est équivalent à l’utilisation de l’information mutuelle (55) sans l’inconvénient du calcul peu fiable sur un petit échantillon multidimensionnel

Autres méthodes suivant un principe similaire : MIMR (Maximum Information and Minimum Redundancy [LSM12]), MRMR (Maximum Relevance and Minimum Redundancy [ZAW19]

Quels critères de sélection pour quelles approches

L’approche de filtrage peut faire appel à tous les critères de sélection explicites mentionnés :

  1. Propriétés intrinsèques d’une variable (d’entrée) et notamment la variance.

  2. Caractérisation de chaque variable d’entrée par rapport à la variable de sortie, en utilisant par ex. la corrélation ou l’information mutuelle.

  3. Caractérisation d’un groupe de variables d’entrée par rapport à la variable de sortie, en utilisant par ex. l’information mutuelle (55).

  4. Caractérisation d’un groupe de variables d’entrée entre elles et par rapport à la variable de sortie, en utilisant par ex. mRMR.

Dans l’approche wrapper l’évaluation d’un groupe de variables est faite uniquement à travers les performances de validation du modèle prédictif qui emploie ce groupe de variables. Cette approche n’emploie pas les propriétés intrinsèques d’une variable d’entrée, évalue en général un groupe de variables d’entrée (et non une variable d’entrée seule) par rapport à la variable de sortie, et ne s’intéresse pas explicitement à la redondance entre des variables d’entrée.

Dans l’approche d’intégration de la sélection de variables à la méthode de construction de modèle prédictif, l’évaluation des variables est faite de façon implicite dans l’algorithme d’optimisation des paramètres du modèle prédictif ; on ne fait donc pas appel aux critères de sélection explicites mentionnés.

Conclusion

La sélection de variables peut présenter des intérêts multiples : réduction du bruit, amélioration de la généralisation, amélioration de la lisibilité, simplification de la mise ne production, etc.

L’approche filtrage est moins coûteuse mais potentiellement moins performante que l’approche wrapper.

Une sélection de variables est intégrée à certaines méthodes de modélisation prédictive (à découvrir dans RCP209).

Combiner optimisation de la qualité prédictive et réduction de la redondance dans une approche de filtrage peut constituer un bon compromis entre coût et performance.

[LSM12]

Li, C., V. P. Singh, and A. K. Mishra. Entropy theory-based criterion for hydrometric network evaluation and design: Maximum information minimum redundancy2. Water Resources Research, 48(5), 2012.

[MBN02]

Molina, L., L. Belanche, and A. Nebot. Feature selection algorithms: a survey and experimental evaluation. In 2002 IEEE International Conference on Data Mining, 2002. Proceedings, pages 306–313, 2002.

[PLD05] (1,2)

Peng, H., F. Long, and C. Ding. Feature selection based on mutual information: Criteria of max-dependency, max-relevance, and min-redundancy. IEEE Trans. Pattern Anal. Mach. Intell., 27(8) :1226–1238, Aug. 2005.

[TAL14]

Tang, J., S. Alelyani, and H. Liu. Feature selection for classification: A review. In Data Classification: Algorithms and Applications, pages 37–64. 2014.

[VMK18]

Vu, T., A. Mishra, and G. Kumar. Information entropy suggests stronger nonlinear associations between hydro-meteorological variables and enso. Entropy, 20 :38, 01 2018.

[ZAW19]

Zhao, Z., R. Anand, and M. Wang. Maximum relevance and minimum redundancy feature selection methods for a marketing machine learning platform, 2019.