Zdyskontowany skumulowany zysk

przez

Przy stosowaniu DCG i miar z nim związanych przyjmuje się dwa założenia.

  1. Dokumenty o wysokiej trafności są bardziej użyteczne, gdy pojawiają się wcześniej na liście wyników wyszukiwarki (mają wyższą rangę)
  2. Dokumenty o wysokiej trafności są bardziej użyteczne niż dokumenty marginalnie istotne, które z kolei są bardziej użyteczne niż dokumenty nieistotne.

DCG wywodzi się z wcześniejszej, bardziej prymitywnej miary zwanej Zyskiem Skumulowanym.

Zysk SkumulowanyEdit

Zysk Skumulowany (CG) jest sumą stopniowanych wartości relewancji wszystkich wyników na liście wyników wyszukiwania. Ten poprzednik DCG nie uwzględnia rangi (pozycji) wyniku na liście wyników w rozważaniach na temat użyteczności zestawu wyników. CG na danej pozycji rangowej p {{displaystyle p}

p

definiuje się jako: C G p = ∑ i = 1 p r e l i {displaystyle {CG_{p}} =suma _{i=1}^{p}rel_{i}}

{mathrm {CG_{p}}}}=suma _{{i=1}}^{p}}rel_{{i}}

Gdzie r e l i {displaystyle rel_{i}}

rel_{{i}}

jest stopniowaną istotnością wyniku na pozycji i {{displaystyle rel_{i}}

i

.

Na wartość obliczoną za pomocą funkcji CG nie mają wpływu zmiany w kolejności wyników wyszukiwania. Oznacza to, że przesunięcie wysoce istotnego dokumentu d i {displaystyle d_{i}}

d_{i}

ponad wyżej sklasyfikowany, mniej istotny dokument d j {displaystyle d_{j}}

d_{j}}

nie zmienia obliczonej wartości dla CG (zakładając, że i , j ≤ p {displaystyle i,j ≤ p}

{displaystyle i,j}

). W oparciu o dwa powyższe założenia dotyczące użyteczności wyników wyszukiwania, (N)DCG jest zwykle preferowane w stosunku do CG.

Cumulative Gain jest czasami nazywany Graded Precision, ponieważ jest identyczny z metryką Precision, jeśli skala ocen jest binarna.

Discounted Cumulative GainEdit

Założeniem DCG jest to, że wysoko istotne dokumenty pojawiające się niżej na liście wyników wyszukiwania powinny być karane, ponieważ wartość graded relevance jest zmniejszana logarytmicznie proporcjonalnie do pozycji wyniku.

Tradycyjna formuła DCG kumuluje na danej pozycji rangi p { {}

p

definiuje się jako: 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

{displaystyle {DCG_{p}} ==suma _{i=1}^{p}{}frac {rel_{i}}{log _{2}(i+1)}}=rel_{1}+suma _{i=2}^{p}{}frac {rel_{i}}{log _{2}(i+1)}}

.

Poprzednio nie było teoretycznie uzasadnienia dla użycia logarytmicznego współczynnika redukcji poza tym, że daje on gładką redukcję. Jednak Wang et al. (2013) dają teoretyczną gwarancję na użycie logarytmicznego współczynnika redukcji w Normalized DCG (NDCG). Autorzy pokazują, że dla każdej pary istotnie różnych funkcji rankingowych, NDCG może zdecydować, która z nich jest lepsza w sposób spójny.

Alternatywne sformułowanie DCG kładzie silniejszy nacisk na odzyskiwanie istotnych dokumentów:

D C G p = ∑ i = 1 p 2 r e l i – 1 log 2 ( i + 1 ) {displaystyle {DCG_{p}} = suma _{i=1}^{p}{}frac {2^{rel_{i}}}-1}{ log _{2}(i+1)}}

{DCG_{{p}}}}==suma _{{i=1}}^{{p}}}{}frac {2^{rel_{{i}}}}-1}{}log _{2}}}(i+1)}}

Ta ostatnia formuła jest powszechnie stosowana w przemyśle, w tym w głównych firmach zajmujących się wyszukiwaniem stron internetowych i platformach konkursowych data science, takich jak Kaggle.

Te dwie formuły DCG są takie same, gdy wartości relewancji dokumentów są binarne;:320 r e l i ∈ { 0 , 1 } {{displaystyle rel_{i}}}}

rel_{{i}}} w \u00}

.

Normalized DCGEdit

Ta sekcja wymaga dodatkowych cytatów do weryfikacji. Prosimy o pomoc w ulepszeniu tego artykułu poprzez dodanie cytatów do wiarygodnych źródeł. Materiały niepochodzące z innych źródeł mogą zostać zakwestionowane i usunięte. (Luty 2020) (Learn how and when to remove this template message)

Listy wyników wyszukiwania różnią się długością w zależności od zapytania. Porównanie wydajności wyszukiwarki z jednego zapytania do następnego nie może być konsekwentnie osiągnięte przy użyciu samego DCG, więc skumulowany zysk na każdej pozycji dla wybranej wartości p {{displaystyle p}}

p

powinien być znormalizowany dla wszystkich zapytań. Dokonuje się tego poprzez posortowanie wszystkich istotnych dokumentów w korpusie według ich względnej istotności, uzyskując maksymalny możliwy DCG dla pozycji p {{displaystyle p}

p

, zwaną również idealną DCG (IDCG) dla tej pozycji. Dla zapytania, znormalizowany zdyskontowany skumulowany zysk, lub nDCG, jest obliczany jako: n D C G p = D C G p I D C G p {displaystyle {nDCG_{p}} ={frac {DCG_{p}}{IDCG_{p}}}}

{mathrm {nDCG_{p}}}}={frac {DCG_{p}}}{IDCG_{p}}}}

,

gdzie IDCG jest idealnym zdyskontowanym skumulowanym zyskiem,

I D C G p = ∑ i = 1 | R E L p | 2 r e l i – 1 log 2 ( i + 1 ) {{displaystyle {IDCG_{p}} = ∑ suma _{i=1}^{|REL_{p}}|}{}{}frac {2^{rel_{i}}}-1}{}log _{2}(i+1)}}.

{displaystyle {IDCG_{p}} = suma _{i=1}^{|REL_{p}}|}{}{frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}

i R E L p {displaystyle REL_{p}}

{displaystyle REL_{p}}

reprezentuje listę istotnych dokumentów (uporządkowanych według ich istotności) w korpusie do pozycji p.

Wartości nDCG dla wszystkich zapytań można uśrednić, aby uzyskać miarę średniej wydajności algorytmu rankingowego wyszukiwarki. Zauważmy, że w idealnym algorytmie rankingowym wartość D C G p {{displaystyle DCG_{p}}

DCG_p

będzie taka sama jak I D C G p {displaystyle IDCG_{p}}

IDCG_p

dając nDCG równe 1,0. Wszystkie obliczenia nDCG są więc wartościami względnymi w przedziale od 0,0 do 1,0, a więc są porównywalne między zapytaniami.

Główną trudnością napotkaną w użyciu nDCG jest niedostępność idealnego uporządkowania wyników, gdy dostępne jest tylko częściowe sprzężenie zwrotne relewancji.

Dodaj komentarz