Kernel ad albero: quantificazione della somiglianza tra dati strutturati ad albero

Una rete o un grafo è un tipo di dati strutturati sotto forma di nodi , con relazioni tra di loro descritte da collegamenti o bordi . I nodi e gli spigoli in un grafico possono avere diversi attributi che possono essere numerici o categoriali o anche più complessi.

Oggi è disponibile un'enorme quantità di dati sotto forma di reti o grafici. Ad esempio, il World Wide Web, con le sue pagine web e collegamenti ipertestuali, i social network, le reti semantiche, le reti biologiche, le reti di citazioni per la letteratura scientifica e così via.

Un albero è un tipo speciale di grafico ed è naturalmente adatto a rappresentare molti tipi di dati. L'analisi degli alberi è un campo importante nell'informatica e nella scienza dei dati. In questo articolo, esamineremo l'analisi della struttura dei collegamenti negli alberi. In particolare, ci concentreremo sui kernel degli alberi, un metodo per confrontare i grafi degli alberi tra loro, consentendoci di ottenere misurazioni quantificabili delle loro somiglianze o differenze. Questo è un processo importante per molte applicazioni moderne come la classificazione e l'analisi dei dati.

Classificazione non supervisionata dei dati strutturati

La classificazione è una componente importante dell'apprendimento automatico e dell'analisi dei dati. In generale, la classificazione può essere supervisionata o non supervisionata . Nella classificazione supervisionata, le classi sono già note e viene costruito un modello di classificazione dai dati di addestramento in cui sono già fornite le classi corrette. La classificazione senza supervisione, al contrario, tenta di identificare le classi di cui non se ne conosce nessuna, raggruppando i dati in categorie in base a una certa misura della loro somiglianza.

La classificazione senza supervisione può essere combinata con la teoria dei grafi per identificare gruppi di reti di alberi simili. Le strutture di dati ad albero vengono utilizzate per modellare oggetti da diversi domini. Nell'elaborazione del linguaggio naturale (NLP), ad esempio, gli alberi di analisi sono modellati come alberi ordinati ed etichettati. Nel ragionamento automatizzato, molti problemi vengono risolti mediante la ricerca, in cui lo spazio di ricerca è rappresentato come un albero i cui vertici sono associati agli stati di ricerca e gli archi rappresentano passaggi di inferenza. Inoltre, i dati semistrutturati, come i documenti HTML e XML, possono essere modellati come alberi ordinati ed etichettati.

Questi domini possono essere utilmente analizzati attraverso tecniche di classificazione senza supervisione. Nella PNL, la classificazione può essere utilizzata per raggruppare automaticamente una serie di frasi in domande, comandi e affermazioni. Allo stesso modo, i gruppi di siti Web simili possono essere identificati applicando metodi di classificazione alla loro fonte HTML. In ognuno di questi casi, tutto ciò di cui abbiamo bisogno è un modo per misurare quanto "simili" due alberi tra loro.

La maledizione della dimensionalità

La maggior parte degli algoritmi di classificazione richiede che i dati vengano trasformati in una forma vettorializzata, che rappresenti i valori delle caratteristiche dei dati nello spazio delle caratteristiche , in modo che i dati possano essere analizzati nello spazio delle caratteristiche utilizzando l'algebra lineare. Nei dati strutturati o semistrutturati, come gli alberi, la dimensionalità dei vettori risultanti (ovvero il numero di caratteristiche nello spazio delle caratteristiche) potrebbe essere piuttosto elevata, poiché lo spazio delle caratteristiche deve preservare le informazioni sulla struttura.

Questo può essere uno svantaggio significativo, considerando che molte tecniche di classificazione non sono in grado di scalare efficacemente con la dimensionalità dell'input. In altre parole, il loro potere di classificazione diminuisce all'aumentare della dimensionalità dell'input. Questo problema è noto come la maledizione della dimensionalità.

Per avere un'idea del motivo di questo degrado delle prestazioni, si consideri uno spazio X di dimensione d . Supponiamo che X contenga un insieme di punti uniformemente distribuiti. Se il numero di dimensioni di X aumenta, il numero di punti necessari per mantenere la stessa densità deve aumentare in modo esponenziale. In altre parole, maggiori sono le dimensioni dell'input, più è probabile che i dati siano scarsi. In generale, un set di dati sparso non fornisce informazioni sufficienti per costruire un buon classificatore perché le correlazioni tra gli elementi di dati sono troppo deboli per essere rilevate dagli algoritmi.

Ogni spazio di funzionalità sopra contiene otto punti dati. Nello spazio unidimensionale, è facile identificare un gruppo di cinque punti a sinistra e tre a destra. Allungare questi punti su un numero maggiore di caratteristiche (cioè dimensioni) rende più difficile trovare questi gruppi. Nelle applicazioni reali, gli spazi delle caratteristiche possono facilmente avere centinaia di dimensioni.

Una rappresentazione vettorializzata per i dati strutturati è appropriata quando le informazioni sul dominio possono essere utilizzate in modo efficace per selezionare un insieme gestibile di funzionalità. Quando tali informazioni non sono disponibili, è opportuno avvalersi di tecniche in grado di gestire direttamente i dati strutturati, senza eseguire operazioni nello spazio vettoriale.

Metodi del kernel

I metodi del kernel evitano la necessità di convertire i dati in forma vettoriale. L'unica informazione di cui hanno bisogno è una misurazione della somiglianza di ciascuna coppia di elementi in un set di dati. Questa misura è chiamata kernel e la funzione per determinarla è chiamata funzione kernel . I metodi del kernel cercano relazioni lineari nello spazio delle caratteristiche. Funzionalmente, equivalgono a prendere il prodotto scalare di due punti dati nello spazio delle funzionalità, e in effetti la progettazione delle funzionalità può ancora essere un passaggio utile nella progettazione delle funzioni del kernel. Tuttavia, i metodi dei metodi del kernel evitano di operare direttamente sullo spazio delle funzionalità poiché si può dimostrare che è possibile sostituire il prodotto scalare con una funzione del kernel, purché la funzione del kernel sia una funzione semidefinita simmetrica e positiva che può prendere come input i dati nel suo spazio originario.

Il vantaggio dell'utilizzo delle funzioni del kernel è quindi che un enorme spazio di funzionalità può essere analizzato con una complessità computazionale non dipendente dalla dimensione dello spazio delle funzionalità, ma dalla complessità della funzione del kernel, il che significa che i metodi del kernel non subiscono la maledizione di dimensionalità.

Se consideriamo un set di dati finito composto da n esempi, possiamo ottenere una rappresentazione completa delle somiglianze all'interno dei dati generando una matrice del kernel la cui dimensione è sempre n × n . Questa matrice è indipendente dalla dimensione di ogni singolo esempio. Questa proprietà è utile quando deve essere analizzato un piccolo set di dati di esempi con un ampio spazio di funzionalità.

In generale, i metodi del kernel si basano su una risposta diversa alla domanda sulla rappresentazione dei dati. Invece di mappare i punti di input in uno spazio delle funzionalità, i dati vengono rappresentati tramite confronti a coppie in una matrice del kernel K e tutte le analisi pertinenti possono essere eseguite sulla matrice del kernel.

Molti metodi di data mining possono essere kernelizzati. Per classificare istanze di dati strutturate ad albero con metodi del kernel, ad esempio con macchine vettoriali di supporto, è sufficiente definire una funzione del kernel valida (simmetrica definita positiva) k : T × T → R , denominata anche kernel ad albero . Nella progettazione di kernel di alberi praticamente utili, si richiederebbe che siano calcolabili in tempo polinomiale sulla dimensione dell'albero e che siano in grado di rilevare grafi isomorfi. Tali kernel ad albero sono chiamati kernel ad albero completi .

Noccioli dell'albero

Ora, introduciamo alcuni utili kernel per alberi per misurare la somiglianza degli alberi. L'idea principale è calcolare il kernel per ogni coppia di alberi nel set di dati al fine di costruire una matrice del kernel, che può quindi essere utilizzata per classificare insiemi di alberi.

Kernel di stringhe

Innanzitutto, inizieremo con una breve introduzione ai kernel di stringa, che ci aiuterà a introdurre un altro metodo del kernel basato sulla conversione di alberi in stringhe.

Definiamo num y (s) come il numero di occorrenze di una sottostringa y in una stringa s , con | s | che denota la lunghezza della corda. Il kernel di stringa che descriveremo qui è definito come:

K stringa (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

Dove F è l'insieme di sottostringhe che si trovano sia in S 1 che in S 2 e il parametro ws serve come parametro di peso (ad esempio, per enfatizzare importanti sottostringhe). Come possiamo vedere, questo kernel dà un valore più alto a una coppia di stringhe quando condividono molte sottostringhe comuni.

Tree Kernel basato sulla conversione di alberi in stringhe

Possiamo usare questo kernel di stringhe per costruire un kernel ad albero. L'idea alla base di questo kernel è convertire due alberi in due stringhe in un modo sistematico che codifichi la struttura dell'albero, e quindi applicare loro il kernel di stringa sopra.

Convertiamo i due alberi in due stringhe come segue:

Sia T uno degli alberi target e label(n s ) l'etichetta della stringa del nodo n s in T . tag(n s ) denota la rappresentazione in stringa del sottoalbero di T radicato in n s . Quindi se n root è il nodo radice di T , tag(n root ) è la rappresentazione in stringa dell'intero albero T .

Quindi, sia string(T) = tag(n root ) indichi la rappresentazione in stringa di T . Applicheremo ricorsivamente i seguenti passaggi in modo bottom-up per ottenere string(T) :

• Se il nodo n s è una foglia, let tag(n s ) = “[” + label(n s ) + “]” (dove + qui è l'operatore di concatenazione di stringhe).
• Se il nodo n s non è una foglia e ha c figli n 1 , n 2 , … , n c , ordina tag(n 1 ), tag(n 2 ), … , tag(n c ) in ordine lessicale per ottenere tag (n 1* ), tag(n 2* ), … , tag(n c* ) e let tag(n s ) = “[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + tag(n c* ) + “]” .

La figura seguente mostra un esempio di questa conversione da albero a stringa. Il risultato è una stringa che inizia con un delimitatore di apertura come "[" e termina con la sua controparte di chiusura, "]", con ciascuna coppia nidificata di delimitatori corrispondente a un sottoalbero radicato in un particolare nodo.

Ora possiamo applicare la conversione di cui sopra a due alberi, T 1 e T 2 , per ottenere due stringhe S 1 e S 2 . Da lì, possiamo semplicemente applicare il kernel di stringa descritto sopra.

Il kernel dell'albero tra T 1 e T 2 tramite due stringhe S 1 e S 2 può ora essere dato come:

K albero (T 1 , T 2 ) = K stringa ( stringa(T 1 ), stringa(T 2 ) ) = K stringa (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

Nella maggior parte delle applicazioni, il parametro peso diventa w | s | , ponderando una sottostringa in base alla sua lunghezza | s | . Tipici metodi di ponderazione per w | s | sono:

• ponderazione costante ( w | s | = 1 )
• k -ponderazione dello spettro ( w | s | = 1 se | s | = k , e w | s | = 0 altrimenti)
• ponderazione esponenziale ( w | s | = λ | s | dove 0 ≤ λ ≤ 1 è un tasso di decadimento)

Per calcolare il kernel, è sufficiente determinare tutte le sottostringhe comuni F , e contare il numero di volte che si verificano in S 1 e S 2 . Questo passaggio aggiuntivo per trovare sottostringhe comuni è un problema ben studiato e può essere eseguito in O( | S 1 | + | S 2 | ) , utilizzando alberi di suffissi o array di suffissi. Se assumiamo che il numero massimo di lettere (bit, byte o caratteri, ad esempio) necessario per descrivere l'etichetta di un nodo sia costante, le lunghezze delle stringhe convertite sono | S 1 | = O( | T 1 | ) e | S 2 | = O( | T 2 | ) . Quindi, la complessità computazionale del calcolo della funzione kernel è O( | T 1 | + | T 2 | ) , che è lineare.

Kernel dell'albero basato su sottopercorsi

Il kernel dell'albero sopra utilizzava un approccio orizzontale, o in ampiezza, per convertire gli alberi in stringhe. Sebbene questo approccio sia abbastanza semplice, questa conversione significa che non può operare sugli alberi direttamente nella loro forma originale.

Questa sezione definirà un kernel ad albero che opera sulle strutture verticali negli alberi, consentendo al kernel di operare direttamente sull'albero.

Una sottosezione di un percorso dalla radice a una delle foglie è chiamata sottopercorso e un insieme di sottopercorsi è l'insieme di tutti i sottopercorsi inclusi nell'albero:

Assumiamo di voler definire un albero kernel K(T 1 , T 2 ) tra due alberi T 1 e T 2 . Usando il set di sottopercorsi, possiamo definire questo kernel ad albero come:

K(T 1 , T 2 ) = Σ p∈P num p (T 1 )num p (T 2 )w | p |

Dove num p (T) è il numero di volte in cui il sottocammino p ricorre nell'albero T , | p | è il numero di nodi nel sottopercorso p e P è l'insieme di tutti i sottopercorsi in T 1 e T 2 . w | p | è il peso, simile a quello introdotto nella sezione precedente.

Qui, presentiamo una semplice implementazione di questo kernel usando una ricerca approfondita. Sebbene questo algoritmo venga eseguito in tempo quadratico, esistono algoritmi più efficienti che utilizzano alberi di suffissi o array di suffissi o un'estensione dell'algoritmo quicksort multichiave, che può ottenere in media tempo lineare ( O( | T 1 | log | T 2 | ) ):

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

In questo esempio, abbiamo utilizzato il parametro di ponderazione w | s | w | p | = 1 . Questo dà a tutti i sottopercorsi la stessa ponderazione. Tuttavia, ci sono molti casi in cui è appropriato utilizzare la ponderazione dello spettro k o un valore di peso assegnato dinamicamente.

Siti web minerari

Prima di concludere, diamo un'occhiata brevemente a un'applicazione nel mondo reale della classificazione ad albero: la categorizzazione dei siti Web. In molti contesti di data mining, è utile sapere da quale "tipo" di sito web provengono alcuni dati. Si scopre che le pagine di siti Web diversi possono essere classificate in modo abbastanza efficace utilizzando alberi a causa delle somiglianze nel modo in cui sono strutturate le pagine Web per servizi simili.

Come lo facciamo? I documenti HTML hanno una struttura logica nidificata, che è molto simile a un albero. Ogni documento contiene un elemento radice, con elementi aggiuntivi nidificati all'interno. Gli elementi annidati in un tag HTML sono logicamente equivalenti ai nodi figlio di quel tag:

Diamo un'occhiata ad alcuni codici che possono convertire un documento HTML in un albero:

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

Questo produrrà una struttura di dati ad albero che potrebbe assomigliare a questa:

L'implementazione sopra fa uso di un paio di utili librerie Python: NetworkX, per lavorare con strutture di grafi complesse, e Beautiful Soup, per estrarre dati dal web e manipolare documenti.

La chiamata html_to_dom_tree(soup.find("body")) restituirà un oggetto grafico NetworkX radicato nell'elemento <body> della pagina web.

Supponiamo di voler trovare gruppi in un insieme di 1.000 home page di siti Web. Convertendo ogni homepage in un albero come questo, possiamo confrontarli, ad esempio usando il kernel dell'albero dei sottopercorsi fornito nella sezione precedente. Con queste misurazioni della somiglianza, potremmo scoprire che, ad esempio, i siti di e-commerce, i siti di notizie, i blog e i siti didattici sono facilmente identificabili dalla loro somiglianza tra loro.

Conclusione

In questo articolo, abbiamo introdotto metodi per confrontare tra loro elementi di dati strutturati ad albero e mostrato come applicare i metodi del kernel agli alberi per ottenere una misura quantificabile della loro somiglianza. I metodi del kernel si sono rivelati una scelta eccellente quando si opera in spazi ad alta dimensione, una situazione comune quando si lavora con strutture ad albero. Queste tecniche preparano il terreno per un'ulteriore analisi di grandi insiemi di alberi, utilizzando metodi ben studiati che operano sulla matrice del kernel.

Le strutture ad albero si trovano in molte aree di parole reali come documenti XML e HTML, composti chimici, elaborazione del linguaggio naturale o determinati tipi di comportamento degli utenti. Come dimostrato nell'esempio della costruzione di alberi da HTML, queste tecniche ci consentono di eseguire analisi significative in questi domini.