Ricerca in Database Strutturati
Traduzione e Integrazione
delle Lezioni a cura di Sandro Gallo
Home Alberi Decisionali OLAP
Spesso ci si trova a lavorare con tipi di dato particolarmente
complessi e strutturati, tali da non poter essere descritti e
immagazzinati in normali basi di dati. Un esempio eclatante
è la rappresentazione dei dati in chimica, che avviene
tramite graphi. Ed è ovvio pensare che esistano database
di graphi sui quali effettuare ricerche strutturate.
Le motivazioni che hanno spinto alla costruzione di database
strutturati sono da una parte inerenti il tipo di oggetti
d'interesse, cioè molecole. Queste sono usualmente
classificate in base alle caratteristiche strutturali presenti in
piu’strutture o in base alla loro attivita’
biologica. Dall'altra parte riguardano l'utilizzo che se ne
fa.
Cioè questi database di strutture chimiche in forma di
grafi possono servire per predire funzioni di un nuovo composto
naturale o sintetizzato in base ai suoi frammenti, o per
ricercare la struttura 2D/3D di proteine. I campi d'applicazione,
quindi, si estendono dalla biologia, bioinformatica, proteomica
alla computer grafica(dai pixel ai grafi per riconoscere
caratteri, o dalle immagini ai grafi per riconoscere regioni
adiacenti). Dati due grafi, G=(V,E) e G'=(V',E'), G e G' sono
isomorfi se esiste una biezione
cioè possiamo rietichettare i vertici di G per essere
vertici di G', mantenendo la corrispondenza tra gli archi in G e
G'. Dati due grafi, G=(V,E) e G'=(V',E'), allora G è
sottografo omomorfo di G', se G è isomorfo a
un sottografo di G'. G può essere sottografo isomorfo a
diversi sottografi di G'. Un grado G = (V,E) è
sottografo isomorfo di G' = (V',E') se esiste una
iniezione
cioè noi possiamo rietichettare i vertici di G per essere
vertici di G', mantenendo gli archi corrispondenti in G. Riguardo
la complessità, l'isomorfismo tra grafi è
difficile, ma ancora non è stato provato se è un
problema NP-completo o meno. Invece è provato che il
matching con sottografi è NP-completo.
Un'algoritmo bruto, rozzo che fa il matching tra grafi impiega
tempo quasi esponenziale, infatti ci sono n! modi se il grafo ha
n nodi di cercare un match. Alcuni modi per aumentare la
velocità nel fare l'isomorfismo tra sottografi sono: l'uso
di computer più veloci, lo sviluppo di trucchi che evitino
quelle soluzioni che portano a fallimento, anticipare molti passi
di computazione nella fase di pre-processing.
Un esempio di trucchi che evitano le soluzioni non corrette
è il backtracking, cioè l'abbandono di
soluzioni parziali quando possiamo affermare che portano ad un
fallimento. Il backtracking procede così:
- Mappa un numero arbitrario di coppie di nodi
- Quindi mappa il loro contorno
- Se ottieni un successo, mappa il contorno del contorno, etc.
etc.
- Altrimenti torna indietro di un passo, e prova un mapping
differente
- L'algoritmo termina quando:
- tutti i nodi sono stati mappati, oppure
- quando tutte le alternative per il primo nodo da matchiare
sono state provate e portano tutte a fallimento.
Al backtracking si può affiancare il partitioning
che tenta di dividere i nodi in gruppi possibilmente
corrispondenti. Se la lista delle corrispondenze possibili
diventa vuota per un nodo query, allora nessun isomorfismo
è possibile.
Un algoritmo per il matching esatto con sottografi
è quello di Ullmann, l'algoritmo VF.
Siano
grafi da matchare. Sia M(s) ={(n,m) in V1xV2 tali che n è
mappato in m nella soluzione parziale corrente corrispondente
allo stato s}, e siano M1(s) e ( M2(s) ) gli insiemi dei primi (
rispettivamente secondi ) componenti delle coppie in M(s). Siano
E1(s) e E2(s) gli insiemi di tutti gli archi che connettono i
nodi in M1(s) e M2(s), rispettivamente. Siano
.
Sia (n,m) una coppia candidata con
.
La coppia (n,m) è aggiunta alla mappa se tutte le seguenti
condizioni sono soddisfatte:
- Il numero di nodi in T1(s) connessi a n è minore o
uguale al numero di nodi in T2(s) connessi a m.
- Il numero di nodi connessi a n che non sono né in
M1(s) né in T1(s) è minore o uguale al numero di
nodi connessi a m che non sono né in M2(s) né in
T2(s).
Lo pseudo-codice della procedura VF è il
seguente:
PROCEDURE Match(s)
INPUT: stato s; per lo stato iniziale so, M(so)= 0
OUTPUT: la mappatura
IF M(s) copre tutti i nodi THEN
OUTPUT M(s)
ELSE
Calcola P(s) di tutte le coppie candidate per l’inclusione
in M(s)
FOREACH p in P(s)
IF Le regole per includere p in M(s) hanno successo THEN
Calcola lo stato s’ ottenuto in modo da aggiungere p a
M(s)
CALL Match(s’)
END IF
END FOREACH
END IF
END PROCEDURE
Per iniziare a parlare di algoritmi di matching inesatto,
dobbiamo innanzitutto definire una funzione distanza. La
distanza tra Ga e Gb è il costo di trasformare Ga in Gb,
cioè dell'isomorfismo. Invece per isomorfismo tra
sottografi, è il costo di trasformare Ga in una parte di
Gb. Il nostro scopo è trovare tutti i match di Ga con Gb
tali che d(Ga, Gb) < threshold. Esempi di funzioni
distanza sono: rietichettatura dei nodi, delete-insert di archi,
delete-insert di nodi, con il relativo costo associato ad ogni
operazione.
Se l'algoritmo di Ullmann è utile per eseguire un
match esatto tra due grafi, per il matching inesatto abbiamo
l'algorimo di Nilsson. Lavoreremo non più sul
confronto tra due grafi, ma sul confronto di un grafo query con
un database di grafi:
Studieremo il GraphBlast, i cui passi sono:
- Filtering, cioè l'indicizzazione per trovare i grafi
candidati e i sottograi candidati.
- Query Specification, cioè la formulazione di una
query.
- Matching, usando VF o combinando i path.
- Data Storing.
Nel GraphBlast un grafo è un insieme di cammini, ed
è in questo modo che viene memorizzato nel database. Il
database usato è il Berkeley DB. Per
filtrare il database usiamo i fingerprint, che sono
indici costruiti con hash, associati ad ogni grafo nel database,
usati per compare le strutture, per cercare similarità.
Dopo aver filtrato il database costruendo un database di
fingerprint da cui prendere una query fingerprint per quanto
concerne i grafi candidati, e aver filtrato i sottografi
candidati decomponendoli in pattern, si mettono insieme i due
risultati e si processa la query. Quindi si passa a fare il match
con il grafo query in ingresso o usando VF, matching grafo-grafo
sui sottografi, o usando SQL come algebra per combinare i cammini
dei sottografi candidati.
GraphBlast definisce GLIDE per le query
approssimate, cioe’ non completamente specificate,
cioe’ contenenti wildcards. È un query
graph language per rappresentare testualmente i grafi.
In molti ambiti gli oggetti di un dataset vengono rappresentati
mediante strutture dati complesse, come i grafi. Anche sui grafi
applicheremo le tecniche di data mining, infatti possiamo fare le
seguenti associazioni tra il mondo dei grafi e il mondo delle
transazioni/dati:
Gli algoritmi per il graph mining si dividono in
due classi:
- Quelli basati su tecniche Apriori:
- AGM/AcGM
- FSG
- PATH#
- FFSM
- E quello basati sulla crescita dei pattern:
- MoFa
- gSpan
- Gaston
Il canonical labeling aiuta alla comparazione veloce tra
grafi e nell'ordinamento completo e deterministico per insiemi di
grafi. Le canonical label usate sono:
- Concatenazione di righe o colonne della matrice di
adiacenza=> non univoco!
- Tra tutte le possibili permutazioni dei nodi, scelta del
codice maggiore o minore.
- Utilizzo di vertex invariants per il partizionamento in
classi di nodi.
Definiamo il problema del mining dei grafi nel seguente
modo:
Frequent Subgraph Discovery:
Input:
dataset di n grafi etichettati non orientati.- s, supporto minimo 0
L'obiettivo è trovare tutti i sottografi non orientati e
connessi presenti in almeno ns grafi del dataset D.
L'algortimo Apriori largamente usato nei modelli
market/basket è lo schema base per alcuni algoritmi di
ricerca di sottografi. Lo pseudo-codice dell'algoritmo
è il seguente:
Tra i tanti algoritmi elencati sopra vedremo FSG e
gSpan. In FSG, basato su Apriori, si osserva l'incremento
della dimensione dei sottografi frequenti mediante aggiunta di un
arco alla volta. Utilizza il canonical labeling e ottimizza la
generazione dei candidati e il conteggio degli insiemi
frequenti.
Fsg(D, s)
{
1: F1 = tutti i sottografi frequenti di dimensione 1 in
D
2: F2 = tutti i sottografi frequenti di dimensione 2 in
D
3: k = 3
4: while 
do
5: Ck = fsg-gen(Fk-1)
6: for each candidate do
7: Gk.count = 0
8: for each transaction 
do
9: if Gk è in T then
10: Gk.count = Gk.count + 1
11: 
12: k = k+1
13: return {F1, F2, ..., Fk-2}
}
Al rigo 1 e 2 si ha la generazione di tutti i sottografi
frequenti di dimensione 1 e 2. Nelle righe 4-6 vi è la
generazione dei sottografi candidati di dim. K mediante fusione
dei sottografi frequenti di dim. k-1. Alle righe 8-10 si fa il
conto dei grafi frequenti. Nel rigo 13 c'è la selezione
dei candidati che soddisfano il vincolo di supporto.
La join avviene tra sottografi di dimensione K che
condividono lo stesso (k-1)-subgraph (core). Il risultato
potrebbe non essere un unico (k+1)-sottografo.
Al rigo 2 vi è la generazione di tutti i core condivisi
per ogni coppia di sottografi frequenti. Al rigo 4 vi è la
generazione di tutti i possibili candidati mediante fusione di
ogni coppia di sottografi frequenti, per ogni core condiviso. E
al rigo 7 inizia il False test.
Un automorfismo di un grafo G è l'isomorfismo di un
grafo con se stesso; cioè una mappa dai vertici di G ai
vertici di G tale che il grafo risultante è isomorfo a G.
Il canonical labeling rappresenta un punto critico
dell’algoritmo. Viene massicciamente impiegato nei test di
ridondanza (candidati già generati durante la join) e nei
False test per la verifica di sottografi frequenti. Per questioni
di efficienza, l’algoritmo di CL utilizzato fa uso di
vertex invariants, prevedendone tre versioni differenti:
Partition ordering, Neighbor list, Iterative partitioning.
Nella generazione dei candidati ci sono tre step
computazionalmente costosi, cioè la generazione di
core ( e automorfismi), join, eliminazione
candidati infrequenti. Le possibili ottimizzazioni da fare
sono 3: Ogni k-subgraph frequente mantiene le canonical label dei
suoi (k-1)-subgraph frequenti; Inverted indexing scheme; Caching
degli automorfismi dei cores precedenti; Uso di canonical
labeling per la verifica di ridondanze e sottografi infrequenti
(test veloci e ricerca binaria).
Il frequency counting di FSG ha un costo elevato, pari a
nxmk (n=|D|, mk=# di candidati al passo k). Il costo
computazionale è ridotto dall’uso di transaction
identifier (TID) lists:
- Ogni sottografo frequente mantiene la lista di TID delle
transazioni nelle quali è contenuto.
- Per il calcolo della frequenza di un (k+1)-subgraph si
considera l’intersezione delle liste di TID dei suoi
k-subgraph frequenti.
- Se la dimensione della lista è minore del supporto
minimo, il candidato viene scartato, altrimenti viene valutata la
frequenza sulle sole transazioni della lista.
I vantaggi di fsg sono la ricerca di sottografi generali e
le numerose ottimizzazioni. Gli svantaggi sono la
Candidate generation che è comunque costosa nonostante
ottimizzazioni (false test e join ridondante), e la
complessità spaziale elevata (a causa di BFS).
Gspan è un altro algoritmo per il graph mining
basato sulla crescita di pattern. Le sue
caratteristiche sono: l'uso di Depth-first search
(DFS) invece di breadth-first search, l'incremento della
dimensione dei sottografi frequenti mediante aggiunta di un arco
alla volta; lo spazio di ricerca è un albero
gerarchicamente basato sul DFS code; la join è
sostituita dalla meno onerosa extension e i false test
sono eliminati.
Quando si usa DFS si costruisce un DFS-tree. A
questo corrisponde la generazione di una sequenza lineare di
vertici, che vengono etichettati con i DFS-subscript. Il
grafo risultante si indica con GT. Chiamiamo il vertice v0 la
radice (root) e vn il vertice più a destra (right-most
vertex). Il cammino da v0 a vn è chiamato rightmost
path. Dato GT il forward edge set Ef,T è
l'insieme degli archi nel DFS-tree, mentre il backward edge
set Eb,T è l'insieme degli archi non presenti nel
DFS-tree. Per semplicità scriviamo così i due
insiemi:
Definiamo quindi:
- ordinamento forward:
- Ordinamento backward:
- Ordinamento forward-backward:
- ordinamento totale:
Dato un DFS-tree per un grafo G, se una sequenza di archi
(ei) può essere costruita usando l'ordinamento totale
definito sopra, allora (ei) è chiamato DFS-code per
G, e si indica con code(G,T).
Un ordinamento lessicografico può essere definito
usando il DFS-code. Sia Z = {code(G,T) | T è un
DFS-tree di G}, cioè Z è un insieme contenente
tutti i DFS-code per G.
Sia a = code(Ga, Ta) = (a0, a1, ..., am) , b = code(Gb, Tb) =
(b0, b1, ..., bn), a, b sono in Z. Allora l'ordinamento
lessicografico DFS è definito così:
se e solo se: 
Il minimum DFS code di un grafo G è il DFS code
minimo in base all’ordinamento lessicografico DFS e
costituisce il canonical label di G.
Lo spazio di ricerca di GSPAN è rappresentato dal
DFS-code tree, che è un albero che in ogni nodo
contiene un DFS-code. L'operazione di extension per la
costruzione dei figli di ogni nodo consta nell'aggiunta di archi
per i soli nodi del rightmost path. La relazione tra fratelli
segue l'ordinamento lessicografico.
Alcuni teoremi sullo spazio di ricerca in Gspan:
- DFS Code Tree Covering: Il DFS-code tree contiene i minimum
DFS-code di tutti i grafi (completa enumerazione)
- DFS Code Growth: Il minimum DFS-code di un grafo G, durante
la DFS, è incontrato prima di qualsiasi altro DFS-code non
minimum rappresentante G.
- DFS Code Pruning: La discendenza di un nodo con DFS-code non
minimum non darà vita ad alcun nodo con DFS code
minimum.
L'algoritmo di Gspan è il seguente:
I vantaggi con Gspan sono i seguenti: La Join in candidate
generation è sostituita da extension (minore
complessità e ridondanze); Vengono eliminate i false test
in candidate generation. La complessità spaziale è
ridotta (grazie a DFS), come ridotte sono le transazioni del
dataset ad ogni macropasso. In generale le prestazioni sono
superiori ad FSG.
Gli svantaggi sono la necessità dei pruning test
per la possibilità di DFS code duplicati, e che la
risoluzione di subgraph isomorphism problems, anche se in
quantità ridotta, è comunque presente.
Home Alberi Decisionali OLAP