たつをの ChangeLog : 2012-04-11

スコア付きランキング出力結果のDCG(Discounted Cumulative Gain)による評価についてのメモ。DCGは関連度の高い要素が上位にあればあるほど評価が高い、という考え方に基づく。

出力結果の順位iの要素はスコア（関連度Ri）を持っている。DCGの計算ではそれを用いる。

順位p（p位）までの結果に対するDCGp：


例：上位5位のそれぞれのスコアが「3,0,2,1,1」のときのDCGは：


■サンプルコード(dcg.pl)：

#!/usr/bin/perl
use strict;
use warnings;

my @r = (3,0,2,1,1);

my $cum = $r[0];
for (my $i = 1; $i < @r; $i++) {
    $cum += $r[$i] / (log($i+1)/log(2));
}
print "$cum\n";

■実行例(dcg.pl)：

% ./dcg.pl
5.19253606521631

■ワンライナー：

perl -nle '$c+=$.>1?$_*log(2)/log$.:$_;print"DCG$. $c"'

% cat a.txt 
3
0
2
1
1
% perl -nle '$c+=$.>1?$_*log(2)/log$.:$_;print"DCG$. $c"' a.txt
DCG1 3
DCG2 3
DCG3 4.26185950714291
DCG4 4.76185950714291
DCG5 5.19253606521631

このDCGを理想的な順位（スコアの降順の順位）のときのDCG(IDCG)で割って正規化したものがnDCG(Normalized Discounted Cumulative Gain)：


■サンプルコード(ndcg.pl)：

#!/usr/bin/perl
use strict;
use warnings;

my @r = (3,0,2,1,1);

my $dcg = dcg(@r);
my $idcg = dcg(sort {$b <=> $a} @r);
my $ndcg = $dcg / $idcg;
print "$dcg / $idcg = $ndcg\n";

sub dcg {
    my @r = @_;
    my $cum = $r[0];
    for (my $i = 1; $i < @r; $i++) {
        $cum += $r[$i] / (log($i+1)/log(2));
    }
    return $cum;
}

■実行例(ndcg.pl)：

% ./ndcg.pl
5.19253606521631 / 6.13092975357146 = 0.846941047104885

参考：
- http://en.wikipedia.org/wiki/Discounted_cumulative_gain
- http://www.r.dl.itc.u-tokyo.ac.jp/~nakagawa/SML1/eval1.pdf