前文《什么是好的推荐，重新理解AUC》从什么是好的推荐系统，引出了AUC的定义，并基于定义推导出AUC的计算、AUC的优点(为什么用AUC评估分类模型)、AUC的缺点，在文末留了几个可以继续讨论的点，本文将继续讨论AUC，主要介绍AUC的具体计算方法，后续文章将会相继分享过拟合，AUC离线和线上表现不一致等问题。

前文根据AUC的定义推导出AUC的计算公式：

n_{j}}}}{P*N} “>AUC=∑(pi,nj)pi>njP∗NAUC=\frac{\sum_{}^{}{(p_{i}, n_{j})_{p_{i} > n_{j}}}}{P*N} ，其中 PP 为正样本数量， NN 为负样本数量， pip_{i} 为正样本预测得分， njn_{j} 为负样本预测得分。

1 方法1

用指示函数表示上式中正样本预测值大于负样本预测值的正负样本对，则得到

正样本负样本AUC=∑I(p正样本,p负样本)P∗NAUC=\frac{\sum_{}^{}{I(p_{正样本}, p_{负样本})}}{P*N} ，其中 p_{负样本} \\ 0.5, p_{正样本} = p_{负样本} \\ 0, p_{正样本} < p_{负样本} \end{aligned} \right. , p”>正样本负样本正样本负样本正样本负样本正样本负样本I(p正样本,p负样本)={1,p正样本>p负样本0.5,p正样本=p负样本0,p正样本<p负样本,pI(p_{正样本}, p_{负样本})=\left\{ \begin{aligned} 1, p_{正样本} > p_{负样本} \\ 0.5, p_{正样本} = p_{负样本} \\ 0, p_{正样本} < p_{负样本} \end{aligned} \right. , p 表示预测得分。

根据上式，AUC的计算的关键则是得到所有正负样本对，以及得到每个正负样本对的指示函数值。这是一个简单的排列组合问题。

以一个例子进行计算说明。

样本编号真实分类预测值A10.4B10.8C00.2D00.4E00.5

在给出的例子中，包含有2个正样本(A, B)和3个负样本(C, D, E)，因此一共有6个(2*3)正负样本对，即公式中分母为6。

接下来计算公式中的分子，即每个正负样本对的指示函数值：

以A为正样本形成的正负样本对为(A, C), (A, D), (A, E)，指示函数值分别为1，0.5，0；以B为正样本形成的正负样本对为(B, C), (B, D), (B, E)，指示函数值分别为1，1，1。

因此 正样本负样本AUC=∑I(p正样本,p负样本)P∗N=1+0.5+0+1+1+12∗3=34AUC=\frac{\sum_{}^{}{I(p_{正样本}, p_{负样本})}}{P*N} = \frac{1+0.5+0+1+1+1}{2*3} = \frac{3}{4}

这种方法计算AUC的时间复杂度为O(P∗N)O(P*N) ，获取正负样本的数量时间复杂度为 O(P+N)O(P+N) ，计算所有样本对的指示函数值时间复杂度为 O(P∗N)O(P*N) ，故时间复杂度为 O(P∗N)O(P*N) 。

2 方法2

用方法1计算AUC易于理解，但需要对所有样本对计算指示函数值，有没有不需要对所有样本对遍历的方法？

AUC计算的关键是找到所有正样本预测值大于负样本预测值的正负样本对。

如果引入排序，则大小关系就可以确定；如果有正样本的排序序号，则可以知道样本对(当前样本，<=当前正样本预测值样本) 的数量，这其中的样本对包括正负样本对，也包括正正样本对，则减去正正样本对就是AUC计算需要的正负样本对。

根据以上两点分析，则可以对所有样本按照预测值从低到高排序。排序后可以得到每个正样本的序号，用rir_{i} 表示第i个正样本的序号，则样本对(当前样本，<=当前正样本预测值的样本) 的数量为 rir_{i}，其中正正样本对有若干个，用PPiPP_{i} 表示，PPiPP_{i} 包括了和当前正样本本身形成的正正样本对。

则由当前正样本形成的正负样本对(正样本预测值>负样本预测值)的数量= ri−PPir_{i}-PP_{i} ，对所有正样本形成的正负样本对(正样本预测值>负样本预测值)求和，即得到了AUC计算公式的分子，即 样本正样本∑样本i∈正样本ri−PPi\sum_{样本_{i}\in正样本}^{}{{r_{i} – PP_{i}}} 。

对每个正样本而言， PPiPP_{i} 值未知，而对所有正样本的 PPiPP_{i} 求和，其值为 P∗(P+1)2\frac{P*(P+1)}{2}。具体计算如下：得分最高的正样本，PPiPP_{i} 是所有正样本的数量，即 PP ，得分第2高的正样本， PPi=P−1PP_{i}=P-1 ，得分最低的正样本 ,PPi=P−1PP_{i}=P-1 ，因此所有正样本的 PPiPP_{i}形成一个等差数列[P,P−1,P−2,…,1]\left[P, P-1, P-2,…,1 \right] ，该等差数列求和值为 P∗(P+1)2\frac{P*(P+1)}{2} 。

因此 样本正样本AUC=∑样本i∈正样本ri−P∗(P+1)2P∗NAUC=\frac{\sum_{样本_{i}\in正样本}{{r_{i} – \frac{P*(P+1)}{2}}}}{P*N} 。

这种方法计算AUC的时间复杂度为O((P+N)∗log(P+N))O((P+N)*log(P+N)) ，获取正负样本的数量时间复杂度为 O(P+N)O(P+N)，排序的时间复杂度 O((P+N)∗log(P+N))O((P+N)*log(P+N)) ，故时间复杂度为 O((P+N)∗log(P+N))O((P+N)*log(P+N)) 。

继续以上面例子为例，按照预测得分从低到高排序

样本编号真实分类预测值排序值A10.42B10.85C00.21D00.43E00.54

在上面的例子中出现了得分相等的情况，这时候排序值由相同得分的排序值算平均值，所以计算AUC时，样本A的排序值等于样本A本身和它相同得分样本D的排序值均值，即(2+3)/2=2.5，因此带入AUC的计算公式，得AUC=(2.5+5)−2∗(2+1)22∗3=34AUC=\frac{(2.5+5)-\frac{2*(2+1)}{2}}{2*3}=\frac{3}{4}。

3 代码实现AUC计算

推荐相关岗位的面试中，面试官经常问到AUC的计算，主要想考察面试者对AUC的理解，也就是本文介绍的方法1或者方法2。下面将给3种计算的代码实现：

python中的sklearn工具本文中的方法1本文中的方法2

在方法2的实现代码中，为了方便，当预测得分相同时，没有按照定义用排序值的均值，而是直接使用排序均值。使用这种近似，对本文中的例子的AUC有影响，但生产环境的数据集大，这种近似对AUC的影响极小。

上述代码运行结果

图1 auc计算代码运行结果

由于方法2做了近似，例子中的样本数量少，影响较大。在实际推荐业务，由于数据量非常大，近似对auc值的影响可以忽略不计。

预告：下一篇将分享过拟合问题。

推荐系列文章：

什么是好的推荐，重新理解AUC

为什么需要推荐