机器学习与你生活密切相关的排序算法的评估指标

读完本文你能够掌握机器学习中排序算法相关的评估指标。

更多:机器学习

读完分类与回归算法的评估指标之后,你已经知道了机器学习中分类与回归算法的评估指标。在这篇给大家介绍一些机器学习中排序算法相关的评估指标。

生活中的排序问题

直接说排序这个名词很多人可能觉得很陌生,但实际上它与你的生活密切相关。这里我们以搜索功能来说明下。

比如你想学习机器学习,但是不知道如何入门,但是你想到有谷歌爸爸,所以就在谷歌中输入了关键词:机器学习入门,接下来你就看到了一个结果页,结果页里包含了一大堆与入门机器学习相关的链接。

可以看到,每个链接对应的内容不一样,位置也分前后,对于你来说,你当然是希望前几个链接的内容就能解决你的问题,这样你就不用花时间去查看靠后的链接,甚至不用去翻页,也就是说你希望越靠前的位置的内容与你搜索的关键词越相关。

换个角度来想,你所看到的这么多链接其实就是一个模型产生的排序列表,这个列表里的每个元素就是一个链接。这里的链接用行话来说就是“文档” 。那么,如何衡量这个排序列表的好坏呢?也就是说每个文档到底排在第几位才是比较合适的呢?接下来我们来看几个衡量排序质量的评估指标。

MAP

MAP(Mean Average Precision,平均准确率均值)计算时分为两部分,第一部分是计算一次查询后的排序结果的平均准确率(AP),第二部分是计算总体的平均准确率均值(MAP)。一般评估MAP时会限定要评估的排序结果个数,也就是会指定要选取的前K个文档。

其中,AP@K表示计算前K个结果的平均准确率,M表示每次排序的文档总数,P(k)表示前k个结果的准确率,

rel(k)表示第k个结果是否是相关文档,相关取值为1,不相关取值为0。

上面得到的就是一次查询的平均准确率,接下来对多次查询的AP求出均值即可得到MAP。

其中,Q表示查询的次数,

表示第q次查询的AP@K的结果。

MRR

MAP没有考虑位置的影响,这里介绍一个新的评估指标:MRR(Mean Reciprocal Rank,平均排序倒数)计算时先求出每一个查询的第一个相关文档位置的倒数,然后将所有倒数值求平均。

假如说有三次查询,每次查询的前5条结果的相关性如下:

query1query2query3
010
100
001
100

其中,0表示文档不相关,1表示文档相关。

可以看到,第一次查询中第一个相关文档的顺序是2,第二次查询中第一个相关文档的顺序是1,第三次查询中第一个相关文档的顺序是3,那么

NDCG

NDCG(Normalized Discounted Cumulative Gain,归一化折损累积增益)是另一个衡量排序质量的评估指标。MAP衡量相关性时只考虑两种情况:1和0,而NDCG可以将相关性分为更多的等级,正式介绍NDCG之前,先来介绍下CG(Cummulative Gain,累积增益)。

其中,CG@K表示计算前K个结果的累计增益,

表示第k个位置的文档的相关性得分。

CG的一个缺点是没有考虑不同位置的影响,我们总是希望相关性高的结果排在前面,如果相关性高的结果排在后面,我们应该进行惩罚,所以引入了DCG(Discounted Cummulative Gain,折扣累积增益),也就是对排名靠后的结果进行“打折处理”。

其中,分子表示相关性越高,DCG越大,分母表示位置越靠后,DCG越小。

虽然DCG考虑了位置的影响,但是DCG也会受到结果数量的影响,为了使得具有可比性,需要对DCG进行归一化处理,这样就得到了NDCG。

其中,

表示前k个排序返回结果集能得到的最佳排序结果,即当越相关的文档排放的位置越靠前时计算得到DCG即为IDCG。

练习题

看完这篇文章,我们来做几道练习题来检验下学习成果:

1. 假定我进行了两次查询,得到的结果如下(1表示相关,0表示不相关),求MAP@5。

query1query2
10
01
10
01
10

2. 假定相关性等级为3级(0-2),模型对4个文档的排序结果如下,求NDCG@4。

文档模型排序相关性最佳排序
d2112
d3213
d1321
d4404

参考:

[1] 美团算法团队.美团机器学习实战.第一章第一节(评估指标)
[2] http://www.infoq.com/cn/articles/cyw-evaluate-seachengine-result-quality
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

《机器学习与你生活密切相关的排序算法的评估指标》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注