Duas suposições são feitas ao usar DCG e suas medidas relacionadas.
- Documentos altamente relevantes são mais úteis quando aparecem mais cedo em uma lista de resultados de mecanismos de busca (têm classificações mais altas)
- Documentos altamente relevantes são mais úteis do que documentos marginalmente relevantes, que por sua vez são mais úteis do que documentos não relevantes.
DCG origina-se de uma medida anterior, mais primitiva, chamada Ganho Acumulado.
Ganho AcumuladoEditar
Ganho Acumulado (GC) é a soma dos valores de relevância graduada de todos os resultados em uma lista de resultados de pesquisa. Este predecessor do DCG não inclui a classificação (posição) de um resultado na lista de resultados na consideração da utilidade de um conjunto de resultados. O GC em uma posição de classificação particular p {\displaystyle p}
é definido como: C G p = ∑ i = 1 p r e l i {\\i} {CG_{p}} ==sum _{i=1}^{p}rel_{i}}
Where r e l i {\i}displaystyle rel_{\i}}
é a relevância graduada do resultado na posição i {\i}displaystyle i}
.
O valor calculado com a função CG não é afetado por alterações na ordenação dos resultados da busca. Ou seja, movendo um documento altamente relevante d i {\i} d_{i}{i}
acima de um documento d j {\i}displaystyle d_{j}} mais alto, menos relevante
não altera o valor computado para CG (assumindo i , j ≤ p {\displaystyle i,j\leq p}
). Com base nas duas suposições feitas acima sobre a utilidade dos resultados da busca, (N)DCG é geralmente preferido em relação a CG.
Ganho cumulativo é às vezes chamado de Graded Precision (Precisão Graduada), pois é idêntico ao Precision metric se a escala de classificação for binária.
Discounted Cumulative GainEdit (Ganho Cumulativo Descontado)
A premissa do DCG é que documentos altamente relevantes que aparecem mais abaixo em uma lista de resultados de pesquisa devem ser penalizados, pois o valor de relevância graduada é reduzido logaritmicamente proporcional à posição do resultado.
A fórmula tradicional do DCG acumulado em uma posição de classificação particular p {\displaystyle p}
é definido como: 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 ) {\\i1}displaystyle mathrm {DCG_{p}} =sum _{i=1}^{p}{\i}{\i}{\i}{\i}{\i1}{log _{\i}(i+1)}=rel_{1}+sum _{i=2}^{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{i+1}}}log _{i+1}
Anteriormente não havia nenhuma justificação teoricamente sólida para usar um factor de redução logarítmico a não ser o facto de que produz uma redução suave. Mas Wang et al. (2013) dão garantia teórica para o uso do fator de redução logarítmico no DCG Normalizado (NDCG). Os autores mostram que para cada par de funções de classificação substancialmente diferentes, o DCG-Normalizado pode decidir qual é melhor de forma consistente.
Uma formulação alternativa do DCG coloca maior ênfase na recuperação de documentos relevantes:
D C G p = ∑ i = 1 p 2 r e l i – 1 log 2 ( i + 1 ) {\i} {\i1}{\i+1} {\i+2}{\i}{\i}}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i}{\i1}{\i+1}}(i+1){\i}}}displaystyle {\i}mathrm
Esta última fórmula é comumente usada na indústria, incluindo as principais empresas de busca na web e plataformas de competição de ciência de dados como a Kaggle.
Estas duas formulações de DCG são as mesmas quando os valores de relevância dos documentos são binários;:320 r e l i ∈ {0 , 1 } {\i} {\i1}displaystyle rel_{\i}in {0,1}}
.
Nota que Croft et al. (2010) e Burges et al. (2005) apresentam o segundo DCG com um log de base e, enquanto ambas as versões do DCG acima usam um log de base 2. Ao calcular o DCG com a primeira formulação de DCG, a base do log não importa, mas a base do log afeta o valor do NDCG para a segunda formulação. Claramente, a base do log afeta o valor do DCG em ambas as formulações.
DCGEdit normalizado
As listas de resultados da pesquisa variam em comprimento dependendo da consulta. A comparação do desempenho de um motor de busca de uma consulta para a seguinte não pode ser conseguida de forma consistente usando apenas DCG, portanto o ganho cumulativo em cada posição para um valor escolhido de p {\displaystyle p}
deve ser normalizado através de consultas. Isto é feito ordenando todos os documentos relevantes no corpus pela sua relativa relevância, produzindo o máximo DCG possível através da posição p {\i1}displaystyle p
, também chamado DCG Ideal (IDCG) através dessa posição. Para uma consulta, o ganho acumulado com desconto normalizado, ou nDCG, é calculado como: n D C G p = D C G p I D C G p {\i1}displaystyle {nDCG_{p}} ={\i1}frac {DCG_{p}}{IDCG_{p}}}}
,
onde IDCG é o ganho acumulado com desconto ideal,
I D C G p = ∑ i = 1 | R E L p | 2 r e l i – 1 log 2 ( i + 1 ) {\i1}{\i1}displaystyle {\i1} =sum _{\i=1}^{\i_REL_{\i}}{\i}}{\i}{\i}{\i}{\i1}{\i1}log _{\i}(i+1)}
representa a lista de documentos relevantes (ordenados pela sua relevância) no corpus até à posição p.
Os valores nDCG para todas as consultas podem ser calculados como média para obter uma medida do desempenho médio do algoritmo de classificação de um motor de busca. Note que em um algoritmo de ranking perfeito, o DCG D C G p {\displaystyle DCG_{p}}
será o mesmo que o I D C G p {\i1}displaystyle IDCG_{p}}
produzindo um nDCG de 1,0. Todos os cálculos do nDCG são então valores relativos no intervalo de 0,0 a 1,0 e, portanto, são comparáveis entre si.
A principal dificuldade encontrada no uso do nDCG é a indisponibilidade de uma ordenação ideal dos resultados quando apenas o feedback de relevância parcial está disponível.