AddIntent:A New Incremental Algorithm for Constructing Concept Lattices
Dean van der Merwe1,Sergei Obiedkov2,and Derrick Kourie1
1Department of Computer Science,University of Pretoria,Pretoria,0002,South Africa Deon.vd.,DKourie@cs.up.ac.za
2Institute f¨u r Algebra,TU Dresden,01062Dresden,Germany s-obj@yandex.ru Abstract.An incremental concept lattice construction algorithm,called
AddIntent,is propod.In experimental comparison,AddIntent outper-
formed a lection of other published algorithms for most types of con-
texts and was clo to the most efficient algorithm in other cas.The
current best estimate for the algorithm’s upper bound complexity to con-
struct a concept lattice L who context has a t of objects G,each of
which posss at most max(|g |)attributes,is O(|L||G|2max(|g |)).
nun1Introduction
In Formal Concept Analysis(FCA)[1,2],the problem of generating the t of all concepts of a formal context and constructing the diagram graph(cover-ing relation)of the concept lattice has been well studied[3–7].See[8]for an overview and comparison.Since lattices can grow exponentially large,leading to correspondingly large computational requirements,efficient algorithms for the construction of concept lattices are of key importance.
In this text,we introduce a new lattice construction algorithm,called AddIn-tent,an earlier version of which appeared in[9]under the name AddAtom.The algorithm produces not only the concept t,but also the diagram graph.Be-ing incremental,it relies on the graph constructed from thefirst objects of the context to integrate the next object into the lattice.Therefore,its u is most appropriate in tho applications that require both the concept t and diagram graph,for example,in applications related to information retrieval and document browsing[10].Nevertheless,experiments show that sometimes it takes other al-gorithms longer merely to construct the concept t of a context than it takes AddIntent to construct the entire diagram graph of the same context.
The upper bound complexity estimate of the algorithm is linear in the lat-tice size modulo some facto
r polynomial in the input size.Although the current estimate of the polynomial factor is higher than that of the lowest known for lattice construction ,that of[11]),experimental comparison in-dicates that,in practice,AddIntent performs well in constructing lattices from many different contexts.It outperforms other algorithms in most cas and may therefore be considered as the best candidate for a universal lattice construction algorithm for diagram graphs amongst the algorithms considered in this study.
2Main Definitions
This ction defines the basic terminology and notation of Formal Concept Anal-ysis[1].
Definition1.A formal context is a triple of ts(G,M,I),where G is called a t of objects,M is called a t of attributes,and I⊆G×M.The notation gIm indicates that(g,m)∈I and denotes the fact that the object g posss the attribute m.
Definition2.For A⊆G and B⊆M:
A ={m∈M|∀g∈A(gIm)}and
B ={g∈G|∀m∈M(gIm)}.
The operator is a closure operator(to be preci, is a homonymous denotation of two closure operators:2G→2G and2M→2M.
Definition3.A formal concept of a formal context(G,M,I)is a pair(A,B), where A⊆G,B⊆M,A =B,and B =A.The t A is called the extent,and the t B is called the intent of the concept(A,B).
For g∈G and m∈M,{g} is denoted by g and called an object intent, and{m} is denoted by m and called an attribute extent.
Definition4.For a context(G,M,I),a concept X=(A,B)is less general than or equal to a concept Y=(C,D)(or X≤Y)if A⊆C or,equivalently, D⊆B.
Definition5.For two concepts X and Y,if X≤Y and there is no concept Z with Z=X,Z=Y,X≤Z≤Y,the concept X is called a lower neighbour (or a child)of Y and Y is called an upper neighbour(or a parent)of X.This relationship is denoted by X≺Y.
Definition6.We call the(directed)graph of the relation≺a diagram graph.A plane embedding of a diagram graph where a concept has larger vertical coordinate than that of any of its lower neighbors is called a line(Has)diagram.
3The AddIntent Algorithm
In this ction,we define the AddIntent algorithm and describe the basic strategy it follows.Readers are referred to[12]for a more detailed discussion.
AddIntent is an incremental ,it takes as input the lattice L i produced by thefirst i objects of the context and inrts the next object g to generate a new lattice L i+1.As obrved in[5,7]lattice construction can be described in terms of four ts of concepts:modified concepts,generator concepts, new concepts and old concepts.
A concept(C,D)∈L i+1is new if D is not an intent of any concept in L i. We call a concept(A,B)∈L i modified if B⊆g since g has to be added to its extent in L i+1.Otherwi,B∩g =D=
B for some concept(C,D)∈L i+1.
If(C,D)is a new concept,then(A,B)is called a generator of(C,D);if not, (A,B)is called old.
Every new concept(C,D)has at least one generator,but it may have veral. The(unique)most general of the generators is called the canonical generator of (C,D).The remaining generators of(C,D)are naturally called its non-canonical generators.Obviously,there is a one-to-one corresponde
nce between canonical generators and new concepts.
The key problem of incremental construction is how to identify all modified concepts(in order to add g to their extents)and all canonical generators of new concepts(in order to generate every new concept exactly once).Efficient algorithms will spend as little effort as possible arching through the unmodified and non-canonical generators.AddIntent approaches this problem by traversing the diagram graph of L i in a recursive fashion.
There are veral ways to identify canonical generators.The algorithm in [5]process the list of concepts in L i starting with the most general ones.In processing a concept(A,B),it generates the intent B∩g and then looks through the t of new concepts produced so far(and arranged in“buckets”according to the cardinality of their intents)to e whether such an intent is already there. The algorithm of Norris[6],in processing a concept(A,B),checks whether B∩g ⊆h for any h∈Gi\A(assuming that G i is the t of objects procesd up to that moment);if so,then A is not the maximal extent,and hence(A,B)is not the most general concept capable of generating B∩g .What both algorithms ignore are the following facts:
Proposition1.If(B ,B)is a canonical generator of a new concept(F ,F), while(D ,D)is a non-canonical g
enerator of(F ,F)–in this ca,B⊂D–then any concept(H ,H)such that H⊂D and H⊂B is neither modified nor is it a canonical generator of any new concept.
Proposition2.If(D ,D)is an old concept and D∩g =B–in this ca, (B ,B)∈L i is modified–then any concept(H ,H)such that H⊂D and H⊂B is neither modified nor is is a canonical generator of any new concept.
Therefore,there is no need to process such concepts(H ,H)in the arch of canonical generators and modified concepts.Since AddIntent maintains the diagram graph(which explicitly orders concepts from most to least general)it can exclude the concepts from further consideration by simply traversing the diagram graph in a bottom-up fashion.Having found a non-canonical genera-tor,AddIntent us the diagram graph tofind the canonical generator of the same concept.It then works only with concepts above that canonical generator, ignoring all other concepts above the non-canonical generator.The canonical generator can be found in a diagram graph in at most O(|G|2|M|)time.
The ideas are expanded in[12]where the notions of the approximate intent reprentative and exact intent reprentative are introduced in the context of so-called compresd pudo-lattices.
Using parameter names to imply types the AddIntent function is defined as follows:
01:Function AddIntent(intent,GeneratorConcept,L)
02:GeneratorConcept=GetMaximalConcept(intent,
GeneratorConcept,L)
03:If GeneratorConcept.Intent=intent
04:Return GeneratorConcept
05:End If
06:GeneratorParents:=GetParents(GeneratorConcept,L)
07:NewParents=
08:For each Candidate in GeneratorParents
09:If Candidate.Intent⊂intent
10:Candidate:=AddIntent(Candidate.Intent∩intent,
Candidate,L)
11:End If
12:addParent:=true
13:For each Parent in NewParents
14:If Candidate.Intent⊆Parent.Intent
15:addParent:=fal
16:Exit For
17:El If Parent.Intent⊆Candidate.Intent
18:Remove Parent from NewParents
19:End If
20:End For
21:If addParent
22:Add Candidate to NewParents
23:End If
24:End For
25:NewConcept:=(GeneratorConcept.Extent,intent)
26:L:=L∪{NewConcept}河南二级建造师报名时间
27:For each Parent in NewParents
oppo手机广告曲28:RemoveLink(Parent,GeneratorConcept,L)
29:SetLink(Parent,NewConcept,L)
30:End For
31:SetLink(NewConcept,GeneratorConcept,L)
32:Return NewConcept
The parameters of the function AddIntent(intent,GeneratorConcept,L)are the intent of a new concept to be placed into the concept lattice L and a pre-computed GeneratorConcept,such that intent is a subt of the intent of Gener-atorConcept.AddIntent returns a concept who intent corresponds to intent–a new concept will be created if there was no such concept before or an existing one will be returned otherwi.
First,the algorithmfinds the most general concept who intent is a super-t of intent(line02)and assigns it to GeneratorConcept.If the intent of this concept is equal to intent,then the desired concept is already in the lattice and the algorithm terminates(line04).Otherwi,GeneratorConcept is the canon-
ical generator of the new concept,which has to be created and linked to other concepts in the diagram graph.
Tofind the parents of the new concept in the diagram graph,we examine all parents of GeneratorCon
cept(lines08-24).If the intent of such a parent,called Candidate,is a subt of intent,then Candidate is modified.Otherwi,a recur-sive call to AddIntent ensures that the lattice contains a concept who intent is equal to the interction of intent and the intent of Candidate.This concept is assigned to Candidate(line10).Then,Candidate is added to the(initially empty)NewParents list if it is minimal among its current elements(that is,has a maximal intent).At the same time,if some concept in NewParents is more general than Candidate,this concept is removed from the list(line18).Thus, the NewParents list always contains being more general) concepts.Moreover,in the end,it contains precily the parents of NewConcept that is to be inrted(line25).Proposition3below provides basis for the out-lined procedure and Corollary1shows a way to optimize it(there is no need to test modified candidates for being minimal):
Proposition3.(F ,F),then the parents of(F ,F)in L i+1are exactly the least general concepts from the t{(D ,D)|D=F∩H for some parent(H ,H)of (B ,B)in L i}.
Corollary1.If(B ,B)is the canonical generator of(F ,F),then every modi-fied parent of(B ,B)in L i is a parent of(F ,F)in L i+1.
Thus,having procesd the parents of GeneratorConcept,we create New-Concept with intent equal t
o intent and link it to concepts in the NewParents list,taking care to remove existing links between the concepts and Genera-torConcept(lines27-30).Finally,NewConcept is t to be an upper neighbor of GeneratorConcept(line31),and the AddIntent function returns NewConcept.
Note that the AddIntent function as described above does not update extents. Such an update is performed by the calling procedure constructing the lattice (shown below),but it can be easily integrated into AddIntent as well.
difference01:Procedure CreateLatticeIcrementally(G,M,I)
02:BottomConcept:=(∅,M)
03:L:={BottomConcept}
04:For each g in G
eba05:ObjectConcept=AddIntent(g’,BottomConcept,L)
06:Add g to the extent of ObjectConcept and all concepts above
07:End For
After adding an object of the context to the lattice via a call to AddIntent, the procedure updates the extents of the concepts above and including the newly generated ObjectConcept.
01:Function GetMaximalConcept(intent,GeneratorConcept,L)
consumer02:parentIsMaximal:=true
03:While parentIsMaximal保质期英文
04:parentIsMaximal:=fal
05:Parents:=GetParents(GeneratorConcept,L)
06:For each Parent in Parents
07:If intent⊆Parent.Intent
08:GeneratorConcept:=Parent
09:parentIsMaximal:=true
available的用法10:Exit For
11:End If
12:End For
13:Return GeneratorConcept
atbelt
In the GetMaximalConcept function,we u the diagram graph tofind the most general concept,who intent is a supert of the input intent.If this concept is not GeneratorConcept,then it is among its predecessors;therefore,it is sufficient to examine the predecessors of GeneratorConcept.If a more general concept is found(line8),no further processing of Parents is required and this more general concept can be tested in the next iteration of the While loop.
The algorithms described above admit a number of optimizations,which are discusd in[12]but are not included here due to space limitations.For ex-ample,the number of t operations in the GetMaximalConcept function can be reduced by pre-computing the number of attributes of g that each con-cept in L has in common with g since|intent|=|P arent.Intent∩g |implies intent⊆P arent.Intent(line07).Byfirst considering the candidate concepts who intents yield the largest interction with the new object intent,unneces-sary traversal of the lattice can be avoided.
A worst-ca time complexity bound of O(|L||G|3|M|)for the above version of the ,the CreateLatticeIcrementally procedure)is derived in[13] (where|L|is the number of concepts in the resulting lattice).A detailed dis-cussion is not possible here due to space limitations,but the main argument is as follows.The complexity depends on the total number of invocations of the AddIntent function.The same intent can be pasd as a parameter of AddIn-tent veral times,but,clearly,the execution of AddIntent will go past line05, i.e.,past the call to GetMaximalConcept,at most once for every intent.Thus, for convenience,we may assume that GetMaximalConcept is called before the invocation of the AddIntent function,which,in its turn,is called only if the intent of the returned“maximal concept”is different from intent.In this t-ting,AddIntent would be called at most once for every intent of the lattice through the inrtion of all objects.Since the length of the GeneratorParents list never exceeds|G|and the complexity of GetMaximalConcept(as defined here)is bounded by O(|G|2|M|),the complexity of a single invocation of AddIn-tent(without a recursive call)can be estimated as O(|G|3|M|),which leads us to the total complexity of O(|L||G|3|M|)as stated above.
By introducing the optimizations referred to,this bound can be improved to O(|L||G|2.max(|g |)where max(|g |)is the maximum number of attributes of any object in the context[12].For the purpo of direct comparison with other
davy crockett
