三元概念的启发式构建及其在社会化推荐中的应用

doi:10.11896/jsjkx.200500136

计算机科学 ›› 2021, Vol. 48 ›› Issue (6): 234-240.doi: 10.11896/jsjkx.200500136

三元概念的启发式构建及其在社会化推荐中的应用

刘忠慧¹, 赵琦¹, 邹璐¹, 闵帆^1,2

1 西南石油大学计算机科学学院成都610500
2 西南石油大学人工智能研究院成都610500

收稿日期:2020-05-27 修回日期:2020-08-17 出版日期:2021-06-15 发布日期:2021-06-03
通讯作者: 闵帆(minfan@swpu.edu.cn)
基金资助:
国家自然科学基金(41604114);四川省青年科技创新团队(2019JDTD0017)

Heuristic Construction of Triadic Concept and Its Application in Social Recommendation

LIU Zhong-hui¹, ZHAO Qi¹, ZOU Lu¹, MIN Fan^1,2

1 School of Computer Science,Southwest Petroleum University,Chengdu 610500,China
2 Institute for Artificial Intelligence,Southwest Petroleum University,Chengdu 610500,China

Received:2020-05-27 Revised:2020-08-17 Online:2021-06-15 Published:2021-06-03
About author:LIU Zhong-hui,born in 1980,postgra-duate,associate professor,master supervisor,is a member of China Compu-ter Federation.Her main research in-terests include machine learning,formal concept analysis and rough set.(Lz_hui@126.com)
MIN Fan,born in 1973,Ph.D,professor,Ph.D supervisor,is a member of CAAI granule computing and knowledge discovery committee and China Computer Federaton.His main research interests include granular computing,recommender systems and active learning.
Supported by:
National Natural Science Foundation of China(41604114) and Sichuan Province Youth Science and Technology Innovation Team(2019JDTD0017).

摘要/Abstract

摘要： 形式概念分析作为知识发现的方法,在理论分析和实际应用中已经取得很多成果。随着三维数据的涌现,许多学者开始了对三元形式概念分析的研究。但是,目前该领域的研究和应用较少,尤其还没有被应用到推荐系统。文中介绍了三元概念的构建及其社会化推荐应用。首先设计启发式信息,构造覆盖所有用户的三元概念集合,启发式信息旨在生成外延和内涵均有一定规模的强概念;然后根据拟推荐项目的属性来筛选用户合适的社会关系,并结合项目在概念中的流行度实现推荐预测。文中分别在真实数据集和抽样数据集中进行了3个实验。实验1对比了启发式方法和∨_oc运算构造的三元概念数量及其运行时间,其中∨_oc运算构造的概念数量少、耗时长且对推荐的提升效果不明显;实验2对比了推荐效果的精确度、召回率和F1值,揭示了增加条件可以有效提升推荐效果;实验3的结果表明,基于三元概念的推荐算法的推荐效果优于KNN及GRHC。

关键词: 流行度, 启发式算法, 三元形式概念分析, 社会化推荐, 项目条件

Abstract: Formal concept analysis is a knowledge discovery method that has great achievements in theory and application.Recently,with the emergence of three-dimensional data,triadic formal concept analysis has been developed.However,there are few researches and applications in this field,especially it has not been applied to recommendation systems.This paper proposes an efficient triadic concept set construction method and applies it to social recommendation.Firstly,the heuristic information is designed to generate a set of triadic concepts covering all users.Heuristic information aims to construct strong concepts with a certain scale of extension and intension.Then,appropriate social relations are screened through the attributes of the proposed items,and the recommendation prediction is realized by combining the popularity of the items in the concept.Three experiments are carried out in real data set and sampled data set respectively.In the first experiment,the number of triadic concepts and running time constructed by the heuristic method and ∨_oc operation are compared respectively.The concepts constructed by the ∨_oc operation do not significantly improve the recommendation effect.The second experiment compares the accuracy,recall rate and F1 of the recommendation effect.It reveals that increasing the number of conditions can effectively improve the recommendation effect.The results of the last experiment show that the recommendation effect of the new algorithm is better than that of KNN and GRHC.

Key words: Heuristic algorithm, Item conditions, Popularity, Social recommendation, Triadic formal concept analysis

中图分类号:

TP181

刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用[J]. 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136

LIU Zhong-hui, ZHAO Qi, ZOU Lu, MIN Fan. Heuristic Construction of Triadic Concept and Its Application in Social Recommendation[J]. Computer Science, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136

参考文献

[1]WILLE R.Restructuring Lattice Theory:An Approach Based on Hierarchies of Concepts[J].Springer,1982,83:314-339.
[2]GANTER B,STUMME G,WILLE R.Formal Concept Analysis:Theory and Applications[J].J Ucs,2004,10(8):926.
[3]LI J H,MEI C L,LV Y J.Knowledge reduction in decision formal contexts[J].Knowledge-based Systems,2011,24(5):709-715.
[4]ZHI H L,LI J H.Granule Description Based on Necessary Attribute Analysis[J].Chinese Journal of Computers,2018,41(12):2702-2719.
[5]GODIN R,MISSAOUI R,ALAOUI H.Incremental concept formation algorithms based on Galois (concept) lattices[J].Computational Intelligence,1995,11(2):246-267.
[6]LI Y,LIU Z T,CHEN L,et al.Attribute-based IncrementalFormation Algorithm of Concept Lattice[J].Journal of Chinese Computer Systems,2004(10):1768-1771.
[7]XIE Z P,LIU Z T.A Fast Incremental Algorithm for Building Concept Lattice [J].Chinese Journal of Computers,2002(5):490-496.
[8]ZHANG W X,WEI L,QI J J.Theory and Method of Attribute Reduction in Concept Lattice[J].Science in China Ser.E Information Sciences,2005(6):628-639.
[9]YAO Y Y.Concept lattices in rough set theory[C]//IEEE Annual Meeting of the Fuzzy Information.2004:796-801.
[10]LI J H,WU W Z,DENG S.Multi-scale theory in formal concept analysis[J].Journal of Shandong University(Natural Science),2019,54(2):34-44.
[11]CHENG H W,WANG L M,ZHANG Z.Top-N Recommendation Algorithm Based on Conceptual Neighborhood[J].Journal of Chinese Computer Systems,2017,38(11):2553-2559.
[12]LI H T,HE K Q,WANG J,et al.A Friends Recommendation Algorithm Based on Formal Concept Analysis and Random Walk in Social Network[J].Advanced Engineering Sciences,2015,47(6):131-138.
[13]LIU Z H,ZOU L,YANG M,et al.Group recommendation with the concept of heuristic construction[J].Journal of Frontiers of Computer Science and Technology,2020,14(4):703-711.
[14]IGNATOV D I,KUZNETSOV S O.Concept-based recommendations for internet advertisement[J].Computer Science,2009,433:157-166.
[15]LEHMANN F,WILLE R.A Triadic Approach to Formal Concept Analysis[C]//International Conference on Conceptual Structures Applications.Springer,1995:32-43.
[16]WANG X,JIANG S,LI J Y,et al.A Construction Method of Triadic Concepts[J].Journal of Computer Research andDevelo-pment,2019,56(4):844-853.
[17]WANG X,TAN S W,LI J Y,et al.Constructions and simplifications of concept lattices based on conditional attribute implications[J].Journal of Nanjing University(Natural Science),2019,55(4):553-563.
[18]TANG Y Q,FAN M,LI J H.Cognitive system model and approach to transformation of information granules under triadic formal concept analysis[J].Journal of Shandong University(Natural Science),2014,49(8):102-106.
[19]TANG Y Q,FAN M,LI J H.An information fusion technology for triadic decision contexts[J].Int.J.Mach.Learn.& Cyber.2016,7:13-24.
[20]KUMAR C A,MOULISWARAN S C,LI J H,et al.Role based access control design using Triadic concept analysis[J].Journal of Central South University,2016,23(12):3183-3191.
[21]WEI L,WAN Q,QIAN T,et al.An overview of triadic concept analysis[J].Journal of Northwest University(Natural Science Edition),2014,44(5):689-699.
[22]LI Z,ZHANG Z,WANG L M.Research on Text Classification Algorithm Based on Triadic Concept Analysis[J].Computer Science,2017,44(8):207-215.
[23]LUO X,OUYANG Y X,XIONG Z,et al.The effect of similarity support in K-Nearest-Neighborhood based collaborative filtering[J].Chinese Journal of Computers,2010,33(8):1437-1445.
[24]HUANG L W,JIANG B T,LYU S Y,et al.Survey on Deep Learning Based Recommender Systems [J].Chinese Journal of Computers,2018,41(7):1619-1647.
[25]MENG X W,LIU S D,ZHANG Y J,et al.Research on social recommender systems[J].Ruan Jian Xue Bao/Journal of Software,2015,26(6):1356-1372.
[26]ZHANG Q S,WENG L J.Review of Social Recommender Systems[J].Computer Engineering and Applications,2020,56(1):1-10.
[27]BOUCHER-RYAN P D,BRIDGE D.Collaborative Recommending using Formal Concept Analysis[J].Knowledge-Based Systems,2006,19(5):309-315.

相关文章 15

[1]	谢柏林, 黎琦, 邝建. 基于隐半马尔可夫模型的微博流行信息检测方法 Microblog Popular Information Detection Based on Hidden Semi-Markov Model 计算机科学, 2022, 49(6A): 291-296. https://doi.org/10.11896/jsjkx.210800011
[2]	耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[3]	韩立锋, 陈莉. 融合用户属性与项目流行度的用户冷启动推荐模型 User Cold Start Recommendation Model Integrating User Attributes and Item Popularity 计算机科学, 2021, 48(2): 114-120. https://doi.org/10.11896/jsjkx.200900152
[4]	郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[5]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[6]	张志扬, 张凤荔, 谭琪, 王瑞锦. 基于深度学习的信息级联预测方法综述 Review of Information Cascade Prediction Methods Based on Deep Learning 计算机科学, 2020, 47(7): 141-153. https://doi.org/10.11896/jsjkx.200300130
[7]	张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078
[8]	杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132
[9]	罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048
[10]	张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501.
[11]	罗建桢,蔡君,刘燕,赵慧民. 一种基于内容流行度和社团重要度的ICN缓存与替换策略 Caching and Replacing Strategy in Information-centric Network Based on Content Popularity and Community Importance 计算机科学, 2018, 45(7): 116-121. https://doi.org/10.11896／j.issn.1002-137X.2018.07.019
[12]	何佶星,陈汶滨,牟斌皓. 流行度划分结合平均偏好权重的协同过滤个性化推荐算法 Coordination Filtering Personalized Recommendation Algorithm Considering Average Preference Weight and Popularity Division 计算机科学, 2018, 45(6A): 493-496.
[13]	史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法 Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading 计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014
[14]	王刚, 蒋军, 王含茹. 社会化推荐研究综述 Review of Social Recommendation 计算机科学, 2018, 45(11A): 37-42.
[15]	单天羽, 管煜旸. 基于种群多样性的可变种群缩减差分进化算法 Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity 计算机科学, 2018, 45(11A): 160-166.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

三元概念的启发式构建及其在社会化推荐中的应用

Heuristic Construction of Triadic Concept and Its Application in Social Recommendation

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0