Journal of Shanghai Jiao Tong University (Science) ›› 2019, Vol. 24 ›› Issue (2): 243-253.doi: 10.1007/s12204-019-2058-6

• • 上一篇    下一篇

Research on Two Main Construction Methods of Concept Lattices

DONG Ying* (董颖), WU Yue (吴悦), LIU Zongtian (刘宗田)   

  1. (School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China)
  • 出版日期:2019-04-30 发布日期:2019-04-01
  • 通讯作者: DONG Ying* (董颖) E-mail:grumpy@shu.edu.cn

Research on Two Main Construction Methods of Concept Lattices

DONG Ying* (董颖), WU Yue (吴悦), LIU Zongtian (刘宗田)   

  1. (School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China)
  • Online:2019-04-30 Published:2019-04-01
  • Contact: DONG Ying* (董颖) E-mail:grumpy@shu.edu.cn

摘要: Because of the completeness of concept lattices, the time complexity of constructing concept lattices has become the main factor affecting the application of formal concept analysis (FCA). The key problems in the research of concept lattices are how to improve the generation efficiency and how to reduce the space and time complexity of constructing concept lattices. So far, reviews on lattice construction algorithms have not been comprehensive. In view of this situation, we give a detailed review on two categories of construction algorithms: batch methods and incremental methods. The first category is a formal context that cannot be updated once the concept lattice has been constructed; the second category is a formal context that can be updated after a new object being added to the formal context. We briefly introduce classical and improved construction methods, illustrate the deficiencies of some algorithms and point out the improvements of the follow-up algorithms. Furthermore, we compare and discuss several key algorithms, and also pay attention to the application of concept lattices. Finally, two further research directions of concept lattices are proposed, including parallel construction methods of concept lattices and research of heterogeneous data concept lattices.

关键词: formal concept analysis (FCA), concept lattice, batch processing, incremental processing

Abstract: Because of the completeness of concept lattices, the time complexity of constructing concept lattices has become the main factor affecting the application of formal concept analysis (FCA). The key problems in the research of concept lattices are how to improve the generation efficiency and how to reduce the space and time complexity of constructing concept lattices. So far, reviews on lattice construction algorithms have not been comprehensive. In view of this situation, we give a detailed review on two categories of construction algorithms: batch methods and incremental methods. The first category is a formal context that cannot be updated once the concept lattice has been constructed; the second category is a formal context that can be updated after a new object being added to the formal context. We briefly introduce classical and improved construction methods, illustrate the deficiencies of some algorithms and point out the improvements of the follow-up algorithms. Furthermore, we compare and discuss several key algorithms, and also pay attention to the application of concept lattices. Finally, two further research directions of concept lattices are proposed, including parallel construction methods of concept lattices and research of heterogeneous data concept lattices.

Key words: formal concept analysis (FCA), concept lattice, batch processing, incremental processing

中图分类号: