本文记录几种常用的AUC计算方式。

AUC(Area Under Curve)指ROC曲线下的面积,是分类任务中常用的衡量指标。
由于其值的相对大小与真实环境的评估结果一致,被广泛应用与CTR、CVR预估等分类任务。
ROC曲线、AUC、以及AUC中的TPR(True Positive Rate),FPR(False Positive Rate)等概念这里不展开。

物理意义上的ROC曲线

对于一批预估好分类的样本,ROC曲线本质是将分类器的分类阈值从1逐步调整到0,并统计TPR和FPR的打点

假设有一批数据集(用sklearn算一下标准AUC值)

1
2
3
4
5
6
y_pred = [0.6, 0.5, 0.4, 0.3, 0.2, 0.1]
y_true = [1, 0, 1, 0, 0, 0]

from sklearn.metrics import roc_auc_score
print(roc_auc_score(y_true, y_pred))
# 0.875

我们逐步将分类阈值从1调整到0,在这个过程中会从高到低依次遍历所有的prediction点位。

每遍历到一个prediction值,我们就记录下当前的tpr和fpr。

tpr = 预测为正的正样本数 / 正样本数
fpr = 预测为正的负样本数 / 负样本数

因此,在所有prediction遍历结束后,我们会得到所有的打点,这里在起始位置追加了0.0,是分类器阈值=1的初始值

1
2
tpr = [0.0, 0.5, 0.5, 1.0, 1.0, 1.0, 1.0]
fpr = [0.0, 0.0, 0.25, 0.25, 0.5, 0.75, 1.0]

生成tpr和fpr打点的代码逻辑如下,从1->0遍历预测结果,本质是对预测结果的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# move threshold from 1 -> 0 is equivalent to sorted by y_pred desc and record at each pred point
y_true, y_pred = zip(*sorted(zip(y_true, y_pred), key=lambda kv: -kv[1]))

pos = sum(y_true)
neg = len(y_true) - pos

tpr = [0. ]
fpr = [0. ]
threshold = ["fpr=0.0, tpr=0.0, thd=1.0"]

accumulated_tp = 0.
accumulated_fp = 0.

for label, pred in zip(y_true, y_pred):

if label == 1:
tpr.append(tpr[-1]+1)
fpr.append(fpr[-1])
else:
tpr.append(tpr[-1])
fpr.append(fpr[-1]+1)
threshold.append("fpr={}\ntpr={}\nth={}".format(fpr[-1]/neg, tpr[-1]/pos, pred))


tpr = [i/pos for i in tpr]
fpr = [i/neg for i in fpr]

我们以fpr为x轴,tpr为y轴,就可以绘制出ROC曲线

1
2
3
4
5
import matplotlib.pyplot as plt
plt.plot(fpr, tpr, 'bo--')
for i, text in enumerate(threshold):
plt.annotate(text, (fpr[i], tpr[i]))
plt.savefig('1.png')

接下来我们只要基于x、y轴的点位(fpr、tpr的值)计算ROC曲线下的面积即可。

1
2
3
4
5
auc = 0.
for i in range(1, len(tpr)):
auc += (fpr[i] - fpr[i-1]) * tpr[i-1]

print(auc) # 0.875

少量 and 批样本的快速求解

从上图的AUC曲线看,其实是对排好序的样本统计积分面积

注意到:

  • 遇到负样本,TPR不变,FPR右移,此时累计x轴长度。
  • 遇到正样本,TPR上升,FPR不变,在积分图上是垂直于x轴的线,这时候可以计算之前一个长方体的积分面积,算完后,x轴累计值清空,y轴记录最新的正样本数
  • 在遍历完成后,需要补上最后一块ROC下的面积。
  • 由于样本量 和 样本占比是等价的,把除以样本总量的操作移到最后

而fpr/neg 和 tpr/pos的分母都可以提取出来。问题变成,按照prediction结果从高到低,累计 遍历过的正样本数 x 从上一个正样本开始到当前位置的负样本数。

$$ \frac{\sum_i^{N} N_{pos}^{0->i} \times N_{neg}^{lastneg->i}}{N_{pos} \times N_{neg}} $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

y_true = [1, 0, 1, 0, 0, 0]
y_pred = [0.6, 0.5, 0.4, 0.3, 0.2, 0.1]

# move threshold from 1 -> 0 is equivalent to sorted by y_pred desc and record at each pred point
y_true, y_pred = zip(*sorted(zip(y_true, y_pred), key=lambda kv: -kv[1]))

accumulative_pos = 0.
accumulative_neg = 0.
auc_raw = 0.
for i in range(len(y_pred)):
if y_true[i]== 1:
auc_raw += accumulative_neg * accumulative_pos
accumulative_neg = 0.
accumulative_pos += 1
else:
accumulative_neg += 1
auc_raw += accumulative_neg * accumulative_pos
pos = sum(y_true)
neg = len(y_true) - pos
auc = auc_raw / pos / neg
print(auc) # 0.875

海量 or 流式样本

在批样本里,用到了sorted函数,这也意味着算法无法应用于海量或流式这类无法排序的样本。

在这种情况下,可以将严格排序替换为粗略的桶排序,只需对桶间的元素保序

桶的数量越多,AUC计算越准确,当分桶的边界完全覆盖所有样本的prediction结果时,意味着每个桶只有一个元素,而桶是保序的,因此元素保序。此时,分桶计算 和 排序后批计算 两者等价

Tensorflow使用该算法,此外在线上真实流式计算时,也通常采用这种算法统计一段时间的AUC

在流式模式下,我们预先分出N个bucket,每个桶都维护一个当前fp和tp的变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


class StreamAuc(object):
def __init__(self, b=2000):
self.b = b
self.fp = [(0, 0) for _ in range(b+1)]
self.tp = [(0, 0) for _ in range(b+1)]
self.pos = 0
self.neg = 0

def one_batch(self, label, pred):
self.pos += sum(label)
self.neg += len(label) - sum(label)

for i in range(len(pred)):
index = int(pred[i] * self.b) + 1
if pred[i] == 0:
index = 0
if pred[i] == 1:
index = self.b

if label[i] == 1:
n, v = self.tp[index]
self.tp[index] = n+1, (v*n + pred[i]) / (n+1)
else:
n, v = self.fp[index]
self.fp[index] = n+1, (v*n + pred[i]) / (n+1)

def show_auc(self):
accumulative_pos = 0.
auc = 0.
for i in range(self.b, 0, -1):
auc += (accumulative_pos + accumulative_pos + self.tp[i][0]) * self.fp[i][0] / 2
accumulative_pos += self.tp[i][0]
return auc / self.pos / self.neg



stream_auc = StreamAuc(2000)

y_true = [1, 0, 1, 0, 0, 0]
y_pred = [0.6, 0.5, 0.4, 0.3, 0.2, 0.1]

stream_auc.one_batch(y_true, y_pred)
print(stream_auc.show_auc()) # 0.875