Attention: je ne suis expert ni en détection d’anomalies ni en lutte contre la fraude. Cet article est le résultat de mes lectures sur le sujet. S’il vous semble que certaines affirmations sont erronées ou discutables, n’hésitez pas à m’en faire part dans les commentaires.
Salut les internautes ! dans le dernier billet, je vous expliquais comment on faisait de la détection de fraude dans un cas où les données étaient étiquetées. J’avais commencé par définir ce qu’est une fraude et j’avais expliqué les problématiques inhérentes à leur détection dans ce contexte. La principale problématique concernait le déséquilibre statistique entre transactions non frauduleuses et transactions frauduleuses, qui pouvait notamment se résoudre en utilisant une pondération différente entre transactions frauduleuses et non frauduleuses dans la fonction de coût d’une part et par une modification de la base de données d’autre part. Aujourd’hui, nous allons nous intéresser aux méthodes spécifiques à la détection d’anomalies dans le contexte de l’apprentissage non supervisé et semi-supervisé.
Détection d’anomalies
Quand les données ne sont pas (toutes) étiquetées, il est impossible d’utiliser les méthodes vues précédemment. Dans le cas où seulement certaines données sont étiquetées, il est possible de les utiliser sur ces données, mais on perd alors l’avantage d’avoir des données bien plus nombreuses. Il peut paraître un peu contre intuitif de déterminer si une transaction est ou non frauduleuse alors qu’on n’a pas d’exemple à portée de main mais cela ne signifie pas qu’il n’y a rien à faire. Comme on l’a dit précédemment, les fraudes ont ceci de particulier qu’elles sont très peu nombreuses et on peut supposer qu’elles sont différentes des transactions normales (sinon, inutile d’essayer d’apprendre quoi que ce soit à partir des données). On peut donc lever une alarme lorsqu’une donnée paraît « étrange » ou « anormale ». C’est à cette problématique que s’intéresse la détection d’anomalies. On distingue généralement deux cas : la détection d’anomalie non supervisée repose sur un cas où aucune donnée n’est étiquetée. Dans ce cas, on va essayer de sortir les données qui ont l’air les moins « normales » et lever une alerte lorsqu’on en trouve une. Cependant, pour une application particulière, il n’y a pas de connaissance sur la proportion de données qui devraient lever une alerte, ce qui rend les choses un peu compliquées. On distingue donc un autre cas : bien que la masse des données ne soit pas étiquetées (on s’imagine assez mal étiqueter chaque transaction d’une base bancaire), il peut être possible d’étiqueter certaines données et de s’appuyer sur ces données pour faire les réglages nécessaires permettant notamment d’éviter que des données normales ne soient vues comme anormales. Ce cas est appelé apprentissage semi-supervisé.
Venons-en à ce qu’on appelle une anomalie. Notons que le domaine de la détection d’anomalies ne s’applique pas uniquement à la détection de fraudes. On peut chercher à intercepter d’autres types d’actions malveillantes (DDOS dans un réseau par exemple) ou même déterminer des erreurs. Ces applications ont toutes un élément en commun : elles cherchent à déterminer des éléments qui s’éloignent de « la norme ». On distingue trois types d’anomalies :
- Les anomalies isolées peuvent être vus comme des individus isolés de tous les autres. Dans le cas de la fraude, il peut s’agir d’une transaction avec un ordre de magnitude de 10 par rapport à la seconde transaction la plus importante.
- Les anomalies contextuelles. Ces anomalies correspondent à des points aberrants non par la valeur de chacun de leurs attributs pris séparément, mais par la conjonction de leurs attributs. Dans notre cas, il pourrait s’agir d’une suite de transactions parfaitement normales indépendamment mais faites dans le même mois à un fournisseur auquel on fait normalement une unique transaction mensuelle.
- Les groupes d’anomalies sont des individus qui forment un groupe qui s’éloigne du ou des autres groupes, et suffisamment petit pour être considéré comme n’étant pas la norme. Il peut par exemple s’agir d’un ensemble de transactions faites vers un certain pays avec une certaine devise et de manière récurrente.
Il existe de nombreuses méthodes pour détecter les anomalies. Chacune est plus efficace pour un certain type d’anomalies. Il est en général recommandé d’utiliser une conjonction de ces méthodes afin de détecter tous les types d’anomalies cités.
Méthodes non supervisées
Cette fois-ci, je vais prendre la peine de décrire les méthodes utilisées plus en détail pour la détection d’anomalies car elles sont généralement spécifiques à cette problématique.
La première méthode de détection d’anomalies non supervisée repose sur les k plus proches voisins. Bien que cette méthode soit généralement utilisée pour de l’apprentissage supervisé, elle est ici modifiée pour détecter les anomalies : pour chaque individu, on va ainsi calculer selon une fonction de distance à définir selon les données quels sont ses k plus proches voisins (avec k à définir). On calcule ensuite la distance moyenne de l’individu avec ses voisins. On fait la supposition qu’une anomalie sera généralement plus loin de ses voisins que les individus normaux. La distance aux moyens peut ainsi être utilisée comme un score d’anomalie. Cette méthode est efficace pour déterminer les anomalies isolées, voire, si la fonction de distance est bien définie, pour les anomalies contextuelles. Elle est en revanche généralement inefficace pour déterminer les groupes d’anomalies, les individus du groupe étant rapprochés les uns des autres.
Une autre famille de méthode repose sur l’apprentissage non supervisé plus classique (clustering). Le but du clustering est de grouper les individus par paquets d’individus rapprochés. Les trois méthodes les plus utilisées à cette fin sont les k-means, les cartes auto-organisatrices et le clustering hiérarchique. Les k-means et les cartes auto-organisatrices calculent ces ensembles en s’appuyant sur des « centres » ou centroïdes, qui déterminent selon leur distance avec les individus à quelle classe ils appartiennent. Il est alors possible de déterminer si un individu est anormal en déterminant sa distance avec son centroïde. Le clustering hiérarchique repose sur un principe différent : il ‘agit d’agréger les groupes d’individus identiques jusqu’à atteindre un certain seuil où on considérera que les groupes sont trop dissemblables pour constituer un cluster. Dans ce cas, on peut déterminer que les individus ou les petits groupes d’individus agrégés avec une distance importante peuvent être considérés comme anormaux, puisque loin des individus ou groupes les plus proches.
Les anomalies sont généralement considérées comme des individus statistiquement différents des autres. Il est possible de déterminer si un individu est significativement différent des autres en faisant une hypothèse sur la manière dont ces individus sont distribués. L’hypothèse la plus commune est de dire que les individus sont répartis selon une gaussienne multivariée. Dans ce cas, après avoir déterminé la matrice de covariance des individus, il est alors possible de déterminer quels sont les individus les plus éloignés de cette distribution. Il est possible de déterminer les outliers de cette distribution. Le problème de cette méthode est qu’elle fait une supposition forte sur la distribution des individus, et qui peut être très erronée. Il est donc possible d’utiliser d’autres hypothèses plus générales sur cette distribution.
Ces méthodes sont généralement efficaces sur les données numériques, pour lesquelles il est facile de déterminer une fonction de distance. La méthode gassienne est quant à elle utilisable sur un espace numérique à plusieurs dimensions. Or, comme nous l’avons vu dans le dernier billet, les données ne correspondent généralement pas à cette présupposition. En effet, elles comprennent généralement des attributs catégoriels tels que la devise ou encore la source, le numéro de compte et le destinataire. D’autre part, les transactions sont généralement datées. On peut donc les considérer comme des séries temporelles. Il est bien sûr possible de considérer le temps comme un attribut comme un autre, mais on manquera alors certains aspects de cet axe. Par exemple, si une transaction identique est faite toujours à la même date chaque mois, le fait que deux transactions soient faites le même mois ne sera pas détecté comme anormal si on considère le temps comme un simple axe, la transaction additionnelle étant vue comme simplement plus proche de la précédente et la suivante.
Il existe donc des méthodes spécifiques à ces données. En ce qui concerne les séries temporelles, on va généralement rechercher deux types d’anomalies. Le premier type d’anomalies va consister à comparer les séries temporelles entre elles. Dans notre cas, il peut s’agir par exemple de déterminer des comptes qui se comportent de manière très différente des autres, et qui pourraient donc être liés à des activités frauduleuses. On en revient donc à la recherche d’une anomalie isolée, mais où chaque individu est une série temporelle. Il est donc nécessaire de trouver un moyen de comparer des séries temporelles. On distingue pour cela trois grandes familles de méthodes. La comparaison point-à-point consiste à comparer les points synchronisés de chaque série. On va donc par exemple comparer l’encours de deux comptes aux mêmes moments, en acceptant par exemple un certain écart en termes de montants. Cette méthode peut être utile dans certains cas bien spécifiques, où deux séries doivent parfaitement correspondre (par exemple les opérations faites sur un compte doivent être répercutées sur un autre compte, et on veut vérifier qu’il n’y a pas d’écart significatif). Mais dans la plupart des cas, deux séries décalées l’une de l’autre ou deux séries identiques à une insertion prêt devraient être vues comme identiques. Certaines mesures prennent ces opérations en compte, et comparent les séries temporelles en termes d’écart brut, d’insertion de points ou de suppression de points, et permettent ainsi de gérer l’aspect temporel des séries. Enfin, il est possible d’utiliser des méthodes dites spectrales, qui transforment la série en un ensemble de valeurs prenant notamment en compte sa périodicité. Ces valeurs peuvent ensuite être plus directement comparées.
La détection de série anormales n’est pas la seule application de la détection d’anomalies aux séries temporelles. Il est également courant de chercher à repérer les anomalies à l’intérieur d’une série. Dans ce cas, on va chercher une séquence qui paraisse anormale en comparaison avec le reste de la série. Pour cela, il est possible de faire des comparaisons par sous-séquences. L’idée est de « couper » un morceau de la séquence et de le comparer à tous les autres morceaux possibles de même taille, selon les méthodes mentionnées ci-dessus. On peut alors utiliser une méthode des k plus proches voisins et ainsi déterminer comme précédemment les séquences suspectes. Cette méthode est cependant coûteuse car elle demande de comparer chaque sous-série possible à toutes les sous-séries de même taille, ce qui peut être très long pour une série longue. Il est aussi possible de découper la série en « mots » (très petites séquences) de taille prédéfinie (qu’il faut déterminer à l’avance) et de déterminer la fréquence de chacun de ces mots pour chaque séquence de taille suffisante. On détermine un score d’anomalie comme la moyenne de l’inverse des fréquences des mots qui le composent. Ainsi, plus le score est proche de 1, plus la série pourra être vue comme anormale. Plus il s’approche de 0, plus elle sera considérée comme normale. Le principal problème de cette méthode est de déterminer la taille des mots et des séquences, mais le fait de calculer le dictionnaire et les fréquences des mots a priori fait drastiquement diminuer le temps de calcul.
Enfin, certaines bases de données se composent de données catégorielles. Il est difficile dans ce cadre de déterminer une distance entre individus, d’autant plus que le fait de déterminer cette distance ne permet pas de vérifier si deux attributs sont corrélés. On peut par exemple s’attendre à ce qu’un virement fait vers un compte au Royaume-Uni soit dans fait en livres Sterling, et un virement vers ce pays en dollars serait dans ce cas anormal. Pour détecter ces corrélations, on utilise généralement deux types de méthodes. La première consiste à calculer la fréquence d’apparition de l’individu (ici, par exemple, les transactions vers le Royaume Uni en dollars) et de le diviser par la racine du produit des fréquences de ses attributs (ici, le nombre de transactions en dollars multiplié par le nombre de transactions vers le Royaume-Uni). Il est nécessaire de faire cette division pour éviter de sanctionner des transactions normales mais peu nombreuses. On peut par exemple imaginer que les transactions vers le Royaume Uni en dollars constituent une transaction sur dix-milles, et qu’il y a autant de transactions vers la Chine en yuan, parce que l’entreprise fait très peu de commerce en Chine. Pour autant, le nombre de transactions en Chine et le nombre de transactions en yuan seront probablement identiques, et la fréquence relative des transactions en Chine en yuan divisé par la racine du produit d nombre de transactions en Chine d’une part et en yuaan d’autre part sera proche de 1, là où la racine du produit des transactions au Royaume Uni d’une part et des transactions en dollars d’une part et au Royaume Uni d’autre part sera bien plus important que le nombre de transactions à la conjonction, ce qui donnera un score très inférieur à 1.
Une autre méthode existe pour rechercher le même résultat. Elle est issue des méthodes de compression de données. Dans ce domaine, on cherche généralement à associer à chaque élément un code, avec un dictionnaire permettant de retrouver à quel élément correspond chaque code. Le but est de trouver le code le plus court pour les éléments revenant le plus souvent. Dans le cas de conjonction de données, on va utiliser un algorithme nommé KRIMP. Je ne vais pas le décrire en détail. Dans le cadre de ce billet, il suffit de savoir qu’il va attribuer un code court à des éléments fréquents et un code long à des éléments rares. Il est donc possible d’utiliser la longueur du code d’un individu pour déterminer s’il est anormal ou non.
Chacune de ces méthodes peut être utilisé sur des données de type différent. Lorsque les données sont de plusieurs types, on va généralement utiliser plusieurs méthodes, soit en parallèle, soit les unes après les autres. Cela me semble un peu problématique : je n’ai vu aucune méthode permettant de prendre en compte les corrélations entre données catégorielles et numériques par exemple. Les seules approches que j’ai vues consistaient à appliquer deux méthodes pour chaque type de données. Il est cependant possible (probable) que de telles méthodes existent et qu’elles m’aient échappé. Si vous en avez connaissance, n’hésitez pas à m’en faire part dans les commentaires !
Méthodes semi-supervisées
Les méthodes que nous avons décrites jusqu’à présent ont pour objectif de produire un score d’anomalie. Elles permettent d’étiqueter les données, et donc de les structurer. Ce score peut être la distance moyenne aux k plus proches voisins, la probabilité d’apparition d’un point en supposant que les données sont gaussiennes ou encore la fréquence marginale d’apparition d’un individu. Puisque ce sont des méthodes d’apprentissage non supervisées, elles ne peuvent cependant décider de si un individu doit être étiqueté comme fraude ou non. Les méthodes semi-supervisées vont précisément servir à cela : elles prennent en compte un grand volume de données non supervisées pour construire un modèle d’anomalie comme défini ci-dessus et utilisent un petit volume de données supervisées pour décider à partir de quand un individu doit être considéré comme fraude. Elles vont pour cela reposer sur des méthodes supervisées simples, telles que l’inférence bayésienne. Par ailleurs, il est possible, lorsqu’on n’a pas de données initialement, d’utiliser des méthodes non supervisées, de fixer une règle initiale et de demander à l’utilisateur d’indiquer si une transaction est frauduleuse lorsqu’on détecte une anomalie. Ces méthodes, appelées active learning, constituent une classe à part entière que je ne ferai que mentionner ici.
Pour conclure ce billet, je tiens à rappeler que je ne suis pas un expert et que je sais que j’ai laissé un certain nombre de méthodes de côté. Si vous pensez qu’il faudrait en ajouter, n’hésitez pas à laisser un commentaire ! Et si vous voulez plus de détail, renseignez-vous, réfléchissez mais surtout, n’oubliez as de rêver.
Bibliographie
Semi supervised learning for fraud detection sur le blog LAMFO
Semi-supervised anomaly detection survey, sur le site de Kaggle
Introduction to anomaly detection, sur le blog datascience
Mohan, Chilukuri K., and Kishan G. Mehrotra. « Anomaly detection in banking operations. » IDRBT JOURNAL OF (2017): 16.
Joseph T. Wells, International Fraud Handbook, ACFE series, Wiley and sons, 2018
