Sélection des fonctionnalités

En apprentissage automatique, la sélection de caractéristiques consiste à choisir un sous-ensemble de caractéristiques pertinentes (variables, prédicteurs) pour la construction du modèle. Les techniques de sélection de caractéristiques sont utilisées pour plusieurs raisons :

simplification des modèles pour les rendre plus faciles à interpréter,
des temps d'entraînement plus courts,
pour éviter la malédiction de la dimensionnalité ,
améliorer la compatibilité des données avec une certaine classe de modèles d'apprentissage,
pour encoder les symétries inhérentes présentes dans l'espace d'entrée.

Le principe fondamental de la sélection de caractéristiques repose sur l'idée que les données contiennent parfois des caractéristiques redondantes ou non pertinentes , qui peuvent donc être supprimées sans entraîner de perte d'information significative. Redondance et non-pertinence sont deux notions distinctes, car une caractéristique pertinente peut être redondante en présence d'une autre caractéristique pertinente avec laquelle elle est fortement corrélée.

L'extraction de caractéristiques crée de nouvelles caractéristiques à partir des fonctions des caractéristiques originales, tandis que la sélection de caractéristiques identifie un sous-ensemble de ces caractéristiques. Les techniques de sélection de caractéristiques sont souvent utilisées dans les domaines où le nombre de caractéristiques est élevé et le nombre d'échantillons (points de données) relativement faible.

Introduction

Un algorithme de sélection de caractéristiques peut être vu comme la combinaison d'une technique de recherche pour proposer de nouveaux sous-ensembles de caractéristiques, et d'une mesure d'évaluation qui attribue un score aux différents sous-ensembles. L'algorithme le plus simple consiste à tester chaque sous-ensemble possible de caractéristiques afin de trouver celui qui minimise le taux d'erreur. Cette recherche exhaustive de l'espace est difficilement calculable, sauf pour les ensembles de caractéristiques les plus petits. Le choix de la métrique d'évaluation influence fortement l'algorithme, et ce sont ces métriques qui distinguent les trois principales catégories d'algorithmes de sélection de caractéristiques : les méthodes enveloppantes, les filtres et les méthodes intégrées.

Les méthodes d'encapsulation utilisent un modèle prédictif pour évaluer des sous-ensembles de caractéristiques. Chaque nouveau sous-ensemble sert à entraîner un modèle, lequel est ensuite testé sur un ensemble de validation. Le nombre d'erreurs commises sur cet ensemble (le taux d'erreur du modèle) détermine le score du sous-ensemble. Comme les méthodes d'encapsulation entraînent un nouveau modèle pour chaque sous-ensemble, elles sont très gourmandes en ressources de calcul, mais offrent généralement le meilleur ensemble de caractéristiques pour ce type de modèle ou ce problème typique.
Les méthodes de filtrage utilisent une mesure indirecte plutôt que le taux d'erreur pour évaluer un sous-ensemble de caractéristiques. Cette mesure est choisie pour sa rapidité de calcul, tout en préservant l'utilité de l'ensemble de caractéristiques. Parmi les mesures courantes , on trouve l' information mutuelle , l' information mutuelle ponctuelle , le coefficient de corrélation de Pearson , les algorithmes basés sur Relief et la distance inter/intra-classe ou les scores des tests de signification pour chaque combinaison classe/caractéristique . Les filtres sont généralement moins gourmands en ressources de calcul que les méthodes d'encapsulation, mais ils produisent un ensemble de caractéristiques non adapté à un type spécifique de modèle prédictif . Ce manque d'adaptation signifie qu'un ensemble de caractéristiques issu d'un filtre est plus général que celui issu d'une méthode d'encapsulation, ce qui se traduit généralement par des performances de prédiction inférieures. Cependant, cet ensemble de caractéristiques ne contient pas les hypothèses d'un modèle de prédiction et est donc plus utile pour mettre en évidence les relations entre les caractéristiques. De nombreux filtres proposent un classement des caractéristiques plutôt qu'un sous-ensemble explicite des meilleures caractéristiques, et le seuil de ce classement est déterminé par validation croisée . Les méthodes de filtrage sont également utilisées comme étape de prétraitement pour les méthodes d'encapsulation, permettant ainsi d'appliquer ces dernières à des problèmes plus complexes. Une autre approche courante est l'algorithme d'élimination récursive de caractéristiques , fréquemment utilisé avec les machines à vecteurs de support pour construire un modèle de manière itérative et supprimer les caractéristiques ayant un faible poids.
Les méthodes intégrées regroupent un ensemble de techniques qui effectuent la sélection de caractéristiques lors de la construction du modèle. La méthode LASSO , utilisée pour construire un modèle linéaire, illustre parfaitement cette approche en pénalisant les coefficients de régression par une pénalité L1, ce qui annule un grand nombre d'entre eux. Toute caractéristique ayant un coefficient de régression non nul est « sélectionnée » par l'algorithme LASSO. Parmi les améliorations apportées à LASSO, on peut citer Bolasso, qui utilise le bootstrap pour l'échantillonnage ; la régularisation Elastic Net , qui combine la pénalité L1 de LASSO avec la pénalité L2 de la régression Ridge ; et FeaLect, qui attribue un score à toutes les caractéristiques en fonction d'une analyse combinatoire des coefficients de régression. AEFS étend LASSO aux cas non linéaires grâce à des auto-encodeurs. Ces approches se situent généralement entre les filtres et les méthodes d'encapsulation en termes de complexité de calcul.

En analyse de régression traditionnelle , la méthode de sélection de variables la plus courante est la régression pas à pas , une technique d'encapsulation. Cet algorithme glouton ajoute la meilleure variable (ou supprime la moins performante) à chaque itération. La principale difficulté réside dans la détermination du moment d'arrêt de l'algorithme. En apprentissage automatique, on utilise généralement la validation croisée . En statistique, certains critères sont optimisés, ce qui engendre le problème inhérent d'imbrication. Des méthodes plus robustes ont été explorées, telles que la méthode par séparation et évaluation ( branch and bound) et les réseaux linéaires par morceaux.

sélection de sous-ensemble

La sélection de sous-ensembles évalue la pertinence d'un ensemble de caractéristiques. Les algorithmes de sélection de sous-ensembles se divisent en trois catégories : les méthodes d'encapsulation, les filtres et les méthodes intégrées. Les méthodes d'encapsulation utilisent un algorithme de recherche pour explorer l'espace des caractéristiques potentielles et évaluer chaque sous-ensemble en appliquant un modèle à celui-ci. Ces méthodes peuvent être gourmandes en ressources de calcul et présentent un risque de surapprentissage. Les filtres fonctionnent de manière similaire aux méthodes d'encapsulation, mais au lieu d'être évalués par rapport à un modèle, ils évaluent un filtre plus simple. Les techniques intégrées sont spécifiques à un modèle et y sont intégrées.

De nombreuses méthodes de recherche populaires utilisent l'algorithme glouton de recherche locale , qui évalue itérativement un sous-ensemble candidat de caractéristiques, puis le modifie et vérifie si le nouveau sous-ensemble représente une amélioration par rapport au précédent. L'évaluation des sous-ensembles nécessite une métrique de score qui attribue une note à chaque sous-ensemble de caractéristiques. La recherche exhaustive étant généralement impraticable, à un certain seuil défini par l'implémenteur (ou l'opérateur), le sous-ensemble de caractéristiques ayant obtenu le score le plus élevé jusqu'à ce point est sélectionné comme sous-ensemble satisfaisant. Le critère d'arrêt varie selon l'algorithme ; il peut s'agir, par exemple, du dépassement d'un seuil par le score d'un sous-ensemble ou du dépassement du temps d'exécution maximal autorisé du programme.

Les techniques de recherche alternatives sont basées sur la recherche de projections ciblées qui trouvent des projections de faible dimension des données qui obtiennent un score élevé : les caractéristiques qui ont les plus grandes projections dans l’espace de dimension inférieure sont ensuite sélectionnées.

Les méthodes de recherche comprennent :

Deux métriques de filtrage couramment utilisées pour les problèmes de classification sont la corrélation et l'information mutuelle . Cependant, aucune ne constitue une véritable métrique ou « mesure de distance » au sens mathématique du terme, car elles ne respectent pas l' inégalité triangulaire et ne calculent donc aucune « distance » réelle ; il convient plutôt de les considérer comme des « scores ». Ces scores sont calculés entre une caractéristique candidate (ou un ensemble de caractéristiques) et la catégorie de sortie souhaitée. Il existe néanmoins de véritables métriques qui sont une fonction simple de l'information mutuelle ; voir ici .

Les autres indicateurs de filtrage disponibles incluent :

séparabilité des classes
- Probabilité d'erreur
- Distance interclasse
- Distance probabiliste
- Entropie
Sélection de caractéristiques basée sur la cohérence
Sélection de caractéristiques basée sur la corrélation

Critères d'optimalité

Le choix des critères d'optimalité est complexe, car une tâche de sélection de caractéristiques comporte de multiples objectifs. De nombreux critères courants intègrent une mesure de précision, pénalisée par le nombre de caractéristiques sélectionnées. On peut citer, par exemple, le critère d'information d'Akaike (AIC) et le C _p de Mallows , qui appliquent une pénalité de 2 pour chaque caractéristique ajoutée. L'AIC repose sur la théorie de l'information et est dérivé du principe d'entropie maximale .

D'autres critères incluent le critère d'information bayésien (BIC), qui utilise une pénalité de pour chaque caractéristique ajoutée, la longueur de description minimale (MDL), qui utilise asymptotiquement , Bonferroni / RIC, qui utilise , la sélection de caractéristiques par dépendance maximale, et divers nouveaux critères inspirés du taux de fausses découvertes (FDR), qui utilisent une valeur proche de . Un critère de taux d'entropie maximal peut également être utilisé pour sélectionner le sous-ensemble de caractéristiques le plus pertinent. ${\displaystyle {\sqrt {\log {n <semantics><mrow><mstyle><mrow><msqrt><mi>log</mi><mo>⁡</mo><mrow><mi>n</mi></mrow></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {\log {n}}}}</annotation></semantics></math><img src=$ ${\displaystyle {\sqrt {\log {n <semantics><mrow><mstyle><mrow><msqrt><mi>log</mi><mo>⁡</mo><mrow><mi>n</mi></mrow></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {\log {n}}}}</annotation></semantics></math><img src=$ ${\displaystyle {\sqrt {2\log {p <semantics><mrow><mstyle><mrow><msqrt><mn>2</mn><mi>log</mi><mo>⁡</mo><mrow><mi>p</mi></mrow></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {2\log {p}}}}</annotation></semantics></math><img src=$ ${\displaystyle {\sqrt {2\log {\frac {p}{q <semantics><mrow><mstyle><mrow><msqrt><mn>2</mn><mi>log</mi><mo>⁡</mo><mrow><mfrac><mi>p</mi><mi>q</mi></mfrac></mrow></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {2\log {\frac {p}{q}}}}}</annotation></semantics></math><img src=$

Apprentissage structuré

La sélection de caractéristiques par filtrage est un cas particulier d'un paradigme plus général appelé apprentissage de structure . La sélection de caractéristiques identifie l'ensemble de caractéristiques pertinentes pour une variable cible spécifique, tandis que l'apprentissage de structure détermine les relations entre toutes les variables, généralement en les représentant sous forme de graphe. Les algorithmes d'apprentissage de structure les plus courants supposent que les données sont générées par un réseau bayésien , et que la structure est donc un modèle graphique orienté . La solution optimale au problème de sélection de caractéristiques par filtrage est la couverture de Markov du nœud cible, et dans un réseau bayésien, chaque nœud possède une couverture de Markov unique.

Mécanismes de sélection de caractéristiques basés sur la théorie de l'information

Il existe différents mécanismes de sélection de caractéristiques qui utilisent l'information mutuelle pour évaluer les différentes caractéristiques. Ils utilisent généralement tous le même algorithme :

Calculez l' information mutuelle sous forme de score entre toutes les caractéristiques ( ) et la classe cible ( c ). ${\displaystyle f_{i}\in F <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mi>F</mi></mstyle></mrow><annotation>{\displaystyle f_{i}\in F}</annotation></semantics></math><img src=$
Sélectionnez la caractéristique ayant le score le plus élevé (par exemple ) et ajoutez-la à l'ensemble des caractéristiques sélectionnées ( S ). ${\displaystyle {\underset {f_{i}\in F}{\operatorname {argmax} }}(I(f_{i},c)) <semantics><mrow><mstyle><mrow><munder><mi>argmax</mi><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mi>F</mi></mrow></munder></mrow><mo>(</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>,</mo><mi>c</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\underset {f_{i}\in F}{\operatorname {argmax} }}(I(f_{i},c))}</annotation></semantics></math><img src=$
Calculez le score qui pourrait être déduit de l' information mutuelle
Sélectionnez la caractéristique ayant le score le plus élevé et ajoutez-la à l'ensemble des caractéristiques sélectionnées (par exemple ) ${\displaystyle {\underset {f_{i}\in F}{\operatorname {argmax} }}(I_{derived}(f_{i},c)) <semantics><mrow><mstyle><mrow><munder><mi>argmax</mi><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mi>F</mi></mrow></munder></mrow><mo>(</mo><msub><mi>I</mi><mrow><mi>d</mi><mi>e</mi><mi>r</mi><mi>i</mi><mi>v</mi><mi>e</mi><mi>d</mi></mrow></msub><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>,</mo><mi>c</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\underset {f_{i}\in F}{\operatorname {argmax} }}(I_{derived}(f_{i},c))}</annotation></semantics></math><img src=$
Répétez les étapes 3 et 4 jusqu'à ce qu'un certain nombre de fonctionnalités soient sélectionnées (par exemple ). ${\displaystyle |S|=l <semantics><mrow><mstyle><mrow><mo>|</mo></mrow><mi>S</mi><mrow><mo>|</mo></mrow><mo>=</mo><mi>l</mi></mstyle></mrow><annotation>{\displaystyle |S|=l}</annotation></semantics></math><img src=$

L'approche la plus simple utilise l' information mutuelle comme score « dérivé ».

Il existe cependant différentes approches qui tentent de réduire la redondance entre les fonctionnalités.

sélection de caractéristiques à redondance minimale et pertinence maximale (mRMR)

Peng et al. ont proposé une méthode de sélection de caractéristiques qui peut utiliser l'information mutuelle, la corrélation ou les scores de distance/similarité. L'objectif est de pénaliser la pertinence d'une caractéristique en fonction de sa redondance par rapport aux autres caractéristiques sélectionnées. La pertinence d'un ensemble de caractéristiques S pour la classe c est définie par la valeur moyenne de toutes les informations mutuelles entre la caractéristique individuelle f _i et la classe c , comme suit :

{\displaystyle D(S,c)={\frac {1}{|S|}}\sum _{f_{i}\in S}I(f_{i};c) <semantics><mrow><mstyle><mi>D</mi><mo>(</mo><mi>S</mi><mo>,</mo><mi>c</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mrow><mo>|</mo></mrow><mi>S</mi><mrow><mo>|</mo></mrow></mrow></mfrac></mrow><munder><mo>∑</mo><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mi>S</mi></mrow></munder><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle D(S,c)={\frac {1}{|S|}}\sum _{f_{i}\in S}I(f_{i};c)}</annotation></semantics></math></span><img src=

La redondance de toutes les caractéristiques de l'ensemble S est la valeur moyenne de toutes les valeurs d'information mutuelle entre la caractéristique f _i et la caractéristique f _j :

{\displaystyle R(S)={\frac {1}{|S|^{2}}}\sum _{f_{i},f_{j}\in S}I(f_{i};f_{j}) <semantics><mrow><mstyle><mi>R</mi><mo>(</mo><mi>S</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mrow><mo>|</mo></mrow><mi>S</mi><msup><mrow><mo>|</mo></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><munder><mo>∑</mo><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>,</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>∈</mo><mi>S</mi></mrow></munder><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle R(S)={\frac {1}{|S|^{2}}}\sum _{f_{i},f_{j}\in S}I(f_{i};f_{j})}</annotation></semantics></math></span><img src=

Le critère mRMR est une combinaison des deux mesures mentionnées ci-dessus et est défini comme suit :

{\displaystyle \mathrm {mRMR} =\max _{S}\left[{\frac {1}{|S|}}\sum _{f_{i}\in S}I(f_{i};c)-{\frac {1}{|S|^{2}}}\sum _{f_{i},f_{j}\in S}I(f_{i};f_{j}) ight]. <semantics><mrow><mstyle><mrow><mi>m</mi><mi>R</mi><mi>M</mi><mi>R</mi></mrow><mo>=</mo><munder><mo>max</mo><mrow><mi>S</mi></mrow></munder><mrow><mo>[</mo><mrow><mrow><mfrac><mn>1</mn><mrow><mrow><mo>|</mo></mrow><mi>S</mi><mrow><mo>|</mo></mrow></mrow></mfrac></mrow><munder><mo>∑</mo><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mi>S</mi></mrow></munder><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo><mo>−</mo><mrow><mfrac><mn>1</mn><mrow><mrow><mo>|</mo></mrow><mi>S</mi><msup><mrow><mo>|</mo></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><munder><mo>∑</mo><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>,</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>∈</mo><mi>S</mi></mrow></munder><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo></mrow><mo>]</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {mRMR} =\max _{S}\left[{\frac {1}{|S|}}\sum _{f_{i}\in S}I(f_{i};c)-{\frac {1}{|S|^{2}}}\sum _{f_{i},f_{j}\in S}I(f_{i};f_{j}) ight].}</annotation></semantics></math></span><img src=

Supposons qu'il existe n caractéristiques complètes. Soit x _i la fonction indicatrice d'appartenance à l'ensemble de caractéristiques f _i , telle que x _i = 1 indique la présence et x _i = 0 indique l'absence de la caractéristique f _i dans l'ensemble de caractéristiques globalement optimal. Soient et . Le problème ci-dessus peut alors être formulé comme un problème d'optimisation : ${\displaystyle c_{i}=I(f_{i};c) <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mi>i</mi></mrow></msub><mo>=</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle c_{i}=I(f_{i};c)}</annotation></semantics></math><img src=$ ${\displaystyle a_{ij}=I(f_{i};f_{j}) <semantics><mrow><mstyle><msub><mi>a</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle a_{ij}=I(f_{i};f_{j})}</annotation></semantics></math><img src=$

{\displaystyle \mathrm {mRMR} =\max _{x\in \{0,1\}^{n}}\left[{\frac {\sum _{i=1}^{n}c_{i}x_{i}}{\sum _{i=1}^{n}x_{i}}}-{\frac {\sum _{i,j=1}^{n}a_{ij}x_{i}x_{j}}{(\sum _{i=1}^{n}x_{i})^{2}}} ight]. <semantics><mrow><mstyle><mrow><mi>m</mi><mi>R</mi><mi>M</mi><mi>R</mi></mrow><mo>=</mo><munder><mo>max</mo><mrow><mi>x</mi><mo>∈</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><msup><mo>}</mo><mrow><mi>n</mi></mrow></msup></mrow></munder><mrow><mo>[</mo><mrow><mrow><mfrac><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>c</mi><mrow><mi>i</mi></mrow></msub><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub></mrow><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub></mrow></mfrac></mrow><mo>−</mo><mrow><mfrac><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><msub><mi>x</mi><mrow><mi>j</mi></mrow></msub></mrow><mrow><mo>(</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow></mrow><mo>]</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {mRMR} =\max _{x\in \{0,1\}^{n}}\left[{\frac {\sum _{i=1}^{n}c_{i}x_{i}}{\sum _{i=1}^{n}x_{i}}}-{\frac {\sum _{i,j=1}^{n}a_{ij}x_{i}x_{j}}{(\sum _{i=1}^{n}x_{i})^{2}}} ight].}</annotation></semantics></math></span><img src=

L'algorithme mRMR est une approximation de l'algorithme de sélection de caractéristiques par dépendance maximale, théoriquement optimal, qui maximise l'information mutuelle entre la distribution conjointe des caractéristiques sélectionnées et la variable de classification. Comme mRMR approxime le problème d'estimation combinatoire par une série de problèmes beaucoup plus petits, chacun impliquant seulement deux variables, il utilise ainsi des probabilités conjointes par paires, plus robustes. Dans certaines situations, l'algorithme peut sous-estimer l'utilité des caractéristiques, car il ne peut mesurer les interactions entre elles susceptibles d'accroître leur pertinence. Cela peut entraîner de faibles performances lorsque les caractéristiques sont individuellement inutiles, mais utiles une fois combinées (un cas pathologique se présente lorsque la classe est une fonction de parité des caractéristiques). Globalement, l'algorithme est plus efficace (en termes de quantité de données requises) que la sélection par dépendance maximale théoriquement optimale, tout en produisant un ensemble de caractéristiques présentant une faible redondance par paires.

mRMR est un exemple d'une vaste classe de méthodes de filtrage qui font des compromis entre pertinence et redondance de différentes manières.

Sélection de caractéristiques de programmation quadratique

mRMR est un exemple typique de stratégie gloutonne incrémentale pour la sélection de caractéristiques : une fois qu’une caractéristique a été sélectionnée, elle ne peut pas être désélectionnée ultérieurement. Bien que mRMR puisse être optimisé à l’aide d’une recherche flottante pour réduire le nombre de caractéristiques, il peut également être reformulé comme un problème d’optimisation quadratique global comme suit :

{\displaystyle \mathrm {QPFS} :\min _{\mathbf {x} }\left\{\alpha \mathbf {x} ^{T}H\mathbf {x} -\mathbf {x} ^{T}F ight\}\quad {\mbox{s.t.}}\ \sum _{i=1}^{n}x_{i}=1,x_{i}\geq 0 <semantics><mrow><mstyle><mrow><mi>Q</mi><mi>P</mi><mi>F</mi><mi>S</mi></mrow><mo>:</mo><munder><mo>min</mo><mrow><mrow><mi>x</mi></mrow></mrow></munder><mrow><mo>{</mo><mrow><mi>α</mi><msup><mrow><mi>x</mi></mrow><mrow><mi>T</mi></mrow></msup><mi>H</mi><mrow><mi>x</mi></mrow><mo>−</mo><msup><mrow><mi>x</mi></mrow><mrow><mi>T</mi></mrow></msup><mi>F</mi></mrow><mo>}</mo></mrow><mspace></mspace><mrow><mstyle><mtext>s.t.</mtext></mstyle></mrow><mtext> </mtext><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><mo>=</mo><mn>1</mn><mo>,</mo><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><mo>≥</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle \mathrm {QPFS} :\min _{\mathbf {x} }\left\{\alpha \mathbf {x} ^{T}H\mathbf {x} -\mathbf {x} ^{T}F ight\}\quad {\mbox{s.t.}}\ \sum _{i=1}^{n}x_{i}=1,x_{i}\geq 0}</annotation></semantics></math></span><img src=

où représente le vecteur de pertinence des caractéristiques (en supposant qu'il y ait n caractéristiques au total), est la matrice de redondance par paire des caractéristiques, et représente les poids relatifs des caractéristiques. Le QPFS est résolu par programmation quadratique. Il a été récemment démontré que le QFPS est biaisé en faveur des caractéristiques à faible entropie , du fait du placement du terme d'auto-redondance des caractéristiques sur la diagonale de H. ${\displaystyle F_{n imes 1}=[I(f_{1};c),\ldots ,I(f_{n};c)]^{T <semantics><mrow><mstyle><msub><mi>F</mi><mrow><mi>n</mi><mo>×</mo><mn>1</mn></mrow></msub><mo>=</mo><mo>[</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mn>1</mn></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo><mo>,</mo><mo>…</mo><mo>,</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo><msup><mo>]</mo><mrow><mi>T</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle F_{n imes 1}=[I(f_{1};c),\ldots ,I(f_{n};c)]^{T}}</annotation></semantics></math><img src=$ ${\displaystyle H_{n imes n}=[I(f_{i};f_{j})]_{i,j=1\ldots n <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></msub><mo>=</mo><mo>[</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo><msub><mo>]</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>=</mo><mn>1</mn><mo>…</mo><mi>n</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle H_{n imes n}=[I(f_{i};f_{j})]_{i,j=1\ldots n}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {x} _{n imes 1 <semantics><mrow><mstyle><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi><mo>×</mo><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathbf {x} _{n imes 1}}</annotation></semantics></math><img src=$ ${\displaystyle I(f_{i};f_{i}) <semantics><mrow><mstyle><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle I(f_{i};f_{i})}</annotation></semantics></math><img src=$

Information mutuelle conditionnelle

Un autre score dérivé de l'information mutuelle est basé sur la pertinence conditionnelle :

{\displaystyle \mathrm {SPEC_{CMI}} :\max _{\mathbf {x} }\left\{\mathbf {x} ^{T}Q\mathbf {x} ight\}\quad {\mbox{s.t.}}\ \|\mathbf {x} \|=1,x_{i}\geq 0 <semantics><mrow><mstyle><mrow><mi>S</mi><mi>P</mi><mi>E</mi><msub><mi>C</mi><mrow><mi>C</mi><mi>M</mi><mi>I</mi></mrow></msub></mrow><mo>:</mo><munder><mo>max</mo><mrow><mrow><mi>x</mi></mrow></mrow></munder><mrow><mo>{</mo><mrow><msup><mrow><mi>x</mi></mrow><mrow><mi>T</mi></mrow></msup><mi>Q</mi><mrow><mi>x</mi></mrow></mrow><mo>}</mo></mrow><mspace></mspace><mrow><mstyle><mtext>s.t.</mtext></mstyle></mrow><mtext> </mtext><mo>‖</mo><mrow><mi>x</mi></mrow><mo>‖</mo><mo>=</mo><mn>1</mn><mo>,</mo><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><mo>≥</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle \mathrm {SPEC_{CMI}} :\max _{\mathbf {x} }\left\{\mathbf {x} ^{T}Q\mathbf {x} ight\}\quad {\mbox{s.t.}}\ \|\mathbf {x} \|=1,x_{i}\geq 0}</annotation></semantics></math></span><img src=

où et . ${\displaystyle Q_{ii}=I(f_{i};c) <semantics><mrow><mstyle><msub><mi>Q</mi><mrow><mi>i</mi><mi>i</mi></mrow></msub><mo>=</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle Q_{ii}=I(f_{i};c)}</annotation></semantics></math><img src=$ ${\displaystyle Q_{ij}=(I(f_{i};c|f_{j})+I(f_{j};c|f_{i}))/2,i eq j <semantics><mrow><mstyle><msub><mi>Q</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mo>(</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mrow><mo>|</mo></mrow><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo><mo>+</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>;</mo><mi>c</mi><mrow><mo>|</mo></mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>)</mo><mo>)</mo><mrow><mo>/</mo></mrow><mn>2</mn><mo>,</mo><mi>i</mi><mo>≠</mo><mi>j</mi></mstyle></mrow><annotation>{\displaystyle Q_{ij}=(I(f_{i};c|f_{j})+I(f_{j};c|f_{i}))/2,i eq j}</annotation></semantics></math><img src=$

L'un des avantages de SPEC _CMI est sa simplicité de résolution, qui consiste à trouver le vecteur propre dominant de Q , ce qui le rend très évolutif. SPEC _CMI gère également l'interaction des caractéristiques du second ordre.

Informations mutuelles conjointes

Dans une étude comparant différents scores, Brown et al. ont recommandé l' information mutuelle conjointe comme un bon score pour la sélection de caractéristiques. Ce score vise à identifier la caractéristique qui apporte le plus d'informations nouvelles aux caractéristiques déjà sélectionnées, afin d'éviter les redondances. Il est formulé comme suit :

{\displaystyle {\begin{aligned}JMI(f_{i})&=\sum _{f_{j}\in S}(I(f_{i};c)+I(f_{i};c|f_{j}))\\&=\sum _{f_{j}\in S}{\bigl [}I(f_{j};c)+I(f_{i};c)-{\bigl (}I(f_{i};f_{j})-I(f_{i};f_{j}|c){\bigr )}{\bigr ]}\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>J</mi><mi>M</mi><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><munder><mo>∑</mo><mrow><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>∈</mo><mi>S</mi></mrow></munder><mo>(</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo><mo>+</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mrow><mo>|</mo></mrow><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo><mo>)</mo></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><munder><mo>∑</mo><mrow><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>∈</mo><mi>S</mi></mrow></munder><mrow><mrow><mo>[</mo></mrow></mrow><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo><mo>+</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><mi>c</mi><mo>)</mo><mo>−</mo><mrow><mrow><mo>(</mo></mrow></mrow><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo><mo>−</mo><mi>I</mi><mo>(</mo><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><mo>;</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mrow><mo>|</mo></mrow><mi>c</mi><mo>)</mo><mrow><mrow><mo>)</mo></mrow></mrow><mrow><mrow><mo>]</mo></mrow></mrow></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}JMI(f_{i})&=\sum _{f_{j}\in S}(I(f_{i};c)+I(f_{i};c|f_{j}))\\&=\sum _{f_{j}\in S}{\bigl [}I(f_{j};c)+I(f_{i};c)-{\bigl (}I(f_{i};f_{j})-I(f_{i};f_{j}|c){\bigr )}{\bigr ]}\end{aligned}}}</annotation></semantics></math></span><img src=

Le score utilise l' information mutuelle conditionnelle et l' information mutuelle pour estimer la redondance entre les caractéristiques déjà sélectionnées ( ) et la caractéristique étudiée ( ). ${\displaystyle f_{j}\in S <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>∈</mo><mi>S</mi></mstyle></mrow><annotation>{\displaystyle f_{j}\in S}</annotation></semantics></math><img src=$ ${\displaystyle f_{i <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle f_{i}}</annotation></semantics></math><img src=$

Sélection de caractéristiques basée sur le critère d'indépendance de Hilbert-Schmidt et le lasso

Pour les données de grande dimension et de petit échantillon (par exemple, dimensionnalité > 10⁵ et le nombre d'échantillons < 10³ ), le Lasso à critère d'indépendance de Hilbert-Schmidt (HSIC Lasso) est utile. Le problème d'optimisation HSIC Lasso est donné comme

{\displaystyle \mathrm {HSIC_{Lasso}} :\min _{\mathbf {x} }{\frac {1}{2}}\sum _{k,l=1}^{n}x_{k}x_{l}{\mbox{HSIC}}(f_{k},f_{l})-\sum _{k=1}^{n}x_{k}{\mbox{HSIC}}(f_{k},c)+\lambda \|\mathbf {x} \|_{1},\quad {\mbox{s.t.}}\ x_{1},\ldots ,x_{n}\geq 0, <semantics><mrow><mstyle><mrow><mi>H</mi><mi>S</mi><mi>I</mi><msub><mi>C</mi><mrow><mi>L</mi><mi>a</mi><mi>s</mi><mi>s</mi><mi>o</mi></mrow></msub></mrow><mo>:</mo><munder><mo>min</mo><mrow><mrow><mi>x</mi></mrow></mrow></munder><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>,</mo><mi>l</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>x</mi><mrow><mi>k</mi></mrow></msub><msub><mi>x</mi><mrow><mi>l</mi></mrow></msub><mrow><mstyle><mtext>HSIC</mtext></mstyle></mrow><mo>(</mo><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo><msub><mi>f</mi><mrow><mi>l</mi></mrow></msub><mo>)</mo><mo>−</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>x</mi><mrow><mi>k</mi></mrow></msub><mrow><mstyle><mtext>HSIC</mtext></mstyle></mrow><mo>(</mo><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo><mi>c</mi><mo>)</mo><mo>+</mo><mi>λ</mi><mo>‖</mo><mrow><mi>x</mi></mrow><msub><mo>‖</mo><mrow><mn>1</mn></mrow></msub><mo>,</mo><mspace></mspace><mrow><mstyle><mtext>s.t.</mtext></mstyle></mrow><mtext> </mtext><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi></mrow></msub><mo>≥</mo><mn>0</mn><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {HSIC_{Lasso}} :\min _{\mathbf {x} }{\frac {1}{2}}\sum _{k,l=1}^{n}x_{k}x_{l}{\mbox{HSIC}}(f_{k},f_{l})-\sum _{k=1}^{n}x_{k}{\mbox{HSIC}}(f_{k},c)+\lambda \|\mathbf {x} \|_{1},\quad {\mbox{s.t.}}\ x_{1},\ldots ,x_{n}\geq 0,}</annotation></semantics></math></span><img src=

où est une mesure d'indépendance basée sur un noyau, appelée critère d'indépendance de Hilbert-Schmidt (HSIC) (empirique), désigne la trace , est le paramètre de régularisation, et sont les matrices de Gram centrées sur l'entrée et la sortie , et sont des matrices de Gram, et sont des fonctions noyau, est la matrice de centrage, est la matrice identité de dimension m ( m : le nombre d'échantillons), est le vecteur de dimension m composé uniquement de 1, et est la norme -norme. Le HSIC prend toujours une valeur non négative, et est nul si et seulement si deux variables aléatoires sont statistiquement indépendantes lorsqu'un noyau reproduisant universel tel que le noyau gaussien est utilisé. ${\displaystyle {\mbox{HSIC}}(f_{k},c)={\mbox{tr}}({\bar {\mathbf {K} }}^{(k)}{\bar {\mathbf {L} }}) <semantics><mrow><mstyle><mrow><mstyle><mtext>HSIC</mtext></mstyle></mrow><mo>(</mo><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><mo>,</mo><mi>c</mi><mo>)</mo><mo>=</mo><mrow><mstyle><mtext>tr</mtext></mstyle></mrow><mo>(</mo><msup><mrow><mrow><mover><mrow><mi>K</mi></mrow><mo>¯</mo></mover></mrow></mrow><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msup><mrow><mrow><mover><mrow><mi>L</mi></mrow><mo>¯</mo></mover></mrow></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\mbox{HSIC}}(f_{k},c)={\mbox{tr}}({\bar {\mathbf {K} }}^{(k)}{\bar {\mathbf {L} }})}</annotation></semantics></math><img src=$ ${\displaystyle {\mbox{tr}}(\cdot ) <semantics><mrow><mstyle><mrow><mstyle><mtext>tr</mtext></mstyle></mrow><mo>(</mo><mo>⋅</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\mbox{tr}}(\cdot )}</annotation></semantics></math><img src=$ ${\displaystyle \lambda <semantics><mrow><mstyle><mi>λ</mi></mstyle></mrow><annotation>{\displaystyle \lambda }</annotation></semantics></math><img src=$ ${\displaystyle {\bar {\mathbf {K} }}^{(k)}=\mathbf {\Gamma } \mathbf {K} ^{(k)}\mathbf {\Gamma } <semantics><mrow><mstyle><msup><mrow><mrow><mover><mrow><mi>K</mi></mrow><mo>¯</mo></mover></mrow></mrow><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msup><mo>=</mo><mrow><mi>Γ</mi></mrow><msup><mrow><mi>K</mi></mrow><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msup><mrow><mi>Γ</mi></mrow></mstyle></mrow><annotation>{\displaystyle {\bar {\mathbf {K} }}^{(k)}=\mathbf {\Gamma } \mathbf {K} ^{(k)}\mathbf {\Gamma } }</annotation></semantics></math><img src=$ ${\displaystyle {\bar {\mathbf {L} }}=\mathbf {\Gamma } \mathbf {L} \mathbf {\Gamma } <semantics><mrow><mstyle><mrow><mrow><mover><mrow><mi>L</mi></mrow><mo>¯</mo></mover></mrow></mrow><mo>=</mo><mrow><mi>Γ</mi></mrow><mrow><mi>L</mi></mrow><mrow><mi>Γ</mi></mrow></mstyle></mrow><annotation>{\displaystyle {\bar {\mathbf {L} }}=\mathbf {\Gamma } \mathbf {L} \mathbf {\Gamma } }</annotation></semantics></math><img src=$ ${\displaystyle K_{i,j}^{(k)}=K(u_{k,i},u_{k,j}) <semantics><mrow><mstyle><msubsup><mi>K</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msubsup><mo>=</mo><mi>K</mi><mo>(</mo><msub><mi>u</mi><mrow><mi>k</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>k</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle K_{i,j}^{(k)}=K(u_{k,i},u_{k,j})}</annotation></semantics></math><img src=$ ${\displaystyle L_{i,j}=L(c_{i},c_{j}) <semantics><mrow><mstyle><msub><mi>L</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>=</mo><mi>L</mi><mo>(</mo><msub><mi>c</mi><mrow><mi>i</mi></mrow></msub><mo>,</mo><msub><mi>c</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle L_{i,j}=L(c_{i},c_{j})}</annotation></semantics></math><img src=$ ${\displaystyle K(u,u') <semantics><mrow><mstyle><mi>K</mi><mo>(</mo><mi>u</mi><mo>,</mo><msup><mi>u</mi><mo>′</mo></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle K(u,u')}</annotation></semantics></math><img src=$ ${\displaystyle L(c,c') <semantics><mrow><mstyle><mi>L</mi><mo>(</mo><mi>c</mi><mo>,</mo><msup><mi>c</mi><mo>′</mo></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle L(c,c')}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {\Gamma } =\mathbf {I} _{m}-{\frac {1}{m}}\mathbf {1} _{m}\mathbf {1} _{m}^{T <semantics><mrow><mstyle><mrow><mi>Γ</mi></mrow><mo>=</mo><msub><mrow><mi>I</mi></mrow><mrow><mi>m</mi></mrow></msub><mo>−</mo><mrow><mfrac><mn>1</mn><mi>m</mi></mfrac></mrow><msub><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></msub><msubsup><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow><mrow><mi>T</mi></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle \mathbf {\Gamma } =\mathbf {I} _{m}-{\frac {1}{m}}\mathbf {1} _{m}\mathbf {1} _{m}^{T}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {I} _{m <semantics><mrow><mstyle><msub><mrow><mi>I</mi></mrow><mrow><mi>m</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathbf {I} _{m}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {1} _{m <semantics><mrow><mstyle><msub><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \mathbf {1} _{m}}</annotation></semantics></math><img src=$ ${\displaystyle \|\cdot \|_{1 <semantics><mrow><mstyle><mo>‖</mo><mo>⋅</mo><msub><mo>‖</mo><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle \|\cdot \|_{1}}</annotation></semantics></math><img src=$ ${\displaystyle \ell _{1 <semantics><mrow><mstyle><msub><mi>ℓ</mi><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle \ell _{1}}</annotation></semantics></math><img src=$

Le lasso HSIC peut s'écrire comme

{\displaystyle \mathrm {HSIC_{Lasso}} :\min _{\mathbf {x} }{\frac {1}{2}}\left\|{\bar {\mathbf {L} }}-\sum _{k=1}^{n}x_{k}{\bar {\mathbf {K} }}^{(k)} ight\|_{F}^{2}+\lambda \|\mathbf {x} \|_{1},\quad {\mbox{s.t.}}\ x_{1},\ldots ,x_{n}\geq 0, <semantics><mrow><mstyle><mrow><mi>H</mi><mi>S</mi><mi>I</mi><msub><mi>C</mi><mrow><mi>L</mi><mi>a</mi><mi>s</mi><mi>s</mi><mi>o</mi></mrow></msub></mrow><mo>:</mo><munder><mo>min</mo><mrow><mrow><mi>x</mi></mrow></mrow></munder><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow><msubsup><mrow><mo>‖</mo><mrow><mrow><mrow><mover><mrow><mi>L</mi></mrow><mo>¯</mo></mover></mrow></mrow><mo>−</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>x</mi><mrow><mi>k</mi></mrow></msub><msup><mrow><mrow><mover><mrow><mi>K</mi></mrow><mo>¯</mo></mover></mrow></mrow><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msup></mrow><mo>‖</mo></mrow><mrow><mi>F</mi></mrow><mrow><mn>2</mn></mrow></msubsup><mo>+</mo><mi>λ</mi><mo>‖</mo><mrow><mi>x</mi></mrow><msub><mo>‖</mo><mrow><mn>1</mn></mrow></msub><mo>,</mo><mspace></mspace><mrow><mstyle><mtext>s.t.</mtext></mstyle></mrow><mtext> </mtext><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi></mrow></msub><mo>≥</mo><mn>0</mn><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {HSIC_{Lasso}} :\min _{\mathbf {x} }{\frac {1}{2}}\left\|{\bar {\mathbf {L} }}-\sum _{k=1}^{n}x_{k}{\bar {\mathbf {K} }}^{(k)} ight\|_{F}^{2}+\lambda \|\mathbf {x} \|_{1},\quad {\mbox{s.t.}}\ x_{1},\ldots ,x_{n}\geq 0,}</annotation></semantics></math></span><img src=

où désigne la norme de Frobenius . Le problème d'optimisation est un problème Lasso et peut donc être résolu efficacement avec un solveur Lasso de pointe tel que la méthode du lagrangien augmenté dual . ${\displaystyle \|\cdot \|_{F <semantics><mrow><mstyle><mo>‖</mo><mo>⋅</mo><msub><mo>‖</mo><mrow><mi>F</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \|\cdot \|_{F}}</annotation></semantics></math><img src=$

Sélection de caractéristiques de corrélation

La mesure de sélection de caractéristiques par corrélation (CFS) évalue des sous-ensembles de caractéristiques selon l'hypothèse suivante : « Les bons sous-ensembles de caractéristiques contiennent des caractéristiques fortement corrélées à la classification, mais non corrélées entre elles. » L'équation suivante donne la qualité d'un sous-ensemble de caractéristiques S composé de k caractéristiques :

{\displaystyle \mathrm {Merit} _{S_{k}}={\frac {k{\overline {r_{cf}}}}{\sqrt {k+k(k-1){\overline {r_{ff}}}}}}. <semantics><mrow><mstyle><msub><mrow><mi>M</mi><mi>e</mi><mi>r</mi><mi>i</mi><mi>t</mi></mrow><mrow><msub><mi>S</mi><mrow><mi>k</mi></mrow></msub></mrow></msub><mo>=</mo><mrow><mfrac><mrow><mi>k</mi><mrow><mover><msub><mi>r</mi><mrow><mi>c</mi><mi>f</mi></mrow></msub><mo>¯</mo></mover></mrow></mrow><msqrt><mi>k</mi><mo>+</mo><mi>k</mi><mo>(</mo><mi>k</mi><mo>−</mo><mn>1</mn><mo>)</mo><mrow><mover><msub><mi>r</mi><mrow><mi>f</mi><mi>f</mi></mrow></msub><mo>¯</mo></mover></mrow></msqrt></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {Merit} _{S_{k}}={\frac {k{\overline {r_{cf}}}}{\sqrt {k+k(k-1){\overline {r_{ff}}}}}}.}</annotation></semantics></math></span><img src=

Ici, représente la valeur moyenne de toutes les corrélations caractéristique-classification, et représente la valeur moyenne de toutes les corrélations caractéristique-caractéristique. Le critère CFS est défini comme suit : ${\displaystyle {\overline {r_{cf <semantics><mrow><mstyle><mrow><mover><msub><mi>r</mi><mrow><mi>c</mi><mi>f</mi></mrow></msub><mo>¯</mo></mover></mrow></mstyle></mrow><annotation>{\displaystyle {\overline {r_{cf}}}}</annotation></semantics></math><img src=$ ${\displaystyle {\overline {r_{ff <semantics><mrow><mstyle><mrow><mover><msub><mi>r</mi><mrow><mi>f</mi><mi>f</mi></mrow></msub><mo>¯</mo></mover></mrow></mstyle></mrow><annotation>{\displaystyle {\overline {r_{ff}}}}</annotation></semantics></math><img src=$

{\displaystyle \mathrm {CFS} =\max _{S_{k}}\left[{\frac {r_{cf_{1}}+r_{cf_{2}}+\cdots +r_{cf_{k}}}{\sqrt {k+2(r_{f_{1}f_{2}}+\cdots +r_{f_{i}f_{j}}+\cdots +r_{f_{k}f_{k-1}})}}} ight]. <semantics><mrow><mstyle><mrow><mi>C</mi><mi>F</mi><mi>S</mi></mrow><mo>=</mo><munder><mo>max</mo><mrow><msub><mi>S</mi><mrow><mi>k</mi></mrow></msub></mrow></munder><mrow><mo>[</mo><mrow><mfrac><mrow><msub><mi>r</mi><mrow><mi>c</mi><msub><mi>f</mi><mrow><mn>1</mn></mrow></msub></mrow></msub><mo>+</mo><msub><mi>r</mi><mrow><mi>c</mi><msub><mi>f</mi><mrow><mn>2</mn></mrow></msub></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>r</mi><mrow><mi>c</mi><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub></mrow></msub></mrow><msqrt><mi>k</mi><mo>+</mo><mn>2</mn><mo>(</mo><msub><mi>r</mi><mrow><msub><mi>f</mi><mrow><mn>1</mn></mrow></msub><msub><mi>f</mi><mrow><mn>2</mn></mrow></msub></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><msub><mi>f</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub></mrow></msub><mo>)</mo></msqrt></mfrac></mrow><mo>]</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {CFS} =\max _{S_{k}}\left[{\frac {r_{cf_{1}}+r_{cf_{2}}+\cdots +r_{cf_{k}}}{\sqrt {k+2(r_{f_{1}f_{2}}+\cdots +r_{f_{i}f_{j}}+\cdots +r_{f_{k}f_{k-1}})}}} ight].}</annotation></semantics></math></span><img src=

Les variables et sont appelées corrélations, mais ne correspondent pas nécessairement au coefficient de corrélation de Pearson ou au ρ de Spearman . La thèse de Hall n'utilise aucun de ces coefficients, mais trois mesures différentes de relation : la longueur de description minimale (MDL), l'incertitude symétrique et le relief . ${\displaystyle r_{cf_{i <semantics><mrow><mstyle><msub><mi>r</mi><mrow><mi>c</mi><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{cf_{i}}}</annotation></semantics></math><img src=$ ${\displaystyle r_{f_{i}f_{j <semantics><mrow><mstyle><msub><mi>r</mi><mrow><msub><mi>f</mi><mrow><mi>i</mi></mrow></msub><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub></mrow></msub></mstyle></mrow><annotation>{\displaystyle r_{f_{i}f_{j}}}</annotation></semantics></math><img src=$

Soit x _i la fonction indicatrice d'appartenance à un ensemble pour la caractéristique f _i ; alors ce qui précède peut être réécrit comme un problème d'optimisation :

{\displaystyle \mathrm {CFS} =\max _{x\in \{0,1\}^{n}}\left[{\frac {(\sum _{i=1}^{n}a_{i}x_{i})^{2}}{\sum _{i=1}^{n}x_{i}+\sum _{i eq j}2b_{ij}x_{i}x_{j}}} ight]. <semantics><mrow><mstyle><mrow><mi>C</mi><mi>F</mi><mi>S</mi></mrow><mo>=</mo><munder><mo>max</mo><mrow><mi>x</mi><mo>∈</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><msup><mo>}</mo><mrow><mi>n</mi></mrow></msup></mrow></munder><mrow><mo>[</mo><mrow><mfrac><mrow><mo>(</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>a</mi><mrow><mi>i</mi></mrow></msub><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><mo>+</mo><munder><mo>∑</mo><mrow><mi>i</mi><mo>≠</mo><mi>j</mi></mrow></munder><mn>2</mn><msub><mi>b</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><msub><mi>x</mi><mrow><mi>i</mi></mrow></msub><msub><mi>x</mi><mrow><mi>j</mi></mrow></msub></mrow></mfrac></mrow><mo>]</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {CFS} =\max _{x\in \{0,1\}^{n}}\left[{\frac {(\sum _{i=1}^{n}a_{i}x_{i})^{2}}{\sum _{i=1}^{n}x_{i}+\sum _{i eq j}2b_{ij}x_{i}x_{j}}} ight].}</annotation></semantics></math></span><img src=

Les problèmes combinatoires ci-dessus sont en fait des problèmes de programmation linéaire mixte 0-1 qui peuvent être résolus à l'aide d'algorithmes de séparation et d'évaluation .

Arbres régularisés

Il est démontré que les caractéristiques issues d'un arbre de décision ou d'un ensemble d'arbres sont redondantes. Une méthode récente, appelée arbre régularisé permet de sélectionner un sous-ensemble de caractéristiques. Les arbres régularisés pénalisent l'utilisation d'une variable similaire à celles sélectionnées aux nœuds précédents pour la division du nœud courant. Ils ne nécessitent la construction que d'un seul modèle d'arbre (ou d'un seul ensemble d'arbres) et sont donc efficaces en termes de calcul.

Les arbres de décision régularisés gèrent naturellement les variables numériques et catégorielles, les interactions et les non-linéarités. Invariants aux échelles (unités) des attributs et insensibles aux valeurs aberrantes , ils nécessitent peu de prétraitement des données, comme la normalisation . La forêt aléatoire régularisée (RRF) est un type d'arbre de décision régularisé. La RRF guidée est une RRF améliorée, guidée par les scores d'importance d'une forêt aléatoire classique.

Aperçu des méthodes métaheuristiques

Une métaheuristique désigne un algorithme conçu pour résoudre des problèmes d'optimisation difficiles (généralement NP-difficiles ) pour lesquels il n'existe pas de méthodes de résolution classiques. De manière générale, une métaheuristique est un algorithme stochastique qui tend vers un optimum global. Il existe de nombreuses métaheuristiques, allant d'une simple recherche locale à un algorithme de recherche globale complexe.

Principes fondamentaux

Les méthodes de sélection de caractéristiques sont généralement présentées en trois classes selon la manière dont elles combinent l'algorithme de sélection et la construction du modèle.

Méthode de filtrage

Méthode de filtrage pour la sélection des caractéristiques

Les méthodes de filtrage sélectionnent les variables indépendamment du modèle. Elles se basent uniquement sur des caractéristiques générales, comme la corrélation avec la variable à prédire. Ces méthodes éliminent les variables les moins pertinentes. Les autres variables font partie d'un modèle de classification ou de régression utilisé pour classifier ou prédire les données. Ces méthodes sont particulièrement efficaces en termes de temps de calcul et robustes au surapprentissage .

Les méthodes de filtrage ont tendance à sélectionner des variables redondantes lorsqu'elles ne tiennent pas compte des relations entre les variables. Cependant, des fonctionnalités plus élaborées tentent de minimiser ce problème en supprimant les variables fortement corrélées entre elles, comme l'algorithme Fast Correlation Based Filter (FCBF).

Méthode Wrapper

Les méthodes d'encapsulation évaluent des sous-ensembles de variables, ce qui permet, contrairement aux approches de filtrage, de détecter les interactions possibles entre les variables. Les deux principaux inconvénients de ces méthodes sont :

Le risque de surapprentissage augmente lorsque le nombre d'observations est insuffisant.
Le temps de calcul est important lorsque le nombre de variables est élevé.

Méthode intégrée

Des méthodes intégrées ont été récemment proposées, qui tentent de combiner les avantages des deux méthodes précédentes. Un algorithme d'apprentissage tire parti de son propre processus de sélection de variables et effectue simultanément la sélection de caractéristiques et la classification, comme l'algorithme FRMT.

Application des métaheuristiques de sélection de caractéristiques

Il s’agit d’une étude des applications récentes des métaheuristiques de sélection de caractéristiques dans la littérature. Cette étude a été réalisée par J. Hammon dans sa thèse de 2013.

Application	Algorithme	Approche	Classificateur	Fonction d'évaluation	Référence
SNP	Sélection de caractéristiques par similarité des caractéristiques	Filtre		r ²	Phuong 2005
SNP	Algorithme génétique	Emballage	Arbre de décision	Précision de la classification (10 plis)	Shah 2004
SNP	Escalade en montagne	Filtre + Emballage	Bayésien naïf	Somme des carrés des résidus prédits	Long 2007
SNP	Recuit simulé		bayésien naïf	Précision de la classification (5 plis)	Ustunkar 2011
Segments de libération conditionnelle	colonie de fourmis	Emballage	Réseau neuronal artificiel	MSE	Al-ani 2005
Commercialisation	Recuit simulé	Emballage	Régression	AIC , ^r²	Meiri 2006
Économie	Recuit simulé, algorithme génétique	Emballage	Régression	BIC	Kapetanios 2007
Masse spectrale	Algorithme génétique	Emballage	Régression linéaire multiple, moindres carrés partiels	erreur quadratique moyenne de prédiction	Broadhurst et al. 1997
Courrier indésirable	PSO binaire + Mutation	Emballage	Arbre de décision	coût pondéré	Zhang 2014
Microréseau	Recherche tabou + PSO	Emballage	Machine à vecteurs de support , k plus proches voisins	Distance euclidienne	Chuang 2009
Microréseau	PSO + Algorithme génétique	Emballage	Machine à vecteurs de support	Précision de la classification (10 plis)	Alba 2007
Microréseau	Algorithme génétique + Recherche locale itérative	Intégré	Machine à vecteurs de support	Précision de la classification (10 plis)	Duval 2009
Microréseau	Recherche locale itérative	Emballage	Régression	Probabilité postérieure	Hans 2007
Microréseau	Algorithme génétique	Emballage	K plus proches voisins	Précision de la classification ( validation croisée Leave-One-Out )	Jirapech-Umpai 2005
Microréseau	algorithme génétique hybride	Emballage	K plus proches voisins	Précision de la classification (validation croisée Leave-One-Out)	Oh 2004
Microréseau	Algorithme génétique	Emballage	Machine à vecteurs de support	Sensibilité et spécificité	Xuan 2011
Microréseau	Algorithme génétique	Emballage	Machine à vecteurs de support appariée	Précision de la classification (validation croisée Leave-One-Out)	Peng 2003
Microréseau	Algorithme génétique	Intégré	Machine à vecteurs de support	Précision de la classification (10 plis)	Hernandez 2007
Microréseau	Algorithme génétique	Hybride	Machine à vecteurs de support	Précision de la classification (validation croisée Leave-One-Out)	Huerta 2006
Microréseau	Algorithme génétique		Machine à vecteurs de support	Précision de la classification (10 plis)	Muni 2006
Microréseau	Algorithme génétique	Emballage	Machine à vecteurs de support	EH-DIALL, CLUMP	Jourdan 2005
maladie d'Alzheimer	Test t de Welch	Filtre	Machine à vecteurs de support	Précision de la classification (10 plis)	Zhang 2015
vision par ordinateur	Sélection de fonctionnalités infinie	Filtre	Indépendant	Précision moyenne , AUC ROC	Roffo 2015
Microréseaux	Centralité de vecteur propre FS	Filtre	Indépendant	Précision moyenne, exactitude, aire sous la courbe ROC	Roffo & Melzi 2016
XML	Tau symétrique (ST)	Filtre	Classification structurale associative	Précision, couverture	Shaharanee & Hadzic 2014

Sélection de caractéristiques intégrée aux algorithmes d'apprentissage

Certains algorithmes d'apprentissage effectuent une sélection de caractéristiques dans le cadre de leur fonctionnement global. Il s'agit notamment des suivants :

Les techniques de régularisation α ${\displaystyle l_{1 <semantics><mrow><mstyle><msub><mi>l</mi><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle l_{1}}</annotation></semantics></math><img src=$ , telles que la régression parcimonieuse, LASSO et α - ${\displaystyle l_{1 <semantics><mrow><mstyle><msub><mi>l</mi><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle l_{1}}</annotation></semantics></math><img src=$ SVM, sont utilisées .
Arbres régularisés, par exemple forêt aléatoire régularisée implémentée dans le package RRF
Arbre de décision
Algorithme mémétique
Logit multinomial aléatoire (RMNL)
Réseaux d'auto-encodage avec une couche de goulot d'étranglement
Sélection de caractéristiques sous-modulaires
Sélection de caractéristiques basée sur l'apprentissage local. Contrairement aux méthodes traditionnelles, elle ne nécessite aucune recherche heuristique, gère aisément les problèmes multiclasses et s'applique aux problèmes linéaires et non linéaires. Elle repose par ailleurs sur des fondements théoriques solides. Des expériences numériques ont démontré que cette méthode permet d'obtenir une solution quasi optimale même lorsque les données contiennent plus d'un million de caractéristiques non pertinentes.
Système de recommandation basé sur la sélection de caractéristiques. Les méthodes de sélection de caractéristiques sont introduites dans la recherche sur les systèmes de recommandation.