机器学习笔记：重拾AUC的计算

AUC这个指标在排序问题里经常用到，之前也有个模糊的印象，就是一个排序正确的比例。

这个模糊印象是，

• 分母是选两个例子的的方式数
• 分子是这两个例子的预测顺序正确的次数

但是今天看了一个python的实现，发现不是很能理解里面的公式，于是查了一下维基百科的定义，

the probability that a classifier will rank a randomly chosen positive instance higher than a randomly chosen negative one (assuming 'positive' ranks higher than 'negative').

上面的意思是，

• 分母是分别选一个正例，一个负例的方式数
• 分子是这两个例子的预测顺序正确的次数

也就是去掉两个负例或者两个正例，这两种情况。想来也是，这种数据属于不知道是对还是错，无法标定，不应该放到准确率中计算。

于是自己试着用一个例子来辅助推导一下公式，如下表所示，$y$是现实的正负例，$\hat{y}$​是模型给出的预测的分数，

index	$y$	$\hat{y}$
0	1	0.9
1	0	0.5
2	1	0.8
3	0	0.7
4	1	0.6

我们需要计算

$$\text{AUC} = \text{P}(\hat{y}_{1}\ge \hat{y}_{0})$$

其中的$\hat{y}_0$和$\hat{y}_1$是随机的一对正负例$y_0$和$y_1$的预测值。

按照定义，分母就是从正例选一个，从负例选一个的方式数，

$$\text{denominator}= n_{pos} n_{neg} = 3 \times2 = 6$$

分子要看预测的分数，一个直接的想法是去生成一个矩阵，比较预测分数，正例和负例谁大，如下面的表格，

正例	1	3
0	1(.9>.5)	1(.9>.7)
2	1(.8>.5)	1(.8>.7)
4	1(.6>.5)	0(.6<.7)

然后去计算矩阵的sum就是正确排序数

$$\text{nominator} = mat.sum() = 5$$

但是这个计算方式有性能问题，类似于冒泡排序的计算量$O(n^2)$；高效一点的实现就是先全排序，复杂度是$O(n\log(n))$，生成一个下面的表中rank值，表明每个值排在第几个位置，

index	$y$	$\hat{y}$	tied_rank
0	1	0.9	5
1	0	0.5	1
2	1	0.8	4
3	0	0.7	3
4	1	0.6	2

这里tied_rank是指，分数一样的话，几个平分一个rank，比如，

>>> tied_rank([1.0, 0.1, 0.8, 0.7, 0.6])
[5.0, 1.0, 4.0, 3.0, 2.0]
>>> tied_rank([1.0, 0.1, 0.7, 0.7, 0.6])
[5.0, 1.0, 3.5, 3.5, 2.0]

如果一个正例在整体中从低分到高分，排在第$k$个，那么他比$k-1$个数大。不过，里面有正例也有负例，我们必须知道里面有正例/负例才行。所以还需要一个只保留正例的计算，如下表。假设这个数在正例中排第$k_{pos}$，那么他比$k-k_{pos}$个负例大。

index	$y$	$\hat{y}$	tied_rank	pos_rank
0	1	0.9	5	3
2	1	0.8	4	2
4	1	0.6	2	1

所以，分子的计算可以写成，

$$\sum_{\text{positives}}{(k - k_{pos})} = (5-3) + (4-2) + (2-1) = 5$$

上面的公式又可以化简，这是因为$\sum{k_{pos}}$其实是是固定的值，只和正例的数目有关系，

$$\sum{k_{pos}} = n_{pos} + (n_{pos}-1) + ...+1 = \frac{n_{pos}(n_{pos}+1)}{2}$$

所以最终的公式为

$$\text{AUC} = \frac{\sum_{\text{positives}}{k} -\frac{n_{pos}(n_{pos}+1)}{2}}{n_{pos}n_{neg}}$$

最后，贴一下网上开源的代码benhamner/Metrics，里面就是这个计算公式。

def auc(actual, posterior):
    """
    Computes the area under the receiver-operater characteristic (AUC)
    This function computes the AUC error metric for binary classification.
    Parameters
    ----------
    actual : list of binary numbers, numpy array
             The ground truth value
    posterior : same type as actual
                Defines a ranking on the binary numbers, from most likely to
                be positive to least likely to be positive.
    Returns
    -------
    score : double
            The mean squared error between actual and posterior
    """
    r = tied_rank(posterior)
    num_positive = len([0 for x in actual if x==1])
    num_negative = len(actual)-num_positive
    sum_positive = sum([r[i] for i in range(len(r)) if actual[i]==1])
    auc = ((sum_positive - num_positive*(num_positive+1)/2.0) /
           (num_negative*num_positive))
    return auc