移动互联网广告推荐算法研究*

张铭芮，刘建毅

（1.北京邮电大学世纪学院 北京 102613；2.北京邮电大学计算机学院 北京 100876）

1 引言

近年来移动终端的用户数量增长迅猛，手机逐渐成为继电视、广播、报刊、互联网之后全新的媒体形式，是极具发展潜力的广告新媒体。传统的短信和WAP广告由于投放行为与受众的兴趣不相符，虽然数量众多但有效性难以提高。传统广告的强势使得移动用户在浏览网络信息时，往往被动地接受一些并不感兴趣的广告内容，这些非相关广告会干扰用户正常的访问和浏览，甚至会泄露用户的个人隐私，因此用户对这种“地毯式轰炸”的广告普遍持反感态度。面向用户需求的智能广告，根据用户的个人兴趣和行为，挖掘用户的潜在购买需求，按需投放广告，其目标客户群价值更高、消费者接触面更广、价格更低、品牌影响力更高，代表着移动广告业智能化的发展方向，具有广阔的应用前景。

目前，学术界和工业界尚未见到专有的移动互联网广告推荐理论和技术，其主要借鉴互联网广告推荐理论技术，主要有搜索引擎广告（sponsored search）和上下文相关广告（contextual advertising）两种[1]。

搜索引擎广告是指显示在搜索结果页面上的网站链接广告。搜索引擎接收到搜索请求后，除了返回匹配网页外，还返回与查询关键词相关的广告。目前比较有名的搜索引擎广告系统包括Google的AdSense Program、百度的竞价排名服务等。搜索引擎广告的研究主要集中在广告关键词优化、广告点击率预测、竞价排名、查询词重写等方面[2～6]。

上下文相关广告是指显示在新闻网页上的与当前网页主题接近的广告。上下文相关广告系统的核心假设是:如果用户对一个网页感兴趣，那么他很有可能对与网页内容相关的某个广告感兴趣。网页与广告的关联是这种广告形式的核心技术，即在网页上显示与网页内容相关的广告[7]。比较有名的上下文相关广告系统有Yahoo的Contextual Match Product、MSN 的 Online Advertising Platform 以 及 天下互联的“窄告”。

网页与广告的关联技术可进一步细分为关键词相关和内容相关。关键词相关广告通过分析网页内容，利用语法或语义方法抽取网页的关键词，通过与广告商的广告关键词进行匹配选取广告[8～11]；内容相关广告利用对网页和广告内容进行相似度计算选取广告[12～14]。然而，仅仅依靠网页与广告在文本内容上的关联是不够的，对于一个“抱怨本田车安全”的网页，如果按照内容相关性推送关于“本田车”的广告就会引起用户的反感，为此有学者开始将情绪分析引入内容定向广告[15～17]。

国内对网络广告的个性化研究基本停留在定性、表面的分析阶段，定量研究并不深入，也并未见到在移动互联网上通过智能分析技术和用户分析技术推荐网络广告的研究。

本文研究与设计了移动互联网的上下文广告推荐系统，当手机用户浏览WAP网页时，系统首先利用WAP网页分类算法判断该网页的类别，然后使用关键词抽取算法提取网页中的广告关键词，最后根据网页类别和关键词在广告库中选择相匹配的广告嵌入WAP网页中，推送给用户。

2 移动互联网广告推荐系统

移动互联网广告推荐系统的体系架构如图1所示，包括WAP网页内容预处理子系统、WAP网页分类子系统、关键词抽取子系统、广告投放子系统。

WAP网页内容预处理子系统，包含网页解析模块和分词模块。网页解析模块实现了正文抽取功能，用于识别网页中有意义的正文，并把无关信息剔除，如网页的导航链接、图片、声音等多媒体信息，主要采用HTML去标签化技术，通过匹配网页脚本标签进行正文抽取，输出结果是网页内容正文（带有标题和一些关键标签），将网页正文交给其他分词模块进行处理；分词模块采用正向最大匹配算法将正文中的长句分为单个词语，并通过词典中的信息给出词语的词性。

WAP网页分类子系统，用于准确识别网页的主题，以提高基于内容的网络广告推荐系统的性能。按照设计的分类体系将内容分类，包括IT科技、房产、健康时尚、教育、财经、汽车交通、气候、体育、休闲娱乐以及工作，并依据已建成的内容分类体系进行细化摸索，将关键词提取模块作为重要输入，从而选择合适类别的广告进行投放。

关键词抽取子系统，对广告的推荐有决定性作用，将网页内容预处理子系统的分词结果作为输入，用于从网页正文内容中抽取多个关键词，并以此为依据与广告库中的具体内容进行匹配。利用网页中的标签特征以及词汇之间的语义关系，将网页表示为一个词汇语义网络，尽可能保留网页的结构信息，计算语义网络上每个词语的重要度，根据重要度选择词语作为网页的关键词。

广告投放子系统，利用广告类别和网页关键词，综合制定广告投放策略。根据网页类别计算网页关键词和广告关键词的相似度，搜索属于该类别的广告库，然后在广告库中搜索与网页关键词相似的广告进行投放。投放过程中结合了多种投放策略，应用灵活，功能完善。

各子系统模块间的数据传递关系如图2所示，具体介绍如下。

图1 移动互联网广告推荐系统架构

图2 各子系统模块间的数据传递关系

首先，WAP网页内容预处理子系统从URL中下载网页页面内容，网页解析模块对内容的格式和类型进行解析，输出带有标记（标记显示出正文标题以及各个段落的划分）的网页正文并传递给分词模块，分词模块通过词典中的词语数据完成分词工作并标注词语的词性。WAP网页分类子系统接收分词后的正文，利用贝叶斯分类算法进行分类，标注正文所属类别；同时，分词后的正文被当作关键词提取子系统的输入，正文抽象模块收到后对正文进行解析操作，记录正文标记中标题和段落的划分情况，同时把正文中的词语抽象成词语网络，根据此网络用PageRank算法计算每个词汇的权重，并进行排名。关键词输出模块根据词语在网页中的标签、频率和出现的位置对排名进行微调，使得关键词排名更合理。最后，根据网页所属类别和关键词信息在广告库中进行匹配，对相应的广告进行投送。网页分类子系统根据类别找到广告库中相应的类别，然后根据已提取出的关键词在这个类别中进行语义相近的运算，符合度最高的就是要投送的广告条目。类判别式为:

3 关键技术介绍

3.1 WAP网页分类算法

3.1.1 算法原理

广告因内容不同有不同类别，可以根据广告类别推送广告。通过参考著名的分类目录并结合广告自身特性，在分类体系中建立了10个类别，分别是IT科技、房产、健康时尚、教育、财经、汽车交通、气候、体育、休闲娱乐以及工作。利用WAP网页分类算法对网页内容类别进行判断，得到WAP网页在内容上所属的类别。考虑到分类性能和效率的折衷，本系统采用了一种改进的朴素贝叶斯算法。

在朴素贝叶斯算法的实现过程中，文本分类预测主要依据:待测文本中每个词语出现一次，记录该词语在已建立的分类器中对各个类别的贡献值，当所有的词语都遍历完成，则计算该文本中所有词语所属类别的贡献值总和，从中选出最大的一个作为预测类别。这样看来，词语在文本中的词频和词语在类别中的贡献值决定了文本类别信息，但对于类别重叠较多的情况，有可能造成误分类，这里采用χ2统计值作为词语的重要特征，把它与类别贡献值相联系，增强对于相近类别的区分性能。文本分

其中，F为文本特征向量，CHI(w,Cj)为词w与类别Cj的 χ2统计值，Pr(w|d′)用文本 d′中 w出现的次数与总词数的比值表示，Pr(Cj)可以由类别Cj的文本数和训练集所有文本数的比值表示，Pr(w|Cj)可以由类别Cj中w出现的次数与文本总数的比值表示。

3.1.2 测试结果

为了确保分类的正确性，必须建立质量优良的训练语料库，并且针对上述10个类别进行足够的资料采集，才能确保分类引擎的性能。通过服务器运行爬虫程序采集了50000篇原始文章，进一步筛选后，每个类别保留了1300篇文章作为有效数据，每个类别中500篇文章作为测试数据集，800篇文章作为语料库训练集。测试结果见表1。

3.2 关键词抽取算法

3.2.1 算法原理

关键词抽取是本系统的核心环节，广告的推送主要由关键词的性质和类别决定。由于网页内容多样化，涉及领域广泛，需要设计实现一个适用性强、准确率高、稳定性强的关键词抽取算法完成这一核心工作。本文采用基于PageRank的关键词抽取算法，首先将网页构建成一个共现网络，将文本D映射为一个词汇网络G={V,E,W}，其中V为顶点集合，E为边集合，W为边的权重。

顶点集:文本主要由名词和动词反映语义内容，因此经过分词和词性标注等预处理后只选择名词和动词作为网络的顶点。相同词语只构造一个节点。

边集:如果两个词汇出现在一个窗口单元中，就认为这两个顶点有关系，为它们建立一条边，并统计它们在同一窗口单元中的出现次数，作为边的权重。在共现网络上利用PageRank算法计算节点（即词汇）的重要程度，选取前N个词汇作为网页的关键词。PageRank算法的具体步骤介绍如下。

表1 分类测试结果

（1）读入分词后的文本正文。

（2）读入每个独立词语作为网络节点（相同的词语属于同一个节点），记录每个词语出现的位置，为建立网络做准备。

（3）遍历整个词语节点，如果有两个词语出现在共现窗口内（窗口值由程序运行时设定，一般为5～10），就认为这两个词语有关系，在网络中的相应节点间建立一条边，否则没有连接边。

（4）统计有边词语在窗口内的出现次数，并作为节点间边的权重。

（5）在网络中保留名词、动词等语义丰富的节点，使网络节点都是可以承载文本含义的词语，无向有权文本网络建立完毕。

（6）迭代计算网络中各节点的PageRank值，直至收敛。

（7）各节点的重要度根据PageRank值的大小排序，选取前N个作为文本关键词。

3.2.2 测试结果

为了验证程序的稳定性和正确性，必须建立一个合适的测试集。关键词测试集需要以文本的形式存在，且每篇文章都需要正确的人工标注的关键词，用来验证自动抽取的关键词的正确性。从上述观点出发，最符合条件的测试集是各类学术论文，因为学术论文都由作者自己标注关键词，但由于专业性强、涉及领域较深入、含有较多专业词语、篇幅过长，和通常所浏览的网页有非常大的偏差，所以不能选取学术论文作为测试集验证关键词抽取程序。本文选取与网页形式较为相似的博客作为测试集，因为大多数博客网站都会要求用户在写博客时为文章添加标签——关键词。为了收集博客文章作为测试集，使用网络爬虫对一些博客网站进行信息采集，确保这些博客文章标注的关键词都是在博主写文章时人工标注的，保证其正确性。

通过服务器运行爬虫程序采集到原始文章15000篇，进行进一步筛选。爬虫抓取保存的是博客原始网页，所以需要对这些网页进行解析处理，相当于利用网页解析模块进行处理，只留下题目和正文内容。首先，选取带有3个以上人工标签的博客为测试集，把人工标签视为已标注关键词；然后，选取的博客以文字描述为主要内容，过滤其图片、视频、音频等非文本内容；最后，对博客的长度加以限制，因为有些博客较为短小，不能表达主题含义，选取字数200字以上的博客作为测试集。经过处理后的测试集一共有1200篇文章，将每篇已标识出的关键词统一建立一个索引保存到统一的文件中，以便进行对比实验。

本文中采用精确度P和召回率R作为衡量关键词抽取子系统的标准。其中，精确度定义为输出的正确关键词数量与输出的关键词总数量之比；召回率定义为输出的正确关键词数量与人工标注的关键词数量之比。根据定义，精确度和召回率的最大值都被输出关键词和已标识人工关键词数限制。当A＞T时，精确度的范围是0～1，召回率范围是0～T/A；否则精确度范围是0～A/T，召回率范围是0～1。

共现网络的构建是整个系统算法的核心，窗口大小是影响共现网络构建的重要因素，控制着在网络节点间建立边的规则。根据不同的窗口大小，得到关键词抽取测试结果，见表2。

表2 关键词抽取测试结果

从表2中可以看出，窗口距离由2到10的变化过程中，实验数据有很明显的上升；但窗口距离从10到20的变化过程中，实验数据变化微小，甚至呈现出微小的下降趋势。这主要是因为当窗口过小时，词语网络对于原文保存的语义不够，造成了重要节点在图中孤立；如果窗口距离过大，将使得许多冗余的无意义边出现在语义网络中，网络整体结构将分散在无用连接中。所以需要通过实验在抽取质量和效率之间找一个平衡点，一般情况下选取窗口大小为10。

4 结束语

本文提出了移动互联网广告推荐系统的体系结构，包括WAP网页内容预处理子系统、WAP网页分类子系统、关键词抽取子系统和广告投放子系统。其中，WAP网页分类子系统采用贝叶斯分类器结合统计特性利用自建语料库实现对网页内容的高精度分类；关键词抽取子系统采用基于PageRank算法的数据文本网络关键节点挖掘技术，有效提高文本网络隐藏信息挖掘的精确度和效率。

本文实现了移动互联网广告推荐系统所需的基本功能，但仍不是一个完善的系统，需进一步测试并对网络广告的其他技术进行进一步研究，如行为定向广告研究，通过挖掘用户的长期和短期行为，更能掌握和跟踪用户的兴趣，从而给予更符合用户需求的广告内容。

1 Broder A,Fontoura M,Josifovski V,et al.A semantic approach to contextual advertising.Proceedings of the 30th International Conference on SIGIR,Amsterdam,2007:559～566

2 Anastasakos T,Hillard D,Kshetramade S,et al.A collaborative filtering approach to ad recommendation using the query-ad click graph.Proceedings of the International Conference on CIKM,2009:1927～1930

3 Attenberg J,Pandey S,Suel T.Modeling and predicting user behavior in sponsored search.Proceedings of the International Conference on KDD,2009:1067～1076

4 Hillard D,Schroedl S,Manavoglu E,et al.Improving ad relevance in sponsored search.Proceedings of the International Conference on WSDM,2010:361～370

5 Zhang W,He X,Rey B,et al.Query rewriting using active learning for sponsored search.Proceedings of the International Conference on SIGIR,2007:853～854

6 Zhang W,Jones R.Comparing click logs and editorial labels for training query rewriting.Proceedings of Workshop on Query Log Analysis:Social and Technological Challenges,2007

7 施水才，程涛，王霞等.基于网页内容的广告推介研究.中文信息学报,2007,21(4):42～47

8 Wen-Tau Yih,Joshua Goodman,Vitor R Carvalho.Finding advertising keywords on Web pages.Proceedings of the 15th International Conference on World Wide Web,2006:213～222

9 Jianyi Liu,Cong Wang,Wenbin Yao.Keyword extraction for contextual advertising.China Communications,2010(10)

10 Mehta A,Saberi A,Vazirani U,et al.Adwords and generalized online matching.Journals on ACM,2007,54(5):22

11 Shen D,Sun J T,Yang Q,et al.Building bridges for Web query classification.Proceedings of the International Conference on SIGIR'06,2006:131～138

12 Murdock V,Ciaramita M,PlachourasV.A noisy-channel approach to contextual advertising. Proceedings of the International Conference on ADKDD'07,2007:21～27

13 Berthier Ribeiro-Neto,Macro Cristo.Impedance coupling in content-targeted advertising. Proceedings of the 28th International Conference on SIGIR,2005:496～503

14 Anisio Lacerda, Marco Cristo. Learning to advertise.Proceedings of the 29th Annual International ACMSIGIR Conference on Research and Development in Information Retrieval,2006:549～556

15 Xin Jin,YingLi,TeresaMah,etal.Sensitive Webpage classification for content advertising.Proceedings of the 1st International Workshop on Data Mining and Audience Intelligence for Advertising,San Jose,California,2007:28～33

16 Teng-Kai Fan,Chia-Hui Chang.Sentiment-oriented contextual advertising.Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval,Toulouse,France,2009:202～215

17 KangmiaoLiu,QuangQiu,Can Wang,etal.Incorporate sentiment analysis in contextual advertising.Proceedings of the First Workshop on Targeting and Ranking for Online Advertising,Beijing,China,2008