Fare un semplice motore di ricerca -> Traccia

[mamilu]

Fare un semplice motore di ricerca -> Traccia

03-01-06, 18:30
*Un piccolo motore che usa i term vector, il calcolo della similarità col coseno ed una semplice attribuzione di pesi con un generico tfidf sarebbe un buon punto di partenza. **

Come istigato da Low è ora di voltare pagina e smettere di parlare solo di tag, bold, BL, PR, macumbe, galli e pande Fiat.

Abbiamo scoperto che esiste il vector model e l' IR ; studiarli e comprenderne il funzionamento significa voltare pagina nella concezione del fare SEO.

Realizzare un semplice motore di ricerca è uno dei modi più pratici per studiare questi concetti e può divenire un formidabile strumento di discussione e di crescita del forum.

Un gruppo di Geniacci è già all'opera e sta tramando la "cosa".

Tutti gli studi, tutto lo sviluppo, tutti i sorgenti, saranno giorno per giorno resi pubblici e liberamente utilizzabili in quanto public code free da chiunque.

E' quindi senz'altro un progetto di studio aperto a tutti e no profit.

Open Source Engine GT

In questo thread (che resterà chiuso) Mamilu farà una raccolta di tutti gli studi e gli sviluppi della "cosa".

Sarà possibile discutere di questi nell'apposito thread.

Buon Studio a Tutti

Giorgio** **

Theory of Information Retrieval, Florida State University LIS-5263 (Fall, 2003)

Introduzione
Questo documento contiene le spiegazioni di alcuni concetti matematici elementari e mostra la loro applicazione nello sviluppo del modello vettoriale di reperimento delle informazioni come descritto nel "Modern Information Retrieval" by Baeza-Yates and Ribeiro-Neto (1999)

È stato scritto in parziale adempimento dei requisiti richiesti dall'Università di Stato della Florida. [classe 2003, "Lis-5263 - Teoria di reperimento delle informazioni]

La discussione è divisa in due parti; la prima riguarda la matematica di base e la seconda la matematica del modello vettoriale.
Questo è dunque un documento scolastico.

La prima sezione riguarda essenzialmente gli elementi matematici fondamentali:

***Logaritmi **
Coseno
Sommatoria
*** Prodotto scalare (moltiplicazione di vettore)

La seconda sezione spiega la matematica richiesta per calcolare il modello vettoriale:

*** La frequenza inversa del documento (IDF) **
*** Frequenza normalizzata (f i, j ) **
*** Calcolo del peso**

*Elementi matematici fondamentali *

**Logaritmi: log(N) **

Il logaritmo è la prima funzione matematica che dobbiamo capire perché il Modello Vettoriale ha equazioni logaritmiche (N/ni).
**Se non conosciamo cos’è un logaritmo non possiamo capire il concetto del Modello Vettoriale. **

In primo luogo, che cosa è una funzione matematica? Nella sua forma più semplice, una funzione è un calcolo che prende un numero come input, effettua un calcolo su quell'input e restituisce il valore del calcolo.
Consideriamo la funzione quadrata, "sq".

• sq(2) restituisce 4.
• sq(9) restituisce 81.
  Così il sq(N) significa restituire il valore di N * N.

Seguendo questa linea di pensiero, il log (2) significa restituire il logaritmo del numero 2.
Il log (N) significa restituire il valore del logaritmo della variabile N, qualunque valore N possa avere.

Conosciamo ora come quadrare un numero, ma che cosa è la funzione di logaritmo?
Come è calcolato?

Si chiama logaritmo in base a di b l'unica soluzione dell'equazione esponenziale elementare.

Supponiamo di dover risolvere un'equazione esponenziale ax=b :
:
• se a e b si scrivono come potenze (razionali) della stessa base, si eguagliano gli esponenti :

2x* =8 --> 2x = 23 --> x=3 *

• se a e b non si scrivono come potenze (razionali) della stessa base, le soluzioni si scrivono sotto forma di logaritmi : 2x = 8 --> x=log2 8

Il logaritmo risulta essere l'operazione inversa dell'esponenziale.

Senza studiare troppo il senso del termine, possiamo giocare un pò con Google e vedere le risposte che restituisce per la funzione di logaritmo. Google ha un calcolatore incorporato che utilizziamo per questa ricerca.
Digitiamo "log 0,5" (senza le virgolette) in Google e otteniamo -0,301029996.
Proviamo con "log 95" ed otteniamo 1,97772361.
Possiamo tentarne altri; qual è il log 6666?

Questi numeri a caso ci danno un’idea del sistema, ma se realizziamo una tabella organizzata di numeri, questa ci rivela la vera traccia:

N -->log ( N )
1 --> 0
10 --> 1
100 --> 2
1000 --> 3
10000 --> 4

Base 10 alla potenza del* log (N)*=N.
Quindi, se abbiamo un numero (10) e prendiamo il suo logaritmo e innalziamo 10 a quella potenza, otteniamo di nuovo il nostro numero originale:

• 10 alla prima =10
• 10 alla seconda = 100
• 10 alla terza = 1.000
• 10 alla quarta = 10.000

La tabella indica che la funzione di logaritmo è utile nei numeri compressi molto grandi fino ai formati maneggevoli; questo è un calcolo di riduzione in "ordine di grandezza”.
Inoltre, notiamo che il log(1) è uguale a zero.

Ripetiamo facendo un altro esempio.

la potenza abbiamo visto è il prodotto di fattori uguali alla base tante volte quanto indicato dall'esponente.
Per esempio:

5 ³ = 125

La potenza ammette due tipi diversi di operazione inversa : la radice ed il logaritmo.

Radici.
Consideriamo la potenza 5 ³ = 125 . Possiamo allora definire l' "operazione" di radice a indice 3 (o radice cubica) :

Logaritmi.
Esiste un altro modo di definire l'operazione inversa dell'elevamento a potenza : il logaritmo.

Consideriamo ancora la potenza 5 ³ = 125 . Chiediamoci : qual'è il numero per cui elevare la base 5 per ottenere 125 ? Ovviamente questo numero è 3 .

Abbiamo così definito il concetto di logaritmo. Scriviamo allora :

dove il numero 5 scritto in basso a destra del simbolo *log *si chiama base ed il numero di cui si fa il logaritmo si chiama argomento.

La definizione di logaritmo è allora :

Il logaritmo di un numero secondo una certa base è quel numero per cui si deve elevare quella base per ottenere il numero dato.

La caratteristica più interessante della funzione di logaritmo è che i log dei valori fra 0 e 1 sono numeri negativi.
Per esempio, log (0,5) = -0,301029996.
Molte volte vedremo* -log(x)* in un'equazione.

Se il valore di quel segno è negativo, ora sappiamo dunque che la X è una variabile che varia da zero ad uno.

Così ora se vediamo il log (N) in un'equazione, abbiamo un’idea di che cosa significhi e con esso possiamo valutare alcuni valori.

Un logaritmo misura quindi l'ordine di grandezza di un numero N.
E’ solo un più piccolo numero che sostituisce quello originale.

E nel caso speciale dove la N è uno, allora il log(N) sarà zero.

E' possibile discutere questi argomenti qui.

[mamilu]

14-01-06, 08:53

Il coseno
Il coseno è una funzione trigonometrica con alcune proprietà che sono molto utili nell'analizzare i vettori. [ vector model ]

Stiamo raffigurando i** documenti** della nostra raccolta del nostro motore come vettori.
Inoltre raffiguriamo la **query **dell'utente come vettore.
Se potessimo confrontare in qualche modo il vettore di domanda ai vettori di ciascuno dei documenti, potremmo dire quale dei documenti sia "il più vicino" alla domanda.
Ciò ci darebbe una classifica per la nostra ricerca.

Dunque, come classificare la prossimità dei vettori?

Una via da considerare (un pò complicata) è misurare l'angolo fra loro.
Se l'angolo è molto piccolo, significa che i due vettori sono abbastanza vicini. Se l'angolo è grande, allora non lo sono.
Facile.

Tuttavia, se desideriamo usare la matematica occupandoci di angoli, otteniamo numeri-gradi bizzarri.
Gli angoli non sono difficili da manipolare se sono predisposti per variare in modo regolare ... come fra uno e zero per esempio.

**0 **potrebbe significare "completamente differente" e 1 potrebbe significare "identico" con una gamma completa di valori (somiglianze) fra 0 e 1.

Ora, se facciamo una tabella di alcuni angoli e dei loro coseni, possiamo vedere come il coseno semplifica gli angoli:

Angolo A --> Coseno (A)
0° --> 1
30° --> .86
45° --> .70
60° --> .5
90° --> 0

La tabella indica che quando l'angolo fra due vettori è molto piccolo, il coseno è prossimo a 1.
Effettivamente, se i due vettori combinano perfettamente, il coseno è uguale a 1.
Nella nostra applicazione IR, quello sarebbe una accostazione perfetta fra il vettore di domanda e un vettore del documento.

Mentre l'angolo aumenta, il coseno (il grado di somiglianza fra i vettori) diminuisce fino a che non raggiunge zero quando i vettori sono a 90 gradi.
Guardiamo l’immagine:

In un sistema organizzato in cui ogni coordinata ha avuto la sua dimensione, quella potrebbe essere una misura approssimativa di somiglianza. Tuttavia per il nostro modello di vettore desideriamo stimare diverse coordinate (termini di ricerca) anche usando sistemi diversi; dobbiamo quindi rendere il sistema un po’ più complicato
E lo faremo presto!

**Per ora, vediamo che il coseno è una funzione che misura un rapporto fra due vettori. **

Il coseno dell'angolo fra loro è prossimo a UNO se i vettori convergono ed è prossimo a ZERO se l’angolo fra i vettori si avvicina a novanta gradi.

---

Abbiamo già visto che usando la funzione matematica dei logaritmi log (N) possiamo suddividere valori fra 0 e 1;

• log (1) = 0

• -log(x) [i log dei valori fra 0 e 1 sono numeri negativi, per esempio, log (0,5) = -0,301029996. ] Se il valore di quel segno è negativo, sappiamo che la X è una variabile che varia da zero ad uno.
  Nel caso speciale log (N) dove il valore (N) è uno, allora il log(N) sarà zero.

Sappiamo ora anche che con l'uso dei coseni possiamo misurare un rapporto fra due vettori; il coseno dell'angolo fra loro è:

• prossimo a UNO se i vettori convergono.

• prossimo a ZERO se l’angolo fra i vettori si avvicina a novanta gradi.

Sommatoria.

Ora cerchiamo di capire l'operatore di sommatoria, pronunciato "sigma."

Il sigma è un operatore, proprio come un segno di moltiplicazione o un segno di divisione.
Dice di aggiungere insieme una serie di numeri. Quando vediamo un segno di moltiplicazione, sappiamo che moltiplicheremo quei numeri.
Quando vediamo una sigma, sappiamo che aggiungeremo insieme una serie di numeri.

Sia data la successione che è come dire la "sequenza" di numeri . Con essa possiamo costruire la seguente successione detta delle somme parziali :

La successione (i puntini significano che si va all'infinito) così ottenuta si chiama serie e si indica con il simbolo :

ed equivale alla somma di tutti i termini della successione da cui siamo partiti, ovvero :

Ci sono alcune variabili connesse con quell'espressione che dobbiamo conoscere.

Le variabili determinano quanti termini vengono aggiunti e quali membri della serie sono inclusi:

• K variabile è l'indice della sommatoria.. I valori di* K* si allontanano da 1 a n nell'espressione qui sopra.

• Le* a *sono i termini che vengono aggiunti insieme. Possono anche essere espressioni molto complesse, ma sono sempre membri di una serie e vengono sempre sommati insieme.

• Il numero 1 è il limite più basso della sommatoria. Quello ci dice da quale termine iniziare.

• La* n* variabile ci dice quando arrestarci, il limite superiore della sommatoria.

Quando vediamo un'espressione come quella, la traduzione sarebbe "**prodotto della sommatoria da k uguali 1 a k uguali n di *a *sub k" **

Così, una sigma significa " ottieni la somma di questa serie" e quando vediamo un sigma, guardiamo solo quali sono i termini e quindi sommiamoli insieme.
Li aggiungeremo sempre insieme; questo è ciò che significa.

**Dot product - Prodotto scalare **

Bene, ci siamo, è ora di allacciare le nostre cinture di sicurezza!

Questa sezione è un pò una sfida, ma è l'essenza di come funziona il modello vettoriale.

Descriviamo ora un altro operatore matematico.

Quando i matematici (o fisici, o assistenti tecnici, o bibliotecari) desiderano moltiplicare insieme due vettori, l'unico sistema è usare un operatore denominato "Prodotto scalare".

Il relativo simbolo è un puntino grasso: •

Se avessimo due vettori A e B e desiderassimo moltiplicarli insieme, scriveremmo A • B.
E pronunceremo quell'espressione "A Prodotto scalare B".

Il risultato di una operazione di Prodotto scalare è uno scalare (un singolo numero), non un vettore.

Se i vettori sono stati allineati perfettamente, calcoliamo un Prodotto scalare moltiplicando i loro termini corrispondenti ed aggiungendo i prodotti insieme.
Ci saranno altrettanti prodotti quante sono le dimensioni nel sistema coordinato.

Quindi, per un vettore tridimensionale, il Prodotto scalare sarebbe la somma (a scalare) delle coordinate moltiplicate l'un l'altra:

Se A = (a1 , a2, a3 ) and B = (b1 , b2, b3 ), quindi

A • B = a1b1 + a2b2 + a3b3 (dove a1b1 significa la prima coordinata in A moltiplicato la prima coordinata in B, ecc.)

Esempio: se A è un vettore (3, 4, 7) e B è un vettore (9, 2, 1) quindi

A • B = (3 * 9) + (4 * 2) + (7 * 1) = 27 + 8 + 7 = 42.

Questo ci dimostra che per due vettori, A e B, che sono stati allineati perfettamente,** A • B** è uguale alla somma dei prodotti delle coordinate corrispondenti dei due vettori.

Tuttavia, se i vettori non sono stati allineati perfettamente, abbiamo bisogno di un fattore di adattamento per riportare la deviazione nel suo allineamento.
Così la formula generalizzata per un Prodotto scalare ci porta al nostro amico coseno:

**A • B =|A||B|cos **

dove misura l'angolo fra i vettori A e B e |A| significa il valore assoluto del vettore equivalente alla sua lunghezza.
[ la derivazione di questa formula viene dalla Legge dei Coseni,... ma ci fidiamo senza approfondire oltre! ]

Se tentiamo alcuni esempi vedremo il significato di tutto questo.

Quando i vettori sono a 90°, cos è zero, quindi il Prodotto scalare è zero.

Quando i vettori sono molto vicini, il coseno si avvicina ad uno e lo scarto è minimo.

Ciò è usato nella fisica per eseguire funzioni di calcolo: i vettori sono forza e distanza e l'angolo è l'angolo a cui la forza è applicata.

L'immagine è riferita ad un esempio che tratteremo presto per i Term Vector auto, car ed insurance.

Se spingiamo un armadio con la spalla in modo che la forza sia parallela al pavimento, lo faremo scorrere facilmente ma graffierà il pavimento! Se alziamo l'armadio e lo spostiamo, c'è molto più lavoro ma non graffieremo il pavimento!

Vedremo più avanti una variabile di questo caso. Se dividiamo entrambi i lati di questa equazione con |A||B|, otteniamo:

All'inizio abbiamo visto di come il coseno sia un buon proxy per il calcolo della similarità fra i vettori, ora abbiamo scoperto la relazione che possiamo usare per descrivere la somiglianza fra due vettori.

Usando "sim (A, B) per significare quella similarità, possiamo ottenere:

Questa è la chiave matematica dell'espressione di cui necessitiamo per il vector model, perché fornisce una formula per calcolare la somiglianza fra i vettori di termini di quei vettori.

Ci sono tuttavia una coppia di altre formule Prodotto scalare che dobbiamo vedere prima che entriamo nel modello vettoriale.
Usano l'algebra per fare le variazioni sulle equazioni che già abbiamo visto.

A partire da A • B =|A||B|cos , se sostituite A per B (cioè usiamo lo stesso vettore sia per A che per B) otteniamo:

A • A =|A||A|cos

Ma se è lo stesso vettore, quindi allineto con sè stesso e quindi l'angolo fra loro è zero, il coseno degli angoli è dunque uguale a** 1**.

Sostituendo 1 per cos ci dà **A • A=|A||A|=|A|2 **

Se prendiamo la radice quadrata di ogni lato otteniamo:

|A|=sqrt A • A

Ricordando che A • B = a1b1 + a2b2 + a3b3, noi possiamo vedere che** A•A = a1a1 + a2a2 + a3a3**

Ma a1a1 è a12 quindi un modo più compatto di esprimerlo è:

**A •A = a12 + a22 + a32 **

Sostituendo la serie per il Prodotto scalare, otteniamo:

Sotto il segno della radice quadrata vediamo una serie, la somma dei quadrati.

Questa equazione può essere scritta in modo più compatto:

Vedremo più avanti una variazione di questo concetto che ci aiuterà a calcolare l'angolo di comparazione tra un vettore di domanda ed un vettore del documento.

Bene, le cinture di sicurezza le abbiamo allacciate e questo è quanto dovevamo sapere circa il Dot Product - Prodotto scalare, ed è tutto quanto dovevamo conoscere per poter comprendere il vector model di Information Retrieval modello vettoriale di reperimento delle informazioni ]

Siamo quindi pronti per cominciare ad approfondire il concetto di
Calcolo del modello vettoriale

E' possibile discutere questi argomenti qui.

[mamilu]

29-01-06, 05:59

Calcolo del modello vettoriale

Il modello vettoriale [ vector model ] di reperimento delle informazioni [ IR ] conta su tre insiemi di calcoli.
Questo modello può lavorare su parole selezionate da un indice o su un testo integrale.
Nella discussione che seguirà, questo è indifferente.

I calcoli necessari per il modello vettoriale sono:

1. Il peso di ogni parola di indice deve essere calcolato attraverso l'intero insieme del documento. Ciò risponde alla domanda di quanto è importante la parola nell'intera raccolta.

2. Il peso di ogni parola di indice all'interno di un dato documento (nel contesto di quel documento soltanto) deve essere calcolato per tutti i N documenti. Ciò risponde alla domanda di quanto è importante la parola all'interno di singolo documento.

3. Per ogni domanda, il vettore di domanda è confrontato a ognuno dei vettori del documento. I risultati possono essere ordinati. Ciò risponde alla domanda di quale documento è più vicino alla domanda, ed ordina gli altri in base alla prossimità appropriata.

Durante tutta la discussione, dobbiamo avere le definizioni di base del modello vettoriale a nostra disposizione:

**N **- Il numero totale di documenti nel sistema. Se la vostra base di dati contiene 1.100 documenti che sono spostati ad incrementi, allora N = 1.100.

***ki ***- Un certo termine particolare di indice.

**ni **- Il numero di documenti in cui il termine ki compare. Nel caso qui sopra (dove N = 1.100), questo può variare da 0 a 1100.

**freq i , j **- Il numero di volte una data parola chiave (ki) compare in un determinato documento (documento "J")

w i , j - il peso di termine per il ki nel documento J.

**w i , q **- il peso di termine per il ki nel vettore di domanda.

q = (w 1 , q , w 2 , q , ... w t , q) - il vettore di domanda. Queste sono coordinate nel t- spazio dimensionale. Ci sono t termini nel sistema di indice; il vettore di domanda ha un peso per ognuno di loro.

dj = (w 1 , j , w 2 , j , ... w t , j) - Il documento vettoriale. Ci sono N documenti nel sistema quindi ci sono N documenti vettoriali. Ognuno ha un peso per ogni parola chiave nel sistema di indice. Se il sistema è grande, molti di questi valori saranno zero, poiché molte parole chiave non compariranno nel vettore del documento per alcun dato documento. Nei termini matematici, questo è chiamato "sparso".

f i , j - Frequenza normalizzata di ki in dj

**dj **- Un documento rappresentativo, il "j th".

La definizione del modello vettoriale della seguente immagine descrive questi termini (Baeza-Yates & Ribeiro-Neta, 1999). In più, spiega i vettori di domanda ed i vettori di documento. Questi consistono nell'assetto coordinato in cui le coordinate sono i pesi per ogni termine nell'intero sistema.

Ora usiamo il prodotto scalare matematico che abbiamo imparato prima per espanderlo.

Perchè lo facciamo?

Il problema di base è che la formula non comprende i pesi dei termini nel vettore di domanda e nei vettori del documento. Desideriamo usare i pesi per scoprire quale documento/i è più vicino al vettore di domanda.
Per risolvere la similitudine quindi, dobbiamo usare una serie di equazioni per esprimere questa stessa formula in termini di coordinate vettoriali (i pesi).

In primo luogo, dobbiamo ricordare questo:

A ? B = a1b1 + a2b2 + a3b3 dalla definizione del prodotto scalare qui sopra.
Ciò significa che per calcolare il valore di un prodotto scalare, dobbiamo moltiplicare insieme le prime coordinate, quindi le aggiungeremo al prodotto delle seconde coordinate, quindi aggiungeremo la somma al prodotto delle terze coordinate e così via via fino a che non arriviamo alla fine delle coordinate.
Concluderemo con un singolo numero, non un vettore.

Ora, nel nostro modello di vettore, stiamo dicendo che A è il vettore del documento, dj = (w 1 , j , w 2 , j , ... , w t , j)

e B è il nostro vettore di domanda **q = (w 1 , q , w 2 , q , ... , w t , q) **

Quindi sostituiamo A e la B, ed espandiamo i termini, prendendo ogni termine di dj, moltiplicandolo per il termine corrispondente di q ed aggiungendo tutti questi prodotti:

dj ? q = (w 1 , j * w 1 , q ) + (w 2 , j * w 2, q ) + ... + (w n , j * w n , q )

Così stiamo cominciando qui ad incorporare i pesi dei termini. Mettendo questo nuovamente nella nostra equazione per similitudine otteniamo:

Ora valutiamo questo denominatore,|d||q|.

Che cosa possiamo fare con questo? Se cominciamo con l'equazione 2:

|A|= sqr di A ? A

e sostituiamo un vettore del documento con A, noi otteniamo

**|d|=sqr di d ? d **per il componente di documento e:

**|q|=sqr di q ? q **per il componente di domanda

Sostituendo questi nella nostra equazione-mostro avremo:

Bene, già sappiamo come eliminare i prodotti scalare: espanderli nella somma dei prodotti dei termini corrispondenti. Così dobbiamo espandere le due radici quadrate nel denominatore.

Ricordiamoci, che quando prendiamo il prodotto scalare di un vettore con se stesso, otteniamo una serie di quadrati. Se questo è D ? D , la risposta sarà d1d1 + d2d2 + d3d3 che è lo stesso di d12 + d22 + d32. Per il nostro vettore del documento, questo rimanda alle serie delle somme dei quadrati dei pesi:

**dj ? dj = (w 1 , j * w 1 , j) + (w 2 , j * w 2, j) + ... + (w n , j * w n , j) **

o

**dj ? dj = w 1 , j 2 + w 2 , j 2 + ... + w n , j 2 **

Da questa piccola operazione di sigma, possiamo comprendere che come la somma dei quadrati, una serie matematica è molto semplice.
Poiché per il vettore del documento i termini sono i pesi w i , j concludiamo con:

Il vettore di domanda riduce in:

Ciascuno di questi sembra intimidirci, ma il significato è abbastanza semplice.
Lavoriamo attraverso le coordinate una alla volta.
Per ognuna facciamo il suo quadrato e lo aggiungiamo al totale corrente.

Così, mettendo i nostri due sigma nuovamente nell'equazione ci dà:

Ora ci siamo quasi.
L'ultima sostituzione e saremo alla conclusione.

Il numeratore è inoltre una serie che può essere espressa attraverso la notazione di sigma:

**(w 1 , j * w 1 , q) + (w 2 , j * w 2, q) + ... + (w n , j * w n , q) **

Guardando questo esempio vediamo una serie che è sommata, dove ogni termine è il prodotto del peso di vettore del documento per il peso nel vettore di domanda per la data parola chiave.

Nella notazione di sigma che è:

e se lo mettiamo nuovamente dentro la nostra equazione otteniamo:

Ora dunque, conosciamo che cosa significa modello vettoriale e da dove proviene.

Potremmo persino calcolare alcuni esempi se ci sentissimo così volonterosi.

Dato un vettore del documento e un vettore di domanda, tutto ciò che dobbiamo fare è moltiplicare alcune coppie di pesi, sommare quei prodotti, fare una piccola divisione ed abbiamo una misura di similarità.

Sembra arduo ma è invece abbastanza facile.

La prossima volta:
**Valori e pesi delle parole **

E' possibile discutere questi argomenti qui.

[mamilu]

**Valori e peso delle parole **

Fino ad ora abbiamo visto espressioni come (W n, J * W n, q) delle quali però ignoriamo che peso esse indichino esattamente.

Abbiamo visto che usando i pesi possiamo calcolare la somiglianza fra i vettori e quindi la prossimità dell'accoppiamento fra un vettore del documento e un vettore di domanda.

Confrontando il vettore di domanda a molti vettori di documento, possiamo allineare i documenti in base "alla qualità" dell'accoppiamento rapportata alla domanda.
Ma da cosa sono prodotti quei pesi e da dove provengono?

Le sezioni seguenti descrivono come sono** calcolati i pesi**.

Ci sono veramente parecchi tipi di pesi che devono essere calcolati!
Un insieme dei pesi che ovviamente abbiamo bisogno di conoscere, sono i pesi usati nel vettore di domanda.

Il vettore di domanda contiene tutti i termini utilizzabili indicizzati nel documento.
Il peso nel vettore di domanda riflette l'importantanza della parola chiave nel contesto dell'intero documento.

Quando la** N** è grande, questo insieme di pesi è abbastanza stabile.
Un nuovo documento può essere aggiunto all'insieme del documento senza cambiare significativamente il valore nel vettore di domanda.

Il secondo insieme dei pesi che ci serve è potenzialmente enorme.

Per ciascuno di N documenti dell'insieme di documenti, dobbiamo calcolare un peso per ogni termine indicizzato in quel documento.

Ogni documento ha un vettore del documento contenente il peso per ogni termine indicizzato presente nel documento.

Se abbiamo 1.000 documenti e 1.000 termini indicizzati, dovremo calcolare 1.000.000 di pesi.
Ogni volta che aggiungiamo un nuovo documento all'insieme dei documenti, dobbiamo calcolare un insieme dei pesi per le parole del nuovo documento.

Cos'è che rende una parola importante per una ricerca?

Può essere importante in due contesti: nella regolazione del documento originale e nel contesto dell'intera raccolta.

Una parola che compare in ogni documento, per esempio, non avrebbe valore nell'insieme del documento.
Per calcolare il peso di una parola chiave, ci occorre quindi un sistema per combinare l'importanza di una parola in un documento e misurare l'importanza di una parola nell'intero insieme del documento.

Una volta che abbiamo quei valori, possimo calcolare i pesi.

Questa tabella ci mostra come questi fattori combinano in generale i termini:

Importanza nel documentoImportanza insieme dei documenti** Peso**

Alto____________ Alto__________________ **Molto alto **
Basso____________ Alto__________________ Medio
Alto______________ Basso________________ Medio
Basso____________ Basso________________ Molto basso

Gli esperti del reperimento delle informazioni usano metodi differenti per calcolare i pesi del vettore del documento che per calcolare i pesi del vettore di domanda, ed hanno una varietà di tecniche di misurazione dell'importanza della parola nei vari differenti contesti.

In generale, per calcolare questi valori essi usano tecniche statistiche che comprendono l'analisi di frequenza della parola.

Guarderemo alle frequenze degli algoritmi e quindi infine vedremo come sono combinati nei pesi.

f i, j: Termine di frequenza normalizzato (tf) di ki in d j

la prima frequenza che esaminiamo è la frequenza di termine di una parola all'interno di un documento. Stiamo andando ad imparare come calcolare la frequenza normalizzata* ki* in d j

La normalizzazione è un processo matematico di adattamento o di confinamento in posizione ordinata.

Un conteggio approssimativo di frequenza è essenzialmente inutile.

In un documento molto grande, una parola rara può tranquillamente comparire anche 25 volte.

Un piccolo documento nello stesso insieme di documenti può anche non avere parole che compaiono 25 volte.

Come possiamo confrontare questi conteggi? Dobbiamo normalizzare il conteggio di frequenza, in modo che sia possibile misurare quanto è rara una parola relativamente al suo documento senza considerare la dimensione del documento stesso.

Un modo per farlo è comparare il numero di volte che una data parola compare (freq i , j) al numero di volte che la parola più presente compare nel testo (max (freq l, j)).

Questo è un modo per ridurre i risultati ed adattarli approssimativamente alla dimensione del testo.

Se li dividiamo, otteniamo una regolare gamma di valori, inferiore o uguale a uno.

Diamo un'occhiata alla formula:

Questo ci dimostra che la frequenza normalizzata per una data parola in un dato documento (f i , j) è uguale alla frequenza approssimativa della parola nel documento (freq i , j) diviso la frequenza approssimativa della parola più comune nel documento (max l freq l , j )

Vediamo nell'esempio seguente come si normalizzano con precisione i conteggi approssimativi di frequenza.

Come sempre, il freq i , j è il conteggio approssimativo di un dato termine *ki *in un dato documento d j. Quindi dovremo immaginare di computare il valore di freq i , j per tutti i termini nel *d j *e conosceremo così la parola più comune, max (freq i , j).

Quella sarà spesso la parola " il "; qui immaginiamo che sia presente 100 volte.

*word____________ freq i , j____ max (freq i , j)___ f i , j *

intercettazione______ 1_________ 100__________ .01

risoluzione_________ 10________ 100__________ 0.1

di________________ 50________ 100__________ 0.5

il________________ 100_______ 100___________ 1

Quindi, "** il** " appare 100 volte ed è la frase più popolare. Questo gli rende una frequenza normalizzata di 1,0.

La parola "risoluzione" compare dieci volte in questo documento, quindi la sua frequenza normalizzata è 10/100 o 0,1.
La parola "intercettazione" appare ma una volta sola ed ha una frequenza normalizzata di 0,01.

In generale, vediamo che le parole più comuni dovrebbero avere un'alta frequenza normalizzata e le parole più rare una più bassa frequenza normalizzata.

La legge di Zipf dice che ci saranno poche parole prossime ad uno e molte parole nell'allineamento più basso con un numero corretto nel mezzo, ma questo è un'altro argomento.

Per concludere, per una parola nell'insieme dei documenti ma non contenuta nel documento in esame,* f i , j* consideriamo uguale a zero, da freq i , j = 0 e quello è nel numeratore della frequenza normalizzata.

Possiamo quindi evincere che la frequenza normalizzata è:
una misura di frequenza che varia da zero a 1 per ogni termine in un documento.
Questa formula assegna un più alto valore alle parole che compaiono più spesso delle parole che compaiono di meno; in un certo senso, le parole più comuni sono più importanti o utili che le parole che appaiono soltanto una o due volte.

La prossima volta:
Frequenza inversa del documento

E' possibile discutere questi argomenti qui.

[mamilu]

19-02-06, 04:56

**Frequenza inversa del documento **

Ora dobbiamo far saltar fuori una misura di frequenza nel contesto dell'intero insieme del documento.

Possiamo definirla come "la frequenza inversa del documento" ed è data dalla formula IDF=log (N/ni). Che cosa significa e che cosa è quella formula nel suo insieme?

In primo luogo, consideriamo la parte "inversa".
A differenza dal caso di frequenza normalizzata all'interno di un documento, nel contesto dell'intero insieme di documento ci occorre che l'importanza di una parola scenda così come la frequenza della parola aumenta.

Quando la parola compare in ogni documento, ci occorre che questo valore sia zero.

Dopo tutto, se compare in ogni documento, è senza valore come differenziatore fra i documenti.

Quando la parola compare soltanto in alcuni documenti, desideriamo che questo abbia un alto valore.

Quindi, l'inverso:

• quantità elevata, valore basso;
• conteggio basso, alto valore.
  Questo è l'opposto della frequenza normalizzata.

Quindi, che valore possiamo dargli? Ricordiamo le definizioni:

N è il totale # dei documenti.

Ni è # dei documenti in cui il termine di ricerca di interesse (ki) compare.

Possiamo fare un rapporto di N diviso da Ni, (N/Ni) che esprimerà abbastanza chiaramente questo rapporto inverso.

Per vederlo, guardiamo questa tabella:

N_ ni___ N/ni___ Commento

1000___ 1___ 1000___ Conteggio basso, valore alto! Se la parola è presente una sola volta, il rapporto diviene molto alto. Hmm, se usiamo questo per determinare il peso diverrà troppo dominante.

1000___ 100___ 10___ Questo è un numero ragionevole, forse...

1000___ 500____ 2___ Conteggio alto, valore basso.

1000___ 1000___ 1___ Oops! Abbiamo detto che quando la parola appare in ogni documento, ci serve che il numero sia zero. Qui il nostro rapporto inverso è pari a uno. Questo è un problema.

Quindi siamo vicini, ma abbiamo alcuni problemi. Come risolvere i problemi con il nostro rapporto inverso? Useremo la funzione di logaritmo per normalizzare i valori.

Anziché N/ni, consideriamo log(N/ni):

N_ ni___ log(N/ni)___ Commento

1000___ 1_______ 3____ Bene, 3 sembra un buon numero da usare come fattore maggiorativo per una parola realmente rara.

1000___ 100_____ 2____ Mi piace anche questo 2

1000___ 500___ .301029996___ Se una parola appare in metà dei documenti, non è molto degna... hmmm, .3 suona bene.

1000___ 1000____ 0____ Bingo! Abbiamo detto che quando la parola compare in ogni documento, avremmo voluto il peso essere zero. Ecco, sta cominciando a funzionare!.

Così questo appare un buon IDF [ Inverse Document Frequencies ].

È zero quando la parola compare in tutti i documenti ed aumenta progressivamente così come il formato dei documenti diviene maggiore.

Usando un paragone per tuffatori, l'IDF è paragonabile "al grado della difficoltà" di un tuffo.

L'IDF di una parola chiave è costante attraverso un insieme dei documenti.

È soltanto necessario calcolarlo una volta per un dato insieme di documenti.

Il grado della difficoltà di un tuffo non cambia mentre i vari tuffatori lo fanno e l'IDF di un termine di ricerca non cambia mentre la parola chiave è usata nelle ricerche su documenti differenti.

Pesi

Ora, per concludere, possiamo calcolare i pesi!

Abbiamo già visto in anteprima come desideriamo si comportino i pesi.

Se aggiungiamo alcuni dati-campione vediamo che una moltiplicazione dei fattori funzionerà perfettamente nella generazione dei pesi:

Frequenza___ Frequenza_______Peso____ Esempio___ Esempio___ Esempio
Normalizzata__ Inversa del doc. _________ ___ nf_______ idf______ (nf * idf)

__ Alta________ Alta______ Molto alto___.9______ 1.2______ 1.08

Bassa_____ Alta_______ Medio_____ .2_______ .9_______ .18

Alta__ _ Bassa______ Medio___ _ .85_______ .04_____ 0.034

Bassa____ Bassa___ Molto basso_ _ .15_______ .09__ __ 0.0135

Come illustrato, poiché entrambi i termini sono stati normalizzati, possiamo moltiplicarli semplicemente insieme per ottenere un valore del peso che segue le regole generali nella tabella.

Questa in effetti è la formula consigliata per calcolare il peso dei documenti:

Questo ci dice che il peso per il ki in dj pari alla sua frequenza normalizzata (nf) di tempi della relativa frequenza inversa del documento (IDF). Puo essere applicato entrambi i pesi di documento.

Per usarla in un peso di domanda, la frequenza normalizzata dovrebbe essere calcolata sull'intero insieme di documento, non su di un singolo documento.

Il testo suggerisce un aumento nel calcolo del vettore di domanda:

Questo ci dice che il peso del termine i nel vettore di domanda q è pari alla frequenza normalizzata del termine di ricerca nel "testo della richiesta delle informazioni q".
Poiché questo sarebbe solitamente un numero basso, c'è un falso fattore di 0,5: la frequenza normalizzata ricalcolata ottiene un mezzo peso ed un valore libero "0,5" è aggiunto.
Ciò aumenterebbe il valore di una frase di ricerca che è stata inserita più di una volta.
Se ad esempio desiderassimo trovare "salto" potremmo cercare "salto salto salto" e questo aumenterebbe il valore di quella frase.
Ho miei dubbi circa l'efficacia del questo sistema come interfaccia utente.

Nel software di prova dell'Università [USA], è stata usata la frequenza normalizzata invariata di termine per il peso di vettore di domanda.

Conclusioni

Il Modello Vettoriale di Reperimento delle Informazioni è un potente strumento per la realizzazione del Motore di ricerca.

Questa discussione ha fornito un'introduzione ai concetti matematici richiesti per capire il Modello Vettoriale ed ha mostrato l'applicazione di quei concetti nello sviluppo del modello stesso.

vector model Information Retrieval

Theory of Information Retrieval, Florida State University LIS-5263 (Fall, 2003)
Written by Rich Ackerman, September 25. 2003
http://www.hray.com/

E' possibile discutere questi argomenti qui.

Concluso questo primo capitolo di studio, prima di passare alla realizzazione di un Semplice Motore di Ricerca valuteremo il:

**Salton's Vector Space Model **