# Layered Concept Lattice Model and Its Application to Build Rapidly Concept Lattice

Authors: Xia Wu; Jialu Zhang; Jiaming Zhong
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

When some attributes of a formal context can be decomposed into some subattributes a model of layered concept lattice to improve the efficiency of building concept lattice with complex structure attribute data is studied, the relationship between concept lattice and layered concept is discussed. Two algorithms are proposed: one is the roll-up building algorithm in which the upper concepts are built by the lower concept and the other is the drill-down algorithm in which the lower concepts are built by the upper concept. The examples and experiments show that the layered concept lattice model can be used to model complex structure attribute data, and the roll-up building algorithm and the drill-down algorithm are effective. The layered concept lattice model expands the scope of the research and application of concept lattice, the roll-up building algorithm, and drill-down algorithm of layered concept lattice to improve the efficiency for building concept lattice.


---

## Body

## 1. Introduction

Humans usually describe and recognize objective things from different levels and different granularity. There is a process of deepening the attribute characteristics of objective things, and hence the knowledge concepts at different levels or at different granularity are obtained [1, 2]. Granular computing is a kind of useful mathematical method for processing complex structure data, and the idea of granular computing fits perfectly with the hierarchical and granular thinking mode of “from coarse to fine, from whole to part” in the process of human cognition [3–5]. The idea of granular computing originated from professor Zadeh [6]. Since Lin summarized relevant studies and introduced the term granular computing in 1998 [7], the thinking and methods of granular computing have appeared in many fields, such as rough set, fuzzy set, evidence theory, cluster analysis, machine learning, data mining, and knowledge discovery. In recent years, research studies on granular computing have been extensive and many meaningful results have been obtained. For example, Yao studied the basic problems and methods of granular computing [3], Lin studied the granular structure and representation [7], Pedrycz studied the granular computing methodology, mathematical framework, and information granulation algorithm [8], and Zhang and Zhang studied the quotient space [9].Concept lattice is the key data structure of formal context analysis, and it is also a kind of basic data structure suitable for knowledge representation and knowledge discovery [10]. There have been many studies on basic theory of concept lattice [11] and algorithms to accelerate the construction of concept lattice [12–14], and concept lattice has been widely applied in many fields including data mining [15], knowledge discovery [16], information retrieval, and information extraction [17, 18]. Theory and application research of concept lattice are inseparable from the structure analysis of concept lattice and the model extension of concept lattice. The existing concept lattice models and their extension models are established on the relation between objects and attributes, they handle only the simple type of data, and there is no model that has been able to handle data with complex structures. For example, by using a fuzzy set on the basic language set [19], Wolff represented attribute values with fuzzy language variable values in a formal context, classified objects according to the scale, and then built concept lattice based on the scale [20]. Burusco and Fuentes discussed the concept lattice structure based on L-fuzzy concept set and proposed a method to build concept lattice in this case [21]. Considering that Burusco and Fuentes’ models cannot handle continuous membership values and have high computational complexity, Qiang et al. proposed a fuzzy conceptual lattice model that can handle continuous membership values, and based on this model, they discussed the extraction of fuzzy rules and the clustering of fuzzy concepts [22]. Ali and Samir introduced the real interval formal context, established the real interval concept lattice, and built the classifier on the real interval concept lattice for data classification [23]. Qu et al. aimed to establish the relationship between formal concept analysis and rough set theory, obtained derivative formal context that can be induced by the notion of nominal scale and plain scaling and the technique of plain scaling in an information system, and proved that some core notions in rough theory such as partition, upper and lower approximation, independence, dependence, and reduction can be reinterpreted in derivative formal context. They pointed out that the rough set model can be extended by using plain scaling, but they have not further studied the concept lattice structure in the derivative formal context [24].Due to the complexity of research objects, complex structural data are widely used in practical applications. For example, in the field of network intelligent information processing, it is necessary to analyze the correlation among characters, time, action, environment, and other elements through text, image, audio, video, etc. These elements are usually expressed in different types of data [25]. In particular, under big data environment, the remarkable feature of data is the diversity of types and the complexity of structures. An application often deals with both structured data and semistructured, unstructured data such as text, images, audio, video, video, and Web. In order to apply formal concept analysis to study knowledge representation and knowledge discovery in big data environment, the first thing to do is to extend the existing concept lattice model. In the process of extending the concept lattice model in big data environment, the attribute values used to describe the characteristics of unstructured data, such as text, images, audio, video, and Web, include word values, text values, vector values, and their composite values, in addition to the usual number value and character value [26, 27]. On formal context analysis on complex structural data, Zhi proposed a generalized concept lattice model for heterogeneous data analysis by discussing the partial order composition on heterogeneous datasets [28, 29]. However, Zhi’s concept lattice model for heterogeneous data is only considered at the same level and at the same granularity, which does not reflect the idea of hierarchy and granularity of human thinking. Therefore, to describe human thinking process from a mathematical perspective or to apply the concept lattice theory to describe the human thinking process, we need to build the concept lattice model at different levels and different granularity.In order to satisfy the need for describing in detail the knowledge concept on unstructured dataset, the thinking of granular computing is applied to the formal concept analysis of data with complex structure. The layered structure of attribute data is fully considered, and a layered concept lattice model with layered and three-dimensional structure is built in the complex structure data environment. The relation between concept lattice of original formal context and layered concept lattice of layered formal context is discussed. The roll-up building algorithm in which the upper concept is built by the lower concept and the drill-down algorithm in which the lower concept is built by the upper concept are proposed. The examples and experiments show that the roll-up and the drill-down algorithms are effective.


## 2. Preliminary

In this section, we summarize some basic notions and conclusions on concept lattices. For more details of these notions and conclusions, we refer the reader to Ganter and Wille’s works “Formal Concept Analysis” [10].Definition 1.
A formal context is a tripletK=G,M,I, where I⊆G×M is a binary relation between G and M. The elements in G and M are called objects and attributes, respectively. g,m∈I or gIm indicates the object g has the attribute m.Definition 2.
LetK=G,M,I be a formal context. For a set A⊆G of objects, we define a set of attributes common to all objects in A as(1)αA=m∈MgIm,∀g∈A.
Correspondingly, for a setB⊆M of attributes, we define the set of objects that have all attributes in B as(2)βB=g∈GgIm,∀m∈B.
In brief, we also denoteαa,βm as αa,βm.Proposition 1 (see [10]).
ForA,A1,A2⊆G and B,B1,B2⊆M,(1)
A1⊆A2⟹αA2⊆αA1,B1⊆B2⟹βB2⊆βB1(2)
A⊆βαA,B⊆αβB(3)
A⊆βB⟺B⊆αA(4)
αA1∪A2=αA1∩αA2, βB1∪B2=βB1∩βB2(5)
αA1∩A2⊇αA1∪αA2, βB1∩B2⊇βB1∪βB2(6)
βαA,αA and βB,αβB are conceptsDefinition 3.
LetK=G,M,I be a formal context. For A⊆G and B⊆M, if αA=B and βB=A, then a pair A,B is called a formal concept of formal context K, and A and B are called the extent and the intent of A,B, respectively. The set of all concepts of formal context K is denoted as CK.Definition 4.
LetA1,B1 and A2,B2 be two formal concepts of a given formal context K. A1,B1 is called a subconcept of A2,B2 if A1⊆A2(or equivalently B1⊇B2), which can be denoted by A1,B1≤A2,B2.
Obviously, the subconcept relation≤ is a partial order on CK. Since ≤ is a partial order, we can adopt the definition of neighboring nodes of order theory here. Let C1 and C2 be two concepts of a given formal context K. We say C1 is a lower neighbor (or a child) of C2 and C2 is an upper neighbor (or a parent) of C1, if C1≤C2 and there is no other concept C3 with C3≠C1, C3≠C2, and C1≤C3≤C2.Theorem 1 (see [10]).
The setCK of all formal concepts of context K together with partial order ≤ makes a complete lattice, which is called a concept lattice of K and is denoted as CK,≤; the upper and lower bound operations are(3)∧t∈TAt,Bt=∩t∈TAt,αβ∪t∈TBt,∨t∈TAt,Bt=βα∪t∈TAt,∩t∈TBt.


## 3. Layered Concept Lattice Model and Its Roll-Up Algorithm to Build the Upper Concept Lattice

According to the analysis in the introduction, when we discuss the concept lattice theory and application of complex data structure, the problem of data attribute stratification is often encountered. For example, on the basis of the discussing new energy vehicles at coarse-grained, we often need to discuss the problem of new energy vehicles at a finer granularity to meet the needs of practical application: hybrid vehicles and pure electric vehicles. In terms of the concept lattice, when the new energy attribute is decomposed into lower hybrid power and pure electric power attributes, we need to analyze the formal concept in the layered formal context.In this section, we give the definition of layered formal context and layered concept lattice, discuss their properties, and propose a roll-up building algorithm of layered concept lattice in a normal layered formal context.


### 3.1. Layered Concept Lattice Model and Roll-Up Algorithm Theory

Definition 5.
LetK=G,M,I be a formal context. If every attribute in M can be represented as a subset, which means that(4)M=m1,m2,⋯,ml,mk=mk1,mk2,⋯,mkik,k=1,2,⋯,l,then K=G,M,I is called a layered formal context and mk is called a layered attribute. In a layered formal context K=G,M,I, the lower attributes corresponding to the layered attribute mk are denoted as(5)mk¯=mk,mk1,mk,mk1,⋯,mk,mkik.
Ifik=1, then mk¯=mk, which is actually not a layered attribute.
By using the formal contextK=G,M,I, we can introduce a new layered formal context K¯=G,N,J, where N=∪k=1lmk¯, and the relation J between objects and attributes is defined by gJmk,mki⟺gImk. For the convenience of expression, we also call K the upper formal context, K¯ the lower formal context, CK the upper concept lattice, and CK¯ the lower concept lattice accordingly.
A layered formal contextK=G,M,I is normal if for every layered attribute gImk iff there is a unique iff there is a unique lower attribute mki such that gJmk,mki.
In this paper, we only discuss the normal layered formal context. The following conclusion is obvious.Proposition 2.
Suppose thatK=G,M,I is a layered formal context. Then,(6)βmk,mk1,βmk,mk2,⋯,βmk,mkik,is a partition of βmk.Example 1.
Table1 shows a simplified layered formal context K=G,M,I, where a=“off-road vehicle,” b= “midrange vehicle,” c= “new energy power vehicle” which is a layer attribute, c1= “hybrid power,” and c2= “pure electric power.”
The formal contextK¯ induced by K is shown in Table 2.
When a formal conceptK contains layered attributes, the upper concept lattice CK is closely related to the lower concept lattice CK¯. Hence, we can start with the lower concept lattice CK¯ by rolling up the lower attributes mk¯ of some lower concepts to an upper attribute mk and then building a upper concept; this is easier than building the concept lattice directly from the formal context K.Table 1
Layered formal contextK.
Gabcc1c2110002010030010400015111061101Table 2
Formal contextK¯ induced by K.
Gabc,c1c,c2110002010030010400015111061101Theorem 2.
Suppose thatK=G,M,I is a layered formal context, K¯=G,N,J is the corresponding lower formal context of K, and CK and CK¯ are upper concept lattice and lower concept lattice, respectively. If A1,B1¯,⋯,Aα,Bα¯⊆CK¯ contain the same layered attribute mk¯ and are the nearest subconcepts of a node concept, then(1)
A1,B1¯,⋯,Aα,Bα¯ can be rolled up as a new concept Ak,Bk, where Ak=A1∪⋯∪Aα and Bk=B1¯−mk¯∩⋯∩Bα¯−mk¯∪mk.(2)
The lower conceptsAi,Bi¯i=1,⋯,α are all updated into Ai,Bi¯−mk¯∪mk, respectively.Proof.
It is worth pointing out before proving that a conceptAi,Bi¯ in CK¯ may contain both nonlayered attributes and lower attributes in the form of mk,mkl. In the following, we prove the theorem by four steps.(1)
Prove equationαAk=m∈MgIm,∀g∈Ak=Bk.
Letml∈αAk. Then, for each g∈Ak=A1∪⋯∪Aα, we have gIml. If ml=mk, then obviously ml∈Bk. If ml≠mk, then because Ai,Bi¯i=1,⋯,α are concepts and gIml for each g∈Ai, we have that ml∈Bi¯i=1,⋯,α. So, ml∈B1¯−mk¯∩⋯∩Bik¯−mk¯. This means that ml∈Bk. Hence,(7)αAk=m∈MgIm,∀g∈Ak⊆Bk.
Suppose thatml∈Bk. If ml∈mk, then ml=mk. Hence, mk are the layered attributes of concepts A1,B1¯,⋯,Aik,Bik¯, so αAi=m∈NgJm,∀g∈Ai=Bi¯,i=1,⋯,α. Thus, for each g∈Ak=A1∪⋯∪Aα, there exists i0 such that g∈Ai0, so gJmk,mki0, and gImk. This shows that gImk for each g∈Ak=A1∪⋯∪Aα. This means that mk∈αAk. If ml∈B1¯−mk¯∩⋯∩Bα¯−mk¯, then ml≠mk is not a layered attribute and ml∈Bi¯,i=1,⋯,α. Since Ai,Bi¯,i=1,⋯,α are concepts, we have gIml for each g∈Ak=A1∪⋯∪Aα. Hence, ml∈αAk. Thus, Bk⊆αAk=m∈MgIm,∀g∈Ak.(2)
Prove equationβBk=g∈GgIm,∀m∈Bk=Ak.
At first, we proveβBk⊆Ak. Let us assume g∈βBk; then, for every m∈Bk=B1¯−mk¯∩⋯∩Bα¯−mk¯∪mk, we have gIm. Hence by gImk, we know that there are some i such that gJmk,mki, so gJmk¯, and let i0 be the subscript of biggest concept Ai0,Bi0¯ in these concepts, where the biggest concept means that the concept contains as many object elements as possible and as fewer attribute elements as possible. Thus, from Ai0,Bi0¯ being the biggest concept, we obtain that(8)g∈βBi0¯=g∈GgJmk,mki,∀mk,mki∈Bi0¯=Ai0.
This means thatg∈Ak. Therefore,(9)βBk=g∈GgIm,∀m∈Bk⊆Ak.
Secondly, we proveAk⊆βBk. Let g∈Ak; then, there are some i such that g∈Ai, and let i0 be the subscript of biggest concept Ai0,Bi0¯ in these concepts. Hence, g∈Ai0=βBi0¯, and for each m∈Bi0¯, gJm. This shows that g∈g∈GgIm,∀m∈Bk, and then g∈βBk. Therefore,(10)Ak⊆βBk=g∈GgIm,∀m∈Bk.
From (1) and (2) we know thatAk,Bk is a concept.(3)
Prove that the conceptsAi,Bi¯∈CK¯i=1,⋯,α, which are not rolled up, are updated new concepts Ai,Bi¯−mk¯∪mki=1,⋯,α.
At first, we prove equationαAi=m∈MgIm,∀g∈Ai=Bi¯−mk¯∪mk.
Letml∈αAi; then, for every g∈Ai, we have gIml. If ml=mk, then certainly ml∈Bi¯−mk¯∪mk. If ml≠mk, then from that Ai,Bi¯ is a concept and gImq for every g∈Ai, we have ml∈Bi¯. Hence, ml∈Bi¯−mk¯. This shows that αAi=m∈MgIm,∀g∈Ai⊆Bi¯−mk¯∪mk.
Conversely, letml∈Bi¯−mk¯∪mk. If ml∈mk, namely, ml=mk is a layered attribute, then by Ai,Bi¯ being a concept, we obtain that(11)Bi¯=αAi=mk,mki∈NgJmk,mki,∀g∈Ai.
Hence, bygJmk,mki⟺gImk, we know mq∈αAi. If mq∈Bi¯−mk¯, then mq≠mk and mq∈Bi¯. Since Ai,Bi¯ is a concept, we have gImq for every g∈Ai; hence, mq∈αAi. Therefore,(12)αAi=m∈MgIm,∀g∈Ai⊇Bi¯−mk¯∪mk.
Secondly, we prove the following equation:(13)βBi¯−mk¯∪mk=g∈GgIm,∀m∈Bi¯−mk¯∪mk=Ai.
Letg∈βBi¯−mk¯∪mk; then, gIm for every m∈Bi¯−mk¯∪mk. Since Ai,Bi¯ is a concept, we know βBi¯=g∈GgJm,∀m∈Bi¯=Ai. Hence, by gJmk,mki⟺gImk, we have(14)βBi¯−mk¯∪mk=g∈GgIm,∀m∈Bi¯−mk¯∪mk⊆Ai.
Conversely, letg∈Ai. Then, since Ai,Bi¯ is a concept, we have βBi¯=g∈GgJm,∀m∈Bi¯=Ai. If m∈Bi¯ is not a layered attribute, then the relation between g and m does not change before and after rolling up. If m∈Bi¯ is a layered attribute and its form is mk,mkj, then by gJmk,mki⟺gImk, we have gIm for each m∈Bi¯−mk¯∪mk. Therefore,(15)Ai⊆βBi¯−mk¯∪mk=g∈GgIm,∀m∈Bi¯−mk¯∪mk.(4)
Prove that the partial order amongAi,Bi¯−mk¯∪mki=1,⋯,α is the same Ai,Bi¯i=1,⋯,α.
By the structure ofAk,Bk, for i=1,⋯,α, we have(16)Ai,Bi¯−mk¯∪mk≤Ak,Bk.
If two conceptsAi,Bi¯ and Aj,Bj¯ are in CK¯ with order Ai,Bi¯≤Aj,Bj¯, then the following also holds:(17)Ai,Bi¯−mk¯∪mk≤Aj,Bj¯−mk¯∪mk.


### 3.2. The Description and Analysis of Roll-Up Algorithm

In order to simplify the presentation below, we introduce the following two terms: parallel lower subconcepts and linear lower subconcepts. LetA1,B1¯,⋯,Aα,Bα¯ be the lower subconcepts under node concept A,B. If there is no partial order relation between each other, then A1,B1¯,⋯,Aα,Bα¯ is called parallel lower subconcepts. If there is linear partial order relation among them, then A1,B1¯,A1,B1¯,⋯,Aα,Bα¯ is called linear lower subconcepts.Because this paper only discusses the normal layered formal context and in a normal layered formal context an object will not have two lower attributes of one layer attribute, a concept will not contain more than two lower attributes except the empty concept (object set is empty set). Hence, every concept in the linear lower subconcepts only contains the same lower attribute, and different attributes among different subconcepts are nonlayer attributes. On the basis of this analysis, we can present a roll-up building algorithm of building a concept lattice based on attribute fusion. The process of rolling up fromCK¯ to CK involves the fusion of attributes, and the partial order in the concept lattice is defined according to the negative inclusion of the attribute subset. Thus, the rolling up is carried out from top to bottom, that is, start with the concept of having fewer attributes. The method of rolling up is to roll up the lower concept of node concept A,B in the lower concept lattice CK¯ in a linear or parallel lower subconcepts, insert the new concept obtained from rolling up into the bottom of node A,B, and update the node concept A,B and its related node concept accordingly (given in Algorithm 1).Algorithm 1: Roll-up building algorithm of layered concept lattice.
Input: a lower concept lattice CK¯ of layered formal context K¯ induced by formal context K.Output: an upper concept lattice.Step 1. For k=1,2,…,l, select all lower concepts containing layered attribute mk¯ and form lower concept set CkK¯ to be rolled up.Step 2. The concepts in CkK¯ are sorted in ascending order according to the number of lower attributes contained within it. When the number of lower attributes is the same, the concepts containing fewer nonlower attributes are ranked ahead.Step 3. From top to bottom, roll up the lower concepts in CK¯. For the linear lower subconcepts under node concept A,B in CkK¯, the rolling-up method is as follows: combine the linear lower concepts A1,B1¯,…,Aβ,Bβ¯ containing mk¯ into a new concept Ak,Bk, where Ak=A1∩⋯∩Aβ, Bk=B1¯−mk¯∪⋯∪Bβ¯−mk¯∪mk, and insert Ak,Bk to node A,B below. If node concept A,B contains subconcepts with nonlower attributes, then node A,B is updated to be the common upper bound of Ak,Bk and other concepts (excluding lower attributes in mk¯) under node A,B.Step 4. For the parallel lower subconcepts and lower subconcepts under node concept A,B in CkK¯, the rolling-up method is as follows: combine the parallel lower concepts A1,B1¯,…,Aβ,Bβ¯ containing mk¯ into a new concept Ak,Bk, where Ak=A1∪⋯∪Aα, Bk=B1¯−mk¯∩⋯∩Bα¯−mk¯∪mk, and insert Ak,Bk to node A,B below. If node concept A,B contains subconcepts with nonlower attributes, then node A,B is updated to be the common upper bound of Ak,Bk and other concepts (excluding lower attributes in mk¯) under node A,B.Step 5. If the node concept A,B has both the parallel lower subconcepts and the linear lower subconcepts, then linear lower subconcepts are fused firstly; the method of fusion is to replace the linear lower subconcepts with the minimum concept in these linear lower subconcepts and then roll up the parallel lower subconcepts by Step 4 secondly.Step 6. Update the subconcept Cj,Dj¯, which is not rolled up from Step 3 to Step 5 but it contains the lower attribute of mk¯, to a new concept Cj,Dj¯−mk¯∪mk.Step 7. Repeat from Step 3 to Step 6 until the concept in CK¯ does not contain the lower attribute of mk¯ (namely, CkK¯ is an empty set).Step 8. Repeat from Step 1 to Step 7 until CK¯ does not contain any layered attribute. Algorithm is completed.The time complexity of Algorithm1 is related to the number of layered attributes and the number of lower attributes in the layered context. In the following, we assume that the number of layered attributes in K is l, the number of node in CK¯ is s, and the maximum number of lower attributes of all layered attributes is r. The computing number at Step 1 is r, and its time complexity is Or. The time complexity at Step 2 is Orlog2r; it is equal to the time complexity of r concept sorting. At Step 3, in the worst case, the number of linear lower subconcepts under a node in CkK¯ is l, and the number of computing in rolling up is l, but the total number of computing of all nodes in rolling up is not more than s. Hence, the time complexity at Step 3 is Os. The time complexity of Step 4 and Step 5 is the same as that of Step 3, which is also Os. The computing number at Step 6 does not exceed s−r, so the time complexity at Step 6 is Os−r. The time complexity analysis at Step 7 has been included from Step 3 to Step 6. Therefore, the time complexity of Algorithm 1 is Or+rlog2r+s+s−rl=Ol2s+rlog2r.The following example illustrates the application of the roll-up building algorithm in building concept lattice.Example 2.
Consider the layered formal contextK as shown in example 1; the induced formal context by K is shown in Figure 1.Figure 1
Concept latticeCK¯ of formal context K¯.Steps 1 and 2.
The concepts containing lower attributes inCK¯ are arranged in ascending order according to the number of attributes of concepts, CkK¯=35,c,c1,46,c,c2,5,abc,c1,6,abc,c2,,abc,c1c,c2.Step 3.
There are no linear lower subconcepts in this example.Step 4.
The concept of parallel lower concepts35,c,c1, 46,c,c2 below node concept U, is rolled up into a new concept 3456,c and inserted below node U,. The upper bound node of the new node concept 3456,c and the node concepts 156,a, 256,b which do not contain lower attributes are also U,.
The parallel lower concept5,abc,c1, 6,abc,c2 below node concept 56,ab is rolled up into a new concept 56,abc.Step 5.
After Step 4 is completed, there is no lower concept to be rolled up. There is only one layered attribute in this example, and the algorithm ends.
Figure2 shows the concept lattice CK obtained after the rolling up.Figure 2
Concept latticeCK after rolling up.


## 3.1. Layered Concept Lattice Model and Roll-Up Algorithm Theory

Definition 5.
LetK=G,M,I be a formal context. If every attribute in M can be represented as a subset, which means that(4)M=m1,m2,⋯,ml,mk=mk1,mk2,⋯,mkik,k=1,2,⋯,l,then K=G,M,I is called a layered formal context and mk is called a layered attribute. In a layered formal context K=G,M,I, the lower attributes corresponding to the layered attribute mk are denoted as(5)mk¯=mk,mk1,mk,mk1,⋯,mk,mkik.
Ifik=1, then mk¯=mk, which is actually not a layered attribute.
By using the formal contextK=G,M,I, we can introduce a new layered formal context K¯=G,N,J, where N=∪k=1lmk¯, and the relation J between objects and attributes is defined by gJmk,mki⟺gImk. For the convenience of expression, we also call K the upper formal context, K¯ the lower formal context, CK the upper concept lattice, and CK¯ the lower concept lattice accordingly.
A layered formal contextK=G,M,I is normal if for every layered attribute gImk iff there is a unique iff there is a unique lower attribute mki such that gJmk,mki.
In this paper, we only discuss the normal layered formal context. The following conclusion is obvious.Proposition 2.
Suppose thatK=G,M,I is a layered formal context. Then,(6)βmk,mk1,βmk,mk2,⋯,βmk,mkik,is a partition of βmk.Example 1.
Table1 shows a simplified layered formal context K=G,M,I, where a=“off-road vehicle,” b= “midrange vehicle,” c= “new energy power vehicle” which is a layer attribute, c1= “hybrid power,” and c2= “pure electric power.”
The formal contextK¯ induced by K is shown in Table 2.
When a formal conceptK contains layered attributes, the upper concept lattice CK is closely related to the lower concept lattice CK¯. Hence, we can start with the lower concept lattice CK¯ by rolling up the lower attributes mk¯ of some lower concepts to an upper attribute mk and then building a upper concept; this is easier than building the concept lattice directly from the formal context K.Table 1
Layered formal contextK.
Gabcc1c2110002010030010400015111061101Table 2
Formal contextK¯ induced by K.
Gabc,c1c,c2110002010030010400015111061101Theorem 2.
Suppose thatK=G,M,I is a layered formal context, K¯=G,N,J is the corresponding lower formal context of K, and CK and CK¯ are upper concept lattice and lower concept lattice, respectively. If A1,B1¯,⋯,Aα,Bα¯⊆CK¯ contain the same layered attribute mk¯ and are the nearest subconcepts of a node concept, then(1)
A1,B1¯,⋯,Aα,Bα¯ can be rolled up as a new concept Ak,Bk, where Ak=A1∪⋯∪Aα and Bk=B1¯−mk¯∩⋯∩Bα¯−mk¯∪mk.(2)
The lower conceptsAi,Bi¯i=1,⋯,α are all updated into Ai,Bi¯−mk¯∪mk, respectively.Proof.
It is worth pointing out before proving that a conceptAi,Bi¯ in CK¯ may contain both nonlayered attributes and lower attributes in the form of mk,mkl. In the following, we prove the theorem by four steps.(1)
Prove equationαAk=m∈MgIm,∀g∈Ak=Bk.
Letml∈αAk. Then, for each g∈Ak=A1∪⋯∪Aα, we have gIml. If ml=mk, then obviously ml∈Bk. If ml≠mk, then because Ai,Bi¯i=1,⋯,α are concepts and gIml for each g∈Ai, we have that ml∈Bi¯i=1,⋯,α. So, ml∈B1¯−mk¯∩⋯∩Bik¯−mk¯. This means that ml∈Bk. Hence,(7)αAk=m∈MgIm,∀g∈Ak⊆Bk.
Suppose thatml∈Bk. If ml∈mk, then ml=mk. Hence, mk are the layered attributes of concepts A1,B1¯,⋯,Aik,Bik¯, so αAi=m∈NgJm,∀g∈Ai=Bi¯,i=1,⋯,α. Thus, for each g∈Ak=A1∪⋯∪Aα, there exists i0 such that g∈Ai0, so gJmk,mki0, and gImk. This shows that gImk for each g∈Ak=A1∪⋯∪Aα. This means that mk∈αAk. If ml∈B1¯−mk¯∩⋯∩Bα¯−mk¯, then ml≠mk is not a layered attribute and ml∈Bi¯,i=1,⋯,α. Since Ai,Bi¯,i=1,⋯,α are concepts, we have gIml for each g∈Ak=A1∪⋯∪Aα. Hence, ml∈αAk. Thus, Bk⊆αAk=m∈MgIm,∀g∈Ak.(2)
Prove equationβBk=g∈GgIm,∀m∈Bk=Ak.
At first, we proveβBk⊆Ak. Let us assume g∈βBk; then, for every m∈Bk=B1¯−mk¯∩⋯∩Bα¯−mk¯∪mk, we have gIm. Hence by gImk, we know that there are some i such that gJmk,mki, so gJmk¯, and let i0 be the subscript of biggest concept Ai0,Bi0¯ in these concepts, where the biggest concept means that the concept contains as many object elements as possible and as fewer attribute elements as possible. Thus, from Ai0,Bi0¯ being the biggest concept, we obtain that(8)g∈βBi0¯=g∈GgJmk,mki,∀mk,mki∈Bi0¯=Ai0.
This means thatg∈Ak. Therefore,(9)βBk=g∈GgIm,∀m∈Bk⊆Ak.
Secondly, we proveAk⊆βBk. Let g∈Ak; then, there are some i such that g∈Ai, and let i0 be the subscript of biggest concept Ai0,Bi0¯ in these concepts. Hence, g∈Ai0=βBi0¯, and for each m∈Bi0¯, gJm. This shows that g∈g∈GgIm,∀m∈Bk, and then g∈βBk. Therefore,(10)Ak⊆βBk=g∈GgIm,∀m∈Bk.
From (1) and (2) we know thatAk,Bk is a concept.(3)
Prove that the conceptsAi,Bi¯∈CK¯i=1,⋯,α, which are not rolled up, are updated new concepts Ai,Bi¯−mk¯∪mki=1,⋯,α.
At first, we prove equationαAi=m∈MgIm,∀g∈Ai=Bi¯−mk¯∪mk.
Letml∈αAi; then, for every g∈Ai, we have gIml. If ml=mk, then certainly ml∈Bi¯−mk¯∪mk. If ml≠mk, then from that Ai,Bi¯ is a concept and gImq for every g∈Ai, we have ml∈Bi¯. Hence, ml∈Bi¯−mk¯. This shows that αAi=m∈MgIm,∀g∈Ai⊆Bi¯−mk¯∪mk.
Conversely, letml∈Bi¯−mk¯∪mk. If ml∈mk, namely, ml=mk is a layered attribute, then by Ai,Bi¯ being a concept, we obtain that(11)Bi¯=αAi=mk,mki∈NgJmk,mki,∀g∈Ai.
Hence, bygJmk,mki⟺gImk, we know mq∈αAi. If mq∈Bi¯−mk¯, then mq≠mk and mq∈Bi¯. Since Ai,Bi¯ is a concept, we have gImq for every g∈Ai; hence, mq∈αAi. Therefore,(12)αAi=m∈MgIm,∀g∈Ai⊇Bi¯−mk¯∪mk.
Secondly, we prove the following equation:(13)βBi¯−mk¯∪mk=g∈GgIm,∀m∈Bi¯−mk¯∪mk=Ai.
Letg∈βBi¯−mk¯∪mk; then, gIm for every m∈Bi¯−mk¯∪mk. Since Ai,Bi¯ is a concept, we know βBi¯=g∈GgJm,∀m∈Bi¯=Ai. Hence, by gJmk,mki⟺gImk, we have(14)βBi¯−mk¯∪mk=g∈GgIm,∀m∈Bi¯−mk¯∪mk⊆Ai.
Conversely, letg∈Ai. Then, since Ai,Bi¯ is a concept, we have βBi¯=g∈GgJm,∀m∈Bi¯=Ai. If m∈Bi¯ is not a layered attribute, then the relation between g and m does not change before and after rolling up. If m∈Bi¯ is a layered attribute and its form is mk,mkj, then by gJmk,mki⟺gImk, we have gIm for each m∈Bi¯−mk¯∪mk. Therefore,(15)Ai⊆βBi¯−mk¯∪mk=g∈GgIm,∀m∈Bi¯−mk¯∪mk.(4)
Prove that the partial order amongAi,Bi¯−mk¯∪mki=1,⋯,α is the same Ai,Bi¯i=1,⋯,α.
By the structure ofAk,Bk, for i=1,⋯,α, we have(16)Ai,Bi¯−mk¯∪mk≤Ak,Bk.
If two conceptsAi,Bi¯ and Aj,Bj¯ are in CK¯ with order Ai,Bi¯≤Aj,Bj¯, then the following also holds:(17)Ai,Bi¯−mk¯∪mk≤Aj,Bj¯−mk¯∪mk.


## 3.2. The Description and Analysis of Roll-Up Algorithm

In order to simplify the presentation below, we introduce the following two terms: parallel lower subconcepts and linear lower subconcepts. LetA1,B1¯,⋯,Aα,Bα¯ be the lower subconcepts under node concept A,B. If there is no partial order relation between each other, then A1,B1¯,⋯,Aα,Bα¯ is called parallel lower subconcepts. If there is linear partial order relation among them, then A1,B1¯,A1,B1¯,⋯,Aα,Bα¯ is called linear lower subconcepts.Because this paper only discusses the normal layered formal context and in a normal layered formal context an object will not have two lower attributes of one layer attribute, a concept will not contain more than two lower attributes except the empty concept (object set is empty set). Hence, every concept in the linear lower subconcepts only contains the same lower attribute, and different attributes among different subconcepts are nonlayer attributes. On the basis of this analysis, we can present a roll-up building algorithm of building a concept lattice based on attribute fusion. The process of rolling up fromCK¯ to CK involves the fusion of attributes, and the partial order in the concept lattice is defined according to the negative inclusion of the attribute subset. Thus, the rolling up is carried out from top to bottom, that is, start with the concept of having fewer attributes. The method of rolling up is to roll up the lower concept of node concept A,B in the lower concept lattice CK¯ in a linear or parallel lower subconcepts, insert the new concept obtained from rolling up into the bottom of node A,B, and update the node concept A,B and its related node concept accordingly (given in Algorithm 1).Algorithm 1: Roll-up building algorithm of layered concept lattice.
Input: a lower concept lattice CK¯ of layered formal context K¯ induced by formal context K.Output: an upper concept lattice.Step 1. For k=1,2,…,l, select all lower concepts containing layered attribute mk¯ and form lower concept set CkK¯ to be rolled up.Step 2. The concepts in CkK¯ are sorted in ascending order according to the number of lower attributes contained within it. When the number of lower attributes is the same, the concepts containing fewer nonlower attributes are ranked ahead.Step 3. From top to bottom, roll up the lower concepts in CK¯. For the linear lower subconcepts under node concept A,B in CkK¯, the rolling-up method is as follows: combine the linear lower concepts A1,B1¯,…,Aβ,Bβ¯ containing mk¯ into a new concept Ak,Bk, where Ak=A1∩⋯∩Aβ, Bk=B1¯−mk¯∪⋯∪Bβ¯−mk¯∪mk, and insert Ak,Bk to node A,B below. If node concept A,B contains subconcepts with nonlower attributes, then node A,B is updated to be the common upper bound of Ak,Bk and other concepts (excluding lower attributes in mk¯) under node A,B.Step 4. For the parallel lower subconcepts and lower subconcepts under node concept A,B in CkK¯, the rolling-up method is as follows: combine the parallel lower concepts A1,B1¯,…,Aβ,Bβ¯ containing mk¯ into a new concept Ak,Bk, where Ak=A1∪⋯∪Aα, Bk=B1¯−mk¯∩⋯∩Bα¯−mk¯∪mk, and insert Ak,Bk to node A,B below. If node concept A,B contains subconcepts with nonlower attributes, then node A,B is updated to be the common upper bound of Ak,Bk and other concepts (excluding lower attributes in mk¯) under node A,B.Step 5. If the node concept A,B has both the parallel lower subconcepts and the linear lower subconcepts, then linear lower subconcepts are fused firstly; the method of fusion is to replace the linear lower subconcepts with the minimum concept in these linear lower subconcepts and then roll up the parallel lower subconcepts by Step 4 secondly.Step 6. Update the subconcept Cj,Dj¯, which is not rolled up from Step 3 to Step 5 but it contains the lower attribute of mk¯, to a new concept Cj,Dj¯−mk¯∪mk.Step 7. Repeat from Step 3 to Step 6 until the concept in CK¯ does not contain the lower attribute of mk¯ (namely, CkK¯ is an empty set).Step 8. Repeat from Step 1 to Step 7 until CK¯ does not contain any layered attribute. Algorithm is completed.The time complexity of Algorithm1 is related to the number of layered attributes and the number of lower attributes in the layered context. In the following, we assume that the number of layered attributes in K is l, the number of node in CK¯ is s, and the maximum number of lower attributes of all layered attributes is r. The computing number at Step 1 is r, and its time complexity is Or. The time complexity at Step 2 is Orlog2r; it is equal to the time complexity of r concept sorting. At Step 3, in the worst case, the number of linear lower subconcepts under a node in CkK¯ is l, and the number of computing in rolling up is l, but the total number of computing of all nodes in rolling up is not more than s. Hence, the time complexity at Step 3 is Os. The time complexity of Step 4 and Step 5 is the same as that of Step 3, which is also Os. The computing number at Step 6 does not exceed s−r, so the time complexity at Step 6 is Os−r. The time complexity analysis at Step 7 has been included from Step 3 to Step 6. Therefore, the time complexity of Algorithm 1 is Or+rlog2r+s+s−rl=Ol2s+rlog2r.The following example illustrates the application of the roll-up building algorithm in building concept lattice.Example 2.
Consider the layered formal contextK as shown in example 1; the induced formal context by K is shown in Figure 1.Figure 1
Concept latticeCK¯ of formal context K¯.Steps 1 and 2.
The concepts containing lower attributes inCK¯ are arranged in ascending order according to the number of attributes of concepts, CkK¯=35,c,c1,46,c,c2,5,abc,c1,6,abc,c2,,abc,c1c,c2.Step 3.
There are no linear lower subconcepts in this example.Step 4.
The concept of parallel lower concepts35,c,c1, 46,c,c2 below node concept U, is rolled up into a new concept 3456,c and inserted below node U,. The upper bound node of the new node concept 3456,c and the node concepts 156,a, 256,b which do not contain lower attributes are also U,.
The parallel lower concept5,abc,c1, 6,abc,c2 below node concept 56,ab is rolled up into a new concept 56,abc.Step 5.
After Step 4 is completed, there is no lower concept to be rolled up. There is only one layered attribute in this example, and the algorithm ends.
Figure2 shows the concept lattice CK obtained after the rolling up.Figure 2
Concept latticeCK after rolling up.


## 4. Drill-Down Algorithm to Build the Lower Concept Lattice

In this section, a drill-down algorithm to build lower layered concept latticeCK¯ based on the upper concept lattice CK is presented.


### 4.1. Drill-Down Algorithm Theory

Definition 6.
LetK=G,M,I be a layered formal context and b∈M. Then, βb,αβb is called an attribute concept.Proposition 3.
βb,αβb is the largest concept containing attribute b.Proof.
Obviously,βb,αβb is a concept containing attribute b. If A,B is another concept containing attribute b, then by b⊆B and Proposition 1, we have βb⊇βB=A. Hence, A,B≤βb,αβb.Theorem 3.
LetK=G,M,I be a layered formal context and K¯=G,N,J be the lower formal context. Suppose that mk is a layered attribute; then,(18)mk¯=mk,mk1,mk,mk2,⋯,mk,mkik,is the lower attribute corresponding to mk, and βmk,mkj,αβmk,mkj are attribute concepts corresponding to the lower attributes mk,mkjj=1,2,⋯,ik. A,B∈CK is a concept and for every j∈1,2,⋯,ik, there is no child X,Y of A,B with A∩βmk,mkj⊆X; then, for every A∩βmk,mkj, j∈1,2,⋯,ik,(1)
IfA∩βmk,mkj=A, then A,B is updated to A,B−mk∪mk,mkj(2)
IfA∩βmk,mkj≠A, then a new concept A∩βmk,mkj,B−mk∪mk,mkj is added as a child of A,BProof.
(1) is a special case of (2), so we only prove (2).
Firstly, we prove that ifA∩βmk,mkj≠φ, then A∩βmk,mkj,B−mk∪mk,mkj are concepts j=1,2,⋯,ik; hence, we need to prove two equations:(19)αA∩βmk,mkj=m∈NgJm,∀g∈A∩βmk,mkj=B−mk∪mk,mkj,(20)βB−mk∪mk,mkj=g∈GgJm,∀m∈B−mk∪mk,mkj=A∩βmk,mkj.
SinceA,B is a concept, we know αA=B. By Proposition 1, we have that(21)αA∩βmk,mkj⊇αA∪αβmk,mkj=B∪αβmk,mkj⊇B−mk∪αβmk,mkj.
Conversely, letmq∈αA∩βmk,mkj. Then, for each g∈A∩βmk,mkj, we have gJmq. In the following, we discuss it in two cases:(i)
mq∈mk¯: if mq≠mk,mkj, then there is i≠j such that mq=mk,mki. By Proposition 2βmk,mk1,⋯,βmk,mkik is a partition of βmk, we know that for every g∈βmk,mkj, g and mk,mki have no relation J. This contradicts gJmq for each g∈A∩βmk,mkj. Thus, mq∈mk,mkj.(ii)
mq∉mk¯: if mq∉B−mk, then obviously mq≠mk, and hence mq∉B. Because A,B is a concept containing attribute mk, there exists g∈A such that g and mq have no relation J. The set of all elements of A that has no relation J with mq is denoted as A0. If A0∩βmk,mkj is an empty set, then for any g∈βmk,mkj and g∈A, g and mq have no relation J. This contradicts gJmq for each g∈A∩βmk,mkj. Hence, there is g0∈A0∩βmk,mkj such that g0 and mq have no relation J. This also contradicts gJmq for each g∈A∩βmk,mkj. Therefore, if mq∉mk¯, then mq∈B−mk.
This proves that(22)αA∩βmk,mkj=B−mk∪mk,mkj.
SinceA,B is a concept, we have βB=A. By Proposition 1 we obtain(23)βB−mk∪mk,mkj=βB−mk∩βmk,mkj⊇βB∩βmk,mkj=A∩βmk,mkj.
Conversely, let(24)g∈βB−mk∪mk,mkj=βB−mk∩βmk,mkj.
Fromg∈βmk,mkj, we know gJmk,mkj. By gImk⟺gJmk,mkj, we have gImk. From g∈βB−mk, we know gIm for each m∈B−mk. Hence, gIm for every m∈B. This shows that g∈βB=A, and hence g∈A∩βmk,mkj. Therefore,(25)βB−mk∪mk,mkj⊆A∩βmk,mkj.
This proves that(26)βB−mk∪mk,mkj=A∩βmk,mkj.
Next, we prove that the partial order among conceptsAi,Bi¯i=1,⋯,α is the same as the partial order among Ai,Bi¯−mk¯∪mki=1,⋯,α.
At first, fori=1,⋯,α, by the construction of Ak,Bk, we have(27)Ai,Bi¯−mk¯∪mk≤Ak,Bk.
Secondly, ifAi,Bi¯≤Aj,Bj¯ in CK¯, then we also have(28)Ai,Bi¯−mk¯∪mk≤Aj,Bj¯−mk¯∪mk.


### 4.2. The Description and Analysis of Drill-Down Algorithm

According to Theorem3, started with the upper concept lattice CK, inserted some new concepts, modified some concepts and deleted some concepts, we can obtained lower concept lattice CK¯. In the following, we propose a drill-down algorithm to build lower concept lattice based on attribute decomposition (given in Algorithm 2).Algorithm 2: Drill-down algorithm to build the lower concept lattice.
Input: a concept lattice CK of formal context K containing layered attributes.Output: the lower concept lattice CK¯.Step 1. For each lower attribute of a layered attribute mk, k∈1,2,…,l: mk¯=mk,mk1,mk,mk2,…,mk,mkik, build all attribute concepts: A∩βmk,mkj,B−mk∪αβmk,mkjj=1,2,…,ik.Step 2. The concept A,B containing layered attribute mk is updated to some new concepts A∩βmk,mkj,B−mk∪αβmk,mkj, which contain lower attributes mk,mkj, j=1,…,ik, respectively, where A∩βmk,mkj is not an empty set. The concepts that do not contain the layered attribute mk remain the same.Step 3. If some concepts with lower attributes obtained from Step 2 can be combined, then these concepts are combined and a concept and is inserted above them.Step 4. The node concepts that are connected to A,B and are also not updated in CK are connected to the updated node concepts.Step 5. For each layered attribute mkk=1,…,l, repeat from Step 1 to Step 4 above.Step 6. End of the algorithm.The time complexity of Algorithm2 is analyzed below. In the following, we assume that the number of layered attributes in K is l, the number of node concepts in CK is s, and the maximum number of lower attributes is r. The Bordat algorithm building concept lattice of formal context G,M,I is improved by Chen in [12], and the time complexity of the improved algorithm is less than OGM2. Then, in the worst case, the time complexity of Step 1 is OGr2. The time complexity of Step 2 is Osr. The time complexity of Step 3 is Or2. Therefore, the time complexity of algorithm 2 is OGr2+sr+r2l=OlG+1r2+sr.The following example illustrates the application of the drill-down building algorithm in building the concept lattice.Example 3.
A layered formal contextK=G,M,I is shown in Table 3, and the concept lattice of K is shown in Figure 3. The lower formal context K¯=G,N,J induced by K is shown in Table 4.
The concept lattice ofK¯ is shown in Figure 4.Table 3
Layered formal contextK.
Gabcc1c2c3110100200100301010401001510100610100Figure 3
Concept latticeCK of context K.Table 4
Formal contextK¯ induced by K.
Gabc,c1c,c2c,c3110100200100301010401001510100610100Figure 4
Concept latticeCK¯ of formal context K¯.Step 1.
Layered attributec has three lower attributes, and the corresponding lower attribute concepts are 1256,c,c1, 3,bc,c2, 4,bc,c3.Step 2.
There are four concepts inCK that contain the layered attribute c. According to Step 2 in Algorithm 2, U,c is updated into three new concepts 1256,c,c1, 3,bc,c2, 4,bc,c3; 34,bc is updated into two new concepts 3,bc,c2, 4,bc,c3; 156,ac is updated into a new concept 156,ac,c1.Step 3.
Two lower attribute concepts3,bc,c2, 4,bc,c3 can be combined into a new concept 34,b and inserted above 3,bc,c2, 4,bc,c3.Step 4.
There is only one layered attribute, and the algorithm ends.
The purpose of the roll-up building algorithm is to build the upper concept latticeCK on the basis of lower concept lattice CK¯, and the drill-down building algorithm is to build the lower concept lattice CK¯ on the basis of the upper concept lattice CK. From the point of view of granular computing, roll-up building algorithm helps us recognize concepts from fine-grained to coarse-grained, while drill-down building algorithm help us recognize concepts from coarse-grained to fine-grained. Therefore, from the human cognitive thinking process, roll-up and drill-own building algorithms are reversed, and then there is a question to be discussed: whether there is reducibility between these two reverse algorithms.
Now, we consider example3.Example 4.
In the layered formal context of example3, by using the drill-down algorithm, we obtain the lower concept lattice CK¯ as shown in Figure 4. Now, we run the roll-up building algorithm on CK¯.Steps 1 and 2.
The concepts containing lower attributes inCK¯ are arranged in ascending order according to the number of attributes contained in the concepts as follows: C′K¯=1256,c,c1,3,bc,c2,4,bc,c3,156,ac,c1,,abc,c1c,c2c,c3.Step 3.
The linear lower subconcepts1256,c,c1, 156,ac,c1 below node concept U, are rolled up into a new concept 156,ac, and the node concept U, is replaced by U,c, which are the parent concept (upper bound node) of the new concept 156,ac and the concept 34,b that does not contain lower attributes.Step 4.
The parallel lower subconcepts3,bc,c2, 4,bc,c3 below node concept 34,b are rolled up into a new concept 34,bc. There are no other concepts below 34,b that do not contain lower attributes c,c2, c,c3, and then 34,b is updated into 34,bc.Step 5.
The lower attributesc,c1, c,c2, c,c3 in the minimum node concept (empty concept) ,abc,c1c,c2c,c3 are integrated, and then we obtain the minimum concept ,abc.Step 6.
There is only one layered attribute, and the algorithm ends.
AfterCK¯ is rolled up, the concept lattice is exactly the same as shown in Figure 3. This also shows that the rolling-up and drilling-down algorithms for layered concept lattice have the reducibility.


## 4.1. Drill-Down Algorithm Theory

Definition 6.
LetK=G,M,I be a layered formal context and b∈M. Then, βb,αβb is called an attribute concept.Proposition 3.
βb,αβb is the largest concept containing attribute b.Proof.
Obviously,βb,αβb is a concept containing attribute b. If A,B is another concept containing attribute b, then by b⊆B and Proposition 1, we have βb⊇βB=A. Hence, A,B≤βb,αβb.Theorem 3.
LetK=G,M,I be a layered formal context and K¯=G,N,J be the lower formal context. Suppose that mk is a layered attribute; then,(18)mk¯=mk,mk1,mk,mk2,⋯,mk,mkik,is the lower attribute corresponding to mk, and βmk,mkj,αβmk,mkj are attribute concepts corresponding to the lower attributes mk,mkjj=1,2,⋯,ik. A,B∈CK is a concept and for every j∈1,2,⋯,ik, there is no child X,Y of A,B with A∩βmk,mkj⊆X; then, for every A∩βmk,mkj, j∈1,2,⋯,ik,(1)
IfA∩βmk,mkj=A, then A,B is updated to A,B−mk∪mk,mkj(2)
IfA∩βmk,mkj≠A, then a new concept A∩βmk,mkj,B−mk∪mk,mkj is added as a child of A,BProof.
(1) is a special case of (2), so we only prove (2).
Firstly, we prove that ifA∩βmk,mkj≠φ, then A∩βmk,mkj,B−mk∪mk,mkj are concepts j=1,2,⋯,ik; hence, we need to prove two equations:(19)αA∩βmk,mkj=m∈NgJm,∀g∈A∩βmk,mkj=B−mk∪mk,mkj,(20)βB−mk∪mk,mkj=g∈GgJm,∀m∈B−mk∪mk,mkj=A∩βmk,mkj.
SinceA,B is a concept, we know αA=B. By Proposition 1, we have that(21)αA∩βmk,mkj⊇αA∪αβmk,mkj=B∪αβmk,mkj⊇B−mk∪αβmk,mkj.
Conversely, letmq∈αA∩βmk,mkj. Then, for each g∈A∩βmk,mkj, we have gJmq. In the following, we discuss it in two cases:(i)
mq∈mk¯: if mq≠mk,mkj, then there is i≠j such that mq=mk,mki. By Proposition 2βmk,mk1,⋯,βmk,mkik is a partition of βmk, we know that for every g∈βmk,mkj, g and mk,mki have no relation J. This contradicts gJmq for each g∈A∩βmk,mkj. Thus, mq∈mk,mkj.(ii)
mq∉mk¯: if mq∉B−mk, then obviously mq≠mk, and hence mq∉B. Because A,B is a concept containing attribute mk, there exists g∈A such that g and mq have no relation J. The set of all elements of A that has no relation J with mq is denoted as A0. If A0∩βmk,mkj is an empty set, then for any g∈βmk,mkj and g∈A, g and mq have no relation J. This contradicts gJmq for each g∈A∩βmk,mkj. Hence, there is g0∈A0∩βmk,mkj such that g0 and mq have no relation J. This also contradicts gJmq for each g∈A∩βmk,mkj. Therefore, if mq∉mk¯, then mq∈B−mk.
This proves that(22)αA∩βmk,mkj=B−mk∪mk,mkj.
SinceA,B is a concept, we have βB=A. By Proposition 1 we obtain(23)βB−mk∪mk,mkj=βB−mk∩βmk,mkj⊇βB∩βmk,mkj=A∩βmk,mkj.
Conversely, let(24)g∈βB−mk∪mk,mkj=βB−mk∩βmk,mkj.
Fromg∈βmk,mkj, we know gJmk,mkj. By gImk⟺gJmk,mkj, we have gImk. From g∈βB−mk, we know gIm for each m∈B−mk. Hence, gIm for every m∈B. This shows that g∈βB=A, and hence g∈A∩βmk,mkj. Therefore,(25)βB−mk∪mk,mkj⊆A∩βmk,mkj.
This proves that(26)βB−mk∪mk,mkj=A∩βmk,mkj.
Next, we prove that the partial order among conceptsAi,Bi¯i=1,⋯,α is the same as the partial order among Ai,Bi¯−mk¯∪mki=1,⋯,α.
At first, fori=1,⋯,α, by the construction of Ak,Bk, we have(27)Ai,Bi¯−mk¯∪mk≤Ak,Bk.
Secondly, ifAi,Bi¯≤Aj,Bj¯ in CK¯, then we also have(28)Ai,Bi¯−mk¯∪mk≤Aj,Bj¯−mk¯∪mk.


## 4.2. The Description and Analysis of Drill-Down Algorithm

According to Theorem3, started with the upper concept lattice CK, inserted some new concepts, modified some concepts and deleted some concepts, we can obtained lower concept lattice CK¯. In the following, we propose a drill-down algorithm to build lower concept lattice based on attribute decomposition (given in Algorithm 2).Algorithm 2: Drill-down algorithm to build the lower concept lattice.
Input: a concept lattice CK of formal context K containing layered attributes.Output: the lower concept lattice CK¯.Step 1. For each lower attribute of a layered attribute mk, k∈1,2,…,l: mk¯=mk,mk1,mk,mk2,…,mk,mkik, build all attribute concepts: A∩βmk,mkj,B−mk∪αβmk,mkjj=1,2,…,ik.Step 2. The concept A,B containing layered attribute mk is updated to some new concepts A∩βmk,mkj,B−mk∪αβmk,mkj, which contain lower attributes mk,mkj, j=1,…,ik, respectively, where A∩βmk,mkj is not an empty set. The concepts that do not contain the layered attribute mk remain the same.Step 3. If some concepts with lower attributes obtained from Step 2 can be combined, then these concepts are combined and a concept and is inserted above them.Step 4. The node concepts that are connected to A,B and are also not updated in CK are connected to the updated node concepts.Step 5. For each layered attribute mkk=1,…,l, repeat from Step 1 to Step 4 above.Step 6. End of the algorithm.The time complexity of Algorithm2 is analyzed below. In the following, we assume that the number of layered attributes in K is l, the number of node concepts in CK is s, and the maximum number of lower attributes is r. The Bordat algorithm building concept lattice of formal context G,M,I is improved by Chen in [12], and the time complexity of the improved algorithm is less than OGM2. Then, in the worst case, the time complexity of Step 1 is OGr2. The time complexity of Step 2 is Osr. The time complexity of Step 3 is Or2. Therefore, the time complexity of algorithm 2 is OGr2+sr+r2l=OlG+1r2+sr.The following example illustrates the application of the drill-down building algorithm in building the concept lattice.Example 3.
A layered formal contextK=G,M,I is shown in Table 3, and the concept lattice of K is shown in Figure 3. The lower formal context K¯=G,N,J induced by K is shown in Table 4.
The concept lattice ofK¯ is shown in Figure 4.Table 3
Layered formal contextK.
Gabcc1c2c3110100200100301010401001510100610100Figure 3
Concept latticeCK of context K.Table 4
Formal contextK¯ induced by K.
Gabc,c1c,c2c,c3110100200100301010401001510100610100Figure 4
Concept latticeCK¯ of formal context K¯.Step 1.
Layered attributec has three lower attributes, and the corresponding lower attribute concepts are 1256,c,c1, 3,bc,c2, 4,bc,c3.Step 2.
There are four concepts inCK that contain the layered attribute c. According to Step 2 in Algorithm 2, U,c is updated into three new concepts 1256,c,c1, 3,bc,c2, 4,bc,c3; 34,bc is updated into two new concepts 3,bc,c2, 4,bc,c3; 156,ac is updated into a new concept 156,ac,c1.Step 3.
Two lower attribute concepts3,bc,c2, 4,bc,c3 can be combined into a new concept 34,b and inserted above 3,bc,c2, 4,bc,c3.Step 4.
There is only one layered attribute, and the algorithm ends.
The purpose of the roll-up building algorithm is to build the upper concept latticeCK on the basis of lower concept lattice CK¯, and the drill-down building algorithm is to build the lower concept lattice CK¯ on the basis of the upper concept lattice CK. From the point of view of granular computing, roll-up building algorithm helps us recognize concepts from fine-grained to coarse-grained, while drill-down building algorithm help us recognize concepts from coarse-grained to fine-grained. Therefore, from the human cognitive thinking process, roll-up and drill-own building algorithms are reversed, and then there is a question to be discussed: whether there is reducibility between these two reverse algorithms.
Now, we consider example3.Example 4.
In the layered formal context of example3, by using the drill-down algorithm, we obtain the lower concept lattice CK¯ as shown in Figure 4. Now, we run the roll-up building algorithm on CK¯.Steps 1 and 2.
The concepts containing lower attributes inCK¯ are arranged in ascending order according to the number of attributes contained in the concepts as follows: C′K¯=1256,c,c1,3,bc,c2,4,bc,c3,156,ac,c1,,abc,c1c,c2c,c3.Step 3.
The linear lower subconcepts1256,c,c1, 156,ac,c1 below node concept U, are rolled up into a new concept 156,ac, and the node concept U, is replaced by U,c, which are the parent concept (upper bound node) of the new concept 156,ac and the concept 34,b that does not contain lower attributes.Step 4.
The parallel lower subconcepts3,bc,c2, 4,bc,c3 below node concept 34,b are rolled up into a new concept 34,bc. There are no other concepts below 34,b that do not contain lower attributes c,c2, c,c3, and then 34,b is updated into 34,bc.Step 5.
The lower attributesc,c1, c,c2, c,c3 in the minimum node concept (empty concept) ,abc,c1c,c2c,c3 are integrated, and then we obtain the minimum concept ,abc.Step 6.
There is only one layered attribute, and the algorithm ends.
AfterCK¯ is rolled up, the concept lattice is exactly the same as shown in Figure 3. This also shows that the rolling-up and drilling-down algorithms for layered concept lattice have the reducibility.


## 5. Experimentation

The previous example has shown that the roll-up building algorithm and the drill-down building algorithm proposed in this paper are effective. To further show the utility of Algorithms1 and 2, we implement two algorithms by using MTLAB program language. The computing environment is a PC (Pentium Win7 × 64, Intel (R) 3.4 GHz, RAM 4 GB). The validity verification about the roll-up building algorithm is mainly to investigate the improvement on time consumption by comparing building the concept lattice CK from the lower concept lattice CK¯ with building the concept lattice CK directly from the formal context K.In the experiment, the number of objects is set to 15000, and the total number of attributes is set to 60 (including lower attributes). The number of lower attributes of each layered attribute is set to 5, the number of layered attributes is 2, 4, 6, 8, and 10, respectively, and the total number of lower attributes correspondingly is 10, 20, 30, 40, and 50, respectively, so the number of upper attributes in the lower form contextK¯ is 52, 44, 36, 28, and 20, respectively. The test data with medium strength filling ratio I/GM 20% are randomly generated. If a layered attribute has no filling value, then its corresponding lower attribute values are all 0. If a layered attribute has filling value, then select randomly a lower attribute to be assigned a value of 1. The improved Bordat algorithm proposed in [12] was adopted for building context lattice directly. The comparison on time consumption building directly the concept lattice from the dataset with building the concept lattice by using roll-up building algorithm is shown in Figure 5, and the time saved by using the roll-up building algorithm to build the concept lattice is shown in Figure 6.Figure 5
Time comparison between building concept lattice by using roll-up algorithm and building concept lattice directly.Figure 6
Saving time of roll-up building lattice.It can be seen from Figures5 and 6 that using the roll-up building algorithm to build concept lattice CK on the basis of CK¯ takes less time than building directly the concept lattice CK from the formal context K. When the number of layered attributes is relatively small, the effect of time saving by using roll-up building algorithm is very obvious, and as the number of layered attributes increases, the time saving decreases.The validity verification about the drill-down building algorithm is mainly to investigate the improvement on time consumption by comparing building the lower concept latticeCK¯ from the upper concept lattice CK with building the concept lattice CK¯ directly from the formal context K¯.In the experiment, the number of objects is set to 15000, and the total number of attributes is set to 60 (including lower attributes). The number of nonlayered attributes is set to 10, the number of layered attributes is set to 2, 4, 6, 8, and 10, respectively, and the number of lower attributes of each layered attribute is set to 5, so the total number of attributes in the lower formal contextK¯ is 20, 30, 40, 50, and 60, respectively. The experimental environment and dataset are the same as the roll-up building algorithm experiment. The comparison on time consumption building directly the concept lattice from the dataset with building the concept lattice by using drill-down building algorithm is shown in Figure 7, and the time saved by using the drill-down building algorithm to build the concept lattice is shown in Figure 8.Figure 7
Time comparison between building concept lattice by using drill-down algorithm and building concept lattice directly.Figure 8
Saving time of drill-down building lattice.It can be seen from Figures7 and 8 that using the drill-down building algorithm to build concept lattice CK¯ on the basis of CK takes less time than building directly the concept lattice CK¯ from the formal context K¯. When the number of layered attributes is relatively small, the effect of time saving by using drill-down building algorithm is very obvious, and as the number of layered attributes increases, the time saving decreases.


## 6. Conclusion

This paper applies the idea of granular computing to build concept lattice in a formal context with complex structure attribute data. When some attributes in a formal context are made up of some subattributes, a layered concept lattice model is established, and the relation between the upper concept lattice based on the original formal context and the lower concept lattice based on the lower formal context is discussed. A roll-up building algorithm that builds the upper concept lattice from the lower concept lattice and a drill-down building algorithm that builds the lower concept lattice from the upper concept lattice are proposed; the time complexity of two algorithms is analyzed. The application of the algorithm and the reducibility of the roll-up building algorithm and the drill-down building algorithm are illustrated by some practical examples. Practical examples and experiments show that the layered concept lattice model can be used to model complex structural data, and the roll-up building algorithm and the drill-down building algorithm proposed in this paper are effective. In future work, we will discuss in detail the reducibility between the roll-up building algorithm and the drill-down building algorithm, the roll-up building algorithm and the drill-down building algorithm for the layered concept lattice in a not-normal layered context. This paper does not discuss the relationship between layered attributes from a quantitative point of view. It also may be another possible research direction to use the analytic hierarchy process to discuss the layered concepts in layered formal context from a quantitative point of view.



---

*Source: 5784209-2020-06-11.xml*