Realization of Rough Set Approximation Toplogical Operations Based on Formal Concept Analysis ()
1. Introduction
Rough set theory (RS), first described by a Polish computer scientist Zdzisław I. Pawlak [1] , is a formal approximation of a crisp set (i.e., conventional set) in terms of a pair of sets which give the lower and the upper approximation of the original set. In the standard version of rough set theory, the lowerand upper-approximation sets are crisp sets, but in other variations, the approximating sets may be fuzzy sets. Formal concept analysis (FCA) is a principled way of automatically deriving ontology from a collection of objects and their properties [2] . The term was introduced by Rudolf Wille in 1984, and built on applied lattice and order theory that was developed by Birkhoff and others in the 1930s.
Research about the relationship between formal concept analysis and rough set theory has gained some development. Kent [3] and Yao [4] bring upper approximation and lower approximation in rough set theory into formal concept analysis, and discuss many approximation operators based on formal concept analysis. Qu Kaishe [5] focuses on the theory research about the correlation between formal concept analysis and rough set. He first reveals limitations of data analysis and processing in the rough set theory, and then provides a way for the synthesis of formal concept analysis and rough set theory by using nominal scale.
In these studies, the link between rough set theory and concept lattice is pointed out, but in practice how to realize the operation of rough set by using concept lattice is still left as a problem. Therefore, in this article, we focus on the way to realize rough set approximation topological operations based concept lattice, which includes upper approximation and lower approximation.
2. About Rough Set Theory and FCA
2.1. Basic Concepts in Rough Set Theory
Indiscernibility Relation is a central concept in rough set theory, and is considered as a relation between two objects or more, where all the values are identical in relation to a subset of considered attributes. Indiscernibility relation is an equivalence relation, where all identical objects of set are considered as elementary [6] .
Approximations is also other an important concept in Rough Sets Theory, being associated with the meaning of the approximation topological operations [7] . The lower and the upper approximations of a set are interior and closure operations in a topology generated by the indiscernibility relation. Below is resented and described the types of approximations that are used in Rough Sets Theory.
a) Lower Approximation 
Lower Approximation is a description of the domain objects that are known with certainty to belong to the subset of interest. The Lower Approximation Set of a set
, with regard to 
is the set of all of objects, which certainly can be classified with 
regarding
, that is, set
.
Formally, 
b) Upper Approximation 
Upper Approximation is a description of the objects that possibly belong to the subset of interest. The Upper Approximation Set of a set 
regarding 
is the set of all of objects which can be possibly classified with 
regarding
, that is, set
.
Formally, 
, 
denote an empty set.
c) Boundary Region (BR)
Boundary Region is description of the objects that of a set 
regarding 
is the set of all the objects, which cannot be classified neither as 
nor 
regarding
. If the boundary region is a set
, then the set is considered “Crisp”, that is, exact in relation to
; otherwise, if the boundary region is a set 
the set 
“Rough” is considered. In that the boundary region is BR.
Formally,
.
2.2. Basic Concepts in Formal Concept Analysis
Formal concept analysis, which is proposed by R. Wille, is founded on a basis of order theory and lattice theory, and is a mathematical structure which depicts relationship between objects and attributes according to basic information provided by data base. Formal concept analysis has been successfully used in many fields, and to some extend it has been treated as a means of external cognition [8] .
Definition 1: Given a formal context
, 
, 
, if 
and 
satisfy
, 
, and
, 
, we call the pair 
is a concept of formal context
. 
is called extent of concept
, 
is called intent of concept
. 
or 
is the set which contains of the concepts of 
[2] .
Definition 2: Given a formal context
, 
, if 
or
, then call 
is a son concept of
, and denote as
. Apparently, 
forms a lattice, which is called concept lattice [2] .
Given two concepts
, 
of a formal context
, we have: If
, then
, for
; If
, then
, for
.
3. Realization of Approximation Operation Based on FCA
Realization of rough set approximation operation can be divided into two steps: first, convert multiple valued information system to multiple valued formal context, and then covert multiple value formal context to single value formal context; second, realize rough set approximation operation by using the technique of formal concept analysis based on concept lattice.
3.1. Convert Multiple Valued Is from to Single Valued Formal Context
In an information system
, 
is the set of attributes, for every attribute
, if the value of 
belongs to 
in which 1 represents an object has this attribute and 0 represents an object doesn’t has this attribute, then this information system corresponds to an single value formal context. Otherwise, if the value of 
belongs to a set
, and the size of 
is greater than 2, then we have to convert this attribute to several attributes according to the size of
. For example, if there is a attribute “shape”, and the value of “shape” belongs to {triangle, round, rectangle}, then attribute “shape” can convert to three attributes, namely “triangle”, “round” and “rectangle”, and the value of every attributes belongs to
.
Definition 3: Let 
be an information system, if the value of an attribute 
belongs to a set
, and the size of 
is
, then convert 
to a series of attributes
, and call 
are derived attributes of
. After carrying out this converting process, attributes set 
convert to a new attributes set
, then 
is called the derived attributes of
.
Definition 4: Let 
be an information system, assume
, 
is the derived attributes of
, 
is the relation between 
and
, the we call 
is the single value formal context derived from information system
.
3.2. Realization of Approximation Based on Concept Lattice
For the sake of narrative convenience, we agree several symbols in this paper. 
denotes Concept lattice of formal context 
and 
denotes all concepts of
. Lower case letters represents concepts, for example, we use letter 
denote a concept, and let 
and 
represent extension and intension of concept 
respectively.
Definition 5: Let 
be an information system, 
is the single value formal context derived from information system
, assume
，
, we call formal context 
is sub-context of 
regarding
.
Theorem 1: Let 
be an information system, 
is the single value formal context derived from information system
, 
, 
, 
, attribute 
is derived from attribute
, 
is sub-context of 
regarding
, 
is the concept lattice of
, Upper Approximation:
Lower Approximation:
.
Proof: According to the definition of concept in FCA, extent set 
has attributes
, and size of
equals to the size of
, then 
forms the equivalence classes of the B-indiscernibility relation, which means 
equals to
. According to definition of upper and lower approximation, this theorem obviously holds.
Theorem 2: Let 
be an information system, 
is the single value formal context derived from information system
, assume
, 
, 
contains all the concepts in concept lattice
, Upper Approximation is:
Lower Approximation is:
.
Proof: According to the definition of concept in FCA, extent set 
has attributes
, and
, then 
forms the equivalence classes of the B-indiscernibility relation, which means 
equals to
. According to definition upper and lower approximation, this theorem obviously holds.
3.3. An Example
In an information system
, three are equivalent classes, namely
,
and
.
Let
,
. Now let’s compute 
and 
by using Theorem 1 and Theorem 2.
In the above information system, 
and 
divide 
into three equivalent classes, thus the size of the value range of 
and 
is 3, and then we must convert these two attributes form multiple value to single value. The derived single value context is shown in Table1 By using Godin algorithm [9] , we can build the concept lattice of a given single valued formal context.
1) Compute 
and 
by using Theorem 1 Under the attributes constraint
, we get sub-context 
of formal context
, which includes the columns labeled by 
and
. Concept lattice 
is shown in Figure 1.
Table 1. Single valued formal context K.
In concept lattice
, the concepts whose extent satisfy the constraint 
are
, and
. According Theorem 1, we have
, 
, and
.
2) Compute 
and 
by using Theorem 2 First 
convert to single vale set 
and 
convert to single vale set
. Besides
, for the father concept 
of concept
, the intent satisfy 
and
, according to Theorem 2, objects 3 and 4 belongs to
.
Finally, we get
, 
and
.
By using different theory, we get the same result, and to some extent this proves the correctness of our method.
4. Conclusions
There is an intimate link between rough set theory and concept lattice, so rough set approximation operation can be realized being aided by FCA. From this perspective, realizing rough set operation aided by FCA can be seen as a kind of generalization of the concept lattice queries that meet certain conditions.
Realization of rough set approximation operation on concept lattice can be divided into two steps: first, convert multiple value information system to multiple value formal context, and then covert multiple value formal context to single value formal context; second, realize rough set approximation operation aided by formal concept analysis on concept lattice.
The method is expected to be of further use for calculating approximation of rough set that with real values, interval numbers and other self-defined types.
Acknowledgements
The work presented in this paper is supported by National Science Foundation of China (60975033) and Doctorial Foundation of Henan Polytechnic University (B2011-102).