Personalized recommendation algorithm based on location bitcode tree

doi:10.11772/j.issn.1001-9081.2016.02.0419

Abstract

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

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

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

CLC Number:

TP311.1

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

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

References

[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