Comparison of Outlier Detection Algorithms on String Data

Cette thèse compare deux algorithmes de détection d'anomalies pour les données textuelles : une variante du Local Outlier Factor adaptée via la distance de Levenshtein hiérarchique et un nouvel algorithme basé sur l'apprentissage d'expressions régulières hiérarchiques, démontrant que le premier excelle lorsque les anomalies se distinguent par leur distance d'édition, tandis que le second est plus efficace pour identifier les écarts structurels.

L'essentiel

Voici une explication simple et imagée de ce travail de recherche, comme si on en discutait autour d'un café.

🕵️‍♂️ Le Grand Détective de Données : Trouver l'Intrus dans la Foule

Imaginez que vous avez une immense boîte remplie de milliers de petits mots ou de phrases. La plupart de ces mots sont normaux, ils suivent un schéma, comme des pièces de monnaie identiques. Mais, au fond de la boîte, il y a quelques intrus : des mots bizarres, mal écrits, ou qui ne devraient pas être là.

Le but de cette thèse est de créer des détecteurs automatiques capables de repérer ces intrus dans des listes de mots (des "chaînes de caractères"), car la plupart des détecteurs existants ne savent regarder que des chiffres.

L'auteur, Philip Maus, a testé deux méthodes différentes pour trouver ces intrus. Voici comment elles fonctionnent, avec des analogies du quotidien.

---

🛠️ Méthode 1 : Le Détective "Voisinage" (LOF)

L'idée : "Si tu es seul au milieu d'une foule, tu es suspect."

Imaginez une grande salle de bal.

• La plupart des gens dansent par groupes serrés (les données normales).
• Un intrus est quelqu'un qui danse tout seul, loin des groupes, ou qui a un style de danse très différent.

Comment ça marche ?

1. Le comptage des voisins : Le détective regarde chaque mot et demande : "Qui sont tes 5 ou 10 voisins les plus proches ?"
2. La mesure de distance : Pour savoir qui est "proche", on utilise une règle spéciale appelée distance de Levenshtein. C'est comme compter le nombre de lettres qu'il faut changer, ajouter ou supprimer pour transformer un mot en un autre.
   • Exemple : Transformer "2024-01-01" en "2024-01-02" ne demande qu'un petit changement. C'est un "voisin".
   • Exemple : Transformer "2024-01-01" en "Bonjour le monde" demande de tout changer. C'est un "lointain".
3. L'astuce du détective (La hiérarchie) : L'auteur a amélioré la règle. Il ne compte pas juste les lettres, il regarde leur famille.
   • Remplacer un chiffre par un autre chiffre (ex: 1 par 2) est une petite erreur (comme changer de couleur de chemise).
   • Remplacer un chiffre par une lettre (ex: 1 par 'A') est une grosse erreur (comme porter un costume de clown à un bal).
   • Cette astuce permet de mieux repérer les mots qui ont la bonne "forme" mais de mauvais détails.

Le verdict : Cette méthode est excellente quand les mots normaux sont très groupés et que les intrus sont clairement isolés dans l'espace.

---

📜 Méthode 2 : Le Détective "Règle du Jeu" (HiLRE)

L'idée : "Si tu ne respectes pas le code vestimentaire, tu es un intrus."

Imaginez que vous organisez une soirée où l'invitation dit : "Portez un t-shirt avec un chiffre de 1 à 5".

• Les mots normaux sont tous des t-shirts avec un chiffre (ex: "12345").
• Les intrus sont des t-shirts avec des lettres, ou des chiffres hors limite.

Comment ça marche ?

1. Apprendre la règle : Au lieu de comparer les mots entre eux, l'algorithme essaie de deviner la règle secrète (un "régulier expression") qui décrit tous les mots normaux.
   • Il observe les mots et se dit : "Ah, ils commencent tous par '20', suivis d'un chiffre entre 0 et 9, puis un tiret..."
2. Le filtre : Une fois la règle trouvée, il teste chaque mot.
   • Si le mot correspond à la règle ➡️ C'est normal.
   • Si le mot ne correspond pas ➡️ C'est un intrus !
3. L'ajustement (Le paramètre $p_{min}$) : Parfois, la règle est trop stricte (elle rejette trop de monde) ou trop souple (elle laisse passer les intrus). L'auteur a ajouté un bouton de réglage : "La règle doit accepter au moins 90% des gens". Cela force l'algorithme à trouver une règle qui couvre la majorité des gens normaux sans être trop laxiste.

Le verdict : Cette méthode est géniale si les mots normaux ont une structure très claire et rigide (comme des dates ou des codes postaux). Mais si les mots normaux sont tous différents (comme des noms de villes), l'algorithme perd ses repères et ne trouve pas de règle.

---

🥊 Le Grand Duel : Qui gagne ?

L'auteur a testé ces deux détectifs sur de vraies données (codes postaux, noms de villes, numéros de téléphone, dates). Voici ce qu'il a découvert :

1. Quand les données sont bien rangées (ex: Codes Postaux) :

   • Le Détective "Règle du Jeu" est un champion. Il trouve la règle parfaite (5 chiffres) et repère instantanément les intrus (des noms de villes) sans faire d'erreur.
   • Le Détective "Voisinage" fonctionne aussi, mais il peut se tromper si un intrus a la même longueur que les mots normaux (ex: un nom de ville de 5 lettres).

2. Quand les données sont chaotiques (ex: Noms de villes) :

   • Le Détective "Règle du Jeu" est perdu. Il ne peut pas inventer une règle unique pour des noms comme "Paris", "Bordeaux" et "Strasbourg". Il finit par ne rien rejeter ou tout rejeter.
   • Le Détective "Voisinage" est plus robuste. Il voit que certains mots sont "étranges" par rapport à la moyenne, même sans règle précise.

💡 En résumé

• Si vous cherchez des erreurs dans des données très structurées (comme des dates, des codes-barres), utilisez la Méthode 2 (Règle). C'est précis et rapide.
• Si vous cherchez des anomalies dans des données plus libres ou variées, utilisez la Méthode 1 (Voisinage). C'est plus flexible et tolérant.

L'auteur conclut que l'outil parfait n'existe pas encore : il faut choisir son détective en fonction de la nature de la "foule" que l'on observe. C'est un pas important pour nettoyer automatiquement les bases de données et repérer les erreurs ou les fraudes dans le monde numérique.

Résumé technique

Voici un résumé technique détaillé de la thèse de bachelor de Philip Maus, intitulée « Comparison of Outlier Detection Algorithms on String Data » (Comparaison d'algorithmes de détection d'anomalies sur des données textuelles), rédigé en français.

1. Problématique et Contexte

La détection d'anomalies (ou d'outliers) est un problème fondamental en apprentissage automatique et en science des données, visant à identifier des points de données qui s'écartent significativement du reste. Bien que ce domaine soit largement étudié, la majorité de la littérature se concentre sur les données numériques.

Cependant, la détection d'anomalies sur les données textuelles (chaînes de caractères) est cruciale pour des applications telles que le nettoyage de données, l'analyse de logs système ou la détection d'activités anormales. Le défi principal réside dans le fait que les algorithmes classiques (basés sur la distance euclidienne, par exemple) ne sont pas directement applicables aux chaînes de caractères. Cette thèse vise à combler ce vide en comparant deux approches adaptées aux données textuelles pour identifier des anomalies syntaxiques (sans nécessiter de contexte sémantique externe).

2. Méthodologie

L'auteur propose et compare deux algorithmes distincts, tous deux conçus pour traiter des chaînes de caractères uniques (mots) en utilisant une partition hiérarchique des classes de caractères (lettres, chiffres, ponctuation, etc.).

A. Approche basée sur les K-Plus Proches Voisins (K-NN) : LOF Adapté

La première approche adapte l'algorithme classique Local Outlier Factor (LOF) pour les chaînes de caractères.

• Principe : L'algorithme calcule un facteur d'anomalie basé sur la densité locale. Un point est considéré comme une anomalie s'il se trouve dans une zone de faible densité par rapport à ses $k$ plus proches voisins.
• Mesure de distance : Au lieu d'une distance euclidienne, l'auteur utilise la distance de Levenshtein (distance d'édition).
• Amélioration clé (Pondération Hiérarchique) : La distance de Levenshtein standard attribue un coût égal à toutes les substitutions. L'auteur propose une distance de Levenshtein pondérée hiérarchiquement. En utilisant une partition hiérarchique des caractères (ex: remplacer un chiffre par un autre chiffre coûte moins cher que de remplacer un chiffre par une lettre), l'algorithme devient plus sensible aux structures syntaxiques spécifiques des données.
• Paramétrage :
  • Le paramètre $k$ (nombre de voisins) est déterminé automatiquement par un algorithme appelé KFCS (basé sur la cohérence du voisinage).
  • Le seuil de décision est dynamique : il est calculé comme un multiple de la moyenne des scores d'anomalie, permettant une détection itérative de plusieurs groupes d'anomalies.

B. Approche basée sur les Expressions Régulières : HiLRE

La seconde approche est une méthode nouvelle basée sur l'apprentissage d'expressions régulières.

• Principe : L'hypothèse est qu'il existe une expression régulière (spécifiquement un HiLRE - Hierarchical Left Regular Expression) qui décrit la langue des données "normales". Toute chaîne ne correspondant pas à cette expression est une anomalie.
• Algorithme d'apprentissage : L'auteur utilise un algorithme d'apprentissage incrémental (inspiré de [Dos+16]) qui infère un HiLRE minimal à partir d'un sous-ensemble de données.
• Stratégie de sélection : L'algorithme génère des HiLREs pour tous les sous-ensembles possibles de données. Il sélectionne le HiLRE optimal ($H^*$) qui maximise la différence de couverture par rapport à ses sous-ensembles (c'est-à-dire celui qui capture le plus de données "normales" tout en excluant le plus d'anomalies potentielles).
• Paramétrage : Une variante introduit un paramètre $p_{min}$ (ratio minimum de données à couvrir) pour éviter que l'algorithme ne sélectionne une expression trop restrictive (qui ne couvrirait qu'une seule valeur répétée) et pour ajuster la sensibilité.

3. Contributions Clés

1. Adaptation du LOF aux chaînes de caractères : Intégration réussie de la distance de Levenshtein dans l'algorithme LOF, avec une proposition novatrice de pondération hiérarchique pour mieux refléter la similarité syntaxique (ex: les erreurs de frappe sur des chiffres sont moins graves que le remplacement par des lettres).
2. Nouvelle méthode de détection par HiLRE : Développement d'un algorithme complet pour détecter des anomalies en inférant une expression régulière hiérarchique qui modélise les données attendues, capable de rejeter les chaînes ne correspondant pas à la structure apprise.
3. Analyse comparative rigoureuse : Évaluation expérimentale des deux approches sur des données synthétiques et réelles (données hospitalières allemandes : codes postaux, noms de villes, numéros de téléphone, dates, heures).
4. Identification des cas d'usage optimaux : La thèse démontre que le choix de l'algorithme dépend fortement de la nature structurelle des données.

4. Résultats Expérimentaux

Les expériences ont été menées sur des jeux de données contenant des codes postaux, des noms de comtés, des numéros de téléphone, des dates et des heures.

• Données structurées (ex: Codes postaux) :

  • L'approche HiLRE excelle lorsque les données normales ont une structure rigide et distincte (ex: exactement 5 chiffres). Elle atteint un taux de vrais positifs de 100% avec zéro faux positifs, car elle peut apprendre une expression régulière parfaite.
  • L'approche LOF fonctionne bien mais est moins précise, car elle peut confondre des chaînes de même longueur mais de contenu différent (ex: un nom de ville de 5 lettres vs un code postal).

• Données peu structurées ou variées (ex: Noms de villes) :

  • L'approche HiLRE échoue souvent. Les noms de villes sont trop diversifiés pour être capturés par une seule expression régulière restrictive sans inclure des anomalies ou exclure des données valides.
  • L'approche LOF (surtout avec la pondération hiérarchique) est plus robuste ici, car elle détecte les anomalies basées sur la densité et la distance d'édition relative, sans avoir besoin d'une structure syntaxique parfaite.

• Données de longueur variable (ex: Numéros de téléphone vs Codes postaux) :

  • LOF performe bien car il détecte facilement les différences de longueur et de densité.
  • HiLRE lutte à trouver un compromis entre sous-ajustement (trop général) et sur-ajustement (trop spécifique).

• Impact de la pondération hiérarchique : Sur les données synthétiques (dates), la version pondérée de Levenshtein dans LOF permet de mieux distinguer les formats valides des formats invalides que la distance standard.

5. Signification et Conclusion

Cette thèse démontre qu'il n'existe pas d'algorithme universel pour la détection d'anomalies sur les chaînes de caractères. Le choix dépend de la structure intrinsèque des données :

• Si les données attendues suivent un motif syntaxique strict (comme des formats de dates, des codes postaux, des emails), l'approche basée sur les expressions régulières (HiLRE) est supérieure, offrant une précision élevée et peu de faux positifs.
• Si les données sont hétérogènes ou si les anomalies sont définies par des écarts de densité plutôt que par une structure absente, l'approche LOF (surtout avec une métrique de distance adaptée) est plus appropriée.

Signification pratique : Ces résultats sont cruciaux pour l'ingénierie des données et la sécurité informatique. Ils permettent de choisir l'outil adéquat pour le nettoyage de bases de données hétérogènes ou la surveillance de logs système, en évitant l'application aveugle d'algorithmes conçus pour des données numériques.

Travaux futurs : L'auteur suggère d'analyser la complexité temporelle et spatiale de l'algorithme HiLRE, d'étendre la détection aux phrases (plusieurs mots) et d'intégrer le contexte sémantique pour améliorer la détection d'anomalies qui ne sont pas uniquement syntaxiques.