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

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.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 triplet $K=\left(G,M,I\right)$, where $I\subseteq G\times M$ is a binary relation between $G$ and $M$. The elements in $G$ and $M$ are called objects and attributes, respectively. $\left(g,m\right)\in I$ or $gIm$ indicates the object $g$ has the attribute $m$.

Definition 2.

Let $K=\left(G,M,I\right)$ be a formal context. For a set $A\subseteq G$ of objects, we define a set of attributes common to all objects in $A$ as$$\begin{array}{}\text{(1)}& \alpha \left(A\right)=\left\{\left.m\in M\right|gIm,\forall g\in A\right\}.\end{array}$$

Correspondingly, for a set $B\subseteq M$ of attributes, we define the set of objects that have all attributes in $B$ as$$\begin{array}{}\text{(2)}& \beta \left(B\right)=\left\{\left.g\in G\right|gIm,\forall m\in B\right\}.\end{array}$$

In brief, we also denote $\alpha \left(\left\{a\right\}\right),\beta \left(\left\{m\right\}\right)$ as $\alpha \left(a\right),\beta \left(m\right)$.

Proposition 1 (see [10]).

For $A,A_1,A_2\subseteq G$ and $B,B_1,B_2\subseteq M$,

(1)

$A_1\subseteq A_2⟹\alpha \left(A_2\right)\subseteq \alpha \left(A_1\right),B_1\subseteq B_2⟹\beta \left(B_2\right)\subseteq \beta \left(B_1\right)$

(2)

$A\subseteq \beta \left(\alpha \left(A\right)\right),B\subseteq \alpha \left(\beta \left(B\right)\right)$

(3)

$A\subseteq \beta \left(B\right)⟺B\subseteq \alpha \left(A\right)$

(4)

$\alpha \left(A_1\cup A_2\right)=\alpha \left(A_1\right)\cap \alpha \left(A_2\right)$, $\beta \left(B_1\cup B_2\right)=\beta \left(B_1\right)\cap \beta \left(B_2\right)$

(5)

$\alpha \left(A_1\cap A_2\right)\supseteq \alpha \left(A_1\right)\cup \alpha \left(A_2\right)$, $\beta \left(B_1\cap B_2\right)\supseteq \beta \left(B_1\right)\cup \beta \left(B_2\right)$

(6)

$\left(\beta \left(\alpha \left(A\right)\right),\alpha \left(A\right)\right)$ and $\left(\beta \left(B\right),\alpha \left(\beta \left(B\right)\right)\right)$ are concepts

Definition 3.

Let $K=\left(G,M,I\right)$ be a formal context. For $A\subseteq G$ and $B\subseteq M$, if $\alpha \left(A\right)=B$ and $\beta \left(B\right)=A$, then a pair $\left(A,B\right)$ is called a formal concept of formal context $K$, and $A$ and $B$ are called the extent and the intent of $\left(A,B\right)$, respectively. The set of all concepts of formal context $K$ is denoted as $C\left(K\right)$.

Definition 4.

Let $\left(A_1,B_1\right)$ and $\left(A_2,B_2\right)$ be two formal concepts of a given formal context $K$. $\left(A_1,B_1\right)$ is called a subconcept of $\left(A_2,B_2\right)$ if $A_1\subseteq A_2$(or equivalently $B_1\supseteq B_2$), which can be denoted by $\left(A_1,B_1\right)\le \left(A_2,B_2\right)$.

Obviously, the subconcept relation $\le$ is a partial order on $C\left(K\right)$. Since $\le$ is a partial order, we can adopt the definition of neighboring nodes of order theory here. Let $C_1$ and $C_2$ be two concepts of a given formal context $K$. We say $C_1$ is a lower neighbor (or a child) of $C_2$ and $C_2$ is an upper neighbor (or a parent) of $C_1$, if $C_1\le C_2$ and there is no other concept $C_3$ with $C_3\ne C_1$, $C_3\ne C_2$, and $C_1\le C_3\le C_2$.

Theorem 1 (see [10]).

The set $C\left(K\right)$ of all formal concepts of context $K$ together with partial order $\le$ makes a complete lattice, which is called a concept lattice of $K$ and is denoted as $\left(C\left(K\right),\le \right)$; the upper and lower bound operations are$$\begin{array}{c}\text{(3)}& {\wedge }_{t\in T}\left(A_t,B_t\right)=\left({\cap }_{t\in T}{A}_t,\alpha \left(\beta \left({\cup }_{t\in T}{B}_t\right)\right)\right),{\vee }_{t\in T}\left(A_t,B_t\right)=\left(\beta \left(\alpha \left({\cup }_{t\in T}{A}_t\right)\right),{\cap }_{t\in T}{B}_t\right).\end{array}$$

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.

Let $K=\left(G,M,I\right)$ be a formal context. If every attribute in $M$ can be represented as a subset, which means that$$\begin{array}{c}\text{(4)}& M=\left\{m_1,m_2,\cdots ,m_l\right\},m_k=\left\{m_{k1},m_{k2},\cdots ,m_{k{i}_k}\right\},\hspace{1em}k=\mathrm{1,2},\cdots ,l,\end{array}$$then $K=\left(G,M,I\right)$ is called a layered formal context and $m_k$ is called a layered attribute. In a layered formal context $K=\left(G,M,I\right)$, the lower attributes corresponding to the layered attribute $m_k$ are denoted as$$\begin{array}{}\text{(5)}& \overline{m_k}=\left\{\left(m_k,m_{k1}\right),\left(m_k,m_{k1}\right),\cdots ,\left(m_k,m_{k{i}_k}\right)\right\}.\end{array}$$

If $i_k=1$, then $\overline{m_k}=m_k$, which is actually not a layered attribute.

By using the formal context $K=\left(G,M,I\right)$, we can introduce a new layered formal context $\overline{K}=\left(G,N,J\right)$, where $N={\displaystyle {\cup }_{k=1}^l\overline{m_k}}$, and the relation $J$ between objects and attributes is defined by $gJ\left(m_k,m_{ki}\right)⟺gI{m}_k$. For the convenience of expression, we also call $K$ the upper formal context, $\overline{K}$ the lower formal context, $C\left(K\right)$ the upper concept lattice, and $C\left(\overline{K}\right)$ the lower concept lattice accordingly.

A layered formal context $K=\left(G,M,I\right)$ is normal if for every layered attribute $gI{m}_k$ iff there is a unique iff there is a unique lower attribute $m_{ki}$ such that $gJ\left(m_k,m_{ki}\right)$.

In this paper, we only discuss the normal layered formal context. The following conclusion is obvious.

Proposition 2.

Suppose that $K=\left(G,M,I\right)$ is a layered formal context. Then,$$\begin{array}{}\text{(6)}& \left\{\beta \left(m_k,m_{k1}\right),\beta \left(m_k,m_{k2}\right),\cdots ,\beta \left(m_k,m_{k{i}_k}\right)\right\},\end{array}$$is a partition of $\beta \left(m_k\right)$.

Example 1.

Table 1 shows a simplified layered formal context $K=\left(G,M,I\right)$, where $a=$“off-road vehicle,” $b=$ “midrange vehicle,” $c=$ “new energy power vehicle” which is a layer attribute, $c_1=$ “hybrid power,” and $c_2=$ “pure electric power.”

The formal context $\overline{K}$ induced by $K$ is shown in Table 2.

When a formal concept $K$ contains layered attributes, the upper concept lattice $C\left(K\right)$ is closely related to the lower concept lattice $C\left(\overline{K}\right)$. Hence, we can start with the lower concept lattice $C\left(\overline{K}\right)$ by rolling up the lower attributes $\overline{m_k}$ of some lower concepts to an upper attribute $m_k$ and then building a upper concept; this is easier than building the concept lattice directly from the formal context $K$.

Table 1

Layered formal context $K$.

$G$	$a$	$b$	$c$
			$c_1$	$c_2$
1	1	0	0	0
2	0	1	0	0
3	0	0	1	0
4	0	0	0	1
5	1	1	1	0
6	1	1	0	1

Table 2

Formal context $\overline{K}$ induced by $K$.

$G$	$a$	$b$	$\left(c,c_1\right)$	$\left(c,c_2\right)$
1	1	0	0	0
2	0	1	0	0
3	0	0	1	0
4	0	0	0	1
5	1	1	1	0
6	1	1	0	1

Theorem 2.

Suppose that $K=\left(G,M,I\right)$ is a layered formal context, $\overline{K}=\left(G,N,J\right)$ is the corresponding lower formal context of $K$, and $C\left(K\right)$ and $C\left(\overline{K}\right)$ are upper concept lattice and lower concept lattice, respectively. If $\left\{\left(A_1,\overline{B_1}\right),\cdots ,\left(A_{\alpha },\overline{B_{\alpha }}\right)\right\}\subseteq C\left(\overline{K}\right)$ contain the same layered attribute $\overline{m_k}$ and are the nearest subconcepts of a node concept, then

(1)

$\left(A_1,\overline{B_1}\right),\cdots ,\left(A_{\alpha },\overline{B_{\alpha }}\right)$ can be rolled up as a new concept $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$, where $A^{\left(k\right)}=A_1\cup \cdots \cup A_{\alpha }$ and $B^{\left(k\right)}=\left(\left(\overline{B_1}-\overline{m_k}\right)\cap \cdots \cap \left(\overline{B_{\alpha }}-\overline{m_k}\right)\right)\cup \left\{m_k\right\}$.

(2)

The lower concepts $\left(A_i,\overline{B_i}\right)\left(i=1,\cdots ,\alpha \right)$ are all updated into $\left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)$, respectively.

Proof.

It is worth pointing out before proving that a concept $\left(A_i,\overline{B_i}\right)$ in $C\left(\overline{K}\right)$ may contain both nonlayered attributes and lower attributes in the form of $\left(m_k,m_{kl}\right)$. In the following, we prove the theorem by four steps.

(1)

Prove equation $\alpha \left(A^{\left(k\right)}\right)=\left\{\left.m\in M\right|gI m,\forall g\in A^{\left(k\right)}\right\}=B^{\left(k\right)}$.

Let $m_l\in \alpha \left(A^{\left(k\right)}\right)$. Then, for each $g\in A^{\left(k\right)}=A_1\cup \cdots \cup A_{\alpha }$, we have $gI{m}_l$. If $m_l=m_k$, then obviously $m_l\in B^{\left(k\right)}$. If $m_l\ne m_k$, then because $\left(A_i,\overline{B_i}\right)\left(i=1,\cdots ,\alpha \right)$ are concepts and $gI{m}_l$ for each $g\in A_i$, we have that $m_l\in \overline{B_i}\left(i=1,\cdots ,\alpha \right)$. So, $m_l\in \left(\overline{B_1}-\overline{m_k}\right)\cap \cdots \cap \left(\overline{B_{i_k}}-\overline{m_k}\right)$. This means that $m_l\in B^{\left(k\right)}$. Hence,$$\begin{array}{}\text{(7)}& \alpha \left(A^{\left(k\right)}\right)=\left\{\left.m\in M\right|gIm,\forall g\in A^{\left(k\right)}\right\}\subseteq B^{\left(k\right)}.\end{array}$$

Suppose that $m_l\in B^{\left(k\right)}$. If $m_l\in \left\{m_k\right\}$, then $m_l=m_k$. Hence, $m_k$ are the layered attributes of concepts $\left(A_1,\overline{B_1}\right),\cdots ,\left(A_{i_k},\overline{B_{i_k}}\right)$, so $\alpha \left(A_i\right)=\left\{\left.m\in N\right|gJm,\forall g\in A_i\right\}=\overline{B_i},\left(i=1,\cdots ,\alpha \right)$. Thus, for each $g\in A^{\left(k\right)}=A_1\cup \cdots \cup A_{\alpha }$, there exists $i_0$ such that $g\in A_{i_0}$, so $gJ\left(m_k,m_{k{i}_0}\right)$, and $gI{m}_k$. This shows that $gI{m}_k$ for each $g\in A^{\left(k\right)}=A_1\cup \cdots \cup A_{\alpha }$. This means that $m_k\in \alpha \left(A^{\left(k\right)}\right)$. If $m_l\in \left(\overline{B_1}-\overline{m_k}\right)\cap \cdots \cap \left(\overline{B_{\alpha }}-\overline{m_k}\right)$, then $m_l\ne m_k$ is not a layered attribute and $m_l\in \overline{B_i},\left(i=1,\cdots ,\alpha \right)$. Since $\left(A_i,\overline{B_i}\right),\left(i=1,\cdots ,\alpha \right)$ are concepts, we have $gI{m}_l$ for each $g\in A^{\left(k\right)}=A_1\cup \cdots \cup A_{\alpha }$. Hence, $m_l\in \alpha \left(A^{\left(k\right)}\right)$. Thus, $B^{\left(k\right)}\subseteq \alpha \left(A^{\left(k\right)}\right)=\left\{\left.m\in M\right|gIm,\forall g\in A^{\left(k\right)}\right\}$.

(2)

Prove equation $\beta \left(B^{\left(k\right)}\right)=\left\{\left.g\in G\right|gI m,\forall m\in B^{\left(k\right)}\right\}=A^{\left(k\right)}$.

At first, we prove $\beta \left(B^{\left(k\right)}\right)\subseteq A^{\left(k\right)}$. Let us assume $g\in \beta \left(B^{\left(k\right)}\right)$; then, for every $m\in B^{\left(k\right)}=\left(\left(\overline{B_1}-\overline{m_k}\right)\cap \cdots \cap \left(\overline{B_{\alpha }}-\overline{m_k}\right)\right)\cup \left\{m_k\right\}$, we have $gIm$. Hence by $gI{m}_k$, we know that there are some $i$ such that $gJ\left(m_k,m_{ki}\right)$, so $gJ\overline{m_k}$, and let $i_0$ be the subscript of biggest concept $\left(A_{i_0},\overline{B_{i_0}}\right)$ 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 $\left(A_{i_0},\overline{B_{i_0}}\right)$ being the biggest concept, we obtain that$$\begin{array}{}\text{(8)}& g\in \beta \left(\overline{B_{i_0}}\right)=\left\{\left.g\in G\right|gJ\left(m_k,m_{ki}\right),\forall \left(m_k,m_{ki}\right)\in \overline{B_{i_0}}\right\}=A_{i_0}.\end{array}$$

This means that $g\in A^{\left(k\right)}$. Therefore,$$\begin{array}{}\text{(9)}& \beta \left(B^{\left(k\right)}\right)=\left\{\left.g\in G\right|gIm,\forall m\in B^{\left(k\right)}\right\}\subseteq A^{\left(k\right)}.\end{array}$$

Secondly, we prove $A^{\left(k\right)}\subseteq \beta \left(B^{\left(k\right)}\right)$. Let $g\in A^{\left(k\right)}$; then, there are some $i$ such that $g\in A_i$, and let $i_0$ be the subscript of biggest concept $\left(A_{i_0},\overline{B_{i_0}}\right)$ in these concepts. Hence, $g\in A_{i_0}=\beta \left(\overline{B_{i_0}}\right)$, and for each $m\in \overline{B_{i_0}}$, $gJm$. This shows that $g\in \left\{\left.g\in G\right|gIm,\forall m\in B^{\left(k\right)}\right\}$, and then $g\in \beta \left(B^{\left(k\right)}\right)$. Therefore,$$\begin{array}{}\text{(10)}& A^{\left(k\right)}\subseteq \beta \left(B^{\left(k\right)}\right)=\left\{\left.g\in G\right|gIm,\forall m\in B^{\left(k\right)}\right\}.\end{array}$$

From (1) and (2) we know that $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$ is a concept.

(3)

Prove that the concepts $\left(A_i,\overline{B_i}\right)\in C\left(\overline{K}\right)\left(i=1,\cdots ,\alpha \right)$, which are not rolled up, are updated new concepts $\left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)\left(i=1,\cdots ,\alpha \right)$.

At first, we prove equation $\alpha \left(A_i\right)=\left\{\left.m\in M\right|gIm,\forall g\in A_i\right\}=\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}$.

Let $m_l\in \alpha \left(A_i\right)$; then, for every $g\in A_i$, we have $gI{m}_l$. If $m_l=m_k$, then certainly $m_l\in \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}$. If $m_l\ne m_k$, then from that $\left(A_i,\overline{B_i}\right)$ is a concept and $gI{m}_q$ for every $g\in A_i$, we have $m_l\in \overline{B_i}$. Hence, $m_l\in \overline{B_i}-\overline{m_k}$. This shows that $\alpha \left(A_i\right)=\left\{\left.m\in M\right|gIm,\forall g\in A_i\right\}\subseteq \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}$.

Conversely, let $m_l\in \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}$. If $m_l\in \left\{m_k\right\}$, namely, $m_l=m_k$ is a layered attribute, then by $\left(A_i,\overline{B_i}\right)$ being a concept, we obtain that$$\begin{array}{}\text{(11)}& \overline{B_i}=\alpha \left(A_i\right)=\left\{\left(m_k,m_{ki}\right)\in \left.N\right|gJ\left(m_k,m_{ki}\right),\forall g\in A_i\right\}.\end{array}$$

Hence, by $gJ\left(m_k,m_{ki}\right)⟺gI{m}_k$, we know $m_q\in \alpha \left(A_i\right)$. If $m_q\in \overline{B_i}-\overline{m_k}$, then $m_q\ne m_k$ and $m_q\in \overline{B_i}$. Since $\left(A_i,\overline{B_i}\right)$ is a concept, we have $gI{m}_q$ for every $g\in A_i$; hence, $m_q\in \alpha \left(A_i\right)$. Therefore,$$\begin{array}{}\text{(12)}& \alpha \left(A_i\right)=\left\{\left.m\in M\right|gIm,\forall g\in A_i\right\}\supseteq \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}.\end{array}$$

Secondly, we prove the following equation:$$\begin{array}{}\text{(13)}& \beta \left(\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)=\left\{\left.g\in G\right|gIm,\forall m\in \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right\}=A_i.\end{array}$$

Let $g\in \beta \left(\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)$; then, $gIm$ for every $m\in \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}$. Since $\left(A_i,\overline{B_i}\right)$ is a concept, we know $\beta \left(\overline{B_i}\right)=\left\{\left.g\in G\right|gJm,\forall m\in \overline{B_i}\right\}=A_i$. Hence, by $gJ\left(m_k,m_{ki}\right)⟺gI{m}_k$, we have$$\begin{array}{}\text{(14)}& \beta \left(\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)=\left\{\left.g\in G\right|gIm,\forall m\in \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right\}\subseteq A_i.\end{array}$$

Conversely, let $g\in A_i$. Then, since $\left(A_i,\overline{B_i}\right)$ is a concept, we have $\beta \left(\overline{B_i}\right)=\left\{\left.g\in G\right|gJm,\forall m\in \overline{B_i}\right\}=A_i$. If $m\in \overline{B_i}$ is not a layered attribute, then the relation between $g$ and $m$ does not change before and after rolling up. If $m\in \overline{B_i}$ is a layered attribute and its form is $\left(m_k,m_{kj}\right)$, then by $gJ\left(m_k,m_{ki}\right)⟺gI{m}_k$, we have $gIm$ for each $m\in \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}$. Therefore,$$\begin{array}{}\text{(15)}& A_i\subseteq \beta \left(\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)=\left\{\left.g\in G\right|gIm,\forall m\in \left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right\}.\end{array}$$

(4)

Prove that the partial order among $\left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)\left(i=1,\cdots ,\alpha \right)$ is the same $\left(A_i,\overline{B_i}\right)\left(i=1,\cdots ,\alpha \right)$.

By the structure of $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$, for $i=1,\cdots ,\alpha$, we have$$\begin{array}{}\text{(16)}& \left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)\le \left(A^{\left(k\right)},B^{\left(k\right)}\right).\end{array}$$

If two concepts $\left(A_i,\overline{B_i}\right)$ and $\left(A_j,\overline{B_j}\right)$ are in $C\left(\overline{K}\right)$ with order $\left(A_i,\overline{B_i}\right)\le \left(A_j,\overline{B_j}\right)$, then the following also holds:$$\begin{array}{}\text{(17)}& \left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)\le \left(A_j,\left(\overline{B_j}-\overline{m_k}\right)\cup \left\{m_k\right\}\right).\end{array}$$

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. Let $\left(A_1,\overline{B_1}\right),\cdots ,\left(A_{\alpha },\overline{B_{\alpha }}\right)$ be the lower subconcepts under node concept $\left(A,B\right)$. If there is no partial order relation between each other, then $\left(A_1,\overline{B_1}\right),\cdots ,\left(A_{\alpha },\overline{B_{\alpha }}\right)$ is called parallel lower subconcepts. If there is linear partial order relation among them, then $\left(A_1,\overline{B_1}\right),\left(A_1,\overline{B_1}\right),\cdots ,\left(A_{\alpha },\overline{B_{\alpha }}\right)$ 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 from $C\left(\overline{K}\right)$ to $C\left(K\right)$ 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 $\left(A,B\right)$ in the lower concept lattice $C\left(\overline{K}\right)$ in a linear or parallel lower subconcepts, insert the new concept obtained from rolling up into the bottom of node $\left(A,B\right)$, and update the node concept $\left(A,B\right)$ 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 $C\left(\overline{K}\right)$ of layered formal context $\overline{K}$ induced by formal context $K$.

 

Output: an upper concept lattice.

 

Step 1. For $k=\mathrm{1,2},\dots ,l$, select all lower concepts containing layered attribute $\overline{m_k}$ and form lower concept set $C_k\left(\overline{K}\right)$ to be rolled up.

 

Step 2. The concepts in $C_k\left(\overline{K}\right)$ 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 $C\left(\overline{K}\right)$. For the linear lower subconcepts under node concept $\left(A,B\right)$ in $C_k\left(\overline{K}\right)$, the rolling-up method is as follows: combine the linear lower concepts $\left(A_1,\overline{B_1}\right),\dots ,\left(A_{\beta },\overline{B_{\beta }}\right)$ containing $\overline{m_k}$ into a new concept $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$, where $A^{\left(k\right)}=A_1\cap \cdots \cap A_{\beta }$, $B^{\left(k\right)}=\left(\left(\overline{B_1}-\overline{m_k}\right)\cup \cdots \cup \left(\overline{B_{\beta }}-\overline{m_k}\right)\right)\cup \left\{m_k\right\}$, and insert $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$ to node $\left(A,B\right)$ below. If node concept $\left(A,B\right)$ contains subconcepts with nonlower attributes, then node $\left(A,B\right)$ is updated to be the common upper bound of $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$ and other concepts (excluding lower attributes in $\overline{m_k}$) under node $\left(A,B\right)$.

 

Step 4. For the parallel lower subconcepts and lower subconcepts under node concept $\left(A,B\right)$ in $C_k\left(\overline{K}\right)$, the rolling-up method is as follows: combine the parallel lower concepts $\left(A_1,\overline{B_1}\right),\dots ,\left(A_{\beta },\overline{B_{\beta }}\right)$ containing $\overline{m_k}$ into a new concept $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$, where $A^{\left(k\right)}=A_1\cup \cdots \cup A_{\alpha }$, $B^{\left(k\right)}=\left(\left(\overline{B_1}-\overline{m_k}\right)\cap \cdots \cap \left(\overline{B_{\alpha }}-\overline{m_k}\right)\right)\cup \left\{m_k\right\}$, and insert $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$ to node $\left(A,B\right)$ below. If node concept $\left(A,B\right)$ contains subconcepts with nonlower attributes, then node $\left(A,B\right)$ is updated to be the common upper bound of $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$ and other concepts (excluding lower attributes in $\overline{m_k}$) under node $\left(A,B\right)$.

 

Step 5. If the node concept $\left(A,B\right)$ 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 $\left(C_j,\overline{D_j}\right)$, which is not rolled up from Step 3 to Step 5 but it contains the lower attribute of $\overline{m_k}$, to a new concept $\left(C_j,\left(\overline{D_j}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)$.

 

Step 7. Repeat from Step 3 to Step 6 until the concept in $C\left(\overline{K}\right)$ does not contain the lower attribute of $\overline{m_k}$ (namely, $C_k\left(\overline{K}\right)$ is an empty set).

 

Step 8. Repeat from Step 1 to Step 7 until $C\left(\overline{K}\right)$ does not contain any layered attribute. Algorithm is completed.

The time complexity of Algorithm 1 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 $C\left(\overline{K}\right)$ 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 $O\left(r\right)$. The time complexity at Step 2 is $O\left(r{\log }_{2}r\right)$; 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 $C_k\left(\overline{K}\right)$ 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 $O\left(s\right)$. The time complexity of Step 4 and Step 5 is the same as that of Step 3, which is also $O\left(s\right)$. The computing number at Step 6 does not exceed $s-r$, so the time complexity at Step 6 is $O\left(s-r\right)$. The time complexity analysis at Step 7 has been included from Step 3 to Step 6. Therefore, the time complexity of Algorithm 1 is $O\left(\left(r+r{\log }_{2}r+s+\left(s-r\right)\right)l\right)=O\left(l\left(2s+r{\log }_{2}r\right)\right)$.

The following example illustrates the application of the roll-up building algorithm in building concept lattice.

Example 2.

Consider the layered formal context $K$ as shown in example 1; the induced formal context by $K$ is shown in Figure 1.

[figure omitted; refer to PDF]

Steps 1 and 2.

The concepts containing lower attributes in $C\left(\overline{K}\right)$ are arranged in ascending order according to the number of attributes of concepts, $C_k\left(\overline{K}\right)=\left\{\left(35,\left(c,c_1\right)\right),\left(46,\left(c,c_2\right)\right),\left(5,ab\left(c,c_1\right)\right),\left(6,ab\left(c,c_2\right)\right),\left(\left\{\right\},ab\left(c,c_1\right)\left(c,c_2\right)\right)\right\}$.

Step 3.

There are no linear lower subconcepts in this example.

Step 4.

The concept of parallel lower concepts $\left(35,\left(c,c_1\right)\right)$, $\left(46,\left(c,c_2\right)\right)$ below node concept $\left(U,\left\{\right\}\right)$ is rolled up into a new concept $\left(3456,c\right)$ and inserted below node $\left(U,\left\{\right\}\right)$. The upper bound node of the new node concept $\left(3456,c\right)$ and the node concepts $\left(156,a\right)$, $\left(256,b\right)$ which do not contain lower attributes are also $\left(U,\left\{\right\}\right)$.

The parallel lower concept $\left(5,ab\left(c,c_1\right)\right)$, $\left(6,ab\left(c,c_2\right)\right)$ below node concept $\left(56,ab\right)$ is rolled up into a new concept $\left(56,abc\right)$.

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.

Figure 2 shows the concept lattice $C\left(K\right)$ obtained after the rolling up.

[figure omitted; refer to PDF]

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

In this section, a drill-down algorithm to build lower layered concept lattice $C\left(\overline{K}\right)$ based on the upper concept lattice $C\left(K\right)$ is presented.

4.1. Drill-Down Algorithm Theory

Definition 6.

Let $K=\left(G,M,I\right)$ be a layered formal context and $b\in M$. Then, $\left(\beta \left(b\right),\alpha \left(\beta \left(b\right)\right)\right)$ is called an attribute concept.

Proposition 3.

$\left(\beta \left(b\right),\alpha \left(\beta \left(b\right)\right)\right)$ is the largest concept containing attribute $b$.

Proof.

Obviously, $\left(\beta \left(b\right),\alpha \left(\beta \left(b\right)\right)\right)$ is a concept containing attribute $b$. If $\left(A,B\right)$ is another concept containing attribute $b$, then by $\left\{b\right\}\subseteq B$ and Proposition 1, we have $\beta \left(b\right)\supseteq \beta \left(B\right)=A$. Hence, $\left(A,B\right)\le \left(\beta \left(b\right),\alpha \left(\beta \left(b\right)\right)\right)$.

Theorem 3.

Let $K=\left(G,M,I\right)$ be a layered formal context and $\overline{K}=\left(G,N,J\right)$ be the lower formal context. Suppose that $m_k$ is a layered attribute; then,$$\begin{array}{}\text{(18)}& \overline{m_k}=\left\{\left(m_k,m_{k1}\right),\left(m_k,m_{k2}\right),\cdots ,\left(m_k,m_{k{i}_k}\right)\right\},\end{array}$$is the lower attribute corresponding to $m_k$, and $\left(\beta \left(m_k,m_{kj}\right),\alpha \left(\beta \left(m_k,m_{kj}\right)\right)\right)$ are attribute concepts corresponding to the lower attributes $\left(m_k,m_{kj}\right)\left(j=\mathrm{1,2},\cdots ,i_k\right)$. $\left(A,B\right)\in C\left(K\right)$ is a concept and for every $j\in \left\{\mathrm{1,2},\cdots ,i_k\right\}$, there is no child $\left(X,Y\right)$ of $\left(A,B\right)$ with $A\cap \beta \left(m_k,m_{kj}\right)\subseteq X$; then, for every $A\cap \beta \left(m_k,m_{kj}\right)$, $j\in \left\{\mathrm{1,2},\cdots ,i_k\right\}$,

(1)

If $A\cap \beta \left(m_k,m_{kj}\right)=A$, then $\left(A,B\right)$ is updated to $\left(A,\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)$

(2)

If $A\cap \beta \left(m_k,m_{kj}\right)\ne A$, then a new concept $\left(A\cap \beta \left(m_k,m_{kj}\right),\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)$ is added as a child of $\left(A,B\right)$

Proof.

(1) is a special case of (2), so we only prove (2).

Firstly, we prove that if $A\cap \beta \left(m_k,m_{kj}\right)\ne \phi$, then $\left(A\cap \beta \left(m_k,m_{kj}\right),\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)$ are concepts $\left(j=\mathrm{1,2},\cdots ,i_k\right)$; hence, we need to prove two equations:$$\begin{array}{c}\text{(19)}& \alpha \left(A\cap \beta \left(m_k,m_{kj}\right)\right)=\left\{\left.m\in N\right|gJm,\forall g\in A\cap \beta \left(m_k,m_{kj}\right)\right\}=\left(B-\left\{m_k\right\}\right)\cup \left.\left\{\left(m_k,m_{kj}\right)\right\}\right),\\ \text{(20)}& \beta \left(\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)=\left\{\left.g\in G\right|gJm,\forall m\in \left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right\}=A\cap \beta \left(m_k,m_{kj}\right).\end{array}$$

Since $\left(A,B\right)$ is a concept, we know $\alpha \left(A\right)=B$. By Proposition 1, we have that$$\begin{array}{}\text{(21)}& \alpha \left(A\cap \beta \left(m_k,m_{kj}\right)\right)\supseteq \alpha \left(A\right)\cup \alpha \left(\beta \left(m_k,m_{kj}\right)\right)=B\cup \alpha \left(\beta \left(m_k,m_{kj}\right)\right)\supseteq \left(B-\left\{m_k\right\}\right)\cup \alpha \left(\beta \left(m_k,m_{kj}\right)\right).\end{array}$$

Conversely, let $m_q\in \alpha \left(A\cap \beta \left(m_k,m_{kj}\right)\right)$. Then, for each $g\in A\cap \beta \left(m_k,m_{kj}\right)$, we have $gJ{m}_q$. In the following, we discuss it in two cases:

(i)

$m_q\in \overline{m_k}$: if $m_q\ne \left(m_k,m_{kj}\right)$, then there is $i\ne j$ such that $m_q=\left(m_k,m_{ki}\right)$. By Proposition 2$\beta \left(m_k,m_{k1}\right),\cdots ,\left.\beta \left(m_k,m_{k{i}_k}\right)\right\}$ is a partition of $\beta \left(m_k\right)$, we know that for every $g\in \beta \left(m_k,m_{kj}\right)$, $g$ and $\left(m_k,m_{ki}\right)$ have no relation $J$. This contradicts $gJ{m}_q$ for each $g\in A\cap \beta \left(m_k,m_{kj}\right)$. Thus, $m_q\in \left\{\left(m_k,m_{kj}\right)\right\}$.

(ii)

$m_q\notin \overline{m_k}$: if $m_q\notin B-\left\{m_k\right\}$, then obviously $m_q\ne m_k$, and hence $m_q\notin B$. Because $\left(A,B\right)$ is a concept containing attribute $m_k$, there exists $g\in A$ such that $g$ and $m_q$ have no relation $J$. The set of all elements of $A$ that has no relation $J$ with $m_q$ is denoted as $A_0$. If $A_0\cap \beta \left(m_k,m_{kj}\right)$ is an empty set, then for any $g\in \beta \left(m_k,m_{kj}\right)$ and $g\in A$, $g$ and $m_q$ have no relation $J$. This contradicts $gJ{m}_q$ for each $g\in A\cap \beta \left(m_k,m_{kj}\right)$. Hence, there is $g_0\in A_0\cap \beta \left(m_k,m_{kj}\right)$ such that $g_0$ and $m_q$ have no relation $J$. This also contradicts $gJ{m}_q$ for each $g\in A\cap \beta \left(m_k,m_{kj}\right)$. Therefore, if $m_q\notin \overline{m_k}$, then $m_q\in B-\left\{m_k\right\}$.

This proves that$$\begin{array}{}\text{(22)}& \alpha \left(A\cap \beta \left(m_k,m_{kj}\right)\right)=\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}.\end{array}$$

Since $\left(A,B\right)$ is a concept, we have $\beta \left(B\right)=A$. By Proposition 1 we obtain$$\begin{array}{c}\text{(23)}& \beta \left(\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)=\beta \left(B-\left\{m_k\right\}\right)\cap \beta \left(m_k,m_{kj}\right)\supseteq \beta \left(B\right)\cap \beta \left(\left(m_k,m_{kj}\right)\right)=A\cap \beta \left(m_k,m_{kj}\right).\end{array}$$

Conversely, let$$\begin{array}{}\text{(24)}& g\in \beta \left(\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)=\beta \left(B-\left\{m_k\right\}\right)\cap \beta \left(m_k,m_{kj}\right).\end{array}$$

From $g\in \beta \left(m_k,m_{kj}\right)$, we know $gJ\left(m_k,m_{kj}\right)$. By $gI{m}_k⟺gJ\left(m_k,m_{kj}\right)$, we have $gI{m}_k$. From $g\in \beta \left(B-\left\{m_k\right\}\right)$, we know $gIm$ for each $m\in B-\left\{m_k\right\}$. Hence, $gIm$ for every $m\in B$. This shows that $g\in \beta \left(B\right)=A$, and hence $g\in A\cap \beta \left(m_k,m_{kj}\right)$. Therefore,$$\begin{array}{}\text{(25)}& \beta \left(\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)\subseteq A\cap \beta \left(m_k,m_{kj}\right).\end{array}$$

This proves that$$\begin{array}{}\text{(26)}& \beta \left(\left(B-\left\{m_k\right\}\right)\cup \left\{\left(m_k,m_{kj}\right)\right\}\right)=A\cap \beta \left(m_k,m_{kj}\right).\end{array}$$

Next, we prove that the partial order among concepts $\left(A_i,\overline{B_i}\right)\left(i=1,\cdots ,\alpha \right)$ is the same as the partial order among $\left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)\left(i=1,\cdots ,\alpha \right)$.

At first, for $i=1,\cdots ,\alpha ,$ by the construction of $\left(A^{\left(k\right)},B^{\left(k\right)}\right)$, we have$$\begin{array}{}\text{(27)}& \left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)\le \left(A^{\left(k\right)},B^{\left(k\right)}\right).\end{array}$$

Secondly, if $\left(A_i,\overline{B_i}\right)\le \left(A_j,\overline{B_j}\right)$ in $C\left(\overline{K}\right)$, then we also have$$\begin{array}{}\text{(28)}& \left(A_i,\left(\overline{B_i}-\overline{m_k}\right)\cup \left\{m_k\right\}\right)\le \left(A_j,\left(\overline{B_j}-\overline{m_k}\right)\cup \left\{m_k\right\}\right).\end{array}$$

4.2. The Description and Analysis of Drill-Down Algorithm

According to Theorem 3, started with the upper concept lattice $C\left(K\right)$, inserted some new concepts, modified some concepts and deleted some concepts, we can obtained lower concept lattice $C\left(\overline{K}\right)$. 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 $C\left(K\right)$ of formal context $K$ containing layered attributes.

 

Output: the lower concept lattice $C\left(\overline{K}\right)$.

 

Step 1. For each lower attribute of a layered attribute $m_k$, $k\in \left\{\mathrm{1,2},\dots ,l\right\}$: $\overline{m_k}=\left\{\left(m_k,m_{k1}\right),\left(m_k,m_{k2}\right),\dots ,\left(m_k,m_{k{i}_k}\right)\right\}$, build all attribute concepts: $\left(A\cap \beta \left(m_k,m_{kj}\right),\left(B-\left\{m_k\right\}\right)\cup \alpha \left(\beta \left(m_k,m_{kj}\right)\right)\right)\left(j=\mathrm{1,2},\dots ,i_k\right)$.

 

Step 2. The concept $\left(A,B\right)$ containing layered attribute $m_k$ is updated to some new concepts $\left(A\cap \beta \left(m_k,m_{kj}\right),\left(B-\left\{m_k\right\}\right)\cup \alpha \left(\beta \left(m_k,m_{kj}\right)\right)\right)$, which contain lower attributes $\left(m_k,m_{kj}\right)$, $j=1,\dots ,i_k$, respectively, where $A\cap \beta \left(m_k,m_{kj}\right)$ is not an empty set. The concepts that do not contain the layered attribute $m_k$ 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 $\left(A,B\right)$ and are also not updated in $C\left(K\right)$ are connected to the updated node concepts.

 

Step 5. For each layered attribute $m_k\left(k=1,\dots ,l\right)$, repeat from Step 1 to Step 4 above.

 

Step 6. End of the algorithm.

The time complexity of Algorithm 2 is analyzed below. In the following, we assume that the number of layered attributes in $K$ is $l$, the number of node concepts in $C\left(K\right)$ is $s$, and the maximum number of lower attributes is $r$. The Bordat algorithm building concept lattice of formal context $\left(G,M,I\right)$ is improved by Chen in [12], and the time complexity of the improved algorithm is less than $O\left(\left|G\right|{\left|M\right|}^2\right)$. Then, in the worst case, the time complexity of Step 1 is $O\left(\left|G\right|r^2\right)$. The time complexity of Step 2 is $O\left(sr\right)$. The time complexity of Step 3 is $O\left(r^2\right)$. Therefore, the time complexity of algorithm 2 is $O\left(\left(\left|G\right|r^2+sr+r^2\right)l\right)=O\left(l\left(\left(\left|G\right|+1\right)r^2+sr\right)\right)$.

The following example illustrates the application of the drill-down building algorithm in building the concept lattice.

Example 3.

A layered formal context $K=\left(G,M,I\right)$ is shown in Table 3, and the concept lattice of $K$ is shown in Figure 3. The lower formal context $\overline{K}=\left(G,N,J\right)$ induced by K is shown in Table 4.

The concept lattice of $\overline{K}$ is shown in Figure 4.

Table 3

Layered formal context $K$.

$G$	$a$	$b$	$c$
			$c_1$	$c_2$	$c_3$
1	1	0	1	0	0
2	0	0	1	0	0
3	0	1	0	1	0
4	0	1	0	0	1
5	1	0	1	0	0
6	1	0	1	0	0

[figure omitted; refer to PDF]

Table 4

Formal context $\overline{K}$ induced by $K$.

$G$	$a$	$b$	$\left(c,c_1\right)$	$\left(c,c_2\right)$	$\left(c,c_3\right)$
1	1	0	1	0	0
2	0	0	1	0	0
3	0	1	0	1	0
4	0	1	0	0	1
5	1	0	1	0	0
6	1	0	1	0	0

[figure omitted; refer to PDF]

Step 1.

Layered attribute $c$ has three lower attributes, and the corresponding lower attribute concepts are $\left(1256,\left(c,c_1\right)\right)$, $\left(3,b\left(c,c_2\right)\right)$, $\left(4,b\left(c,c_3\right)\right)$.

Step 2.

There are four concepts in $C\left(K\right)$ that contain the layered attribute $c$. According to Step 2 in Algorithm 2, $\left(U,c\right)$ is updated into three new concepts $\left(1256,\left(c,c_1\right)\right)$, $\left(3,b\left(c,c_2\right)\right)$, $\left(4,b\left(c,c_3\right)\right)$; $\left(34,bc\right)$ is updated into two new concepts $\left(3,b\left(c,c_2\right)\right)$, $\left(4,b\left(c,c_3\right)\right)$; $\left(156,ac\right)$ is updated into a new concept $\left(156,a\left(c,c_1\right)\right)$.

Step 3.

Two lower attribute concepts $\left(3,b\left(c,c_2\right)\right)$, $\left(4,b\left(c,c_3\right)\right)$ can be combined into a new concept $\left(34,b\right)$ and inserted above $\left(3,b\left(c,c_2\right)\right)$, $\left(4,b\left(c,c_3\right)\right)$.

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 lattice $C\left(K\right)$ on the basis of lower concept lattice $C\left(\overline{K}\right)$, and the drill-down building algorithm is to build the lower concept lattice $C\left(\overline{K}\right)$ on the basis of the upper concept lattice $C\left(K\right)$. 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 example 3.

Example 4.

In the layered formal context of example 3, by using the drill-down algorithm, we obtain the lower concept lattice $C\left(\overline{K}\right)$ as shown in Figure 4. Now, we run the roll-up building algorithm on $C\left(\overline{K}\right)$.

Steps 1 and 2.

The concepts containing lower attributes in $C\left(\overline{K}\right)$ are arranged in ascending order according to the number of attributes contained in the concepts as follows: $C^{\prime }\left(\overline{K}\right)=\left\{1256,\left(c,c_1\right),\left(3,b\left(c,c_2\right)\right),\left(4,b\left(c,c_3\right)\right),\left(156,a\left(c,c_1\right)\right),\left(\left\{\right\},ab\left(c,c_1\right)\left(c,c_2\right)\left(c,c_3\right)\right)\right\}$.

Step 3.

The linear lower subconcepts $\left(1256,\left(c,c_1\right)\right)$, $\left(156,a\left(c,c_1\right)\right)$ below node concept $\left(U,\left\{\right\}\right)$ are rolled up into a new concept $\left(156,ac\right)$, and the node concept $\left(U,\left\{\right\}\right)$ is replaced by $\left(U,c\right)$, which are the parent concept (upper bound node) of the new concept $\left(156,ac\right)$ and the concept $\left(34,b\right)$ that does not contain lower attributes.

Step 4.

The parallel lower subconcepts $\left(3,b\left(c,c_2\right)\right)$, $\left(4,b\left(c,c_3\right)\right)$ below node concept $\left(34,b\right)$ are rolled up into a new concept $\left(34,bc\right)$. There are no other concepts below $\left(34,b\right)$ that do not contain lower attributes $\left(c,c_2\right)$, $\left(c,c_3\right)$, and then $\left(34,b\right)$ is updated into $\left(34,bc\right)$.

Step 5.

The lower attributes $\left(c,c_1\right)$, $\left(c,c_2\right)$, $\left(c,c_3\right)$ in the minimum node concept (empty concept) $\left(\left\{\right\},ab\left(c,c_1\right)\left(c,c_2\right)\left(c,c_3\right)\right)$ are integrated, and then we obtain the minimum concept $\left(\left\{\right\},abc\right)$.

Step 6.

There is only one layered attribute, and the algorithm ends.

After $C\left(\overline{K}\right)$ 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 Algorithms 1 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 $C\left(K\right)$ from the lower concept lattice $C\left(\overline{K}\right)$ with building the concept lattice $C\left(K\right)$ 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 context $\overline{K}$ is 52, 44, 36, 28, and 20, respectively. The test data with medium strength filling ratio $\left(\left|I\right|/\left(\left|G\right|\left|M\right|\right)\right)$ 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 omitted; refer to PDF][figure omitted; refer to PDF]

It can be seen from Figures 5 and 6 that using the roll-up building algorithm to build concept lattice $C\left(K\right)$ on the basis of $C\left(\overline{K}\right)$ takes less time than building directly the concept lattice $C\left(K\right)$ 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 lattice $C\left(\overline{K}\right)$ from the upper concept lattice $C\left(K\right)$ with building the concept lattice $C\left(\overline{K}\right)$ directly from the formal context $\overline{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 context $\overline{K}$ 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 omitted; refer to PDF][figure omitted; refer to PDF]

It can be seen from Figures 7 and 8 that using the drill-down building algorithm to build concept lattice $C\left(\overline{K}\right)$ on the basis of $C\left(K\right)$ takes less time than building directly the concept lattice $C\left(\overline{K}\right)$ from the formal context $\overline{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.

Acknowledgments

This study was supported in part by the Key Science Research Project of Hunan Province Education Department (no. 19A463), the Natural Science Foundation of Hunan Province (no. 2018JJ2371 and no. 2020JJ2251), and the Science and Technology Development Project of Chenzhou (no. zdyf201807).

References

[1] B. M. Lake, R. Salakhutdinov, J. B. Tenenbaum, "Human-level concept learning through probabilistic program induction," Science, vol. 350 no. 6266, pp. 1332-1338, DOI: 10.1126/science.aab3050, 2015.

[2] S. W. Hou, H. J. Wen, S. X. Feng, H. Wang, L. Zhibin, "Application of layered coding genetic algorithm in optimization of unequal area production facilities layout," Computational Intelligence and Neuro-Science, vol. 2019,DOI: 10.1155/2019/3650923, 2019.

[3] Y. Y. Yao, "Granular computing: basic issues and possible Solutions," Proceedings the 5th Joint Conference on Information Sciences, pp. 186-189, .

[4] W. X. Zhang, Y. Liang, W. Z. Wu, Rough Sets and Concept Lattice, 2006.

[5] X. Wu, J. Zhang, R. Lu, "Attribute logic formula description of granule and its application to build concept lattice," IEEE Access, vol. 8, pp. 12592-12606, DOI: 10.1109/access.2020.2964834, 2020.

[6] L. Zadeh, "Fuzzy sets and information granularity," Advances in Fuzzy Set Theory and Applications, 1979.

[7] T. Y. Lin, Granular Computing on Binary Relations II: Rough Set Representations and Belief Functions, Rough Sets in Knowledge Discovery, pp. 121-140, 1998.

[8] W. Pedrycz, Granular Computing: An Emerging Paradigm, 2001.

[9] B. Zhang, L. Zhang, Theory and Application of Problem Solving, 2005.

[10] B. Ganter, R. Wille, Formal Concept Analysis Mathematical Foundations, 1999.

[11] W. H. Xu, J. H. Li, L. Wei, Theory and Application of Formal Concept Analysis, 2016.

[12] Q. Y. Chen, "Improvement on Bordat algorithm for building concept lattice," Computer Engineering and Application, vol. 46 no. 35, pp. 33-35, 2010.

[13] Y.-M. Chai, Z. Zhang, L.-M. Wang, "An algorithm for mining global closed frequent itemsets based on distributed frequent concept direct product," Chinese Journal of Computers, vol. 35 no. 5, pp. 990-1001, DOI: 10.3724/sp.j.1016.2012.00990, 2012.

[14] S. Y. Fan, L. M. Wang, Q. Jiang, "Research of distributed integration algorithm on concept lattice," Computer Science, vol. 43 no. 1, pp. 223-278, 2016.

[15] Z. Zhang, Research on Web Base Extraction Based on Formal Concept Analysis, 2011.

[16] H. L. Zhi, "Knowledge representation on incomplete formal context," Computer Science, vol. 42 no. 1, pp. 276-278, 2015.

[17] Q. Li, L. Guo, "Formal query systems on contexts and a representation of algebraic lattices," Information Sciences, vol. 239 no. 4, pp. 72-84, DOI: 10.1016/j.ins.2013.03.032, 2013.

[18] J. Xie, M. Yang, J. Li, Z. Zheng, "Rule acquisition and optimal scale selection in multi-scale formal decision contexts and their applications to smart city," Future Generation Computer Systems, vol. 83, pp. 564-581, DOI: 10.1016/j.future.2017.03.011, 2018.

[19] F. Herrera, E. Herrera-Viedma, L. Martı́nez, "A fusion approach for managing multi-granularity linguistic term sets in decision making," Fuzzy Sets and Systems, vol. 114 no. 1, pp. 43-58, DOI: 10.1016/s0165-0114(98)00093-1, 2000.

[20] K. E. Wolff, "Conceptual interpretation of fuzzy theory," The 6th European Congress on Intelligent Techniques and Soft Computing, vol. 1, pp. 555-562, 1998.

[21] A. Burusco, R. Fuentes, "The study of L-fuzzy concept lattices," Mathware & Soft Computing, vol. 1 no. 3, pp. 209-218, 1994.

[22] Y. Qiang, Z. T. Liu, W. Lin, "Research on fuzzy concept lattice in knowledge discovery and a building algorithm," Acta Electronica Sinica, vol. 33 no. 2, pp. 350-353, 2005.

[23] J. Ali, E. Samir, "Galois connection, formal concepts and Galois lattice in real relation application in a real classifier," Journal of Systems & Software, vol. 60 no. 2, pp. 149-163, DOI: 10.1016/s0164-1212(01)00087-5, 2002.

[24] K.-S. Qu, Y. H. Zhai, J. Y. Liang, "Representation and extension of rough set theory based on formal concept analysis," Journal of Software, vol. 18 no. 9, pp. 2174-2182, DOI: 10.1360/jos182174, 2007.

[25] W. Liu, W. J. Xu, J. F. Fu, "An extended description logic for event ontology," Advances in Grid and Pervasive Computing, pp. 471-481, DOI: 10.1007/978-3-642-13067-0_49, 2010.

[26] Y. Z. Wang, X. L. Jin, X. Q. Cheng, "Network big data: present and furture," Chinese Journal of Computers, vol. 36 no. 6, pp. 1125-1138, DOI: 10.3724/sp.j.1016.2013.01125, 2013.

[27] H. Y. Wang, Y. F. Guo, "Application of big data technology in artificial intelligence," Digital Technology and Application, vol. 12, pp. 109-110, 2015.

[28] H. L. Zhi, "Extended model of formal concept analysis oriented for heterogeneous data analysis," Acta Electronica Sinica, vol. 41 no. 12, pp. 2451-2455, 2013.

[29] H. Zhi, J. Li, "Granule description based on formal concept analysis," Knowledge-Based Systems, vol. 104, pp. 62-73, DOI: 10.1016/j.knosys.2016.04.011, 2016.