Brevet FR3076384A1 — publié le 20190705

DETECTION D'ANOMALIES PAR UNE APPROCHE COMBINANT APPRENTISSAGE SUPERVISE ET NON-SUPERVISE DOMAINE DE L' INVENTION La presente invention concerne la detection d'anomalies dans un ensemble de transactions. Elle concerne notamment la detection de fraudes dans des transactions financieres. CONTEXTE DE L' INVENTION Dans la plupart des cas pratiques, le volume des donnees a traiter est enorme. C'est notamment le cas du volume des transactions financieres que les serveurs d'une banque sont amenes a gerer quotidiennement (retraits et achats par carte bancaire, etc.). Ce peut etre le cas des transactions de service sur des services web (non necessairement financieres). Il est connu de faire appel a des techniques de traitement automatique des donnees afin de pouvoir analyser ces donnees et y determiner des anomalies le plus rapidement possible. Ces anomalies peuvent etre des simples erreurs, mais egalement des fraudes. Les fraudeurs cherchant a dejouer les parades mises en place, it est difficile de pouvoir caracteriser un comportement typique qui pourrait guider la recherche de fraudes dans un important volume de donnees. Il est donc necessaire d'analyser l'ensemble des donnees pour y detecter des transactions atypiques. Ces transactions atypiques sont alors presentees a un operateur humain qui les analyse afin de decider de leur caractere frauduleux ou non et declencher d'eventuelles contremesures. Il est donc important d'a la fois determiner un ensemble de transactions suspectes qui minimise les transactions frauduleuses non detectees, mais qui minimise aussi la sur-detection (ou fausses alertes) afin de limiter la charge des operateurs humains. Les techniques automatiques permettant de considerer cette problematique generale se basent en general sur un mecanisme d'apprentis sage, permettant de construire un « modele » qui formalise la « typicite » des transactions. Les nouvelles transactions sont ensuite presentees a ce modele qui peut alors predire un caractere anormal (notamment frauduleux) ou non, par rapport a ce modele de typicite. 2 Ces techniques d'apprentissage (typiquement appelees « machine learning » en anglais) peuvent se diviser en deux grandes families, basees sur un apprentissage supervise ou sur un apprentissage non supervise. Dans le cas d'un apprentissage supervise, on indique pour chaque transaction 5 du jeu d'entrainement si elle represente une anomalie ou non. Cette indication (ou etiquette, « label » en anglais) est utilisee pour la construction du modele. En consequence, la detection d'une anomalie pour une nouvelle transaction peut se ramener a une Cache de classification. L'apprentissage supervise permet de bien detecter les anomalies qui 10 correspondent a une classe determinee par le jeu d'apprentissage. Cependant, une anomalie qui ne correspond pas bien a une classe prealablement determinee ne sera pas correctement detectee. En fait, par essence meme, ces methodes visent a determiner des classes correspondant aux anomalies presentees dans le jeu d'apprentissage. Or, les fraudeurs sont 15 sans cesse en recherche de nouvelles strategies de fraude, et leur comportement visent donc a echapper a toute tentative de classification deterministe. Il est alors necessaire de regulierement entrainer de nouveau le modele de classification pour prendre en compte les nouveaux types d'anomalies. Mais tant que le nombre de transactions d'un nouveau type n'est pas suffisamment important, le modele ne 20 pourra pas les classifier correctement. D'une fawn plus generale, ce type d'approche souffre du faible nombre d'anomalies qui ne permet pas toujours une bonne classification. L'autre grande famille methodologique est celle de l'apprentis sage non supervisee. Selon le principe, un jeu d'entrainement est egalement utilise mais on n'associe 25 aucune information aux transactions du jeu d'entrainement indiquant s'il s'agit d'une transaction representant une anomalie ou non. Le modele se constitue donc en determinant des « tendances synthetiques » dans ce jeu d'entrainement, et les transactions anormales sont considerees comme celles presentant une anomalie par rapport au modele ainsi constitue. 30 Un avantage de cette approche est de ne pas faire de supposition sur des types ou classes d'anomalies (ou fraudes). Elle permet ainsi d'être plus robuste et efficace pour la detection de nouveaux types de fraudes. 3 Toutefois, elle souffre de la difficulte de distinguer des transactions presentant effectivement une anomalie, de celles ne presentant pas d'anomalies mais detectees comme suspectes par le modele. D'une fawn generale, les methodes non supervises presentent un important taux de fausses alertes. 5 RESUME DE L' INVENTION Le but de la presente invention est de fournir une solution palliant au moins partiellement les inconvenients precites. A cette fin, la presente invention propose un procede pour la detection 10 d'anomalies dans un ensemble de transactions etablies au travers d'un reseau de telecommunication, comportant la determination pour chaque transaction d'un ensemble de valeurs de parametres associees a ladite transaction ; le parcours, pour chaque transaction, d' au moins un arbre prealablement defini 15 sur un jeu d'entrainement, en comparant les valeurs desdits parametres avec les valeurs associes a chaque nceud dudit au moins un arbre, jusqu'a ce qu'une feuille soit atteinte ; ledit au moins un arbre etant entraine de sorte de sorte que chacune des feuilles dudit arbre corresponde a une unique transaction dudit jeu d'entrainement et que ses feuilles soient associees, chacune, a une indication si celles-ci correspondent a une transaction normale 20 ou en anomalie, la determination d'un score en fonction d'une premiere metrique dependant de la position de ladite feuille dans ledit arbre, et d'une seconde metrique dependant desdites indications des feuilles, ledit score indiquant une estimation que ladite transaction est normale ou en anomalie. 25 Suivant des modes de realisation preferes, l'invention comprend une ou plusieurs des caracteristiques suivantes qui peuvent etre utilisees separement ou en combinaison partielle entre elles ou en combinaison totale entre elles : - le procede comporte en outre une etape de determination pour chaque nceud du chemin entre ladite feuille et la racine dudit au moins un arbre, d'un nombre 30 d'anomalies cumulant les indications qu'une transaction soit en anomalie, associees a l'ensemble des feuilles descendantes dudit nceud, et dans lequel ladite seconde metrique est la somme des nombres d'anomalies sur l'ensemble des nceuds dudit chemin ; 4 - le procede comporte en outre une etape de determination (S4) pour chaque nceud du chemin entre ladite feuille et la racine dudit au moins un arbre, d'un nombre d' anomalies cumulant les indications qu'une transaction soit en anomalie, associees a l'ensemble des feuilles descendantes dudit nceud, et dans lequel ladite seconde 5 metrique est la distance entre ladite feuille et le nceud le plus proche dudit chemin pour lequel ledit nombre d'anomalie est non nul ; - ladite premiere metrique est la profondeur de ladite feuille dans ledit au moins un arbre ; - ledit au moins un arbre forme une foret d'arbres, chaque arbre de ladite 10 foret etant defini sur un jeu d'entrainement different ; - ledit au moins un arbre est defini, a partir d'un nceud racine, par un processus recursif comprenant les stapes de : choix aleatoire d'un parametre parmi l'ensemble des parametres des transactions dudit jeu d'entrainement ; 15 division de l'ensemble des valeurs prises par ledit parametre pour l'ensemble desdites transactions, en une pluralite de sous-ensembles ; creation de nceuds fils, chacun correspondant a l'un des sous-ensembles de ladite pluralite; dans lequel ledit processus recursif s'arrete lorsque le nceud considers 20 correspond a une unique valeur, de sorte que chacune des feuilles dudit arbre correspond a une unique transaction dudit jeu d'entrainement, une indication si celui-ci correspond a une transaction normale ou en anomalie etant alors associee audit nceud considers. - ledit au moins un arbre est un arbre binaire et ladite pluralite de sous- 25 ensembles est form& de deux sous-ensembles ; - ledit au moins arbre est un « itree ». Un autre objet de l'invention est relatif a un programme d'ordinateur comportant du code pour mettre en oeuvre un procede tel que precedemment defini, 30 lorsque execute sur un ordinateur. 5 D'autres caracteristiques et avantages de l'invention apparaitront a la lecture de la description qui suit d'un mode de realisation prefere de l'invention, donnee a titre d'exemple et en reference aux dessins annexes. 5 BREVE DESCRIPTION DES DESSINS La figure 1 represente schematiquement un organigramme relatif a un mode de realisation de l'invention. La figure 2 represente schematiquement un exemple d' arbre construit et entraine selon un mode de realisation de l'invention. 10 DESCRIPTION DETAILLEE DE L'INVENTION L'invention repose sur une phase d'apprentissage qui consiste a creer et entrainer au moins un arbre modelisant l'ensemble des transactions du jeu d'entrainement, puis une phase d'exploitation durant laquelle on confronte de nouvelles transactions a 15 l'arbre ou arbres afin d'en &duke des scores. Ces scores permettent d'indiquer si les transactions correspondantes sont des anomalies ou normales. Selon un mode de realisation de l'invention, ces deux etapes peuvent etre concomitantes, au sens que les nouvelles transactions presentees pendant la phase d'exploitation peuvent egalement entrainer l'arbre, ou les arbres. Le modele est ainsi 20 dynamique et en constante adaptation au flux de donnees. Selon un mode de realisation de l'invention, une pluralite d'arbres, formant une « foret » est consideree. Cette fawn de faire permet d'apporte une meilleure robustesse de l'apprentissage par rapport au jeu d'entrainement et aux tirages aleatoires effectuees dans le cadre du processus d'apprentissage qui va etre decrit. 25 Dans une premiere etape, indiquee 51 sur la figure 1, on determine un ensemble de valeurs de parametres caracteristiques des transactions. Le choix de ces parametres depend de la nature des transactions considerees et de choix operationnels. Par exemple, dans le cas de transactions financieres (achats en ligne ou par carte bancaire), on peut determiner comme parametres : le montant de la 30 transaction, les parties a la transaction (par exemple, un acheteur et un vendeur, ou plus generalement, un debiteur et un crediteur), une date, un horaire, un lieu physique des parties au moment de la transaction, etc. 6 Tout element transmis par les reseaux de communication au serveur en charge d'effectuer la transaction peuvent etre pris en compte, dans la mesure oil il peut permettre de caracteriser une eventuelle anomalie dans un ensemble de transactions. En consequence, l'invention ne se limite pas aux exemples de parametres mentionnes ci- 5 dessus, mais est susceptibles de prendre en compte tout parametre disponible. La phase d'apprentissage S2 est un processus iteratif visant a creer un arbre, ou une foret d'arbres, dans lequel chaque iteration considere un parametre afin de subdiviser l'ensemble des valeurs pris par ce parametre sur l'ensemble des transactions du jeu d'apprentissage, de sorte a, au bout d'un nombre suffisant d'iterations, isoler chaque 10 transaction dans une feuille de l'arbre. Ce processus d'apprentissage s'inspire des arbres d'isolation, ou « isolation tree » en langue anglaise, ou encore iTree. Une definition de ce type d'arbre est notamment donne dans l' article « Isolation Forest >> de Feil Tony Liu, Kai Ming Ting et Zhi-Hua Zhou, in Proceedings of the 2008 Eighth IEEE International Conference on Data 15 Mining (ICDM '08). Selon cet article, un arbre d'isolation est defini comme un ensemble de nceuds T, de sorte que T est soit une feuille, soit un nceud interne associe a un test et exactement deux nceuds fils Ti, Tr. Le test consiste en un attribut q et une valeur pivot p, de sorte que q REVENDICATIONS1. Procede pour la detection d'anomalies dans un ensemble de transactions etablies au travers d'un reseau de telecommunication, comportant - la determination (S1) pour chaque transaction d'un ensemble de valeurs de parametres associees a ladite transaction ; - le parcours (S3), pour chaque transaction, d'au moins un arbre prealablement defini sur un jeu d'entrainement, en comparant les valeurs desdits parametres avec les valeurs associes a chaque nceud dudit au moins un arbre, jusqu'a ce qu'une feuille soit atteinte ; ledit au moins un arbre etant entraine (S2) de sorte de sorte que chacune des feuilles dudit arbre corresponde a une unique transaction dudit jeu d'entrainement et que ses feuilles soient associees, chacune, a une indication si celles-ci correspondent a une transaction normale ou en anomalie, - la determination (S5) d'un score en fonction d'une premiere metrique dependant de la position de ladite feuille dans ledit arbre, et d'une seconde metrique dependant desdites indications des feuilles, ledit score indiquant une estimation que ladite transaction est normale ou en anomalie. 2. Procede selon la revendication precedente, comportant en outre une etape de determination (S4) pour chaque nceud du chemin entre ladite feuille et la racine dudit au moins un arbre, d'un nombre d'anomalies cumulant les indications qu'une transaction soit en anomalie, associees a l'ensemble des feuilles descendantes dudit nceud, et dans lequel ladite seconde metrique est la somme des nombres d'anomalies sur l'ensemble des nceuds dudit chemin. 3. Procede selon la revendication 1, comportant en outre une etape de determination (S4) pour chaque nceud du chemin entre ladite feuille et la racine dudit au moins un arbre, d'un nombre d'anomalies cumulant les indications qu'une transaction soit en anomalie, associees a l'ensemble des feuilles descendantes dudit nceud, et dans lequel ladite seconde metrique est la distance entre ladite feuille et le nceud le plus proche dudit chemin pour lequel ledit nombre d'anomalie est non nul. 13 4. Procede selon l'une des revendications precedentes, dans lequel ladite premiere metrique est la profondeur de ladite feuille dans ledit au moins un arbre. 5. Procede selon l'une des revendications precedentes, dans lequel ledit au 5 moins un arbre forme une foret d'arbres, chaque arbre de ladite foret etant defini sur un jeu d'entrainement different. 6. Procede selon l'une des revendications precedentes, dans lequel ledit au moins un arbre est defini, a partir d'un nceud racine, par un processus recursif comprenant 10 les stapes de : - choix aleatoire (S21) d'un parametre parmi l'ensemble des parametres des transactions dudit jeu d'entrainement ; - division (S22) de l'ensemble des valeurs prises par ledit parametre pour l'ensemble desdites transactions, en une pluralite de sous-ensembles ; 15 - creation (S23) de nceuds fils, chacun correspondant a l'un des sous- ensembles de ladite pluralite; dans lequel ledit processus recursif s'arrete lorsque le nceud considers correspond a une unique valeur, de sorte que chacune des feuilles dudit arbre correspond a une unique transaction dudit jeu d'entrainement, une indication si celui-ci correspond a 20 une transaction normale ou en anomalie etant alors associee (S24) audit nceud considers. 7. Procede selon la revendication precedente, dans lequel ledit au moins un arbre est un arbre binaire et ladite pluralite de sous-ensembles est form& de deux sous-ensembles. 25 8. Procede selon l'une des revendications precedentes, dans lequel ledit au moins arbre est un « itree ». 9. Programme d'ordinateur comportant du code pour mettre en oeuvre un 30 procede selon l'une des revendications precedentes, lorsque execute sur un ordinateur.