Forêt aléatoire en ligne
- Introduite par
- Saffari, A. et al.
- Année
- 2009
- Type
- Incremental ensemble (streaming decision trees)
- Famille
- Machine learning
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La Forêt Aléatoire en Ligne (ORF) étend la Forêt Aléatoire classique aux environnements de flux, mettant à jour chaque arbre de manière incrémentielle à mesure que de nouvelles observations arrivent, sans stocker ni rejouer l'ensemble du jeu de données d'entraînement.
Des algorithmes tels que les Forêts Aléatoires Adaptatives (ARF) ajoutent la détection de dérive afin que l'ensemble s'adapte lorsque la distribution des données change au fil du temps.
L’intuition derrière la méthode
La Forêt Aléatoire classique nécessite l'intégralité du jeu de données au préalable pour construire ses arbres. La Forêt Aléatoire en Ligne remplace l'échantillonnage bootstrap par lots par une astuce d'ensachage en ligne pondéré par Poisson : chaque observation entrante est transmise à chaque arbre, qui décide — en tirant un compte de Poisson — combien de fois traiter cet exemple comme un nouveau point d'entraînement. Les arbres se construisent de manière incrémentielle en utilisant des critères de recherche de division en ligne (par exemple, les bornes de Hoeffding), et un module de détection de dérive surveille la dérive du concept, remplaçant les arbres obsolètes par de nouveaux. Le résultat est une forêt qui apprend en continu à partir d'un flux tout en combinant plusieurs arbres diversifiés pour réduire la variance.
Histoire
L'ensachage en ligne a été formalisé par Oza & Russell (2001) comme une approximation pondérée par Poisson de l'agrégation bootstrap. Saffari et al. (2009) ont introduit les Forêts Aléatoires en Ligne combinant l'ensachage en ligne avec la sélection aléatoire de caractéristiques et des critères de division basés sur Hoeffding pour les flux de vision par ordinateur. Gomes et al. (2017) ont introduit les Forêts Aléatoires Adaptatives (ARF), ajoutant la détection de dérive par arbre via ADWIN, et ont démontré une précision de pointe sur des tâches de classification de flux de données de référence. ARF est devenu une base de référence standard dans le cadre MOA (Massive Online Analysis).
Quand l’utiliser
Utilisez la Forêt Aléatoire en Ligne lorsque les données arrivent en continu ou par grands lots qui ne peuvent pas être conservés en mémoire, lorsque la dérive du concept est plausible (par exemple, flux financiers, réseaux de capteurs, journaux de comportement utilisateur), ou lorsque des prédictions à faible latence sont requises avant que l'ensemble du jeu de données ne soit disponible. C'est également une solution naturelle pour les applications où les données étiquetées arrivent progressivement au fil du temps. Évitez-la lorsque l'ensemble du jeu de données tient confortablement en mémoire et que le réentraînement est abordable — dans ce cas, une Forêt Aléatoire standard entraînée hors ligne sera généralement plus précise et plus simple à valider. Évitez-la également lorsque vous avez besoin de classements d'importance des caractéristiques stables et reproductibles, car les forêts en ligne produisent des estimations d'importance moins stables que leurs homologues par lots.
Limites et points d’attention
- Les décisions de division prises tôt avec des données éparses peuvent être sous-optimales et difficiles à réviser.
- Les estimations d'importance des caractéristiques sont moins stables que dans la Forêt Aléatoire par lots.
- Le réglage des hyperparamètres (nombre d'arbres, seuils de détection de dérive) est plus complexe dans un contexte de flux.
- L'évaluation nécessite des protocoles dédiés basés sur les flux (prédictif/test-avant-entraînement) qui diffèrent de la validation croisée standard.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Apprend à partir de données en flux avec une mémoire constante par arbre, indépendamment de la longueur du flux.
- S'adapte à la dérive du concept lorsqu'elle est associée à des mécanismes de détection de dérive tels que ADWIN.
- Hérite des avantages de réduction de variance de l'agrégation d'ensembles même dans un cadre en ligne.
- Fournit des prédictions utilisables dès les premières observations, s'améliorant avec le temps.
- Pas besoin de stocker ou de rejouer l'ensemble du jeu de données historique.
Applications
- Détection de fraude et d'intrusion en temps réel sur les flux réseau ou transactionnels.
- Maintenance prédictive à partir de flux de capteurs où les distributions changent avec le vieillissement de l'équipement.
- Prédiction du taux de clics dans la publicité où le comportement de l'utilisateur évolue quotidiennement.
- Surveillance médicale où l'état du patient change continuellement au fil du temps.
- Détection environnementale et climatique avec des modèles saisonniers non stationnaires.
Comment ça marche
Comment ça marche
Un ensemble de T arbres (ou arbres de Hoeffding) est initialisé. Chaque arbre maintient des statistiques suffisantes par feuille — décomptes de classes ou sommes des carrés pour la régression — au lieu de stocker les observations brutes, rendant le modèle constant en mémoire par arbre.
Pour chaque observation arrivante, chaque arbre tire indépendamment k d'une distribution Poisson(1) et traite l'observation comme k réplications virtuelles de lui-même. Lorsque k = 0, l'arbre ignore le point (agissant comme son échantillon hors-sac). Ceci approxime l'échantillonnage bootstrap sans nécessiter l'ensemble du jeu de données.
Formule
k \sim \text{Poisson}(\lambda),\; \lambda=1Chaque arbre met à jour les statistiques suffisantes à sa feuille active. Une division est déclenchée lorsqu'un critère statistiquement valide (tel que la borne de Hoeffding) indique qu'il est peu probable que la meilleure division change avec plus de données, après quoi la feuille est étendue en un nœud interne et de nouvelles feuilles sont initialisées.
Un module optionnel de détection de dérive (par exemple, ADWIN) surveille l'erreur de prédiction de chaque arbre sur le flux hors-sac. Lorsqu'une dégradation statistiquement significative est détectée, l'arbre affecté est réinitialisé ou remplacé par un arbre fraîchement amorcé, maintenant l'ensemble à jour avec les distributions évolutives.
À tout moment, tous les arbres actifs votent : vote majoritaire pour la classification ou moyenne des prédictions pour la régression. Les arbres qui ont traité très peu d'exemples peuvent être sous-pondérés ou exclus jusqu'à ce qu'ils accumulent suffisamment de données pour donner des votes fiables.
Formule
\hat{y} = \text{mode/mean of active trees}Pièges courants
- Évaluation avec validation croisée k-pli standard, qui suppose des données i.i.d. et ignore l'ordre temporel.
- Ignorer la dérive du concept : ne pas inclure de composant de détection de dérive lorsque la distribution des données change au fil du temps.
- Comparer la précision de la forêt en ligne directement à une Forêt Aléatoire par lots entraînée sur l'ensemble du jeu de données historique — cette dernière a un avantage informationnel inhérent.
- Utiliser trop peu d'arbres au début du flux avant que chaque arbre n'ait vu suffisamment de données pour faire des divisions fiables.
- Oublier que l'ensachage pondéré par Poisson approxime le bootstrap — il ne reproduit pas exactement les propriétés statistiques du bootstrap par lots.
Questions fréquentes
En quoi la Forêt Aléatoire en Ligne diffère-t-elle de la Forêt Aléatoire standard ?
La Forêt Aléatoire standard entraîne tous les arbres simultanément sur l'ensemble du jeu de données en utilisant l'échantillonnage bootstrap. La Forêt Aléatoire en Ligne remplace le bootstrap par lots par l'ensachage en ligne pondéré par Poisson, met à jour les divisions des arbres de manière incrémentielle à mesure que chaque observation arrive, et détecte et s'adapte optionnellement à la dérive du concept — le tout sans stocker les données passées.
Qu'est-ce que l'astuce de pondération par Poisson ?
Chaque exemple entrant est présenté à chaque arbre k fois, où k est tiré de Poisson(1). Comme la valeur attendue de k est 1, et que k = 0 avec une probabilité d'environ 37%, cela approxime statistiquement le processus bootstrap (échantillonnage avec remplacement) sans nécessiter l'ensemble du jeu de données en mémoire.
Comment dois-je évaluer une forêt aléatoire en ligne ?
Utilisez le protocole prédictif (test-avant-entraînement) : pour chaque observation entrante, prédisez d'abord avec le modèle actuel, enregistrez l'erreur, puis mettez à jour le modèle. Cela donne une estimation impartiale et temporellement ordonnée des performances prédictives sans fuite de données.
Quand dois-je ajouter la détection de dérive ?
Chaque fois que le processus de génération de données est susceptible de changer au fil du temps — par exemple, les préférences des utilisateurs, les marchés financiers, ou les systèmes mécaniques qui s'usent. Sans détection de dérive, les arbres obsolètes s'accumulent et dégradent la précision de l'ensemble. ADWIN est un choix courant et bien testé.
La Forêt Aléatoire Adaptative est-elle la même chose ?
ARF est la variante la plus largement adoptée de la Forêt Aléatoire en Ligne. Elle combine l'ensachage en ligne, la sélection aléatoire de caractéristiques et la détection de dérive ADWIN par arbre, et est disponible dans les bibliothèques MOA et scikit-multiflow/River. Le terme 'Forêt Aléatoire en Ligne' fait souvent référence génériquement à la famille ; ARF est une implémentation spécifique, hautement recommandée.
Méthodes associées
Sources
Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.
Ouvrir la référence de la publicationCopié.Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.
Ouvrir la référence DOICopié.