NDCG指标的理解与优缺点

[dbthinking]

NDCG 指标简介

NDCG，Normalized Discounted Cumulative Gain，直译为归一化折损累计增益，是用来衡量排序质量的指标。

数据示例：

i	reli	log2(i+1)	reli/log2(i+1)
1	3	1	3
2	2	1.58	1.26
3	3	2	1.5
4	0	2.32	0
5	1	2.58	0.38
6	2	2.8	0.71

• 注释：
  • i 是展示顺序
  • reli 是主观评分
  • log2(i+1) 是折损强度
  • reli/(log2(i+1)) 是折损增益

NDCG 相关名词

• CG
  • cumulative gain 累计增益
  • 单个搜索词的多条结果打分的累计值
• DCG
  • Normalized Discounted cumulative gain 折损累计增益
  • 考虑其位置的折损：reli / log2(i+1) ；i为排在第几位
  • 折损就是考虑了其排序位置的影响
  • 折损有不同的的计算方法(折损程度)
• IDCG
  • Ideal Discounted cumulative gain 理想(topN)情况下最大DCG值
  • 也就是topN的理想排序（分值由高到低）
• NDCG
  • Normalized Discounted cumulative gain 归一化折损累计增益
  • NDCG = DCG/iDCG
  • 注意只取topN或all的NDCG区别

NDCG 优缺点分析

• CG 与 DCG 都是跟测评标准结合比较紧密的量化指标
  • CG不考虑位置情况，不能评价排序的情况
  • DCG则在一定程度上综合考虑了排序与召回
  • 测评条数与测评标准的分档都会影响两个数值
  • 数据同比例放大后，CG、DCG会随之同比例放大
• NDCG 很大程度上摆脱了测评标准的影响，可横向对比
  • 数据同比例放大后，NDCG值不会变
  • 标准层次越多，结论可信度就越高
• NDCG 不适合衡量寻址类搜索的情况
  • 寻址类搜索：
    • 有明确的已预知的唯一答案
    • 搜索官网、搜索某网站某内容
  • 衡量寻址搜索可使用MRR指标
• NDCG 适合衡量信息补充类的搜索情况
  • 无明确的唯一预期，搜寻参考信息
• NDCG 在意 TOPN 排序，而无法衡量整体召回
  • 或者说，NDCG的前提是召回已做到了极致
  • 比如前五条打分是11000，NDCG是满分

实践问题

• 理解各种指标在表达什么，根据搜索场景寻找合适的评价指标。
• 在固定标准与固定条目的情况下，DCG能很好的衡量召回与排序。
• 在常规的搜索中，前3条大致贡献80%的搜索流量，前5大约90%。
• NDCG的优势：
  • 极大降低了评分标准与条数的影响；
  • 输出0-1区间内的量化结果；
  • 指标能够横向对比。
• NDCG的劣势：
  • 理论上来看，NDCG忽略了召回情况，更多是评价排序；
  • 比如会出现 11000 的NDCG值，比 13210 要高很多；
  • 一般在计算topN的NDCG值时，实际测评条数可以大于N；
    • N值之外的结果提高了IDCG的值，相对更在意召回；
    • N值之外的结果越多，越是考虑了全局情况。
  • 但依然可能存在更好的结果未被召回未被测评的情况。
• 新指标 MNDCG：
  • MNDCG = DCG / MIDCG
  • 在计算IDCG时，改为计算MIDCG，考虑理想情况下的最大DCG；
  • 每个条目都取标注标准的最大值，MIDCG是固定的最大值。
  • 优点：
    • 综合考虑了召回与排序，结果也能量化到0-1区间。
    • 得分值能更明确的对比出 召回+排序 的综合表现。
  • 缺点：
    • 由于假设存在理想的最大MIDCG数值；
    • 也就是假设每个query都存在一堆好答案；
    • 类似DCG，不适合评价寻址类搜索；
    • 不适合评价客观上缺乏合适召回的搜索。
    • 高分比较难得到，低分比较容易；
    • 高分段中，MNDCG与NDCG的评价差别大不；
    • 低分段中，NDCG更在意对已知项目的排序。

NDCG 计算公式

#!/usr/bin/env python3
# encoding: utf-8
"""
NDCG
"""
import math


def get_ndcg(lst, topn):
    """python calculate ndcg"""

    # ndcg@n 关心前n个排序是否正确，后面的排序不予考虑。
    dcg_lst = list(lst)[:topn]
    idcg_lst = list(sorted(lst, reverse=True))[:topn]

    # 初始序列是0，故 i + 2
    # idcg为理想情况下最大的DCG值
    dcg = sum(j / math.log2(i + 2) for i, j in enumerate(dcg_lst))
    idcg = sum(j / math.log2(i + 2) for i, j in enumerate(idcg_lst))

    ndcg = dcg / idcg

    return dcg, idcg, ndcg


if __name__ == "__main__":
    print(get_ndcg([3, 2, 3, 0, 1, 2, 3, 0], 6))
    print(get_ndcg([3, 2, 3, 0, 1, 2], 6))
    print(get_ndcg([6, 4, 6, 0, 2, 4, 6, 0], 6))
    print(get_ndcg([6, 4, 6, 0, 2, 4], 6))

• output(dcg, idcg, ndcg):
  • (6.861126688593502, 8.384055178438263, 0.8183541904922859)
  • (6.861126688593502, 7.1409951840957, 0.9608081943360617)
  • (13.722253377187004, 16.768110356876527, 0.8183541904922859)
  • (13.722253377187004, 14.2819903681914, 0.9608081943360617)

MNDCG 计算公式

#!/usr/bin/env python3
# encoding: utf-8
"""
MNDCG
"""
import math


def get_map(lst, maxi):
    """python calculate ndcg"""

    # 标注区间要映射为从0到1，maxi是最高标准，mini应该是0
    nlst = [i / maxi for i in lst]
    nmap = sum(nlst) / len(nlst)

    nlst = sorted(lst, reverse=True)
    dcg = sum(j / math.log2(i + 2) for i, j in enumerate(lst))
    idcg = sum(j / math.log2(i + 2) for i, j in enumerate(nlst))
    maxdcg = sum(5 / math.log2(i + 2) for i, j in enumerate(nlst))
    ndcg = dcg / idcg
    mndcg = dcg / maxdcg

    # 此处是想计算nmap与ndcg的f1值，作为参考
    f1value = 2 * (nmap * ndcg) / (nmap + ndcg)

    return nmap, ndcg, f1value, mndcg


if __name__ == "__main__":
    print(get_map([0, 5, 5, 5, 5], 5))
    print(get_map([5, 5, 0, 5, 5], 5))
    print(get_map([5, 5, 5, 5, 0], 5))
    print(get_map([5, 5, 0, 0, 5], 5))
    print(get_map([5, 0, 0, 5, 5], 5))
    print(get_map([5, 0, 0, 0, 5], 5))
    print("----")
    print(get_map([1, 2, 0, 0, 0], 5))
    print(get_map([1, 5, 0, 0, 0], 5))
    print(get_map([2, 1, 0, 0, 0], 5))
    print(get_map([5, 3, 0, 5, 0], 5))

• output(nmap, ndcg, f1value, mndcg):

  • (0.8, 0.7606395682357036, 0.7798234351785439, 0.6608397947263839)
  • (0.8, 0.9558295932317544, 0.870999870981756, 0.8304198973631919)
  • (0.8, 1.0, 0.888888888888889, 0.8687949224876582)
  • (0.6, 0.9469024295259745, 0.7345537079409504, 0.6843515475204854)
  • (0.6, 0.8529278650606568, 0.7044489012054694, 0.6164336326286644)
  • (0.4, 0.8503449055347546, 0.5440706171685159, 0.47036528278595796)

  ---

  • (0.12000000000000002, 0.8597186998521972, 0.21060380698628617, 0.15342654694853425)
  • (0.24, 0.737826424707602, 0.362187679644219, 0.28181830578925077)
  • (0.12000000000000002, 1.0, 0.2142857142857143, 0.17846133505635198)
  • (0.52, 0.936975779087716, 0.6688201850969538, 0.6136203139570392)

• 数据分析：

  • 在具体的ndcg得分上：
    • 12000高于15000，0.8597 > 0.7378；
    • 21000高于53050, 1.0 > 0.9370。
  • 在具体的mndcg得分上：
    • 12000低于15000，0.1534 < 0.2818；
    • 21000低于53050, 0.1784 < 0.6136。
  • 在无明确预期的情况下，mndcg分值更接近用户感受；
  • NDCG假设的是，已经把所有相关召回考虑到测评里；
  • 假如存在未被测评到的相关内容，NDCG无法评价；
  • 在以上逻辑下，NDCG分值，10002高于10005的含义是：
    • 区分更明显的条目还排到了后面，性质更恶劣
  • 在以上逻辑下，NDCG分值，21000高于53050的含义是：
    • 是否严格倒排比数值更重要

参考文章

• Discounted cumulative gain by wikipeida
• 搜索评价指标——NDCG - 胖喵~ - 博客园
• 如何量化评价搜索引擎的结果质量- 知乎