Der er to antagelser ved brug af DCG og beslægtede mål.
- Højt relevante dokumenter er mere nyttige, når de vises tidligere i en søgemaskines resultatliste (har højere rang)
- Højt relevante dokumenter er mere nyttige end marginalt relevante dokumenter, som igen er mere nyttige end ikke-relevante dokumenter.
DCG stammer fra et tidligere, mere primitivt mål kaldet Cumulative Gain.
Cumulative GainRediger
Cumulative Gain (CG) er summen af de graduerede relevansværdier for alle resultater i en søgeresultatliste. Denne forgænger til DCG medtager ikke et resultats rang (position) i resultatlisten i overvejelserne om et resultatmængdes anvendelighed. CG på en bestemt rangposition p {\displaystyle p}
er defineret som: C G p = ∑ i = 1 p r e l i {\displaystyle \mathrm {CG_{p}}} =\sum _{i=1}^{p}rel_{i}}
Hvor r e l i {\displaystyle rel_{i}}}
er den graduerede relevans af resultatet på position i {\displaystyle i}
.
Værdien, der beregnes med CG-funktionen, er upåvirket af ændringer i rækkefølgen af søgeresultaterne. Det vil sige, at flytning af et meget relevant dokument d i {\displaystyle d_{i}}
over et højere rangeret, mindre relevant, dokument d j {\displaystyle d_{j}}}
ændrer ikke den beregnede værdi for CG (under forudsætning af i , j ≤ p {\displaystyle i,j\leq p}
). På grundlag af de to ovenstående antagelser om anvendeligheden af søgeresultaterne foretrækkes (N)DCG normalt frem for CG.
Cumulative Gain kaldes undertiden Graded Precision, da den er identisk med præcisionsmåleren, hvis vurderingsskalaen er binær.
Discounted Cumulative GainRediger
Forudsætningen for DCG er, at meget relevante dokumenter, der optræder lavere i en søgeresultatliste, bør straffes, da den graduerede relevansværdi reduceres logaritmisk proportionalt med resultatets placering.
Den traditionelle formel for DCG akkumulerede ved en bestemt rangposition p {\displaystyle p}
er defineret som: D C G p = ∑ i = 1 p r e l i log 2 ( i + 1 ) = r e l 1 + ∑ i = 2 p r e l i log 2 ( i + 1 ) {\displaystyle \mathrm {DCG_{p}}} =\sum _{i=1}^{p}{\frac {rel_{i}}}{\log _{2}(i+1)}}=rel_{1}+\sum _{i=2}^{p}{\frac {rel_{i}}}{\log _{2}(i+1)}}}
Der var tidligere ingen teoretisk forsvarlig begrundelse for at anvende en logaritmisk reduktionsfaktor ud over det faktum, at det giver en jævn reduktion. Men Wang et al. (2013) giver en teoretisk garanti for at bruge den logaritmiske reduktionsfaktor i Normalized DCG (NDCG). Forfatterne viser, at for hvert par af væsentligt forskellige rangordningsfunktioner kan NDCG beslutte, hvilken der er bedst på en konsistent måde.
En alternativ formulering af DCG lægger stærkere vægt på at hente relevante dokumenter:
D C G p = ∑ i = 1 p 2 r e l i – 1 log 2 ( i + 1 ) {\displaystyle \mathrm {DCG_{p}} =\sum _{i=1}^{p}}{\frac {2^{{rel_{i}}}-1}{\log _{2}(i+1)}}}
Den sidstnævnte formel er almindeligt anvendt i industrien, herunder store web-søgningsvirksomheder og datavidenskabelige konkurrenceplatforme som Kaggle.
Disse to formuleringer af DCG er de samme, når dokumenternes relevansværdier er binære;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}\in \{0,1\}}
.
Bemærk, at Croft et al. (2010) og Burges et al. (2005) præsenterer den anden DCG med en log i base e, mens begge versioner af DCG ovenfor anvender en log i base 2. Ved beregning af NDCG med den første formulering af DCG er logbogens base ligegyldig, men logbogens base har betydning for værdien af NDCG for den anden formulering. Det er klart, at logbogens base påvirker værdien af DCG i begge formuleringer.
Normaliseret DCGEdit
Søgeresultatlister varierer i længde afhængigt af forespørgslen. En sammenligning af en søgemaskines præstationer fra den ene forespørgsel til den anden kan ikke konsekvent opnås ved hjælp af DCG alene, så den kumulative gevinst på hver position for en valgt værdi af p {\displaystyle p}
bør normaliseres på tværs af forespørgsler. Dette gøres ved at sortere alle relevante dokumenter i korpus efter deres relative relevans, hvilket giver den størst mulige DCG gennem position p {\displaystyle p}
, også kaldet ideel DCG (IDCG) gennem denne position. For en forespørgsel beregnes den normaliserede diskonterede kumulative gevinst, nDCG, som: n D C G p = D C G p I D C G p {\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}}{IDCG_{p}}}}
,
hvor IDCG er den ideelle diskonterede kumulative gevinst,
I D C G p = ∑ i = 1 | R E L p | 2 r e l i – 1 log 2 ( i + 1 ) {\displaystyle \mathrm {IDCG_{p}}} =\sum _{i=1}^{|REL_{p}|}{\frac {2^{rel_{i}}}-1}{\log _{2}(i+1)}}}}
og R E L p {\displaystyle REL_{p}}}
repræsenterer listen over relevante dokumenter (ordnet efter deres relevans) i korpus indtil position p.
Den gennemsnitlige nDCG-værdi for alle forespørgsler kan beregnes for at få et mål for den gennemsnitlige ydelse af en søgemaskines rangordningsalgoritme. Bemærk, at i en perfekt rangordningsalgoritme vil D C G p {\displaystyle DCG_{p}}
vil være den samme som I D C G p {\displaystyle IDCG_{p}}
, hvilket giver en nDCG på 1,0. Alle nDCG-beregninger er derefter relative værdier på intervallet 0,0 til 1,0 og er således sammenlignelige på tværs af forespørgsler.
Den største vanskelighed ved anvendelse af nDCG er, at der ikke findes en ideel rækkefølge af resultater, når der kun foreligger delvis relevansfeedback.