Una recente pubblicazione [15] presenta una sintesi dello stato dell’arte dei modelli di sequential pattern mining facendo una ricognizione delle tecniche e degli algoritmi attualmente in uso. L’attività di mining di pattern sequenziali è di tipo enumerativo. Si tratta di enumerare tutti i pattern (sotto-sequenze) che abbiano un supporto uguale o superiore ad un valore minimo specificato dall’utente. Indipendentemente dall’algoritmo utilizzato, per un dato insieme di sequenze e per un dato valore di supporto minimo, l’insieme dei pattern ottenuti sarà sempre il medesimo. L’estrazione dei pattern è un problema np-hard. L’approccio più banale consiste nel calcolare il supporto per ogni possibile sotto-sequenza e produrre in output solo le sotto-sequenze che presentano valori uguali o superiori al valore minimo specificato. Chiaramente questo approccio è inefficiente dato che il numero di sotto-sequenze è esponenziale. Una sequenza composta da n elementi dà luogo ad un insieme di sotto-sequenze di cardinalità pari a 2n− 1. Una strada del genere
CAPITOLO 4. IL PROCESSO DI KDD risulta impraticabile per i problemi reali e pertanto si è reso necessario adottare tecniche e sviluppare algoritmi che evitino di esplorare l’intero spazio di ricerca.
Tra gli algoritmi più popolari sviluppati per l’estrazione di pattern sequenziali frequenti troviamo GSP [1, 27], SPADE [32], PrefixSpan [25], SPAM [4] , CM-SPAM [14], CM-SPADE [14] e LAPIN [31].
Tutti questi algoritmi prendono in input un insieme di sequenze ed un valore di supporto minimo specificato dall’utente e restituiscono in output l’insieme dei pattern frequenti. Ciò che differenzia un algoritmo da un altro sono la strategia e la struttura dati con la quale viene esplorato lo spazio di ricerca. La naturale conseguenza è che vi sono algoritmi più efficienti di altri.
Gli algoritmi esplorano lo spazio di ricerca attraverso due operazioni fonda- mentali chiamate s-extension e i-extension. Queste due operazioni sono necessarie per generare sotto-sequenze di lunghezza K + 1 partendo da sotto-sequenze di lunghezza K (contenenti un numero di elementi pari a K). In generale tutti gli algoritmi possono essere inquadrati in due categorie in funzione della strategia di ricerca:
• Breadth first search: con la prima scansione del database vengono individuate tutte le sotto-sequenze di lunghezza 1 (contenenti 1 solo elemento). Attraverso le operazioni i-extension e s-extension viene generato l’insieme delle sotto- sequenze di lunghezza 2. Questo insieme viene utilizzato per generare le sotto-sequenze di lunghezza 3 e cosi vià fino a quando non è più possibile generare nuovi insiemi. Questo approccio è chiamato level-wise in quanto i pattern sono analizzati in ordine crescente rispetto alla lunghezza. Lo spazio di ricerca può essere molto grande dato che vi sono una moltitudine di modi diversi di combinare gli elementi per generare potenziali pattern. Nel caso peggiore, in un database di m item dove la sequenza più lunga contiene x item, viene esplorato uno spazio di ricerca contenente tutte le sotto-sequenze di lunghezza uguale o minore ad x. La cardinalità dello spazio di ricerca può essere molto maggiore di 2m.
• Depth first search: gli algoritmi che adottano questa strategia dopo aver prodotto le sotto-sequenze di lunghezza 1 esplorano lo spazio di ricerca compiendo ricorsivamente le operazioni di estensione su di esse per produrre sotto-sequenze più lunghe. Quando una sotto-sequenza non può essere estesa ulteriormente l’algoritmo compie un passo di backtrack e prova a generare altre sotto-sequenze.
L’algoritmo GSP adotta la prima strategia mentre tutti gli altri citati adottano la seconda. Indipendentemente dalla strategia utilizzata esplorare l’intero spazio di ricerca può essere computazionalmente proibitivo. Un algoritmo che voglia essere
efficiente deve integrare una tecnica di pruning che riduca lo spazio di ricerca. La proprietà di anti-monotonicità, altrimenti detta proprietà Apriori consente di evitare di prendere in considerazione tutte le possibili sotto-sequenze. Date due sequenze sa ed sb, se sav sb, allora il supporto di sb deve essere uguale o minore
al supporto di sa. Per fare un esempio chiarificatore, date le due sequenze h{a}i e
h{a, b}i , la frequenza di occorrenza di h{a, b}i non può essere superiore a quella di h{a}i dato che la prima è più specifica. Da ciò consegue che il supporto è una misura antimonotonica. Questa proprietà ci consente di ridurre lo spazio di ricerca dato che se una sotto-sequenza non è frequente allora non lo sono nemmeno le sue estensioni.
Sinteticamente gli algoritmi di sequential pattern mining si differenziano in base alle seguenti caratteristiche:
1. Utilizzo di una strategia di ricerca di tipo breadth-first o depth first.
2. La struttura dati utilizzata per la rappresentazione interna od esterna delle sequenze.
3. Modo in cui generano o determinani prossimi pattern da esplorare nello spazio di ricerca.
4. Modo in cui viene calcolato il supporto dei pattern per determinare se soddisfano il supporto minimo.
L’algoritmo GSP usa un rappresentazione standard del database di sequenze, detta proiezione orizzontale, di cui la la tabella 4.1 costituisce una esemplificazione. Negli anni recenti sono stati sviluppati algoritmi più efficienti di GSP che soffre di importanti limitazioni quali:
• Molteplici scansioni del DB: viene ripetutamente scandito l’intero DB per calcolare il supporto dei pattern candidati. Operazione molto costosa su grandi insiemi di sequenze.
• Produzioni di candidati inesistenti: vengono generate pattern candidati che non esistono nelle sequenze del DB. Il motivo risiede nel fatto che GSP genera i pattern candidati combinando tra di loro quelli più piccoli già verificati senza leggere il DB. Questo genera un costo non necessario in termini di tempo richiesto per la verifica del pattern.
• Mantenimento in memoria dei candidati: tipico degli algoritmi che adottano la strategia di ricerca breadth-first è tenere in memoria tutti i pattern di lunghezza K al fine di generare i pattern di lunghezza K + 1. Molto costoso in termini di memoria occupata-
CAPITOLO 4. IL PROCESSO DI KDD Altri algoritmi come SPADE, oltre ad utilizzare una strategia di ricerca di tipo depth-first, utilizzano una rappresentazione verticale del database di sequenze visibile in tabella 4.3. a sid itemsets 10 1 20 1,4 30 1 40 b sid itemsets 10 1 20 3,4 30 2 40 1 c sid itemsets 10 2 20 2 30 40 d sid itemsets 10 20 1 30 40 e sid itemsets 10 5 20 4 30 4 40 f sid itemsets 10 3 20 4 30 3 40 2 g sid itemsets 10 3,4 20 30 3 40 2
Tabella 4.3: Proiezione verticale del DB.
In una rappresentazione verticale del database sono indicati gli itemsets in cui ogni item i compare all’interno del database di sequenze. Questo tipo di informazione è chiamata idList. Per fare un esempio, la idList dell’item c indica che tale elemento compare nel secondo itemset della prima sequenza, nel terzo itemset della seconda, nel primo e nel terzo itemset della terza e nel quarto itemset della quarta. Le idList di ogni singolo item sono create con un’unica scansione del database. La rappresentazione verticale del database presenta due interessanti proprietà per il mining di sequential pattern:
1. Le idList di ogni pattern permettono di calcolarne direttamente il supporto dato che questo è esattamente il numero di sequenze distinte nella propria idList.
2. La idList di un qualsiasi pattern pa, ottenuto con le operazioni di estensione di
un pattern pb con l’item i, viene creata senza ulteriori scansioni del database
in quanto è sufficiente effettuare una operazione di giunzione tra la idList del pattern pb e la idList dell’item i.
Grazie a queste due proprietà gli algoritmi SPADE, SPAM, CM-SPADE e CM-SPA sono in grado di esplorare l’intero spazio di ricerca dei pattern scandendo
una volta sola il database di sequenze per creare le idList dei singoli item. Le idList di ogni pattern, che di volta in volta viene incontrato durante l’esplorazione, viene calcolata attraverso l’operazione di giunzione delle relative idList che permettono di calcolare in maniera immediata il supporto del pattern. Tutti i pattern frequenti sono quindi enumerati effettuando una sola scansione del database e senza tenere in memoria un grande numero di pattern. Questa metodologia si è rivelata essere di gran lunga più efficiente dei primi algoritmi ,quali appunto GSP, che utilizzano una strategia di ricerca breadth-first ed una rappresentazione orizzontale del database di sequenze.
Una ulteriore ottimizzazione consiste nella rappresentazione delle idList tramite una ricodifica delle stesse in vettori di bit detti BitMap. Le idList possono essere molto lunghe quando i pattern compaiono in molte sequenze, specialmente nei casi in cui ci troviamo in presenza di database molto densi costituiti da sequenze molto lunghe. Conseguentemente l’operazione di giunzione delle idList risulta molto costosa dato che per essere effettuata necessità di confrontare tutti gli elementi delle idList interessate dall’operazione. In una rappresentazione BitMap avremo per ogni elemento o pattern una vettore di bit di lunghezza uguale alla somma del numero di itemset di ogni sequenza. Ogni bit è impostato al valore 1 se l’elemento o il pattern sono presenti nell’itemset rappresentato dal bit oppure sarà impostato a 0 nel caso contrario. L’operazione di giunzione delle idList può quindi essere effettuata con l’operazione di AND logico tra i vettori BitMap delle idList. L’algoritmo SPAM utilizza questa tecnica di rappresentazione di cui forniamo un’esempio in tabella 4.4 . item BitMap a 100001001100000 b 100000011010010 c 010000100000000 d 000001000000000 e 000010001000100 f 001000001001001 g 001100000001001
Tabella 4.4: Rappresentazione BitMap delle idList.
La versione dell’algoritmo SPADE che utilizza questa tenica prende il nome di BitSPADE [3]. In tempi recenti i due algoritmi SPAM e BitSPADE sono stati ulteriormente ottimizzati, dando vita a CM-SPAM e CM-SPADE, riducendo il numero di operazioni di giunzione grazie al concetto di co-occurence pruning. Con la scansione iniziale del database viene creata una struttura dati chiamata co- occurence map in cui sono memorizzate tutte le sequenze frequenti di lunghezza
CAPITOLO 4. IL PROCESSO DI KDD pari a 2. Per ogni pattern considerato durante l’esplorazione dello spazio di ricerca vengono esaminati gli ultimi 2 elementi dello stesso e se questi non sono sequenze frequenti di lunghezza 2 allora il pattern può essere automaticamente eliminato senza bisogno di costruire la relativa idList con l’operazione di giunzione. Gli algoritmi CM-SPAM e CM-SPADE sono risultati essere molto più efficienti di GSP, SPAM, BitSPADE e PrefixSpan ed in particolar modo CM-SPADE è quello più veloce di tutti.
PrefixSpan oltre ad utilizzare una strategia depth-first adotta una tecnica di ricerca chiamara pattern-growth. Questa tecnica permette di evitare la generazione di candidati pattern inesistenti nel database di sequenze scandendolo ricorsivamente per cercare pattern più lunghi. Questo consente di prendere in considerazione solo i pattern effettivamente esistenti. Per ridurre il costo delle letture del database gli algoritmi che adottano questa tecnica utilizzano un database proiettato che consente di ridurre la grandezza dello stesso mano a mano che vengono esaminati pattern più lunghi durante la ricerca in profondità.
La prima operazione di PrefixSpan consiste nella scansione del database di sequenze per calcolare il supporto di ogni singolo item al fine di identificare quelli frequenti (aventi un supporto maggiore o uguale a quello minimo specificato). Questi sequential pattern di lunghezza 1 sono utilizzati come base di partenza per la ricerca in profondità di pattern più lunghi. Durante la ricerca, dato un pattern Pa di lunghezza K, viene creato il database proiettato del pattern stesso. Il
database proiettato viene letto per cercare item da aggiungere al pattern, tramite le operazioni di giunzione, e calcolarne il supporto. Questo processo è ripetuto ricorsivamente per trovare tutti i pattern sequenziali. Di seguito forniamo le definizioni formali dei concetti di base di questa tecnica.
Definizione 4.11 (Prefisso). Date due sequenze α = ha1, a2, a3, . . . , ani e β =
hb1, b2, b3, . . . , bmi con m ≤ n, la sequenza β è detta prefisso di α se e solo se:
1. bi = ai, ∀i ≤ m − 1.
2. bm ⊆ am.
3. Tutti gli item in (am− bm) sono ordinativamente successivi a bm.
Ad esempio date α = h(a), (a, b, c), (a, c), (d), (c, f)i e β = h(a), (a, b, c), (a)i, la sequenza β è prefisso della sequenza α.
Definizione 4.12 (Proiezione). Date due sequenze α e β con β v α, una sotto- sequenza α0 di α è detta proiezione di α rispetto al prefisso β se e solo se:
1. α0 ha il prefisso β.
2. @α00.α0
Ad esempio date α = h(a), (a, b, c), (a, c), (d), (c, f)i e β = h(b, c), (a)i, la sequenza α0 = h(b, c), (a, c), (d), (c, f )i è la proiezione della sequenza α.
Definizione 4.13 (Suffisso). Data la sequenza α0 = ha1, a2, . . . , ani proiezione
della sequenza α rispetto al prefisso β = hb1, b2, . . . , bmi con m ≤ n, la sequenza
γ = ha00m, am+1, . . . , ani, in cui a00m = (am−bm), è detta suffisso di α ed è indicata con
γ = α/β. Definiamo α = β·γ. Ad esempio date α = h(a), (a, b, c), (a, c), (d), (c, f)i e β = h(a), (a, b, c), (a)i, la sequenza γ = h(_, c), (d), (c, f)i è il suffisso della sequenza α.
Definizione 4.14(Database proiettato). Sia α un pattern sequenziale nel database di sequenze DB. Il database proiettato per il pattern α indicato con DB|α è
l’insieme di tutti i suffissi delle sequenze in DB rispetto al prefisso α. Nella tabella 4.5 è riportata la proiezione del database di sequenze per il pattern h(a)i.
sid S
10 h (_, b), (c), (f, g), (g), (e) i 20 h (_, d), (c), (b), (a, b, e, f) i 30 h (b), (f, g), (e) i
Tabella 4.5: Proiezione del database di sequenze per il pattern h(a)i.
Definizione 4.15 (Supporto in un database proiettato). Siano α un pattern sequenziale nel database di sequenze DB e β una sequenza con prefisso α. Il supporto di β in un database proiettato per α, DB|α, indicato come SupDB|α(β) è
il numero delle sequenze γ in DB|α tali che β v α · γ.
La complessità computazionale in termini di tempo di un algoritmo di sequential pattern mining dipende dal numero di pattern nello spazio di ricerca e dal costo delle operazioni per generare e esaminare ciascun itemset. Gli algoritmi che adottano una tecnica pattern-growth hanno il vantaggio di prendere in considerazione solo i pattern che esistono veramente nel database. Purtroppo questo vantaggio non si traduce in performance in quanto il costo delle operazioni di lettura del database per creare le proiezioni può essere molto alto. L’algoritmo CM-SPADE è più veloce di PrefixSpan di almeno un ordine di grandezza [14].
Il numero di pattern nello spazio di ricerca dipende dal parametro di supporto minimo specificato dall’utente e da quanto similari sono le sequenze nel database. In generale al decrescere dal valore di supporto minimo il numero di pattern sequenziali aumenta esponenzialmente. Lo spazio di ricerca può essere molto grande perfino per quei database che contengono poche sequenze. Basti pensare che in un database che contiene solo due sequenze identiche composte di 100 item può dar luogo ad un numero di pattern sequenziali uguale a 2100.
CAPITOLO 4. IL PROCESSO DI KDD