Isolation Forest comment ça marche ?

Détecter des valeurs atypiques ou extrêmes grâce aux forêts d’isolations (Isolation Forest une méthode de machine learning non supervisée)

La forêt d’isolation est un algorithme de machine learning qui permet de détecter des valeurs extrêmes (outliers) ou 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 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, un client de 50 ans sera facilement isolé grâce à son âge.

Fonctionnement de l’algorithme d’isolation Forest

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, 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 jusqu’à ce que chaque point soit isolé dans une feuille de l’arbre.

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

Aucun point n’est isolé on continue donc 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. Le travail est terminé pour ces 2 points et l’objectif est d’itérer jusqu’a ce que chaque point soit isolé. Pour le calcul du prochain seuil on calculera donc le min et le max de X ou Y en excluant ces 2 points qui sont déjà isolés.

Voici le résultat obtenu quand chaque point est isolé (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 c’est un algorithme de forêt d’isolation donc qui dit forêt 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 utiliser 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 : ça 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.

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s