基于位置编码索引树的个性化推荐算法

doi:10.11772/j.issn.1001-9081.2016.02.0419

计算机应用 ›› 2016, Vol. 36 ›› Issue (2): 419-423.DOI: 10.11772/j.issn.1001-9081.2016.02.0419

• 第三届CCF大数据学术会议(CCF BigData 2015) • 上一篇下一篇

基于位置编码索引树的个性化推荐算法

梁俊杰, 甘文婷, 余敦辉

湖北大学计算机与信息工程学院, 武汉 430062

收稿日期:2015-08-29 修回日期:2015-09-15 出版日期:2016-02-10 发布日期:2016-02-03
通讯作者: 甘文婷(1989-),女,江西丰城人,硕士研究生,主要研究方向:Web信息挖掘、个性化推荐。
作者简介:梁俊杰(1974-),女,湖北武汉人,副教授,博士,CCF会员,主要研究方向:多媒体数据库、高维索引;余敦辉(1974-),男,湖北武汉人,副教授,博士,CCF会员,主要研究方向:个性化推荐、大数据。
基金资助:
湖北省自然科学基金重点资助项目(2015CFA067);湖北省教育厅科研项目计划重点项目(D20151001);武汉市科技攻关计划项目(2013012401010851)。

Personalized recommendation algorithm based on location bitcode tree

LIANG Junjie, GAN Wenting, YU Dunhui

School of Computer Science and Information Engineering, Hubei University, Wuhan Hubei 430062, China

Received:2015-08-29 Revised:2015-09-15 Online:2016-02-10 Published:2016-02-03

摘要/Abstract

摘要： 针对协同过滤算法在海量数据环境个性化推荐应用中存在的低效率问题,结合MapReduce框架特点,设计了一种应用于个性化推荐的基于位置编码的索引树(LB-Tree),创新性地将索引结构应用于个性化推荐。利用聚类资源的差异性存储策略,提升MapReduce任务处理并行性;根据聚类数据分布特征,以质心为圆心对聚类中的数据对象进行同心圆分层,并对每层采用不同长度的二进制编码来表达,将所有数据对象的编码组织成索引树结构,缩短频繁推荐的数据查找路径,达到个性化推荐时利用索引结构快速确定搜索空间的目的。与基于项目的Top-N推荐算法和基于最近邻的推荐算法(SBNM)相比,LB-Tree所需时间开销增长最慢,准确率最高,验证了方法的有效性和高效性。

关键词: 海量数据, MapReduce, 个性化推荐, 索引树, 位置编码

Abstract: Since collaborative filtering recommendation algorithm is inefficient in large data environment, a personalized recommendation algorithm based on location bitcode tree, called LB-Tree, was developed. Combined with the characteristics of the MapReduce framework, a novel approach which applyed the index structure in personalized recommendation processing was proposed. For efficient parallel computing in MapReduce, a novel storage strategy based on the differences between clusters was presented. According to the distribution, each cluster was partitioned into several layers by concentric circles with the same centroid, and each layer was expressed by binary bitcodes with different length. To make the frequently recommended data search path shorter and quickly determine the search space by using the index structure, an index tree was constructed by bitcodes of all the layers. Compared with the Top-N recommendation algorithm and Similarity-Based Neighborhood Method (SBNM), LB-Tree has the highest accuracy with the slowest time-increasing, which verifies the effectiveness and efficiency of LB-Tree.

Key words: big data, MapReduce, personalized recommendation, index tree, location bitcode

中图分类号:

TP311.1

梁俊杰, 甘文婷, 余敦辉. 基于位置编码索引树的个性化推荐算法[J]. 计算机应用, 2016, 36(2): 419-423.

LIANG Junjie, GAN Wenting, YU Dunhui. Personalized recommendation algorithm based on location bitcode tree[J]. Journal of Computer Applications, 2016, 36(2): 419-423.

参考文献

[1] International Data Corporation. EMC digital universe study with research and analysis by IDC [EB/OL]. [2014-11-30]. http://www.emc.com/leadership/digital-universe/index.htm.
[2] RESNICK P, VARIAN H R. Recommender systems[J]. Communications of the ACM, 1997, 40(3): 56-58.
[3] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]//UAI '98: Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, 1998: 43-52.
[4] DESHPANDE M, KARYPIS G. Item-based top-N recommendation algorithms[J]. ACM Transactions on Information Systems, 2004, 22(1):143-177.
[5] LINDEN G, SMITH B, YORK J. Amazon.com recommendations: item-to-item collaborative filtering[J]. IEEE Internet Computing, 2003, 7(1):76-80.
[6] LIU Z B, QU W Y, LI H T, et al. A hybrid collaborative filtering recommendation mechanism for P2P networks[J]. Future Generation Computer Systems, 2010, 26(8): 1409-1417.
[7] 陈克寒,韩盼盼,吴健.基于用户聚类的异构社交网络推荐算法[J].计算机学报,2013,36(2):349-359. (CHEN K H, HAN P P, WU J. User clustering based social network recommendation[J]. Chinese Journal of Computers, 2013, 36(2): 349-359.)
[8] SHANG M-S, JIN C-H, ZHOU T, et al. Collaborative filtering based on multi-channel diffusion[J]. Physica A: Statistical Mechanics & Its Applications, 2009, 388(23): 4867-4871.
[9] ZHANG Z K, YU L, FANG K, et al. Website-oriented recommendation based on heat spreading and tag-aware collaborative filtering[J]. Physica A: Statistical Mechanics & Its Applications, 2014, 399: 82-88.
[10] KIM J K, CHO Y H. Using Web usage mining and SVD to improve e-commerce recommendation quality[C]//PRIMA 2003: Proceedings of the 6th Pacific Rim International Workshop on Multi-Agents, LNAI 2891. Berlin: Springer-Verlag, 2003: 86-97.
[11] 黄创光,印鉴,汪静,等.不确定近邻的协同过滤推荐算法[J].计算机学报,2010,33(8):1369-1377. (HUANG C G, YIN J, WANG J, et al. Uncertain neighbors's collaborative filtering recommendation algorithm[J]. Chinese Journal of Computers, 2010, 33(8): 1369-1377.)
[12] DESHPANDE M, KARYPIS G. Item-based top-N recommendation algorithms[J]. ACM Transactions on Information Systems, 2004, 22(1): 143-177.
[13] PAN R, DOLOG P, XU G. KNN-based clustering for improving social recommender systems[C]//ADMI 2012: Proceedings of the 8th International Workshop on Agents and Data Mining Interaction, LNCS 7607. Berlin: Springer-Verlag, 2013: 115-125.
[14] ZHAO Z-D, SHANG M-S. User-based collaborative-filtering recommendation algorithms on Hadoop[C]//WKDD '10: International Workshop on Knowledge Discovery and Data Mining. Washington, DC: IEEE Computer Society, 2010: 478-481.
[15] DE PESSEMIER T, VANHECKE K, DOOMS S, et al. Content-based recommendation algorithms on the Hadoop mapreduce framework[C]//WEBIST-2011: Proceedings of the 7th International Conference on Web Information Systems and Technologies, LNBIP 101. Berlin: Springer-Verlag, 2011: 237-240.
[16] SCHELTER S, BODEN C, MARKL V. Scalable similarity-based neighborhood methods with MapReduce[C]//RecSys '12: Proceedings of the sixth ACM Conference on Recommender Systems. New York: ACM, 2012: 163-170.
[17] 朱夏,宋爱波,东方,等.云计算环境下基于协同过滤的个性化推荐机制[J].计算机研究与发展,2014,51(10):2255-2269. (ZHU X, SONG A B, DONG F, et al. A collaborative filtering recommendation mechanism for cloud computing[J]. Journal of Computer Research and Development, 2014, 51(10): 2255-2269.)
[18] FORMOSO V, FERNÁNDEZ D, CACHEDA F, et al. Distributed architecture for k-nearest neighbors recommender systems[J]. World Wide Web: Internet & Web Information Systems, 2014, 18(4): 1-21.
[19] PAGARE R, SHINDE A. recommendation system using Bloom filter in MapReduce[J]. International Journal of Data Mining & Knowledge Management Process, 2013, 3(6): 127-134.
[20] LEE C-R, CHANG Y-F. Enhancing accuracy and performance of collaborative filtering algorithm by stochastic SVD and its MapReduce implementation[C]//IPDPSW 2013: Proceedings of the 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and PhD Forum. Washington, DC: IEEE Computer Society, 2013: 1869-1878.
[21] Institut for Informatic Freiburg. Booking-crossing data sets [EB/OL]. [2014-12-20]. http://www2.informatik.uni-freiburg.de/~cziegler/BX

基于位置编码索引树的个性化推荐算法

Personalized recommendation algorithm based on location bitcode tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘欢, 李晓戈, 胡立坤, 胡飞雄, 王鹏华. 基于知识图谱驱动的图神经网络推荐模型[J]. 计算机应用, 2021, 41(7): 1865-1870.
[2]	孙鹤立, 徐统, 何亮, 贾晓琳. 融合用户历史行为与社交关系的个性化社交事件推荐方法[J]. 计算机应用, 2021, 41(2): 324-329.
[3]	邓凯, 黄佳进, 秦进. 基于物品的统一推荐模型[J]. 计算机应用, 2020, 40(2): 530-534.
[4]	唐林川, 邓思宇, 吴彦学, 温柳英. 基于pHash分块局部探测的海量图像查重算法[J]. 计算机应用, 2019, 39(9): 2789-2794.
[5]	郭方方, 潮洛蒙, 朱建文. 基于相似连接的多源数据并行预处理方法[J]. 计算机应用, 2019, 39(1): 57-60.
[6]	马友忠, 张智辉, 林春杰. 大数据相似性连接查询技术研究进展[J]. 计算机应用, 2018, 38(4): 978-986.
[7]	曹云鹏, 王海峰. 面向MapReduce计算模式的中间数据通信优化[J]. 计算机应用, 2018, 38(4): 1078-1083.
[8]	孙丽梅, 李悦, Ejike Ifeanyi Michael, 曹科研. 简化的Slope One在线评分预测算法[J]. 计算机应用, 2018, 38(2): 497-502.
[9]	冯勇, 韩晓龙, 付陈平, 王嵘冰, 徐红艳. 集成用户信任度和品牌认可度的商品推荐方法[J]. 计算机应用, 2018, 38(10): 2886-2891.
[10]	张承畅, 张华誉, 罗建昌, 何丰. 基于云计算和改进K-means算法的海量用电数据分析方法[J]. 计算机应用, 2018, 38(1): 159-164.
[11]	马生俊, 陈旺虎, 俞茂义, 李金溶, 郏文博. 云环境下影响数据分布并行应用执行效率的因素分析[J]. 计算机应用, 2017, 37(7): 1883-1887.
[12]	廖彬, 张陶, 国冰磊, 于炯, 张旭光, 刘炎. 基于Spark的ItemBased推荐算法性能优化[J]. 计算机应用, 2017, 37(7): 1900-1905.
[13]	肖子达, 朱立谷, 冯东煜, 张迪. 分布式数据库聚合计算性能优化[J]. 计算机应用, 2017, 37(5): 1251-1256.
[14]	吴家皋, 夏轩, 刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用, 2017, 37(5): 1282-1286.
[15]	王卓, 索勃, 潘巍. 三角形的并行枚举算法[J]. 计算机应用, 2017, 37(12): 3397-3400.