一种分布式用户浏览点击模型算法

doi:10.19678/j.issn.1000-3428.0050119

计算机工程 ›› 2019, Vol. 45 ›› Issue (3): 1-6. doi: 10.19678/j.issn.1000-3428.0050119

所属专题：云计算与大数据专题；

一种分布式用户浏览点击模型算法

张浩盛伦^1,2,李翀¹,柯勇¹,张士波¹

1.中国科学院计算机网络信息中心,北京 100190; 2.中国科学院大学,北京 100190

收稿日期:2018-01-05 出版日期:2019-03-15 发布日期:2019-03-15
作者简介:张浩盛伦(1993—),男,硕士研究生,主研方向为点击模型、分布式计算;李翀(通信作者),副研究员、博士;柯勇,高级工程师;张士波,工程师
基金资助:
中国科学院信息化专项“中国科学院信息化评估”(Y647021189)

A Distributed User Browse Click Model Algorithm

ZHANG Haoshenglun ^1,2,LI Chong¹,KE Yong ¹,ZHANG Shibo¹

1.Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China; 2.University of Chinese Academy of Sciences,Beijing 100190,China

Received:2018-01-05 Online:2019-03-15 Published:2019-03-15

摘要/Abstract

摘要：

为从海量搜索点击日志中快速挖掘用户行为,提出一种分布式用户浏览点击模型(UBM)算法。原始UBM算法求出的检验度参数E只与搜索结果文档所在排序位置以及上一文档的点击位置有关,且非常稳定,基于此特性,将EM迭代求解转换为抽样估计检验度以求解吸引度的分布式UBM算法。在Spark数据平台上进行仿真,结果表明,与原始UBM算法相比,该算法能够解决点击日志中存在的严重数据倾斜问题,且运行效率较高。

关键词: 点击日志, 点击模型, 用户浏览点击模型算法, 搜索引擎, Spark平台

Abstract:

A distributed User Browse Click Model(UBM) algorithm is proposed to quickly mine user behavior from massive search click logs.The validation parameter E derived from the original UBM algorithm is only related to the ranking position of the search results and the click position of the previous document,and is very stable.Based on this characteristic,the EM iteration solution is transformed into a distributed UBM algorithm which estimates the test degree by sampling to solve the attraction degree.Results of simulation on Spark data platform show that compared with the original UBM algorithm,the proposed algorithm can solve the serious data skew problem in click log,and has higher efficiency.

Key words: click log, click model, User Browse Click Model(UBM) algorithm, search engine, Spark platform

中图分类号:

TP391

张浩盛伦,李翀,柯勇,张士波. 一种分布式用户浏览点击模型算法[J]. 计算机工程, 2019, 45(3): 1-6.

ZHANG Haoshenglun,LI Chong,KE Yong,ZHANG Shibo. A Distributed User Browse Click Model Algorithm[J]. Computer Engineering, 2019, 45(3): 1-6.

http://www.ecice06.com/CN/Y2019/V45/I3/1

参考文献

［1］CHUKLIN A,MARKOV I,RIJKE M D.Click models for Web search［J］.Synthesis Lectures on Information Concepts,Retrieval,and Services,2015,7(3):110-115.
［2］CRASWELL N,ZOETER O,TAYLOR M,et al.An experimental comparison of click position-bias models［C］//Proceedings of 2008 International Conference on Web Search and Data Mining.New York,USA:ACM Press,2008:87-94.
［3］DUPRET G E,PIWOWARSKI B.A user browsing model to predict search engine click data from past observations［C］//Proceedings of International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,2008:331-338.
［4］GUO F,LIU C,WANG Y M.Efficient multiple-click models in Web search［C］//Proceedings of the 2nd ACM International Conference on Web Search and Data Mining.New York,USA:ACM Press,2009:124-131.
［5］GUO F,LIU C,KANNAN A,et al.Click chain model in Web search［C］//Proceedings of International Conference on World Wide Web.New York,USA:ACM Press,2009:11-20.
［6］CHAPELLE O,ZHANG Y.A dynamic Bayesian network click model for Web search ranking［C］//Proceedings of International Conference on World Wide Web.New York,USA:ACM Press,2009:1-10.
［7］SKIERA B,ECKERT J,HINZ O.An analysis of the importance of the long tail in search engine marketing［J］.Electronic Commerce Research and Applications,2010,9(6):488-494.
［8］DEMPSTER A P,LAIRD N M,RUBIN D B,et al.Maximum Likelihood from incomplete data via the EM algorithm［J］.Journal of the Royal Statistical Society,1977,39(1):1-38.
［9］ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al.Spark:cluster computing with working sets［C］//Proceedings of USENIX Conference on Hot Topics in Cloud Computing.San Diego,USA:USENIX Association,2010:5-10.
［10］王超,刘奕群,马少平.搜索引擎点击模型综述［J］.智能系统学报,2016,11(6):711-718.
［11］RICHARDSON M,DOMINOWSKA E,RAGNO R.Predicting clicks:estimating the click-through rate for new ads［C］//Proceedings of International Conference on World Wide Web.New York,USA:ACM Press,2007:521-530.
［12］王爱平,张功营,刘方.EM算法研究与应用［J］.计算机技术与发展,2009,19(9):108-110.
［13］SHVACHKO K,KUANG H,RADIA S,et al.The Hadoop distributed file system［C］//Proceedings of 2010 IEEE Symposium on Mass Storage Systems and Technologies.Washington D.C.,USA:IEEE Press,2010:1-10.
［14］KARAU H,KONWINSKI A,WENDELL P,et al.Learning spark:lightning-fast big data analytics［M］.［S.l.］:O’Reilly Media,Inc.,2015.
［15］FAROOK S,LAKSHMI G,TARAKESWARA B.Spark is superior to map reduce over big data［J］.International Journal of Computer Applications,2016,133:13-16.
［16］KWON Y,BALAZINSKA M,HOWE B,et al.A study of skew in mapreduce applications［EB/OL］.［2018-01-05］.http://nuage.cs.washington.edu/pubs/opencirrus2011.pdf.
［17］RANA N,DESHMUKH S.Shuffle performance in apache Spark［J］.International Journal of Engineering Research and Technology,2015,4(2):177-180.
［18］AKBARINIA R,LIROZ-GISTAU M,AGRAWAL D,et al.An efficient solution for processing skewed mapreduce jobs［J］.Database and Expert Systems Applications,2015,9262:417-429.
［19］TANG Z,MA W,LI K,et al.A data skew oriented reduce placement algorithm based on sampling［J］.IEEE Transactions on Cloud Computing,2016,15(6):13-16.
［20］LIU G,ZHU X,WANG J,et al.SP-partitioner:a novel partition method to handle intermediate data skew in Spark streaming［J］.Future Generation Computer Systems,2017,86:1054-1063.
［21］DAVIDSON A,OR A.Optimizing shuffle performance in Spark［EB/OL］.［2018-01-05］.https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F13/projects/reports/project16_report.pdf.
［22］BREIMAN L.Bagging predictors［J］.Machine Learning,1996,24(2):123-140.

[1]	贾晓芳, 桑国明, 祁文凯. 基于Spark平台的ALS加速算法研究[J]. 计算机工程, 2020, 46(2): 103-109.
[2]	王谟瀚, 翟俊海, 齐家兴. 基于MapReduce和Spark的大规模压缩模糊K-近邻算法[J]. 计算机工程, 2020, 46(11): 139-147.
[3]	高权,万晓冬. 基于负载均衡的并行FP-Growth算法[J]. 计算机工程, 2019, 45(3): 32-35,40.
[4]	杨正龙, 高建华. 基于蜕变测试的面向用户搜索引擎性能分析[J]. 计算机工程, 2019, 45(10): 52-56,63.
[5]	严锐,李石君. 基于查询意图识别与主题建模的文档检索算法[J]. 计算机工程, 2018, 44(3): 189-194.
[6]	王林,刘继源,马安进. 基于兴趣衰减的个性化排序算法[J]. 计算机工程, 2017, 43(9): 214-219,227.
[7]	陈广胜,程逸群,景维鹏. 基于KD树划分的云计算DBSCAN优化算法[J]. 计算机工程, 2017, 43(4): 21-27.
[8]	黄廷辉,王玉良,汪振,崔更申. 基于内存与文件共享机制的Spark I/O性能优化[J]. 计算机工程, 2017, 43(3): 1-6.
[9]	杨志伟,郑烇,王嵩,杨坚,周乐乐. 异构Spark集群下自适应任务调度策略[J]. 计算机工程, 2016, 42(1): 31-35,40.
[10]	张乃洲. 基于时间点击图挖掘的查询建议方法[J]. 计算机工程, 2015, 41(5): 191-196.
[11]	平宇，向阳，张波，黄寅飞. 基于MapReduce的并行PageRank算法实现[J]. 计算机工程, 2014, 40(2): 31-34,38.
[12]	张旭东，孙志明，刘亚宁，单栋栋，闫宏飞. 基于64位体系结构的倒排索引压缩算法[J]. 计算机工程, 2014, 40(2): 71-76.
[13]	方爽,殷俊杰,徐武平. 基于相似图片聚类的Web文本特征算法[J]. 计算机工程, 2014, 40(12): 161-165,171.
[14]	王东, 牛军钰. 基于多角度关联模型的实体检索方法[J]. 计算机工程, 2013, 39(1): 71-75.
[15]	尹美娟, 王清贤, 刘晓楠. 结合网页和语句共现的Web社会关系评估[J]. 计算机工程, 2012, 38(22): 34-38.

选择文件类型/文献管理软件名称

选择包含的内容

一种分布式用户浏览点击模型算法

A Distributed User Browse Click Model Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种分布式用户浏览点击模型算法

A Distributed User Browse Click Model Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价