The General Concept Lattice (GCL) proposes a novel general construction of concept hierarchy from formal context, where the conventional Formal Concept Lattice based on Formal Concept Analysis (FCA) only serves as a substructure.
The formal context is a data table of heterogeneous relations illustrating how objects carrying attributes. By analogy with truth-value table, every formal context can develop its fully extended version including all the columns corresponding to attributes constructed, by means of Boolean operations, out of the given attribute set. The GCL is based on the extended formal context which comprehends the full information content of formal context in the sense that it incorporates whatever the formal context should consistently imply. Noteworthily, different formal contexts may give rise to the same extended formal context.
Background The GCL claims to take into account the extended formal context for preservation of information content. Consider describing a three-ball system (3BS) with three distinct colours, e.g., red, green and blue. According to Table 1, one may refer to different attribute sets, say, , or to reach different formal contexts. The concept hierarchy for the 3BS is supposed to be unique regardless of how the 3BS being described. However, the FCA exhibits different formal concept lattices subject to the chosen formal contexts for the 3BS , see Fig. 1. In contrast, the GCL is an invariant lattice structure with respect to these formal contexts since they can infer each other and ultimately entail the same information content. + Table 1: The extended version for the formal context describing the 3BS. From one can also deduce , thereby deducing the full . Note that ,, .123
In information science, the Formal Concept Analysis (FCA) promises practical applications in various fields based on the following fundamental characteristics.
It orders the formal concepts in a hierarchy i.e. the formal concept lattice (FCL) which can be visualized as a line diagram that may be helpful for understanding the data. It enables the attribute exploration, a knowledge acquisition technique based on implications. It is possible to acquire the canonical (Guigues-Duquenne) basis, the non-redundant collection of informative implications based on which valid implications available from the formal context can be derived by the Armstrong rules.
The FCL does not appear to be the only lattice applicable to the interpretation of data table. Alternative concept lattices subject to different derivation operators based on the notions relevant to the Rough Set Analysis have also been proposed. Specifically, the object-oriented concept lattice, which is referred to as the rough set lattice (RSL) afterwards, is found to be particularly instructive to supplement the standard FCA in further understandings of the formal context.
The FCL exhibits the categorisation for object class according to their common properties while the RSL is according to those properties which other classes do not possess. The RSL provides an alternative scheme for implications available from the formal context which are beyond the scope of FCL, as will be clarified later.
Consequently, there are two crucial points to be contemplated. The FCL and RSL reflect different concept hierarchies interpreting the same formal context in a complementary way. However, similar to the case of FCL, RSL also suffers from different lattice structures varying with respect to the chosen formal contexts, see Fig. 2. The implication relations extracted via the RSL from the formal context signify a different part of logic content from the ones extractable via the FCL. The treatment via the RSL would require further efforts of construction, the Guigues-Duquenne basis for the RSL. Moreover, it is unwarranted that the implications of these two together suffices the full logic content.
The GCL accomplishes a sound theoretical foundation for the concept hierarchies acquired from formal context. Maintaining the generality that preserves the information, the GCL underlies both the FCL and RSL, which correspond to substructures at particular restrictions. Technically, the GCL would be reduced to the FCL and RSL when restricted to conjunctions and disjunctions of elements in the referred attribute set (), respectively. In addition, the GCL unveils extra information complementary to the results via the FCL and RSL. Surprisingly, the implementation of formal context via GCL is much more manageable than those via FCL and RSL.
Related mathematical formulations
Algebras of derivation operators The derivation operators constitute the building blocks of concept lattices and thus deserve distinctive notations. Subject to a formal context concerning the object set and attribute set ,
are considered as different modal operators (Sufficiency, Necessity and Possibility, respectively) that generalise the FCA. For notations, , the operator adopted in the standard FCA, follows and R. Wille; as well as follows Y. Y. Yao. By , i.e., the object carries the attribute as its property, which is also referred to as where is the set of all objects carrying the attribute .
With it is straightforward to check that
where the same relations hold if given in terms of .
Two Galois lattices
Galois connections From the above algebras, there exist different types of Galois connections, e.g., (1) , (2) and (3) that corresponds to (2) when one replaces and . Note that (1) and (2) enable different object-oriented constructions for the concept hierarchies FCL and RSL, respectively. Note that (3) corresponds to the attribute-oriented construction where the roles of object and attribute in the RSL are exchanged. The FCL and RSL apply to different 2-tuple concept collections that manifest different well-defined partial orderings.
Two concept hierarchies Given as a concept, the 2-tuple is in general constituted by an extent and an intent , which should be distinguished when applied to FCL and RSL. The concept is furnished by based on (1) while is furnished by based on (2). In essence, there are two Galois lattices based on different orderings of the two collections of concepts as follows. entails and since iff , and iff .
entails and since iff , and iff .
Common extents of FCL and RSL Every attribute listed in the formal context provides an extent for FCL and RSL simultaneously via the object set carrying the attribute. Though the extents for FCL and for RSL do not coincide totally, every for is known to be a common extent of FCL and RSL. This turns up from the main results in FCL () and RSL: every () is an extent for FCL and is an extent for RSL. Note that choosing gives rise to .
Two types of informative implications The consideration of the attribute set-to-set implication () via FCL has an intuitive interpretation: every object possessing all the attributes in possesses all the attributes in , in other words . Alternatively, one may consider based on the RSL in a similar manner: the set of all objects carrying any of the attributes in is contained in the set of all objects carrying any of the attributes in , in other words . It is apparent that and relate different pairs of attribute sets and are incapable of expressing each other.
Extension of formal context For every formal context one may acquire its extended version deduced in the sense of completing a truth-value table. It is instructive to explicitly label the object/attribute dependence for the formal context, say, rather than since one may have to investigate more than one formal contexts. As is illustrated in Table 1, can be employed to deduce the extended version , where is the set of all attributes constructed out of elements in by means of Boolean operations. Note that includes three columns reflecting the use of and the attribute set .
Obtaining the general concept lattice
Observations based on mathematical facts
Intents in terms of single attributes The FCL and RSL will not be altered if their intents are interpreted as single attributes. can be understood as with (the conjunction of all elements in ), plays the role of since .
can be understood as with (the disjunction of all elements in ), plays the role of since . Here, the dot product stands for the conjunction (the dots is often omitted for compactness) and the summation the disjunction, which are notations in the Curry-Howard style. Note that the orderings become and , both are implemented by .
Implications from single attribute to single attribute Concerning the implications extracted from formal context, serves as the general form of implication relations available from the formal context, which holds for any pair of fulfilling . Note that turns out to be trivial if , which entails . Intuitively, every object carrying is an object carrying , which means the implication any object having the property must also have the property . In particular, can be interpreted as with and , can be interpreted as with and , where and collapse into .
Lattice of 3-tuple concepts with double Galois connection When extended to , the algebras of derivation operators remain formally unchanged, apart from the generalisation from to which is signified in terms of the replacements , and . The concepts under consideration become then and , where and , which are constructions allowable by the two Galois connections i.e. and , respectively. Henceforth, and for , and for .
The extents for the two concepts now coincide exactly. All the attributes in are listed in the formal context , each contributes a common extent for FCL and RSL. Furthermore, the collection of these common extents amounts to which exhausts all the possible unions of the minimal object sets discernible by the formal context. Note that each collects objects of the same property, see Table 2. One may then join and into a 3-tuple with common extent: where , and . Note that are introduced in order to differentiate the two intents. Clearly, the number of these 3-tuples equals the cardinality of set of common extent which counts . Moreover, manifests well-defined ordering. For , where and , iff and and .
Emergence of the GCL
While it is generically impossible to determine subject to , the structure of concept hierarchy need not rely on these intents directly. An efficient way to implement the concept hierarchy for is to consider intents in terms of single attributes.
Let henceforth and . Upon introducing , one may check that and , . Therefore, , which is a closed interval bounded from below by and from above by since . Moreover, iff , iff iff . In addition, , namely, the collection of intents exhausts all the generalised attributes , in comparison to . Then, the GCL enters as the lattice structure based on the formal context via : The collection of all the general concepts constitutes the poset ordered as iff and and .
Both (meet) and (join) operations are applicable for finding further lattice points: , where
, where The GCL appears to be a complete lattice since both and can be found in : , .
Consequence of the general concept lattice
Manageable general lattice The construction for FCL was known to count on efficient algorithms, not to mention the construction for RSL which did not receive much attention yet. Intriguingly, though the GCL furnishes the general structure on which both the FCL and RSL can be rediscovered, the GCL can be acquired via simple readout.
Reading out the lattice
The completion of GCL is equivalent to the completion of the intents of GCL in terms of the lower and bounds.
The lower bounds can be employed to determine the upper bounds , and vice versa. For concreteness, both and are extents of the GCL, coexists with . Subsequently, and , where .