古い記事
ランダムジャンプ
新しい記事
スコア付きランキング出力結果の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