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 -