DCGによるスコア付きランキング出力結果の評価
2012-04-11-1
[Programming][Algorithm]
スコア付きランキング出力結果のDCG(Discounted Cumulative Gain)による評価についてのメモ。DCGは関連度の高い要素が上位にあればあるほど評価が高い、という考え方に基づく。
出力結果の順位iの要素はスコア(関連度Ri)を持っている。DCGの計算ではそれを用いる。
順位p(p位)までの結果に対するDCGp:
例:上位5位のそれぞれのスコアが「3,0,2,1,1」のときのDCGは:
■サンプルコード(dcg.pl):
■実行例(dcg.pl):
■ワンライナー:
このDCGを理想的な順位(スコアの降順の順位)のときのDCG(IDCG)で割って正規化したものがnDCG(Normalized Discounted Cumulative Gain):
■サンプルコード(ndcg.pl):
■実行例(ndcg.pl):
参考:
- http://en.wikipedia.org/wiki/Discounted_cumulative_gain
- http://www.r.dl.itc.u-tokyo.ac.jp/~nakagawa/SML1/eval1.pdf
出力結果の順位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
この記事に言及しているこのブログ内の記事