Nel corso dello sviluppo e della sperimentazione del sistema di analisi dei pattern sequenziali è stato possibile individuare alcune criticità:
• Problematiche di ordine computazionale per il mining;
• Elevato numero dei pattern estratti e conseguente difficoltà nell’individuare quelli più significativi ed importanti.
Come abbiamo visto nel capitolo precedente, per lo scenario S2 non ci è stato possibile effettuare le analisi per tutte le minacce a causa della limitatezza delle risorse necessarie all’elaborazione dei dati rispetto a quanto evidentemente era necessario. La lunghezza delle sequenze di attacco, l’elevato numero di elementi di cui gli attacchi sono composti e la densità degli stessi hanno determinato un esaurimento della memoria RAM con conseguente crash del software di mining. Anche avendo a disposizione un quantitativo di memoria RAM adeguato, non ci è dato comunque sapere se l’algoritmo termini in un tempo accettabile. Per risolvere questo problema sarebbe più appropriato eseguire il mining su di una piattaforma distribuita utilizzando algoritmo ad-hoc.
La seconda problematica, ovvero l’elevato numero di pattern ed il ranking degli stessi, dipende principalmente da due fattori: la scelta del tipo di pattern sequenziali da estrarre, ad esempio utilizzando i massimali che, come abbiamo visto, sono in numero inferiore rispetto ai frequenti ed i chiusi; la predisposizione delle metriche che catturino la caratteristiche di interesse e ci consentano di individuare i pattern più importanti e significativi. Per questo progetto abbiamo predisposto una scelta dei pattern tra i modelli basilari (frequenti, chiusi e massimali) per poi scegliere di condurre la sperimentazioni con i massimali per i motivi già illustrati. Niente vieta di predisporre l’utilizzo di altri modelli di pattern sequenziali come, ad esempio, gli high-utility sequential patterns, oppure i multidimensional sequential patterns, che tra l’altro sono inclusi nella libreria utilizzata per il nostro caso di studio (SPMF). Più il modello applicato è raffinato e più precisa sarà la conoscenza derivata dalle informazioni raccolte. La definizione delle metriche di interesse, utilizzate per il ranking dei pattern sequenziali, dipende dalla quantità delle informazioni
CAPITOLO 8. CONCLUSIONI che definiscono il livello di dettaglio. In questa sede abbiamo considerato, oltre alle metriche oggettive (supporto, lunghezza del pattern e score), informazioni di dominio e minimali, che descrivessero la quantità di lavoro residua da svolgere, da parte di un attaccante, per comprendere la distanza tra un pattern e le sequenze che lo soddisfano. Ulteriori e differenti metriche diverse possono essere definite per comprendere meglio aspetti specifici.
COPERTURA E TIPI DI
PATTERN SEQUENZIALI
Definizione A.1. Definiamo cover di un pattern sequenziale SP l’insieme delle sequenze nel database D che contengono SP . Formalmente:
coverD(SP ) = {S ∈ D | SP v S}
Lemma A.1. Se SP1 v SP2 allora cover(SP1) ⊇ cover (SP2).
Definizione A.2. Dato un insieme di pattern sequenziali C, definiamo: coverD(C) = ∪SP ∈CcoverD(SP )
Diremo che C copre il database di sequenze D se ogni sequenza in D è coperta da qualche pattern in C. Il problema di trovare un insieme C tale che coverD(C) = D
è un’istanza di un problema noto come set cover problem [19]. Tipicamente, comunque, si mira a trovare un insieme C con cardinalità massima k. Nel nostro caso di studio, per esempio, gli esperti del dominio devono esaminare la copertura e hanno quindi bisogno che questa sia sufficientemente piccola per prestarsi ad un’ispezione da parte di un umano. Una copertura di cardinalità k potrebbe non esistere. Si cerca quindi un insieme C di cardinalità massima k che massimizzi |coverD(C)|– il numero di sequenze coperte in D. Questa è un’istanza del maximum
coverage problem [19]. Come ulteriore generalizzazione assumiamo che i pattern sequenziali in C appartengano ad un insieme predeterminato P, ad esempio, pattern sequenziali frequenti, chiusi o massimali.
Definizione A.3. Sia P un insieme di pattern sequenziali, e k ≥ 1. Definiamo k-cover di P:
APPENDICE A. COPERTURA E TIPI DI PATTERN SEQUENZIALI Più di un sottoinsieme C ⊆ P può massimizzare la funzione obiettivo. Scriveremo quindi C ∈ Cov(k, P) per indicare uno qualsiasi di tali sottoinsiemi. Il calcolo dell’insieme di copertura k-cover è un problema NP-hard. Un algoritmo greedy per questo problema sceglie i pattern sequenziali da P rispettando una semplice regola: ad ogni iterazione seleziona il pattern sequenziale la cui copertura presenta il maggior numero di sequenze non ancora coperte dai pattern sequenziali scelti precedentemente. Un algoritmo del genere raggiunge un’approssimazione pari a ≈ 0.632 rispetto la copertura ottimale [19].
Dimostreremo adesso formalmente che i pattern sequenziali frequenti FP e chiusi CP non sono scelte adeguate per il calcolo di k-cover di P, mentre i pattern massimali MP lo sono. Introduciamo prima la definizione degli elementi minimali di un insieme di pattern sequenziali rispetto alla relazione v.
Definizione A.4.
M in(P) = {SP ∈ P | @SP0 ∈ P. SP0 @ SP }
Il prossimo risultato mostra che nella ricerca di k-cover di P possiamo restringere la scelta ai soli elementi minimali di P.
Teorema A.2. Sia C ∈ Cov(k, P). Esiste C0 ∈ Cov(k, M in(P))tale che cover(C) = cover (C0) e |C| ≥ |C0|.
Dimostrazione. Definiamo l’insieme C0 come segue. Per ogni SP ∈ C scegliamo un
qualsiasi SP0 ∈ M in(P)tale che SP0 v SP. Per un dato SP , esiste almeno un SP0
– potrebbe essere SP stesso, se esso è elemento minimale in P. Uno qualsiasi di tali SP0’s può essere scelto. Per costruzione |C0| ≤ |C| ≤ k (infatti uno stesso elemento minimale può essere scelto per due SP ’s in C). Per la proprietà di antimonotonicità, cover (SP ) ⊆ cover (SP0). Ne consegue:
cover (C) = ∪SP ∈Ccover(SP ) ⊆ ∪SP0∈C0cover(SP0) = cover (C0).
Dato che C è un k-cover e P ⊇ Min(P), allora |cover(C)| è massimale ed implica che l’inclusione di cui sopra è una uguaglianza. Per concludere, si osservi che un k-cover di Cov(k, Min(P)) non può coprire più sequenze di un k-cover di P, per definizione di massimizzazione. Dato che C0 ⊆ M in(P) e |C0| ≤ k e |cover(C0)| è
massimale, concludiamo C0 ∈ Cov(k, M in(P)).
La conseguenza di questo risultato è notevole. Non ha senso cercare di coprire un database di sequenze usando i pattern frequenti o chiusi
Esempio A.1. L’elemento minimale dei pattern sequenziali frequenti FP è la sequenza vuota, Min(FP) = {hi}. Banalmente, {hi} copre qualsiasi database di sequenze. Per il Teorema A.2, {hi} ∈ Cov(k, FP). Sfortunatamente un pattern sequenziale vuoto non è di nessun aiuto pratico in nessuna applicazione.
Senza considerare il pattern sequenziale vuoto il risultato non è molto inte- ressante perchè non abbiamo proprio bisogno dei pattern sequenziali per cercare la copertura. Ad esempio, un approccio standard per la selezione degli elementi, consiste nell’applicazione di un algoritmo greedy per la selezione degli item (non pattern sequenziali) che hanno la più alta frequenza residua nelle sequenze non ancora coperte.
Esempio A.2. Si considerino i pattern sequenziali frequenti non vuoti: FP0 = F P \ {hi}. Risulta che Min(FP0) = {F P ∈ F P | ∃i ∈ I. F P = h{i}i}. Quindi, per cercare la copertura, si possono considerare solo i pattern sequenziali composti da un solo item frequente. In altre parole non vi è proprio bisogno di estrarre i pattern sequenziali dal database.
Per i pattern sequenziali chiusi CP vale lo stesso ragionamento e si raggiungono le medesime conclusioni. Per cercare una via di uscita si potrebbe considerare Cov(k, P) per P come un insieme di pattern sequenziali frequenti o chiusi con un supporto nell’intervallo [minsup, maxsup]. Tuttavia, quale valore massimo maxsup scegliere non è chiaro. Proponiamo quindi di utilizzare i pattern sequenziali massimali MP dato che gli elementi minimali di tale insieme sono i pattern massimali stessi.
Appendice B
ARCHITETTURA DEL SISTEMA
SOFTWARE
B.1
Componenti software
Il sistema di analisi è costituito da diverse componenti software, alcune scritte in linguaggio Java e altre in Python.
Per quanto riguarda i componenti Java: CSV2FIMI (credits to Prof. Salvatore Ruggieri) è un tool per la codifica degli item in identificativi univoci; SPMF (credits to Fournier-Viger, P., Lin, C.W., Gomariz, A., Gueniche, T., Soltani, A., Deng, Z., Lam, H. T.) è una libreria di algoritmi per il data mining.
I componenti scritti in linguaggio Python si occupano invece della fase di pre-processing (calcolo delle distribuzioni degli item, estrazione dei dati da DB e preparazione dell’input per gli algoritmi di mining) e di quella di post-processing (calcolo delle metriche dei pattern e calcolo degli insiemi di copertura)