平衡采样的广告点击率预估方式

前言：本站为你精心整理了平衡采样的广告点击率预估方式范文，希望能为你的创作提供参考价值，我们的客服老师可以帮助你提供个性化的参考范文，欢迎咨询。

类别不平衡问题，指的是训练样本的分布不均匀问题。具体的说就是某些类的样本远多于其他类的样本。通常定向广告联盟的广告点击日志中正样本（被点击的记录）和负样本（未被点击的记录）比例为1:1000，很显然这是一个类别不平衡问题。众多处理类别不平衡算法中，对训练数据进行下采样是一种被广泛接受和采纳的策略[7,8,9]，下采样能削减训练数据的大小，缩短训练时间，然而单纯的下采样无法全面利用大类样本提供的信息。平衡采样通过集成一组在下采样之后训练集上训练所得分类器，补回了下采样所造成的信息丢失。本文借鉴平衡采样思想，构建一组逻辑回归模型对进行点击率预估，我们称这一方法为平衡采样逻辑回归。本文的组织结构如下，第二节介绍简单介绍类别不平衡算法的问题以及常用的采样策略，第三节介绍平衡逻辑回归模型，第四节给出性能和效果实验，最后对未来的工作进行总结和展望。

1类别不平衡问题和下采样算法

类别不平衡问题指的是训练样本的分布不均匀的问题。例如在人脸检测[10]中，照片中人脸的数据显然是大大少于背景的数目的。类别不平衡问题在生活中非常常见，它会给机器学习的算法带来诸多困难。首先由于类别的不平衡性，稀有类的样本过少，很难真实的刻画稀有类的分布信息。同时由于正样本过于稀疏，很容易在特征空间中形成一些比较小的数据区块。Weiss[11]表明分类错误很多时候都会集中在一些很小的区块中间。其次，传统的机器学习算法在处理类别不平衡问题时都会有不同程度的下降。最后，以准确率为标准的评判标准通常会忽视稀有类的重要性和影响。以广告点击率为例，在一个千分之一的广告点击率下，即使我们认为所有的广告都不会被点击，它仍然有99.9%的准确率。这显然是不符合实际情况的。通常解决类别不平衡问题的方法主要分为两大类，一种是从训练集角度出发，通过改变训练样本的分布，降低训练样本之间的不平衡性，提高分类效果。另一种从算法的角度出发，针对算法在处理类别不平衡问题中所碰到的缺陷，有目的性的解决这些问题。基于训练集的算法最重要的策略就是上采样和下采样，上采样通过对稀有类增加数据来调整训练数据的类别不平衡性，下采样方法通过删除大类的数据从而改变训练数据的分布使得训练数据更加平衡。在点击率预估问题中，考虑到线上日志的数据量已经达到TB级别，上采样给计算资源和存储资源的带来更加沉重的消耗，因此，本文不予考虑。最原始的下采样方法就是随机下采样[3]，事实证明，这样的采样方法在一定程度上降低了类别不平衡性。在此基础上，很多启发式的下采样方法被提了出来，Hart[4]中提出了CNN原则，提出了稳定子集的概念。并以此为采样原则对数据进行采样。Wilson在[9]中提出了ENN原则，如果一个大类样本最近的三个样本有两个是被标记为稀有样本的，则进行删除这一样本。在ENN的基础上，Laurikkala[8]提出了NCL方法，使用ENN在稀有类和大类同时进行样本的删除。Tomek[13]考虑到类别不平衡问题在决策边界中的不稳定性，使用样本之间距离来删除训练样本中决策边界的样本点来进行数据的下采样。

2平衡采样逻辑回归

2.1基于逻辑回归的点击率预估

逻辑回归是机器学习中被广泛使用的分类模型，它的输出值表示了某个样本被标记为正样本的概率，在定义上它和点击率（广告被点击的概率）是相吻合的。因此，在文献[14]中被提出之后，它就被广泛采用到了各大联盟的点击率预估系统之中。由于联盟广告点击率系统中特征总数非常庞大，然而真正有用的特征较少，L1范式的正则化项能有效的让模型变得稀疏，起到一个特征选择的作用。随后，微软提出的owlqn[15]算法有效的解决了LBFGS[16]优化算法中L1范式不可微的问题，因此，L1范式+逻辑回归的模型以及owlqn算法的优化成了各大联盟系统的首选。

2.2平衡随机森林和easyensemble

随机森林通过集成多个决策树在机器学习中得到了广泛的应用。它通过的对原始数据的自采样，决策树训练过程中对特征空间的随机划分，使得模型训练过程中在样本和特征选择上都进行随机，让不同的决策树都有较高的准确率以及决策树之间较大的差异性，实验表明，它比普通单个决策树在泛化误差要好.然而，和传统的机器学习算法一样，它在处理类别不平衡数据的时候很难的。文献[17,18]发现对于决策树这样的分类器，如果能人工的使用采样或者插值的方法将数据集调整到类别平衡时将会取得更好的分类效果，它也证明了下采样通常能取得比上采样更好的分类效果。根据上述理论，Chen[19]提出了平衡随机森林方法，该方法对正类和反类分别进行不同力度重采样，使得采样后的数据类别平衡（这个过程称之为平衡采样）。最后在重采样多次后采用多数投票的方法进行集成学习，整个算法的流程如下所示。

2.3平衡逻辑回归的点击率预估

上文介绍了平衡采样策略在处理类别不平衡问题时的广泛应用。它删除了大量的负样本数据，缩短训练时间。而训练多个分类器进行集成能有效的将下采样所带来的信息丢失补回。当将它应用到广告点击率预估问题中的时候，考虑到线上模型都是使用逻辑回归模型。因此，本文提出了平衡逻辑回归算法进行点击率预估。平衡采样逻辑回归算法的流程如算法2所示，和平衡随机森林相比，两者之间有以下两点的区别。1.平衡逻辑回归在每一步采样之后，所采用的方法是逻辑回归，这一策略主要的考虑在于现有联盟所采用的基本都是逻辑回归算法，独立开发一套新的大规模并行的机器学习算法需要消耗大量的时间。2.平衡逻辑回归在采样过程中，没有真正的做到类别平衡。每一轮都是以一定的采样力度α对负样本进行采样。使用这样的策略主要是出于运算和存储资源考虑。现有的定向广告的点击率通常只有千分之一，这意味着正样本和负样本比值达到1:1000，如果在每一轮都做到真正类别平衡，意味着删除99.9%的负样本，这会删除大量的负样本，相应的，也需要训练大量的分类器进行集成以补回采样造成的信息丢失。这样的策略在现实点击率预估系统是不现实的，首先训练大量的分类器是一个非常消耗计算资源的过程，其次，线上加载大量模型会造成机器的CPU空闲时间大大减少，甚至造成系统的瘫痪。因此在平衡采样的逻辑回归算法中，通常只能加载若干（3-5个）模型，因此也在每一轮采样过程中无法做到真正的平衡采样。

3实验结果

3.1实验设置

实验采用国内最大的定向广告联盟，百度联盟的点击日志作为训练集，训练逻辑回归模型。并使用这一模型在百度线上进行了多天线上实验。该数据集包含150多种特征，既有广告ID，网站ID等ID类特征，也有广告物料等泛化类特征，由于所有类的特征都被离散化处理，因此每条记录的特征数目是非常庞大的。所有实验数据的准备和owlqn算法的训练过程都在hadoop集群上运行[21]。集群共有4000个节点，每个节点由8核*2.4GHZ的CPU以及16G内存以及12TB硬盘组成。每天产生原始的日志数据量达到20T，在经过特征归一化，hash索引后，压缩至200G的训练数据。

3.2实验设计

实验主要从以下几个方面展开，首先作为一个广告点击率相关的策略，虽然它主要的目的在于缩短训练时间，减小线上模型。但是它不能在点击率预估的效果上有太大下降，要争取做到持平。其次，在点击率预估效果没有太大下降的前提之下，考察这一算法在性能上的表现，包括计算资源和存储资源的节约。最后，性能的提升可以带来的模型的可扩展性，为了展示这一扩展性。一些过去无法被加入点击率预估的特征被采纳进来，并取得了良好的点击率预估效果。在评判指标的选择中，采用了类别不平衡问题中最常见的评判标准AUC。同时也在真实线上环境中做实验，观察策略对线上广告点击率造成的影响。

3.3点击率预估效果实验

3.3.1不同采样力度α对点击率预估效果影响联盟广告的点击日志是一份非常冗余的日志。很多网页或广告很可能在广告点击日志中只有个位数的展现，无法反映广告点击率这样的数据占据了广告点击日志的很大部分，因此我们大胆的删除大量负样本数据，在实验中，考察四个删除力度α（0%、90%、95%、99%）为了排除多个模型带来的影响，暂时只使用一个线上模型。

3.3.2模型个数对点击率预估效果的影响在平衡采样的逻辑回归过程中，模型个数是非常重要的参数。模型个数过少则线上点击率预估效果会下降，模型个数过多则会消耗过多的计算、存储资源。图3是删除力度为90%的情况下，采用不同模型个数，线下AUC的变化。可以看到，整体上AUC是随着的模型个数的增加而逐渐增加的，但是，这样的趋势逐渐放缓。模型个数为7和8的AUC基本持平。造成这样的现象主要在于逻辑回归本身是一种比较稳定的模型，虽然对样本的采样能造成一定的不稳定性，然而随着模型个数的增多。这样不稳定性逐渐被消除，最终趋于统一。表3反映了加载一、三、五个模型和不进行采样只使用一个模型的线上的点击率变化，可以看到，线上实验和线下的AUC评估效果基本一致。而且，在加载5个模型之后，数据删除所带来的信息丢失被多个模型的集成补了回来，线上广告点击率效果上已经基本和未删除样本和集成的策略基本持平，这也与本文算法中“加载若干（3-5）模型”的假设是相一致的。

3.3.3关于采样的讨论在平衡采样的逻辑回归算法中，节约资源的主要原因在于采样，然而我们没有采用类别不平衡算法中启发式的ENN，CNN采样方法，而是用了最简单的随机采样，这主要从性能因素考虑。无论是的ENN，CNN或者NCL这样的采样方法，都需要计算样本和样本之间的距离或者样本和决策边界的距离，由于百度联盟点击率日志规模庞大，训练样本数目较多（TB级别）、特征维度也非常庞大（几十万），计算样本之间距离过程是非常消耗计算资源的。以ENN为例，在每一轮样本采样的过程中，都需要计算每个样本的3NN样本，这个过程意味我们要重新对整个训练集（TB级样本）进行一次遍历，时间复杂度为O(n)，显然这是非常消耗资源的。然而，随机采样则完全不同，决定每个样本是否删除只需要产生一个随机数就能完成，时间复杂度为O(1)。在本算法过程中，本文采用了一种单边采样的策略，即只对负样本进行采样。为了证明这一思想的正确性，本文进行了一次实验，对比了对正样本和负样本同时采样和单边采样的在不同模型个数下的线下AUC。（双边采样中对正样本采样20%，负样本采样90%。单边采样只对负样本采样90%）。实验结果表明，双边采样效果明显不如单边采样。

3.4性能实验

本算法最主要的目的在于性能上的提升。表5比较了未对数据进行采样和采样之后整个系统的性能参数。其中，删除力度α为90%，使用3个模型进行投票。在进行数据删除之后，在主要的几个性能指标上都有了显著的性能提升。每个模型所需的训练数据大小缩减了88%，这和删除90%负样本的预期基本一致，节约了大量的线上数据存储资源。由于owlqn算法每一轮都要遍历所有的样本，因此在样本删除之后，算法每一轮所遍历样本数目减少，迭代的时间也大幅度缩减，从600秒下降到了100秒。整体训练时间从过去的八个小时下降到了一个半小时，大大加快了模型的产出速度。与此同时，模型的大小也随之缩减了50%。由于在线上进行点击率预估的时候需要同时加载三个模型，因此线上机器的CPU空闲时间下降了，然而这样的降低和整体的性能提升相比完全是可以接受的。综合效果实验和性能实验的结果，可以看到平衡采样逻辑回归方法节约了大量的线下存储和计算资源，有效的提升了点击率预估系统的性能。更重要的是，这样的性能提升并没有造成点击率预估效果上的下降。主要原因在于两点，首先广告点击率预估的负样本中的冗余性非常高，即使删除大量的负样本也不会造成显著的预估效果下降，其次多次采样的集成多个模型的学习方法能有效的补回由于删除负样本所造成的信息丢失。

3.5模型可扩展性实验

平衡采样逻辑回归帮助广告点击率预估节省了大量的计算和存储资源，这些节省下来的资源帮助后续的策略团队上线更多过去不可能被使用的特征，为了说明这一扩展性，本文简单的做了一个实验。网站url和用户cookie是两个非常细粒度的特征，每天的点击日志中会有数以亿计的url和cookie。在离散化的逻辑回归算法下，如果把这两个特征加入到模型之中会造成线上模型大小以及训练时间的大幅度增加，因此在过去几年的特征团队一直没有将其放入点击率预估模型。然而在进行平衡采样之后，计算和存储资源被节省了下来，这两个特征以及可以被尝试加入到广告点击率预估模型之中，首先看一下在加入特征之后系统整体的性能参数。

4结束语

本文借鉴了在类别不平衡算法中平衡采样方法，并针对广告点击率问题中训练数据的特点，提出了平衡采样逻辑回归算法。事实证明，该算法能在不牺牲模型点击率预估效果的前提下，有效提升整个系统的性能指标。然而，现有的平衡采样方法由于加载多个模型造成线上机器CPU空闲时间的下降。因此，是否存在其他方法不让系统同时加载多个模型，是否有更好的办法弥补数据删除所带来的信息丢失是下一步需要考虑的问题和工作。

作者：施梦圜顾津吉单位：南京大学软件新技术国家重点实验室百度中国有限公司联盟研发部