›› 2016,Vol. 31 ›› Issue (3): 577-594.doi: 10.1007/s11390-016-1648-0

所属专题: Artificial Intelligence and Pattern Recognition Data Management and Data Mining

• • 上一篇    下一篇

Trinity——一种基于用户-对象-标签异质网络游走的个性化推荐方法

Ming-Xin Gan(甘明鑫)1,2,*, Lily Sun(孙力)3, and Rui Jiang(江瑞)4,*   

  1. 1 Department of Management Science and Engineering, Donlinks School of Economics and Management University of Science and Technology Beijing, Beijing 100083, China;
    2 Department of Statistics, University of California Berkeley, Berkeley, CA 94720, U.S.A.;
    3 School of Systems Engineering, University of Reading, Reading, RG6 6UR, U.K.;
    4 Department of Automation, Tsinghua University, Beijing 100084, China
  • 收稿日期:2014-11-15 修回日期:2016-01-29 出版日期:2016-05-05 发布日期:2016-05-05
  • 通讯作者: Ming-Xin Gan, Rui Jiang E-mail:ganmx@ustb.edu.cn;ruijiang@tsinghua.edu.cn
  • 作者简介:Ming-Xin Gan received her B.S. degree in automation from Tsinghua University, Beijing, in 2001, her Ph.D. degree in management science and engineering from Beijing Institute of Technology, Beijing, in 2006. She is currently an associate professor in the Department of Management Science and Engineering, Donlinks School of Economics and Management, University of Science and Technology Beijing, Beijing. She has published more than 40 papers. Her current research interests concern recommender systems, information retrieval, complex systems, social network, big data analysis and visualization.
  • 基金资助:

    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 71101010 and 71471016.

Trinity: Walking on a User-Object-Tag Heterogeneous Network for Personalised Recommendations

Ming-Xin Gan(甘明鑫)1,2,*, Lily Sun(孙力)3, and Rui Jiang(江瑞)4,*   

  1. 1 Department of Management Science and Engineering, Donlinks School of Economics and Management University of Science and Technology Beijing, Beijing 100083, China;
    2 Department of Statistics, University of California Berkeley, Berkeley, CA 94720, U.S.A.;
    3 School of Systems Engineering, University of Reading, Reading, RG6 6UR, U.K.;
    4 Department of Automation, Tsinghua University, Beijing 100084, China
  • Received:2014-11-15 Revised:2016-01-29 Online:2016-05-05 Published:2016-05-05
  • Contact: Ming-Xin Gan, Rui Jiang E-mail:ganmx@ustb.edu.cn;ruijiang@tsinghua.edu.cn
  • Supported by:

    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 71101010 and 71471016.

互联网的迅速发展迫切需要推荐系统能够从在线资源中迅速筛选出有用信息。虽然用户-对象评分数据仍是推荐系统中广泛使用的重要信息, 最新研究进展已经表明标签信息的引入能够改善推荐系统的性能。此外, 标签深受卓有成效的在线社会化媒体如 CiteULike, MovieLens和Bibsonomy的重视, 使得用户能够轻松表达自己的喜好, 上传资源以及管理个性化标签。然而, 大多数现有的基于标签的推荐方法将用户、对象和标签作为一个三部图, 从而忽视了同一类型节点之间的关系。为了克服这种局限性, 我们提出了一个名为Trinity的新方法, 将历史数据和标签信息集成起来, 在所构建的用户-对象-标签三层网络上进行带重启动的随机游走。Trinity不仅考虑了网络中异质节点的关联, 而且考虑了同质节点的关联。我们通过10倍交叉验证的实验方法验证了方法的有效性。结果表明, 该方法在三类综合评价指标下的推荐性能, 不仅明显优于基于用户和基于对象的协同过滤方法, 而且明显优于基于用户-对象-标签的三部图游走等方法。

Abstract: The rapid evolution of the Internet has been appealing for effective recommender systems to pinpoint useful information from online resources. Although historical rating data has been widely used as the most important information in recommendation methods, recent advancements have been demonstrating the improvement in recommendation performance with the incorporation of tag information. Furthermore, the availability of tag annotations has been well addressed by such fruitful online social tagging applications as CiteULike, MovieLens and BibSonomy, which allow users to express their preferences, upload resources and assign their own tags. Nevertheless, most existing tag-aware recommendation approaches model relationships among users, objects and tags using a tripartite graph, and hence overlook relationships within the same types of nodes. To overcome this limitation, we propose a novel approach, Trinity, to integrate historical data and tag information towards personalised recommendation. Trinity constructs a three-layered object-user-tag network that considers not only interconnections between different types of nodes but also relationships within the same types of nodes. Based on this heterogeneous network, Trinity adopts a random walk with restart model to assign the strength of associations to candidate objects, thereby providing a means of prioritizing the objects for a query user. We validate our approach via a series of large-scale 10-fold cross-validation experiments and evaluate its performance using three comprehensive criteria. Results show that our method outperforms several existing methods, including supervised random walk with restart, simulation of resource allocating processes, and traditional collaborative filtering.

[1] Huang Z, Chung W Y, Chen H C. A graph model for E-commerce recommender systems. J. Am. Soc. Inf. Sci. Technol., 2004, 55(3): 259-274.

[2] Brin S, Page L. The anatomy of a large-scale hypertextual web search engine. Comput. Networks and ISDN Systems, 1998, 30: 107-117.

[3] Al-Masri E, Mahmoud Q H. Investigating web services on the world wide web. In Proc. the 17th Int. Conf. World Wide Web, April 2008, pp.795-804.

[4] Jeong B, Lee J, Cho H. Improving memory-based collaborative filtering via similarity updating and prediction modulation. Inf. Sci.: an International Journal, 2010, 180(5): 602-612.

[5] Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. Knowl. Data Eng., 2005, 17(6): 734-749.

[6] Sarwar B, Karypis G, Konstan J, Reidl J. Item-based collaborative filtering recommendation algorithms. In Proc. the 10th Int. Conf. World Wide Web, May 2001, pp.285-295.

[7] Linden G, Smith B, York J. Amazon.com recommendations: Item-to-item collaborative filtering. IEEE Internet Comput., 2003, 7(1): 76-80.

[8] Bogers T, van den Bosch A. Fusing recommendations for social bookmarking web sites. Int. J. Electron. Commer., 2011, 15(3): 31-72.

[9] Prawesh S, Padmanabhan B. Probabilistic news recommender systems with feedback. In Proc. the 6th ACM Conf. Recomm. Syst., September 2012, pp.257-260.

[10] Barragáns-Martínez A B, Costa-Montenegro E, Burguillo J C, Rey-López M, Mikic-Fonte F A, Peleteiro A. A hybrid content-based and item-based collaborative filtering approach to recommend TV programs enhanced with singular value decomposition. Inf. Sci.: an International Journal, 2010, 180(22): 4290-4311.

[11] Cheng J S, Sun A, Hu D N, Zeng D. An information diffusion-based recommendation framework for microblogging. J. Assoc. Inf. Syst., 2011, 12(7): 463–486.

[12] Biau G, Cadre B, Rouvière L. Statistical analysis of knearest neighbor collaborative recommendation. Ann. Stat., 2010, 38(3): 1568-1592.

[13] Georgiou O, Tsapatsoulis N. The importance of similarity metrics for representative users identification in recommender systems. In Artif. Intell. Appl. Innov., Papadopoulos H, Andreou A S, Bramer M (eds.), Springer Berlin Heidelberg, 2010, pp.12-21.

[14] Pérez I, Cabrerizo F, Herrera-Viedma E. Group decision making problems in a linguistic and dynamic context. Expert Syst. Appl., 2011, 38(3): 1675-1688.

[15] Burke R. Hybrid recommender systems: Survey and experiments. User Model. User-Adapt. Interact., 2002, 12(4): 331-370.

[16] Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems. Computer, 2009, 42(8): 30-37.

[17] Paterek A. Improving regularized singular value decomposition for collaborative filtering. In Proc. the 13th KDD Cup Work., August 2007, pp.39-42.

[18] Wang X, Sun J T, Chen Z, Zhai C. Latent semantic analysis for multiple-type interrelated data objects. In Proc. the 29th Annu. Int. ACM SIGIR Conf. Res. Dev. Inf. Retr., August 2006, pp.236-243.

[19] Zhou T, Ren J, Medo M, Zhang Y C. Bipartite network projection and personal recommendation. Phys. Rev. E, 2007, 76(4pt2): 046115.

[20] Gan, M. COUSIN: A network-based regression model for personalized recommendations. Decision Support Systems, 2016, 82: 58-68.

[21] Golder S A, Huberman B A. Usage patterns of collaborative tagging systems. J. Inf. Sci., 2006, 32(2): 198-208.

[22] Vig J, Sen S, Riedl J. The tag genome: Encoding community knowledge to support novel interaction. ACM Trans. Interact. Intell. Syst., 2012, 2(3): Article No. 13.

[23] Zhang Z K, Zhou T, Zhang Y C. Tag-aware recommender systems: A state-of-the-art survey. J. Comput. Sci. Technol., 2011, 26(5): 767-777.

[24] Gan M. TAFFY: Incorporating tag information into a diffusion process for personalized recommendations. World Wide Web—Internet and Web Information Systems, 2015.

[25] Hotho A, Robert J, Schmitz C, Stumme G. Information retrieval in folksonomies: Search and ranking. In Proc. the 3rd ESWC, June 2006, pp.411-426.

[26] Lambiotte R, Ausloos M. Collaborative tagging as a tripartite network. In Proc. the 6th ICCS, May 2006, pp.1114-1117.

[27] Song Y, Zhuang Z, Li H, Zhao Q, Li J, Lee W C et al. Real-time automatic tag recommendation. In Proc. the 31st Annu. Int. ACM SIGIR Conf. Res. Dev. Inf. Retr., July 2008, pp.515-522.

[28] Zhou X, Xu Y, Li Y, Josang A, Cox C. The state-of-the-art in personalized recommender systems for social networking. Artif. Intell. Rev., 2011, 37(2): 119-132.

[29] Clements M, De Vries A P, Reinders M J T. The taskdependent effect of tags and ratings on social media access. ACM Trans. Inf. Syst., 2010, 28(4): Article No. 21.

[30] Zhang Z K, Zhou T, Zhang Y C. Personalized recommendation via integrated diffusion on user-item-tag tripartite graphs. Phys. A: Stat. Mech. Its Appl., 2010, 389(1): 179-186.

[31] Kolda T G, Bader B W. Tensor decompositions and applications. SIAM Rev., 2009, 51(3): 455-500.

[32] Rendle S, Marinho L B, Nanopoulos A, Schmidt-Thieme L. Learning optimal ranking with tensor factorization for tag recommendation. In Proc. the 15th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., June 28-July 1, 2009, pp.727-736.

[33] Symeonidis P, Nanopoulos A, Manolopoulos Y. Tag recommendations based on tensor dimensionality reduction. In Proc. ACM Conf. Recomm. Syst., October 2008, pp.43-50.

[34] Symeonidis P, Nanopoulos A, Manolopoulos Y. A unified framework for providing recommendations in social tagging systems based on ternary semantic analysis. IEEE Trans. Knowl. Data Eng., 2010, 22(2): 179-192.

[35] Zhang QM, Zeng A, Shang M S. Extracting the information backbone in online system. PLoS One, 2013, 8(5): e62624.

[36] Gan M, Jiang R. Improving accuracy and diversity of personalized recommendation through power law adjustments of user similarities. Decis. Support Syst., 2013, 55(3): 811-821.

[37] Gan M, Jiang R. Constructing a user similarity network to remove adverse influence of popular objects for personalized recommendation. Expert Syst. Appl., 2013, 40(10): 4044-4053.

[38] Gan M, Jiang R. ROUND: Walking on an object-user heterogeneous network for personalized recommendations. Expert Syst. Appl., 2015, 42(22): 8791-8804.

[39] Jiang R. Walking on multiple disease-gene networks to prioritize candidate genes. J. Mol. Cell Biol., 2015, 7(3): 214-230.

[40] YuW, Lin X. IRWR: Incremental random walk with restart. In Proc. the 36th Int. ACM SIGIR Conf. Res. Dev. Inf. Retr., July 28-August 1, 2013, pp.1017-1020.

[41] Chiang M F, Liou J J, Wang J L, Peng W C, Shan M K. Exploring heterogeneous information networks and random walk with restart for academic search. Knowl. Inf. Syst., 2012, 36(1): 59-82.

[42] Li J, Xia F, Wang W, Chen Z, Asabere N Y, Jiang H. ACRec: A co-authorship based random walk model for academic collaboration recommendation. In Proc. the 23rd Int. Conf. World Wide Web Companion, April 2014, pp.1209-1214.

[43] Gan M. Walking on a user similarity network towards personalized recommendations. PLoS One, 2014, 9(12): e114662.

[44] Backstrom L, Leskovec J. Supervised random walks: Predicting and recommending links in social networks. In Proc. the 4th ACM Intl. Conf. Web Search and Data Mining, Feb. 2011, pp.635-644.

[45] Shang M S, Zhang Z K, Zhou T, Zhang Y C. Collaborative filtering with diffusion-based similarity on tripartite graphs. Phys. A: Stat. Mech. Its Appl., 2010, 389(6): 1259-1264.

[46] Tso-Sutter K H L, Marinho L B, Schmidt-Thieme L. Tagaware recommender systems by fusion of collaborative filtering algorithms. In Proc. the 2008 ACM Symp. Appl. Comput., March 2008, pp.1995-1999.

[47] Wetzker R, UmbrathW, Said A. A hybrid approach to item recommendation in folksonomies. In Proc. WSDM 2009 Work. Exploit. Semant. Annot. Inf. Retr., February 2009, pp.25-29.

[48] Zlati? V, Ghoshal G, Caldarelli G. Hypergraph topological quantities for tagged social networks. Phys. Rev. E., 2009, 80: 036118.

[49] Zhang Z K, Liu C. A hypergraph model of social tagging networks. J. Stat. Mech.: Theory & Exp., 2010, 2010: P10005.

[50] Shang M S, Zhang Z K. Diffusion-based recommendation in collaborative tagging systems. Chinese Phys. Lett., 2009, 26(11): 118903.

[51] Emamy K, Cameron R. CiteULike: A researcher’s social bookmarking service. Ariadne., 2007, 51(5).

[52] Grouplens Research. MovieLens datasets. http://www.grouplens.org/node/73, April 2016.

[53] Benz D, Hotho A, Jäschke R, Krause B, Mitzlaff F, Schmitz C et al. The social bookmark and publication management system BibSonomy. VLDB J., 2010, 19(6): 849-875.

[54] Zhang M, Tang J, Zhang X, Xue X. Addressing cold start in recommender systems: A semi-supervised co-training algorithm. In Proc. the 37th Int. ACM SIGIR Conf. Res. Dev. Inf. Retr., July 2014, pp.73-82.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 刘铁英; 叶新铭;. An Algorithm for Determining Minimal Reduced-Coverings of Acyclic Database Schemes[J]. , 1996, 11(4): 347 -355 .
[2] 王坚;. Integration Model of Eye-Gaze, Voice and Manual Response in Multimodal User Interface[J]. , 1996, 11(5): 512 -518 .
[3] . CLASCN: 支持高效数据库关键词Top-k查询的候选网络选择方法[J]. , 2007, 22(2): 197 -207 .
[4] 刘海龙, 陈群, 李战怀. RFID复杂事件处理优化[J]. , 2009, 24(4): 723 -733 .
[5] Cheng-Wen Xing, Hai-Chuan Ding, Guang-Hua Yang, Shao-Dan Ma, and Ze-Song Fei. 协作Ad Hoc网络的中断概率分析[J]. , 2013, 28(3): 403 -411 .
[6] Guo-Dong Zhou, and Pei-Feng Li. 基于缺省项恢复的汉语句法分析改进研究[J]. , 2013, 28(6): 1106 -1116 .
[7] Guo-Jie Li. Preface[J]. , 2015, 30(2): 225 -226 .
[8] Tao Xie. Preface[J]. , 2015, 30(5): 933 -934 .
[9] Xin Bi, Xiang-Guo Zhao, Guo-Ren Wang. 基于节点分发的分布式Twig查询处理技术[J]. , 2017, 32(1): 78 -92 .
[10] Renzhen Ye, Xuelong Li. 基于协同表达的异常事件检测[J]. , 2017, 32(3): 470 -479 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: