HABRARD AMAURY (FR)
SEBBAN MARC (FR)
GUELTON LIYUN (FR)
CAELEN OLIVIER (BE)
UNIV JEAN MONNET SAINT ETIENNE (FR)
CENTRE NAT RECH SCIENT (FR)
WO2002097563A2 | 2002-12-05 |
R. SCHAPIRE: "The strength of week learnability", MACHINE LEARNING, vol. 5, 1990, pages 197 - 227
Y. FREUND; R. SCHAPIRE: "Experiments with a new boosting algorithm", INTERNATIONAL CONFÉRENCE ON MACHINE LEARNING, 1996, pages 148 - 156, XP008082830
J. H. FRIEDMAN: "Greedy function approximation: a gradient boosting machine", ANNALS OF STATISTICS, 2001, pages 1189 - 1232, XP055249500
REVENDICATIONS 1. Procédé pour la détection d'anomalies dans un ensemble de transactions de paiement, consistant à - établir (E3) un méta-modèle formé d'un ensemble de modèles, chacun optimisé sur un jeu d'entraînement pour déterminer un risque pour chaque transaction d'être en anomalie, ledit méta- modèle étant établi par la technique du « gradient boosting », de sorte à optimiser une fonction dérivable exprimant la précision moyenne dudit méta-modèle; - soumettre (E4) ledit ensemble audit méta-modèle, afin de déterminer des risques pour chaque transaction dudit ensemble, et, - déterminer un sous-ensemble de transactions correspondant à un risque supérieur à un seuil déterminé pour fournir un nombre prédéterminé de transaction dans ledit sous-ensemble. 2. Procédé selon la revendication précédente, dans lequel ledit sous- ensemble est présenté à un ou plusieurs experts humains et ledit seuil est déterminé en fonction du nombre de transactions pouvant être traitées par ledit un ou plusieurs experts humains. 3. Procédé selon l'une des revendications précédentes, dans lequel préalablement à l'établissement du méta-modèle, une étape de sous- échantillonnage (E2) est appliquée audit ensemble de transactions, afin d'améliorer l'équilibre entre transactions en anomalie et transactions légitimes. 4. Procédé selon la revendication précédente, dans lequel ladite étape de sous-échantillonnage consiste à optimiser une mesure F2. 5. Procédé selon la revendication précédente, dans lequel l'optimisation de ladite mesure F2 consiste à minimiser une fonction dérivable exprimant ladite mesure F2. 6. Procédé selon l'une des revendications précédentes, dans lequel ladite précision moyenne est appliquée sur le rang d'une transaction, les transactions étant ordonnée par niveau de risque. 7. Procédé selon la revendication précédente, dans lequel la précision moyenne AP s'exprime par l'équation : avec et dans laquelle F(¾) est le risque déterminé pour la transaction Xi, y; est égal à 1 si ladite transaction est en anomalie, 0 sinon, I() est la fonction indicatrice, N le nombre de transaction du jeu d'apprentissage, et ri est le rang de la transaction xi 8. Procédé selon la revendication précédente, dans lequel ladite fonction s'exprime par l'équation , avec : de lissage. 9. Programme d'ordinateur comportant des instructions qui, lorsqu'exécutés par un processeur d'un système informatique, entraînent la mise en œuvre d'un procédé de compilation selon l'une des revendications 1 à 8. 10. Dispositif pour la détection d'anomalies comportant des moyens permettant la mise en œuvre du procédé selon l'une des revendications 1 à 8. |
DOMAINE DE L'INVENTION
La présente invention est relative à un mécanisme de détection d'anomalies par apprentissage automatique dans un ensemble de transactions bancaires. Elle s'applique notamment à la détection de fraudes.
CONTEXTE DE L'INVENTION
La fraude sur les transactions de paiement, incluant principalement les transactions bancaires, est un phénomène important et grandissant, notamment du fait de la généralisation des transactions en lignes, effectuées via les réseaux de télécommunication. En sus des fraudes, d'autres types d'anomalies peuvent également survenir (erreurs...).
Aussi, différents mécanismes pour détecter les anomalies ont été déployées, en particulier par les établissements bancaires.
Ces mécanismes peuvent être mis en place avant ou après l'autorisation de transaction par un serveur de paiement. Dans le premier cas, on parle de détection de fraudes, ou d'anomalies, en temps-réel. Dans le deuxième cas, il s'agit de détection proche du temps-réel (« near real- time »).
Le premier cas présente l'avantage de pouvoir bloquer une transaction frauduleuse avant que celle-ci n'ait lieu, mais elle est assujettie à une contrainte forte sur le temps de traitement, puisque le mécanisme retarde la finalisation de la transaction de paiement et impacte donc négativement l'expérience de l'utilisateur. Le deuxième cas permet de disposer davantage de temps et donc de pouvoir mettre en place des traitements plus comptes et plus fins.
Des solutions pour permettre des détections d'anomalies dans ce deuxième cas ont été proposées. Pour une grande partie, ces solutions se basent sur différents mécanismes de classification.
Toutefois, la plupart des technologies classiques de classification ne peuvent s'appliquer directement du fait de spécificités de la détection d'anomalies dans un ensemble de transactions de paiement. Notamment, le très fort déséquilibre dans les données tend à induire des modèles prédisant seulement des transactions non frauduleuses.
Tout d'abord, les conséquences de la fraude sont extrêmement importantes et très sensibles. S'il est donc important de détecter le maximum de cas de fraude, il est également très dommageable d'annuler une transaction suspecte alors que celle-ci s'avère licite. La gravité et la complexité de la situation ne permettent pas aujourd'hui un traitement automatique et les solutions existantes consister à présenter un certain nombre de transactions litigieuses à un opérateur humain, et c'est cet opérateur humain qui, en dernier ressort, est responsable de la classification finale d'une transaction litigieuse en tant qu'anomalie ou licite.
En outre, du fait du caractère confidentiel et sensible des informations relatives aux paiements et aux données bancaires, très peu d'informations sont publiquement disponibles sur les outils mis en place pour la détection de fraude. Il est dès lors malaisé de comparer les solutions de l'état de la technique.
RESUME DE L 'INVENTION
Le but de la présente invention est de fournir une solution palliant au moins partiellement les inconvénients précités. Plus particulièrement, l'invention vise à fournir des outils permettant la détermination d'un ensemble de transactions présentant un certain risque d'être en anomalie (fraudes ou autres phénomènes), et pouvant être présenté à un opérateur humain.
A cette fin, la présente invention propose un procède pour la détection d'anomalies dans un ensemble de transactions de paiement, consistant à
- établir un méta-modèle formé d'un ensemble de modèles, chacun optimisé sur un jeu d'entraînement pour déterminer un risque pour chaque transaction d'être en anomalie, ledit méta-modèle étant établi par la technique du « gradient boosting », de sorte à optimiser une fonction dérivable exprimant la précision moyenne dudit méta-modèle ;
- soumettre ledit ensemble audit méta-modèle, afin de déterminer des risques pour chaque transaction dudit ensemble, et,
- déterminer un sous-ensemble de transactions correspondant à un risque supérieur à un seuil déterminé pour fournir un nombre prédéterminé de transactions dans ledit sous-ensemble.
Suivant des modes de réalisation préférés, l'invention comprend une ou plusieurs des caractéristiques suivantes qui peuvent être utilisées séparément ou en combinaison partielle entre elles ou en combinaison totale entre elles :
ledit sous-ensemble est présenté à un ou plusieurs experts humains et ledit seuil est déterminé en fonction du nombre de transactions pouvant être traitées par ledit un ou plusieurs experts humains ; préalablement à l'établissement du méta-modèle, une étape de sous-échantillonnage (E2) est appliquée audit ensemble de transactions, afin d'améliorer l'équilibre entre transactions en anomalie et transactions légitimes ;
ladite étape de sous-échantillonnage consiste à optimiser une mesure F2 ; l'optimisation de ladite mesure F2 consiste à minimiser une fonction dérivable exprimant ladite mesure F2 ;
ladite précision moyenne est appliquée sur le rang d'une transaction, les transactions étant ordonnée par niveau de risque, la précision moyenne AP s'exprime par l'équation :
est le risque déterminé comme une fraude pour la transaction x. ;
y i est égal à 1 si ladite transaction est en anomalie,0 sinon ;
I() est la fonction indicatrice, elle est égale à 1 si la condition est vraie, 0 sinon ;
- N le nombre de transaction du jeu d'apprentissage ;
et n est le rang de la transaction x; par rapport au classement de toutes les transactions, prédit par modèle F ladite fonction s'exprime par l'équation ( ), avec :
et dans laquelle a est un
paramètre de lissage.
Un autre objet de l'invention est un programme d'ordinateur comportant des instructions qui, lorsqu'exécutés par un processeur d'un système informatique, entraînent la mise en œuvre d'un procédé tel que précédemment décrit. Un autre objet de l'invention est un dispositif pour la détection d'anomalies comportant des moyens permettant la mise en œuvre du procédé précédemment décrit. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description qui suit d'un mode de réalisation préféré de l'invention, donnée à titre d'exemple et en référence aux dessins annexés.
BREVE DESCRIPTION DES DESSINS
La figure 1 représente schématiquement un exemple de déroulement du procédé selon un mode de réalisation de l'invention.
DESCRIPTION DETAILLEE DE L'INVENTION
Comme il a été dit en introduction, l'invention consiste à déterminer au sein d'un ensemble de transactions, le sous-ensemble de transactions présentant un risque élevé et devant être présenté à un (ou plusieurs) opérateur humain.
Le cardinal de ce sous-ensemble peut être prédéterminé puisqu'il peut correspondre au nombre de transactions qui peuvent être traitées sur une durée donnée (par exemple une journée) par les opérateurs humains.
Le problème résolu par l'invention consiste donc à trouver rapidement les k transactions présentant le risque le plus élevé d'être des anomalies, k étant le nombre de transactions pouvant être traitées par les opérateurs humains.
Dans un premier temps, une étape de prétraitement des transactions peut être mise en place. Cette étape est référencée El sur la figure 1.
Ce prétraitement consiste à préparer les données correspondant aux transactions afin de permettre leur bon traitement par les étapes ultérieures. Ces données comprennent à la fois des données contenues préalablement dans les transactions, et des données extérieures à celles-ci.
Plus particulièrement, ce prétraitement peut recouvrir au moins deux opérations :
Une première opération consiste à une mise en forme des données présentes dans les transactions soumises, afin de permettre leur traitement par l'algorithme de type « machine learning » auquel elles sont ensuite soumises. Par exemple, la date de la transaction peut être transformée en plusieurs données, ou caractéristiques (« features ») : jour, mois, année, heure, minute...
Une seconde opération consiste à associer de nouvelles caractéristiques aux transactions. Ces nouvelles caractéristiques peuvent être créées à partir de l'historique des parties à la transaction, notamment du porteur d'une carte de paiement utilisée pour la transaction : moyenne des montants dépensés, magasins précédemment visités, etc.
Ces caractéristiques sont prévues pour être pertinentes par rapport au problème posé qui est la détection d'anomalies et plus particulièrement de fraude. Ainsi, un montant très supérieur à la moyenne des transactions précédentes peut être un élément de risque, sans pour autant caractériser en soi une anomalie.
Les transactions, ainsi formées chacune d'un ensemble de caractéristiques, sont ensuite transmises à une étape E2 de sous- échantillonnage.
Cette étape E2 peut être omise dans le processus global conforme à l'invention, mais elle permet d'en améliorer les performances et le temps de traitement.
Elle permet notamment d'améliorer le jeu d'apprentissage sur lequel vont être entraînés les modèles statistiques de l'étape ultérieur. En effet, comme il a été évoqué précédemment, le nombre de transactions en anomalie est certes trop élevé, mais il représente toutefois une proportion très faible du volume total des transactions (par exemple, de l'ordre de 0.2%). Il en ressort que la population des transactions est très déséquilibrée, et ce déséquilibre engendre des problèmes importants pour la plupart des mécanismes d'apprentissage. Un des objectifs de l'invention est de prendre en compte cette spécificité et de proposer une solution permettant d'y remédier.
Il s'agit dans cette étape E2 d'écarter un certain nombre de transactions que l'on peut juger comme n'étant pas en anomalie (c'est-à-dire qui sont « légitimes »), afin d'une part de réduire le nombre de transactions entant dans le jeu d'apprentissage et d'autre part d'améliorer la répartition entre transactions en anomalie et transactions légitimes.
De telles techniques de sous-échantillonnages par exemple décrites dans l'article « Smote-rsb* : a hybrid preprocessing approach based on oversampling and undersampling for high imbalanced data-sets using smote and rough set theory » de E. Ramentol, Y. Caballero et F. Herrera, in Knowledge and Information Systems, 33(2), 2012, pages 245-265. Cet article présente également une technique complémentaire ou alternative consistant à sur-échantillonner l'ensemble des données, c'est-à-dire à créer des données « synthétiques » de la classe minoritaire.
Plus précisément encore, l'étape E2 est une étape de classification binaire consistant à affecter chaque transaction du jeu d'apprentissage soumis dans une classe « transaction en anomalie » ou dans une classe « transaction légitime ». Elle peut viser à optimiser une mesure F2 combinant le taux de rappel et la précision mesurés pour cette étape de sous- échantillonnage.
Le taux de rappel pour une classe donnée est défini par le rapport entre le nombre de transactions correctement classifiées et le nombre de transactions effectivement dans cette classe. La précision est définie par le rapport entre le nombre de transactions correctement classifîées et le nombre total de transactions.
Si l'on considère les critères habituels en classification de « vrais positifs » TP, « faux positifs » FP et « faux négatifs » FN, le taux rappel et la précision peuvent s'exprimer :
Les taux « vrais positifs » TP, « faux positifs » FP et « faux négatifs » FN peuvent s'exprimer en fonction des scores fournis par un modèle F établi pour cette étape de classification binaire avec deux classes « +1 » et « 0 ».
On considère la probabilité pour une transaction x ;
d'appartenir à la classe positive « 1 ». Dans un jeu d'apprentissage de N transactions, on peut associer à chaque transaction X i , la « vraie » classe yi. Ce jeu d'apprentissage peut s'écrire
On peut alors écrire :
Ces deux critères, précision et rappel, sont insuffisants, en général, pour mesurer la performance d'un mécanisme de classification. Il est en effet possible d'obtenir un taux de rappel très élevé (soit égal à 1 au maximum) au détriment d'une précision très faible et inversement.
Il existe plusieurs mesures classiques combinant rappel et précision, de sorte à capturer une performance considérée comme pertinente et représentative de la capacité du mécanisme à fournir des résultats acceptables.
Une telle mesure peut par exemple être la mesure F (ou F mesure), définie par :
Selon un mode de réalisation de l'invention, une mesure F2 est préférée pour l'accent qu'elle met sur le rappel, plutôt que la précision.
c'est-à-dire :
En insistant sur le rappel, l'étape de sous-échantillonnage permet d'écarter un grand nombre de transactions « légitimes », tout en gardant un maximum de transactions en anomalie pour la prochaine étape E3.
Selon un de mode de réalisation, l'optimisation de la mesure F2 consiste à minimiser une fonction dérivable exprimant ladite mesure F2.
Pour ce faire, on peut définir des approximations pour chaque somme TP, FP, FN, dans lesquels on remplace la fonction indicatrice par une approximation avec la fonction sigmoïde.
Les définitions données plus haut deviennent alors :
On peut utiliser ces définitions pour construire une approximation de la mesure F2,
Cette approximation peut être utilisée comme fonction objective dans un processus d'optimisation classique. Ce processus d'optimisation peut être une descente de gradient et par exemple utiliser la technique du « gradient boosting », cela même façon que l'étape E3. Ces méthodes d'optimisation seront plus détaillées dans les paragraphes suivants, en relation avec l'étape E3.
Cette étape E3 consiste à établir un méta-modèle formé d'un ensemble de modèles, chacun optimisé sur un jeu d'entraînement, par la technique du « gradient boosting », de sorte à optimiser une fonction dérivable exprimant la précision moyenne dudit méta-modèle.
D'une façon générale, il s'agit d'établir un méta-modèle permettant, en généralisation, de déterminer un sous-ensemble de transactions correspondant à un risque supérieur à un seuil déterminé pour fournir un nombre prédéterminé de transaction dans ledit sous-ensemble
En effet, comme il a été évoqué précédemment, les transactions considérées comme « à risque » sont soumises à des utilisateurs experts afin que ceux-ci décident si celles-ci sont des anomalies ou non. En conséquence, les ressources humaines disponibles fournissent ce nombre prédéterminé. La problématique consiste donc à fournir les k transactions les plus risquées, k étant le nombre de transactions que les utilisateurs- experts peuvent traités. Afin de résoudre ce problème technique, les inventeurs ont considéré que le critère habituel de l'exactitude (ou « accuracy » en langue anglaise) du modèle à utiliser pour la généralisation n'était pas optimum. Ils considèrent que le critère de la précision moyenne est mieux à même de rendre compte de la spécificité du problème technique. Dans le cadre de l'apprentissage ensemb liste mis en œuvre dans l'invention, optimiser la précision moyenne permet de favoriser l'apprentissage de modèles qui génèrent une bonne précision sur les transactions présentant les risques les plus élevés.
La méthode utilisée dans le cadre de l'invention est une méthode d'apprentissage ensembliste, c'est-à-dire se basant sur un modèle global, ou méta-modèle, formé d'un ensemble de modèles « individuels ». Chaque modèle individuel, ou « de base », est construit et optimisé à partir d'un jeu d'apprentissage.
Ces méthodes ensemb listes ont été présentées dans l'état de la technique dans de nombreuses publications dans le domaine de l'apprentissage automatique.
D'une façon générale, elles reposent sur les limites que l'on constate pour tout modèle lorsqu'on recherche un bon compromis entre le biais et la variance. Des études ont démontré qu'on considérant non pas un modèle mais un ensemble de modèles, on pouvait améliorer à la fois le biais et la variance du méta-modèle.
Dans la phase de prédiction, chaque modèle effectue une prédiction, et la prédiction finale, effectuée par le méta-modèle, est une combinaison des prédictions individuelles. Différentes combinaisons sont possibles : vote majoritaire, vote majoritaire pondéré, vote avec seuil, unanimité, etc.
Dans le cadre de l'invention, la combinaison peut être faite avec un vote majoritaire pondéré.
En apprentissage automatique, chaque modèle apprend de façon autonome, de façon itérative, et est évalué par rapport à un résultat à atteindre qui, dans le cadre de l'invention, est l'optimisation d'une fonction exprimant une précision moyenne des modèles.
Selon un mode de réalisation de l'invention, la technique ensembliste utilisée est une technique de « boosting », ou stimulation, et plus particulièrement de « gradient boosting » (stimulation du gradient), puisqu'il s'agit d'une optimisation de fonction.
La technique du boosting a été proposée par R. Schapire dans l'article « The strength of week learnability » in Machine Learning, 5, 1990, pages 197-227, et a fait l'objet depuis d'une abondante littérature.
L'idée de base est de considérer les transactions ayant été mal appris par les modèles et de se focaliser dessus afin d'améliorer leur apprentissage en priorité par rapport aux autres transactions, dans les itérations suivantes du processus d'apprentissage.
Une implémentation de ce principe est détaillée par exemple dans l'algorithme AdaBoost fourni par l'article « Experiments with a new boosting algorithm » de Y. Freund et R. Schapire, in International Conférence on Machine Learning, 1996, pages 148-156.
Dans sa généralité, le principe consiste à affecter des poids aux exemples des jeux d'apprentissage et, à chaque itération, à faire évoluer ses poids en augmentant les poids des exemples mal classés et en diminuant ceux des exemples bien classés. De même l'utilisation de la technique du « boosting » pour réaliser une optimisation par descente de gradient est bien connue et par exemple décrite dans l'article de J. H. Friedman, « Greedy function approximation: a gradient boosting machine » in Annals of statistics, 2001, pages 1189-1232.
L'invention ne réside pas dans un nouvel algorithme de boosting ou de gradient boosting, mais sur la façon de les utiliser. D'un point de vue pratique, un mode de réalisation de l'invention peut être un procédé, mis en œuvre par un logiciel, utilisant un tel algorithme comme un module fonctionnel autonome, qui peut être fourni par une librairie par exemple. Le problème que l'on recherche à résoudre au moyen de l'algorithme de gradient boosting est d'améliorer l'ensemble des k « meilleures » transactions en anomalie, où k est le nombre de transactions que les utilisateurs-experts peuvent traître. Dès lors, une fonction objective basée sur les rangs (ou classements) est particulièrement adapté.
On peut définir le rang n de la transaction x; par l'expression
Chaque transaction x; appartient à une classe « +1 », correspondant aux transactions en anomalie, ou bien à une classe « 0 » correspondant aux transactions « légitimes ». F est un modèle qui a pour sortie un risque, c'est- à-dire une probabilité pour une transaction d'appartenir à la classe « +1 ». I() représente la fonction indicatrice. Enfin, N est le nombre de transactions dans le jeu d'apprentissage S. Ce jeu d'apprentissage peut s'écrire dans lequel la transaction x i est associée à une classe y i .
L'expression ci-dessus définit donc le nombre de transactions qui ont un risque supérieur ou égal à la transaction x i .
La précision p i de ce rang n peut alors être définie par l'expression
La précision moyenne AP peut ensuite être obtenue par :
avec M
Autrement dit, on considère donc la précision moyenne appliquée au rang des transactions, celles-ci étant ordonnée par risques F(x i ).
Cette précision moyenne AP peut donc également s'écrire L'utilisation d'une technique de type « gradient boosting » nécessite que la fonction objectif soit différentiable afin de permettre une descente de gradient.
Une idée de l'invention consiste donc à approximer cette expression de la précision moyenne par une fonction dérivable exprimant cette précision moyenne. C'est cette fonction dérivable qui sera optimisé par l'algorithme de « gradient boosting ».
Pour ce faire, on détermine une approximation dérivable de la fonction indicatrice I() :
Ou encore :
avec et dans laquelle a est un
paramètre de lissage. Plus ce paramètre croit, et plus l'approximation s'approche de la précision moyenne réelle AP.
En utilisant cette approximation de la fonction indicatrice, on peut écrire la fonction à optimiser de la manière suivante : avec
On peut finalement écrire :
Il est alors possible d'introduire la fonction comme fonction à
minimiser par une descente de gradient selon la technique du « gradient boosting ». L'invention peut être mise en œuvre par l'utilisation d'un algorithme du « gradient boosting » connu en soi, mais modifié par l'introduction d'une fonction spécifique à minimiser qui est une fonction dérivable exprimant la précision moyenne du méta-modèle.
Ainsi, en fin de phase d'apprentissage, le méta-modèle est entraîné de sorte à minimiser la précision moyenne. Dans une étape E4, il peut alors être utilisé en prévision pour affecter un risque aux transactions.
Pour ce faire, on soumet l'ensemble des transactions à ce méta- modèle. Chaque transaction se voit affecter un risque, mais surtout on peut déterminer un sous-ensemble de transactions correspondant à un risque supérieur à un seuil déterminé pour fournir un nombre prédéterminé, k, de transactions dans ce sous-ensemble qui correspondent à celles que les experts peuvent traiter.
Ce seuil prédéterminé peut avoir été appris pendant la phase d'apprentissage. Son apprentissage peut être empirique et être constant. Il est également possible de le faire varier en fonction de certains paramètres comme la date, car certains événements calendaires sont susceptibles d'influencer les taux d'anomalies et de fraudes (vacances, week-end...). Sur ces événements où la fraude est plus présente, le seuil sera augmenté afin d'obtenir un nombre de transactions « à risque » constant (en faisant l'hypothèse que les ressources humaines demeurent constantes). Bien entendu, la présente invention n'est pas limitée aux exemples et au mode de réalisation décrits et représentés, mais elle est susceptible de nombreuses variantes accessibles à l'homme de l'art.