Elaborazione della somiglianza tra due elenchi

Question

MODIFICA: poiché tutti si confondono, voglio semplificare la mia domanda. Ho due liste ordinate. Ora, voglio solo calcolare quanto sia simile una lista all'altra.

Ad esempio,

1,7,4,5,8,9 
1,7,5,4,9,6 

cosa è una buona misura di somiglianza tra queste due liste in modo che l'ordine è importante. Ad esempio, dovremmo penalizzare la similarità in quanto 4,5 è scambiato nelle due liste?

Ho 2 sistemi. Un sistema all'avanguardia e un sistema che ho implementato. Data una query, entrambi i sistemi restituiscono un elenco di documenti classificati. Ora, voglio confrontare la somiglianza tra il mio sistema e il "sistema stato dell'arte" per misurare la correttezza del mio sistema. Si noti che l'ordine dei documenti è importante in quanto stiamo parlando di un sistema classificato. Qualcuno sa di qualsiasi misura che possa aiutarmi a trovare la somiglianza tra queste due liste.

Answer 1

Il DCG [Guadagno cumulativo scontato] e nDCG [DCG normalizzato] sono in genere una buona misura per le liste classificate.

Fornisce il guadagno completo per il documento pertinente se è classificato per primo, e il guadagno diminuisce man mano che la classifica diminuisce.

Utilizzando DCG/nDCG valutare il sistema rispetto alla linea di base SOA:

Nota: se si imposta tutti i risultati restituiti da "stato del sistema dell'arte" come rilevanti, allora il sistema è identico allo stato dell'arte se hanno ricevuto lo stesso grado utilizzando DCG/nDCG.

Così, una possibile valutazione potrebbe essere: DCG(your_system)/DCG(state_of_the_art_system)

Per migliorare ulteriormente, si può dare una rilevanza grado [rilevanza non sarà binario] - e sarà determinato in base al modo in cui ogni documento è stato classificato in lo stato dell'arte. Ad esempio rel_i = 1/log(1+i) per ogni documento nel sistema all'avanguardia.

Se il valore ricevuto da questa funzione di valutazione è vicino a 1: il sistema è molto simile alla linea di base.

Esempio:

mySystem = [1,2,5,4,6,7] 
stateOfTheArt = [1,2,4,5,6,9] 

In primo luogo vi darà punteggio per ogni documento, a seconda dello stato del sistema dell'arte [utilizzando la formula dall'alto]:

doc1 = 1.0 
doc2 = 0.6309297535714574 
doc3 = 0.0 
doc4 = 0.5 
doc5 = 0.43067655807339306 
doc6 = 0.38685280723454163 
doc7 = 0 
doc8 = 0 
doc9 = 0.3562071871080222 

Ora si calcola DCG(stateOfTheArt), e utilizzare la pertinenza come indicato sopra [nota la pertinenza non è binario qui, e ottenere DCG(stateOfTheArt)= 2.1100933062283396
Avanti, cal culate per il sistema utilizzando gli stessi pesi relecance e ottenere: DCG(mySystem) = 1.9784040064803783

Pertanto, la valutazione è DCG(mySystem)/DCG(stateOfTheArt) = 1.9784040064803783/2.1100933062283396 = 0.9375907693942939

Answer 2

Suppongo che si sta parlando di confronto tra due Information Retrieval sistema che fido di me non è una cosa banale. È un problema complesso di informatica.

Per misurare la pertinenza o fare tipo di test A/B è necessario avere paio di cose:

1. Un concorrente per misurare la pertinenza. Poiché si dispone di due sistemi, questo requisito viene soddisfatto.

2. È necessario valutare manualmente i risultati. Puoi chiedere ai tuoi colleghi di valutare le coppie di query/url per le query più comuni e poi per i buchi (es. Query/url pair non valutato puoi avere qualche funzione di ranking dinamico usando l'algoritmo "Apprendimento a classifica" http://en.wikipedia.org/wiki/Learning_to_rank. Non essere sorpreso da questo, ma cosa vera (si prega di leggere qui di seguito di un esempio di Google/Bing).

Google e Bing sono concorrenti nel mercato della ricerca orizzontale. Questi motori di ricerca impiegano giudici manuali in tutto il mondo e investono milioni su di loro, per votare i risultati per le query. Quindi per ogni query/coppie di url generalmente vengono valutati i primi 3 o i primi 5 risultati. Sulla base di queste valutazioni possono utilizzare una metrica come NDCG (guadagno cumulativo scontato normalizzato), che è uno dei migliori e quello di il più popolare.

Secondo Wikipedia:

scontato crescita cumulata (DCG) è una misura di efficacia di un algoritmo del motore di ricerca sul Web o applicazioni correlate, spesso usato nel recupero delle informazioni. Utilizzando una scala graduata di rilevanza dei documenti in un set di risultati di un motore di ricerca, DCG misura l'utilità o il guadagno di un documento in base alla sua posizione nell'elenco dei risultati. Il guadagno viene accumulato dalla cima della lista dei risultati alla fine con il guadagno di ogni risultato scontato ai ranghi più bassi.

Wikipedia spiega NDCG in maniera eccezionale. È un breve articolo, per favore passa attraverso quello.

Answer 3

L'elenco dei documenti è esauriente? Cioè, ogni rank di documento ordinato dal sistema 1 è classificato anche dal sistema 2? Se è così, a Spearman's rho può servire ai tuoi scopi. Quando non condividono gli stessi documenti, la grande domanda è come interpretare quel risultato. Non penso ci sia una misurazione che risponda a questa domanda, anche se potrebbero esserci alcuni che implementano una risposta implicita ad essa.

Answer 4

Come hai detto, vuoi calcolare quanto un elenco simile sia all'altro. Penso in modo semplicistico, puoi iniziare contando il numero di Inversioni.C'è un approccio O (NlogN) per dividere e conquistare questo. È un approccio molto semplice per misurare la "somiglianza" tra due liste.

ad es. vuoi confrontare il modo in cui 'simili' i gusti musicali sono per due persone su un sito di musica, prendi il loro ranking di un insieme di canzoni e conta il no. di inversioni in esso. Minore il conteggio, più 'simile' è il loro gusto.

poiché si sta già considerando il "sistema all'avanguardia" come un punto di riferimento della correttezza, il conteggio delle inversioni dovrebbe fornire una misura di base della "somiglianza" della propria classifica. Naturalmente questo è solo un approccio antipasti, ma si può costruire su di essa come modo rigoroso si desidera essere con la "inversione di gap", ecc

D1 D2 D3 D4 D5 D6 
    ----------------- 
R1: 1, 7, 4, 5, 8, 9 [Rankings from 'state of the art' system] 
R2: 1, 7, 5, 4, 9, 6 [ your Rankings] 

Dal classifiche sono in ordine di documenti che è possibile scrivere il proprio funzionale comparatore basato su R1 (ranking dello "stato del sistema dell'arte" e quindi conta le inversioni confronto a quella comparatore

È possibile "penalizzare" 'somiglianza' per ogni inversioni trovati:. i < j ma R2 [ i]> 'R2 [j]
(>' qui tu utilizzare il proprio confronto)

Link si possono trovare utili:
Link1
Link2
Link3

Answer 5

Kendalls tau è la metrica che si desidera. Misura il numero di inversioni a coppie nella lista. La regola del piede di Spearman fa lo stesso, ma misura la distanza piuttosto che l'inversione. Sono entrambi progettati per il compito in corso, misurando la differenza in due elenchi ordinati in ordine di priorità.

Answer 6

In realtà conosco quattro diverse misure a tale scopo.

Tre sono già stati menzionati:

• NDCG
• Tau di Kendall
• di Spearman Rho

Ma se si dispone di più di due gradi che devono da confrontare, utilizzare K endall W.

Answer 7

Oltre a quanto già detto, desidero indicarvi il seguente eccellente documento: W. Webber et al, A Similarity Measure for Indefinite Rankings (2010). Oltre a contenere una buona revisione delle misure esistenti (come Kendall Tau e Spearman's footrule di cui sopra), gli autori propongono una misura probabilistica intuitivamente attraente che è applicabile per la lunghezza variabile delle liste di risultati e quando non tutti gli elementi si verificano in entrambi gli elenchi. In parole povere, è parametrizzato da una probabilità di "persistenza" p che un utente esegue la scansione dell'oggetto k + 1 dopo aver ispezionato l'oggetto k (piuttosto che abbandonare). Sovrapposizione di posizionamento parziale (RBO) è il rapporto di sovrapposizione previsto dei risultati nel punto in cui l'utente interrompe la lettura.

L'implementazione di RBO è leggermente più coinvolta; puoi dare un'occhiata a un'implementazione in Apache Pig here.

Un'altra semplice misura è somiglianza coseno, il coseno tra due vettori con dimensioni corrispondenti a elementi e ranghi inversi come pesi. Tuttavia, non gestisce gli elementi con garbo che si verificano solo in uno degli elenchi (vedere l'implementazione nel link sopra).

1. Per ogni articolo nella lista 1, lasciare h_1 (i) = 1/rank_1 (i). Per ogni elemento nella lista 2 non presente nella lista 1, lasciare h_1 (i) = 0. Fare lo stesso per h_2 rispetto all'elenco 2.
2. Calcolo v12 = sum_i h_1 (i) * h_2 (i); v11 = sum_i h_1 (i) * h_1 (i); V22 = sum_i H_2 (i) * H_2 (i)
3. V12 Ritorno/sqrt (V11 * V22)

Per esempio, questo dà un valore di ,7252,747 mila.

Per favore lascia che ti dia qualche consiglio pratico oltre la tua domanda immediata. A meno che la linea di base del "sistema di produzione" sia perfetta (o si tratti di un set di oro), è quasi sempre meglio confrontare una misura di qualità (come l'nDCG sopra menzionato) piuttosto che la somiglianza; una nuova classifica sarà talvolta migliore, a volte peggiore della linea di base, e vorrete sapere se il primo caso si verifica più spesso del secondo. In secondo luogo, le misure di similarità non sono banali da interpretare su una scala assoluta. Ad esempio, se ottieni un punteggio di similarità di 0,72, significa che è davvero simile o significativamente diverso? Le misure di similarità sono più utili nel dire che per es. un nuovo metodo di classificazione 1 è più vicino alla produzione di un altro nuovo metodo di classificazione 2.