資訊檢索評估指標計算法說明 2005/11/24-2008/12/8
==========================
假設某次查詢q1,資料集60篇中應有10篇相關文章,
但系統傳回15篇文章中,只有5篇屬相關文章,
現列出排名由高到低的15篇文章,如下,其中,+表相關,-表不相關,
d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15
+, -, +, -, -, +, -, -, -, +, -, -, -, -, +
則就此次q1查詢,可計算如下各項評估指標,
機Y 機N .0 60 +1 59 -2 58 +3 57 -4 56 -5 55 +6 54 +15 45
------- ----- ---- ---- ---- ---- ---- ---- -----
人Y TP FN 0 10 1 9 1 9 2 8 2 8 2 8 3 7 5 5
人N FP TN 0 50 0 50 1 49 1 49 2 48 3 47 3 47 ... 10 40
a.一次查詢曲線結果
1.相關召回點準確率,P vs R, P@Rel
(註: P=TP/(TP+FP), R=TP/(TP+FN), FP=多進數, FN=少進數)
+ - + - - + - - - + - - - - +
R=0.1 0.1 0.2 0.2 0.2 0.3 0.3 0.3 0.3 0.4 0.4 0.4 0.4 0.4 0.5
P=1/1 1/2 2/3 2/4 2/5 3/6 3/7 3/8 3/9 0.4 0.3 0.3 0.3 0.2 0.3
2.標準11召回點準確率,P vs R (0%,10%,20%,...,100%), P@11Rel
(註:當標準召回點無值或多值時,可用內插法,採計召回點以上最高準確率)
R=0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
P=1 1/1 2/3 3/6 0.4 0.3 0 0 0 0 0
3.標準3召回點準確率,P vs R (20%,50%,80%), P@3Rel
(註:當標準召回點無值或多值時,可用內插法,採計召回點以上最高準確率)
R=0.2 0.5 0.8
P=2/3 0.3 0
4.不相關出現點召回率(ROC接收器工作特性曲線),TP_rate vs FP_rate, ROC
(註:相關正判率 TP_rate=TP/(TP+FN),不相關誤判率 FP_rate=FP/(FP+TN))
+ - + - - + - - - + - - - - +
FP_rate=0/50 1/50 1/50 2/50 3/50 3/50 4/50 5/50 6/50 6/50 7/50 8/50 9/50 10/50 10/50
TP_rate=1/10 1/10 2/10 2/10 2/10 3/10 3/10 3/10 3/10 4/10 4/10 4/10 4/10 4/10 5/10
5.判別點準確率(lift chart提昇圖),TP vs subset_size, lift_chart
(註: subset_size = (TP+FP)/(TP+FP+TN+FN))
+ - + - - + - - - + - - - - +
subset_size=1/60 2/60 3/60 4/60 5/60 6/60 7/60 8/60 9/60 10/60 11/60 12/60 13/60 14/60 15/60
P=1 1 2 2 2 3 3 3 3 4 4 4 4 4 5
b.一次查詢單值結果
6.準確率(P@ALL), P=TP/(TP+NP),NP=多進數,不應進而進
P@ALL = 5 / (5 + 10)
7.召回率(R@ALL), R=TP/(TP+FP)=TP_rate,FP=少進數,應進而未進
R@ALL = 5 / (5 + 5)
8.相關出現點平均準確率, AveP@Rel
AveP@Rel = (1/1 + 2/3 + 3/6 + 4/10 + 5/15) / 5
9.總相關數召回點準確率, R-value, R-precision, P@R-value
P@R-value = 4/10
10.最大召回準確率之調和平均數(F measure),F=2/(1/R+1/P), maxF
+ - + - - + - - - + - - - - +
R=0.1 0.1 0.2 0.2 0.2 0.3 0.3 0.3 0.3 0.4 0.4 0.4 0.4 0.4 0.5
P=1/1 1/2 2/3 2/4 2/5 3/6 3/7 3/8 3/9 0.4 0.3 0.3 0.3 0.2 0.3
F=0.18 0.16 0.3 0.28 0.26 0.37 0.35 0.33 0.31 0.4 0.38 0.36 0.34 0.33 0.4
maxF = 0.4
11.前10名準確率, P@10
P@10 = 4 / 10
12.前10名平均準確率, AveP@10,average precision)
AveP@10 = (1/1 + 1/2 + 2/3 + 2/4 + 2/5 + 3/6 + 3/7 + 3/8 + 3/9 + 4/10) / 10
13.成功率, (TP+TN) / (TP+FP+TN+FN), SUCCESS_RATE
SUCCESS_RATE = (5 + 40) / (5 + 10 + 40 + 5)
14.相關綜合判別率, TP_rate*(1-FP_rate) = TP*TN/(TP+FP)/(FP+TN)
Rel = 5 * 40 / (5+10) / (10 + 40)
假設有q1,q2,q3共計三次查詢,結果自資料集60篇文章中,
分別得到三次結果,如下,
應該傳回相關文章數(TP+FN),10,15,20,
實際傳回相關文章數(TP+FP),15,20,25,
其中,真正相關文章數(TP), 5, 2, 6,
詳情如下,
q1, +,-,+,-,-,+,-,-,-,+,-,-,-,-,+
q2, -,-,-,+,-,-,-,+,-,-,-,-,-,-,-,-,-,-,-,-
q3, -,+,-,-,+,-,+,-,-,-,+,-,-,-,+,-,-,-,-,-,+,-,-,-,-
機Y 機N q1 15 45 q2 20 40 q3 25 35
------- ----- ----- -----
人Y TP FN 5 5 2 13 6 14
人N FP TN 10 40 18 27 19 21
c.多次查詢曲線結果
15.召回點準確率平均圖,MP@Rel
仿照方法1,針對三次查詢,計算各召回點之準確率,再除以3,求平均
16.內插標準11召回點平均準確率, MP@11Rel
仿照方法2,針對三次查詢,計算11召回點之準確率,再除以3,求平均
17.無內插相關召回點平均準確率(依相關文章召回數及查詢數作平均)
q1_AveP@Rel = (1/1 + 2/3 + 3/6 + 4/10 + 5/15)/5
q2_AveP@Rel = (1/4 + 2/8)/2
q3_AveP@Rel = (1/2 + 2/5 + 3/7 + 4/11 + 5/10 + 6/16)/6
MAveP@Rel = (q1_AveP@Rel + q2_AveP@Rel + q3_AveP@Rel) / 3
18.特定相關數召回點平均準確率(前5,10,20,100相關文章召回點之查詢平均準確率)
q1_P@5R = 5/10
q2_P@5R = 無
q3_P@5R = 5/10
MP@5R = (q1_P@5R + q2_P@5R + q3_P@5R) / 3
19.總相關數召回點平均準確率(前5,10,20,100相關文章召回點之查詢平均準確率)
q1_P@R-value = 2/5
q2_P@R-value = 0/2
q3_P@R-value = 2/6
MP@5R = (q1_P@R-value + q2_P@R-value + q3_P@R-value) / 3
d.多次查詢單值結果
20.微觀平均準確率(micro average precision),依文章數作平均
map = (5 + 2 + 6) / (15 + 20 + 25)
21.巨觀平均準確率(macro average precision),依查詢數作平均
MAP = (5/15 + 2/20 + 6/25) / 3
22.前10名有正確之查詢比例 robust@10
q1前10名有正確文章=true
q1前10名有正確文章=true
q1前10名有正確文章=true
robust@10 = (1 + 1 + 1) / 3
23.總相關數召回點之查詢平均準確率, MP@R-value
q1總相關數召回點準確率=4/10
q2總相關數召回點準確率=2/10
q3總相關數召回點準確率=3/10
MP@R-value = (4/10 + 2/10 + 3/10) / 3
24.首相關排名之幾何平均數
q1首相關排名=1
q2首相關排名=4
q3首相關排名=2
幾何平均數=(1*4*2)^(1/3)
25.MAP(mean average precision),平均精確率平均
值介於0~1之間,越高越好,適用於二值相關度場合
MAP(Q) = 1/|Q| Sum_from_j=1_to_|Q| 1/m_j Sum_from_k=1_to_m_j Precision(R_jk)
Q:問題集, |Q|:問題數, m_j:問題j之應召回相關文件數,
R_jk: 問題j排名結果中,由前取到第k份相關文件出現為止的文件集
Precision(R_jk): 問題j第k份相關文件召回點之精確率
= 1/3 * [ 1/5 * (1/3 + 2/3 + 3/6 + 4/10 + 5/15)
+ 1/2 * (1/4 + 2/8)
+ 1/6 * (1/2 + 2/5 + 3/7 + 4/11 + 5/15 + 6/21)]
26.NDCG(normalized discounted cumulative gain),前k名累計打折正確率
值介於0~1之間,越高越好,適用於非二值相關度之機器學習場合
NDCG(Q,k)=1/|Q| Sum_from_j=1_to_|Q| Zk Sum_from_m=1_to_k [2^R(j,m) - 1]/log(1+m)
Q:問題集, |Q|:問題數,
Zk:正規化因子,讓NDCG在完美排名(前k份文件全相關)下,其值為1,
R(j,m): 問題j和文件m之相關度分數,介於0~1
若問題j回傳文件數k'小於指定的k,則NDCG(Q,k)就只累計到k'
例子: NDCG(Q,k=2)
= 1/3 * { Z2 * [(2^1-1)/log(1+1) + (2^0-1)/log(1+2)]
+ Z2 * [(2^0-1)/log(1+1) + (2^0-1)/log(1+2)]
+ Z2 * [(2^0-1)/log(1+1) + (2^1-1)/log(1+2)]}
with Z2 = (2^1-1)/log(1+1) + (2^1-1)/log(1+2)
e.多次查詢表格結果
25.查詢問題數,所有查詢傳回文章總數
查詢問題數=3
所有查詢傳回文章總數=60
26.所有查詢傳回相關文章總數,所有查詢實際相關文章總數
所有查詢傳回相關文章總數=15+20+25
所有查詢實際相關文章總數=5+2+6
參考文獻
1.baezayates-aw-99-modern information retrieval
2.witten-mkp-99-managing gigabytes
3.witten-mkp-00-data mining- practical machine learning tools and techniques
4.manning-cup-08-introduction to information retrieval
2008年12月8日 星期一
Evaluation Indices for Information Retrieval
訂閱：
張貼留言 (Atom)
沒有留言:
張貼留言