Construction Algorithm of Concept Set Based on Simulated Annealing Algorithm
LIU Zhonghui1, CHEN Jianyu1, SONG Guojie2,3, MIN Fan1,3
1. School of Computer Science, Southwest Petroleum University, Chengdu 610500 2. School of Sciences, Southwest Petroleum University, Chengdu 610500 3. Institute for Artificial Intelligence, Southwest Petroleum University, Chengdu 610500
Abstract In formal concept analysis, the construction of concept lattice produces high time and space complexity, but only partial lattices or concept sets are applied in recommendation. To solve this problem, a construction algorithm of concept set based on simulated annealing algorithm is proposed. The candidate concepts generation technique is presented based on the simulated annealing algorithm. The objective function takes the extension similarity of a concept into account. The Metropolis criterion is employed to update the solution. The concept filtering technique is designed based on all candidate concepts. Strong concepts of each user are selected with the extension similarity as the evaluation indicator, and the filtered strong concepts constitute a concept set. The recommendation technique is proposed based on the strong concept set. It provides personalized recommendations to the target user using the preferences of neighbor users in the same extension. Experimental results on 5 public datasets demonstrate that the recommendation performance and the efficiency of proposed algorithm are superior.
Fund:National Natural Science Foundation of China(No.41674141)
Corresponding Authors:
MIN Fan, Ph.D., professor. His research interests include gra-nular computing, recommender system and active learning.
About author:: LIU Zhonghui, master, associate profe-ssor. Her research interests include machine learning, formal concept analysis and rough set.CHEN Jianyu, master student. His research interests include formal concept analysis and recommender system.SONG Guojie, Ph.D., professor. His research interests include deep learning and high performance computing.
[1] WILLE R. Restructuring Lattice Theory: An Approach Based on Hie-rarchies of Concepts // RIVAL I, ed. Ordered Sets. Berlin, Germany: Springer, 1981: 445-470. [2] 李金海,魏 玲,张 卓,等.概念格理论与方法及其研究展望.模式识别与人工智能, 2020, 33(7): 619-642. (LI J H, WEI L, ZHANG Z, et al. Concept Lattice Theory and Method and Their Research Prospect. Pattern Recognition and Artificial Intelligence, 2020, 33(7): 619-642.) [3] BORDAT J P. Calcul Pratique du Treillis de Galois d′une Correspondance. Mathématiques et Sciences Humaines, 1986, 96: 31-47. [4] CHEIN M. Algorithme de Recherche des Sou-matrices Premières d′une Matrice. Bulletin of the Malaysian Mathematical Sciences Society, 1969, 13(1): 21-25. [5] NOURINE L, RAYNAUD O. A Fast Algorithm for Building La-ttices. Information Processing Letters, 1999, 71(5/6): 199-204. [6] GODIN R, MISSAOUI R, ALAOUI H. Incremental Concept Formation Algorithms Based on Galois (Concept) Lattices. Computational Intelligence, 1995, 11(2): 246-276. [7] LI J H, MEI C L, WANG J H, et al. Rule Preserved Object Compression in Formal Decision Contexts Using Concept Lattices. Knowledge-Based Systems, 2014, 71: 435-445. [8] TRNECKA M, TRNECKOVA M. Data Reduction for Boolean Matrix Factorization Algorithms Based on Formal Concept Analysis. Knowledge-Based Systems, 2018, 158: 75-80. [9] 张文修,魏 玲,祁建军.概念格的属性约简理论与方法.中国科学(信息科学), 2005, 35(6): 628-639. (ZHANG W X, WEI L, QI J J. Attribute Reduction Theory and Approach to Concept Lattice. Science in China(Information Sciences), 2005, 35(6): 628-639.) [10] BENÍTEZ-CABALLERO M J, MEDINA J, RAMIREZ-POUSSA E, et al. Rough-Set-Driven Approach for Attribute Reduction in Fuzzy Formal Concept Analysis. Fuzzy Sets and Systems, 2020, 391: 117-138. [11] 魏 玲,曹 丽,祁建军,等.形式概念分析中的概念约简与概念特征.中国科学(信息科学), 2020, 50(12): 1817-1833. (WEI L, CAO L, QI J J, et al. Concept Reduction and Concept Characteristics in Formal Concept Analysis. Scientia Sinica Informationis, 2020, 50(12): 1817-1833.) [12] 谢小贤,李进金,陈东晓,等.基于布尔矩阵的保持二元关系不变的概念约简.山东大学学报(理学版), 2020, 55(5): 32-45. (XIE X X, LI J J, CHEN D X, et al. Concept Reduction of Preserving Binary Relations Based on Boolean Matrix. Journal of Shandong University(Natural Science), 2020, 55(5): 32-45.) [13] CASTELLANOS A, CIGARRAN J, GARCÍA-SERRANO A. Formal Concept Analysis for Topic Detection: A Clustering Quality Experimental Analysis. Information Systems, 2017, 66: 24-42. [14] 李 贞,张 卓,王黎明.基于三元概念分析的文本分类算法研究.计算机科学, 2017, 44(8): 207-215. (LI Z, ZHANG Z, WANG L M. Research on Text Classification Algorithm Based on Triadic Concept Analysis. Computer Science, 2017, 44(8): 207-215.) [15] ZHANG Z P, ZHAO J, YAN X P. A Web Page Clustering Method Based on Formal Concept Analysis. Information, 2018, 9(9): 228-241. [16] ZHI H L, LI J H. Granule Description Based Knowledge Discovery from Incomplete Formal Contexts via Necessary Attribute Analysis. Information Sciences, 2019, 485: 347-361. [17] 孙小兵,李 云,李必信,等.形式概念分析在软件维护中的应用综述.电子学报, 2015, 43(7): 1399-1406. (SUN X B, LI Y, LI B X, et al. A Survey of Using Formal Concept Analysis for Software Maintenance. Acta Electronica Sinica, 2015, 43(7): 1399-1406.) [18] GREENE G J, ESTERHUIZEN M, FISCHER B. Visualizing and Exploring Software Version Control Repositories Using Interactive Tag Clouds over Formal Concept Lattices. Information and Software Technology, 2017, 87: 223-241. [19] JINDAL R, SEEJA K R, JAIN S. Construction of Domain Ontology Utilizing Formal Concept Analysis and Social Media Analy-tics. International Journal of Cognitive Computing in Engineering, 2020, 1: 62-69. [20] CHEN R C, BAU C T, YEH C J. Merging Domain Ontologies Based on the WordNet System and Fuzzy Formal Concept Analysis Techniques. Applied Soft Computing, 2011, 11(2): 1908-1923. [21] 李 征,李 斌.一种基于关联规则与K-means的领域本体构建方法.河南师范大学学报(自然科学版), 2020, 48(1): 24-32. (LI Z, LI B. An Approach for Domain Ontology Construction Based on Association Rules and K-means. Journal of Henan Normal University(Natural Science Edition), 2020, 48(1): 24-32.) [22] RESNICK P, VARIAN H R. Recommender Systems. Communications of the ACM, 1997, 40(3): 56-58. [23] 王晓东,时俊雅,李 淳,等.学习资源精准推荐模型及应用研究.河南师范大学学报(自然科学版), 2019, 47(1): 26-32. (WANG X D, SHI J Y, LI C, et al. Accurate Recommendation Model and Application of Learning Resources. Journal of Henan Normal University(Natural Science Edition), 2019, 47(1): 26-32.) [24] ZOU C F, ZHANG D Q, WAN J F, et al. Using Concept Lattice for Personalized Recommendation System Design. IEEE Systems Journal, 2017, 11(1): 305-314. [25] 陈昊文,王黎明,张 卓.基于概念邻域的Top-N推荐算法.小型微型计算机系统, 2017, 38(11): 2553-2559. (CHEN H W, WANG L M, ZHANG Z. Top-N Recommendation Algorithm Based on Conceptual Neighborhood. Journal of Chinese Computer Systems, 2017, 38(11): 2553-2559.) [26] 谢志鹏,刘宗田.概念格的快速渐进式构造算法.计算机学报, 2002, 25(5): 490-496. (XIE Z P, LIU Z T. A Fast Incremental Algorithm for Building Concept Lattice. Chinese Journal of Computers, 2002, 25(5): 490-496.) [27] 李 云,刘宗田,陈 崚,等.多概念格的横向合并算法.电子学报, 2004, 32(11): 1849-1854. (LI Y, LIU Z T, CHEN L, et al. Horizontal Union Algorithm of Multiple Concept Lattices. Acta Electronica Sinica, 2004, 32(11): 1849-1854.) [28] 智慧来,智东杰,刘宗田.概念格合并原理与算法.电子学报, 2010, 38(2): 455-459. (ZHI H L, ZHI D J, LIU Z T. Theory and Algorithm of Concept Lattice Union. Acta Electronica Sinica, 2010, 38(2): 455-459.) [29] NJIWOUA P, NGUIFO E M. A Parallel Algorithm to Build Concept Lattice // Proc of the 4th Groningen International Information Technology Conference for Students. Berlin, Germany: Springer, 1997: 103-107. [30] FU H G, NGUIFO E M. A Parallel Algorithm to Generate Formal Concepts for Large Data // Proc of the 2nd International Confe-rence on Formal Concept Analysis. Berlin, Germany: Springer, 2004: 394-401. [31] 刘忠慧,邹 璐,杨 梅,等.启发式概念构造的组推荐方法.计算机科学与探索, 2020, 14(4): 703-711. (LIU Z H, ZOU L, YANG M, et al. Group Recommendation with Concept of Heuristic Construction. Journal of Frontiers of Computer Science and Technology, 2020, 14(4): 703-711.) [32] METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al. Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 1953, 21(6): 1087-1092. [33] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by Simulated Annealing. Science, 1983, 220(4598): 671-680. [34] BURUSCO A, FUENTES-GONZALEZ R. Construction of the L-Fuzzy Concept Lattice. Fuzzy Sets and Systems, 1998, 97(1): 109-114.
2021, Vol. 34 
