Press "Enter" to skip to content

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

本文是《机器学习宝典》第 4 篇,读完本文你能够掌握机器学习中排序算法相关的评估指标。

 

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

 

生活中的排序问题

 

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

 

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

 

 

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

 

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

 

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] https://blog.csdn.net/simple_the_best/article/details/52296608?utm_source=blogxgwz2

 

[3] http://www.infoq.com/cn/articles/cyw-evaluate-seachengine-result-quality

Be First to Comment

发表回复

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