Två antaganden görs vid användning av DCG och dess relaterade mått.
- Högrelevanta dokument är mer användbara när de visas tidigare i en sökmotors resultatlista (har högre rankning)
- Högrelevanta dokument är mer användbara än marginellt relevanta dokument, som i sin tur är mer användbara än icke-relevanta dokument.
DCG har sitt ursprung i ett tidigare, mer primitivt mått som kallas Cumulative Gain.
Cumulative GainEdit
Cumulative Gain (CG) är summan av de graderade relevansvärdena för alla resultat i en sökresultatlista. Denna föregångare till DCG inkluderar inte rang (position) av ett resultat i resultatlistan i övervägandet av användbarheten av en resultatuppsättning. CG vid en viss rangposition p {\displaystyle p}
definieras som: C G p = ∑ i = 1 p r e l i {\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}
Var r e l i {\displaystyle rel_{i}}
är den graderade relevansen av resultatet på position i {\displaystyle i}
.
Värdet som beräknas med CG-funktionen påverkas inte av ändringar i sökresultatens ordningsföljd. Det innebär att om man flyttar ett mycket relevant dokument d i {\displaystyle d_{i}}
över ett högre rankat, mindre relevant, dokument d j {\displaystyle d_{j}}}
ändrar inte det beräknade värdet för CG (förutsatt att i , j ≤ p {\displaystyle i,j\leq p}
). På grundval av de två antaganden som gjorts ovan om sökresultatens användbarhet är (N)DCG vanligen att föredra framför CG.
Cumulative Gain kallas ibland Graded Precision eftersom det är identiskt med precisionsmåttet om betygsskalan är binär.
Discounted Cumulative GainEdit
Principen för DCG är att högrelevanta dokument som förekommer längre ner i en sökresultatlista bör bestraffas eftersom det graderade relevansvärdet minskas logaritmiskt proportionellt mot resultatets position.
Den traditionella formeln för DCG ackumuleras vid en viss rangposition p {\displaystyle p}
definieras 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)}}}
Förut fanns det ingen teoretiskt hållbar motivering för att använda en logaritmisk reduktionsfaktor annat än det faktum att den ger en jämn reduktion. Men Wang et al. (2013) ger en teoretisk garanti för att använda den logaritmiska reduktionsfaktorn i Normalized DCG (NDCG). Författarna visar att för varje par av väsentligt olika rangordningsfunktioner kan NDCG avgöra vilken som är bättre på ett konsekvent sätt.
En alternativ formulering av DCG lägger större vikt vid att hämta relevanta dokument:
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 sistnämnda formeln är vanligt förekommande inom industrin, bland annat hos stora sökföretag på webben och på plattformar för tävlingar om datavetenskap, som Kaggle.
Dessa två formuleringar av DCG är desamma när dokumentens relevansvärden är binära;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}\in \{0,1\}}
.
Notera att Croft et al. (2010) och Burges et al. (2005) presenterar den andra DCG med en log av bas e, medan båda versionerna av DCG ovan använder en log av bas 2. Vid beräkning av NDCG med den första formuleringen av DCG spelar logbasen ingen roll, men logbasen påverkar värdet av NDCG för den andra formuleringen. Det är uppenbart att logbasen påverkar värdet av DCG i båda formuleringarna.
Normaliserad DCGEdit
Sökresultatlistorna varierar i längd beroende på förfrågan. Att jämföra en sökmotors prestanda från en fråga till nästa kan inte konsekvent uppnås enbart med hjälp av DCG, så den kumulativa vinsten på varje position för ett valt värde på p {\displaystyle p}
bör normaliseras mellan olika sökningar. Detta görs genom att sortera alla relevanta dokument i korpusen efter deras relativa relevans, vilket ger högsta möjliga DCG genom positionen p {\displaystyle p}
, även kallad Ideal DCG (IDCG) genom den positionen. För en fråga beräknas den normaliserade diskonterade kumulativa vinsten, nDCG, på följande sätt: n D C G p = D C G p I D C G p {\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}}
,
där IDCG är idealisk diskonterad kumulativ vinst,
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)}}}}
och R E L p {\displaystyle REL_{p}}
representerar listan över relevanta dokument (ordnade efter relevans) i korpusen fram till position p.
Värdena för nDCG för alla sökfrågor kan räknas som ett medelvärde för att få ett mått på den genomsnittliga prestandan hos en sökmotors rankningsalgoritm. Observera att i en perfekt rankningsalgoritm är D C G p {\displaystyle DCG_{p}}
kommer att vara densamma som I D C G p {\displaystyle IDCG_{p}}
vilket ger en nDCG på 1,0. Alla nDCG-beräkningar är då relativa värden på intervallet 0,0-1,0 och är därmed jämförbara mellan olika sökningar.
Den största svårigheten med att använda nDCG är att det inte finns någon idealisk ordningsföljd för resultaten när endast en partiell relevansåterkoppling är tillgänglig.