Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (2): 412-418.DOI: 10.11772/j.issn.1001-9081.2021041155
Special Issue: 人工智能
• Artificial intelligence • Previous Articles Next Articles
Zhonghui LIU1, Ziyou WANG1, Fan MIN1,2()
Received:
2021-07-05
Revised:
2021-07-27
Accepted:
2021-08-05
Online:
2022-02-11
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.通讯作者:
闵帆
作者简介:
刘忠慧(1980—),女,四川南充人,副教授,硕士,CCF会员,主要研究方向:机器学习、形式概念分析、粗糙集;CLC Number:
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.
刘忠慧, 王梓宥, 闵帆. 近似概念的遗传生成算法及其推荐应用[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 412-418.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2021041155
0 | 1 | 0 | 1 | 1 | 1 | 0 | |
0 | 1 | 1 | 0 | 1 | 0 | 0 | |
1 | 0 | 1 | 1 | 0 | 0 | 1 | |
1 | 0 | 0 | 1 | 0 | 1 | 0 | |
1 | 1 | 1 | 1 | 0 | 0 | 1 | |
1 | 1 | 0 | 0 | 1 | 0 | 0 | |
0 | 1 | 0 | 1 | 0 | 1 | 1 | |
1 | 0 | 1 | 0 | 1 | 0 | 1 | |
0 | 0 | 1 | 0 | 0 | 0 | 1 | |
1 | 0 | 1 | 0 | 0 | 1 | 0 |
Tab. 1 Example of formal context
0 | 1 | 0 | 1 | 1 | 1 | 0 | |
0 | 1 | 1 | 0 | 1 | 0 | 0 | |
1 | 0 | 1 | 1 | 0 | 0 | 1 | |
1 | 0 | 0 | 1 | 0 | 1 | 0 | |
1 | 1 | 1 | 1 | 0 | 0 | 1 | |
1 | 1 | 0 | 0 | 1 | 0 | 0 | |
0 | 1 | 0 | 1 | 0 | 1 | 1 | |
1 | 0 | 1 | 0 | 1 | 0 | 1 | |
0 | 0 | 1 | 0 | 0 | 0 | 1 | |
1 | 0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 5 | 1 | 1 | 0 | |
0 | 3 | 2 | 0 | 1 | 0 | 0 | |
2 | 0 | 5 | 2 | 0 | 0 | 1 | |
4 | 0 | 0 | 1 | 0 | 3 | 0 | |
1 | 2 | 1 | 1 | 0 | 0 | 1 | |
3 | 4 | 0 | 0 | 1 | 0 | 0 | |
0 | 2 | 0 | 1 | 0 | 5 | 1 | |
2 | 0 | 2 | 0 | 1 | 0 | 5 | |
0 | 0 | 3 | 0 | 0 | 0 | 3 | |
5 | 0 | 2 | 0 | 0 | 1 | 0 |
Tab. 2 Example of scoring formal context
0 | 1 | 0 | 5 | 1 | 1 | 0 | |
0 | 3 | 2 | 0 | 1 | 0 | 0 | |
2 | 0 | 5 | 2 | 0 | 0 | 1 | |
4 | 0 | 0 | 1 | 0 | 3 | 0 | |
1 | 2 | 1 | 1 | 0 | 0 | 1 | |
3 | 4 | 0 | 0 | 1 | 0 | 0 | |
0 | 2 | 0 | 1 | 0 | 5 | 1 | |
2 | 0 | 2 | 0 | 1 | 0 | 5 | |
0 | 0 | 3 | 0 | 0 | 0 | 3 | |
5 | 0 | 2 | 0 | 0 | 1 | 0 |
数据集 | 大小 | 稀疏度 |
---|---|---|
ML-100K | 943 | 0.937 0 |
ML-1M | 6 040 | 0.958 1 |
EachMovie | 72 916 | 0.992 2 |
Jester | 24 983 | 0.755 1 |
Tab. 3 Experimental datasets
数据集 | 大小 | 稀疏度 |
---|---|---|
ML-100K | 943 | 0.937 0 |
ML-1M | 6 040 | 0.958 1 |
EachMovie | 72 916 | 0.992 2 |
Jester | 24 983 | 0.755 1 |
数据集 | 大小 | 稀疏度 | 算法 | 精确度 | 召回率 | F1值 |
---|---|---|---|---|---|---|
ML-100K-sd1 | 200 | 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 | 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 | 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 | 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 | 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 | 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 | 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 |
Tab. 4 Comparison of ACGA, GRHC algorithm and KNN algorithm on sampling datasets
数据集 | 大小 | 稀疏度 | 算法 | 精确度 | 召回率 | F1值 |
---|---|---|---|---|---|---|
ML-100K-sd1 | 200 | 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 | 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 | 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 | 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 | 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 | 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 | 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 |
数据集 | 算法 | 精确度 | 召回率 | |
---|---|---|---|---|
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 |
Tab. 5 Comparison of ACGA and other algorithms on complete datasets
数据集 | 算法 | 精确度 | 召回率 | |
---|---|---|---|---|
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 |
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] | Tingjie TANG, Jiajin HUANG, Jin QIN. Session-based recommendation with graph auxiliary learning [J]. Journal of Computer Applications, 2024, 44(9): 2711-2718. |
[2] | Lin GAO, Yu ZHOU, Tak Wu KWONG. Evolutionary bi-level adaptive local feature selection [J]. Journal of Computer Applications, 2024, 44(5): 1408-1414. |
[3] | Xuanfeng LI, Shengcai LIU, Ke TANG. Novel genetic algorithm for solving chance-constrained multiple-choice Knapsack problems [J]. Journal of Computer Applications, 2024, 44(5): 1378-1385. |
[4] | Li ZENG, Jingru YANG, Gang HUANG, Xiang JING, Chaoran LUO. Survey on hypergraph application methods: issues, advances, and challenges [J]. Journal of Computer Applications, 2024, 44(11): 3315-3326. |
[5] | Yuan LIU, Yongquan DONG, Rui JIA, Haolin YANG. Hierarchical and phased attention network model for personalized course recommendation [J]. Journal of Computer Applications, 2023, 43(8): 2358-2363. |
[6] | Hao SUN, Jian CAO, Haisheng LI, Dianhui MAO. Session-based recommendation model based on enhanced capsule network [J]. Journal of Computer Applications, 2023, 43(4): 1043-1049. |
[7] | Qing YE, Xin SHI, Mengwei SUN, Jian ZHU. Greedy synchronization topology algorithm based on formal concept analysis for traffic surveillance based sensor network [J]. Journal of Computer Applications, 2023, 43(3): 869-875. |
[8] | Xuanyu SUN, Yancui SHI. Session-based recommendation model by graph neural network fused with item influence [J]. Journal of Computer Applications, 2023, 43(12): 3689-3696. |
[9] | Xuejian ZHAO, Hao LI, Haotian TANG. Recommendation rating prediction algorithm based on user interest concept lattice reduction [J]. Journal of Computer Applications, 2023, 43(11): 3340-3345. |
[10] | Li’e WANG, Xiaocong LI, Hongyi LIU. News recommendation method with knowledge graph and differential privacy [J]. Journal of Computer Applications, 2022, 42(5): 1339-1346. |
[11] | Xiaohan LI, Huading JIA, Xue CHENG, Taiyong LI. Stock market volatility prediction method based on improved genetic algorithm and graph neural network [J]. Journal of Computer Applications, 2022, 42(5): 1624-1633. |
[12] | Yanfei LIU, Zheng PENG, Yihui WANG, Zhong WANG. PID parameter tuning of brushed direct-current motor based on improved genetic algorithm [J]. Journal of Computer Applications, 2022, 42(5): 1634-1641. |
[13] | Junhua GU, Rui WANG, Ningning LI, Suqi ZHANG. Knowledge graph attention network fusing collaborative filtering information [J]. Journal of Computer Applications, 2022, 42(4): 1087-1092. |
[14] | Lu CHEN, Xiaoxia ZHANG, Hong YU. Partially explainable non-negative matrix tri-factorization algorithm based on prior knowledge [J]. Journal of Computer Applications, 2022, 42(3): 671-675. |
[15] | ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||