Comparison of Outlier Detection Algorithms on String Data

Questa tesi confronta due algoritmi per il rilevamento di outlier nei dati testuali: una variante del Local Outlier Factor basata su una misura di Levenshtein pesata e un nuovo approccio basato su espressioni regolari gerarchiche, dimostrando che il primo è efficace quando gli outlier hanno una distanza di modifica distinta, mentre il secondo eccelle quando gli outlier differiscono strutturalmente dai dati attesi.

L'essenziale

Immagina di essere il responsabile di una grande biblioteca o di un archivio digitale. Hai migliaia di documenti, ma sai che alcuni sono sbagliati: forse sono stati scritti da un pazzo, sono stati copiati male, o sono semplicemente fuori posto. Il tuo compito è trovare questi "intrusi" (gli outlier, o dati anomali) prima che rovinino tutto.

Di solito, quando pensiamo a questi problemi, pensiamo a numeri: "Quanto è alto questo edificio?", "Quanto costa questo prodotto?". Ma cosa succede se i tuoi dati sono parole? Come fai a dire che "Via Roma 10" è normale, ma "Via Roma 1000000000" o "Via Roma è un sogno" sono strani?

Questa tesi di laurea di Philip Maus si pone esattamente questa domanda: come troviamo gli "stranieri" in un mondo di parole?

L'autore ha testato due metodi diversi, come se fossero due detective con approcci completamente opposti.

1. Il Detective "Vicino" (L'Algoritmo LOF)

Immagina una grande festa dove tutti i presenti sono amici e stanno parlando in gruppi affiatati.

• Il metodo: Questo detective guarda ogni persona e si chiede: "Quante persone sono vicine a te?". Se sei in mezzo a un gruppo rumoroso e affollato, sei "normale". Se invece sei l'unico che sta in piedi in un angolo silenzioso, lontano da tutti, probabilmente sei un intruso.
• La novità: Per le parole, il detective non guarda la distanza fisica, ma quanto sono diverse le parole tra loro (una misura chiamata distanza di Levenshtein). Se cambi una lettera, è come fare un piccolo passo. Se cambi una parola intera, è come attraversare l'oceano.
• Il trucco intelligente: L'autore ha aggiunto un "occhiale speciale" (pesi gerarchici). Immagina che le lettere siano come famiglie. Cambiare una 'a' con una 'e' (entrambe vocali) è come cambiare un cugino con un altro: è un piccolo passo. Cambiare una 'a' con un numero '5' è come cambiare un cugino con un alieno: è un passo enorme. Questo aiuta il detective a capire meglio quali parole sono davvero "strane" e quali sono solo leggermente diverse.

In sintesi: Questo metodo funziona benissimo se gli intrusi sono "lontani" dalle parole normali, anche se sono della stessa lunghezza. È come notare che qualcuno alla festa ha un cappello da clown mentre tutti gli altri hanno un cappello da sera.

2. La Modella "Regola d'Oro" (L'Algoritmo HiLRE)

Immagina di avere un gruppo di persone che indossano tutti lo stesso tipo di uniforme perfetta.

• Il metodo: Questo detective non guarda chi è vicino a chi. Invece, cerca di scrivere una regola (un "modello") che descriva perfettamente l'uniforme di tutti gli ospiti normali.
  • Esempio: "Tutti gli ospiti devono avere un numero di 5 cifre".
  • Una volta trovata questa regola perfetta, il detective guarda tutti gli ospiti. Chiunque non rispetti la regola (chi ha 3 cifre, chi ha lettere, chi ha 10 cifre) viene immediatamente etichettato come intruso.
• La sfida: Trovare la regola giusta è difficile. Se la regola è troppo rigida ("Devi avere esattamente 5 cifre e iniziare con 1"), potresti scacciare ospiti normali che iniziano con 2. Se è troppo lasca ("Puoi avere qualsiasi numero"), non scaccerai nessuno.
• Il trucco intelligente: L'autore ha creato un sistema che prova milioni di regole diverse e sceglie quella che si adatta meglio alla "massa" degli ospiti, ignorando i pochi che non ci stanno.

In sintesi: Questo metodo è un maestro nel trovare intrusi quando gli ospiti normali seguono una struttura molto precisa (come i codici postali), ma fallisce miseramente se gli ospiti normali sono tutti diversi tra loro (come i nomi delle città).

Cosa hanno scoperto? (Il Verdetto)

L'autore ha messo alla prova questi due detective con dati reali (indirizzi, date, numeri di telefono) e ha scoperto che non esiste un detective perfetto per tutto:

1. Quando funziona il "Modellista" (HiLRE): Se i dati normali sono molto ordinati e seguono una regola ferrea (es. tutti i codici postali tedeschi hanno 5 cifre), questo metodo è imbattibile. Trova gli intrusi senza sbagliare mai. Ma se i dati normali sono caotici (es. nomi di città come "Bonn" e "Frankfurt (Oder)"), il modello non riesce a capire la regola e smette di funzionare.
2. Quando funziona il "Vicino" (LOF): Se i dati normali sono un po' più variabili, ma gli intrusi sono chiaramente diversi (es. un numero di telefono mescolato a un codice postale), il detective che guarda le distanze funziona meglio. Non è perfetto, a volte scambia un ospite normale per un intruso, ma riesce a vedere le differenze di "lunghezza" o "struttura" che il modellista non vede.

La Conclusione in Pillole

Questa tesi ci insegna che per pulire i dati (come i log dei computer o gli indirizzi), non possiamo usare un unico martello per tutti i chiodi.

• Se i tuoi dati sono come mattoni perfetti, usa il Modellista (Regole).
• Se i tuoi dati sono come sassi in un fiume (tutti diversi ma simili), usa il Vicino (Distanza).

L'autore ci mostra che, combinando questi due approcci e adattandoli al tipo di "parola" che stiamo analizzando, possiamo costruire sistemi molto più intelligenti per pulire i nostri dati e trovare le anomalie che altrimenti rimarrebbero nascoste.

Sommario tecnico

Ecco un riassunto tecnico dettagliato della tesi di laurea "Comparison of Outlier Detection Algorithms on String Data" di Philip Maus, redatto in italiano.

Titolo: Confronto di Algoritmi di Rilevamento degli Outlier su Dati Stringa

1. Problema e Contesto

Il rilevamento degli outlier (anomalie) è un problema fondamentale nell'apprendimento automatico e nell'ingegneria dei dati. Tuttavia, la maggior parte della letteratura esistente si concentra sui dati numerici, trascurando i dati testuali (stringhe).
Il problema affrontato in questa tesi è la mancanza di algoritmi robusti per il rilevamento di anomalie in dataset composti da stringhe singole (parole), senza l'ausilio di contesto semantico aggiuntivo. Le applicazioni pratiche includono la pulizia dei dati, l'analisi di sequenze proteiche e, in particolare, il rilevamento di attività anomale nei file di log di sistema o la validazione di indirizzi e date.

L'obiettivo è confrontare due approcci concettualmente diversi per identificare stringhe anomale basandosi esclusivamente sulle loro proprietà sintattiche.

2. Metodologia

L'autore propone e confronta due algoritmi principali:

A. Approccio basato sui Vicini più Vicini (K-Nearest Neighbor - LOF)

• Algoritmo: Una variante dell'algoritmo Local Outlier Factor (LOF), che calcola la densità locale di un punto dati rispetto ai suoi $k$ vicini.
• Metrica di Distanza: Poiché LOF richiede una metrica di distanza, l'autore utilizza la distanza di Levenshtein (edit distance).
• Innovazione Chiave: Viene introdotta una Levenshtein pesata gerarchicamente. Invece di assegnare un costo unitario a tutte le operazioni di sostituzione, l'algoritmo utilizza una partizione gerarchica dei caratteri (es. lettere minuscole, maiuscole, numeri, punteggiatura). La distanza di sostituzione tra due caratteri è proporzionale alla distanza tra le loro classi nella gerarchia. Questo permette di distinguere meglio tra errori sintattici minori (es. 'a' vs 'b') e maggiori (es. 'a' vs '1').
• Parametri:
  • Selezione automatica di $k$ tramite un "guesser" chiamato KFCS (basato sulla coerenza del vicinato).
  • Soglia dinamica per il punteggio di anomalia, calcolata come multiplo della media dei punteggi, permettendo di rilevare gruppi di outlier con diversi gradi di anomalia.

B. Approccio basato su Espressioni Regolari (HiLRE)

• Algoritmo: Basato sull'apprendimento incrementale di Espressioni Regolari Sinistrorse Gerarchiche (Hierarchical Left Regular Expressions - HiLRE).
• Concetto: L'algoritmo assume che i dati "normali" seguano una struttura linguistica specifica descrivibile da un'espressione regolare. Qualsiasi stringa che non corrisponde a questa espressione è un outlier.
• Meccanismo:
  1. Utilizza la stessa partizione gerarchica dei caratteri usata nel LOF.
  2. Genera tutte le possibili espressioni regolari per i sottoinsiemi del dataset.
  3. Seleziona l'espressione regolare $H^*$ che massimizza la differenza minima tra il numero di corrispondenze e quelle dei suoi sottoinsiemi (trovando il miglior compromesso tra copertura e specificità).
  4. Variante con Parametro $p_{min}$: Viene introdotta una soglia minima ($p_{min}$) per la percentuale di dati che l'espressione regolare deve coprire, evitando di selezionare espressioni troppo specifiche che catturano solo un singolo valore ripetuto.

3. Contributi Chiave

1. Adattamento del LOF alle Stringhe: Implementazione e valutazione del LOF su dati stringa utilizzando la distanza di Levenshtein, con un focus specifico sull'ottimizzazione tramite pesi gerarchici.
2. Nuovo Algoritmo di Rilevamento: Proposta di un metodo di rilevamento outlier basato sull'inferenza di espressioni regolari (HiLRE) per dati stringa, adattato per gestire dataset con rumore.
3. Analisi Comparativa: Un'analisi empirica approfondita che dimostra come la scelta dell'algoritmo dipenda fortemente dalla natura strutturale del dataset (es. dati con struttura rigida vs. dati liberi).
4. Dataset e Benchmark: Utilizzo di dataset reali derivati dai rapporti di qualità degli ospedali tedeschi (indirizzi, codici postali, date, orari) e dataset sintetici per validare le ipotesi.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su dataset sintetici e reali (indirizzi, codici postali, nomi di contee, date, orari).

• Performance del LOF:

  • Funziona bene quando gli outlier hanno una struttura sintattica simile ai dati normali ma differiscono per lunghezza o edit distance.
  • La versione pesata gerarchicamente offre risultati più stabili quando le classi di caratteri sono distinte (es. distinguere numeri da lettere), riducendo i falsi positivi rispetto alla versione non pesata in certi scenari.
  • Tende a rilevare più outlier ma con un tasso di falsi positivi più elevato se la soglia non è calibrata correttamente.

• Performance di HiLRE:

  • Eccellente quando i dati normali hanno una struttura rigida e ben definita (es. codici postali a 5 cifre). In questi casi, raggiunge un tasso di veri positivi del 100% con zero falsi positivi.
  • Scarsa quando i dati normali sono molto variabili o privi di una struttura regolare chiara (es. nomi di contee o indirizzi liberi). In questi casi, l'algoritmo fatica a trovare un'espressione regolare rappresentativa, portando a zero rilevamenti o a un alto numero di falsi positivi.
  • Il parametro $p_{min}$ si è rivelato cruciale per bilanciare la specificità dell'espressione regolare.

• Confronto Diretto:

  • Su dati strutturati (es. codici postali vs nomi di contee): HiLRE vince nettamente.
  • Su dati con variazioni di lunghezza ma stessa classe di caratteri (es. codici postali vs numeri di telefono/case): LOF performa meglio, poiché HiLRE non riesce a distinguere le lunghezze diverse se la struttura dei caratteri è simile.

5. Significato e Conclusioni

La tesi dimostra che non esiste un algoritmo "universale" per il rilevamento di outlier su stringhe. La scelta dipende dalla natura dei dati:

• Se i dati hanno una struttura sintattica forte e ripetitiva, l'approccio basato su espressioni regolari (HiLRE) è superiore per precisione.
• Se i dati sono meno strutturati o le anomalie si manifestano principalmente come variazioni di distanza edit (lunghezza o caratteri simili ma diversi), l'approccio basato sulla densità (LOF) è più robusto.

Implicazioni Future:
Il lavoro apre la strada a ricerche su:

• Analisi della complessità temporale e spaziale degli algoritmi proposti.
• Estensione del rilevamento a stringhe contenenti più parole o frasi.
• Integrazione di contesto semantico (oltre alla sola sintassi) per migliorare l'accuratezza.
• Utilizzo di questi algoritmi come strumento di esplorazione dei dati per scoprire pattern nascosti (es. orari di invio dei report ospedalieri).

In sintesi, questa tesi fornisce un quadro metodologico solido per l'applicazione di tecniche di outlier detection su dati testuali, offrendo strumenti pratici per la pulizia e l'analisi di dataset reali.