Isolation Forest comment ça marche ?

Isolation Forest (forêt d’isolation) est un algorithme de machine learning qui permet de détecter des valeurs atypiques dans un dataset. C’est par exemple une méthode qui donne de bons résultats pour la détection de fraude en identifiant des cas atypiques.

C’est une méthode multi-dimensionnelle assez simple à comprendre (moi en tout cas j’aime beaucoup). Pour en savoir plus sur le fonctionnement de l’algorithme d’isolation forest c’est par ici.

Isolation Forest qu’est ce que c’est ?

Isolation forest est une méthode non supervisée basée sur la construction d’arbres. L’idée derrière cet algorithme c’est qu’une donnée atypique sera plus facile à isoler qu’une donnée standard. Par exemple si j’ai une base client plutôt jeune avec une majorité de clients de moins de 20 ans, alors un client de 50 ans sera facilement isolé grâce à son âge.

Fonctionnement de l’algorithme des forêts d’isolation

Regardons ensemble comment se construit un arbre d’isolation. Pour cela nous prenons un exemple en 2 dimensions (X et Y) avec les données suivantes :

Etape 1 : Sélection d’une variable et d’un seuil

On sélectionne aléatoirement une variable, dans notre exemple ça se joue donc entre X et Y. Dans notre cas on sélectionne X. Puis on sélectionne uniformément une valeur u1 située entre le min de X et le max de X.

Voyons ce que ça donne pour nos données, premièrement on trace le seuil u1 et on commence à construire un arbre avec ce premier split de X en fonction de u1.

Etape 2 : étape itérative

Pour construire le premier arbre on continue d’appliquer l’étape 1. On s’arrête quand chaque point est isolé dans une feuille de l’arbre.

Donc on sélectionne aléatoirement une variable (disons Y cette fois-ci) et un seuil u2.

Comme aucun point n’est isolé on continue notre boucle itérative. On tire aléatoirement la variable Y et un nouveau seuil u3.

A ce stade on voit que les 2 points en noir à droite sont bien isolés par le découpage de u1, u2 et u3. C’est terminé pour ces 2 points. Notre objectif est maintenant d’itérer pour tous les points.

Pour le calcul du prochain seuil on calculera donc le min et le max de X ou Y en excluant ces 2 points.

Voici le résultat final (la représentation de l’arbre n’est pas 100% exhaustive, faute de place)

Etape 3 : passer d’un arbre à une forêt

Nous venons de faire le travail pour un arbre mais qui dit forêt d’isolation dit plusieurs arbres. On va donc relancer la même méthodes pour construire plusieurs arbres sur le même principe mais avec des sélections de variables et de seuils qui seront forcément différentes.

Comment appliquer un isolation Forest ?

Ok vous avez construit vos arbres d’isolation c’était assez marrant avec ces découpages et ces seuils mais pour l’instant ça ne nous dit pas vraiment où sont les valeurs atypiques. Vous allez voir c’est très simple : les valeurs atypiques sont celles que vous avez réussi à isoler le plus facilement. C’est une information que vous allez pouvoir lire sur chaque arbre. Ca s’appelle le score d’isolation et son calcul se base sur la profondeur de l’arbre pour chaque point. Pour une donnée il vous suffira ensuite de calculer la moyenne des scores d’isolation de cette donnée sur l’ensemble des arbres.

Regardons comment définir la profondeur sur un arbre. 1er exemple avec un des 1ers points qu’on a réussi à isoler. On suit le parcours de ce point dans l’arbre (X>u1, Y>u2, Y>u3) on a donc compté 3 splits.

Autre exemple avec un point un peu plus difficile à isoler. Il aura fallu 7 splits aléatoires sur cet arbre pour isoler ce point. On comprend donc déjà que la valeur précédente est plus atypique que celle-ci.

Pour finir l’algorithme transforme cette information sur la profondeur de l’arbre en isolation score (pour ceux qui souhaitent voir la formule exacte). L’avantage de ce score est qu’il normale les résultats :

• Un score proche de 1 indique une valeur atypique
• Un score proche de 0,5 indique une valeur standard

Alors que pensez vous de cet algorithme? Perso je suis fan, j’aime beaucoup l’idée que je trouve très maline. J’ai hâte de tester ce que ça donne sur un vrai dataset et de partager tout ça avec vous.