Como comparar dois algoritmos de classificação?

12

Eu quero comparar dois algoritmos de classificação. Nesses algoritmos, o cliente especifica algumas condições em sua pesquisa. De acordo com os requisitos do cliente, esse algoritmo deve atribuir uma pontuação para cada item da base de dados e recuperar itens com a pontuação mais alta.

Eu li diferentes tópicos relacionados à minha pergunta neste site e procurei na net. De acordo com minhas pesquisas, o artigo mais relevante que explica algumas métricas para comparar algoritmos de classificação foi o seguinte: Brian McFee e Gert RG Lanckriet, Metric Learning to Rank, ICML 2010 ( https://bmcfee.github.io/papers/mlr .pdf ). Acho que prec @ k, MAP, MRR e NDCG são boas métricas para usar, mas tenho um problema:

Meu algoritmo classifica os resultados; portanto, o primeiro item da minha lista de resultados é o melhor com a pontuação mais alta, o segundo resultado tem a segunda pontuação máxima e assim por diante. Limito meu algoritmo de pesquisa a, por exemplo, para encontrar 5 melhores resultados. Os resultados são os 5 principais itens. Portanto, a precisão será 1. Quando limito minha pesquisa para encontrar o melhor resultado, ele encontra o melhor. Novamente, a precisão será 1.Mas o problema é que, é inaceitável para quem vê esse resultado.

O que eu posso fazer? Como posso comparar esses algoritmos e mostrar que um é melhor que o outro?

6

O ganho cumulativo com desconto (DCG) é uma das métricas mais populares usadas para avaliação de classificação por qualquer mecanismo de pesquisa. É uma medida da qualidade do ranking. Na recuperação de informações, é frequentemente usado para medir a eficácia do mecanismo de pesquisa na web.

É baseado nas seguintes suposições:

Documentos altamente relevantes são mais úteis se aparecerem mais cedo em um resultado de pesquisa.
Documentos altamente relevantes são mais úteis do que documentos marginalmente relevantes, melhores do que documentos não relevantes.

A fórmula para o DCG é a seguinte:

\begin{matrix} (1) & D C G_{p} = \sum_{i = 1}^{p} \frac{r e l_{i}}{l o g_{2} (i + 1)} = r e l_{1} + \sum_{i = 2}^{p} \frac{r e l_{i}}{l o g_{2} (i + 1)} \end{matrix}

$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)} \tag{1}$

Onde:

i é a posição retornada de um documento no resultado da pesquisa.
$rel_i$ é a relevância classificada do documento
soma sobre p (número de resultados retornados), portanto, o ganho acumulado acumulado fornece as métricas de desempenho do resultado retornado.

O DCG é derivado do GC (Ganho Cumulativo) , dado por:

\begin{matrix} (2) & C G_{p} = \sum_{i = 1}^{p} r e l_{i} \end{matrix}

$CG_p = \sum_{i=1}^p rel_i \tag{2}$

De (2) pode-se ver que não muda para uma alteração na ordem dos resultados. Assim, para superar esse problema, o DCG foi introduzido. Existe uma forma diferente de DCG, popular por colocar uma ênfase muito alta na recuperação dos documentos. Esta versão do DCG é fornecida por: $CG_p$

\begin{matrix} (3) & D C G_{p} = \sum_{i = 1}^{p} \frac{2^{r e l_{i}} - 1}{l o g_{2} (i + 1)} \end{matrix}

$DCG_p = \sum_{i=1}^p \frac {2^{rel_i} - 1} {log_2 (i+1)} \tag{3}$

Uma desvantagem óbvia da equação do DCG apresentada em (1) e (3) é que os algoritmos que retornam um número diferente de resultados não podem ser comparados efetivamente. Isso ocorre porque quanto maior o valor de maior o valor de será dimensionado para. $p$ $DCG_p$

Para superar esse problema, é proposto o DCG normalizado (nDCG) . É dado por,

n D C G_{p} = \frac{D C G_{p}}{I D C G_{p}}

$nDCG_p = \frac {DCG_p} {IDCG_p}$

onde é o ideal , fornecido por, $IDCG_p$ $DCG_p$

I D C G_{p} = \sum_{i = 1}^{| R E L |} \frac{2^{r e l_{i}} - 1}{l o g_{2} (i + 1)}

$IDCG_p = \sum_{i=1}^{|REL|} \frac {2^{rel_i} - 1} {log_2 (i+1)}$

Onde | REL | é a lista de documentos ordenados por relevância no corpus até a posição p.

Para um algoritmo de classificação perfeito,

D C G_{p} = I D C G_{p}

$DCG_p = IDCG_p$

Como os valores de nDCG são dimensionados dentro do intervalo [0,1], a comparação entre consultas é possível usando essas métricas.

Desvantagens: 1. O nDCG não penaliza a recuperação de documentos incorretos no resultado. Isso pode ser corrigido ajustando os valores de relevância atribuídos aos documentos. 2. O nDCG não penaliza os documentos ausentes. Isso pode ser corrigido fixando o tamanho da recuperação e usando a pontuação mínima para os documentos ausentes.

Consulte isso para ver exemplos de cálculos de nDCG.

Referência

m1cro1ce
fonte

0

Recursos úteis:

http://www.cs.utexas.edu/~mooney/ir-course/slides/Evaluation.ppt
http://www.nii.ac.jp/TechReports/05-014E.pdf
http://www.stanford.edu/class/cs276/handouts/EvaluationNew-handout-6-per.pdf
http://hal.archives-ouvertes.fr/docs/00/72/67/60/PDF/07-busa-fekete.pdf
Aprendendo a classificar para recuperação de informações (Tie-Yan Liu)

Renaud
fonte

Como comparar dois algoritmos de classificação?

Respostas: