TalkingData大规模机器学习的应用

TalkingData诞生于2011年，目前提供应用统计分析、游戏运营分析、移动广告监测、移动数据DMP平台、移动行业数据分析和洞察，以及企业级移动数据分析和挖掘的解决方案等产品和服务。随着各项业务快速发展，需要机器学习支撑的需求也越多越多，数据规模也越来越大，带来很大的挑战。而且TalkingData作为一个新兴企业，资源相对有限，没有办法通过大量增加硬件资源、增加计算能力来应对大数据问题，这给我们带来了更大的挑战。本文将简要介绍我们应对这些挑战的一些经验。

计算平台

TalkingData的数据处理集群目前仅有32台机器，除了承担机器学习任务外，更多的工作是数据处理，集群的负荷是非常繁重的。为了尽可能提高集群计算效率和程序开发效率，我们选择了Spark。我们认为Spark最大的两个优点。一是数据处理效率高（相对于Hadoop MapReduce而言）。二是开发效率高，Scala语言的特性和Spark的DAG机制使得复杂的数据处理流程和计算逻辑能够很简洁地编写，虽然Scala语言的特性也非常多，但是Spark对Scala语言的掌握程度要求不高，对一般程序员而言，一周时间足够掌握，而且程序开发效率相比Hadoop MapReduce能够提高一倍以上。 而且Spark社区的发展也很快(活跃开发者人数已经超过Hadoop MapReduce)，能够得到较好的社区支持和未来更多新功能。当然也有人质疑Spark在大规模集群上的稳定性，但对我们来说目前这还不是一个问题。

算法分析

大数据给机器学习带来了很大的机遇，也给机器学习带来了很多的挑战。大量的训练样本和丰富的特征维度，使得学习算法更容易学到较好的模型。数据更新速度很快，我们也可以更快地更新模型。同时，由于数据规模的增大使得机器学习算法的效率问题越来越突出。首先，从算法复杂度来说，有些算法的复杂度与训练样本数（如SVM）或者特征数量（如决策树）的关系是超线性关系。有一些模型学习中用到的优化方法，如牛顿法，需要计算训练特征维度规模的海塞矩阵的逆矩阵及其乘法，其计算复杂度为 O(n^3)）。随着数据量和特征数量的增长，模型训练的计算量急速增加，使得训练时间变得越来越长而不可接受。而硬件数量的扩充，带来的计算效率提升往往是低于线性的增长。因此，在进行大数据问题时，我们始终面临着计算资源相对不足的问题。

为了解决计算复杂度的问题，也出现一些计算量较小的优化方法，如随机梯度下降（Stochastic Gradient Decent）、小批量梯度下降（mini-Batch Gradient Decent）等方法。但是，机器学习算法大部分都是迭代算法，需要反复使用数据多次，而在处理大规模问题的时候，训练数据集可能无法全部装载到内存中，而需要一次一次的从分布式文件系统中读取，带来巨大的重复I/O开销。即使Spark这样具有In-Memory计算能力的分布式计算框架，同样受制于集群资源和任务队列资源的限制，很多情况下并不能够把训练数据全部装载到内存中，还是需要多次从分布式文件系统中读取数据文件。

数据迭代是机器学习算法处理大数据问题的“阿格硫斯之踵”。因此，尽可能降低算法迭代次数，是提高大规模机器学习任务的有效方法。在实践中，我们尽可能使用那些只需扫描数据一遍的算法。 如用SimHash来进行聚类， 用关联表算法来做推荐等。同时，我们也会优化算法实现，使其无需迭代即可训练出较好的模型，如随机决策树算法（Random Decision Tree）、线性回归(Linear Regression)和逻辑斯特回归（Logsitic Regression）等。另外，虽然我们以Spark为计算平台，但是并没有太多的使用Spark内嵌的MLLib来完成机器学习任务。最主要的原因也是因为MLLib中的算法基本都是迭代算法，其效率达不到我们的要求。

实际应用

TalkingData的业务比较多，需要机器学习提供支持的地方也比较多。目前大致可分为四个方面：移动应用推荐，广告投放优化，用户画像和游戏数据挖掘等四大块。这里分别简要介绍下这几个方面的工作。

【移动应用推荐】

TalkingData为几家移动应用市场提供过移动应用推荐解决方案如机锋和同步推，使用用户的下载和浏览行为数据，来进行移动应用的关联推荐和个性化推荐。但是这种外包模式显然无法充分利用我们的数据优势，也不是一种便捷的服务提供模式。前几年当推荐系统成为工业界和学术界都非常关心的技术时，国内外都出现了以提供推荐系统解决方案的公司。但目前这些公司都已经转型，比如MyStrands.com, 目前已专注于提供金融客户数据管理和分析工具，而不再把推荐系统解决方案作为重点。

实践已经证明第三方提供技术解决方案（包括提供SaaS服务）的模式并不具备很大的市场。我们通过这些外包项目，发现这种模式最大的问题在于数据的收集处理。如果我们要求客户按照我们提供的数据格式，为我们准备好数据，则会给客户带来很大的负担。由于客户对推荐系统了解不多，对于如何把已有的数据映射成我们的数据格式通常会感到比较困惑，而难以正确完成。而如果我们根据用户提供的现有数据进行转换，又使得我们的服务难以标准化而快速复制。另外就是一旦我们把推荐系统交付给客户后，我们也很难给客户提供持续及时的效果优化服务。

因为上述这些问题，我们的推荐系统服务，就从提供外包转向了提供轻量级的移动应用推荐服务接口。这一服务也可以算是一种SaaS模式，但是与之前其他公司提供的推荐SaaS服务的重大区别是我们不需要客户提供推荐模型训练数据，客户仅需要调用我们的接口获得关联推荐和个性化推荐的结果。这就样也就没有转换客户数据的问题，从而极大地降低推荐系统服务的使用门槛。而通过SaaS服务，我们也可以持续优化和升级推荐算法的效果。

我们能够提供这样的服务，主要是随着TalkingData积累的数据量越来越大，我们逐渐积累了大量的移动应用使用情况数据，这些数据比下载和浏览行为数据能更准确地反映用户的移动应用兴趣偏好，我们完全具备了不使用客户的数据而提供更好的推荐结果的能力。移动应用服务是作为TalkingData DMP里的一组接口向外提供服务的，我们将其作为TalkingData向外提供数据能力的一个出口。目前TalkingData推荐服务接口，每天要处理上亿的移动应用使用行为Session来建立推荐模型，覆盖30万以上的移动应用。现在，已经有一些移动应用换量平台使用我们的服务接口，也有一些移动应用市场准备尝试使用我们的推荐接口来为用户提供移动应用推荐。

近些年来，推荐算法是数据挖掘，机器学习学术会议上非常热门的主题之一。可以说相关的文献是汗牛充栋，各种新算法和算法改进层出不穷。Netflix悬赏100万美元的推荐系统竞赛更是推动了推荐算法研究的热潮。然而众多的推荐算法，在实际应用中并不是那么好用。首先对于最基础的协同过滤算法，即通过计算用户或者物品之间相似性的方法，由于其计算复杂度与用户或者物品的数量是超线性的关系，而且需要计算矩阵乘法，难以并行化，用来处理大规模问题比较困难。而基于矩阵分解的方法，除了效率问题外，就是难以保证有较好的训练数据。因为这些算法的假设是基于每个用户和物品都有足够多的评分，但是实际上这是不可能的。另外，矩阵分解算法的目标是预测评分值与实际评分值最小化， 而实际应用中我们真正关心的是用户对不同物品感兴趣程度的排序。最小化评分误差，是否就能最小化排序误差？当然，也有一些矩阵分解算法被提出来用以最小化排序误差，但是其计算量的增长又是十分巨大的。

因此，我们基于现实的数据情况（都是隐式反馈，设备规模较大， 和应用较多）， 采用了在工程上比较好实现，计算效率较高，结果也较好解释， 但是一点也不先进的算法，或者说算法框架—关联表。关联表算法原理比较简单，可以看做是对关联规则挖掘的一种简化。该算法通过统计物品两两之间同时出现的频次（如一个设备在一段时间内使用了哪些应用），构建出物品到物品的关联表。在进行关联推荐时，通过在关联表中查找目标物品的Top N关联物品进行推荐。而在进行个性化推荐时，使用用户最近有行为的那些物品分别查询关联表，然后再合并这些结果作为最后的推荐结果。

下面是一个关联表构建和使用的例子：

基于以上的关联表，做Top 2的关联推荐时, 如果目标物品是a2, 推荐的结果是a5和a3(排除a2)。如果要做Top 2个性化推荐，有d11: a1, a2, 用a1查关联表(a1, a2)得到a5(3), a3(2), a4(2)用a2查关联表得到a5(5), a3(4), a4(3). 合并以后得到a5(8), a3(6), a4(5), 取前两个为a5, a3。在此基础上，根据实际情况的需要，我们还需要对关联表的结果进行去流行，已避免推荐出来的全都是最流行的那些应用，在这里就不详述了。

为了平衡长期兴趣和短期兴趣，我们采用不同时间内的数据建立关联表，比如一个月，一周和一天的数据分别建立关联表。也可以使用不同的数据源来建立关联表，比如使用应用的数据和安装应用的数据。然后再通过多个关联表的加权结果来获得最后的结果。实际上，除了用用户行为数据来统计应用之间的关联程度来建立关联表外，还可以使用其他的数据和方法来构建物品两两之间的关系。比如为了解决应用的冷启动问题，我们使用应用的介绍文本，采用文本处理的一些技术建立应用之间的关联关系。因此，我们推荐系统的核心就是一系列这样的关联表。在做推荐时，通过一定的规则根据输入参数查询各个关联表，然后融合也这些关联表的结合，作为最终的推荐结果。关联表方法，从算法的角度上看无疑是十分简单的，但是是非常适合工程化的。从我们的实践来看，在很多情况下，在精度上并不比先进算法有太大的差距。

【广告投放优化】

TalkingData积累了大量移动数据，完全具备进行广告精准投放的能力。但是作为第三方数据平台，我们严守中立，不会从事任何具体的广告投放业务，我们仅仅是为移动广告生态系统提供数据能力，提高整个生态系统的效率。

我们的移动DMP可以提供移动设备的应用兴趣等标签，广告主、网盟、DSP都可以通过我们的DMP平台来获得受众数据来优化广告投放。但是也有一些合作伙伴，希望我们能够直接提供投放的目标设备或者媒体。为了提供较好的结果，我们使用超过1.5亿移动设备使用行为作为训练数据，特征空间超过180万维，以使用过投放目标应用的设备为正样本进行训练。为了能够对所有设备进行预测并输出所有应用与目标应用的关系，我们选择使用Logistic Regression算法进行训练。Logistic Regress也是处理大规模分类问题的常用算法，模型和训练过程相对简单，模型的可解释性也强。

但是这个规模的问题，如果采用一般的算法实现，如MLLib的实现，在我们的集群上最少也需要几个小时的时间进行训练， 这会长时间占据集群资源影响其他任务的完成。 而且这个学习问题，除了数据规模比较大以外，还有一个挑战就是正样本数量通常较少。因为需要投放广告的应用，通常使用的用户不会太多。我们遇到的情况，正样本从几百到几百万都有，但即使是几百万的正样本，相对于1.5亿的训练样本，正样本比例也是极低的，不过千分之几。在这种情况下，一般很难训练得到较好的模型，我们使用过MLLib的LR算法进行训练，即使有几百万的正样本，模型的AUC指标也仅比0.5高一点，基本不具备区分正负样本的能力。

这种情况下，一般可以对训练数据采样来增加正样本的比例来改善的学习结果。采样有两种方式，一种是增加正样本数量，另一种是减少负样本数量。前者会增加训练样本的数量而增加计算量。而后者又因为用户行为数据是稀疏数据且维度很高，如果丢弃大量的负样本，就会丢弃大量的特征，使得在预测时对只有这些特征的设备无法进行预测。因此我们不希望通过调整样本比例的方式来解决这个问题。为了解决训练效率和样本偏倚的问题，我们优化了Logistic Regression算法求解的过程，使得训练过程只需要扫描数据一遍即可达到收敛，而且在样本偏倚很严重的情况下也能达到较好的效果。在仅占用集群8%资源的情况下，Logistic Regression算法仅需5分钟即可完成具有180万维特征，1.5亿样本的训练。从测试情况来看，在正样本较多的情况下（几十万到几百万），AUC基本都在0.7以上，很多时候超过0.8，甚至0.9。而在正样本较少的情况下（几百到几千），一般也能达到0.6以上的AUC。 从实际广告投放情况来看，通常能提高50%以上的转化率。

虽然Logistic Regression算法已经优化得很快了，但是在有多个优化任务的时候，还是可能会感到速度太慢。曾有过要跑500个任务的情况，一个任务跑5分钟，就需要2500分钟，接近42个小时。实际上500个任务，就需要扫描数据500次，这是最大的开销。实际上，对于这500个任务，使用的都是同一份数据。其格式如下：

设备id, 应用1， 应用2， 应用3……

只是每个任务会指定一个应用为学习目标，其余的应用则为特征。把原始数据根据指定应用加工成训练数据，这在Spark中是非常容易完成的。但是每个任务都这么干一次，就会多次的读取这个数据。显然，这是非常不经济的。要提高效率，就需要消除这些冗余IO操作，只进行一次数据读取。因为我们的算法是在每个数据分片上对数据逐条处理，因此对一条数据，进行多种不同的处理并没有难度，只是在最后的Reduce阶段，需要对不同分片上不同任务的模型结果进行整合，这在技术上不是什么难题。批量训练程序的效率是非常高的，对于500个任务，批量训练程序只需要50分钟就可以完成训练，训练时间缩短到原来的2%。平均一个任务（有1.5亿训练样本，180万的特征空间）的训练时间为6秒。批量训练程序的限制在于内存，任务越多，对应的模型越多，占用的内存就越大。目前的数据情况能够支撑大约1000个模型。

【用户画像】

TalkingData积累的数据以移动设备的行为数据为主，无法直接获得设备的兴趣标签。而DMP向外提供数据时，又必须以标签的形式向外提供数据，而且直接提供行为数据也对隐私保护不利。目前主要是利用移动应用的标签（由我们的专业团队人工标注）和设备使用应用的数据对设备进行标签标注。除了为每个设备画像，有时候我们需要对某个或者某类应用的使用者进行群体画像。

我们曾通过直接统计用户群使用过的其他应用比例作为用户画像的基础，但是发现由于应用活跃程度的长尾效应，不管是什么人群，使用率最高的应用基本都是微信，QQ这些平台级应用，也就没有办法总结出这个人群的特征了。而如果将这个人群的各个应用的使用率除以所有设备上的应用使用率，得到应用使用率的提升率，又会突出那些使用率很低的应用。通过调整公式和参数，可以在提升率和使用率之间做一些妥协，但很难达到理想的状态。

为了解决这个问题，我们将这个问题作为分类问题，使用Logistic Regression模型来处理，以获得模型中各个特征（即应用）的系数作为关联程度的分值，取得了非常好的效果。这个学习问题与广告投放优化中的问题是完全一样的，都是以某个或者某些应用的使用设备为正样本，其他设备为负样本，而以其他的应用作为特征，训练Logistic Regression模型，从而得到各个应用与目标人群的关联程度。

从训练得到的结果来看，流行度高的应用都得到了抑制，而关联程度高的应用使用率也不会太低。得到了人群的关联应用后，可以再利用这些应用的标签为这个人群标注兴趣标签。用这个方法，我们为招商银行掌上生活，和一些广告的受众人群做了画像，都取得了比较好的效果。

【游戏数据挖掘】

TalkingData的游戏运营分析平台，是国内手游运营分析工具的开创者。目前为超过3万款游戏服务，其中包括消灭星星、植物大战僵尸这些非常受欢迎的游戏。游戏运营分析平台可以看作应用统计平台的游戏专业版，在数据收集上增加了游戏相关的一些标准事件如升级，虚拟币消费，付费等。

因为TalkingData的游戏运营分析平台的定位，不仅仅是提供统计指标，还需要一定的预测能力，为游戏运营方预测哪些用户可能流失，哪些用户有可能付费。流失预测和付费预测，都是分类问题。因为我们需要考虑同时为3万多款游戏提供这样的预测，我们没办法逐个分析和抽取每款游戏收集的数据，特别是自定义事件来作为训练的特征。因此从规模化的角度考虑，我们立足于使用十几个标准化事件的数据作为特征。

而对于自定义事件，我们也将其作为标准化事件来使用，仅使用自定义事件的总次数，和出现的不同的自定义事件的种数作为特征。我们认为一个玩家产生的自定义事件的次数和种类，与玩家对这个游戏的兴趣和投入程度应该是正相关的。这样，既能利用一些自定义事件的信息，但是又不需要对每个游戏的自定义事件做深入分析。当然，这个方案是预测精度向工程可行性的妥协方案，必然是要损失一定的精度。但是从我们的测试结果来看，预测精度还是可以接受的。这个工作与前面提到的广告投放优化问题，在规模上也有一些不同。对于每一个游戏而言，都不是一个大规模的机器学习问题，训练样本和最多也就百万规模，而特征数量仅有十几维。用我们优化过的Logistic Regression算法，这样的规模单机训练仅需要十几秒的事件即可完成计算。但另一方面，因为需要支持所有游戏，每次需要训练3万多个模型。

这种情况下，运用Spark的并行能力来加速每个任务的训练速度没有什么意义，反而会因为多节点之间的同步问题，浪费掉不少计算能力。因此，我们在每个游戏的训练数据和预测数据处理好以后，把每一个游戏的数据Shuffle到一起，然后在Reduce过程中进行单机的Logistic Regression算法模型训练，然后进行预测。实际上，这里利用了Spark的并行能力来调度多个单机任务在集群上执行。

总结：机器学习能力服务化

前面介绍了我们在机器学习方面的一些工作。最后，总结一下我们的一点工作经验。TalkingData作为一个数据公司，很多业务都需要机器学习能力的支持，而我们的机器学习团队规模并不大，无法对每一个业务需求都做到及时响应。比如广告投放优化的工作，每次业务部门接到客户的需求，都需要来联系我们，让我们跑结果。这种方式让我们经常要干一些重复劳动，每次修改一下脚本，然后向Spark集群提交任务，跑出结果，再筛选设备和媒体出来。而客户的需求也得不到及时的响应。

为了解决这个问题，我们就把这个机器学习的能力进行了服务化，提供了Web界面给我们的业务部门使用。他们收到客户需求后，就不需要再找我们了，而是直接使用Web工具，自动生成结果。这个工具几乎不涉及机器学习的专业知识，使用者仅需要指定投放的目标应用是哪一个就行。这样，我们免去了一些没有太多意义的重复性劳动，又让业务部门不再需要依赖我们来跑结果，提高了双方工作效率。

移动应用推荐服务接口也是一个机器学习能力服务化的例子，我们把为客户部署推荐系统，改为了提供推荐服务，而且进一步利用了我们的数据能力，降低用户使用门槛。而我们也可以把精力集中在提供更高质量的标准化服务，而不是为客户的需求变化而疲于奔命。

基于这些经验，我们认为一个机器学习团队，不仅要能提供好的机器学习能力（高效精准的算法），还需要把这些能力尽可能的服务化，为其他部门或者是客户提供简单易用的机器学习服务。机器学习团队的工作应该是不断解决新的问题，把这些问题的解决方案固化成服务给公司内外的用户来使用。当我们解决了一个问题时，就不要再让这个问题成为我们的日常性工作，而牵扯我们解决新问题的精力。

作者简介：张夏天，TalkingData首席数据科学家，负责TalkingData机器学习和数据挖掘工作，为TalkingData的数据产品和服务提供支持。曾在IBM中国研究院、腾讯数据平台部和华为诺亚方舟实验室任职。对大数据环境下的机器学习、数据挖掘有深入的研究和实践经验。

<="" div="" style="">