AUC 是一个对分类器预测数值不敏感的指标，具有比较好的稳定性，也因此成为推荐系统中最常用的模型离线指标之一。但是就这个如此常见的指标，很多人对它也只是一知半解，知道该用它，也知道调用函数去计算它，但是对它的计算过程、它还有哪些用处，却知之甚少。这篇文章就再唠叨一下 AUC 的概念、计算过程以及它如何应用于特征选择上。
AUC (Area Under the Curve) 的概念
AUC（Area Under Curve）被定义为 ROC 曲线下与坐标轴围成的面积。AUC 主要用来评估二分类问题的准确率，即随机给定一个正样本和一个负样本，分类器预测该正样本的得分比预测该负样本的得分大的概率。
AUC 越接近 1 表明这个分类器的性能越好，随机猜测的 AUC 接近 0.5，如果一个分类器的 AUC 低于 0.5，只需要将它的结果取反就能一下子提高模型性能。
AUC 的计算
根据 AUC 的含义，给定样本的真实标签和预测得分，计算分类器的 AUC 指标，主要有三种方法：梯形法、穷举法和序数法。
梯形法 (trapezoid method)
梯形法就是先根据真实标签和预测得分，画出 ROC 曲线，然后简单地将每个相邻的点以直线连接，计算连线下方的总面积。ROC 曲线的详细说明可以参考 wiki，这里给出一个简单的绘制方法：
- 计算所有样本中正样本数 和负样本数 ，进一步计算 x 轴的步长为 ，y 轴的步长为 ；
- 初始化 ROC 曲线在原点 $(0,0)$；
- 将所有样本按预测得分降序排列，然后按顺序进行以下判断并绘制：
- 如果当前样本为正样本，则 ROC 曲线沿 y 轴向上移动单位步长 $s_y$；
- 如果当前样本为负样本，则 ROC 曲线沿 x 轴向右移动单位步长 $s_x$；
- 假设有连续 $k$ 个样本预测得分相同，其中有 $k_p$ 个正样本和 $k_n$ 个负样本，则 ROC 曲线沿着向量 $(k_n\cdot s_x,k_p\cdot s_y)$ 进行移动；
有了 ROC 曲线，我们可以用梯形法计算 ROC 曲线下的面积。举个例子：假设有 6 条样本，某个分类器对每个样本的预测得分 及其真实标签 如下表所示：
| ID | $\hat{y}$ | $y$ |
|---|---|---|
| A | 0.1 | 0 |
| B | 0.3 | 1 |
| C | 0.5 | 0 |
| D | 0.5 | 1 |
| E | 0.7 | 0 |
| F | 0.9 | 1 |
则根据上面的 ROC 画法，我们计算出步长 $s_x=s_y=\frac{1}{3}$，再通过依次观察 F $\rightarrow$ A 的真实标签，可以画出如下的红色 ROC 曲线，并计算出曲线下的面积为：$\frac{1}{3}\times \frac{1}{3}+\frac{1}{2}\times(\frac{1}{3}+\frac{2}{3})\times\frac{1}{3}+\frac{1}{3}=0.61$。
穷举法
穷举法就是穷举样本中所有的正负样本对并计数，从而计算这些样本对中正样本预测得分大于负样本预测得分的比例。假设正例集合为 ，正例数量为 ；负例集合为 ，负例数量为 ，则：
其中， 是指示函数：
例如，在上一小节中的例子中有 3 个正例 (BDF) 和 3 个负例 (ACE)，一共有 $3\times 3=9$ 种组合，每种组合的得分如下：
| 负正样本对 | 指示函数得分 |
|---|---|
| AB | 1 |
| AD | 1 |
| AF | 1 |
| CB | 0 |
| CD | 0.5 |
| CF | 1 |
| EB | 0 |
| ED | 0 |
| EF | 1 |
| 合计 | 5.5 |
因此，该分类器的 $AUC=\frac{5.5}{9}=0.61$，是个相当差的分类器了。
序数法
穷举法比较适合小数据量情况下的计算，但是其实其中有很多比较是重复的。例如当我们按上例中 $\hat{y}$ 将样本排好序以后，对某个正样本而言，它上面的所有负样本数就是它的得分，没必要再穷举其他的样本对。因此我们考虑将样本排序后，基于样本序数来计算 AUC，这里略去推导过程，直接给出计算方法：
其中，$r_i$ 就是按 $\hat{y}$ 排序后，第 $i$ 个样本的序号，如果有多个样本预测得分相同，则这些样本的序号直接求平均。例如对于上面的例子，我们可以对这些样本做如下的编号：
| ID | $\hat{y}$ | $y$ | $r$ |
|---|---|---|---|
| A | 0.1 | 0 | 1 |
| B | 0.3 | 1 | 2 |
| C | 0.5 | 0 | 3.5 |
| D | 0.5 | 1 | 3.5 |
| E | 0.7 | 0 | 5 |
| F | 0.9 | 1 | 6 |
其中，CD 的预测得分相同，因此它们的编号为 $\frac{3+4}{2}=3.5$。根据式 $(3)$ 我们可以算出所有正样本的序数和为 $2+3.5+6=11.5$，$AUC=\frac{11.5-3\times 4\div 2}{3\times 3}=0.61$。
Group AUC
上面介绍了通常意义下 AUC 的计算方法，这个指标实际上是将所有的正负样本放在一起，来衡量模型整体的排序能力。但是在推荐场景下，实际上我们更关心的是对单个用户而言，推荐结果的相对顺序，至于不同用户之间是否正样本的得分一定比负样本高，其实影响并不大。
因此，在某些场景下 AUC 可能无法真实的度量模型的排序能力 (比如离线指标相对较高，但是线上指标相对较差)，这时可以考虑尝试使用 GAUC 来度量。
GAUC 实际上就是按用户进行分组，计算每个用户下样本排序的 AUC，再汇总加权得分，计算公式如下：
这里的用户权重 可以设置为该用户的点击数/曝光数。至于每个用户样本的 计算还是参考式 $(1)$ 或式 $(3)$。
单特征 AUC 的计算
特征选择中一个重要的技术就是单特征 AUC 的计算，它体现了这维特征正确划分样本的能力。单特征 AUC 越高，这维特征也就越重要，尤其是在线性模型中。
单值离散特征的 AUC 计算
单值离散特征是指特征取值是离散特征，而且每个样本中该特征取值只有一个，例如用户的城市、性别等。我们基于训练数据和测试数据可以使用以下算法高效的计算该特征的 AUC (推导过程参考这里)：
- 计算这维特征的每个特征值在训练数据中的正样本占比；
- 在测试数据中，用第 1 步计算的结果作为样本的预测值；
- 基于上一小节中的 AUC 计算方法计算理论上该特征在 LR 下的 AUC；
举个例子，我们考虑性别特征的单值 AUC 计算，假设有 10 条样本 (前 6 条作为训练样本，后 4 条作为测试样本)：
| ID | gender | $y$ | $\hat{y}$ |
|---|---|---|---|
| A | m | 0 | |
| B | f | 1 | |
| C | m | 1 | |
| D | f | 0 | |
| E | f | 1 | |
| F | m | 0 | |
| G | m | 1 | 0.33 |
| H | f | 1 | 0.67 |
| I | f | 1 | 0.67 |
| J | m | 0 | 0.33 |
我们先根据训练样本 A-F 计算性别为 m 的正样本比例为 $0.33$，性别为 f 的正样本比例为 $0.67$，因此我们预测样本 G-J 的得分依次为 $[0.33,0.67,0.67,0.33]$，从而根据式 $(1)$ 可以很快算出来，这维特征的 AUC 为 $(0.5+1+1)/3=0.83$。
多值离散特征的 AUC 评估
多值离散特征是指特征取值是离散特征，而且每个样本中该特征取值可能有多个，例如视频的标签、演员等。虽然单值离散特征可以高效的计算它的 AUC，遗憾的是，多值离散特征的 AUC 似乎无法进行类似的推导。因此我们目前还是通过仅使用这一维特征构建训练数据，用于训练 LR 模型，再用该 LR 模型预测测试数据的得分，用模型的 AUC 来作为该特征的 AUC。
实际上，单值离散特征也可以用建模型的方式来评估，我们两种方法都尝试了，结果证明两种方法得到的结果是十分接近的。
连续特征的 AUC 评估
连续特征就是指取值是连续值的特征，比如视频的播放次数、播放完成度等。
有一些特征如年龄，虽然是连续值，但是因为取值有限，既可以作为连续特征，也可以作为离散特征。但是连续特征，尤其是非均匀分布、或者偏序关系不明确的连续特征，对于线性模型是不太友好的，例如我们考虑预测用户是否播放一个恐怖电影，可能年龄大的或者年龄小的用户都不喜欢看，而比较年轻的用户最喜欢，线性模型就难以区分了。
因此，如果在线性模型中使用连续值特征，除了像播放完成度这类取值范围有限且偏序关系一致 (播放完成度越高，通常表明视频质量越好，用户点击的概率也越大) 的连续特征，我们最好还是按下面的算法来评估某连续特征的单特征 AUC：
- 在训练数据中使用该连续特征训练 GBDT 模型；
- 如果第 1 步中使用多棵树，则用第 1 步训练的 GBDT 对测试数据中的该连续特征进行分桶，将分桶结果作为新的多值离散特征，并使用多值离散特征的 AUC 评估方法进行评估；
- 如果第 1 步中使用单棵树，则用第 1 步训练的 GBDT 对测试数据中的该连续特征进行分桶，将分桶结果作为新的单值离散特征，并使用单值离散特征的 AUC 计算方法进行评估；
至于使用单棵树还是多棵树，最好参数与模型实际执行的特征变换保持一致。