Copyrigtht © 2001 Universita' di Firenze. All rights reserved.
Free license available.
Una volta definita la rappresentazione di un documento, è necessario capire quale possa essere il criterio di confronto che permetta di stabilire se due pagine hanno lo stesso contenuto. L'algebra lineare ci aiuta ad individuare un criterio di confronto consistente con la nostra rappresentazione del documento.
L'algebra lineare permette di stabilire un criterio di confronto tra due documenti. Ecco ciò che è utile al nostro scopo.
Si definisce prodotto scalare fra gli elementi X, Y appartenenti a Rn il numero reale:
Si verifica che valgono le seguenti proprietà:
X, Y appartenenti a Rn si dicono ortogonali se:
Si dice norma di X appartenente a Rn il numero reale non negativo:
Vale la seguente disuguaglianza di Schwarz:
Dalla disuguaglianza di Schwarz segue immediatamente:
Dati X, Y appartenenti a Rn\{Ø}, si dice angolo fra X e Y
l'angolo tale che:
L'algoritmo di confronto si basa sulla seguente rappresentazione del documento.
Ogni documento d è rappresentato come un vettore d = (d1, ... , d|V|), dove |V| è il numero di elementi del vocabolario costruito in precedenza. In questo modo i documenti con un contenuto simile avranno un vettore di rappresentazione simile in accordo ad una fissata metrica di similarità. Ogni elemento di rappresenta una distinta parola wi. Il termine di viene calcolato come combinazione dei due termini TF(wi, d) e DF(wi). Il termine TF(wi, d) (term frequency) è il numero di volte che la parola wi compare nel documento d, mentre il termine DF(wi) (document frequency) è il numero di documenti nei quali la parola wi compare almeno una volta. Possiamo così definire il termine IDF(wi) (inverse document frequency) nel seguente modo:
dove |D| è il numero totale dei documenti. Intuitivamente il termine IDF(wi) è piccolo se la parola wi compare in molti documenti ed è grande se la parola wi compare in un solo documento.
Il peso di di una parola wi nel documento d è dato da:
L'euristica per pesare una parola afferma che una parola wi è un termine importante per il documento d se compare molte volte in esso. D'altra parte, le parole che compaiono in molti documenti sono meno importanti come conferma la loro frequenza inversa.
Poiché i nostri documenti sono delle pagine html, non tutte le parole presenti nella pagina hanno la stessa importanza. Alcuni tags html attribuiscono un particolare significato alle parole a cui sono legati e sembra quindi opportuno pesare diversamente quelle parole. In conclusione, il peso di di una parola wi nel documento d è dato da:
dove WEIGHT(wi, tag) rappresenta il peso della parola associata ad un particolare tag html.
A questo punto interviene l'algebra lineare. Siano H1 e H2 le due pagine html da confrontare e siano d1 e d2 le rispettive rappresentazioni. Come criterio di confronto viene scelto il coseno dell'angolo compreso tra i due vettori d1 e d2:
Se le due pagine sono molto simili, i due vettori di rappresentazione saranno molto vicini e l'angolo compreso sarà quindi piccolo, risultando in un valore del coseno prossimo ad 1. D'altra parte, se le due pagine sono completamente diverse, i due vettori di rappresentazione saranno ortogonali e il coseno dell'angolo compreso varrà 0.
Adesso non resta che definire una soglia al di sopra della quale si attribuisce lo stesso contenuto ai due documenti. Un valore appropriato sembra essere compreso tra [0.8, 0.9].