Kaggle大神带你上榜单Top2%：点击预测大赛纪实（上）

大数据文摘作品

作者：Gabriel Moreira

编译：朝夕、Katherine Hou、党晓芊、Niki、元元、钱天培

作为全世界最知名的数据挖掘、机器学习竞赛平台，Kaggle早已成为数据玩家在学习了基础机器学习之后一试身手的练兵场。

那么，参加Kaggle比赛到底是怎样一种体验呢？Kaggle比赛的爱好者们不计其数，很显然这些比赛不会是简单枯燥的模型调参。

更进一步地问，Kaggle比赛的优胜者们又是如何取得优异的成绩的呢？优质的算法对大多数Kaggle竞赛来说显然不是制胜法宝——SVM、随机森林、神经网络等的应用对多数参赛者都不是难事，而改进甚至发明新算法似乎也更属于学术研究的范畴。

今天，文摘菌将为大家介绍一位资深数据科学家Gabriel参加Kaggle的Outbrain点击预测比赛的经历。相信大家在读完他的比赛经历后，会对Kaggle比赛有更深一步的了解，也能一窥大神在Kaggle比赛中取得优异成绩背后的秘密。

2017年1月18日的午夜，Outbrain点击预测机器学习竞赛刚刚结束。在此之前，我连续三个半月工作到深夜。当我翻阅排行榜（leaderboard）页面时，我发现我的名字在第19位，在将近1000名参赛者中排在前2%。而这只是我参加的第一个Kaggle比赛！

这项Kaggle竞赛是由Outbrain赞助的。Outbrain是一家广告公司，这家公司每个月将上千家网站上相关的内容与读者匹配，提供2500亿条个性化推荐。在这个竞赛中，参赛者们的挑战是要预测全球用户群体将点击哪些广告或者其他形式的赞助内容。Outbrain运营一个发布者和广告商的关系网。比如说，在下面的图片中，CNN（发布者）在新闻页面中将赞助内容（广告）呈现给用户。

图中标注（从左到右，从上到下）：

来源，发布者，文档，

推广内容区域，

推广内容模块

这个竞赛要求参赛者能够准确地对推荐内容按照点击率预测值进行排序。点击率（Click-Through Rate, CTR）预测与像电子商务和广告这样的行业息息相关，因为用户转化率的微小提升可能带来利润的巨大增长，同时带来更好的用户体验。

数据集和基础架构

竞赛中的一大难点是要处理庞大的数据集：来自560个网站的7亿个独立用户，20亿次页面浏览量和大约1700万次点击记录。其中包括2016年6月14日到6月28日在美国多个新闻网站观测到的用户的页面浏览和点击样本。

考虑到这是一个大型的关系数据库，且其中一些数据表比内存还大，Apache Spark非常适合用来做数据探索和快速分布式的预处理。谷歌云平台提供了我需要的存储和分布式处理的主要组件。

用Google Cloud Dataproc（谷歌云数据处理）管理服务可以很容易地部署一个Spark集群。我发现1个主进程和8个工作进程节点的“n1-highmem-4”型集群（大约相当于4核CPU和16GB内存）能够在一个小时左右的时间里处理所有的竞赛数据，其中包括合并大的表、变换特征以及存储向量。

我主要的开发环境是Jupyter notebook，一个非常高效的Python界面。这个谷歌云平台的教程介绍了如何在数据处理主节点上设置Jupyter，并使用PySpark库。

Dataproc Spark集群利用谷歌云存储（Google Cloud Storage, GCS）作为分布式文件系统而非通常默认使用的HDFS。作为一个管理存储(Managed storage)方式，它使得实例间的大型文件的传输和存储更加便利。Spark能够直接使用GCS中的数据做分布式处理。

我还使用了一些机器学习框架（比如FTRL, FFM, GBM等），这些框架是基于并行计算而非分布式计算的，所以它们需要用到高CPU核数和大内存来处理大型数据集。部署在Google计算引擎(Google Compute Engine, GCE)上的一个’n1-highmem-32’型实例(32核CPU和256GB内存)使得运行时间缩短到1个小时以内。由于数据处理过程为I/O密集型，我将SSD硬盘接到实例上以避免瓶颈。

初次尝试

这次竞赛的评价算法是MAP@12（点击率前12位广告平均精准度），这个指标用来衡量的是广告排序的质量。换句话说，这个算法评估的是实际高点击率的广告是否被模型排在了前面。

常识告诉我们，广告的平均流行程度可能可以很好的预测是新点击量。这个方法的主要思路是按照降序的点击率（CTR，点击量/浏览量）对展示给用户的广告进行排序。

在下面的Python代码片段中，我将展示如何用PySpark从训练数据集 (click_trains.csv) 计算广告点击率。这个CSV文件有超过8700万行，存储于GCS。完整的代码在Dataproc Spark集群中用8个工作节点能够在30秒内运行完。

把训练数据 (click_trains.csv) 加载到一个Spark DataFrame内，并计算行数。

得到不重复的广告数量

在下一段代码片段中，我用广告编号分组，计算了每组的点击量和浏览量，并由此定义了一个新的DataFrame。我用了一个叫ctr_udf的用户自定义函数（User Defined Function, UDF）计算点击量。这个片段输出的结果是一个包含10个广告的数据表，内容为广告编号及对应的点击量，浏览量和点击率。

计算广告平均点击率

为了提高点击率的可信度，我们只考虑超过5次浏览的广告。我们用collectAsMap()函数，把分布式的数据集转换成一个内存内的可供查询的字典，字典的键是广告编号，值是对应的平均点击率。

这是大多数参赛者提交的基准线，即使没有用任何机器学习算法，这个方法仍然可以得到MAP@12为0.637的成绩。作为参考，官方的竞赛基线是按照广告编号排序（近似于随机方法），得到的MAP@12是0.485。因此，这个原始方法已经能很好地预测点击率了。

数据分析

和往常一样，在应用任何机器学习技术之前，很重要的过程是要分析数据，并且做出假设，哪些特征和算法会对解决这个问题有帮助。我用PySpark对最大的数据集（page_views.csv ~ 100GB）做了探索性数据分析（Exploratory Data Analysis, EDA）。

我的探索性分析核（Kernel）介绍了如何用Python，Spark SQL和Jupyter Notebook在谷歌Dataproc平台上分析竞赛提供的最大的数据集。我把这个内核分享给了其他参赛者，最终这个核被票选为受欢迎程度排名第二的贡献（金牌）。根据核下面的评论，我发现许多参赛者都在考虑在机器学习竞赛中使用谷歌Dataproc和Spark。

在分析时，我通过合并page_views数据集和训练集与测试集（events.csv），找到从数据集中提取数据值的方法。比如，在如下所示的累积图表中，我们可以看到有65%的用户只有一次页面浏览，77%的用户有最多两次浏览，89%的用户有最多5次浏览。

最多浏览了N次页面的用户累积百分比

这是一个典型的“冷启动”现象，我们对大多数用户知之甚少，却需要预测他们会点击哪个推荐内容。

通常，传统的推荐系统技术，例如协调过滤和基于内容过滤，在这样的情况下会失效。我的策略是采取另一种机器学习算法，让我们能够利用用户行为和推荐赞助内容的上下文信息。

特征工程

特征工程是指选择或创建机器学习中需要用到的正确的特征的重要步骤。通常，根据数据复杂度不同，特征工程可能占到所有工作内容的80%。下面的图片展示了竞赛的原始数据模型，其中特征的数据类型用颜色进行了区分。

Outbrain 点击预测大型关系数据库

所有的分类型字段最初都是整数形式的。依据机器学习算法，序数值型的编号会让模型认为一个类型比另一个类型有更大的关联。例如，阿根廷的编号是1，巴西的是2，算法会推测巴西的代表性是阿根廷的两倍。为了处理这个问题，通常会使用诸如单热编码（One-Hot Encoding, OHE）的技巧，这种方法会把每个分类转换成一个稀疏的向量。在这个稀疏的向量中，除了编号值对应的位置，其他位置都是0。

对于有大量唯一值的分类型特征来说，另一个很流行的技巧特征哈希化（Feature Hashing），这一方法将分类与一个固定长度的向量通过哈希函数匹配。这种方法相较于单热编码提供了更低的稀疏度和更高的压缩度，而且对新的少见的分类值（比如之前未出现过的用户代理商）也能处理得很好。当把多个特征匹配于相同的向量位置时，它也会产生一些冲突，不过机器学习算法通常在处理这些冲突时足够稳健。我在处理数据时同时用了这两种方法。

我还对数值型标量特征做了分箱（Binning）操作。有些特征的噪声很大，所以我们最好用数据变换的方法降低微小观测单位带来的误差和偏差。例如，我把“小时”这个变量分箱处理成了不同时段如早晨，中午，下午，晚上等，因为我假设用户在比如上午十点和上午十一点的行为差异不会特别大。

对于长尾分布的变量，比如用户浏览次数，大多数用户只有一次页面浏览记录，少量用户有大量浏览记录。采用像对数（log(1 + 浏览次数)）这样的变换能够使分布平滑。一个有1000次浏览量的用户可能和有500次浏览量的用户没有太大差别，他们都是模型的异常值。

标准化和正态化对于大多数用比如梯度下降这样的优化方法的机器学习算法来说也很重要。通常，对值和方差数量级不同的几个原始数值型特征，只有基于决策树的模型是稳健的。

基于探索性分析，我对数据特征的一定的认识，也检验了一些的假设。我在竞赛数据提供的原始特征外，为我的机器学习模型创建了一些特征，也通过转换数据得到了一些特征。下面是一部分我新建特征。

用户相关特征

user_has_already_viewed_doc

记录用户是否已经浏览过向他们推荐的页面。

user_views_count

热心读者的行为是否与其他客户不同？让我们加入这个特征，让机器学习模型给出答案。

user_views_categories, user_views_topics, user_views_entities

用户特征指标包括客户之前浏览过的内容分类、主题和页面内容（按照置信度和词频-逆向文件频率来分配权重），通过对内容的筛选来对客户偏好进行建模。

user_avg_views_of_distinct_docs

（客户浏览去重文档数/客户总浏览次数）得到的比率，用来定义客户重复阅读网页的频率。

广告/文档相关特征

doc_ad_days_since_published, doc_event_days_since_published

广告对特定用户已经发布的天数。普遍的共识是用户对新的内容更感兴趣。但是如果你正在读一篇旧报道，你很可能对其他旧新闻也感兴趣。

doc_avg_views_by_distinct_users_cf

客户对广告网页的平均浏览量。用户常常登陆这个网站吗？

ad_views_count, doc_views_count

指示某个文档或者广告的受欢迎程度。

事件相关特征

event_local_hour (已分箱), event_weekend —事件发生的时间戳都是美国东部时间，我根据事件的地理位置调整得到用户的当地时间。然后按照上午，下午，中午，晚上，夜里等时间段进行分箱。同时我创建了另一个特征来表示是否是周末。我假设时间会影响到客户对阅读内容的选取。

event_country, event_country_state

我从event_geolocation这个变量中提取出用户所在的国家和省份

ad_id, doc_event_id, doc_ad_id, ad_advertiser, … 

模型中所有原始的分类数据都使用单热编码，因此特征扩展到了12万6千个。

平均点击率

avg_ctr_ad_id, avg_ctr_publisher_id, avg_ctr_advertiser_id, avg_ctr_campain_id, avg_ctr_entity_id_country …

基于一些分类组合和点击率置信度（详见之后的第二篇）的平均点击率（点击次数/浏览次数）。比如点击某两个分类的概率。

内容的相似度

这些特征使用词频-逆向文件频率（TF-IDF）技术为用户和页面建立特征参数，对客户喜好和内容分别建模。然后利用余弦相似性对比所有候选文档与客户喜好的相似程度。这是一种非常普遍的基于两个向量之间夹角，忽略向量量级的信息检索方法。

user_doc_ad_sim_categories, user_doc_ad_sim_topics, user_doc_ad_sim_entities

计算客户信息和广告内容这两个向量的余弦相似度。

doc_event_doc_ad_sim_categories, doc_event_doc_ad_sim_topics, doc_event_doc_ad_sim_entities

计算事件信息(页面内容)和广告内容这两个向量的余弦相似度(TF-IDF)。

我们根据自己的假设创建了一些可能会影响用户对点击内容选择的特征。数据已经准备好了，可以开始机器学习建模了！

交叉验证

对一个机器学习模型而言，能不能把从训练集得到的规律推广到训练集之外的数据是非常重要的。交叉验证（Cross-Validation）就是确保这种推广能力的重要一步。

把原始的训练集clicks_train.csv按照一定比例分成验证集和新的训练集很有必要。验证集占原数据集的30%，其余部分是新的训练集。机器学习的训练过程是这样的，先通过训练集找到模型，然后用该模型对验证集作出预测，将预测值与验证集中的已知结论（是否被点击）进行对比，以评估模型的准确性。

我们通过尝试不同的特征工程，改进算法和超参数调整这样的方法，提高用交叉验证的方法得到的准确率，从而使我们在竞赛排行榜上的排名逐渐提高（这其实也就是增加了用测试集得到的结果的准确率）。

大部分的Kaggle竞赛，对于当天提交结果的次数是有限制的（对于本次竞赛，这个上限是2次/每天）。我们通过交叉验证的方法，也可无限次的检验我们的模型，不用担心这个限制。

对于这次竞赛，我使用的交叉验证方法叫做holdout，这种方法就是简单地从原训练集中取固定的一部分作为验证集。此外，还有一些其它常用的交叉验证的方法，比如说k重选择法。

对于基于人类行为的机器学习模型，时间因素也是一个评价模型需要考虑的重要指标。有很多数据特征会随着时间的变化对用户产生新的影响，就像近因效应，搜索趋势还有某些真实世界发生的事情等。

如下图所示，我们观察到训练和测试集的数据在15天内，随时间分布的图表。大约有一半的测试数据（来自clicks_test.csv数据集）和训练集的数据是在同一天进行采样（同步采样），而另一半的测试数据是在紧随其后的两天内采样，以此作为对于未来的预测（非同步采样）。

训练和测试集数据按天数的比例分布。数据来源于joconnor EDA kernel

基于上述的观察，我的交叉验证策略如下：我的验证集将采取和测试集一样的时间分布。在下面的代码片段，你会看到这种分层抽样可以很简单的通过Spark SQL Dataframe实现（Spark集群是部署在Google Dataproc上面的）。对于验证集，除了最后两天抽取全部的事件外（11和12），其余每天仅仅抽样数据的20%。

基于日期的分层取样。使用SparkDataframe (Python)

这种精心设计的对于验证集的取样，在模型训练的时候很有帮助，因为我的交叉验证得到的分数与排行榜上的分数在四位有效数字上保持一致。这样，我可以放心的以我的交叉验证分数作参考进行模型的优化，然后只有提交显著提高的模型。

基线模型的预测结果

截至到目前，我用了非常大的精力进行试探性数据分析，特征工程以及实现前文所说的交叉验证策略。以我的经验，处理这些任务会花费掉整个机器学习工程的60%-80%的时间。但是，如果这些前期步骤没有做对或者做好，它们会大大削弱你的模型可能达到的最大预测精度。

现在让我们换一套想法，开始讨论一下模型训练的算法。我的策略注重个人的学习过程，我从最简单的模型开始测试，逐步验证到最强大最前沿的算法，这一样来我们就可以知道对于这个挑战每种算法预测准确度的上限。

我的第一个方法已经在之前介绍过了，就是简单地使用过去的点击率来对广告进行排行，这个方法并不涉及机器学习算法。对于大多数竞赛参与者来说，这是个非常流行的基线模型，以MAP@12 作为指标，它在排行榜上给出了0.637的分数。

Kaggle社区在分享经验和方法方面很活跃，即使是在比赛进行的阶段依然如此。有一位竞赛参与者在社区里分享了他发现的数据泄露。这个数据泄露是基于对page_views.csv数据集的分析，揭露了在测试集中4%的用户访问(通过display_ids确定)实际点击的广告。作为一个机器学习竞赛来说，分享数据泄露是一个公平的做法，同时还提供了一个新的基线模型。我的第二个方法就是在第一个方案的基础上，仅仅调整了泄露出来的广告排名，把它们放到别的广告之前。这样一来我的分数就一下子上涨到0.65317。和其他竞赛参与者一样，我在之后提交的所有结果都使用了这个数据泄露。

大多数广告由于被观看到的次数太少（小于10次），从而无法进行有效地统计点击率。我的直觉是，通过其他分类变量对点击率影响的先验知识，可以对无法观察到的数据进行预测。这样，当我计算平均点击率的时候，我不单单只考虑广告编号的影响，还同时考虑了其他分类变量对点击率的作用。这就是条件概率P(click | category)，甚至是两个不同的分类变量对点击率的协同作用：P(click | category1, category2)。

在交叉验证中平均点击率预测准确度更高的的分类变量分别为：

ad_document_id, ad_source_id, ad_publisher_id, ad_advertiser_id, ad_campain_id,

文档特征 (category_ids, topics_ids, entities_ids) 和上述几个变量与event_country_id的结合。结合event_country_id的分类变量可以用来模拟各区域用户的偏好。

点击率置信度（CTR confidence）是我在这次竞赛中设计的衡量标准，用于衡量分类点击率预测某一特定广告点击率的准确性。

点击率置信度

在这个公式中，d代表某一类别中不同广告的数量，v代表这些广告的阅览量。d的值越高意味着这个分类对于某个特定的广告太宽泛（比如“主题=政治”），从而导致点击率置信度较低。

一个高的v值代表相应类别的广告有很高的阅览量，从而增加了点击率的统计显著性。比如说，某一特定广告的点击率（分类值）可能相比之前采用的广告商的点击率（更高的d值）更加准确。因此，可能这个广告没有足够的阅览量达到统计显著性（v<10），从而导致它的点击率置信度低于之前采用的广告商点击率的置信度。

对数转换同样也被用来平滑处理一些流行的类别或广告。最后，我们通过除以m来是特征标准化，使得取值范围在0到1之间。这是不同广告的平均浏览量（v/d）的一个参考值，其最大置信度为1。在这次比赛中我用m=100，000。

第三种方法是对每一个类别的点击率的加权平均，权重为相应的点击率置信度。这种方法让我的排行榜分值增加到0.65498.

手动计算这些基线预测值后，就可以开始运用机器学习的算法来处理这些问题了。

机器学习模型

在这一小节我将展示我在这次挑战中尝试的第一个机器学习模型：协同过滤和树集成。

协同过滤 – ALS 矩阵分解

协同过滤可能是推荐系统中最常见的方法。这种方法通过收集其他用户的喜好或品味的相关信息（协同）来预测用户的喜好从而提供个性化的建议（过滤）。因此，这种方法也自然是第一个被评估的。

交替最小二乘（ALS）矩阵分解作为以模型为基础的协同过滤方法可应用于用户庞大的信息矩阵。我们使用了Spark交替最小二乘的应用，它的突出点在于在一个群集之中分布运行，同时也支持了内在的反馈数据（例如，阅览量，点击量，购买，点赞和分享）和外在的反馈数据（例如，电影或书的评分）。

第一步是去建立一个稀疏的用户和文件的效用矩阵（内容页代表每个广告）。矩阵中包含每个用户对每个文件的浏览量。对数转换在平滑浏览量中十分关键，因为一些用户（或机器）在竞赛提供的十五天的数据中浏览过同一网站多次。

多次尝试调整Spark交替最小二乘矩阵分解中的超参数后，我发现最好的模型（见下图）在交叉验证中平均精度均值（MAP score）有0.56116，比之前的基准值低很多。因此，我最后的集成解决方法中没有采用这个模型。

导致糟糕的结果的一个可能的原因是“冷启动”，在两百万多页中平均阅览量只有2.5，这使协同过滤的方式去推断用户偏好并完成这样大却稀疏的矩阵十分困难。

Spark交替最小二乘模型训练（Python)

梯度提升决策树

标准的协同过滤只采用了用户和文件之间的效用矩阵。但这次比赛中还有大量关于用户访问内容，登录页面和广告的信息。因此，我们用一种排序学习的方法来利用这些信息。

我采用的是梯度提升决策树模型（GBDT）。这个机器学习模型是一个由多个决策树（弱学习器）组成的集成模型。跟随机森林（RF）相似，为了得到不同视角下数据的模型，每个决策树是通过一个训练集组成的子样本（又称套袋法）和其属性的子样本(随机选取部分特征) 得到的。与随机森林模型不同的是，GBDT模型对训练集中在前一个树模型分类错误的样本权重更高，从而使提高模型的精确度，也使模型成为更稳健的分类器。

我测试了两个GBDT框架：XGBoost和LightGBM，它们应用在大的数据库上速度快、所需储存空间小。在我们所遇到的问题中，它们能够着重最优化某次用户访问(由display_id确定)看到的广告排行，而不是去预测每个广告是否被点击。以排行为目的XGBoost方法基于平均精度均值（MAP）的标准（官方的衡量标准）进行最优化学习。LightGBM是基于另一个叫NDCG的标准进行最优化。

XGBoost模型中的特征，在第一个帖子中已经有详细介绍，分别为：类别的独热编码，各种分类下的平均点击率和其置信度，上下文相似度（登录页面中的分类、主题、主体和广告信息的余弦相似度）和用户偏好相似度（用户信息和广告信息的余弦相似度）。这些特征变量，尤其是分类的独热编码，导致特征向量十分稀疏，其维度超过126，000，而且只有40个非零的特征。

XGBoost的超参数调整是一个比较棘手的问题，这个调整参考对我来说很有帮助。最好的XBGoost模型（方法四）得到了排行榜分值0.66821（超参数值见下图），相比基准模型这是个巨大的进步。训练这个模型用一个32CPU和28GB RAM的服务器用时大约三小时(Google GCE上的n1-highmem-32型实例)。

用自带的Python API训练最好的XGBoost模型

在LightGBM模型中，我只用了数值类的信息（点击率和相似度）作为输入，没有用分类数据，这样的速度非常快，只用了不到十分钟。令人惊讶的是，LightGBM（方法五）得到的模型比XGBoost得到的要更好（排行榜分值0.67073）。我的假设是高维分类的分类变量使独热编码更难得到一个对树预测准确的随机集合。事实上，一些竞赛者用原始提供的分类（不是独热编码或特征哈希）所得到的单一GBDT模型得到了高于0.68的排行榜分值，可能是因为上千个分类树模型在GBDT集成中能够忽略干扰并为这些分类建模。

我用了LightGBM命令行界面训练并预测模型，我所得到的最优的超参数展示在下图。

现在，通过使用一些基础的统计和树集成，我的排行榜分值相比基准值有显著的提高。在该文的后半部分中，我将介绍解决预测点击率问题最强大的机器学习模型和集成工具，正是它们让我上升到排行榜第19位（前2%）。