近似概念的遗传生成算法及其推荐应用

doi:10.11772/j.issn.1001-9081.2021041155

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (2): 412-418.DOI: 10.11772/j.issn.1001-9081.2021041155

• 人工智能 • 上一篇

近似概念的遗传生成算法及其推荐应用

刘忠慧¹, 王梓宥¹, 闵帆¹^,²()

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

收稿日期:2021-07-05 修回日期:2021-07-27 接受日期:2021-08-05 发布日期:2021-11-02 出版日期:2022-02-10
通讯作者: 闵帆
作者简介:刘忠慧（1980—），女，四川南充人，副教授，硕士，CCF会员，主要研究方向：机器学习、形式概念分析、粗糙集；
王梓宥（1998—），女，四川南充人，硕士研究生，主要研究方向：形式概念分析、机器学习、推荐系统；
闵帆（1973—），男，重庆人，教授，博士，CCF会员，主要研究方向：粒计算、推荐系统、主动学习。

Genetic algorithm for approximate concept generation and its recommendation application

Zhonghui LIU¹, Ziyou WANG¹, Fan MIN¹^,²()

^1.School of Computer Science，Southwest Petroleum University，Chengdu Sichuan 610500，China
^2.Institution for Artificial Intelligence，Southwest Petroleum University，Chengdu Sichuan 610500，China

Received:2021-07-05 Revised:2021-07-27 Accepted:2021-08-05 Online:2021-11-02 Published:2022-02-10
Contact: Fan MIN
About author:LIU Zhonghui， born in 1980， M. S.， associate professor. Her research interests include machine learning， formal concept analysis， rough set.
WANG Ziyou， born in 1998， M. S. candidate. Her research interests include formal concept analysis， machine learning， recommender system.
MIN Fan， born in 1973， Ph. D.， professor. His research interests include granular computing， recommender system， active learning.

摘要/Abstract

摘要：

由于构造概念格的时间复杂度高，在推荐领域已有研究者提出用概念集合来替代概念格。但目前对概念集合的研究未考虑近似概念的作用，因此将近似概念引入推荐应用，并提出基于遗传算法（GA）的近似概念生成算法（ACGA）和相应的推荐应用方案。首先由启发式方法生成初始概念集合；其次用交叉算子对初始概念集合中的概念的外延两两求交集，从而得到近似概念；然后用选择算子根据外延相似度以及相关阈值筛选出满足条件的近似概念来更新概念集合，而不满足条件的近似概念由变异算子按照用户相似度进行外延调整，直到其满足条件；最后基于新的概念集合，根据邻居用户的偏好向目标用户进行推荐。在4个推荐系统常用的数据集上进行实验，结果表明ACGA生成的近似概念提升了推荐效果，尤其是在2个电影评分数据集上，ACGA与概率矩阵分解（PMF）算法相比，F1值提升了近78%，召回率提升了近104%，精确度提升了近57%；与K最近邻（KNN）算法比较，精确度提升了近12%。

关键词: 形式概念分析, 概念格, 遗传算法, 近似概念, 推荐系统

Abstract:

Some researchers suggest replacing concept lattices with concept sets in recommendation field due to the high time complexity of concept lattice construction. However， the current studies on concept sets do not consider the role of approximate concepts. Therefore， approximate concepts were introduced into recommendation application， and a genetic algorithm based Approximate Concept Generation Algorithm （ACGA） and the corresponding recommendation scheme were proposed. Firstly， the initial concept set was generated through the heuristic method. Secondly， the crossover operator was used to obtain the approximate concepts by calculating the extension intersection set of any two concepts in the initial concept set. Thirdly， the selection operator was used to select the approximate concepts meeting the conditions according to the similarity of extensions and the relevant threshold to update the concept set， and the mutation operator was adopted to adjust the approximate concepts without meeting the conditions to meet the conditions according to the user similarity. Finally， the recommendation to the target users was performed according to the neighboring users’ preferences based on the new concept set. Experimental results show that， on four datasets commonly used by recommender systems， the approximate concepts generated by ACGA algorithm can improve the recommendation effect， especially on two movie scoring datasets， compared with Probabilistic Matrix Factorization （PMF） algorithm， ACGA algorithm has the F1-score， recall and precision increased by nearly 78%， 104% and 57% respectively； and compared with K-Nearest Neighbor （KNN） algorithm， ACGA algorithm has the precision increased by nearly 12%.

Key words: formal concept analysis, concept lattice, Genetic Algorithm (GA), approximate concept, recommender system

中图分类号:

TP181

刘忠慧, 王梓宥, 闵帆. 近似概念的遗传生成算法及其推荐应用[J]. 计算机应用, 2022, 42(2): 412-418.

Zhonghui LIU, Ziyou WANG, Fan MIN. Genetic algorithm for approximate concept generation and its recommendation application[J]. Journal of Computer Applications, 2022, 42(2): 412-418.

图/表 5

表1 一个形式背景的例子

Tab. 1 Example of formal context

$U$	$M$
$U$	$m 0$	$m 1$	$m 2$	$m 3$	$m 4$	$m 5$	$m 6$
$u 0$	0	1	0	1	1	1	0
$u 1$	0	1	1	0	1	0	0
$u 2$	1	0	1	1	0	0	1
$u 3$	1	0	0	1	0	1	0
$u 4$	1	1	1	1	0	0	1
$u 5$	1	1	0	0	1	0	0
$u 6$	0	1	0	1	0	1	1
$u 7$	1	0	1	0	1	0	1
$u 8$	0	0	1	0	0	0	1
$u 9$	1	0	1	0	0	1	0

表1 一个形式背景的例子

Tab. 1 Example of formal context

$U$	$M$
$U$	$m 0$	$m 1$	$m 2$	$m 3$	$m 4$	$m 5$	$m 6$
$u 0$	0	1	0	1	1	1	0
$u 1$	0	1	1	0	1	0	0
$u 2$	1	0	1	1	0	0	1
$u 3$	1	0	0	1	0	1	0
$u 4$	1	1	1	1	0	0	1
$u 5$	1	1	0	0	1	0	0
$u 6$	0	1	0	1	0	1	1
$u 7$	1	0	1	0	1	0	1
$u 8$	0	0	1	0	0	0	1
$u 9$	1	0	1	0	0	1	0

表2 一个评分形式背景的例子

Tab. 2 Example of scoring formal context

$U$	$M$
$U$	$m 0$	$m 1$	$m 2$	$m 3$	$m 4$	$m 5$	$m 6$
$u 0$	0	1	0	5	1	1	0
$u 1$	0	3	2	0	1	0	0
$u 2$	2	0	5	2	0	0	1
$u 3$	4	0	0	1	0	3	0
$u 4$	1	2	1	1	0	0	1
$u 5$	3	4	0	0	1	0	0
$u 6$	0	2	0	1	0	5	1
$u 7$	2	0	2	0	1	0	5
$u 8$	0	0	3	0	0	0	3
$u 9$	5	0	2	0	0	1	0

表2 一个评分形式背景的例子

Tab. 2 Example of scoring formal context

$U$	$M$
$U$	$m 0$	$m 1$	$m 2$	$m 3$	$m 4$	$m 5$	$m 6$
$u 0$	0	1	0	5	1	1	0
$u 1$	0	3	2	0	1	0	0
$u 2$	2	0	5	2	0	0	1
$u 3$	4	0	0	1	0	3	0
$u 4$	1	2	1	1	0	0	1
$u 5$	3	4	0	0	1	0	0
$u 6$	0	2	0	1	0	5	1
$u 7$	2	0	2	0	1	0	5
$u 8$	0	0	3	0	0	0	3
$u 9$	5	0	2	0	0	1	0

表3 实验数据集

Tab. 3 Experimental datasets

数据集	大小	稀疏度
ML-100K	943 $×$ 1 682	0.937 0
ML-1M	6 040 $×$ 3 952	0.958 1
EachMovie	72 916 $×$ 1 628	0.992 2
Jester	24 983 $×$ 101	0.755 1

表3 实验数据集

Tab. 3 Experimental datasets

数据集	大小	稀疏度
ML-100K	943 $×$ 1 682	0.937 0
ML-1M	6 040 $×$ 3 952	0.958 1
EachMovie	72 916 $×$ 1 628	0.992 2
Jester	24 983 $×$ 101	0.755 1

表4 ACGA与GRHC算法以及KNN算法在抽样数据集上的对比

Tab. 4 Comparison of ACGA， GRHC algorithm and KNN algorithm on sampling datasets

数据集	大小	稀疏度	算法	精确度	召回率	F1值
ML-100K-sd1	200 $×$ 420	0.941 3	ACGA	0.166428	0.229 931	0.193092
			GRHC	0.131 462	0.264881	0.175 716
			KNN（k=3）	0.145 847	0.228 175	0.177 950
ML-100K-sd2	200 $×$ 420	0.941 2	ACGA	0.164634	0.254717	0.200000
			GRHC	0.148 995	0.225 367	0.179 391
			KNN（k=3）	0.148 990	0.247 379	0.185 973
ML-1M-sd1	300 $×$ 200	0.964 8	ACGA	0.126 230	0.294455	0.176707
			GRHC	0.132 931	0.252 390	0.174 142
			KNN（k=3）	0.195652	0.120 459	0.149 112
ML-1M-sd2	300 $×$ 200	0.975 8	ACGA	0.117 155	0.144330	0.129330
			GRHC	0.087 850	0.121 134	0.101 841
			KNN（k=3）	0.132075	0.090 206	0.107 198
EachMovie-sd	2 000 $×$ 1 648	0.992 2	ACGA	0.193 876	0.313215	0.239 503
			GRHC	0.247 783	0.241 192	0.244442
			KNN（k=3）	0.300627	0.175 391	0.221 535
Jester-sd1	300 $×$ 100	0.831 2	ACGA	0.197 620	0.142970	0.197620
			GRHC	0.321 238	0.142 654	0.197 571
			KNN（k=3）	0.383024	0.084 834	0.138 903
Jester-sd2	300 $×$ 100	0.839 4	ACGA	0.313 687	0.133985	0.187768
			GRHC	0.320 066	0.129 182	0.184 071
			KNN（k=3）	0.394344	0.083 140	0.137 327

表4 ACGA与GRHC算法以及KNN算法在抽样数据集上的对比

Tab. 4 Comparison of ACGA， GRHC algorithm and KNN algorithm on sampling datasets

数据集	大小	稀疏度	算法	精确度	召回率	F1值
ML-100K-sd1	200 $×$ 420	0.941 3	ACGA	0.166428	0.229 931	0.193092
			GRHC	0.131 462	0.264881	0.175 716
			KNN（k=3）	0.145 847	0.228 175	0.177 950
ML-100K-sd2	200 $×$ 420	0.941 2	ACGA	0.164634	0.254717	0.200000
			GRHC	0.148 995	0.225 367	0.179 391
			KNN（k=3）	0.148 990	0.247 379	0.185 973
ML-1M-sd1	300 $×$ 200	0.964 8	ACGA	0.126 230	0.294455	0.176707
			GRHC	0.132 931	0.252 390	0.174 142
			KNN（k=3）	0.195652	0.120 459	0.149 112
ML-1M-sd2	300 $×$ 200	0.975 8	ACGA	0.117 155	0.144330	0.129330
			GRHC	0.087 850	0.121 134	0.101 841
			KNN（k=3）	0.132075	0.090 206	0.107 198
EachMovie-sd	2 000 $×$ 1 648	0.992 2	ACGA	0.193 876	0.313215	0.239 503
			GRHC	0.247 783	0.241 192	0.244442
			KNN（k=3）	0.300627	0.175 391	0.221 535
Jester-sd1	300 $×$ 100	0.831 2	ACGA	0.197 620	0.142970	0.197620
			GRHC	0.321 238	0.142 654	0.197 571
			KNN（k=3）	0.383024	0.084 834	0.138 903
Jester-sd2	300 $×$ 100	0.839 4	ACGA	0.313 687	0.133985	0.187768
			GRHC	0.320 066	0.129 182	0.184 071
			KNN（k=3）	0.394344	0.083 140	0.137 327

表5 ACGA与其他算法在完整数据集上的对比

Tab. 5 Comparison of ACGA and other algorithms on complete datasets

数据集	算法	精确度	召回率	$F 1$ 值
ML-100K	ACGA	0.221 558	0.279 950	0.247 355
	GRHC	0.274392	0.179 850	0.217 282
	PMF	0.135 033	0.137 450	0.136 231
	KNN	0.197 734	0.347350	0.252009
ML-1M	ACGA	0.189944	0.250 171	0.215 937
	GRHC	0.158 647	0.333 543	0.215 021
	PMF	0.126 818	0.122 410	0.124 576
	KNN	0.171 339	0.353130	0.230728

表5 ACGA与其他算法在完整数据集上的对比

Tab. 5 Comparison of ACGA and other algorithms on complete datasets

数据集	算法	精确度	召回率	$F 1$ 值
ML-100K	ACGA	0.221 558	0.279 950	0.247 355
	GRHC	0.274392	0.179 850	0.217 282
	PMF	0.135 033	0.137 450	0.136 231
	KNN	0.197 734	0.347350	0.252009
ML-1M	ACGA	0.189944	0.250 171	0.215 937
	GRHC	0.158 647	0.333 543	0.215 021
	PMF	0.126 818	0.122 410	0.124 576
	KNN	0.171 339	0.353130	0.230728

参考文献 28

1	WILLE R. Concept lattices and conceptual knowledge systems［J］. Computers and Mathematics with Applications， 1992， 23（6/7/8/9）： 493-515. 10.1016/0898-1221(92)90120-7
2	LI J H， MEI C L， LV Y J. Incomplete decision contexts： approximate concept construction， rule acquisition and knowledge reduction［J］. International Journal of Approximate Reasoning， 2013， 54（1）： 149-165. 10.1016/j.ijar.2012.07.005
3	LI M Z， WANG G Y. Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts［J］. Knowledge-Based Systems， 2016， 91： 165-178. 10.1016/j.knosys.2015.10.010
4	范妍，魏玲. k级近似概念及其应用［J］.西北大学学报（自然科学版）， 2018， 48（6）： 803-809. 10.16152/j.cnki.xdxbzr.2018-06-007
	FAN Y， WEI L. k grade approximate concept and its application［J］. Journal of Northwest University （Natural Science Edition）， 2018， 48（6）： 803-809. 10.16152/j.cnki.xdxbzr.2018-06-007
5	WAN Q， WEI L. Approximate concepts acquisition based on formal contexts［J］. Knowledge-Based Systems， 2015， 75： 78-86. 10.1016/j.knosys.2014.11.020
6	GUO L K， LI Q G， ZHANG G Q. A representation of continuous domains via relationally approximable concepts in a generalized framework of formal concept analysis［J］. International Journal of Approximate Reasoning， 2019， 114： 29-43. 10.1016/j.ijar.2019.08.007
7	李进金，李克典，吴燕华.概念格上的近似概念［J］.南京大学学报（自然科学版）， 2013， 49（2）： 244-249.
	LI J J， LI K D， WU Y H. The approximation concept of lattices［J］. Journal of Nanjing University （Natural Sciences）， 2013， 49（2）： 244-249.
8	ZOU C F， ZHANG D Q， WAN J F， et al. Using concept lattice for personalized recommendation system design［J］. IEEE Systems Journal， 2017， 11（1）： 305-314. 10.1109/jsyst.2015.2457244
9	DONG Y， WU Y， LIU Z T. Research on two main construction methods of concept lattices［J］. Journal of Shanghai Jiaotong University （Science）， 2019， 24（2）： 243-253. 10.1007/s12204-019-2058-6
10	ZHANG J P， LIU R H， ZOU L G， et al. A new rapid incremental algorithm for constructing concept lattices［J］. Information， 2019， 10（2）： No.78. 10.3390/info10020078
11	KENGUE J F D， VALTCHEV P， DJAMEGNI C T. A parallel algorithm for lattice construction ［C］// Proceedings of the 2005 International Conference on Formal Concept Analysis， LNCS3403. Berlin： Springer， 2005： 249-264.
12	刘忠慧，邹璐，杨梅，等.启发式概念构造的组推荐方法［J］.计算机科学与探索， 2020， 14（4）： 703-711. 10.3778/j.issn.1673-9418.1905012
	LIU Z H， ZOU L， YANG M， et al. Group recommendation with concept of heuristic construction［J］. Journal of Frontiers of Computer Science and Technology， 2020， 14（4）： 703-711. 10.3778/j.issn.1673-9418.1905012
13	BURUSCO A， FUENTES-GONZÁLEZ R. Construction of the L-fuzzy concept lattice［J］. Fuzzy Sets and Systems， 1998， 97（1）： 109-114. 10.1016/s0165-0114(96)00318-1
14	HOLLAND J H. Adaptation in Natural and Artificial Systems： an Introductory Analysis with Applications to Biology， Control， and Artificial Intelligence［M］. Cambridge： MIT Press， 1992： 211. 10.7551/mitpress/1090.001.0001
15	CHEN J Y， ZHANG C S. Efficient clustering method based on rough set and genetic algorithm［J］. Procedia Engineering， 2011， 15： 1498-1503. 10.1016/j.proeng.2011.08.278
16	杜鹃，丁爱萍，汪传建，等.形式概念演化生成算法［J］.计算机应用， 2010， 30（10）： 2598-2601. 10.3724/sp.j.1087.2010.02598
	DU J， DING A P， WANG C J， et al. Genetic algorithm to generate formal concept［J］. Journal of Computer Applications， 2010， 30（10）： 2598-2601. 10.3724/sp.j.1087.2010.02598
17	BOBADILLA J， ORTEGA F， HERNANDO A， et al. Recommender systems survey［J］. Knowledge-Based Systems， 2013， 46： 109-132. 10.1016/j.knosys.2013.03.012
18	朱扬勇，孙婧.推荐系统研究进展［J］.计算机科学与探索， 2015， 9（5）： 513-525. 10.3778/j.issn.1673-9418.1412023
	ZHU Y Y， SUN J. Recommender system： up to now［J］. Journal of Frontiers of Computer Science and Technology， 2015， 9（5）： 513-525. 10.3778/j.issn.1673-9418.1412023
19	BERKOVSKY S， FREYNE J. Group-based recipe recommendations： analysis of data aggregation strategies ［C］// Proceedings of the 4th ACM Conference on Recommender Systems. New York： ACM， 2010： 111-118. 10.1145/1864708.1864732
20	张玉洁，杜雨露，孟祥武.组推荐系统及其应用研究［J］.计算机学报， 2016， 39（4）： 745-764. 10.11897/SP.J.1016.2016.00745
	ZHANG Y J， DU Y L， MENG X W. Research on group recommender systems and their applications［J］. Chinese Journal of Computers， 2016， 39（4）： 745-764. 10.11897/SP.J.1016.2016.00745
21	QUIJIANO-SÁNCHEZ L， RECIO-GARCÍA J A， DÍAZ-AGUDO B， et al. Social factor in group recommender systems［J］. ACM Transactions on Intelligent Systems and Technology， 2013， 4（1）： No.8. 10.1145/2414425.2414433
22	王刚，蒋军，王含茹.社会化推荐研究综述［J］.计算机科学， 2018， 45（11A）： 37-42， 62. 10.11896/j.issn.1002-137X.2018.11A.006
	WANG G， JIANG J， WANG H R. Review of social recommendation［J］. Computer Science， 2018， 45（11A）： 37-42， 62. 10.11896/j.issn.1002-137X.2018.11A.006
23	MUANGPRATHUB J， BOONJING V， CHAMNONGTHAI K. Learning recommendation with formal concept analysis for intelligent tutoring system［J］. Heliyon， 2020， 6（10）： No.e05227. 10.1016/j.heliyon.2020.e05227
24	DU BOUCHER-RYAN P， BRIDGE D. Collaborative recommending using formal concept analysis［J］. Knowledge-Based Systems， 2006， 19（5）： 309-315. 10.1016/j.knosys.2005.11.017
25	LIU Q， CHEN E H， XIONG H. A cocktail approach for travel package recommendation［J］. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（2）： 278-293. 10.1109/tkde.2012.233
26	ZAIER Z， GODIN R， FAUCHER L. Recommendation quality evolution based on neighborhood size ［C］// Proceedings of the 3rd International Conference on Automated Production of Cross Media Content for Multi-Channel Distribution. Piscataway： IEEE， 2007： 33-36. 10.1109/axmedis.2007.12
27	LIU J T， WU C H， XIONG Y， et al. List-wise probabilistic matrix factorization for recommendation［J］. Information Sciences， 2014， 278： 434-447. 10.1016/j.ins.2014.03.063
28	MNIH A， SALAKHUTDINOV R R. Probabilistic matrix factorization［C］// Proceedings of the 20th International Conference on Neural Information Processing System. New York： ACM， 2008： 1257-1264.

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[4]	刘欢, 李晓戈, 胡立坤, 胡飞雄, 王鹏华. 基于知识图谱驱动的图神经网络推荐模型[J]. 计算机应用, 2021, 41(7): 1865-1870.
[5]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[6]	林怿星, 唐华. 基于异构信息网络的混合推荐模型[J]. 计算机应用, 2021, 41(5): 1348-1355.
[7]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[8]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[9]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[10]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[11]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[12]	陈宪聪, 潘微科, 明仲. 面向异构单类协同过滤的阶段式变分自编码器[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3499-3507.
[13]	骆锦潍, 刘杜钢, 潘微科, 明仲. 基于改进的倾向得分估计的无偏推荐模型[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3508-3514.
[14]	李改, 李磊, 张佳强. 融合显/隐式反馈的社会化协同排序推荐算法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3515-3520.
[15]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.

近似概念的遗传生成算法及其推荐应用

Genetic algorithm for approximate concept generation and its recommendation application

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 28

相关文章 15

编辑推荐

Metrics