Telemat Lab's home page


Copyrigtht © 2001 Universita' di Firenze. All rights reserved.

Free license available.

WEB CHANGE 2001

di: Sauro Menchetti

Revisore: Prof. Franco Pirri


Capitolo 4 - Criterio di Confronto

Home Page Indice Pag. Prec. Pag. Succ.

4 Criterio di Confronto

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.


Indice del Capitolo 4


4.1 Richiami di Algebra Lineare

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:

Prodotto Scalare

Si verifica che valgono le seguenti proprietà:

Proprietà Prodotto Scalare

X, Y appartenenti a Rn si dicono ortogonali se:

Ortogonalità

Si dice norma di X appartenente a Rn il numero reale non negativo:

Norma

Vale la seguente disuguaglianza di Schwarz:

Disuguaglianza Schwarz

Dalla disuguaglianza di Schwarz segue immediatamente:

Prodotto Scalare Normalizzato

Dati X, Y appartenenti a Rn\{Ø}, si dice angolo fra X e Y l'angolo Zero PiGreco tale che:

Coseno Theta


4.2 Algoritmo di Confronto

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:

Inverse Document Frequency

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:

Elemento del Documento

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:

Elemento del Documento

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:

Coseno Theta

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].

Ultimo aggiornamento: 11 Febbraio 2001


Telemat Lab's home page

Home Page Indice Pag. Prec. Pag. Succ.


Explore the TELEMAT Site !!!