Bei der Verwendung von DCG und verwandten Maßen werden zwei Annahmen getroffen.
- Hoch relevante Dokumente sind nützlicher, wenn sie früher in der Ergebnisliste einer Suchmaschine erscheinen (einen höheren Rang haben)
- Hoch relevante Dokumente sind nützlicher als marginal relevante Dokumente, die wiederum nützlicher sind als nicht relevante Dokumente.
DCG geht auf ein früheres, primitiveres Maß namens Cumulative Gain zurück.
Cumulative GainEdit
Cumulative Gain (CG) ist die Summe der abgestuften Relevanzwerte aller Ergebnisse in einer Suchergebnisliste. Dieser Vorgänger von DCG bezieht den Rang (Position) eines Ergebnisses in der Ergebnisliste nicht in die Betrachtung der Nützlichkeit einer Ergebnismenge ein. Der CG an einer bestimmten Rangposition p {\displaystyle p}
ist definiert als: C G p = ∑ i = 1 p r e l i {\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}
Wo r e l i {\displaystyle rel_{i}}
die abgestufte Relevanz des Ergebnisses an Position i {\displaystyle i} ist
.
Der mit der CG-Funktion berechnete Wert bleibt von Änderungen in der Reihenfolge der Suchergebnisse unberührt. Das heißt, die Verschiebung eines hoch relevanten Dokuments d i {\displaystyle d_{i}}
über ein höherrangiges, weniger relevantes Dokument d j {\displaystyle d_{j}}
ändert den berechneten Wert für CG nicht (vorausgesetzt i , j ≤ p {\displaystyle i,j\leq p}
). Auf der Grundlage der beiden oben gemachten Annahmen über die Nützlichkeit von Suchergebnissen wird (N)DCG in der Regel gegenüber CG bevorzugt.
Cumulative Gain wird manchmal als Graded Precision bezeichnet, da es mit der Precision-Metrik identisch ist, wenn die Bewertungsskala binär ist.
Discounted Cumulative GainEdit
Die Prämisse von DCG ist, dass hochrelevante Dokumente, die in einer Suchergebnisliste weiter unten erscheinen, bestraft werden sollten, da der abgestufte Relevanzwert logarithmisch proportional zur Position des Ergebnisses reduziert wird.
Die traditionelle Formel der DCG kumuliert an einer bestimmten Rangposition p {\displaystyle p}
ist definiert als: 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)}}
Früher gab es keine theoretisch fundierte Begründung für die Verwendung eines logarithmischen Reduktionsfaktors, außer der Tatsache, dass er eine glatte Reduktion bewirkt. Wang et al. (2013) geben jedoch eine theoretische Garantie für die Verwendung des logarithmischen Reduktionsfaktors in der Normalized DCG (NDCG). Die Autoren zeigen, dass die NDCG für jedes Paar wesentlich unterschiedlicher Ranking-Funktionen auf konsistente Weise entscheiden kann, welche davon besser ist.
Eine alternative Formulierung der DCG legt den Schwerpunkt stärker auf das Auffinden relevanter Dokumente:
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)}}
Die letztgenannte Formel wird häufig in der Industrie verwendet, einschließlich großer Websuchunternehmen und Data-Science-Wettbewerbsplattformen wie Kaggle.
Diese beiden Formulierungen der DCG sind gleich, wenn die Relevanzwerte der Dokumente binär sind;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}\in \{0,1\}}
.
Beachte, dass Croft et al. (2010) und Burges et al. (2005) die zweite DCG mit einem Logarithmus zur Basis e darstellen, während beide Versionen der obigen DCG einen Logarithmus zur Basis 2 verwenden. Bei der Berechnung der NDCG mit der ersten Formulierung der DCG spielt die Basis des Logarithmus keine Rolle, aber die Basis des Logarithmus beeinflusst den Wert der NDCG für die zweite Formulierung. Es ist klar, dass die Basis des Logarithmus den Wert der DCG in beiden Formulierungen beeinflusst.
Normalized DCGEdit
Suchergebnislisten sind je nach Abfrage unterschiedlich lang. Ein Vergleich der Leistung einer Suchmaschine von einer Abfrage zur nächsten ist mit DCG allein nicht konsistent möglich, so dass der kumulative Gewinn an jeder Position für einen gewählten Wert von p {\displaystyle p}
über Abfragen hinweg normalisiert werden sollte. Dies geschieht, indem alle relevanten Dokumente im Korpus nach ihrer relativen Relevanz sortiert werden, was den maximal möglichen DCG durch die Position p {\displaystyle p}
, auch ideale DCG (IDCG) genannt, durch diese Position. Für eine Abfrage wird der normalisierte diskontierte kumulative Gewinn oder nDCG wie folgt berechnet: n D C G p = D C G p I D C G p {\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}}
,
wobei IDCG der ideale diskontierte kumulative Gewinn ist,
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)}}
und R E L p {\displaystyle REL_{p}}
stellt die Liste der relevanten Dokumente (geordnet nach ihrer Relevanz) im Korpus bis zur Position p dar.
Die nDCG-Werte für alle Abfragen können gemittelt werden, um ein Maß für die durchschnittliche Leistung des Ranking-Algorithmus einer Suchmaschine zu erhalten. Man beachte, dass bei einem perfekten Ranking-Algorithmus die D C G p {\displaystyle DCG_{p}}
gleich dem I D C G p {\displaystyle IDCG_{p}}
, was eine nDCG von 1,0 ergibt. Alle nDCG-Berechnungen sind dann relative Werte auf dem Intervall 0,0 bis 1,0 und damit abfrageübergreifend vergleichbar.
Die Hauptschwierigkeit bei der Verwendung der nDCG besteht darin, dass es keine ideale Reihenfolge der Ergebnisse gibt, wenn nur ein teilweises Relevanz-Feedback verfügbar ist.