Résumé Technique : Forêt PCA Randomisée pour la Détection Non Supervisée d'Anomalies

Énoncé du Problème

La détection d'anomalies est une tâche fondamentale en fouille de données et en apprentissage automatique, cruciale pour des applications telles que la détection d'intrusions, le diagnostic de pannes et la détection de fraude. Malgré la prolifération d'algorithmes novateurs, des évaluations complètes indiquent que les méthodes classiques comme le K-Plus Proche Voisin (KNN) et le Facteur d'Anomalie Local (LOF) restent souvent à la pointe de l'état de l'art. Ces méthodes répondent efficacement à des défis tels que les frontières imprécises entre les données normales et anomales et la présence de bruit, mais elles souffrent d'une complexité computationnelle élevée due à la nécessité de recherches exactes des plus proches voisins. Bien que les méthodes basées sur des arbres comme la Forêt d'Isolement (iForest) offrent de l'efficacité, elles reposent sur une sélection aléatoire des caractéristiques, ce qui peut ne pas toujours capturer efficacement la structure sous-jacente des données de haute dimension. Il existe un besoin d'une méthode qui équilibre l'efficacité computationnelle et la robustesse, en exploitant la réduction de dimensionnalité sans sacrifier la capacité de détecter à la fois les anomalies globales et locales.

Méthodologie

Les auteurs proposent une nouvelle méthode de détection d'anomalies non supervisée basée sur les Forêts PCA Randomisées (RPCA). L'approche adapte la Forêt RPCA, conçue à l'origine pour la recherche approximative des K-Plus Proches Voisins (KNN), à la détection d'anomalies en dérivant un score d'anomalie spécifique à partir des propriétés intrinsèques de la forêt.

Composants Principaux

1. Construction de la Forêt RPCA :

   • La méthode construit un ensemble d'arbres. Contrairement à l'iForest, qui sélectionne aléatoirement des caractéristiques, les Forêts RPCA utilisent une PCA Randomisée (Halko et al., 2011) à chaque nœud.
   • À la racine et aux nœuds subséquents, les points de données sont projetés dans un sous-espace de dimension inférieure en utilisant un petit nombre de composantes principales ($p$). Cela préserve la valeur informationnelle de l'espace de caractéristiques original tout en réduisant la dimensionnalité.
   • Critère de Séparation : Au lieu de coupures aléatoires, l'algorithme échantillonne des points de séparation pour chaque composante principale à partir d'une distribution de Laplace centrée sur la moyenne. Les points de données sont assignés aux enfants gauche ou droit sur la base d'un vote majoritaire à travers les $p$ composantes.
   • Critère d'Arrêt : La croissance de l'arbre se poursuit jusqu'à ce que les nœuds feuilles contiennent un nombre de points inférieur ou égal à une taille de voisinage prédéfinie ($k$).

2. Formulation du Score d'Anomalie :
   La méthode proposée définit un score d'anomalie ($RPCAForestScore$) pour un point de requête $q$ en combinant deux critères distincts :

   • Anomalité basée sur la Profondeur ($P(q)$) : Basée sur l'observation que les anomalies sont souvent isolées plus tôt dans l'arbre (profondeur plus faible). Cela est calculé comme l'inverse normalisé de la profondeur du nœud feuille contenant $q$ à travers la forêt.
   • Anomalité basée sur la Distance ($\mu_{dist}(q)$) : Calculée comme la distance euclidienne moyenne entre le point de requête $q$ et tous les autres points au sein du même nœud feuille dans l'espace de caractéristiques original.
   • Score Final : Le score final est le produit de ces deux composantes :
     $$RPCAForestScore(q) = P(q) \times \mu_{dist}(q)$$
     Cette combinaison garantit que même si une anomalie est regroupée avec des inliers dans une feuille (en raison de la projection), sa grande distance par rapport au centre du cluster dans l'espace original résultera en un score d'anomalie élevé.

3. Classification :
   Un seuil d'anomalie est déterminé à l'aide d'un paramètre de contamination ($\alpha$), représentant le pourcentage attendu d'anomalies. Les points ayant des scores dépassant le quantile $(1-\alpha)$ de la distribution des scores sont étiquetés comme des anomalies.

Contributions Clés

• Intégration Novatrice : L'article introduit la première application des Forêts RPCA spécifiquement pour la détection d'anomalies non supervisée, comblant le fossé entre la recherche approximative des plus proches voisins et la détection d'anomalies.
• Mécanisme de Score Hybride : Il propose un score d'anomalie composite qui exploite à la fois la profondeur d'isolation structurelle (similaire à l'iForest) et la densité/distance locale dans l'espace de caractéristiques original (similaire au KNN/LOF), visant à surmonter les limites de l'utilisation de l'une ou l'autre métrique seule.
• Efficacité via PCA Randomisée : En employant une SVD randomisée, la méthode atteint une haute efficacité computationnelle, en particulier pour les données de haute dimension, car la complexité dépend du nombre de composantes principales plutôt que de la pleine dimensionnalité des données.
• Robustesse : La méthode est conçue pour être robuste face au réglage des hyperparamètres, ne nécessitant que la sélection du nombre d'arbres, de composantes principales ($p$) et de la taille des feuilles ($k$).

Résultats Expérimentaux

Les auteurs ont évalué la méthode sur 22 ensembles de données divers provenant d'un dépôt de référence standard, la comparant à des méthodes classiques et à la pointe de l'état de l'art incluant KNN, KNNW, LOF, SLOF, ODIN, DAO et iForest. La performance a été mesurée à l'aide de la Surface Sous la Courbe Caractéristique de Fonctionnement du Récepteur (AUC).

• Performance : La Forêt RPCA a démontré une performance supérieure ou deuxième meilleure sur de nombreux ensembles de données et est restée compétitive sur d'autres. Elle a montré une force particulière sur les ensembles de données de haute dimension où l'iForest (qui utilise une sélection aléatoire de caractéristiques) peinait.
• Robustesse : La méthode a maintenu une performance compétitive en utilisant seulement deux paramètres pour le nombre de composantes principales ($p=1$ et $p=5$), alors que les méthodes concurrentes ont été testées avec 100 configurations d'hyperparamètres différentes. Cela suggère que la méthode proposée est moins sensible au réglage des hyperparamètres.
• Étude d'Ablation : Des expériences séparant les composantes basées sur la profondeur et basées sur la distance ont révélé que le score combiné surpassait significativement la composante basée sur la profondeur et était généralement compétitif ou supérieur à la composante basée sur la distance seule.
• Efficacité : Bien que l'iForest reste la méthode la plus rapide, la Forêt RPCA a démontré une scalabilité significativement meilleure que les méthodes basées sur KNN à mesure que la taille de l'ensemble de données augmentait, maintenant des temps d'exécution efficaces adaptés aux mégadonnées.
• Limitations Observées : La méthode a montré une performance inférieure sur des ensembles de données spécifiques (par exemple, ALOI, InternetAds, Annthyroid, Wilt). Les auteurs attribuent cela à :
  • Une haute dimensionnalité où peu de composantes principales ($p=1, 5$) étaient insuffisantes pour isoler les anomalies (InternetAds).
  • Des anomalies très similaires aux inliers, nécessitant plus d'informations que les $p$ sélectionnés ne pouvaient fournir (Annthyroid, Wilt).
  • La nature des anomalies locales par rapport aux anomalies globales dans des ensembles de données avec des extractions de caractéristiques spécifiques (ALOI), où les méthodes de structure locale (LOF) ont surpassé l'approche de projection globale.

Signification et Revendications

L'article revendique que la Forêt RPCA offre une alternative robuste et computationnellement efficace pour la détection d'anomalies non supervisée. Sa signification réside dans sa capacité à :

1. Équilibrer Efficacité et Précision : Elle fournit une approche « boîte blanche » pour la recherche de voisinage approximatif qui utilise la structure interne de l'arbre (via des projections PCA) plutôt que de traiter la recherche comme une boîte noire.
2. Bien Généraliser : La méthode performe de manière compétitive sur un large éventail d'ensembles de données sans nécessiter d'optimisation exhaustive des hyperparamètres, abordant le problème où de nombreuses méthodes novatrices excellent uniquement sur des instances de problèmes spécifiques.
3. Détecter à la fois les Anomalies Globales et Locales : Théoriquement, la méthode est conçue pour détecter les anomalies globales (via une isolation précoce dans l'arbre) et les anomalies locales (via des métriques de distance dans les nœuds plus profonds), bien que les auteurs reconnaissent des limitations avec les anomalies en grappe.

Les auteurs concluent que, bien que la méthode ne soit pas une solution universelle pour tous les types d'anomalies (en particulier les anomalies en grappe), elle représente un choix solide pour la détection d'anomalies à usage général, offrant un compromis favorable entre la vitesse computationnelle des méthodes basées sur des arbres et la précision des méthodes basées sur la distance.