Feature space reduction method for ultrahigh-dimensional, multiclass data: Random forest-based multiround screening (RFMS)

Résumé technique : Écran multi-rounds basé sur les forêts aléatoires (RFMS)

Énoncé du problème
L'article traite du défi de la réduction de l'espace des caractéristiques dans les ensembles de données ultra-hautement dimensionnelles contenant des centaines de milliers de caractéristiques et des milliers de classes. Bien que de nombreuses méthodes de sélection existent pour les données ultra-hautement dimensionnelles, la plupart ne parviennent pas à gérer efficacement les variables de réponse multiclasses. Ce problème spécifique survient fréquemment dans l'authentification biométrique (par exemple, la vérification de signature, l'analyse de la démarche) et en neurosciences, où les modèles de prédiction doivent authentifier les utilisateurs sur la base de données multicanaux. Les méthodes traditionnelles de sélection de variables peinent souvent à identifier l'ensemble optimal de prédicteurs actifs dans de tels espaces hautement dimensionnels, et les techniques de réduction de dimensionnalité comme l'Analyse en Composantes Principales (ACP) ont été signalées comme produisant des résultats insatisfaisants. De plus, les méthodes de sélection existantes manquent souvent de la capacité à examiner les structures interactives et non linéaires d'ordre supérieur inhérentes à ces ensembles de données.

Méthodologie
Les auteurs proposent le Random Forest-based Multiround Screening (RFMS), un nouvel algorithme conçu pour gérer les données multiclasses ultra-hautement dimensionnelles. La méthode fonctionne en divisant l'espace des caractéristiques en sous-ensembles plus petits et en exécutant une série de constructions de modèles partiels pour distiller de manière itérative un sous-ensemble de caractéristiques performant.

L'algorithme procède comme suit :

1. Préparation : Le vecteur de caractéristiques d'entrée $x$ (contenant $n$ caractéristiques) est permuté aléatoirement et divisé en $m$ sous-ensembles de taille $\alpha$.
2. Itération (Tri par tournoi) : L'algorithme traite ces sous-ensembles séquentiellement. À chaque tour $i$, il concatène le sous-ensemble actuel avec les $\beta$ meilleures caractéristiques sélectionnées lors du tour précédent ($z_{i-1}$). Une forêt aléatoire (RF) est entraînée sur cet ensemble combiné pour déterminer l'importance des caractéristiques basée sur la fréquence de sélection (le nombre de fois qu'une caractéristique apparaît dans la forêt de classification).
3. Sélection : Les $\beta$ caractéristiques les plus importantes du tour actuel sont conservées et transmises à l'itération suivante.
4. Résultat : Après avoir traité tous les sous-ensembles, l'ensemble final de $\beta$ caractéristiques représente le sous-ensemble le plus informatif identifié par l'algorithme.

La méthode est implémentée dans un package Julia disponible publiquement. Pour évaluer RFMS, les auteurs ont utilisé BiometricBlender, un générateur de données synthétiques qui crée des espaces de caractéristiques multiclasses ultra-hautement dimensionnels avec une vérité terrain connue et des paramètres d'utilité des caractéristiques. L'ensemble de données de test comprenait 100 classes, 64 échantillons par classe, 10 000 caractéristiques (100 vraies, 300 fausses, et autres), et des structures intercorrélées.

Principales contributions

• Nouvel algorithme : Introduction de RFMS, une méthode spécifiquement adaptée aux problèmes multiclasses ultra-hautement dimensionnels où la sélection traditionnelle échoue.
• Raffinement itératif : Contrairement à la sélection statique, RFMS utilise une approche par tours de type tournoi pour affiner itérativement la sélection des caractéristiques, permettant l'identification de structures non linéaires et interactives.
• Sortie sans transformation : Contrairement à l'Analyse Factorielle (AF) ou à l'ACP, RFMS produit un sous-ensemble des caractéristiques originales plutôt qu'un espace de caractéristiques transformé. Cela préserve l'interprétabilité et permet de calculer uniquement les caractéristiques sélectionnées dans les environnements de production.
• Évaluation comparative : Évaluation complète par rapport aux méthodes standards de l'industrie (ACP, AF, k-best) en utilisant trois classificateurs : k-Plus Proches Voisins (kNN), Classificateur à Vecteurs de Support (SVC) et Forêt Aléatoire (RF).

Résultats
L'étude a comparé RFMS à l'ACP, l'AF et la sélection k-best en utilisant trois classificateurs : k-Plus Proches Voisins (kNN), Classificateur à Vecteurs de Support (SVC) et Forêt Aléatoire (RF).

• Précision : RFMS et l'AF ont surpassé l'ACP et la sélection k-best. La précision la plus élevée (61,4 %) a été obtenue par les combinaisons RFMS–SVC et FA–RF. Notamment, RFMS a démontré une robustesse supérieure à travers différents classificateurs ; bien que FA–RF ait bien performé, l'AF combinée avec kNN ou SVC a donné des précisions nettement inférieures (10 % et 42 %, respectivement). En revanche, RFMS a maintenu une haute performance à travers les trois classificateurs (par exemple, 38,1 % pour kNN, 61,4 % pour SVC).
• Robustesse : RFMS a montré une plus grande stabilité concernant le nombre de caractéristiques sélectionnées. Réduire le nombre de caractéristiques de 500 à 100 n'a que légèrement diminué la précision de RFMS (de ~61 % à 55,4 %), tandis que la précision de l'AF a chuté de manière précipitée (de ~61 % à 25 %) sous des réductions similaires.
• Efficacité : Bien que le temps de sélection initial pour RFMS soit plus long (environ 11 000 s) que pour l'AF ou l'ACP, les auteurs notent que la sélection est effectuée de manière peu fréquente par rapport à l'ajustement du modèle. De plus, les hyperparamètres de RFMS peuvent être ajustés pour réduire considérablement le temps de sélection (par exemple, à ~2 143 s) avec un impact minimal sur la précision.
• Données propriétaires : Sur un ensemble de données propriétaire (10 000 classes, 81 000 échantillons), les caractéristiques filtrées par RFMS ont atteint jusqu'à 93 % de précision de classification, surpassant les caractéristiques transformées par l'AF (environ 82 %), bien qu'avec un temps de sélection plus long.

Signification et affirmations
L'article affirme que RFMS est « sur le même plan que les méthodes de sélection de caractéristiques standards de l'industrie » tout en offrant des avantages distincts en termes de flexibilité, de robustesse et d'opération. La principale signification réside dans sa capacité à sélectionner efficacement des données multiclasses ultra-hautement dimensionnelles — un domaine où peu de méthodes existantes sont applicables.

Les auteurs soulignent que RFMS fournit une solution sans transformation, ce qui est crucial pour les systèmes de production où le coût computationnel et l'interprétabilité sont primordiaux. En sélectionnant un sous-ensemble des caractéristiques originales, la méthode évite de devoir calculer l'ensemble complet des caractéristiques pour chaque nouvel échantillon, ce qui permet d'économiser un temps et des ressources considérables.

L'article conclut modestement, reconnaissant que le générateur de données synthétiques (BiometricBlender) ne reproduit pas encore pleinement toutes les propriétés des données réelles qui mettent au défi les sélecteurs de caractéristiques, particulièrement concernant la performance de l'Analyse Factorielle. Par conséquent, les auteurs suggèrent que les travaux futurs devraient se concentrer sur l'affinement du générateur de données et l'optimisation des hyperparamètres de RFMS (par exemple, détermination automatique de la rétention de caractéristiques, parallélisation et scores de tournoi alternatifs) pour améliorer davantage la précision et l'efficacité computationnelle.