NDCG（@R）指标 – 小飞侠

Notes

检索中常用几种评价指标：

NDCG（Normalized Discounted Cumulative Gains）相比 mAP 的一个特点是支持多值的相似性（multi-level similarity），而 mAP 只是二值的：相似或不相似。这种特性在涉及 multi-label 数据的检索时显得更加合理。

mAP 有一种扩展是 WAP（Weighted mAP）
^[2]
，基于 ACG（Average Cumulative Gains）
^[3]
，支持多值相似性。

对于查询样本 q，检索序列为 V，DCG 公式：

(

)

∑

[

(

)

]

⋅

(

)

DCG@k(q, V)=\sum_{i=1}^kG[rel(q,i)]\cdot D(i)

$D C G @ k (q, V) = i = 1 \sum k G [r e l (q, i)] \cdot D (i)$

其中：

$\text{rel}(q,i) rel ( q , i ) 表示第 i 个检索数据与查询数据之间的相似性，可以多值，如定义成 q 和第 i 个数据之间共同标签数： r e l ( q , i ) = l q T l i rel(q,i)=l_q^Tl_i r e l ( q , i ) = l q T l i ；$
$G(\cdot) G ( ⋅ ) 是 gain 函数，一般取 G ( x ) = 2 x − 1 G(x)=2^x-1 G ( x ) = 2 x − 1 ；$
$D(\cdot) D ( ⋅ ) 是 discount 函数，与位置有关，一般取 D ( i ) = log ⁡ 2 ( 1 + i ) D(i)=\log_2(1+i) D ( i ) = lo g 2 ( 1 + i ) 。$

即

(

)

∑

(

)

−

log

⁡

(

)

DCG@k(q, V)=\sum_{i=1}^k\frac{2^{rel(q,i)}-1}{\log_2(1+i)}

$D C G @ k (q, V) = i = 1 \sum k \frac{2 ^{r e l (q, i)} - 1}{lo g _{2} ( 1 + i )}$

若对于 q，最优的检索序列为

I

$I$

，则 NDCG@k 为：

(

)

(

)

(

)

NDCG@k(q)=\frac{DCG@k(q,V)}{DCG@k(q,I)}

$N D C G @ k (q) = \frac{D C G @ k ( q , V )}{D C G @ k ( q , I )}$

易知，上限为 1。

当距离为 hamming 距离时，应用 tie-aware 版本的指标，见

tie-aware的检索指标

。

Code

与 [4] 对拍通过。

# import numpy as np

def cos(A, B=None):
    """cosine"""
    An = normalize(A, norm='l2', axis=1)
    if (B is None) or (B is A):
        return np.dot(An, An.T)
    Bn = normalize(B, norm='l2', axis=1)
    return np.dot(An, Bn.T)


def hamming(A, B=None):
    """A, B: [None, bit]
    elements in {-1, 1}
    """
    if B is None: B = A
    bit = A.shape[1]
    return (bit - A.dot(B.T)) // 2


def euclidean(A, B=None, sqrt=False):
    aTb = np.dot(A, B.T)
    if (B is None) or (B is A):
        aTa = np.diag(aTb)
        bTb = aTa
    else:
        aTa = np.diag(np.dot(A, A.T))
        bTb = np.diag(np.dot(B, B.T))
    D = aTa[:, np.newaxis] - 2.0 * aTb + bTb[np.newaxis, :]
    if sqrt:
        D = np.sqrt(D)
    return D


def sim_mat(label, label_2=None, sparse=False):
    if label_2 is None:
        label_2 = label
    if sparse:
        S = label[:, np.newaxis] == label_2[np.newaxis, :]
    else:
        S = np.dot(label, label_2.T) > 0
    return S.astype(label.dtype)


def NDCG(qF, rF, qL, rL, what=0, k=-1, sparse=False):
    """Normalized Discounted Cumulative Gain
    ref: https://github.com/kunhe/TALR/blob/master/%2Beval/NDCG.m
    """
    n_query = qF.shape[0]
    if (k < 0) or (k > rF.shape[0]):
        k = rF.shape[0]
    Rel = np.dot(qL, rL.T).astype(np.int)
    G = 2 ** Rel - 1
    D = np.log2(2 + np.arange(k))
    if what == 0:
        Rank = np.argsort(1 - cos(qF, rF))
    elif what == 1:
        Rank = np.argsort(hamming(qF, rF))
    elif what == 2:
        Rank = np.argsort(euclidean(qF, rF))

    _NDCG = 0
    for g, rnk in zip(G, Rank):
        dcg_best = (np.sort(g)[::-1][:k] / D).sum()
        if dcg_best > 0:
            dcg = (g[rnk[:k]] / D).sum()
            _NDCG += dcg / dcg_best
    return _NDCG / n_query

multiple

multi_nDCG
，支持单个或多个 position thresholds，传 int 或 int tuple/list。

# import copy
# import numpy as np
# from util import *  # `euclidean` 放在这里面


def nDCG(Dist, Rel, k=-1):
    """单 k 版
    即原 NDCG（见前文），只是换了 API，用来对拍
    """
    n, m = Dist.shape
    if (k < 0) or (k > m):
        k = m
    G = 2 ** Rel - 1
    D = np.log2(2 + np.arange(k))
    Rank = np.argsort(Dist)

    _NDCG = 0
    for g, rnk in zip(G, Rank):
        dcg_best = (np.sort(g)[::-1][:k] / D).sum()
        if dcg_best > 0:
            dcg = (g[rnk[:k]] / D).sum()
            _NDCG += dcg / dcg_best
    return _NDCG / n


def multi_nDCG(Dist, Rel, k=-1):
    """支持单 k、多 k
    多个 k 时传 int tuple/list
    """
    if isinstance(k, int):
        k = [k]
    else:
        k = copy.deepcopy(k)
    n, m = Dist.shape
    for kid in range(len(k)):
        if (k[kid] < 0) or (k[kid] > m):
            k[kid] = m
    k = sorted(k)  # ascending
    assert k[0] != 0, "`@0` is meaningless and disallowed for efficiency"
    G = 2 ** Rel - 1
    # D = np.log2(2 + np.arange(k))
    D = np.log2(2 + np.arange(m))
    Rank = np.argsort(Dist)

    _nDCG = np.zeros([len(k)], dtype=np.float32)
    for g, d, rnk in zip(G, D, Rank):
        # dcg_best = (np.sort(g)[::-1][:k] / D).sum()
        g_desc = np.sort(g)[::-1]
        if 0 == g_desc[0]:  # biggist DCG
            continue
        dcg_best_list = (g_desc / D).cumsum()
        # if dcg_best > 0:
        #     dcg = (g[rnk[:k]] / D).sum()
        #     _NDCG += dcg / dcg_best
        g_sort = g[rnk]
        dcg_list = (g_sort / D).cumsum()
        for kid, _k in enumerate(k):
            dcg = dcg_list[_k - 1]
            _nDCG[kid] += dcg / dcg_best_list[_k - 1]

    _nDCG /= n
    if 1 == _nDCG.shape[0]:
        _nDCG = _nDCG[0]
    return _nDCG


if __name__ == "__main__":
    print("对拍。结论：一致")
    N, M = 5, 20
    qF = np.random.randn(N, 3)
    rF = np.random.randn(M, 3)
    qL = np.random.randint(0, 2, size=(N, 7))
    rL = np.random.randint(0, 2, size=(M, 7))
    D = euclidean(qF, rF)
    S = sim_mat(qL, rL)
    k_list = [1] + list(range(0, M + 1, 5)[1:])
    print("k_list:", k_list)
    ndcg1 = [nDCG(D, S, k=_k) for _k in k_list]
    ndcg2 = multi_nDCG(D, S, k_list)
    print("nDCG 1:", ndcg1)
    print("nDCG 2:", ndcg2)

References

原文链接：https://blog.csdn.net/HackerTom/article/details/108413141

Notes

multiple R R R

References

你可能也喜欢

multiple