NDCG和AUC算法评价指标介绍

机器学习

#1

一、NDCG

  • 1.DCG

     首先,介绍一下DCG。DCG的全称是Discounted Cumulative Gain,它是衡量搜索引擎算法的一个指标。搜索引擎一般采用PI(per item)的方式进行评测,即逐条对搜索结果进行等级的打分。比如在Google搜索到一个词,得到5个结果。我们对这些结果进行3个等级的区分:Good、Fair、Bad,对应的分值分别是3、2、1。假设这5个结果的分值分别是3、1、2、3、2。
     使用DCG这个统计方法有两个前提:
     (1) 在搜索页面中,相关度越高的结果排在前面越好。
     (2) 在PI标注时,等级高的结果比等级低的结果好。
    

在一个搜索结果的list里面,假设有两个结果的评级都是Good,但是第一个排在第一位,第二个排在第40位,虽然等级是一样的,但排在40位的那个结果被用户看到的概率比较小,对整个页面的贡献也要比第一个结果小很多。所以第二个结果的得分应该有所减少。DCG的计算公式如下: image

其中,就是第 i 个结果的得分。

    1. NDCG

      因为不同的搜索结果的数量很可能不相等,所以不同搜索的DCG值不能直接做对比。解决的方法是比较NDCG。NDCG的定义如下: image IDCG(Ideal DCG),即理想的DCG。举上面的例子来说,5个搜索结果的分值是3、1、2、3、2,那么DCG = 3 + (1+1.26+1.5+0.86 )=7.62。 而IDCG下的分值排列顺序是3、3、2、2、1,所以IDCG=3 + (3+1.26+1+0.43)=8.69。 所以,NDCG = DCG / IDCG = 0.88。

二、AUC

    1. ROC曲线 ROC分析的是二元分类模型,即输出结果只有两种类别的模型。ROC空间将伪阳性率(FPR,False Position Rate)定为X轴,真阳性率(TPR,True Position Rate)定为Y轴。 TPR = TP / ( TP + FN),表示在所有实际为阳性的样本中,被正确判断为阳性的比例。(TP:真阳性,FN:伪阴性) FPR = FP / ( FP + TN),表示在所有实际为阴性的样本中,被正确判断为阴性的比例。(TN:真阴性,FP:伪阳性)

对于包含100个阳性和100个阴性的样本,以下是4个分类器的结果:

其中,ACC表示准确率。可以把这四个分类器映射成ROC空间中的一个点,如下图所示: 可以发现两个规律:(1) 越靠近左上角的点,准确率越高。(2) 如果点位于(0,0)和(1,1)的连线下方,那么一个有效的补救方法是把所有预测结果反向(即,如果输出结果为正类,则最终判定为负类;如果输出结果为负类,则判定为正类)。 在同一个分类器内,设置不同的阈值则会产生不同的坐标,这些坐标连成的曲线叫做ROC曲线。 当阈值被设定为最高时,所有的样本都被预测为阴性,所以FP=0,TP=0,此时的FPR = FP / (FP+TN)=0,TPR = TP / (TP+FN) =0。这是坐标为(0,0)。 当阈值被设定为最低时,所有样本都被预测为阳性,同理可得:FPR=1,TPR=1,坐标为(1,1)。所以ROC曲线经过了(0,0)和(1,1)。

    1. AUC ROC曲线示例如下: image 为了比较分类器的好坏,就将每个曲线下的面积作为比较,面积越大,则分类器效果越好。其中,这个面积就叫做AUC,全称是Area Under the roc Curve(ROC曲线下面积)。

#2

DCG = 3 + (1+1.26+1.5+0.86 )=7.62,IDCG下的分值排列顺序是3、3、2、2、1,所以IDCG=3 + (3+1.26+1+0.43)=8.69。这个是怎么变换的,没看懂。