衡量搜索引擎質(zhì)量指標(biāo)(DCG -- Discounted Cumulative Gain)

https://www.cnblogs.com/ywl925/archive/2012/11/21/2780861.html　　

DCG的英文全稱是Discounted cumulative gain，它是一個(gè)衡量搜索引擎算法的指標(biāo)。

　　搜索引擎一般采用PI（peritem）的方式進(jìn)行評(píng)測(cè)，簡(jiǎn)單地說就是逐條對(duì)搜索結(jié)果進(jìn)行分等級(jí)的打分。假設(shè)我們現(xiàn)在在Google上搜索一個(gè)詞，然后得到5個(gè)結(jié)果。我們對(duì)這些結(jié)果進(jìn)行3個(gè)等級(jí)的區(qū)分：Good（好）、Fair（一般）、Bad（差），然后賦予他們分值分別為3、2、1，假定通過逐條打分后，得到這5個(gè)結(jié)果的分值分別為3、2 、1 、3、 2。

　　接下來我們來看看是怎么計(jì)算DCG的　　使用DCG這個(gè)統(tǒng)計(jì)方法有兩個(gè)前提：

　　1.在搜索結(jié)果頁(yè)面，越相關(guān)的結(jié)果排在越前面越好

　　2.在PI標(biāo)注時(shí)，等級(jí)高的結(jié)果比等級(jí)低的結(jié)果好，即Good要比Fair好、Fair要比Bad好。

　　DCG這個(gè)概念是從Cumulative Gain這個(gè)概念發(fā)展起來的

　　什么叫Cumulative Gain（CG）

　　CG并不考慮在搜索結(jié)果頁(yè)面中結(jié)果的位置信息，它是在這個(gè)搜索結(jié)果list里面所有的結(jié)果的等級(jí)對(duì)應(yīng)的得分的總和。如一個(gè)搜索結(jié)果list頁(yè)面有P個(gè)結(jié)果，CG被定義為：

rel_i 是第i位結(jié)果的得分。CG的統(tǒng)計(jì)并不能影響到搜索結(jié)果的排序，CG得分高只能說明這個(gè)結(jié)果頁(yè)面總體的質(zhì)量比較高并不能說明這個(gè)算法做的排序好或差。什么是好的排序？也就是說要把Good的結(jié)果排到Fair結(jié)果上面、Fair結(jié)果排到Bad結(jié)果上面，如果有Bad的結(jié)果排在了Good上面，那當(dāng)然排序就不好了。到底排序好不好，需要一個(gè)指標(biāo)來衡量，DCG就是這樣的一個(gè)指標(biāo)。

　　上面的例子CG=3+2+1+3+2=11，如果調(diào)換第二個(gè)結(jié)果和第三個(gè)結(jié)果的位置CG=3+1+2+3+2=11，并沒有改變總體的得分。

Discounted Cumulative Gain

　　在一個(gè)搜索結(jié)果list里面，比如有兩個(gè)結(jié)果的打分都是Good，但是有一個(gè)是排在第1位，還有一個(gè)是排在第40位，雖然這兩個(gè)結(jié)果一樣都是Good，但是排在第40位的那個(gè)結(jié)果因?yàn)楸挥脩艨吹降母怕适潜容^小的，他對(duì)這整個(gè)搜索結(jié)果頁(yè)面的貢獻(xiàn)值是相對(duì)排在第一位那個(gè)結(jié)果來得小的。

　　DCG的思想是等級(jí)比較高的結(jié)果卻排到了比較后面，那么在統(tǒng)計(jì)分?jǐn)?shù)時(shí)，就應(yīng)該對(duì)這個(gè)結(jié)果的得分有所打折。一個(gè)有p（P≥2）個(gè)結(jié)果的搜索結(jié)果頁(yè)面的DCG定義為：　　

為什么要用以2為底的對(duì)數(shù)函數(shù)？這個(gè)并沒有明確的科學(xué)依據(jù)，大概是根據(jù)大量的用戶點(diǎn)擊與其所點(diǎn)寶貝的位置信息，模擬出一條衰減的曲線。

　　那么上例中的數(shù)字如下：　　

DCG=3+（1+1.26+1.5+0.86）=7.62

　　DCG的公式另外一種表達(dá)式是：　　

這個(gè)表達(dá)式在一些搜索文檔中經(jīng)常會(huì)被提到，他的作用和之前的那個(gè)公式一樣，但是這個(gè)公式只適合打分分兩檔的評(píng)測(cè)。

NDCG（Normalize DCG）　　

因?yàn)椴煌琿uery的搜索結(jié)果有多有少，所以不同query的DCG值就沒有辦法來做對(duì)比。

　　定義：　

IDCG（ideal DCG），就是理想的DCG。IDCG如何計(jì)算？首先要拿到搜索的結(jié)果，人工對(duì)這些結(jié)果進(jìn)行排序，排到最好的狀態(tài)后，算出這個(gè)排列下本query的DCG，就是IDCG。

　　因?yàn)閚DCG是一個(gè)相對(duì)比值，那么不同的query之間就可以通過比較nDCCG來決定哪個(gè)query的排序比較好。

　　例子中，理想的排序應(yīng)該是3 、3 、2 、2 、1，那么IDCG=3+3+1.26+1+0.43=8.69

　　nDCG=DCG/IDCG=7.62/8.69=0.88，從nDCG這個(gè)值可以看出目前算法存在的優(yōu)化空間。

引用：http://hi.baidu.com/jasonlyy/item/a195e9369e503dfe2684f455