TY - JOUR
T1 - Formal concept analysis based on the topology for attributes of a formal context
AU - Pei, Zheng
AU - Ruan, Da
AU - Meng, Dan
AU - Liu, Zhicai
N1 - Funding Information:
This work is partially supported by the National Natural Science Foundation ( 61175055, 61105059 ), Sichuan Key Technology Research and Development Program ( 2012GZ0019, 2011FZ0051 ), the research fund of Sichun Key Laboratory of Intelligent Network Information Processing ( SGXZD1002-10 ) and the open research fund of key laboratory of intelligent network information processing, Xihua University ( SZJJ2012-032 ). The authors also gratefully acknowledge the helpful comments and suggestions of the reviewers, which have improved the presentation.
PY - 2013/7/1
Y1 - 2013/7/1
N2 - Formal concept analysis (FCA) concerns the hierarchical structures induced by a binary relation between a pair of sets, it is widely applied in data analysis, information retrieval, and knowledge discovery. Within the framework of FCA, computing all formal concepts is the main challenge due to its exponential complexity. It has be proved that all formal concepts is a closure system on objects, hence, the closure operator on objects are general used to generate all formal concepts of a formal context. In the lexicographic tree approach, a base on objects is used to generate extensions of all formal concepts and construct the formal concept lattice. Inspired from the approach, we concentrate a base on attributes and generate intensions of all formal concepts in this paper. To this end, we firstly analyze an example, the lexicographic tree approach is used to generate all formal concepts, from the time complexity point of view, we present that it is not trivial to generate the base on attributes by a simple symmetrical way from the methods based on objects. Then, we deduce a set-valued mapping from attributes to the power set of attributes in a formal context and define a binary relation on attributes by the set-valued mapping. Using the binary relation on attributes, we construct an approximation space and a topology for attributes, respectively, and obtain a base for the topology. We prove that intensions of all formal concepts are included in the topology for attributes, this means that the base can be used to generate intensions of all formal concepts of the formal context and construct the formal concept lattice. More general, our results represent relationships and the hierarchical structures among attributes of the formal context, we present some typical applications, in which the topology for attributes and the base for the topology are applied for association rules discovery from a formal context and linguistic concept analysis.
AB - Formal concept analysis (FCA) concerns the hierarchical structures induced by a binary relation between a pair of sets, it is widely applied in data analysis, information retrieval, and knowledge discovery. Within the framework of FCA, computing all formal concepts is the main challenge due to its exponential complexity. It has be proved that all formal concepts is a closure system on objects, hence, the closure operator on objects are general used to generate all formal concepts of a formal context. In the lexicographic tree approach, a base on objects is used to generate extensions of all formal concepts and construct the formal concept lattice. Inspired from the approach, we concentrate a base on attributes and generate intensions of all formal concepts in this paper. To this end, we firstly analyze an example, the lexicographic tree approach is used to generate all formal concepts, from the time complexity point of view, we present that it is not trivial to generate the base on attributes by a simple symmetrical way from the methods based on objects. Then, we deduce a set-valued mapping from attributes to the power set of attributes in a formal context and define a binary relation on attributes by the set-valued mapping. Using the binary relation on attributes, we construct an approximation space and a topology for attributes, respectively, and obtain a base for the topology. We prove that intensions of all formal concepts are included in the topology for attributes, this means that the base can be used to generate intensions of all formal concepts of the formal context and construct the formal concept lattice. More general, our results represent relationships and the hierarchical structures among attributes of the formal context, we present some typical applications, in which the topology for attributes and the base for the topology are applied for association rules discovery from a formal context and linguistic concept analysis.
KW - Approximation space
KW - Formal concept analysis
KW - KDD
KW - Set-valued mapping
KW - The lexicographic tree approach
KW - Topological space
UR - http://www.scopus.com/inward/record.url?scp=84875759345&partnerID=8YFLogxK
U2 - 10.1016/j.ins.2013.02.027
DO - 10.1016/j.ins.2013.02.027
M3 - Article
AN - SCOPUS:84875759345
SN - 0020-0255
VL - 236
SP - 66
EP - 82
JO - Information Sciences
JF - Information Sciences
ER -