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 resea...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.展开更多
There is an intimate correlation between rough set theory and formal concept analysis theory, so rough set approximations can be realized by means of formal concept analysis. For any given multiple valued information ...There is an intimate correlation between rough set theory and formal concept analysis theory, so rough set approximations can be realized by means of formal concept analysis. For any given multiple valued information system, the realization of rough set approximation operation has two major steps, firstly convert the information system from multiple valued one to single valued formal context, secondly realize rough set approximation operations aided by concept lattice, which is equivalent to a query operation under some necessary conditions.展开更多
The theory of concept lattices is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. Based on t...The theory of concept lattices is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. Based on the reduction theory of classical formal context, this paper proposes the definition of decision formal context and its reduction theory, which extends the reduction theory of concept lattices. In this paper, strong consistence and weak consistence of decision formal context are defined respectively. For strongly consistent decision formal context, the judgment theorems of consistent sets are examined, and approaches to reduction are given. For weakly consistent decision formal context, implication mapping is defined, and its reduction is studied. Finally, the relation between reducts of weakly consistent decision formal context and reducts of implication mapping is discussed.展开更多
基金the National Natural Science Foundation of China(No.61273328)the National Key Foundation for Exploring Scientific Instrument of China(No.51227803)
文摘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.
文摘There is an intimate correlation between rough set theory and formal concept analysis theory, so rough set approximations can be realized by means of formal concept analysis. For any given multiple valued information system, the realization of rough set approximation operation has two major steps, firstly convert the information system from multiple valued one to single valued formal context, secondly realize rough set approximation operations aided by concept lattice, which is equivalent to a query operation under some necessary conditions.
基金the National 973 Program of China (Grant No.2002CB312200)the National Natural Science Foundation of China (Grant Nos.60703117, 60433010 and 60673096)the Doctor Research Fund of Northwest University in China
文摘The theory of concept lattices is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. Based on the reduction theory of classical formal context, this paper proposes the definition of decision formal context and its reduction theory, which extends the reduction theory of concept lattices. In this paper, strong consistence and weak consistence of decision formal context are defined respectively. For strongly consistent decision formal context, the judgment theorems of consistent sets are examined, and approaches to reduction are given. For weakly consistent decision formal context, implication mapping is defined, and its reduction is studied. Finally, the relation between reducts of weakly consistent decision formal context and reducts of implication mapping is discussed.
