基于点割集图分割的矩阵变换与分解的推荐算法

计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 272-279.doi: 10.11896/jsjkx.210600159

基于点割集图分割的矩阵变换与分解的推荐算法

何亦琛¹, 毛宜军¹, 谢贤芬², 古万荣¹

1 华南农业大学数学与信息学院广州 510642
2 暨南大学经济学院广州 510632

出版日期:2022-06-10 发布日期:2022-06-08
通讯作者: 古万荣(guwanrong@scau.edu.cn)
作者简介:(heyichen666@hotmail.com)
基金资助:
全国统计科学研究项目(2020LY018);全国统计科学研究重点项目(2019LZ37);广东省社会科学项目(GD19CGL34);国家重点研发计划(2017YFC1601701);广东省农业厅创新团队项目(2019KJ130)

Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation

HE Yi-chen¹, MAO Yi-jun¹, XIE Xian-fen², GU Wan-rong¹

1 School of Mathematics and Information,South China Agricultural University,Guangzhou 510642,China
2 School of Economy,Jinan University,Guangzhou 510632,China

Online:2022-06-10 Published:2022-06-08
About author:HE Yi-chen,born in 1998,postgra-duate,is a student member of China Computer Federation.His main research interests include recommendation system and data mining.
GU Wan-rong,born in 1982,Ph.D,assistant professor.His main research interests include recommendation system,information retrieval and big data processing.
Supported by:
National Statistical Science Research Project(2020LY018),National Statistical Science Research Key Project(2019LZ37),Social Science Project of Guangdong Province(GD19CGL34),National Key Research and Development Project(2017YFC1601701) and Department of Agriculture of Guangdong Provincial Innovation Research Team Project(2019KJ130).

摘要/Abstract

摘要： 基于模型的协同过滤算法通过矩阵分解来将用户偏好以及物品属性用隐变量来表示,但现有的矩阵分解算法很难应对个性化推荐系统中严重的数据稀疏性以及数据变化性所带来的问题。针对上述问题,提出了基于双边块对角矩阵的矩阵分解算法。首先通过基于社区发现的点割集图分割算法将原始的稀疏矩阵转换成双边块对角矩阵,将具有相同偏好的用户以及相似特征的物品归并到同一个对角块中,然后将结构中的对角块和双边拼接成数个密度较高的子矩阵。实验结果表明,对这几个密度有提高的子矩阵进行并行分解,基于其分解结果进行原始矩阵的预测,能够有效缓解矩阵分解中数据稀疏性所带来的问题,既能提升预测的精度,又能提高推荐结果的可解释性。同时,每个子对角块都能并行独立分解,能达到提高算法效率的目的。

关键词: 矩阵分解, 社区发现, 推荐系统, 协同过滤

Abstract: Model-based collaborative filtering algorithms usually express user's preferences and item's attributes by latent factors through matrix factorization,but the traditional matrix factorization algorithm is difficult to deal with the serious data sparsity and data variability problems in the recommendation system.To solve the above problem,a matrix factorization algorithm based on bordered block diagonal matrix is proposed.Firstly,the original sparse matrix is transformed into bordered block diagonal matrix by a graph partitioning algorithm based on community discovery,which merges users with the same preference and items with similar characteristics into the same diagonal block,and then splices the diagonal blocks and the bordered into several sub-diagonal matrices which have higher densities.The experimental results show that,by decomposing the sub-diagonal matrices in parallel can not only improve the precision of prediction,but also improve the interpretability of the recommendation results.At the same time,each sub-diagonal matrix can be decomposed independently and in parallel,which can improve the efficiency of the algorithm.

Key words: Collaborative filtering, Community discovery, Matrix factorization, Recommendation system

中图分类号:

TP391.3

何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法[J]. 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159

HE Yi-chen, MAO Yi-jun, XIE Xian-fen, GU Wan-rong. Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation[J]. Computer Science, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159

参考文献

[1] BOBADILLA J,ALONSO S,HERNANDO A.Deep learning architecture for collaborative filtering recommender systems[J].Applied Sciences,2020,10(7):2441.
[2] WU L,GE Y,LIU Q,et al.Modeling the Evolution of Users' Preferences and Social Links in Social Networking Services[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(6):1240-1253.
[3] BOBADILLA J,ORTEGA F,GUTIERREZ A,et al.Classification-based Deep Neural Network Architecture for Collaborative Filtering Recommender Systems[J].International Journal of Interactive Multimedia & Artificial Intelligence,2020,6(1):68-77.
[4] FENG C,LIANG J,SONG P,et al.A fusion collaborative filtering method for sparse data in recommender systems[J].Information Sciences,2020,521:365-379.
[5] LI D S,CHEN C,LV Q,et al.An algorithm for efficient privacy-preserving item-based collaborative filtering[J].Future Ge-neration Computer Systems,2016,55:311-320.
[6] SAMMEL M D,RYAN L M.Latent variable models with fixed effects[J].Biometrics,1996,52:650-663.
[7] DEERWESTER S,DUMAIS S T,FURNAS G W,et al.Indexing by latent semantic analysis[J].Journal of the American society for information science,1990,41(6):391-407.
[8] LEE D D,SEUNG H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.
[9] MNIH A,SALAKHUTDINOV R R.Probabilistic matrix fac-torization[J].Advances in Neural Information Processing Systems,2007,20:1257-1264.
[10] NAJAFABADI M K,MAHRIN M N,CHUPRAT S,et al.Improving the accuracy of collaborative filtering recommendations using clustering and association rules mining on implicit data[J].Computers in Human Behavior,2017,67(FEB.):113-128.
[11] WANG Y G,SONG Z Z,XIAO C L.Collaborative filtering recommendation algorithm based on improved clustering and matrix factorization[J].Journal of Computer Applications,2018,38(4):1001-1006.
[12] ABBASI-MOUD Z,VAHDAT-NEJAD H,SADRI J.Tourismrecommendation system based on semantic clustering and sentiment analysis[J].Expert Systems with Applications,2021,167:114324.
[13] AALDERING L J,LEKER J,SONG C H.Recommending untapped M&A opportunities:A combined approach using principal component analysis and collaborative filtering[J].Expert Systems with Applications,2019,125:221-232.
[14] NGUYEN T T.On the Edge and Cloud:Recommendation Systems with Distributed Machine Learning[C]//2021 InternationalConference on Information Technology(ICIT).IEEE,2021:929-934.
[15] YU H F,HSIEH C J,SI S,et al.Scalable coordinate descent ap-proaches to parallel matrix factorization for recommender systems[C]//2012 IEEE 12th International Conference on Data Mining.IEEE Computer Society,2012:765-774.
[16] LIU Q Q,LUO Y L,WANG Y F,et al.Hybrid Recommendation Algorithm Based on SVD Filling[J].Computer Science,2019,46(S1):468-472.
[17] SU Y,ZHOU K,ZHANG X,et al.A parallel multi-objective evo-lutionary algorithm for community detection in large-scale complex networks[J].Information Sciences,2021,576:374-392.
[18] OSABA E,DEL SER J,CAMACHO D,et al.Community detection in networks using bio-inspired optimization:Latest developments,new results and perspectives with a selection of recent meta-heuristics[J/OL].Applied Soft Computing,2020,87.https://doi.org/10.1016/j.asoc.2019.106010.
[19] FORTUNATO S,HRIC D.Community detection in networks:A user guide[J].Physics reports,2016,659:1-44.
[20] ZHAO W J,ZHANG F B,LIU J L.Review on community Detection in Complex Networks[J].Computer Science,2020,47(2):10-20.
[21] GLIGORIJEVIĆ V,PANAGAKIS Y,ZAFEIRIOU S.Non-negative matrix factorizations for multiplex network analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2018,41(4):928-940.
[22] SINGH A P,GORDON G J.Relational learning via collectivematrix factorization[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Association for Computing Machinery.2008:650-658.
[23] KARYPIS G,KUMAR V.A fast and high quality multilevelscheme for partitioning irregular graphs[J].SIAM Journal on Scientific Computing,1998,20(1):359-392.
[24] KOREN Y,BELL R,VOLINSKY C.Matrix factorization techniques for recommender systems[J].Computer,2009,42(8):30-37.
[25] KOREN Y.Factorization meets the neighborhood:a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.Association for Computing Machinery.2008:426-434.
[26] SALAKHUTDINOV R,MNIH A.Bayesian probabilistic matrix factorization using Markov chain Monte Carlo[C]//Proceedings of the 25th International Conference on Machine Learning.Association for Computing Machinery.2008:880-887.
[27] LUO X,ZHOU M C,XIA Y B,et al.An efficient non-negative matrix-factorization-based approach to collaborative filtering for recommender systems[J].IEEE Transactions on Industrial Informatics,2014,10(2):1273-1284.

相关文章 15

[1]	程章桃, 钟婷, 张晟铭, 周帆. 基于图学习的推荐系统研究综述 Survey of Recommender Systems Based on Graph Learning 计算机科学, 2022, 49(9): 1-13. https://doi.org/10.11896/jsjkx.210900072
[2]	王冠宇, 钟婷, 冯宇, 周帆. 基于矢量量化编码的协同过滤推荐方法 Collaborative Filtering Recommendation Method Based on Vector Quantization Coding 计算机科学, 2022, 49(9): 48-54. https://doi.org/10.11896/jsjkx.210700109
[3]	秦琪琦, 张月琴, 王润泽, 张泽华. 基于知识图谱的层次粒化推荐方法 Hierarchical Granulation Recommendation Method Based on Knowledge Graph 计算机科学, 2022, 49(8): 64-69. https://doi.org/10.11896/jsjkx.210600111
[4]	方义秋, 张震坤, 葛君伟. 基于自注意力机制和迁移学习的跨领域推荐算法 Cross-domain Recommendation Algorithm Based on Self-attention Mechanism and Transfer Learning 计算机科学, 2022, 49(8): 70-77. https://doi.org/10.11896/jsjkx.210600011
[5]	帅剑波, 王金策, 黄飞虎, 彭舰. 基于神经架构搜索的点击率预测模型 Click-Through Rate Prediction Model Based on Neural Architecture Search 计算机科学, 2022, 49(7): 10-17. https://doi.org/10.11896/jsjkx.210600009
[6]	齐秀秀, 王佳昊, 李文雄, 周帆. 基于概率元学习的矩阵补全预测融合算法 Fusion Algorithm for Matrix Completion Prediction Based on Probabilistic Meta-learning 计算机科学, 2022, 49(7): 18-24. https://doi.org/10.11896/jsjkx.210600126
[7]	孙晓寒, 张莉. 基于评分区域子空间的协同过滤推荐算法 Collaborative Filtering Recommendation Algorithm Based on Rating Region Subspace 计算机科学, 2022, 49(7): 50-56. https://doi.org/10.11896/jsjkx.210600062
[8]	蔡晓娟, 谭文安. 一种改进的融合相似度和信任度的协同过滤算法 Improved Collaborative Filtering Algorithm Combining Similarity and Trust 计算机科学, 2022, 49(6A): 238-241. https://doi.org/10.11896/jsjkx.210400088
[9]	洪志理, 赖俊, 曹雷, 陈希亮, 徐志雄. 基于遗憾探索的竞争网络强化学习智能推荐方法研究 Study on Intelligent Recommendation Method of Dueling Network Reinforcement Learning Based on Regret Exploration 计算机科学, 2022, 49(6): 149-157. https://doi.org/10.11896/jsjkx.210600226
[10]	郭亮, 杨兴耀, 于炯, 韩晨, 黄仲浩. 基于注意力机制和门控网络相结合的混合推荐系统 Hybrid Recommender System Based on Attention Mechanisms and Gating Network 计算机科学, 2022, 49(6): 158-164. https://doi.org/10.11896/jsjkx.210500013
[11]	熊中敏, 舒贵文, 郭怀宇. 融合用户偏好的图神经网络推荐模型 Graph Neural Network Recommendation Model Integrating User Preferences 计算机科学, 2022, 49(6): 165-171. https://doi.org/10.11896/jsjkx.210400276
[12]	余皑欣, 冯秀芳, 孙静宇. 结合物品相似性的社交信任推荐算法 Social Trust Recommendation Algorithm Combining Item Similarity 计算机科学, 2022, 49(5): 144-151. https://doi.org/10.11896/jsjkx.210300217
[13]	陈壮, 邹海涛, 郑尚, 于化龙, 高尚. 基于用户覆盖及评分差异的多样性推荐算法 Diversity Recommendation Algorithm Based on User Coverage and Rating Differences 计算机科学, 2022, 49(5): 159-164. https://doi.org/10.11896/jsjkx.210300263
[14]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[15]	唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法 EWCC Community Discovery Algorithm for Two-Layer Network 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed