Se fac două presupuneri în utilizarea DCG și a măsurilor aferente.
- Documentele extrem de relevante sunt mai utile atunci când apar mai devreme în lista de rezultate a unui motor de căutare (au ranguri mai mari)
- Documentele extrem de relevante sunt mai utile decât documentele marginal relevante, care la rândul lor sunt mai utile decât documentele nerelevante.
DCG își are originea într-o măsură anterioară, mai primitivă, numită Câștig cumulativ.
Câștig cumulativEdit
Câștigul cumulativ (CG) este suma valorilor de relevanță gradată ale tuturor rezultatelor dintr-o listă de rezultate de căutare. Acest predecesor al DCG nu include rangul (poziția) unui rezultat în lista de rezultate în luarea în considerare a utilității unui set de rezultate. CG la o anumită poziție de rang p {\displaystyle p}
se definește astfel: C G p = ∑ i = 1 p r e l i {\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}.
Unde r e l i {\displaystyle rel_{i}}
este relevanța gradată a rezultatului de la poziția i {\displaystyle i}
.
Valoarea calculată cu ajutorul funcției CG nu este afectată de modificările în ordinea rezultatelor căutării. Altfel spus, mutarea unui document foarte relevant d i {\displaystyle d_{i}}
deasupra unui document mai bine clasat, mai puțin relevant, d j {\displaystyle d_{j}}
nu modifică valoarea calculată pentru CG (presupunând că i , j ≤ p {\displaystyle i,j\leq p}
). Pe baza celor două ipoteze formulate mai sus cu privire la utilitatea rezultatelor căutării, (N)DCG este de obicei preferată față de CG.
Cumulative Gain se numește uneori Graded Precision deoarece este identică cu metrica Precision în cazul în care scara de evaluare este binară.
Discounted Cumulative GainEdit
Primăria DCG este că documentele foarte relevante care apar mai jos în lista de rezultate ale unei căutări ar trebui să fie penalizate, deoarece valoarea relevanței gradate este redusă în mod logaritmic proporțional cu poziția rezultatului.
Formula tradițională a DCG a acumulat la o anumită poziție de rang p {\displaystyle p}
se definește astfel: 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)}}}}
Până acum nu exista o justificare teoretică solidă pentru utilizarea unui factor de reducere logaritmic, în afară de faptul că produce o reducere lină. Dar Wang et al. (2013) oferă o garanție teoretică pentru utilizarea factorului de reducere logaritmic în DCG normalizat (NDCG). Autorii arată că, pentru fiecare pereche de funcții de clasificare substanțial diferite, NDCG poate decide care dintre ele este mai bună într-un mod consecvent.
O formulare alternativă a DCG pune un accent mai mare pe recuperarea documentelor relevante:
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)}}}}.
Aceasta din urmă formulă este folosită în mod obișnuit în industrie, inclusiv în marile companii de căutare pe internet și în platformele de concursuri de știință a datelor, cum ar fi Kaggle.
Aceste două formulări ale DCG sunt identice atunci când valorile de relevanță ale documentelor sunt binare;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}\in \{0,1\}}
.
Rețineți că Croft et al. (2010) și Burges et al. (2005) prezintă al doilea DCG cu un logaritm de bază e, în timp ce ambele versiuni ale DCG de mai sus utilizează un logaritm de bază 2. La calcularea NDCG cu prima formulare a DCG, baza logaritmului nu contează, dar baza logaritmului afectează valoarea NDCG pentru cea de-a doua formulare. În mod clar, baza logaritmului afectează valoarea DCG în ambele formulări.
Normalized DCGEdit
Listele de rezultate ale căutării variază în lungime în funcție de interogare. Compararea performanțelor unui motor de căutare de la o interogare la alta nu poate fi realizată în mod consecvent folosind doar DCG, astfel încât câștigul cumulat la fiecare poziție pentru o valoare aleasă a lui p {\displaystyle p}
ar trebui să fie normalizat între interogări. Acest lucru se face prin sortarea tuturor documentelor relevante din corpus în funcție de relevanța lor relativă, producând DCG maxim posibil prin poziția p {\displaystyle p}
, numită și DCG ideală (IDCG) prin poziția respectivă. Pentru o interogare, câștigul cumulativ actualizat normalizat, sau nDCG, se calculează astfel: n D C G p = D C G p I D C G p {\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}}{IDCG_{p}}}}
,
unde IDCG este câștigul cumulativ ideal actualizat,
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)}}}}
și R E L p {\displaystyle REL_{p}}
reprezintă lista documentelor relevante (ordonate în funcție de relevanța lor) din corpus până la poziția p.
Valorile nDCG pentru toate interogările pot fi mediate pentru a obține o măsură a performanței medii a algoritmului de clasificare al unui motor de căutare. Rețineți că, într-un algoritm de clasificare perfect, D C G p {\displaystyle DCG_{p}}
va fi același cu cel al I D C G p {\displaystyle IDCG_{p}}.
producând un nDCG de 1,0. Toate calculele nDCG sunt apoi valori relative pe intervalul 0,0 – 1,0 și, prin urmare, sunt comparabile prin interogare încrucișată.
Principala dificultate întâlnită în utilizarea nDCG este indisponibilitatea unei ordonări ideale a rezultatelor atunci când este disponibil doar un feedback de relevanță parțială.
.