一种基于实时CTR的移动应用商店内容推荐改进算法

冯欣，夏旸

（长春理工大学 计算机科学技术学院，长春 130022）

一种基于实时CTR的移动应用商店内容推荐改进算法

冯欣，夏旸

（长春理工大学 计算机科学技术学院，长春 130022）

针对内容信息过载，冷启动等导致移动应用市场用户消费受限、广告收入受阻的问题，文章提供一种能够提高移动应用市场人均分发能力的内容推荐算法。首先，收集一段时间内产生的内容推荐数据，作为待处理的推荐内容集合。然后，通过一种改进的实时CTR推荐算法，对已有内容进行基于展示、点击、下载的重新排列，并将重新排列的数据展示在移动应用市场内部。与传统的CTR推荐算法相比较，改进后的实时CTR推荐算法在评价维度上更加合理。通过对比，改进后的实时CTR推荐算法可以提高移动应用市场的分发能力，适用于信息过载下的移动应用市场。

移动应用市场；内容推荐；CTR

智能手机、高速网络以及各种各样的移动应用为人们创造了丰富多彩的生活［1-3］。从聊天交友，分享生活精彩到办公软件，再到影音娱乐和电子商务，人们越来越离不开这些应用，需要这些应用来进行娱乐和管理自己的生活［4，5］。2015年是移动应用爆发增长的一年，GooglePlay全球应用年度下载量与2014年相比实现了将近100%的增长，IOS应用商店全球应用年度收入同比显著增长，可见，作为移动应用分发主要来源的移动应用市场，在这一年中扮演了至关重要的角色［6］。

由于政策等原因，Google Play无法为我国大陆地区的安卓用户提供相关服务，经过几年发展，国内的主流移动应用市场包括应用宝、360手机助手、PP助手、豌豆荚、以及其他手机品牌自有的独立应用商店均占有很大一部分用户，根据艾媒咨询发布的2015～2016中国手机应用商店年度报告显示，截止至2015Q4，第三方手机应用商店的活跃用户规模已达4.40亿，然而2014年相对2015环比增长仅为0.92%［7］。

图1 国内第三方安卓应用商店活跃用户规模图示

随着活跃用户抵达天花板，如何在接近稳定的用户群中，进一步提高移动应用市场应用分发的能力和广告的收入，成为了各大移动应用市场需要思考的问题［8］。

1 内容推荐算法综述

1.1 协同过滤推荐算法

协同过滤的概念是由Goldberg Nicols Oki及Terry在1992年首次提出的，作为协同过滤推荐的雏形，该算法展示了一种新的推荐思想，其后，出现了基于评分的协同推荐系统，比如用于新闻和电影网站的GroupLens［9-12］.

目前，主要分为两类协同过滤推荐算法：基于用户的协同过滤推荐算法［13］和基于物品的协同过滤推荐算法［14］。其中，前者基于这样的一个假设，即若目标用户的最近邻居（最相似的若干用户）用户群对某项目的评分比较相似，算法便根据这些评分来逼近目标用户对该项目的评分。基于物品的协同过滤算法认为，用户对不同物品的评分存在一定的相似性，当需要对某用户对一个物品的评分时，可根据用户在历史上对该物品的若干相似物品的评分来评估评分。

1.1.1 基于用户的协同过滤推荐算法

采用该算法为目标用户Ui（i=1，2，…，n）确定给定物品Ij（j=1，2，…，n）的评分Pij，通常分为以下步骤：

（1）计算目标用户Ui和其他为Ij评分过的用户之间的相似度，其中为Ij评分过的用户集合记为U*

（2）根据所有Uk∈U*对项目Ij的评分来估算Ui对Ij的评分。

若把用户评分作为n维向量空间上的向量，则用户相似性可通过向量间余弦表示：

然而向量的余弦相似度并没有考虑用户评分的极端问题，修正的余弦相似度方法通过减去用户对项目的平均评分来改善评分落差巨大的问题，用户i和用户j之间的相似性表示为：

其中，Ri,c表示用户i对物品c的评分，Rj,c表示用户 j对物品c的评分，Rˉi与Rˉj表示用户i、用户 j对自己已评分项目的平均值。

根据上步得出的用户相似性，进而计算用户Ui对物品Ij的评分：

1.1.2 基于物品的协同过滤推荐算法

就目前移动应用市场的情况来说，虽然每天有大量的新应用上架，然而同质化趋势却日趋严重，因此可以认为，需要被推荐的项目数量保持了相对稳定，由此计算出的物品相似度矩阵更新频率比较低，可以在比较长的一段时间内应用。这一特点恰好为采用基于物品（item-based）的推荐算法带来了可能。该算法概括起来一般包括以下三个步骤：

（1）内容抽象（Item Representation）

在现实生活中，一个item通常都会有一些可以用来描述其自身的属性，而这些属性通常又分为结构化属性和非结构化属性。对于结构化的属性，它们是一些很容易定义的，意义明确的属性；而对于非结构化的属性，往往要把它转化为结构化的属性后才能使用。其中应用内容推荐就是一个使用场景。

（2）用户特征的学习（Profile Learning）

利用一个用户过去喜欢的item的属性数据，通过机器学习得出该用户的喜好特征（profile）；加入一个用户user1对一些item做出了喜好的判断。那么，这一步就是根据用户user1的喜好数据来建立一个模型，并以此来推断user1是否会喜欢上一个特定应用item。所以接下来需要解决的就是一个采用某分类算法的机器学习过程，常用的学习算法包括：最近邻居方法、决策树算法，线性分类算法，朴素贝叶斯算法等。

（3）推荐内容的生成（RecommendationGenera⁃tion）

这一步基本就是根据学习得到的用户特征与item特征进行相似度的判断，然后为用户推荐一组与其相关性最大的item。

上述3个步骤的大体流程图如图2所示。

图2 以app为例的推荐流程图

2 存在问题

2.1 冷启动问题

无论是基于用户还是基于物品的协同过滤推荐，冷启动［15-17，19］都是一直以来让使用者头疼的问题。

随着移动应用市场收录的条目增长以及用户规模的进一步扩大，用户数量和应用数量快速增长，导致用户-物品评分表经常需要反复计算用户或物品之间的相似性，进而导致算法的耗时不断升高，另一方面，当一个新用户或者新应用进入移动应用市场时，相关的评分都是空白，所形成的相关性推荐并不准确，这也导致推荐结果的可靠性在不断下降。

考虑两种情况：

1.1.1的推荐中，如果被推荐者是一个新用户，那么就不会有任何的消费记录和喜好倾向，故而无法找到和该用户相似的用户，也就无法进行推荐。

1.1.2的推荐中，针对物品进行条件抽取已经十分困难并必然伴随着抽取不完全的情况，无法很好的将该物品分类，也就无法进行推荐。

2.2 推荐速度问题

随着用户数和应用数的增多，协同过滤算法的计算量也在迅猛增长。当内容推荐所面临的用户规模达到数百万甚至更高级别时，推荐算法面临的可扩展问题将会十分严峻。对于在线服务，推荐的实时性显得至关重要，然而对于时间复杂度为O(n2m)的协同过滤算法来讲，计算开销非常大，虽然可以通过降维、聚类、分类等方法能够在一定程度上缩短计算开销，然而这些措施本身也占用了大量的时间。

2.3 物品本身特征提取问题

虽然对文本信息的特征提取技术已比较成熟，但是对于一个本身具有多媒体属性的app来说，其特征提取技术依旧进展缓慢，目前的移动应用市场主要采用开发者对app进行标签分类的方式标注一个app的特征信息，这一方法在推荐的灵活性上较差。

2.4 其他问题

除了上述问题之外，移动应用市场还面临着app刷榜刷量［18］、隐私问题、非注册用户行为收集困难等问题。对于这些问题，现有的大多数推荐算法都无法令人满意，只有通过一些人工的运营方式来进行干预。

3 CTR推荐算法

CTR（Click-Through-Rate）是一个互联网广告常用语，即网络广告（图片、文字、关键词、排名、视频等广告形式）的到达率，也成点击率，其计算公式如下。

基于CTR进行的推荐算法主要分为两大部分，即CTR的实时计算和对CTR进行预估，其中对CTR进行的实时计算一方面可以用来进行内容推荐，另一方面，也为内容的CTR预估提供了历史数据。

一个CTR实时计算系统的架构图通常如图3所示。

图3 一种实时计算系统的架构示意图

客户端将内容的CTR原始数据上传至服务器，服务器端通过CTR实时计算系统生成该内容的实时CTR数据，并将该数据存储于CTR数据库中，该数据库需要满足高并发性［20］。当服务器开始计算预估CTR时，CTR预估系统调用已有的实时CTR数值，来进行计算，并将计算结果上传至内容推荐系统，内容系统根据CTR队列，将内容抽取出来并排序，推送给客户端，最后呈现在用户面前。

3.1 单纯CTR排序算法

该算法关注特定内容组合的最优排序，以期实现一定时间段内所展示页面的平均CTR最高。

假设某特定内容 j在不同的位置i上的CTRi,j恒定，每个位置的曝光占比Impri恒定且递减。

排序方法：在某一时间段内，CTR越高的内容所获得的曝光量越大，进而使整体内容的平均CTR最高。即通过历史CTR数据进行内容的CTR预测，通过调整内容的位置i来控制曝光量，从而给出最优排序，公式表述如下：

然而上述算法中，同一内容在不同位置上的CTR很有可能不恒定，当波动大于某一阈值时，假设的前提将不存在。

3.2 实时CTR预测排序算法

在单纯CTR排序的基础上，缩短计算CTR和生成新推荐序列的时间，每个小时计算一次下个小时某内容的CTR预测值，使每个小时的预测值都尽可能接近真实值，并据此调整推荐内容序列，使全天的平均CTR更高。

误差检测

针对部分内容和整体内容，采取下边两个公式进行预测CTR值的误差检测：

4 实时CTR排序算法改进

4.1 一种结合分发效率调权的实时CTR排序算法改进

在移动应用市场领域，除直接下载带来的分发行为外，非直接下载的点击行为也有一定概率转化为下载行为，可以通过离线计算的方式来统计这部分非直接下载点击行为转化到下载行为的转化率，记为c，当前内容的分发效率记为Ri( ) consumption，从而得出每一个内容的排序值：

其中，CTRi为实际计算得出的真实值，如果是首次推荐的内容，其CTR值和分发效率需要一段时间计算得出，并且在这段时间内要保证其有充足曝光，因此会为初次推荐的内容指定一个初始的R值，有

其中，Ravg和Rmax为当前页面排序值的均值与最大值，m为一个随机数，目的是为了调整Rj上限。通过这样的一个公式，可以保证首次推荐的内容有足够的曝光量，也利于后续计算CTR值与分发效率。

4.2 实验结果

将改进前后的推荐算法分别运用到同一组内容上去，通过观察一段时间内的数据反馈情况，得到如下结论。由实验结果可以看出，执行了分发调权改进算法的实验组在人均分发和消费渗透率这两个数据指标上均优于未采用改进算法的对照组，所以可以说，针对实时CTR推荐算法的改进是有正向作用的。

图4 算法改进前后人均分发情况对比

图5 算法改进前后分发渗透率情况对比

5 结论

国内移动应用市场发展至今，其大部分的流量已经被百度、腾讯、360等几家互联网巨头牢牢占据，为了能够在竞争如此激烈的市场中保持健康而持续的状态，其他独立和第三方移动应用市场唯有在已有的流量渠道之下，进一步提升各项分发指标，找到适合自己生存的商业模式，辅以恰当的内容推荐技术，将自己的分发能力不断提高。笔者通过对协同过滤推荐算法进行综述，指出了其过于依赖计算资源，反馈不够及时，受信息矩阵稀疏性影响大导致推荐结果失准等问题，也通过提出一种基于实时CTR推算算法的改进，该改进的算法在内容池确定的情况下，能够使移动应用市场的分发能力进一步提升，然而，一个完整的移动应用市场生态并不是任何单一技术能够支撑起来的，而是多种技术协作而成。因此，越来越多的应用分发厂商选择走向了混合推荐的路线：将固定展示的内容根据展示下载等影响因素进行排序推荐，将即时更新的内容或个性化内容通过协同过滤、内容匹配推荐等其他算法进行推荐，以几种算法结合而成的混合推荐系统来不断提高自身的分发能力。

同时，缺少了谷歌的国内安卓市场，如何保证App的渠道来源正规，如何区分山寨应用，也是各大应用市场急需解决的事情，混乱的现状需要规范的引导的同时，也存在着很大的机遇，希望国内的安卓应用市场可以为用户提供优质可靠的服务。

［1]北京大学媒介研究中心.移动分发市场研究报告［EB/ OL］.http：//www.looec.cn/detail-6188727.html，2014.

［2]蔡可.基于用户采纳的手机商店研究［D］.武汉：华中科技大学，2010.

［3]闵栋，刘东明.移动应用商店跟踪研究［J］.电信网技术，2010（2）：13-18.

［4]翁昱.移动应用盈利模式研究与分析［J］.商业文化（下半月），2012（10）：5.

［5]李晓宾.中国移动应用商店商业模式评价研究［D］.北京：北京邮电大学，2012：8-15.

［6]App Annie.全球移动应用市场2015年回顾［R］.App Annie，2016

［7]艾媒咨询.2015-2016中国手机应用商店年度报告［R］.艾媒咨询，2016

［8]陈婉玲，范久红.我国移动应用分发平台发展仍受制约，突破瓶颈须探索模式创新［J］.世界电信，2014（11）：43-48.

［9]Arwar B，Karypis G，Konstan J，et al.Analysis of rec⁃ommendationalgorithms for E-commerce［C］.In：Pro⁃cessing of 2nd ACM Conferenceon Electronic Com⁃merce，2000：158-167.

［10]Wang Zhi-mei，Yang Fan.P2P recommendation algo⁃rithmbased on hebbian consistency learning［J］.Com⁃puterEngineering and Applications，2006，42（36）：110-113.

［11]You Wen，Ye Shui-sheng.A survey of collaborative filteringalgorithm applied in E-commerce recommend⁃er system［J］.Computer Technology and Development，2006，16（9）：70-72.

［12]Wu Yan，Shen Jie，Gu Tian-zhu，et al.Algorithm for sparseproblem in collaborative filtering［J］.Application Research ofComputers，2007，24（6）：94-97.

［13]Wang Wei-ping，Liu Ying.Recommendation algo⁃rithm based oncustomer behavior locus［J］.Computer Systems&Applications，2006，15（9）：35-38.

［14]Deng Ai-lin，Zhu Yang-yong，Shi Bai-le.A collabor⁃ativefiltering recommendation algorithm based on item ratingprediction［J］.Journal of Software，2003，14（9）：1621-1628.

［15]于洪，李俊华.一种解决新项目冷启动问题的推荐算法［J］.软件学报，2015（6）：1395-1408.

［16]孙冬婷，何涛，张福海.推荐系统中的冷启动问题研究综述［J］.计算机与现代化，2012（5）：59-63.

［17]孙小华.协同过滤系统的稀疏性与冷启动问题研究［D］.杭州：浙江大学，2005.

［18]孙飞飞，张淇人.APP刷榜黑幕调查［J］.IT时代周刊，2012（5）：29-34.

［19]Bobadilla J S，Ortega F，Hernando A，et al.A collabor⁃ativefilteringapproachtomitigatethenewuser cold start problem［J］.Knowledge-Based Systems，2012，26：225-238.

［20]王欢，赵建平，姜晓明，等.高并发性Web应用平台研究与实现［J］.长春理工大学学报：自然科学版，2015，38（3）：144-147.

An Improvement of Content-Recommend Algorithm Based on Real-time CTR in Mobile Market

FENG Xin，XIA Yang
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

For the content and information overload，cold start and others as results of the limitation of mobile application market users’consumption and the obstruction of advertise revenue，in this paper，a content-recommend algorithm to improve the con⁃sumption ability of the mobile application market for each consumer is provided.First，the recommended content datum generated within the period are collected as the pending set.Then，through an improved real-time CTR recommendation algorithm，the existing contents based on their impressions are rearranged，clicked and downloaded，then the result in mobile application market is displayed.Compared with the traditional CTR recommendation algorithm，the improved real-time CTR recommendation algo⁃rithm is more reasonable in the evaluation dimensions.By contrast，the improved real-time recommendation algorithm can im⁃prove the distribution capabilities of the mobile application market，especially for those with the problem of information overload.

mobile application market；content-recommend；CTR

TP391

A

1672-9870（2017）02-0122-05

2016-08-25

冯欣（1973-），男，博士，副教授，E-mail：1203511908@qq.com