Dérive conceptuelle

En analyse prédictive et en apprentissage automatique, on parle de dérive conceptuelle lorsque les propriétés statistiques de la variable cible, que le modèle essaie de prédire, évoluent au cours du temps d'une manière imprévue^[1]. Ceci pose des problèmes parce que les prédictions deviennent moins exactes au fur et à mesure que le temps passe. La notion de Concept se réfère à la mesure que l'on veut prédire. Plus généralement, il peut faire référence à d'autres phénomènes intéressants en dehors des concepts cibles, tels que les entrées. La dérive conceptuelle est une des contraintes en fouille de flux de données.

Définitions

Mihai M. Lazarescu^[2] définit la dérive conceptuelle en termes de consistance et de persistance.
Définition 1 : soit θ_t le concept à l'instant t=0,1,...n et soit $\epsilon_t=\theta_t - \theta_{t-1}$ le changement de concept entre les instants t-1 et t. Un concept est consistant si $\epsilon_t \le \epsilon_c$ où $\epsilon_c$ est un seuil de consistance prédéfini.
Définition 2 : soit Χ la taille de la fenêtre temporelle contenant les observations. Un concept est persistant si $\epsilon_{t-p}, \epsilon_{t-p+1},...,\epsilon_t \le \epsilon_c$ et $p \ge \frac{\Chi }{2}$ où p est la persistance du changement , c'est-à-dire le nombre d'observations consécutives pendant lesquelles le changement est consistant.
Définition 3 : La dérive est permanente si elle est à la fois persistante et consistante. La dérive est virtuelle^[3] si elle est consistante mais pas persistante. La dérive est considérée comme du bruit si elle n'est ni consistante, ni persistante.

Prise en compte

La prise en compte de la dérive conceptuelle en fouille de flux de données se fait soit implicitement, soit explicitement^[4].

implicite

La prise en compte implicite se fait par l'intermédiaire du stockage de l'information.

• Si les statistiques sur les observations sont entièrement stockées, celles-ci sont pondérées par leur ancienneté en mémoire. Plus elles sont âgées et moins elles ont d'importances. La diminution du poids des observations âgées se fait linéairement ou d'une manière exponentielle.
• Si les statistiques conservées en mémoire sont celles des observations des plus récentes, celles-ci sont utilisées avec des fenêtres temporelles fixes ou bien adaptatives.

Dans ces deux cas la prise en compte de la dérive conceptuelle se fait par l'oubli, on ne tient compte que des observations les plus récentes et on oublie les plus anciennes. Les algorithmes basés sur les classifieurs multiples (les méthodes-ensembles) tels que DWM^[5], « LIFT-based weight assigning » et « adaptive classifiers for changing environments (ACE) »^[6] utilisent cette approche.

explicite

La prise en compte explicite s'effectue par l'intermédiaire de méthodes de détections.

• Certaines utilisent des indicateurs comme l'exactitude, le rappel et la précision pour détecter le changements de concepts. On trouve dans cette catégorie des algorithmes tel que FLORA et FLORA2.
• D'autres utilisent deux fenêtres temporelles, l'une comme référence, l'autre contenant les plus récentes observations^[7]. VFDT de Joao Gama utilise cette technique.

Voir aussi

Liens internes

• Fouille de flots de données
• Algorithme de fouille de flots de données
• Glossaire du data mining

Liens externes

• (en) ECMLPKDD 2010 International Workshop on Handling Concept Drift in Adaptive Information Systems
• (en) Michèle Basseville, Igor V. Nikiforov, Detection of Abrupt Changes:Theory and Application
• (en) Ryan Elwell, Robi Polikar, Incremental Learning of Variable Rate Concept Drift

Notes

(en) Cet article est partiellement ou en totalité issu de l’article en anglais intitulé « Concept drift » (voir la liste des auteurs)

Références

1. ↑ Alexey Tsymbal, The problem of concept drift: definitions and related work
2. ↑ Mihai M. Lazarescu, Svetha Venkatesh, Hung H. Bui,Using Multiple Windows To Track Concept Drift
3. ↑ Peter Vorburger, Abraham Bernstein, Entropy-based Detection of Real and Virtual Concept Shifts
4. ↑ Joao Gama, Kowledge Discovery from Data Stream, CRC Press, 2010, page 37-38
5. ↑ J. Zico Kolter, Marcus A. Maloof, Dynamic Weighted Majority: An Ensemble Method for Drifting Concepts
6. ↑ Kyosuke Nishida, Koichiro Yamauchi,Takashi OmoriACE: Adaptive Classifiers-Ensemble System for Concept-Drifting Environments
7. ↑ Daniel Kifer, Shai Ben-David, Johannes Gehrke, Detecting Change in Data Streams

Bibliographie

• Kolter, J.Z. and Maloof, M.A. Dynamic Weighted Majority: An ensemble method for drifting concepts. Journal of Machine Learning Research 8:2755--2790, 2007. PDF
• Scholz, Martin and Klinkenberg, Ralf: Boosting Classifiers for Drifting Concepts. In Intelligent Data Analysis (IDA), Special Issue on Knowledge Discovery from Data Streams, Vol. 11, No. 1, pages 3-28, March 2007.
• Maloof M.A. and Michalski R.S. Selecting examples for partial memory learning. Machine Learning, 41(11), 2000, pp. 27-52.
• Mitchell T., Caruana R., Freitag D., McDermott, J. and Zabowski D. Experience with a Learning Personal Assistant. Communications of the ACM 37(7), 1994, pp. 81-91.
• Schlimmer J., Granger R. Beyond Incremental Processing: Tracking Concept Drift. AAAI 1986.
• Wang H., Fan W., Yu Ph. S. and Han J. Mining concept-drifting data streams using ensemble classifiers. KDD 2003.
• Widmer G. and Kubat M. Learning in the presence of concept drift and hidden contexts. Machine Learning 23, 1996, pp. 69-101.