Granule Description of Object (Attribute)-Oriented Linguistic Concept Lattice Based on Dominance Relation

Hui Cui; Ansheng Deng; Chunmei Chang; Hongyue Diao; Li Zou

doi:10.2991/ijcis.d.201230.001

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 14, Issue 1, 2021, Pages 701 - 714

Granule Description of Object (Attribute)-Oriented Linguistic Concept Lattice Based on Dominance Relation

Authors

Hui Cui¹, Ansheng Deng¹^{, *}, Chunmei Chang², Hongyue Diao¹, Li Zou³^{, *}

¹Information Science and Technology College, Dalian Maritime University, Dalian, Liaoning, 116026, P.R. China

²School of Computer and Information Technology, Liaoning Normal University, Dalian, Liaoning, 116019, P.R. China

³School of Computer Science and Technology, Shandong Jianzhu University, Jinan, Shandong, 250101, P.R. China

^*Corresponding authors. Email: ashdeng@dlmu.edu.cn; zoulicn@163.com

Corresponding Authors

Ansheng Deng, Li Zou

Received 15 July 2020, Accepted 6 December 2020, Available Online 6 January 2021.

DOI: 10.2991/ijcis.d.201230.001 How to use a DOI?
Keywords: Concept lattice; Object (attribute)-oriented linguistic concept lattice; Dominance relation; Granular computing; Linguistic term set
Abstract: Concept lattice, as an effective tool for knowledge acquisition and data analysis, has been successfully used in many fields. Aiming at the problem of groups for uncertain information in the linguistic environment, this paper mainly focuses on the granule description with linguistic concept lattice from the two aspects of object-oriented and attribute-oriented. Specifically, we present an object-oriented linguistic concept lattice to describe the linguistic dominance relation between attributes, the corresponding attribute dominant class is obtained meanwhile. Furthermore, we devote to constructing an object-oriented linguistic granular concept lattice by using the equivalence relations on the set of objects, combining the idea of granular computing. In order to deal with the linguistic information under the different importance of objects, the notion of attribute-oriented linguistic concept lattice based on object dominance relation is put forward. What’s more, we classify the attribute set so as to generate the attribute-oriented linguistic granular concepts with respect to a set of attributes. Besides, the effectiveness of the object-oriented linguistic concept lattice, object-oriented linguistic granular concept lattice, attribute-oriented linguistic concept lattice, attribute-oriented linguistic granular concept lattice is illustrated by the comparative analysis with other methods.
Copyright: © 2021 The Authors. Published by Atlantis Press B.V.
Open Access: This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION

Formal concept analysis, also called concept lattice, was first proposed by German mathematician Wille [1]. As the basis of formal concept analysis, the formal context can express the binary relation between objects and attributes while concept lattice can be constructed to visualize the hidden information in the formal context by defining the formal concept shorted as a concept. Over the past 20 years, scholars have conducted multi-angle and deep research on concept lattice, the research results of concept lattice are becoming more and more abundant [2–7]. Formal concept analysis with the advantage of providing a strong formal theory, has been widely used in various fields, such as information retrieval [8], semantic web [9,10], cognitive computing [11–13], three-way decisions [14,15] and knowledge engineering [16].

Considering that formal concept analysis and rough set are highly complementary, and rough set can analyze incomplete information such as inaccuracy, inconsistency and incompleteness, many scholars have studied the issue of knowledge discovery by combining the two theories to research and compare from multiple aspects [17,18]. Dntsch and Gediga [19,20] defined the model-style operator based on the binary relation, then the attribute-oriented concept lattice was established by the upper approximation operator. Yao [21,22] introduced rough set theory into the concept lattice and proposed object-oriented concept lattice. Based on this, the research of object (attribute)-oriented concept lattices has been mainly reflected in construction algorithms, attribute reduction and rule extraction. In order to reduce the time complexity, Ma et al. [23] presented a novel approach to acquire object-oriented concept lattice by discussing the properties of layered extension sets. Shao et al. [24] studied the reconstruction of attribute (object)-oriented concept lattice after coarsening attribute granularity based on granularity tree by using zoom algorithms. Qin et al. [25] adopted some equivalence relations and discernibility attributes to improve the attribute reduction and rule acquisition of formal decision context based on object (attribute)-oriented concept lattices. Kumar [26] focused on drawing the object and attribute based m-polar fuzzy concept lattice using the projection operator to discover some useful patterns for solving the particular issue of a given problem. Inspired by the above research, Zhi et al. [27] introduced three-way decision ideas to describe several connections among three-way concept analysis models where the dual concepts could cater the specific applications of international import and export transactions.

In recent years, with the rapid development of granular computing (GrC), the research of formal concept analysis has also advanced to a higher level. The core idea of GrC comes from Zadeh’s fuzzy information granules [28]. Qian et al. [29,30] extended the classic rough set model to a multi-granularity rough set, and obtained a rough set characterized by multiple upper and lower approximations of equivalence relations. Subsequently, GrC has attracted more and more attention in different fields [31–33], among them, the combination of GrC and formal concept analysis is particularly emerging. Xu and Li [34] discussed a novel GrC method of machine learning by using formal concept description of information granules. Belohlavek et al. [35] established a simple formal structure to provide users with different levels of attribute granularity. In order to reduce the time complexity and save the storage space in formal concept analysis, Mi et al. [36] further studied a simple discernibility matrix combining the object concept and the attribute concept with granular concept. Long et al. [37] proposed a dynamic updating method of attribute-induced three-way granular concept by deleting multiple objects and attributes in the formal context, which improved the efficiency and flexibility of construction for three-way concepts.

Many aspects of different activities in the real world cannot be described in a quantitative information, but rather in a qualitative one, for example, evaluating a school’s educational resources may be “very good”, “quite high” in quality of teaching, “a bit remote” in environment. Therefore, it is necessary to study the approaches with linguistic information. Affected by the research of computing with words (CWWs) [38,39], many related linguistic term models have been proposed [40–44]. Xu et al. [45] studied linguistic information from the perspective of formal concept analysis, which realized the combination of multiple formal sub-contexts to support the lattice-valued concept lattices. In order to solve the problems of reasoning under uncertainty, Zou et al. [46,47] proposed fuzzy linguistic concept lattice and knowledge reduction method via introducing linguistic terms into formal concept analysis. However, fuzzy linguistic concept lattice cannot solve some specific problems. For example, for the Mathematics, Physics and Chemistry scores of several students, it is easy to get the common level of these students based on the fuzzy linguistic concept lattice while we cannot get the highest scores of these students. Meanwhile, it is difficult to obtain information such as which subject is better for these students or which student is better. In this way, how to deal with linguistic information with dominance relation becomes particularly important [48–50]. In view that granular computing can effectively process a large amount of complex information, this article focuses on studying granular concepts with dominance relation in fuzzy linguistic formal context. We construct object (attribute)-oriented linguistic concept lattice and granular concept lattice to discuss the information of group linguistic value with dominance relation. It will further enrich the concept lattice theory of linguistic formal concept analysis.

The remainder of this paper is organized as follows: In order to make the paper self-contained, basic notions of ordered information system (IS), object (attribute)-oriented concept lattice and linguistic term set are briefly reviewed in Section 2. In Section 3, we propose an object-oriented linguistic concept lattice and provide the construction algorithm of object-oriented linguistic concept lattice. The object-oriented linguistic granular concept lattice which is granularization of object-oriented linguistic concept lattice based on equivalence relation is presented in Section 4. In Section 5, we propose the notions of attribute-oriented linguistic concept based on object dominance relation. The related attribute granulation method for linguistic formal context based on object dominance relation is presented in Section 6. In Section 7, we make some comparative analysis to illustrate the effectiveness of the proposed methods in this paper. It is concluded with a summary and the prospects for further research.

2. PRELIMINARIES

In this section, we briefly review the concepts of ordered IS, formal context and linguistic term set, seeing the following definitions for more details.

An IS is a quadruple I=(U,AT,V,f), where U is a finite nonempty set of objects and AT is a finite nonempty set of attributes, V=⋃a∈ATVa and Va is a domain of attribute a, f:U×AT→V is a total function such that f(x,a)∈Va for every a∈AT, x∈U, called an information function.

Definition 1.

[48] An IS is called an ordered information system (OIS) if all condition attributes are criterions.

It is assumed that the domain of a criterion a∈AT is completely preordered by an outranking relation ⩾a; x⩾ay means that x is at least as good as (outranks) y with respect to criterion a. In the following, without any loss of generality, we consider a condition criterion having a numerial domain, that is, x⩾ay⇔f(x,a)⩾f(y,a) (according to increasing preference) or x⩾ay⇔f(x,a)⩽f(y,a) (according to decreasing preference), where a∈AT, x,y∈U. For a subset of attributes A⊆AT, we define x⩾Ay⇔∀a∈A,x⩾ay. That is, x is at least as good as y with respect to all attributes in A. In general, the domain of the condition criterion may be also discrete, but the preference order between its values has to be provided.

The dominance relation that identifies granules of knowledge is defined as follows:

For a given OIS, we say that x dominates y with respect to A⊆AT if x⩾Ay, and denoted by xRA⩾y. Namely,

RA⩾={(y,x)∈U×U|y⩾Ax}(1)

If (y,x)∈RA⩾, then y dominates x with respect to A.

Given A⊆AT and A=A1⋃A2, where attributes set A1 according to increasing preference, A2 according to decreasing preference. The granules of knowledge induced by the dominance relation RA⩾ are the set of objects dominating x.

[x]A⩾={y∈U|f(y,a1)⩾f(x,a1)(∀a1∈A1),f(y,a2)⩽f(x,a2)(∀a2∈A2)}={y∈U|(y,x)∈RA⩾}(2)

and the set of objects dominated by x.

[x]A⩽={y∈U|f(y,a1)⩽f(x,a1)(∀a1∈A1),f(y,a2)⩾f(x,a2)(∀a2∈A2)}={y∈U|(x,y)∈RA⩾}(3)

which are called the A-dominating set and the A-dominated set with respect to x∈U, respectively.

Definition 2.

[22] A triple K=(G,M,I) is called a formal context, if G (the collection of objects) and M (the collection of attributes) are two finite nonempty sets and I (subset of cartesian product G×M) represents the binary relation between G and M, where 1 denotes that object has attribute and 0 denotes that object does not have the attribute.

Definition 3.

[19,22] Let K=(G,M,I) be a formal context, X⊆G, B⊆M. Operators ↑ and ↓ are defined as follows:

↑,↓,2G→2M:

X↑=XI={b∈M|∃x∈G,(xIb∧(x∈X))}X↓={b∈M|∀x∈G,(xIb⇒(x∈X))}(4)

↑,↓,2M→2G:

B↑=IB={x∈G|∃b∈M,(xIb∧(b∈B))}B↓={x∈G|∀b∈M,(xIb⇒(b∈B))}(5)

Definition 4.

[19,22] Let K=(G,M,I) be a formal context. A pair (X,B)(X⊆G,B⊆M) is called an object-oriented concept if X=B↑ and X↓=B. Similarly, (X,B) is called attribute-oriented concept if X↑=B and X=B↓. X and B are called the extent and intent of the object (attribute)-oriented concept respectively.

Let (X1,B1) and (X2,B2) be the object(attribute)-oriented concepts. The partial order ⩽ among them is defined by

(X1,B1)⩽(X2,B2)⇔X1⊆X2(⇔B1⊆B2)(6)

Let K=(G,M,I) be a formal context. Obviously, the complete set of object (attribute)-oriented concepts forms a complete lattice denoted by LO(G,M,I) and LA(G,M,I) respectively.

In real life, most people prefer to use “good,” “very good,” “very poor” and other linguistic values to describe things because of the ambiguous environment. In order to deal with the uncertain problems with linguistic values, Herrera et al. [51,52] proposed a linguistic term set as follows:

Let S={si|i=0,1,…,g} be a linguistic term set with odd cardinality. Any label, si represents a possible value for a linguistic variable, and it should satisfy the following characteristics:

Order relation: si>sj, if i>j.
Negation operator: Neg(si)=sj, where j=g−i.
Maximization operator: max {si,sj}=si, if i⩾j.
Minimization operator: min {si,sj}=sj, if i⩾j.

For example, a set of seven terms of S could be given as S = {s₀ = extremely poor, s₁ = very poor, ₂ = poor, s₃ = medium, s₄ = good, s₅ = very good, s₆ = extremely good}.

3. THE CONSTRUCTION OF OBJECT-ORIENTED LINGUISTIC CONCEPT LATTICE

3.1. Object-Oriented Linguistic Concept Lattice

In formal concept analysis, the traditional formal context is mostly composed of 0 and 1. However, due to the uncertainty and complexity of the environment, the data obtained is sometimes linguistic values. In order to avoid the problem of missing information in the process of linguistic information conversion, this section studies the object-oriented linguistic concept lattice based on formal context with linguistic terms, which is under dominance relation from the perspective of attribute importance.

Definition 5.

[46] Let (U,A,S) be a fuzzy linguistic formal context, where U={xi|i∈1,2,…,n} is a nonempty finite set of objects, A={aj|j∈1,2,…,m} is a nonempty finite set of attributes and S={sl|l∈0,1,…,g} is a relation between U and A, which is a subset of Cartesian product U×A, such that S(x,a)=sl.

Let (U,A,S) be a fuzzy linguistic formal context, for any x∈U, aj,ak∈A(j,k∈1,2,…,m), we can establish an attribute partial order relation ⩽x, in which ak⩽xaj indicates that the linguistic values corresponding to attribute aj dominant ak with respect to object x, i.e., S(x,ak)⩽S(x,aj). For simplicity, the partial order relation on ak⩽xaj is abbreviated as ajk.

Therefore, when there exists ajk in a formal context, if S(x,ak)⩽S(x,aj), we use S(x,aj) to represent the relation between x and ajk. If S(x,ak)>S(x,aj), we use “ ◇” to represent that the linguistic values of attribute aj don’t dominant attribute ak with respect to object x which we won’t consider in this article. In this way, we can get a formal context based on dominance relation with linguistic values.

Definition 6.

A triple (U,M,S◇) is called a linguistic formal context based on attribute dominance relation, where M={Mj|j∈1,2,…,m}, Mj={ajk|k∈1,2,…,m} denotes a set of attributes with a partial order relation, S◇ is a relation between U and M, such that S◇(x,ajk)={sl∈S or ◇|x∈U,ajk∈M}.

The linguistic formal context based on attribute dominance relation divides the attributes into a number of small blocks Mj(j=1,2,…,m) with dominance relation. Each small block represents the importance of the attribute aj compared with other attributes. Therefore, the attributes of the same block are comparable while not all of the blocks have a dominance relation.

Theorem 1.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation. For any ajk∈M, if j=k, then the linguistic values under ajk is the same as aj, i.e., S◇(x,ajk)=S(x,aj) with respect to object x.

Definition 7.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, for any a∈M, the attribute dominant class [a]U≺ can be defined as follows

[a]U≺={b∈M|S(x,a)⩽S(x,b),∀x∈U}(7)

In practical applications, it is very general to study whether objects possess attributes in common in a formal context. For example, teachers often need to be familiar with the knowledge of each student and focus on the explanation through the common learning problems of students in schools. However, if we want to hold a group subject competition for a class, we need to organize the performance of each member of the group, whether there are enough outstanding students in each subject to compete with others. In other words, not only the individual abilities of the students are very important, but also the comprehensive abilities of the group. As mentioned above, we give the following Example 1.

Example 1.

Consider the grades of four students in a class, the details about these students are shown with a fuzzy linguistic formal context (U,A,S) in Table 1, where U={x1,x2,x3,x4} is the set of students, A = {a₁ = Mathematics, a₂ = Physics, a₃ = Chemistry, a₄ = Biology} is the set of subjects and S = {s₀ = failing, s₁ = passing, s₂ = medium, s₃ = good, s₄ = excellent} is the relation between U and A. We can obtain a linguistic formal context based on attribute dominance relation (U,M,S◇), combining the dominance relation with respect to the attributes as shown in Table 2, where M={M1,M2,M3,M4}={{a11,a12,a13,a14},{a21,a22,a23,a24},{a31,a32,a33,a34},{a41,a42,a43,a44}.

U∕A	a1	a2	a3	a4
x1	s3	s2	s2	s1
x2	s1	s3	s4	s0
x3	s2	s0	s3	s2
x4	s3	s2	s4	s3

Table 1

Fuzzy linguistic formal context (U, A, S).

U∕M	M1				M2				M3				M4
	a11	a12	a13	a14	a21	a22	a23	a24	a31	a32	a33	a34	a41	a42	a43	a44
x1	s3	s3	s3	s3	◇	s2	s2	s2	◇	s2	s2	s2	◇	◇	◇	s1
x2	s1	◇	◇	s1	s3	s3	◇	s3	s4	s4	s4	s4	◇	◇	◇	s0
x3	s2	s2	◇	s2	◇	s0	◇	◇	s3	s3	s3	s3	s2	s2	◇	s2
x4	s3	s3	◇	s3	◇	s2	◇	◇	s4	s4	s4	s4	s3	s3	◇	s3

Table 2

Linguistic formal context based on attribute dominance relation (U,M,S◇).

From Table 2, we can obviously find some attributes with the same linguistic values. In order to simplify the operation, a new updated linguistic formal context based on attribute dominance relation is shown in Table 3.

U∕M	a11	a12	a13	a21	a22	a23	a24	a31	a33	a41	a44
x1	s3	s3	s3	◇	s2	s2	s2	◇	s2	◇	s1
x2	s1	◇	◇	s3	s3	◇	s3	s4	s4	◇	s0
x3	s2	s2	◇	◇	s0	◇	◇	s3	s3	s2	s2
x4	s3	s3	◇	◇	s2	◇	◇	s4	s4	s3	s3

Table 3

The updated linguistic formal context based on attribute dominance relation.

We can conclude from Tables 1–3, S(x1,a1)=s3 means that student x1 has a good Mathematics (a1) score in the fuzzy linguistic formal context (U,A,S). Meanwhile, in the linguistic formal context based on attribute dominance relation (U,M,S◇), S◇(x3, a12)=s2 represents that student x3 has a medium Mathematics score and his Mathematics score is better than his Physics (a2) score while S◇(x2, a12)=◇ means that the Mathematics score of student x2 is worse than his Physics score. For the object set E={x1,x2,x3} in Table 2, we have [a44]E≺={a11,a14,a32,a33,a34,a44}, i.e., their Mathematics and Chemistry (a3) scores are generally greater than or equal to their Biological (a4) scores for students x1,x2 and x3. It can be found that the linguistic formal context based on attribute dominance relation (U,M,S◇) can not only express the information in fuzzy linguistic formal context (U,A,S) but also describe the partial order relation between attributes.

For the linguistic formal context based on attribute dominance relation (U,M,S◇), we record US as the set which is the subset of U defined in S.

Definition 8.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, λ∈S be a credibility threshold, for any X⊆US, B⊆M, s∈S, the operators ′, ∗ and △ can be defined as follows:

x′={a∈M|∀x∈U,S◇(x,a)⩾λ},(8)

a′=sx∈US|∀a∈M,S◇(x,a)⩾λ,(9)

X∗={a∈M|a′⊆X},(10)

B△=∨sx∈US|x′∩B≠Ø.(11)

Remark 1.

X∗ is the set of attributes such that linguistic values corresponding to any object that satisfy one of them is necessarily in X, B△ denotes a set of maximum linguistic values between attributes and objects, which possesses at least one attribute in B.

Definition 9.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation. For any X⊆US, B⊆M, if there exist X∗=B and B△=X, then (X,B) is called object-oriented linguistic concept based on attribute dominance relation, abbreviated as object-oriented linguistic concept. X and B are called the extent and intent of the object-oriented linguistic concept, respectively.

The set of all object-oriented linguistic concepts of (U,M,S◇) is denoted by LLO(U,M,S◇), which called the object-oriented linguistic concept lattice of (U,M,S◇). For (X1,B1),(X2,B2)∈LLO(U,M,S◇), the partial order relation ⩽ of object-oriented linguistic concepts is defined by

(X1,B1)⩽(X2,B2)⇔X1⊆X2(⇔B1⊆B2)(12)

Remark 2.

For any a∈B,X1⊆X2 indicates that the linguistic value corresponding to each object under X2 is greater than or equal to the linguistic value under X1, and the objects in X1 are included in the objects in X2.

Proposition 1.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation. For any X,X1,X2⊆US,B,B1,B2⊆M. Then

B1⊆B2⇒B1△⊆B2△, X1⊆X2⇒X1∗⊆X2∗;
X∗△⊆X,B⊆B△∗;
X∗△∗=X∗,B△=B△∗△;
(X1∩X2)∗=X1∗∩X2∗, (B1∪B2)△=B1△∪B2△.

Proof.

We only prove X∗△∗=X∗, others can be proved analogously.

Suppose that a∈X∗△∗, then a′⊆X∗△, i.e., for any x∈U when sx∈a′, it satisfies x′∩X∗≠Ø. There exists an attribute b such that b∈x′ and b∈X∗ if sx∈a′, which means that if sx∈a′, we have that b∈x′ and b′⊆X. Since b∈x′ if and only if sx∈b′, we can find that x∈X in the case of sx∈a′ such that a′⊆X. Thus, a∈X∗, we can obtain X∗△∗⊆X∗.

On the contrary, suppose that a∈X∗, then a′⊆X. It implies that for any sx∈a′,a∈X∗, i.e., a′⊆sx|x′∩X∗≠Ø=X∗△, thus, a∈X∗△∗ such that X∗⊆X∗△∗.

Hence, we conclude that X∗△∗=X∗.

Proposition 2.

The object-oriented linguistic concept lattice LLO(U,M,S◇) is a complete lattice. For any (X1,B1),(X2,B2)∈LLO(U,M,S◇), the infimum and supermum are given by

(X1,B1)∨(X2,B2)=(X1∪X2,(B1∪B2)△∗)(X1,B1)∧(X2,B2)=((X1∩X2)∗△,B1∩B2)(13)

Theorem 2.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation. ∀a,b∈M,E⊆U,S(x,a)⩽S(x,b) if and only if a△E⊆b△E for each x∈E.

Proof.

According to dominance relation and approximation operator in linguistic formal context based on attribute dominance relation, it is obviously proved and the details are omitted here.

Corollary 1.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation. For any a,b∈M,E⊆U,b∈[a]E≺ if and only if a△E⊆b△E.

Proof.

It can be proofed by Definition 7 and Theorem 2 easily.

3.2. The Construction Algorithm of Object-Oriented Linguistic Concept Lattice

The main idea of the construction algorithm for object-oriented linguistic concept lattice is as follows. Firstly, transform the fuzzy linguistic formal context into a linguistic formal context based on attribute dominance relation. Secondly, start from the minimum object-oriented linguistic concept, the type of the concepts is judged from the bottom to the top obviously. Thirdly, find the corresponding extent according to the different combinations of attributes, and then generate the valid concepts by updating, deleting, until the maximal concept is found. Finally, the object-oriented linguistic concept lattice is drawn.

Algorithm 1: Construction algorithm for object-oriented linguistic concept lattice

Input: Fuzzy linguistic formal context (U,A,S);

Output: Object-oriented linguistic concept lattice LLO(U,M,S◇);

1: J1=(U,A,S);

2: J2=(U,M,S◇); // Compare the linguistic values relations corresponding to each attribute according to the dominance relation between attributes

3: CO=(Xi,Bi); // For Xi⊆US,Bi⊆M, set threshold λ, generate object-oriented linguistic concepts

4: C1=(Ø,Ø); // The minimum object-oriented linguistic concept of CO

5: while Bi≠Ø

6: if Bi only has one attribute

7: Find Xi according to Xi={sx|x′⊆Bi};

8: end if

9: if Bi has more than one attribute elements

10: Find Xi according to Bi△=Xi;

11: end if

12: Delete (Xi,Bi) with less attributes which has the same extent for other concepts;

13: if Xi∗=Bi and Bi△=Xi

14: Generate object-oriented linguistic concept (Xi,Bi);

15: end if

16: end while

17: LLO(U,M,S◇)={(Xi,Bi)};

18: return LLO(U,M,S◇);

Based on the construction algorithm of object-oriented linguistic concept lattice, we make some analysis on its time complexity. Comparing the linguistic values relation corresponding to each attribute according to the dominance relation between attributes, the running steps 1-2 to get a linguistic formal context based on attribute dominance relation take O(|M|). Running steps 3-8 take at most O(|M||U|), and running steps 9-18 take at most O|1+M||M|22|U|. Then the total time complexity is at most O|M||1+M||M|2|U|+|U|+1.

Example 2.

Consider the grades of four students in a class as presented in Example 1. Set λ=s2 as the standard score, in order to simplify the calculation, the attributes a12 and a44 in Table 3 are removed. We obtain the object-oriented linguistic concepts and its lattice structure which are as follows by Definition 9:

1#s3x1+s2x3+s3x4,a11a13a23a41, 2#s3x1,a13a23, 3#s2x1,a21, 4#s2x1+s3x2+s2x4,a21a22a23a24, 5#s2x1,a23, 6#s2x1+s3x2,a21a23a24, 7#s4x2+s3x3+s4x4,a21a31a41, 8#s2x1+s4x2+s3x3+s4x4,a21a22a23a24a31a33a41, 9#s2x3+s3x4,a41, 10#s3x1+s3x2+s2x3+s3x4,a11a13a21a22a23a24a41, 11#s3x1+s4x2+s3x3+s4x4,a11a13a21a22a23a24a31a33a41, 12#s3x1+s3x2,a13a21a23a24, 13#s3x1+s3x2+s2x4,a13a21a22a23a24, 14#s3x2+s2x3+s3x4,a21a41, 15#s2x1+s3x2+s2x3+s3x4,a21a22a23a24a41, 16#s2x1+s2x3+s3x4,a23a41, 17#(Ø,Ø).

The Hasse diagram of object-oriented linguistic concept lattice is shown as Figure 1.

The object-oriented linguistic concept 1# (s3x1+s2x3+s3x4,a11a13a23a41) in Figure 1 indicates that at least one subject in the attribute set {a1,a2,a4} has achieved the standard score for at least one student of the object set {x1,x3,x4}, i.e., taking students x1,x3 and x4 as a group, it is best for Mathematics, Physics and Biology can reach good, medium, good, respectively. From the perspective of attribute dominance relation, at least one of students x1,x3 and x4 meets a situation where the score of Mathematics is higher than Chemistry, the score of Physics is higher than Chemistry and the score of Biology is higher than Mathematics among their highest overall scores.

4. GRANULARIZATION OF OBJECT-ORIENTED LINGUISTIC CONCEPT LATTICE

Influenced by rough set and dominance relation, this paper constructs an object-oriented linguistic concept lattice, introducing the idea of approximate operator in rough set into linguistic formal concept analysis. In terms of granular computing, the rough set model can be characterized by multiple granules according to the equivalence relation. In order to describe the relation between objects and attributes under a class of attributes, we further study the granularization of object-oriented linguistic concept lattice.

4.1. Object-Oriented Linguistic Granular Concept Lattice

Similarly, we can define the classification in linguistic formal context based on attribute dominance relation according to the equivalence relation of rough set.

Definition 10.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, for any K⊆M, the equivalence relation on object set U is defined as follows:

RK={(x,v)|xS◇a=vS◇a,∀x,v∈U,a∈K}(14)

the classification of equivalence relation RK on object set U can be recorded as U∕RK, and [x]K={v|(x,v)∈RK} is an equivalence class on object set U.

Definition 11.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, for any X⊆US,K⊆M, the approximation operator ∗K on attribute set K can be defined as follows:

X∗K={a∈M|a′⊆XandY⊆U∕RK}(15)

where Y={x∈U|(x,a)∈S◇}.

Proposition 3.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, ∀X,X1,X2⊆US,K⊆M, there hold:

X1⊆X2⇒X1∗K⊆X2∗K;
X∗K△⊆X;
X∗K△∗K=X∗K;
(X1∩X2)∗K=X1∗K∩X2∗K.

Proof.

∀a∈X1∗K, we have a′⊆X1 and Y⊆U∕RK where Y={x∈U|(x,a)∈S◇}. If X1⊆X2 is satisfied, there must be a′⊆X2 and Y⊆U∕RK, therefore, a∈X2∗K, i.e., X1⊆X2⇒X1∗K⊆X2∗K.
∀sx∈X∗K△, we have x′⋂X∗K≠Ø. Then there exists an attribute a such that a∈x′ and a∈X∗K, thus, sx∈X, we can conclude X∗K△⊆X.
Obviously, X∗K⊆X∗K△∗K. By (1)(2), it follows that X∗K△∗K⊆X∗K, hence, X∗K△∗K=X∗K.
Since(1), we obtain (X1∩X2)∗K⊆X1∗K∩X2∗K. On the contrary, ∀a∈X1∗K∩X2∗K, we note that a′⊆X1 and a′⊆X2, Y⊆U∕RK, then a′⊆X1∩X2, Y⊆U∕RK, i.e., a⊆(X1∩X2)∗K, Thus, (X1∩X2)∗K=X1∗K∩X2∗K.

Definition 12.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, for any X⊆US,K,D⊆M, if there satisfy X∗K=D and D△=X, then (X,D) is called an object-oriented linguistic granular concept based on attribute set K, referred to as object-oriented linguistic granular concept.

The set of all the object-oriented linguistic granular concepts of (U,M,S◇) is denoted by LLO∕K(U,M,S◇). For (X1,D1),(X2,D2)∈LLO∕K(U, M,S◇), the partial order relation ⩽ on LLO∕K(U,M,S◇) is defined by

(X1,D1)⩽(X2,D2)⇔X1⊆X2(⇔D1⊆D2)(16)

Obviously, LLO∕K(U,M,S◇) forms a complete lattice which is called the object-oriented linguistic granular concept lattice of (U,M,S◇).

Theorem 3.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, then LLO∕K(U,M,S◇) is a sub-lattice of LLO(U,M,S◇).

Proof.

Obviously, the extent of LLO∕K(U,M,S◇) is the subset of the extent of LLO(U,M,S◇). For any concepts (X1,D1),(X2,D2)∈LLO∕K(U, M,S◇), we have (X1,D1)∧(X2,D2)=((X1∩X2)∗K△,D1∩D2). And (X1∩X2)∗K△∗K= (X1∩X2)∗K=X1∗K∩X2∗K= D1∩D2; (D1∩D2)△=(X1∗K∩X2∗K)△=(X1∩X2)∗K△.

Thus, (X1,D1)∧(X2,D2)∈LLO∕K(U,M,S◇). Similarly, (X1,D1)∨(X2,D2)∈LLO∕K(U,M,S◇). Therefore, LLO∕K(U,M,S◇) is a sub-lattice of LLO(U,M,S◇).

Theorem 4.

Let (U,M,S◇) be a linguistic formal context based on attribute dominance relation, for any K1,K2⊆M, if K1≠K2 and U∕RK1=U∕RK2, then LLO∕K1(U,M,S◇) = LLO∕K2(U,M,S◇).

Proof.

For any X⊆US,K1,K2⊆M,U∕RK1=U∕RK2, we have X∗K1={a∈M|a′⊆Xand Y⊆U∕RK1}={a∈M|a′⊆Xand Y⊆U∕RK2}=X∗K2 for Y={x∈U|(x,a)∈S◇} according to the Definition 11. To sum up, LLO∕K1(U,M,S◇) = LLO∕K2(U,M,S◇), this theorem is proved.

4.2. Construction Algorithm of Object-Oriented Linguistic Granular Concept Lattice

Based on the construction algorithm of object-oriented linguistic concept lattice mentioned in Algorithm 1, we can give the following construction algorithm for object-oriented linguistic granular concept lattice, combining the equivalence relations under a kind of attributes.

The main idea of the construction algorithm for object-oriented linguistic granular concept lattice is as follows: Set the threshold of linguistic information in the linguistic formal context based on attribute dominance relation (U,M,S◇) to obtain a new formal context for simplification. Find the equivalence relation on attribute set K and generate the object-oriented linguistic granular concepts according to the approximation operator. Then, the corresponding object-oriented linguistic granular concept lattice is performed as Algorithm 2.

Algorithm 2: Construction algorithm for object-oriented linguistic granular concept lattice

Input: A linguistic formal context based on attribute dominance relation (U,M,S◇);

Output: Object-oriented linguistic granular concept lattice LLO∕K (U,M,S◇);

1: J2=(U,M,S◇);

2: CO′=(Xi,Di); // For Xi⊆US,Di⊆M, set threshold λ′, generate object-oriented linguistic granular concepts

3: while K⊆M do

4: RK={(x,v)|xS◇a=vS◇a,∀x,v∈U,a∈K}; // The equivalence relation on object set U

5: while Xi⊆US,Di⊆M do

6: if Xi∗K=Di,Di△=Xi then

7: CO′=(Xi,Di);

8: end if

9: end while

10: end while

11: LLO∕K(U,M,S◇)={(Xi,Di)};

12: return LLO∕K(U,M,S◇);

On the basis of the established linguistic formal context based on attribute dominance relation (U,M,S◇), we make some analysis on the time complexity of construction algorithm for object-oriented linguistic granular concept lattice. In order to obtain the equivalence relation under the attribute set K, we need to take O(|U||K|) from step 1 to step 4. Running steps 5-12 take at most O(2|U∕RK|), then the total time complexity is at most O(|U||K|+2|U∕RK|).

Example 3.

Consider the grades of four students in a class as described in Example 1, set attribute set to K1={a21,a23,a24}, the corresponding equivalence relation is U∕RK1={{x1},{x2},{x3,x4}}. Based on that, we can get 12 object-oriented linguistic granular concepts according to Definition 12, and the lattice structure is shown as Figure 2:

Likewise, we can get the object-oriented linguistic granular concept lattice with attribute set K2={a13,a23} which is shown in Figure 3.

The object-oriented linguistic granular concept s4x2+s3x3+s4x4,a31 in Figure 3 represents that the score of Chemistry (a3) for the student set {x2,x3,x4} has reached the standard with the meaning that the scores of Chemistry are excellent, good, excellent for students x2 to x4, respectively. And their scores of Chemistry are higher than the Mathematics for these three students.

From the above discussions, we can conclude that the object-oriented linguistic granular concept lattice is the sub-lattice of the object-oriented linguistic concept lattice. The object-oriented linguistic concept lattice can express the highest level of linguistic evaluation for an objects group while the object-oriented linguistic granular concept lattice is to study linguistic concepts under an equivalence object set by classifying the objects under several attributes, so that we can quickly find out the characteristics of a class of objects in a targeted manner. Both of them can express the dominance relations between attributes, in addition, we can also obtain an object-oriented linguistic concept lattice by constructing object-oriented linguistic granular concepts.

5. THE CONSTRUCTION OF ATTRIBUTE-ORIENTED LINGUISTIC CONCEPT LATTICE

The above discussion is considered from the perspective of attribute dominance relations. Sometimes we also need to investigate the dominance relations of objects in the formal context. In order to describe the uncertain linguistic information under the object group with dominance relation, this section proposes the notion of attribute-oriented linguistic concept lattice based on object dominance relation.

5.1. Attribute-Oriented Linguistic Concept Lattice

For a fuzzy linguistic formal context (U,A,S), ∀xi,xr∈U, a∈A, an object partial order relation “ ⩽a,” in which xr⩽axi indicates that the linguistic values corresponding to object xi dominant xr with respect to attribute a, i.e., S(xr,a)⩽S(xi,a). For simplicity, the partial order relation on xr⩽axi is abbreviated as xir.

Therefore, when there exists xir in a formal context, if S(xr,a)⩽S(xi,a), we use S(xi,a) to represent the relation between xir and a. If S(xr,a)>S(xi,a), we use “ ◇” to represent that the linguistic values of object xi don’t dominant object xr with respect to attribute a which we won’t consider in this article. In this case, we can establish a linguistic formal context based on object dominance relation.

Definition 13.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, G={Gi|i∈1,2,…,n}, where Gi={xir|r∈1,2,…,n} denotes a set of objects with a partial order relation, S◇ is a relation between G and A, such that S◇(xir,a)={sl∈S or ◇|xir∈G,a∈A}.

The linguistic formal context based on object dominance relation divides the objects into a number of small blocks Gi(i=1,2,…,n) with dominance relation. Each small block represents the importance of the object xi compared with other objects. Therefore, the objects of the same block are comparable while not all of the blocks have a dominance relation.

Theorem 5.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation. For any xir∈G, if i=r, then the linguistic values under xir is the same as xi such that S◇(xir,a)=S(xi,a).

Definition 14.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, for any x∈G, the object dominant class [x]A≺ can be defined as follows:

[x]A≺={y∈G|S(x,a)⩽S(y,a),∀a∈A}(17)

Example 4.

Consider the fuzzy linguistic formal context (U,A,S) presented in Example 1. We can obtain a simplified linguistic formal context based on object dominance relation (G,A,S◇) as shown in Table 4, combining the dominance relation with respect to the objects, where G={G1,G2,G3,G4}={{x11,x12,x13},{x21,x22},{x31,x32,x33},{x41,x42}}.

G∕A	a1	a2	a3	a4
x11	s3	s2	s2	s1
x12	s3	◇	◇	s1
x13	s3	s2	◇	◇
x21	◇	s3	s4	◇
x22	s1	s3	s4	s0
x31	◇	◇	s3	s2
x32	s2	◇	◇	s2
x33	s2	s0	s3	s2
x41	s3	s2	s4	s3
x42	s3	◇	s4	s3

Table 4

Linguistic formal context based on object dominance relation (G,A,S◇)..

S◇(x12,a1)=s3 represents that the Mathematics of student x1 is good and his Mathematics is greater than or equal to student x2 in linguistic formal context based on object dominance relation (G,A,S◇), while S◇(x21,a1)=◇ means that the Mathematics of student x2 is worse than student x1. For the attribute set H={a1,a3,a4}, it follows [x33]H≺={x33,x41,x42}, i.e., the Mathematics, Chemistry, and Biology of student x4 are higher than that of student x3, and the three scores of student x4 are higher than those of student x1 and student x2 as well. It is worth noting that the linguistic formal context based on object dominance relation (G,A,S◇) can not only express the information in fuzzy linguistic formal context (U,A,S) but also describe the partial order relation between objects.

For the linguistic formal context based on object dominance relation (G,A,S◇), we record AS as the set which is the subset of A defined in S.

Definition 15.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, γ∈S be a credibility threshold. For any X̃⊆G,B̃⊆AS, a∈A,s∈S, the operators ♯, ∗ and △ can be defined as follows:

x♯={sa∈AS|∀x∈G,S◇(x,a)⩾γ},(18)

a♯={x∈G|∀a∈A,S◇(x,a)⩾γ},(19)

X̃△=∨{sa∈AS|a♯∩X̃≠Ø},(20)

B̃∗={x∈G|x♯⊆B̃}(21)

Remark 3.

X̃△ denotes a set of maximum linguistic values between attributes and objects, which possesses at least one object in X̃, B̃∗ is the set of objects such that linguistic values corresponding to any attribute that satisfy one of them is necessarily in B̃.

Definition 16.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation. For any X̃⊆G,B̃⊆AS, if there exist X̃△=B̃ and X̃=B̃∗, then (X̃,B̃) is called attribute-oriented linguistic concept based on object dominance relation, abbreviated as attribute-oriented linguistic concept. X̃ and B̃ are called the extent and intent of the attribute-oriented linguistic concept, respectively.

The set of all the attribute-oriented linguistic concepts of (G,A,S◇) is denoted by LLA(G,A,S◇). For (X̃1,B̃1),(X̃2,B̃2)∈LLA(G,A,S◇), the partial order relation ⩽ on LLA(G,A,S◇) is defined by

(X̃1,B̃1)⩽(X̃2,B̃2)⇔X̃1⊆X̃2(⇔B̃1⊆B̃2)(22)

Obviously, LLA(G,A,S◇) forms a complete lattice which is called the attribute-oriented linguistic concept lattice of (G,A,S◇).

Proposition 4.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation. For any X̃,X̃1,X̃2⊆G,B̃,B̃1,B̃2⊆AS. Then

B̃1⊆B̃2⇒B̃1∗⊆B̃2∗, X1̃⊆X̃2⇒X̃1△⊆X̃2△.
X̃⊆X̃△∗,B̃∗△⊆B̃.
X̃△∗△=X̃△,B̃∗△∗=B̃∗.
(X̃1∪X̃2)△=X̃1△∪X̃2△,(B̃1∩B̃2)∗=B̃1∗∩B̃2∗.

Proof.

We only prove B̃∗△∗=B̃∗, the others are the same.

Suppose that x∈B̃∗△∗, then x♯⊆B̃∗△, i.e., when sa∈x♯, it satisfies a♯∩B̃∗≠Ø. There exists an object y such that y♯∈a♯ and y∈B̃∗ if sa∈x♯, which means when sa∈x♯, we have y∈a♯ and y♯⊆B̃. Since y∈a♯ if and only if sa∈y♯, we can find that sa∈B̃ in the case of sa∈x♯ such that x♯⊆B̃. Thus, x∈B̃∗, we can obtain B̃∗△∗⊆B̃∗.

On the contrary, suppose that x∈B̃∗, then x♯⊆B̃. It means that for any sa∈x♯,x∈B̃∗, i.e., x♯⊆{sa|a♯∩B̃∗≠Ø}=B̃∗△, thus, x∈B̃∗△∗ such that B̃∗⊆B̃∗△∗.

Hence, we conclude that B̃∗△∗=B̃∗.

Proposition 5.

The attribute-oriented linguistic concept lattice LLA(G,A,S◇) is a complete lattice. For any (X̃1,B̃1),(X̃2,B̃2)∈LLA(G,A,S◇), the infimum and supermum are given as follows:

(X̃1,B̃1)∨(X̃2,B̃2)=((X̃1∪X̃2)△∗,B̃1∪B̃2)(X̃1,B̃1)∧(X̃2,B̃2)=(X̃1∩X̃2,(B̃1∩B̃2)∗△)(23)

Theorem 6.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation. ∀x,y∈G,H⊆A,S(x,a)⩽S(y,a) if and only if x△H⊆y△H for each a∈A.

Corollary 2.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation. For any x,y∈G,H⊆A,y∈[x]H≺ if and only if x△H⊆y△H.

5.2. The Construction Algorithm of Attribute-Oriented Linguistic Concept Lattice

The construction algorithm for attribute-oriented linguistic concept lattice is similar to the construction algorithm for object-oriented linguistic concept lattice as follows:

Algorithm 3: Construction algorithm for attribute-oriented linguistic concept lattice

Input: Fuzzy linguistic formal context (U,A,S);

Output: Attribute-oriented linguistic concept lattice LLA(G,A,S◇);

1: J1=(U,A,S);

2: J2′=(G,A,S◇); // Compare the linguistic values relations corresponding to each object according to dominance relation between objects

3: CA=(X̃i,B̃i); // For X̃i⊆G,B̃i⊆AS, set threshold γ to generate attribute-oriented linguistic concepts

4: C1=(Ø,Ø); // The minimum attribute-oriented linguistic concept of CA

5: while X̃i≠Ø

6: if X̃i only has one object

7: Find B̃i according to B̃i={sa|a♯⊆Xĩ}

8: end if

9: if X̃i has more than one object elements

10: Find B̃i according to B̃i=X̃i△;

11: end if

12: Delete (X̃i,B̃i) with less objects which has the same intent for other concepts;

13: if X̃i△=B̃i and B̃i∗=X̃i

14: Generate attribute-oriented linguistic concept (X̃i,B̃i);

15: end if

16: end while

17: LLA(G,A,S◇)={(X̃i,B̃i)};

18: return LLA(G,A,S◇);

Based on the construction algorithm of attribute-oriented linguistic concept lattice, we make some analysis on its time complexity. Comparing the linguistic values relation corresponding to each object according to the dominance relation between objects, the running steps 1-2 for getting a linguistic formal context based on object dominance relation take O(|G|). Running steps 3-8 take at most O(|G||A|), and running steps 9-18 take at most O(|1+G||G|22|A|). Then the total time complexity is at most O(|G|(|1+G||G|2|A|+|A|+1)).

Example 5.

Consider the grades of four students in a class as presented in Example 1, we analysis the relations between students and subjects further from the perspective of attribute-oriented linguistic concepts. Set γ=s2, the attribute-oriented linguistic concepts and the lattice structure are generated as follows after removing redundant information by Definition 16:

1#(Ø,Ø), 2#x11x12x13,s3a1+s2a2+s2a3, 3#x12,s3a1, 4#x12x13,s3a1+s2a2, 5#x21,s3a2+s4a3, 6#x31,s3a3+s2a4, 7#x32,s2a1+s2a4, 8#x31x32x33,s2a1+s3a3+s2a4, 9#x11x12x13x31x32x41x42,s2a1+s2a2+s4a3+s3a4, 10#x12x31x32x33x42,s3a1+s4a3+s3a4, 11#x11x12x13x21,s3a1+s3a2+s4a3, 12#x11x12x13x31x32x33,s3a1+s2a2+s3a3+s2a4, 13#x11x12x13x32,s3a1+s2a2+s2a3+s2a4, 14#x12x31x32x33,s3a2+s3a3+s2a4, 15#x12x32,s3a1+s2a4, 16#x21x31,s3a2+s4a3+s2a4, 17#x21x31x32x33,s2a1+s3a2+s4a3+s2a4, 18#x11x12x13x21x31x32x33x41x42,s3a1+s3a2+s4a3+s3a4, 19#x11x12x13x21x31x32x33,s3a1+s3a2+s4a3+s2a4.

The Hasse diagram of attribute-oriented linguistic concept lattice is shown as Figure 4.

If the object elements xir(i,r=1,2,…,n) in the extent of attribute-oriented linguistic concept are under the same block Gi, take x11x12x13,s3a1+s2a2+s2a3 as an example, x11,x12,x13∈G1, which denotes that the Mathematics, Physics and Chemistry of student x1 are good, medium and medium respectively. Meanwhile, at least one of the three subjects of x1 is higher than or equal to those of student x2 and student x3. If the object elements xir in the extent of attribute-oriented linguistic concept are under different blocks, take x12x32,s3a1+s2a4 as an example, x12∈G1,x32∈G3, more specifically, it has two meanings, on the one hand, it means that at least one of student x1 and student x3 has achieved at least one of good Mathematics and medium Biology. On the other hand, it represents that dividing student x1 and student x3 into a group, their Mathematics and Biology can achieve the best results of good and medium. From the perspective of object dominance relation, at least one of the Mathematics and Biology of student x1 is higher than those of student x2, so are students x3 and x2 for the attribute-oriented linguistic concept x12x32,s3a1+s2a4.

6. GRANULARIZATION OF ATTRIBUTE-ORIENTED LINGUISTIC CONCEPT LATTICE

6.1. Attribute-Oriented Linguistic Granular Concept Lattice

In this section, in order to meet the needs of different people and construct an attribute-oriented linguistic concept lattice more purposefully, we propose the equivalence relation of attribute sets to study the granularization of attribute-oriented linguistic concept lattices, considering the dominance relation of objects in fuzzy linguistic formal context.

Definition 17.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, for any F⊆G, the equivalence relation on attribute set A is defined as follows:

RF={(b,h)|xS◇b=xS◇h,∀x∈F,b,h∈A}(24)

the classification of equivalence relation RF on attribute set A can be recorded as A∕RF, and [b]F={h|(b,h)∈RF} is an equivalence class on attribute set A.

Definition 18.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, for any F⊆G, B̃⊆AS, the approximation operator ∗F on object set F can be defined as follows:

B̃∗F={x∈G|x♯⊆B̃andZ⊆A∕RF}(25)

where Z={a∈A|(x,a)∈S◇}.

Proposition 6.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, ∀B̃,B̃1,B̃2⊆AS,F⊆G, there hold:

B̃1⊆B̃2⇒B̃1∗F⊆B̃2∗F;
B̃∗F△⊆B̃;
B̃∗F△∗F=B̃∗F;
(B̃1∩B̃2)∗F=B̃1∗F∩B̃2∗F.

Proof.

∀y∈B̃1∗F, we have y♯⊆B̃1 and Z⊆A∕RF where Z={a∈A|(x,a)∈S◇}. If B̃1⊆B̃2 is satisfied, there must be y♯⊆B̃2 and Z⊆A∕RF, therefore, y∈B̃2∗F, i.e., B̃1⊆B̃2⇒B̃1∗F⊆B̃2∗F.
∀sa∈B̃∗F△, we have a♯⋂B̃1∗F≠Ø. Then there exist y∈a♯ and y∈B̃∗F, thus, sa∈B̃, we can conclude B̃∗F△⊆B̃.
Obviously, B̃∗F⊆B̃∗F△∗F. By (1)(2), it follows that B̃∗F△∗F⊆B̃∗F, hence, B̃∗F△∗F=B̃∗F.
Since(1), we obtain (B̃1∩B̃2)∗F⊆B̃1∗F∩B̃2∗F. On the contrary, ∀y∈B̃1∗F∩B̃2∗F, we note that y♯⊆B̃1 and y♯⊆B̃2, Z⊆A∕RF, then y♯⊆B̃1∩B̃2, Z⊆A∕RF, i.e., y⊆(B̃1∩B̃2)∗F. Thus, (B̃1∩B̃2)∗F=B̃1∗F∩B̃2∗F.

Definition 19.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, for any F,Q⊆G, B̃⊆AS, if there satisfy B̃∗F=Q and Q△=B̃, then (Q,B̃) is called an attribute-oriented linguistic granular concept based on object set F, referred to as attribute-oriented linguistic granular concept.

The set of all the attribute-oriented linguistic granular concepts of (G,A,S◇) is denoted by LLA∕F(G,A,S◇). For (Q1,B̃1),(Q2,B̃2)∈LLA∕F(G,A,S◇), the partial order relation ⩽ on LLA∕F(G,A,S◇) is defined by

(Q1,B̃1)⩽(Q2,B̃2)⇔Q1⊆Q2(⇔B̃1⊆B̃2)(26)

Obviously, LLA∕F(G,A,S◇) forms a complete lattice which is called the attribute-oriented linguistic granular concept lattice of (G,A,S◇).

Theorem 7.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, then LLA∕F(G,A,S◇) is a sub-lattice of LLA(G,A,S◇).

Proof.

Similar to Theorem 3 and the details are omitted.

Theorem 8.

Let (G,A,S◇) be a linguistic formal context based on object dominance relation, for any F1,F2⊆G, if F1≠F2 and A∕RF1=A∕RF2, then LLA∕F1(G,A,S◇) = LLA∕F2(G,A,S◇).

Proof.

For any B̃⊆AS,F1,F2⊆G,A∕RF1=A∕RF2, we have B̃∗F1={x∈G|x♯⊆B̃and Z⊆A∕RF1}={x∈G|x♯⊆B̃and Z⊆A∕RF2}=B̃∗F2 for Z={a∈A|(x,a)∈S◇} according to the Definition 18. To sum up, LLA∕F1(G,A,S◇) = LLA∕F2(G,A,S◇), this theorem is proved.

6.2. Construction Algorithm of Attribute-Oriented Linguistic Granular Concept Lattice

Based on the construction algorithm of attribute-oriented linguistic concept lattice mentioned in Algorithm 3, we can give the following construction algorithm for attribute-oriented linguistic granular concept lattice, combining the equivalence relation under a kind of objects.

Algorithm 4: Construction algorithm for attribute-oriented linguistic granular concept lattice

Input: A linguistic formal context based on object dominance relation (G,A,S◇);

Output: Attribute-oriented linguistic granular concept lattice LLA∕F(G,A,S◇);

1: J2′=(G,A,S◇);

2: CA′=(Qi,B̃i); // For Qi⊆G,B̃i⊆AS, set threshold γ′, generate attribute-oriented linguistic granular concepts

3: while F⊆G

4: RF={(b,h)|xS◇b=xS◇h,∀b,h∈A, x∈F}; // The equivalence relation on attribute set A

5: while Qi⊆G, Bĩ⊆AS

6: if Bĩ∗F=Qi and Qi△=Bĩ

7: CA′=(Qi,B̃i);

8: end if

9: end while

10: end while

11: LLA∕F(G,A,S◇)={(Qi,B̃i)};

12: return LLA∕F(G,A,S◇);

In linguistic formal context based on object dominance relation (G,A,S◇), we make some analysis on the time complexity of construction algorithm for attribute-oriented linguistic granular concept lattice. In order to obtain the equivalence relation under object set F, we need to take O(|A||F|) from step 1 to step 4. Running steps 5-12 take at most O(2|A∕RF|), then the total time complexity is at most O(|A||F|+2|A∕RF|).

Example 6.

We consider the fuzzy linguistic formal context (U,A,S) presented in Example 1. Set object set to F1={x41,x42}, then the corresponding equivalence relation is A∕RF1={{a1,a4},{a2},{a3}}. Based on that, we can get 4 attribute-oriented linguistic granular concepts according to Definition 19, and the lattice structure is shown as follows:

Similarly, we can get the attribute-oriented linguistic granular concept lattice when the object set is F2={x12,x32} which is shown in Figure 6.

Through the above analysis, it is obvious that attribute-oriented linguistic granular concept lattice is the sub-lattice of attribute-oriented linguistic concept lattice. Constructing attribute-oriented linguistic granular concept lattices from the equivalence relations of attributes can obtain attribute-oriented linguistic concept lattice with dominance relation. For a type of objects set, the linguistic relations between attributes and objects as well as the dominance relations of the objects are analyzed at the finer object granularity. In this way, we can get results faster according to the different needs of different people in a targeted manner.

7. COMPARATIVE ANALYSIS

In this section, we conduct some comparative analysis to assess the effectiveness of the proposed methods in this paper. Compared with [24] and [46], we summarize the following characteristics:

Shao et al. [24] proposed a method for constructing object(attribute)-oriented multi-granularity concept lattices, which realized the two-way transformation of attributes from fine-granularity to coarse-granularity and coarse-granularity to fine-granularity, effectively improving the construction speed of object (attribute)-oriented concept lattices. But sometimes 0 and 1 are not enough to accurately express the relation between objects and attributes, the object (attribute)-oriented linguistic concept lattice studied in this paper can directly describe the relations between objects and attributes with qualitative linguistic values. Meanwhile, the object (attribute)-oriented linguistic concept lattice can avoid the loss of information in the process of converting linguistic values into numeral values. And setting different linguistic thresholds can better meet different requirements of different people.
Liu et al. [46] discussed fuzzy linguistic formal context in uncertain environment, and studied the fuzzy linguistic concept lattice through the common relations between the objects and attributes. In real life, in addition to the importance of the commonality between objects and attributes, the problem of grouping is also very important. The object (attribute)-oriented linguistic concept lattice proposed in this paper takes into account the importance of groups on objects and attributes. Therefore, the object (attribute)-oriented linguistic concept lattice proposed in this paper further studies specific group problems and can solve different practical applications.
From the perspective of object dominance relation and attribute dominance relation, object (attribute)-oriented linguistic concept can reflect the relation between individuals, more importantly, it can express the comprehensive ability of the group to provide a new idea for group issues. In addition, the use of the dominance relation between objects and attributes to establish linguistic granular concept lattice can obtain the object (attribute)-oriented linguistic concept lattices, which finds more dominant objects and attributes quickly.

Finally, it should be pointed out that our object (attribute)-oriented linguistic concept lattices with dominance relation are proposed on the basis of the object (attribute)-oriented concept lattice. Its time complexity is a bit high. We will take it as the future discussion direction so as to propose better construction method.

8. CONCLUSION

Granular computing is an important idea in the cross fusion of rough set and concept lattice. It can divide large amounts of complex information into several simple parts according to its characteristics, which is more conducive to studying concept lattices. This paper has discussed the group problems by constructing object-oriented linguistic concept lattice and attribute-oriented linguistic concept lattice based on dominance relation in fuzzy linguistic formal context. For object-oriented linguistic concept lattice, we have put forward a construction algorithm of object-oriented linguistic granular concept lattice by using an equivalence relation with respect to objects, so that we can more purposeful get a specific concept lattice. The attribute-oriented linguistic granular concept lattice has been presented to construct attribute-oriented linguistic concept lattice under the dominance relation of objects. The method proposed in this paper further enriches the concept lattice theory, which describes the importance from the perspective of objects and attributes, thereby extracting the effective information in an uncertain environment.

The object-oriented linguistic granular concepts and attribute-oriented linguistic granular concepts proposed in this paper are constructed based on the equivalence relationship and only consider one granularity, which cannot meet the problem of multiple granularity choices in real life. In the future, we plan to further study the optimal granularity selection problem and construct object-oriented and attribute-oriented linguistic concept lattices by multiple granularities with dominance relation, so as to provide a new way of thinking for the research of formal concept analysis.

CONFLICTS OF INTEREST

Authors have no conflict of interest.

AUTHORS' CONTRIBUTIONS

Among the authors in the list, Hui Cui proposed the innovative points of the paper and mainly took charge of writing and researching. Ansheng Deng played a guiding role and gave a lot of advice and contributions on the paper during the review process. Chunmei Chang carried out algorithm design and data analysis during the revision of the paper. Hongyue Diao was mainly responsible for proofreading and revision issues. Li Zou was as the cooperation teacher who was responsible for checking and guiding of this paper.

ACKNOWLEDGMENTS

This work is partially supported by the National Natural Science Foundation of China (Nos. 61502068, 61772250) and the Scientific Research Project of Department of Education of Liaoning Province (No. LJ2020007).

REFERENCES

1.R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, S. Ferré and S. Rudolph (editors), Formal Concept Analysis, Springer, Berlin, Heidelberg, Germany, 2009.

2.J.S. Mi, Y. Leung, and W.Z. Wu, Approaches to attribute reduction in concept lattices induced by axialities, Knowl. Based Syst., Vol. 23, 2010, pp. 504-511.

3.R.L. Zhang, S.W. Xiong, and Z. Chen, Construction method of concept lattice based on improved variable precision rough set, Neurocomputing, Vol. 188, 2016, pp. 326-338.

4.S.C. Yang, Y.N. Lu, X.Y. Jia, and W.W. Li, Constructing three-way concept lattice based on the composite of classical lattices, Int. J. Approx. Reason., Vol. 121, 2020, pp. 174-186.

5.Z. Zhang, Constructing L-fuzzy concept lattices without fuzzy Galois closure operation, Fuzzy Sets Syst., Vol. 333, 2018, pp. 71-86.

6.M.W. Shao, W.Z. Wu, X.Z. Wang, and C.Z. Wang, Knowledge reduction methods of covering approximate spaces based on concept lattice, Knowl. Based Syst., Vol. 191, 2020, pp. 1-9.

7.J.H. Li, C.L. Mei, L.D. Wang, and J.H. Wang, On inference rules in decision formal contexts, Int. J. Comput. Intell. Syst., Vol. 8, 2015, pp. 175-186.

8.M. Huang, J.J. Lin, Y. Peng, and X. Xie, Design a batched information retrieval system based on a concept-lattice-like structure, Knowl. Based Syst., Vol. 150, 2018, pp. 74-84.

9.Y.C. Jiang, Semantifying formal concept analysis using description logics, Knowl. Based Syst., Vol. 186, 2019, pp. 1-14.

10.A. Formica, Semantic web search based on rough sets and fuzzy formal concept analysis, Knowl. Based Syst., Vol. 26, 2012, pp. 40-47.

11.J.H. Li, C.L. Mei, W.H. Xu, and Y.H. Qian, Concept learning via granular computing: a cognitive viewpoin, Inf. Sci., Vol. 298, 2015, pp. 447-467.

12.Y. Shi, Y.L. Mi, J.H. Li, and W.Q. Liu, Concurrent concept-cognitive learning model for classification, Inf. Sci., Vol. 496, 2019, pp. 65-81.

13.B.J. Fan, E.C.C. Tsang, W.H. Xu, D.G. Chen, and W.T. Li, Attribute-oriented cognitive concept learning strategy: a multi-level method, Int. J. Mach. Learn. Cybern., Vol. 10, 2019, pp. 2421-2437.

14.L. Wei, L. Liu, J.J. Qi, and T. Qian, Rules acquisition of formal decision contexts based on three-way concept lattices, Inf. Sci., Vol. 516, 2020, pp. 529-544.

15.H.L. Zhi, J.J. Qi, T. Qian, and R.S. Ren, Conflict analysis under one-vote veto based on approximate three-way concept lattice, Inf. Sci., Vol. 516, 2020, pp. 316-330.

16.J.F. Viaud, K Bertet, R. Missaoui, and C. Demko, Using congruence relations to extract knowledge from concept lattices, Discrete Appl. Math., Vol. 249, 2018, pp. 135-150.

17.L. Wei and Q.J. Jun, Relation between concept lattice reduction and rough set reduction, Knowl. Based Syst., Vol. 23, 2010, pp. 934-938.

18.S.L. Wu, S. Yang, and Q.Y. Wang, Classification of open pit iron mine rock mass blastability based on concept lattice and rough set, Geotech. Geol. Eng., Vol. 38, 2020, pp. 449-458.

19.I. Dntsch and G. Gediga, Modal-style operators in qualitative data analysis, in Proceeding 2nd IEEE International Conference on Data Mining (Maebashi, Japan), 2002, pp. 155-162.

20.I. Dntsch and G. Gediga, Approximation operators in qualitative data analysis, H. de Swart, E. Orłowska, G. Schmidt, and M. Roubens (editors), Theory and Applications of Relational Structures as Knowledge Instruments, Springer-Verlag, Berlin, Germany, Vol. 2929, 2003, pp. 214-230.

21.Y.Y. Yao, A comparative study of formal concept analysis and rough set theory in data analysis, S. Tsumoto, R. Słowiński, J. Komorowski, and J.W. Grzymała-Busse (editors), Rough Sets and Current Trends in Computing, Lecture Notes in Artificial Intelligence, Springer, Berlin, Heidelberg, Germany, Vol. 3066, 2004, pp. 59-68.

22.Y.Y. Yao, Concept lattices in rough set theory, in Proceeding of 4th Annual Conference of the North American Fuzzy Information Processing Society (Banff, Canada), 2004, pp. 796-801.

23.J.M. Ma, M.J. Cai, and C.J. Zou, Concept acquisition approach of object-oriented concept lattices, Int. J. Mach. Learn. Cybern., Vol. 8, 2017, pp. 123-134.

24.M.W. Shao, M.M. Lv, K.W. Li, and C.Z. Wang, The construction of attribute (object)-oriented multi-granularity concept lattices, Int. J. Mach. Learn. Cybern., Vol. 11, 2020, pp. 1017-1032.

25.K.Y. Qin, B. Li, and Z. Pei, Attribute reduction and rule acquisition of formal decision context based on object (property) oriented concept lattices, Int. J. Mach. Learn. Cybern., Vol. 10, 2019, pp. 2837-2850.

26.S.P. Kumar, Object and attribute oriented m-polar fuzzy concept lattice using the projection operator, Granul. Comput., Vol. 4, 2019, pp. 545-558.

27.H.L. Zhi, J.J. Qi, T. Qian, and L. Wei, Three-way dual concept analysis, Int. J. Approx. Reason., Vol. 114, 2019, pp. 151-165.

28.L.A. Zadeh, Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets Syst., Vol. 90, 1997, pp. 111-127.

29.Y.H. Qian, J.Y. Liang, and C.Y. Dang, MGRS in Incomplete Information Systems, in in IEEE International Conference on Granular Computing (GRC 2007) (Fremont, CA, USA), 2007.

30.Y.H. Qian, J.Y. Liang, and C.Y. Dang, Incomplete multigranulation rough set, IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., Vol. 40, 2010, pp. 420-431.

31.S. Xu, Multigranulation rough set: a multiset based strategy, Int. J. Comput. Intell. Syst., Vol. 10, 2017, pp. 277-292.

32.G. Wang, J. Yang, and J. Xu, Granular computing: from granularity optimization to multi-granularity joint problem solving, Granul. Comput., Vol. 2, 2017, pp. 105-120.

33.H. Fujita, A. Gaeta, V. Loia, and F. Orciuoli, Resilience analysis of critical infrastructures: a cognitive approach based on granular computing, IEEE Trans. Cybern., Vol. 49, 2019, pp. 1835-1848.

34.W.H. Xu and W.T. Li, Granular computing approach to two-way learning based on formal concept analysis in fuzzy datasets, IEEE Trans. Cybern., Vol. 46, 2016, pp. 366-379.

35.R. Belohlavek, D.B. Baets, and J. Konecny, Granularity of attributes in formal concept analysis, Inf. Sci., Vol. 260, 2014, pp. 149-170.

36.L.J. Li, M.Z. Li, J.S. Mi, and B. Xie, A simple discernibility matrix for attribute reduction in formal concept analysis based on granular concepts, J. Intell. Fuzzy Syst., Vol. 37, 2019, pp. 4325-4337.

37.A.B. Long, W.H. Xu, X.Y. Zhang, and L. Yang, The dynamic update method of attribute-induced three-way granular concept in formal contexts, Int. J. Approx. Reason., Vol. 126, 2020, pp. 228-248.

38.L.A. Zadeh, Fuzzy logic = computing with words, IEEE Trans. Fuzzy Syst., Vol. 4, 1996, pp. 103-111.

39.L.A. Zadeh, The concept of linguistic variable and application to approximate reasoning, part I, part II, part III, Inf. Sci., Vol. 8, 1975, pp. 301-357.

40.D. Meng and Z. Pei, On weighted unbalanced linguistic aggregation operators in group decision making, Inf. Sci., Vol. 223, 2013, pp. 31-41.

41.R.M. Rodriguez, L. Martinez, and F. Herrera, Hesitant fuzzy linguistic term sets for decision making, IEEE Trans. Fuzzy Syst., Vol. 20, 2012, pp. 109-119.

42.J.J. Lai and Y. Xu, Linguistic truth-valued lattice-valued propositional logic systeml, Inf. Sci., Vol. 180, 2010, pp. 1990-2002.

43.Y. Liu, J. Liu, Y. Qin, and Y. Xu, A novel method based on extended uncertain 2-tuple linguistic muirhead mean operators to MAGDM under uncertain 2-Tuple linguistic environment, Int. J. Comput. Intell. Syst., Vol. 12, 2019, pp. 498-512.

44.Y.X. Zhang, D.G. Huang, W. Gao, and V.G. Kaburlasos, A decision making approach with linguistic weight and unavoidable incomparable ranking, Int. J. Comput. Intell. Syst., Vol. 12, 2019, pp. 1102-1112.

45.L. Yang, Y. Wang, and Y. Xu, A combination algorithm of multiple lattice-valued concept lattices, Int. J. Comput. Intell. Syst., Vol. 6, 2013, pp. 881-892.

46.P.S. Liu, H. Cui, Y.M. Cao, X.H. Hou, and L. Zou, A method of multimedia teaching evaluation based on fuzzy linguistic concept lattice, Multimedia Tools Appl., Vol. 78, 2019, pp. 30975-31001.

47.L. Zou, K. Pang, X.Y. Song, N. Kang, and X. Liu, A knowledge reduction approach for linguistic concept formal context, Inf. Sci., Vol. 524, 2020, pp. 165-183.

48.Y.H. Qian, J.Y. Liang, and C.Y. Dang, Interval ordered information systems, Comput. Math. Appl., Vol. 56, 2008, pp. 1994-2009.

49.C. Luo, T. Li, H. Chen, and D. Liu, Incremental approaches for updating approximations in set-valued ordered information systems, J. Knowl. Based. syst., Vol. 50, 2013, pp. 914-233.

50.L. Wang, M. Li, J. Ye, and X. Yu, Dynamic knowledge update using three-way decisions in dominance-based rough sets approach while the object set varies, Int. J. Comput. Intell. Syst., Vol. 12, 2019, pp. 914-928.

51.C.C. Li, R.M. Rodriguez, L. Martinez, Y.C. Dong, and F. Herrera, Personalized individual semantics based on consistency in hesitant linguistic group decision making with comparative linguistic expressions, Knowl. Based Syst., Vol. 145, 2018, pp. 156-165.

52.D.C. Liang, W. Pedrycz, D. Liu, and H. Pei, Three-way decisions based on decision-theoretic rough sets under linguistic assessment with the aid of group decision making, Appl. Soft Comput., Vol. 29, 2015, pp. 256-269.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 14 - 1
Pages: 701 - 714
Publication Date: 2021/01/06
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.d.201230.001 How to use a DOI?
Open Access: This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Hui Cui
AU  - Ansheng Deng
AU  - Chunmei Chang
AU  - Hongyue Diao
AU  - Li Zou
PY  - 2021
DA  - 2021/01/06
TI  - Granule Description of Object (Attribute)-Oriented Linguistic Concept Lattice Based on Dominance Relation
JO  - International Journal of Computational Intelligence Systems
SP  - 701
EP  - 714
VL  - 14
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.d.201230.001
DO  - 10.2991/ijcis.d.201230.001
ID  - Cui2021
ER  -

download .riscopy to clipboard

U∕M	M1				M2				M3				M4
	a11	a12	a13	a14	a21	a22	a23	a24	a31	a32	a33	a34	a41	a42	a43	a44
x1	s3	s3	s3	s3	◇	s2	s2	s2	◇	s2	s2	s2	◇	◇	◇	s1
x2	s1	◇	◇	s1	s3	s3	◇	s3	s4	s4	s4	s4	◇	◇	◇	s0
x3	s2	s2	◇	s2	◇	s0	◇	◇	s3	s3	s3	s3	s2	s2	◇	s2
x4	s3	s3	◇	s3	◇	s2	◇	◇	s4	s4	s4	s4	s3	s3	◇	s3

U∕M	a11	a12	a13	a21	a22	a23	a24	a31	a33	a41	a44
x1	s3	s3	s3	◇	s2	s2	s2	◇	s2	◇	s1
x2	s1	◇	◇	s3	s3	◇	s3	s4	s4	◇	s0
x3	s2	s2	◇	◇	s0	◇	◇	s3	s3	s2	s2
x4	s3	s3	◇	◇	s2	◇	◇	s4	s4	s3	s3

G∕A	a1	a2	a3	a4
x11	s3	s2	s2	s1
x12	s3	◇	◇	s1
x13	s3	s2	◇	◇
x21	◇	s3	s4	◇
x22	s1	s3	s4	s0
x31	◇	◇	s3	s2
x32	s2	◇	◇	s2
x33	s2	s0	s3	s2
x41	s3	s2	s4	s3
x42	s3	◇	s4	s3

U∕M	M1				M2				M3				M4
	a11	a12	a13	a14	a21	a22	a23	a24	a31	a32	a33	a34	a41	a42	a43	a44
x1	s3	s3	s3	s3	◇	s2	s2	s2	◇	s2	s2	s2	◇	◇	◇	s1
x2	s1	◇	◇	s1	s3	s3	◇	s3	s4	s4	s4	s4	◇	◇	◇	s0
x3	s2	s2	◇	s2	◇	s0	◇	◇	s3	s3	s3	s3	s2	s2	◇	s2
x4	s3	s3	◇	s3	◇	s2	◇	◇	s4	s4	s4	s4	s3	s3	◇	s3

U∕M	a11	a12	a13	a21	a22	a23	a24	a31	a33	a41	a44
x1	s3	s3	s3	◇	s2	s2	s2	◇	s2	◇	s1
x2	s1	◇	◇	s3	s3	◇	s3	s4	s4	◇	s0
x3	s2	s2	◇	◇	s0	◇	◇	s3	s3	s2	s2
x4	s3	s3	◇	◇	s2	◇	◇	s4	s4	s3	s3

G∕A	a1	a2	a3	a4
x11	s3	s2	s2	s1
x12	s3	◇	◇	s1
x13	s3	s2	◇	◇
x21	◇	s3	s4	◇
x22	s1	s3	s4	s0
x31	◇	◇	s3	s2
x32	s2	◇	◇	s2
x33	s2	s0	s3	s2
x41	s3	s2	s4	s3
x42	s3	◇	s4	s3

U∕M	M1				M2				M3				M4
	a11	a12	a13	a14	a21	a22	a23	a24	a31	a32	a33	a34	a41	a42	a43	a44
x1	s3	s3	s3	s3	◇	s2	s2	s2	◇	s2	s2	s2	◇	◇	◇	s1
x2	s1	◇	◇	s1	s3	s3	◇	s3	s4	s4	s4	s4	◇	◇	◇	s0
x3	s2	s2	◇	s2	◇	s0	◇	◇	s3	s3	s3	s3	s2	s2	◇	s2
x4	s3	s3	◇	s3	◇	s2	◇	◇	s4	s4	s4	s4	s3	s3	◇	s3

U∕M	a11	a12	a13	a21	a22	a23	a24	a31	a33	a41	a44
x1	s3	s3	s3	◇	s2	s2	s2	◇	s2	◇	s1
x2	s1	◇	◇	s3	s3	◇	s3	s4	s4	◇	s0
x3	s2	s2	◇	◇	s0	◇	◇	s3	s3	s2	s2
x4	s3	s3	◇	◇	s2	◇	◇	s4	s4	s3	s3

G∕A	a1	a2	a3	a4
x11	s3	s2	s2	s1
x12	s3	◇	◇	s1
x13	s3	s2	◇	◇
x21	◇	s3	s4	◇
x22	s1	s3	s4	s0
x31	◇	◇	s3	s2
x32	s2	◇	◇	s2
x33	s2	s0	s3	s2
x41	s3	s2	s4	s3
x42	s3	◇	s4	s3