KwCheng's blog

NDCG (normalize discount cumulative gain)

一般在衡量一個retrieve的方法是否好不好時,通常會去判斷其 P-R curve,

即計算每個relevance level的average precision,

但在判斷時面對此document是否relevance時,

通常只以 0 (不相關)或 1 (相關)來進行判斷. (binary degree relevance assessment)

但是有些document並非完全不相關,而可能是有些許相關,

而只以 0 或 1 這樣的方法並無法有效的衡量出一些retrieve方法的相異性.

而有些方法雖然利用到了 multiple degree relevance assessment ,但確無法有效發揮.

因此Kalervo就提出 CG及 DCG的方法,而這方法判斷一個retrieve 方法的好壞,

架構在兩個概念上,即:

1.高相關的document會比低相關的document來的有價值.

2.同樣相關等級的document,排名較前面的會比排名較後面的來得有價值.

在point 1,用CG (cumulated gain)即可進行判斷,

將query所得到的document list以relevance進行評分,

即3-highly relevance,2-fairly relevance,1-marginally relevance,0-rest of the database.

再將其document list依其score進行累加,即得此query的CG評分.

但是如果將同樣為3 level的document,一個排在rank 1,而另一個排在rank 10,

那rank 10的評分應該要比較低才公平,所以我們改用DCG (discount cumulated gain),

將每個分數除上他所在的rank取log.

而在衡量兩個retrieval system的performance時 , 我們並不可能只用一個query來進行衡量 , 

可是每個query所得的list長度又不同 , 這樣一來 , 每個query所計算出來DCG並不具同樣標準 , 

因為長的query,其DCG一定會比短的query高 , 

所以我們需對DCG進行normalize,即將DCG除上IDCG (ideal discount cumulated gain),

此時所得即為NDCG.

PS:IDCG即將document list依其理想狀況進行排列,再計算其DCG而得.

reference : http://en.wikipedia.org/wiki/Discounted_cumulative_gain