Formal Concept Analysis has become a real approach in the trend Information-Knowledge-Wisdom. It turns around the mining of a data set to built a concept lattice which provides an strong structure of the knowledge. Implications play the role of an alternative speci cation of this concept lattice and may be managed by means of inference rules. This syntactic treatment is guided by several properties like directness, minimality, optimality, etc. In this work, we propose a method to calculate the direct-optimal basis equivalent to a given Implicational System. Our method deals with unitary and non-unitary implications. Moreover, it shows a better performance that previous methods in the literature by means of the use of Simpli cation Logic and reduction paradigm, which remains narrow implications in any stage of the process. We have also developed an empirical study to compare our method with previous approaches in the literature.
Formal Concept Analysis (FCA) is a trending upward area which establishes a
proper and ne mixture of formalism, data analysis and knowledge discovering. It
is able to analyze and extract information from a context K, rendering a concept
lattice. Attribute implications [
The study of sets of implications that satis es some criteria is one of the relevant topics in FCA. An implicational system (IS) of K is de ned as a set of implications of K from which any valid implication for K can be deduced by means a syntactic treatment of the implications. This symbolic manipulation introduces the notion of equivalent sets of implications and opens the door to the de nition of several criteria to discriminate good sets of implications according to these criteria. Thus, the challenges are the de nition of an speci c notion of IS, named basis, ful lling some criteria related with minimality and the introduction of e cient methods to transform an arbitrary IS into a basis.
For instance, if the criteria is to obtain an IS with minimum cardinal we can
build the so-called Duquenne-Guigues (or stem) basis [
In this paper, we introduce a method to compute the direct-optimal basis.
This kind of basis was introduced in [
In the following, rst we establish the background necessary for the understanding of the paper (Section 2). In Section 3 SLFD is summarized and a motivation of the simpli cation paradigm to remove redundant attributes is provided. Section 4 is focussed on the methods of Bertet et al. to get a direct-optimal basis. In Section 5 the new method is introduced and a comparison among all the methods is showed. Some conclusions are presented in Section 6. 2
We assume well-known the main concepts in FCA [
This paper focuses on the notion of implication, which can be introduced as follows: De nition 2. Let K = (G; M; I) be a formal context and A; B 2 2M . The implication A ! B holds in K if every object o 2 G satis es the following: (o; a) 2 I for all a 2 A implies (o; b) 2 I for all b 2 B.
An implication A ! B is said to be unitary if the set B is a singleton.
Implications may be syntactically managed by means of inference systems.
The former axiomatic system was Armstrong's Axioms [
In [
De nition 3 (Language). Given a non-empty nite alphabet S (whose elements are named attributes and denoted by lowercase letters a; b; c; etc.), the language of SLFD is LS = fA ! B j A; B Sg.
Sets of formulas (implications) will be named implicational systems (IS). In order to distinguish between language and metalanguage, inside implications, AB means A [ B and A-B denotes the set di erence A r B. Moreover, when no confusion arises, we omit the brackets, e.g. abc denotes the set fa; b; cg. De nition 4 (Semantics). Let K = (G; M; I) be a context and A ! B 2 LS . The context K is said to be a model for A ! B, denoted K j= A ! B, if A; B M S and A ! B holds in K.
For a context K and an IS , then K j= means K j= A ! B for all A ! B 2 and j= A ! B denotes that every model for is also a model for A ! B. If 1 and 2 are implicational systems, 1 2 denotes both IS are equivalent (i.e. K j= 1 i K j= 2 for all context K).
De nition 5 (Syntactic derivations). SLFD considers re exivity axioms [Ref] AB ! AB ; and the following inference rules named fragmentation, composition and simplication respectively.
[Frag] AA!!BBC ; [Comp] A !ACB!;CB!D D ; [Simp] If A C; A \ B = ;, AC!-BB!;CD!-BD
Given an IS and a formula A ! B, ` A ! B denotes that A ! B can
be derived from by using the axiomatic system in a standard way. The above
axiomatic system is sound and complete (i.e. j= A ! B i ` A ! B). The
main advantage of SLFD is that inferences rules may be considered equivalence
rules and they are enough to compute all the derivations (see [
Theorem 1 (Mora et al. [
fA ! B; C ! Dg fA ! B; C ! D-Bg Note that these equivalencies (reading from left to right) remove redundant information. SLFD was conceived as a simpli cation framework.
To conclude this section, we introduce the outstanding notion of closure of a set of attributes, which is strongly related with the syntactic treatment of implications.
largest subset of S, noted X+, such that
S. The closure of X wrt ` X ! X+.
is the We omit the subindex (i.e. we write X+) when no confusion arise. Given a context K and an IS satisfying K j= A ! B i ` A ! B, it is well-known that the closed sets of attributes wrt are in bijection with the concepts of K.
One of the main topics is the computation of the closure of a set of attributes,
and for this reason, it is necessary to have an e cient method to calculate
closures. We emphasize for this problem, the works of Bertet et al. in [
The study of sets of implications that satis es some criteria is one of the most
important topics in FCA. In [
De nition 7. An IS
is said to be: { minimal if r fA ! Bg 6 for all A ! B 2 { minimum if 0 implies j j j 0j, for all IS { optimal if 0 implies k k k 0k, for all IS .
0. 0. where j j is the cardinality of and k k is its size, ie k k = (jAj+jBj).
A minimal set of implications is named a basis, and a minimum basis is then a basis of least cardinality. Let us now introduce the main property used in this paper, namely the direct-optimal property.
is said to be direct if, for all X X+ = X [ [fB j A
X and A ! B 2
S: g Moreover, is said to be direct-optimal if it is direct and, for any direct IS 0 implies k k k 0k.
0,
X
A!B2
In words, is direct if the computation of the closure of any attribute set wrt
requires only one iteration, that is, a unique traversal of the set of implications.
Obviously, the direct-optimal property is the combination of the directness and
optimality properties. In [
As we have said in the preliminaries, one of the most important problems is
how to calculate quickly and easily the closure X+ of any set X because a number
of problems related to an IS can be answered by computing closures. For this
reason, Bertet et al. propose a type of base called direct-optimal basis [
In this section, the algorithm proposed by Bertet and Nebut in [
S:
If B \ C 6= ;, Then, the direct implicational system generated from an IS smallest IS that contains and is closed for [Overlap].
is de ned as the A ! B; C ! D A(C-B) ! D De nition 9. The direct implicational system as the smallest IS such that: d generated from is de ned 1. d and 2. For all A; B; C; D
A(C-B) ! D 2
S, if A ! B; C ! D 2 d and B \ C 6= ; then Function Bertet-Nebut-Direct( ) input : An implicational system on S output: The direct IS d on S equivalent to begin
d := foreach A ! B 2 d do foreach C ! D 2 d do
if B \ C 6= ; then add A(C-B) ! D to d; return
d
d = Bertet-Nebut-Direct( ) is a direct basis. be an implicational system. Then Moreover, if an IS is direct but not direct-optimal, then there exists an equivalent IS 0 of smaller size which is direct-optimal. The properties that it must hold are the following:
only if the following properties hold.
Extensiveness: for all A ! B 2 , A \ B = ;.
Isotony: for all A ! B; C ! D 2 , C A implies B \ D = ;. Premise: if A ! B; A ! B0 2 then B = B0.
Not empty conclusion: if A ! B 2 then B 6= ;. is direct-optimal if and Function Bertet-Nebut-Minimize( ) input : An implicational system on S output: An smaller IS m on S equivalent to begin
m := ; foreach A ! B 2 do
B0 := B foreach C ! D 2 do if C = A then B0 := B0 [ D; if C A then B0 := B0 r D; B0 := B0 r A add A ! B0 to m return m Function Bertet-Nebut-DO computes the direct-optimal basis do generated from an IS . It rst computes d using Function Bertet-Nebut-Direct and then minimizes d using Function Bertet-Nebut-Minimize.
Function Bertet-Nebut-DO( )
input : An implicational system on S
output: The direct-optimal IS do on S equivalent to
begin
d = Bertet-Nebut-direct( )
do = Bertet-Nebut-Minimize( d)
return do
Theorem 4 (Bertet and Nebut [
In some areas, the management of formulas is limited to unitary ones. Thus, the use of Horn Clauses in Logic Programming is widely accepted. Such a language restriction allows an improvement in the performance of the methods, which are more direct and lighter. Nevertheless, the advantages provided by the limited languages have a counterpart: a signi cant growth of the input set. In this section we are going to present new versions of the de nitions and methods introduced above restricted to Unit Implicational System (UIS), i.e. set of implications with unitary right-hand sides. An UIS is named proper if it does not contain implications A ! a such that a 2 A.
In this line, Bertet [
Function Bertet-Unit-Direct( ) input : A proper UIS on S output: The direct UIS d on S equivalent to begin
d := foreach A ! a 2 d do foreach Ca ! b 2 d do
if a 6= b and b 62 A then add AC ! b to d; return
d Function Bertet-Unit-Minimize( ) input : A proper UIS on S output: An smaller UIS m on S equivalent to begin
m := foreach A ! b 2 m do foreach C ! b 2 m do
if A C then delete C ! b from return m m;
The above functions was used in [
Function Bertet-Unit-DO( ) input : An implicational system output: The direct-optimal IS begin u := fA ! b j A ! B 2 and b 2 B r Ag ud := Bertet-Unit-Direct( u) udo := Bertet-Unit-Minimize( ud) do := fA ! B j B = fb j A ! b 2 g 6= ;g return do
on S
do on S equivalent to
Theorem 5 (Bertet [
As we have mentioned at the beginning of this subsection, some authors introduce unitary formulas as a way to provide simpler and more direct methods having a better performance. Thus, in this case, Bertet-Unit-DO is more e cient than Bertet-Nebut-DO, as we shall see at the end of the paper in Section 5.1. 5
In this paper, our goal is the integration of the techniques proposed by Bertet
et al. [2{4] and the Simpli cation Logic proposed by Cordero et al. [
In the same way that Bertet-Unit-DO, we are going to develop a function to get direct-optimal basis whose rst step will be to narrow the implications. However, the use of unit implications has some disadvantages that we are going to avoid by considering another kind of formulas. Thus, we are going to use reduced IS and introduce simpli cation rules which transform it preserving reduceness. A signal which indicates it is a good approach is the fact that at the end of the process, the function renders the direct-optimal basis directly, avoiding the converse switch.
for all A; B S.
is reduced if A ! B 2 implies B 6= ; and A\B = ; Obviously, any IS can be turned into a reduced equivalent one r as follows r := fA ! B-A j A ! B 2 ; B 6 Ag The method proposed begins with this transformation and, once the IS is reduced, this property is preserved. For this reason, [Overlap] must be substituted. Thus, we introduce a new inference rule covering directness without losing reduceness and, at the same time, it makes progress on the minimization task following the simpli cation paradigm. The kernel of the new method is the following inference rule, named strong simpli cation: [sSimp] If B \ C 6= ; and D 6 A [ B,
A ! B; C ! D A(C-B) ! D-(AB) Regardless the conditions, the inference rule always holds. Nevertheless, the conditions ensure a precise application of the rule in those cases where it is necessary. De nition 11. Given a reduced IS , the direct-reduced implicational system dr generated from is de ned as the smallest IS such that 1. dr and 2. For all A; B; C; D S, if A ! B; C ! D 2 dr, B \ C 6= ; and D 6 A [ B then AC-B ! D-(AB) 2 dr Theorem 6. Given a reduced IS and reduced IS.
, then dr =Direct-Reduced( ) is a direct Function Direct-Reduced( ) input : A reduced implicational system on S output: The direct-reduced IS dr on S begin foreach A ! B 2 dr and C ! D 2 dr do
if B \ C 6= ; 6= D r (A [ B) then add AC-B ! D-(AB) to dr; return dr Theorem 1 provides four equivalencies which allow to remove redundant information when they are read from left to right. An implicational system in which these equivalences are used to remove redundant information is going to be named simpli ed implicational system.
for all A; B; C; D S, 1. A ! B, A ! C 2 2. A ! B, C ! D 2 implies B = C.
and A C imply C \ B = ; = D \ B.
Then, Function RD-Simplify turns any direct-reduced IS into a direct-reducedsimpli ed equivalent one by systematically applying the equivalences provided in Theorem 1.
is simpli ed if the following conditions hold: Function RD-Simplify( ) input : A direct-reduced implicational system on S output: The direct-reduced-simpli ed IS drs on S equivalent to begin
drs := ; foreach A ! B 2 do foreach C ! D 2 do if C = A then B := B [ D; if C A then B := B r D; if B 6= ; then add A ! B to drs; return drs Function doSimp( ) input : An implicational system on S output: The direct-optimal IS do on S begin r := fA ! B-A j A ! B 2 dr := Direct-Reduced( r) do := RD-Simplify( dr) return do
; B 6 Ag Theorem 7. Let be an implicational system on S. Then, is the direct-optimal basis equivalent to . do = doSimp( ) Note that, unlike Bertet-Unit-DO where a nal step was needed to revert the e ects of the rst transformation, doSimp do not need to revert the rst step. We conclude this section with an experiment which illustrates the advantages of the new method. 5.1
Logic programming has been used as a natural framework in the areas in which it is neccessary to develop automatic deduction methods. The Prolog prototypes provides a declarative and pedagogical point of departure and illustrates the behavior of new techniques in a very fast and easy way.
Some authors have explored the use of Logic Programming in the framework
of Formal Concept Analysis. Even, in [
In a rst step, the methods proposed in this paper have been developed in a Logic Programming language (Prolog) that is a well-known tool to develop fast prototypes. In our case, the implementation in Prolog is close because the method proposed in this paper is based on logic.
The methods of Bertet et al. [
The following table and gures summarize the results obtained. We show in the columns the results of Prolog: Lips (logical inferences per second lips - used to describe the performance of a logical reasoning system), Time (execution time in seconds), and Comp (the number of couple of implications in which a rule is applied). Areas in Figure 2 show the percentages of each algorithm with respect the number of comparisons. 1 Available at http://www.lcc.uma.es/~enciso/doSimp.zip Lips/Time/Comp.
Bertet-Nebut-DO
Bertet-Unit-DO
Direct-Reduced Ex.1 Ex.2 Ex.3
Ex.a
Ex.a3red Ex.derivation5 Ex.Olomouc Ex.Ganter Ex.CLA14 Ex.Saedian1 Ex.Saedian2 EX.Saedian3 Ex.Wastl10 Ex.Wastl13 Example1
1555372119591012811193762073809212590593647541238681701054584912041233432325 000000000411.........52200000000026422001000000827522594243 4113992211213873020969821176804007076358 151126171411666264003174859191355446391605304424478286538999209413 000000000.........0030000000.032100000110000189372216 1118632331143841076036203 1254313134124567761000627366458924621802083628284991476 000000000.........00000000000000000013111151100000 1715111122553244351226 5594556921 7008.890 134175 2662181973 1351.950 5389 1199498 0.197 1103 Lips - logical inferences Time of execution (seconds) Number of comparisons
IS Bertet Nebut 374; 760; 194:4 467; 728:5 9588:4
UIS Bertet
177; 610; 983:3
90; 130:03693
388:4
In this work, we have presented another algorithm to calculate the direct-optimal
basis in a further way, in the most of the cases, than the algorithms which exist in
the literature. It is shown with a test that we have realised by running di erent
examples with the methods of Bertet et al. for UIS [
Our aim is to reduce the cost of the algorithm by using the Simpli cation Logic as a useful tool to work with implications. By the time, we have improved the algorithms that existed but we are going to go on working in that way to try to cut down the cost of our method.
The perspectives we have are improvements by pretreatments: reduction, canonical basis, etc in order to reach our main objective which would be to directly compute the direct-optimal basis without extra implication generation.
Supported by grant TIN11-28084 of the Science and Innovation Ministry of Spain.