FR 3084742 A1 20200207 FR 1800828 A 20180731 Description Titre de l'invention : PROCEDE POUR DETECTER DISTINCTEMENT DES ANOMALIES ISOLEES, DES ANOMALIES COLLECTIVES ET DES POINTS DE RUPTURES DANS UNE SERIE TEMPORELLE DE MESURES CAPTEUR [0001] La présente invention concerne un procédé pour détecter des anomalies dans des mesures issues de capteurs environnementaux tel que par exemple des mesures de température, d'humidité, de pression, de concentration de gaz ou de niveau. [0002] Ces mesures issues de capteurs sont utilisées par des industriels ou des collectivités pour améliorer la performance de processus industriels, logistique, énergétique ou simplement pour surveiller l'état d'un écosystème. [0003] La qualité des mesures issues des capteurs et en conséquence la détection des anomalies de mesures sont essentielles pour atteindre les objectifs de performances pre-cités. [0004] L'invention peut être utilisée pour optimiser la logistique d'approvisionnement de matière en surveillant à distance le niveau de ces matières dans des cuves de stockage. L'invention peut être utilisée pour surveiller des niveaux d'humidité dans le sol pour déclencher des actions d'irrigation dans le domaine agricole. L'invention peut être utilisée pour surveiller des concentrations de CO2 dans les bâtiments pour déclencher des actions de ventilation. L'ensemble de ces domaines d'application nécessite de détecter et ainsi de réduire au maximum les anomalies de mesures pour prendre les bonnes décisions. [0005] Etat de la technique: [0006] Les méthodes de détection d'anomalies basées sur les approches de calcul de distance sont connues de l'état de l'art. [0007] Par exemple dans la publication E. Eskin, A. Arnold, M. Prerau, L. Portnoy, andS. Stolfo, \A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data," Applications of data mining in computer security, vol. 6, pp. 77{102, 2002}, les auteurs définissent le score d'anomalie d'un échantillon de mesure comme la somme des distances à ses K plus proche voisins. [0008] Dans la publication E. M. Knorr and R. T. Ng, \A unified approach for mining outliers," in Proceedings of the 1997 conference of the Centre for Advanced Studies on Collaborative research, p. 11, IBM Press, 1997 les auteurs definissent le score d'anomalie comme le nombre de plus proches voisins dans une sphere de rayon d. [0009] Dans la publication M. Wu and C. Jermaine, \Outlier detection by sampling with accuracy guarantees," in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 767{772, ACM, 2006, les auteurs utilisent une approche similaire à la précédente mais au lieu de calculer la distance euclidienne l'ensemble des points est converti en une chaine de caractères grâce à l'algorithme de l'état de l'art SAX (Symbolic Aggregate Approximation). Le score d'anomalie est alors l'entropie de la chaîne de caractère. [0010] Cependant l'efficacité de ces techniques est limitée car (i) elles ont des performances faibles sur la détection des anomalies locales(ii) ces techniques ne permettent pas de distinguer une anomalie d'un point de rupture. [0011] On connaît aussi des méthodes de détection basées sur un calcul de densité. Il existe de nombreuses techniques pour calculer la densité. [0012] Par exemple dans la publication M. M. Breunig, H.-P. Kriegel, R. T. Ng, and J. Sander, \Lof: ldentifying density-based local outliers," SIGMOD Rec., vol. 29, pp. 93{104, May 2000 les auteurs définissent le score Local Outlier Factor (LOF) comme le ratio entre la moyenne des densités locales des K plus proches voisins sur la densité locale du point considéré. [0013] Dans la publication J. Tang, Z. Chen, A. W.-c. Fu, and D. Cheung, \A robust outlier detection scheme for large data sets," in In 6th Pacific-Asia Conf. on Knowledge Discovery and Data Mining, Citeseer, 2001 les auteurs définissent la technique Connectivity-based Outlier Factor (COF) qui estime la densité locale du voisinage en utilisant une approche du plus court chemin que l'on appelle la distance de chainage. La distance de chainage d'un point etant la somme des distances qui connectent les K-voisins avec le point considéré. [0014] Dans la publication Z. He, X. Xu, and S. Deng, \Discovering cluster-based local outliers," Pattern Recognition Letters, vol. 24, no. 9, pp. 1641{1650, 2003 les auteurs utilisent la encore une technique basée sur la densité qui calcule le nombre de voisins dans un cercle autour d'un point de mesure comme score d'anomalie. [0015] Enfin Twitter propose une methode open source nommée Seasonal Hybrid ESD décrite dans la publication dans J. Hochenbaum, O. S. Vallis, and A. Kejariwal, \Automatic anomaly detection in the cloud via statistical learning," arXiv preprint arXiv:1704.07706, 2017. Cette technique utilise une décomposition saisonnière et une métrique statistique pour détecter les anomalies. [0016] Cependant l'efficacité de ces techniques sont limitées car (i) la performance de la detection est tres sensible aux paramètres d'entrée tel que le rayon K. (ii) Les fausses detections des points de rupture sont fréquentes. [0017] Définitions [0018] Série ou fenêtre temporelle : séquence finie de données scalaires indexées par le temps. [0019] Classification : Processus aboutissant à assigner à un état d'une entité une classe connue donnant lieu à des actions prédéterminées de la part de l'opérateur de réseau. [0020] Mesure : C'est l'estimation de la valeur d'une grandeur en unité correspondant, ces valeurs formant une série temporelle fournie par un système d'acquisition de données. [0021] Caractéristique : scalaire ou vecteur constituant une information significative pour le processus étudié [0022] Point de rupture : Changement brutal dans la séquence de mesure qui représente bien le paramètre physique mesuré mais qui peut être perçue à tort comme une anomalie. Exemple : rechargement d'une cuve dont on monitore le niveau, ouverture d'une fenêtre qui renouvelle l'air et dilue le CO2,... [0023] Anomalie collective : Ce type d'anomalie contient un ensemble d'anomalies consécutives qui représente un pattern de mesure aberrantes. Le pattern n'est pas conforme à la distribution des mesures normales. [0024] Anomalie isolée : Une simple mesure est une anomalie si elle significativement différente du reste des mesures. [0025] Méthode probabiliste : Désigne un type de méthodes ou algorithmes basés sur des calculs de probabilités et utilisés pour la mise en oeuvre de machine d'auto-apprentissage (machine learning) tel que la classification. Les arbres de décision sont par exemple une méthode probabiliste [0026]Résumé de l'invention [0027] La présente invention vise à pallier ces inconvénients, et propose un procédé de détection automatique d'anomalies avec les caractéristiques suivantes : - Le procédé permet de bien distinguer les points de rupture et les anomalies - Le procédé permet de détecter des séries continues de mesures aberrantes (non isolée) - Le procédé permet d'être peu sensible aux paramètres d'entrée Le procédé est relativement économique en termes de puissance de traitement informatique - Le procédé est capable d'enrichir les données d'apprentissage à partir d'anomalies marquées par une interaction humaine [0028] L'invention est un procédé pour détecter des anomalies dans une série temporelle d'échantillons de mesures physiques issues de capteurs et séparées par des intervalles de temps, le procédé est caractérisé par les étapes suivantes : [0029] Etape 1- définir des fenêtre temporelles correspondant chacune à des intervalles de temps [0030] Etape 2- rechercher dans chaque fenêtre temporelle les échantillons candidats « anomalies » ou les candidat « points de rupture » sans les discriminer. [0031] Etape 3- produire un vecteur de métriques scores pour chaque candidat retenu qui évaluent le caractère isolé du candidat. [0032] Etape 4- utiliser une méthode probabiliste couplé avec une méthode d'apprentissage actif pour classifier les candidats. Un candidat pouvant être assigné à la classe « anomalie », la classe « anomalie collective » ou la classe « point de rupture » [0033] L'intervalle de temps entre deux mesures (échantillons) d'une série temporelle est par exemple de quelques minutes, par exemple 10 minutes. [0034] La durée d'une fenêtre temporelle est variable en fonction de la fréquence de mesure et du cas d'usage (un cycle complet en mesure de qualité d'air est couvert en 24h, la vidange d'une cuve peut se faire en plusieurs semaines).. Ainsi une série temporelle comprend typiquement de nombreuses mesures (échantillons). On peut avantageusement mettre en oeuvre le procédé simultanément pour des fenêtres temporelles de durées différentes. [0035] Pendant une fenêtre temporelle, les paramètres mesurés par les capteurs, et constituant les séries temporelles, subissent des variations, par exemple en fonction de paramètres tels que l'heure, la saison, la météorologie, ou des interventions humaine tel que l'apport de matière dans une cuve dont on mesure le niveau. [0036] Selon un mode de réalisation, pour rechercher les échantillons candidats on utilise une métrique basée sur la déviation médiane absolue. [0037] Pour rechercher les échantillons candidats on compare la valeur de l'échantillon candidat avec le cumul de la déviation médiane absolue et de la médiane selon la méthode suivante : [0038] Calculer la déviation de la médiane absolue sur les échantillons )(Me la fenetre W tel que W=(X0--XN-1) [Math. 1] MAD(W) = Mediane(IW - Mediane(W)I) Xi est consideré comme candidat si: [Math. 2] Xi > MAD(W)+ Median(W) [0039] Au coeur de l'invention il y a le calcul de métrique score qui permettent d'évaluer le caractère isolé d'un candidat pour discriminer selon trois classes : les anomalies isolées, les anomalies collectives, et les points de ruptures. [0040] Selon un mode de réalisation, pour chaque candidat 0i, les trois métriques score MS, CS et VS sont calculées selon la séquence suivante : [0041] Etape 1 : pour chaque candidat 0i, déterminer Size (INN(0i)), le nombre des K plus proches voisins de Oi selon la méthode dite des K plus proches voisins réciproques qui est revendiquée comme nouvelle dans le cadre de cette invention. La méthode des K plus proche voisins réciproques est une extension de la méthode des K plus proche voisins bien connu de l'état de l'art et décrite dans l'ouvrage de référence "Pattern Classification" by Duda and Hart. Si on appelle les K plus proches voisin de Oi: NNK (0i) alors les K plus proches voisins réciproques /NNK (0i) sont définis comme suit : Etant donnés Oi et Xi dans un ensemble de données W, alors les K plus proches voisins réciproques /NNK (0i) sont définis formellement comme suit : [Math. 3] Xi E INNK (Of) si Xi E NNK (Os) et Oi E NNK (Xi) [0042] Etape 2 : pour chaque candidat 0i, calculer MS(0i) le « Magnitude Score » de Oi qui donne une information sur l'isolation d'un point. [Math. 4] Size (INN (0,)) MS(°i) - Size(W) [0043] Etape 3 : utiliser la méthode dite "Symbolic Aggregate Approximation" (SAX) pour transformer les séries temporelles INN(0j) et W en deux chaines de carracteres n and 1c respectivement. La méthode "Symbolic Aggregate Approximation" (SAX) est bien connue de l'etat de l'art et est décrite dans Lin, Jessica, et al. "A symbolic representation of time series, with implications for streaming algorithms." Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery. ACM, 2003. [0044] Etape 4 : calculer le "correlation score" CS(01) qui represente la frequence d'occurrence de i dans K [Math. 5] CS(0i) = 71K [0045] Etape 5 : Calculer crw l'écart type des echantillons de la fenetre W ainsi que crwumNro,» l'écart type de la fenêtre W dont on a retiré les echantillons INN(01) [0046] Etape 6 : Calculer le "Variance Score" (VS) du candidat Oi qui représente la variation de l'écart type apres avoir retiré de la fenetre temporelle les echantillons INN(X1) [Math.6] VS(Z) = ciwurNN(0,)) [0047] Selon un mode de réalisation, on utilise un modèle d'apprentissage automatique de type « random forest » issus des techniques d'auto-apprentissage machine (« machine learning »), appliqués aux vecteurs de métriques score pour classifier les candidats. La méthode de classification random forest est bien connue de l'état de l'art. Elle est décrite dans : A. Liaw, M. Wiener, et al., Classification and regression by random forest,"R news, vol. 2, no. 3,pp. 18-22, 2002. [0048] L'entrée du modèle est une matrice dont les lignes sont les triplets de métriques scores obtenues pour chaque candidat.[Math. 7] [VSx2, MSx2, CSx2] [V.Sx2, MSx2, CSx2I with Xi e Candidate List [17Sxn, MSxn, CSxn] [0049] La sortie du modèle est une matrice dont chaque ligne représente la probabilité pour chaque candidat d'être une anomalie, un point de rupture ou une anomalie collective. [Math. 8] o-w [Pr_AN,,Pr_CAxi,Pr_CPxi] Candidate List [Pr_ANx2,Pr_CAx2,Pr_CPx2] with xi E [Pr_ANx,Pr_CAxn,Pr_CPx.] Pr_AN, Pr_CA, Pr_CP représentent la probabilité d'être une anomalie, une anomalie collective ou un point de rupture. [0050]A chaque itération sur le modèle un utilisateur humain peut si il le souhaite forcer une décision sur un candidat afin d'améliorer le modèle. [0051] Lors d'une étape d'initialisation, on peut avantageusement selon l'invention définir sous la forme d'une matrice les règles de décision qui permettent d'amorcer l'algorithme d'apprentissage automatique. [0052] Présentation des figures [0053] Les avantages et caractéristiques de l'invention seront mieux appréciées grâce à la description qui suit. La description s'appuie sur les figures annexées qui représentent : [0054] [Fig. 1] : Une représentation schématique des différents éléments d'un système mettant en oeuvre un procédé selon l'invention [0055] [Fig. 2]: Un organigramme des étapes du procédé selon un mode de réalisation de l'invention [0056] [Fig. 3]: Un organigramme des étapes du procédé de classification selon un mode de réalisation de l'invention [0057] [Fig. 4]: Un graphique illustrant un exemple de série temporelle de mesures capteur incluant des anomalies isolées des anomalie collective et des points de rupture [0058] [Fig. 5]: Un graphique illustrant un résultat de détection des candidats basé sur le calcul de médiane absolue [0059] [Fig. 6]: Un graphique illustrant un résultat de classification automatique d'anomalies et point de rupture [0060] Description détaillée dans mode de réalisation [0061] Nous présentons ici à titre d'exemple un mode de réalisation particulier pour la surveillance de niveau de remplissage de cuve de produit chimique afin d'optimiser la logistique d'approvisionnement de ces produits chimiques. Ce mode de réalisation n'est nullement limitatif. [0062] Comme on le voit sur la [Fig. 1], le système met en oeuvre en premier lieu un capteur de niveau 10. [0063] Le système met en oeuvre en second lieu un lien sans fil 11 entre le capteur et une plateforme de calcul 12 et sa base de données 13. Ce lien sans fil peut être par exemple une liaison cellulaire ou WIFI. Les mesures brutes de niveau issues du capteur transitent sur le lien 11 entre le capteur et le calculateur. Cette plateforme de calcul accueille un programme informatique qui implémente les traitements de l'invention présentée. Le rôle du programme informatique et par conséquent de l'invention est de détecter les anomalies parmi les mesures transmises par le capteur. [0064] Le système met en oeuvre en troisième lieu un lien filaire ou sans fil entre le calculateur et une plateforme de supervision 14 présentant des tableaux de bord à un utilisateur final du dispositif. L'utilisateur final peut agir sur le dispositif en taguant certaines mesures qu'il juge comme étant des anomalies afin d'enrichir le processus d'apprentissage actif. [0065] Dans ce mode de réalisation particulier le calculateur est déployé sur une infrastructure « cloud ». [0066] La [Fig. 2] représente un organigramme des étapes du procédé selon l'invention dans un mode de réalisation nullement limitatif. Comme on le voit sur cette figure le procédé comporte plusieurs étapes : [0067] Dans une première étape 20 le programme informatique fait l'acquisition des échantillons de mesures brutes issues du capteur sous la forme de fenêtres de séries temporelles qui sont stockées en mémoire sous la forme de vecteurs. La taille de la fenêtre temporelle est dimensionnée de manière à avoir plusieurs points de rupture et éventuellement plusieurs anomalies. Dans un mode de réalisation particulier la taille de la fenêtre est fixée à mille échantillons de mesures. Chaque série temporelle est susceptible de contenir des mesures aberrantes (anomalies) ou des points de rupture. Dans cet exemple de réalisation de l'invention un point de rupture peut être associé à un évènement de remplissage de la cuve qui fait passer le niveau de la cuve d'un niveau bas à un niveau haut dans un temps qui peut être inferieur à l'intervalle de temps entre deux mesures de la série. La [Fig. 4] représente en 42 un tel point de rupture. La [Fig. 4] représente en 41 une anomalie isolée et en 40 une anomalie collective. Dans ce mode de réalisation une anomalie isolée peut être due à une erreur de communication entre le capteurs 10 et son microprocesseur embarqué 16. Dans ce mode de réalisation une anomalies collectives (ou succession d'anomalies) peut être due à un obstacle temporaire qui s'installe entre le capteur et le produit dont il faut mesurer le niveau. Dans ce mode de réalisation la taille d'une série temporelle est fixée à mille échantillons de mesures qui correspondent à environ deux semaines de mesures. Cette série temporelle est stockée dans la mémoire du calculateur. [0068] Dans une seconde étape 21 pour chaque fenêtre temporelle on recherche les candidats potentiellement anomalies isolée, anomalies collectives ou point de rupture représentés respectivement à titre d'exemple en 50 sur la [Fig. 5]. Dans cette étape le dit programme informatique exécuté sur le calculateur 12 calcule pour chaque fenêtre temporelle W=(X0..X1v_1) une métrique MAD dite déviation médiane absolue.[Math. 1] MAD(W) = MedianeaW - Mediane(W)I) [0069] Ensuite le programme informatique vérifie la relation suivante pour chaque échantillon Xi : [Math. 2] Xi > MAD(W) + Median(W) Si la relation est vrai alors Xi est stocké en mémoire dans le vecteur des candidats 0=(00.. [0070] Dans une troisième étape 22 le programme informatique met en oeuvre une technique d'auto apprentissage machine du type « machine learning » pour classifier les candidats parmi les trois classes : anomalie isolée, anomalie collective, point de rupture. Dans ce mode de réalisation cette technique d'auto apprentissage est complétée par un procédé d'apprentissage actif. [0071] Le process de classification peut être mis à jour à chaque nouvelle mesure reçue ou bien dans un mode de réalisation préférée à chaque nouvelle série d'échantillons de mesures reçues. [0072] Le modèle classificateur est alimenté avec les métriques score qui caractérisent chacun des échantillons de mesure candidats. Il est aussi alimenté par les données d'apprentissage. [0073] Dans mode de réalisation on alimente le classificateur avec une matrice dont les lignes sont chacunes composées de trois métriques score qui caractérisent un échantillon de mesure candidat. Le nombre de lignes de la matrice caractérise donc le nombre de candidats qui alimentent le modèle. [0074] La technique d'auto apprentissage de classification est amorcée avec une matrice de règles de décisions préalablement définie. Dans un mode de réalisation, ces règles de décisions sont définies en associant un triplet de métriques score avec une classe décidée. [0075] Dans un mode de réalisation non limitatif on peut définir des règles de décisions de la manière suivante : [0076] Oi est une anomalie isolée si MS=1, CS 0.5 Oi est une anomalie collective si MS= = 0.5 Oi est un point de rupture si MS>0.05, CS>0.1 et VS