Algoritmo di Rocchio - Rocchio algorithm

L' algoritmo di Rocchio si basa su un metodo di feedback di rilevanza trovato nei sistemi di recupero delle informazioni che derivavano dal sistema di recupero delle informazioni SMART, sviluppato nel 1960-1964. Come molti altri sistemi di recupero, l'approccio di feedback di Rocchio è stato sviluppato utilizzando il Vector Space Model . L' algoritmo si basa sul presupposto che la maggior parte degli utenti abbia una concezione generale di quali documenti dovrebbero essere indicati come rilevanti o non rilevanti. Pertanto, la query di ricerca dell'utente è rivisto per includere una percentuale arbitraria dei documenti rilevanti e non rilevanti, come mezzo per aumentare il motore di ricerca s' di richiamo , e, eventualmente, la precisione pure. Il numero di documenti rilevanti e non rilevanti consentiti per inserire una query è dettato dai pesi delle variabili a, b, c elencate di seguito nella sezione Algoritmo .

Algoritmo

La formula e le definizioni delle variabili per il feedback sulla rilevanza di Rocchio sono le seguenti:

${\ displaystyle {\ overrightarrow {Q_ {m}}} = {\ bigl (} a \ cdot {\ overrightarrow {Q_ {o}}} {\ bigr)} + {\ biggl (} b \ cdot {\ tfrac { 1} {| D_ {r} |}} \ cdot \ sum _ {{\ overrightarrow {D_ {j}}} \ in D_ {r}} {\ overrightarrow {D_ {j}}} {\ biggr)} - {\ biggl (} c \ cdot {\ tfrac {1} {| D_ {nr} |}} \ cdot \ sum _ {{\ overrightarrow {D_ {k}}} \ in D_ {nr}} {\ overrightarrow { D_ {k}}} {\ biggr)}}$

Variabile	Valore
${\ displaystyle {\ overrightarrow {Q_ {m}}}}$	Vettore di query modificato
${\ displaystyle {\ overrightarrow {Q_ {o}}}}$	Vettore di query originale
${\ displaystyle {\ overrightarrow {D_ {j}}}}$	Vettore documento correlato
${\ displaystyle {\ overrightarrow {D_ {k}}}}$	Vettore di documento non correlato
${\ displaystyle a}$	Peso query originale
${\ displaystyle b}$	Documenti correlati Peso
${\ displaystyle c}$	Peso documenti non correlati
${\ displaystyle D_ {r}}$	Set di documenti correlati
${\ displaystyle D_ {nr}}$	Set di documenti non correlati

Come dimostrato nella formula, i pesi associati ( a , b , c ) sono responsabili della forma del vettore modificato in una direzione più vicina o più lontana dalla query originale, dai documenti correlati e dai documenti non correlati. In particolare, i valori di b e c devono essere incrementati o decrementati proporzionale al set di documenti classificati dall'utente. Se l'utente decide che la query modificata non deve contenere termini della query originale, documenti correlati o documenti non correlati, il valore del peso corrispondente ( a , b , c ) per la categoria deve essere impostato su 0.

Nella parte successiva dell'algoritmo, le variabili e vengono presentate come insiemi di vettori contenenti le coordinate di documenti correlati e documenti non correlati. Anche se e non sono vettori stessi, e sono i vettori usati per iterare attraverso i due insiemi e formare somme vettoriali . Queste somme vengono normalizzate (divise) per la dimensione del rispettivo set di documenti ( , ). ${\ displaystyle D_ {r}}$ ${\ displaystyle D_ {nr}}$ ${\ displaystyle D_ {r}}$ ${\ displaystyle D_ {nr}}$ ${\ displaystyle {\ overrightarrow {Dj}}}$ ${\ displaystyle {\ overrightarrow {Dk}}}$ ${\ displaystyle D_ {r}}$ ${\ displaystyle D_ {nr}}$

Per visualizzare le modifiche in atto sul vettore modificato, fare riferimento all'immagine sottostante. Man mano che i pesi vengono aumentati o diminuiti per una particolare categoria di documenti, le coordinate per il vettore modificato iniziano ad avvicinarsi o ad allontanarsi dal centroide della raccolta di documenti. Pertanto, se il peso viene aumentato per i documenti correlati, le coordinate dei vettori modificati rifletteranno l'essere più vicini al centroide dei documenti correlati.

Complessità temporale

Variabile	Valore
${\ displaystyle \ mathbb {D}}$	Set di documenti con etichetta
${\ displaystyle L_ {ave}}$	Token medi per documento
${\ displaystyle \ mathbb {C}}$	Set di classe
${\ displaystyle V}$	Vocabolario / Termine Set
${\ displaystyle L_ {a}}$	Numero di token nel documento
${\ displaystyle M_ {a}}$	Numero di tipi nel documento

La complessità temporale per l'addestramento e il test dell'algoritmo è elencata di seguito e seguita dalla definizione di ciascuna variabile . Si noti che in fase di test, la complessità temporale può essere ridotta a quella del calcolo della distanza euclidea tra un centroide di classe e il rispettivo documento. Come mostrato da: . ${\ displaystyle \ Theta (\ vert \ mathbb {C} \ vert M_ {a})}$

Formazione = Test = ${\ Displaystyle \ Theta (\ vert \ mathbb {D} \ vert L_ {ave} + \ vert \ mathbb {C} \ vert \ vert V \ vert)}$
${\ displaystyle \ Theta (L_ {a} + \ vert \ mathbb {C} \ vert M_ {a}) = \ Theta (\ vert \ mathbb {C} \ vert M_ {a})}$

Utilizzo

Classificazione Rocchio

Sebbene ci siano dei vantaggi nel classificare i documenti come non rilevanti, una classificazione dei documenti pertinenti si tradurrà in documenti più precisi resi disponibili per l'utente. Pertanto, i valori tradizionali pesi dell'algoritmo ( un , b , c ) in Rocchio classificazione sono tipicamente intorno a = 1 , b = 0,8 , e c = 0,1 . I moderni sistemi di recupero delle informazioni si sono mossi verso l'eliminazione dei documenti non correlati impostando c = 0 e quindi contabilizzando solo i documenti correlati. Sebbene non tutti i sistemi di recupero abbiano eliminato la necessità di documenti non correlati, la maggior parte ha limitato gli effetti sulla query modificata tenendo conto solo dei documenti non correlati più forti nel set Dnr .

Limitazioni

L'algoritmo di Rocchio spesso non riesce a classificare classi e relazioni multimodali. Ad esempio, il paese della Birmania è stato ribattezzato Myanmar nel 1989. Pertanto, le due query "Birmania" e "Myanmar" appariranno molto più distanti nel modello dello spazio vettoriale , sebbene entrambe contengano origini simili.

Guarda anche

Classificatore del centroide più vicino , noto anche come classificatore di Rocchio

Languages

In other projects