search for




 

Notes on Independence of Attributes in Soft Contexts
International Journal of Fuzzy Logic and Intelligent Systems 2019;19(3):158-162
Published online September 25, 2019
© 2019 Korean Institute of Intelligent Systems.

Won Keun Min

Department of Mathematics, Kangwon National University, Chuncheon, Korea
Correspondence to: Won Keun Min (wkmin@kangwon.ac.kr)
Received August 24, 2018; Revised September 17, 2019; Accepted September 20, 2019.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

For the purpose of studying the formal concepts and the reduction in a formal context, we have combined the formal contexts with the soft sets to form soft contexts and proposed the soft concept in a soft context. As a series of studies, it is necessary to investigate specific properties of attributes. For this purpose, we introduce and study the notion of independent and dependent attributes in a given soft context. In particular, we will study the following: (1) Every dependent attribute is generated by some independent attributes: (2) The set of all soft concepts can be completely constructed by independent attributes.

Keywords : Formal context, Formal concept, Concept lattice, Soft set, Soft context, Soft concept, Independent attributes
1. Introduction

For the purpose of the study of hierarchical structures based on a binary relation between objects and attributes, Wille introduced FCA (formal concept analysis) [1] in 1982 and investigated the notions of context, formal concept, and concept lattice. A formal context, a type of information system, is represented in a tabular form of an object-attribute value relationship [25]. A formal concept is presented in pairs consisting of objects and attributes. The order relationship between two formal concepts is well defined, and it is well known that through this order relationship the collection of all formal concepts is a complete lattice. It is simply called the concept lattice [5]. Formal concept analysis has been widely applied to many information systems research fields, and many studies are actively conducted to apply problems in real-world situations. [511].

The concept of soft sets was introduced by Molodtsov in 1999 [12] for the purpose of dealing with complex problems and uncertainties: Let U be an initial universe set (simply, universe set) and A be a collection of characteristics or properties of objects in U. A pair (F,A) is called a soft set over U if F is a mapping of A into the set of all subsets of the set U. For the soft set theory, Ali et al. [13] proposed new operations that complements the concepts defined by Maji in [14].

In [15], we constructed the soft context combining the notions of formal contexts and soft sets as set-valued mappings. Additionally, we introduced and investigated the notions of soft concepts and soft concepts lattice that are closely related to formal concepts and concept lattices in FCA.

As a series of studies in [15], we would like to investigate the specific properties of attributes. In this paper, we introduce and study the notions of independent and dependent attributes in a given soft context. In particular, we will show the following two facts: 1) Every dependent attribute is generated by some independent attributes: 2) The set of all soft concepts can be completely constructed by independent attributes.

2. Preliminaries

We recall some basic definitions of formal concept analysis used in this paper. A formal context is a triplet (U, A, I), where U is a non-empty finite set of objects, A is a nonempty finite set of attributes, and I is a relation between U and A. In the formal context (U, A, I), for a pair of elements xU and aA, if (x, a) ∈ I, we write xIa. A set of attributes with an object xU and a set of objects with an attribute aA can be represented as ( [1, 5]):

x*={aA|xIa};   a*={xU|xIa}.

Extending x to a subset XU and a to a subset BA:

X*={aA|xX,xIa};   B*={xU|bB,xIb}.

A pair (X,B) of two sets XU and BA is called a formal concept of the context (U, A, I) if X = B* and B = X* (see [1, 5]). X and B are called the extent and the intent of the concept, respectively.

Let U be an initial universe set (simply, universe set) and E be a collection of all possible parameters with respect to U, where parameters are the characteristics or properties of objects in U. We will call E the set of parameters with respect to U. Let P(U) denote the power set and AE.

A pair (F,A) is called a soft set [12] over U if F is a set-valued mapping of A into the set of all subsets of the set U, i.e.,

F:AP(U).

In other words, the soft set is a parameterized family of subsets of the set U. Every set F(e), for eAE, from this family may be considered as the set of e-elements of the soft set (F,A), or as the set of e-approximate elements of the soft set.

We call a soft set (F,A) is pure if ∩aAF(a) = ∅︀ and F(a) ≠ ∅︀ for every aA. From now on, we assume that all soft sets are pure.

Let U = {x1, x2, . . . , xn} be a non-empty finite set of objects, A = {a1, a2, . . . , am} a non-empty finite set of attributes, and F : AP(U) a soft set. Then the triple (U, A, F) is called a soft context [15].

Let (U, A, F) be a soft context. Then for a soft set (F,A),

1) F+ : P(A) → P(U) is a mapping defined as F+(B) = ∩bBF(b);

2) F : P(U) → P(A) is a mapping defined as F(X) = {aA : XF(a)}.

We will denote Im(F+) = {F+(B)|BP(A)} and Im(F) = {F(X)|XP(U)}.

Simply, we denote F+({a}) = F+(a) for each aA, and F({x}) = F(x) for each xU.

Theorem 2.1 ( [15])

Let (U, A, F) be a soft context, X, YU and C,DA. Then we have the following things:

1) If XY, then F(Y ) ⊆ F(X); if CD, then F+(D) ⊆ F+(C);

2) XF+F(X); CFF+(C);

3) F(XY ) = F(X)∩F(Y ), F+(CD) = F+(C)∩ F+(D);

4) F(X) = FF+F(X), F+(C) = F+FF+(C);

5) F(X) ∪ F(Y ) ⊆ F(XY ), F+(C) ∪ F+(D) ⊆ F+(CD).

In a soft context (U, A, F), let us define two associated operations ΨF and ΦF [15] induced by F+,F+ as the following ways:

For each XP(U),

ΨF:P(U)P(U)is a mapping defined asΨF(X)=F+F-(X):

In the rest of the paper, Ψ is instead of ΨF when there is no ambiguity.

Let (U, A, F) be a soft context and XP(U). Then X is called a soft concept [15] in (U, A, F) if Ψ(X) = F+F(X) = X. The set of all soft concepts will be denoted by s(U, A, F).

Theorem 2.2 ( [15])

Let (U, A, F) be a soft context. Then

1) ∅︀, U, Ψ(X) are soft concepts.

2) For each BA, F+(B) is a soft concept.

3) For each aA, F(a) is a soft concept.

4) X is a soft concept if and only if X = F+(B) for some BP(A).

5) Im(F+) = s(U, A, F).

3. Independence, Dependence of Attributes

For a soft context (U, A, F), we introduce and study the notions of dependent and independent in A. We will show that every formal concept of formal context is represented by independent elements of the associated soft context.

From now on, we will denote |X| the cardinal number of any set X.

Definition 3.1

Let (U, A, F) be a soft context. Put Ga(A) = {gA | F(a) ⊊ F(g)} ⊆ A (simply, Ga). Then for dA, d is said to be dependent on A if there exists Gd ≠ ∅︀ satisfying F(d) = F+(Gd) = ∩aGdF(a).

Otherwise, d is said to be independent on A.

We denote:AD={aA|ais dependent on A};AI={aA|ais independent on A}.

Example 3.2

Let U = {1, 2, 3, 4, 5} and A = {a, b, c, d, e, f}. Let us consider a soft set F : AP(U) defined by

F(a)=F(d)={1,2,4};   F(b)={2,4,5};F(c)={2,4};   F(e)={1,3};   F(f)={1,3,5}.

Then a is independent on A since Ga = ∅︀, and also e is independent since Ge = {f} ≠ ∅︀ but F+(Ge) = ∩gGeF(g) = F(f) ≠ F(e). In case of cA, it is dependent since Gc = {a, b, d} ≠ ∅︀ and F+(Gc) = ∩gGcF(g) = F(c).

Consequently, we have

AI={a,b,d,e,f};   AD={c}.

Then we easily obtain the following facts:

Theorem 3.3

Let (U, A, F) be a soft context. Then

1) ADAI = ∅︀; ADAI = A.

2) a is independent if and only if either Ga = ∅︀ or if Ga ≠ ∅︀, then F+(Ga) = ∩gGaF(g) ≠ F(a).

Definition 3.4

Let (U, A, F) be a soft context. For aA, we say that the element a is generated by finitely many elements b1, b2, · · ·, bnA if F(a) = ∩bBF(b) for some B = {b1, b2, · · ·, bn} ⊆ A, and bB is called generator for a.

Example 3.5

In Example 3.2, for cA, a, b and d are generators for c.

Lemma 3.6

Let (U, A, F) be a soft context. For dAD, Gd = {gA | F(d) ⊊ F(g)} is the maximal set of generators.

Theorem 3.7

Let (U, A, F) be a soft context. Then every dependent element of A is generated by finitely many independent elements of A, that is, for each dAD, there exists BAI such that F+(B) = ∩bBF(b) = F(d).

Proof

Suppose that there is a dependent element d of A such that it can not be generated only by independent elements of A.

Put is not generated only by independent elements of A}. Then by hypothesis, is not empty. Furthermore, .

For the proof, assume that .

First, pick up one element in , say d1. Then since , Gd1 = {aA | F(d1) ⊊ F(a)} is not empty set and . So, we can pick up . Then obviously, F(d1) ⊊ F(d2).

Second, for , let us consider Gd2 = {aA | F(d2) ⊊ F(a)}. Then since and Gd2 is the maximal set of generators for d2, . Now, pick up . Then obviously, F(d2) ⊊ F(d3) and so, F(d1) ⊊ F(d2) ⊊ F(d3).

Repeating this process, after a finite number (n − 2), we get an element . Then it satisfies that F(d1) ⊊, · · · ⊊ F(dn−2) ⊊ F(dn−1) and .

Finally, since , we can pick up the last element . Then F(d1) ⊊ F(d2) ⊊ · · · ⊊ F(dn−1) ⊊ F(dn).

In the last step, since dn is the last element in , for Gdn = {aA | F(dn) ⊊ F(a)}, . So, the last element is generated by finitely many independent elements of A. From this fact and F(d1) ⊊, · · · ⊊ F(dn−2) ⊊ F(dn−1) ⊊ F(dn), we know that should be generated by finitely many independent elements of A. Consequently, is the empty set. So the proof is completed.

Theorem 3.8

Let (U, A, F) be a soft context. Then ∩aAIF(a) = ∅︀.

Proof

From Theorem 2.1 and Theorem 3.7, it follows F+(AI )∩ F+(AD) = F+(AI ) and ∩aAIF(a) = F+(AI) = F+(AI )∩ F+(AD) = F+(AIAD) = F+(A) = ∩aAF(a). Since the soft set (F,A) is pure, ∩aAIF(a) = ∅︀.

Theorem 3.9

Let (U, A, F) be a soft context. Put for AIA. Then

s(U,A,F)={SSAI}.
Proof

1) Take . Then from the theorem above, . It is obvious that . Take ; . Then clearly, .

2) Let Xs(U, A, F). Then, from (4) of Theorem 2.2, there exists BA such that X = F+(B). Let C = BAI and D = BAD. From B = CD and CD = ∅︀, it follows X = F+(B) = F+(CD) = F+(C) ∩ F+(D) = F+(C) ∩ (∩dDF(d)). So, from Theorem 3.7, for each dDAD, there exists EdAI such that F+(Ed) = ∩eEdF(e) = F(d). Put H = ∪dDEd. Then HAI and F+(H) = F+(∪dDEd) = ∩dDF+(Ed) = ∩dDF(d). It impliesX = F+(B) = F+(C) ∩ (∩dDF(d)) = F+(C) ∩ F+(H) = F+(CH) for CHAI. Finally, put ; then and . So the proof is completed.

For a formal context (U, A, I), let us define a soft set FI : AP(U) as follows FI (a) = {xU : (x, a) ∈ I}. Then (U, A, FI ) is a soft context. So, every formal context (U, A, I) induces a soft context (U, A, FI ). In this paper, we call (U, A, FI ) the associated soft context induced by a formal context (U, A, I).

Theorem 3.10

Let (U, A, I) be a formal context. Then for the associated soft context (U, A, FI ), s(U, A, FI) = {F+(B)|B is any subset of AI}.

Proof

For the associated soft context (U, A, FI ), from Theorem 3.9, it is obvious that X ∈ {F+(B)|B is any subset of AI} if and only if . So the fact is obtained.

In [1], for a formal context (U, A, I), The concepts of (U, A, I) are ordered by

(X1,B1)(X2,B2)X1X2(B1B2),

where (X1,B1), (X2,B2) are two concepts.

(X1,B1) is called a sub-concept of (X2,B2), and (X2,B2) is called a super-concept of (X1,B1). The ordered set of all concepts in (U, A, I) is denoted by L(U, A, I) and called the concept lattice of (U, A, I), where the infimum and supremum are defined by:

(X1,B1)(X2,B2)=(X1X2,(B1B2)**),(X1,B1)(X2,B2)=((X1X2)**,B1B2).

Theorem 3.11 ( [15])

Let (U, A, I) be a formal context. Then

L(U,A,I)={(X,FI-(X))|Xisanyelementofs(U,A,FI)}.

By Theorem 3.10 and Theorem 3.11, the following theorem is obtained:

Theorem 3.12

Let (U, A, I) be a formal context. Then

L(U, A, I) = {(F+(B), FF+(B))|B is any subset of AI in (U, A, FI )}.

4. Conclusions

We introduced the notion of independent and dependent attributes in a given soft context. Then we showed that every dependent attribute is generated by some independent attributes in a given soft context. In the next research, we will study special properties of the independent attributes, and characterizations for soft concepts and soft concept lattice by using a nonempty finite set of attributes. Furthermore, the results of this paper will be applied to the reduction of formal concepts and the research of the formal concept analysis.

References
  1. Wille, R (1982). Restructuring lattice theory: an approach basedon hierarchies of concepts. Ordered Sets. Dordrecht: Springer, pp. 445-470 https://doi.org/10.1007/978-94-009-7798-315
    CrossRef
  2. Chen, LY, Huang, T, Song, ZM, and Pei, Z (2008). Formal-concept analysis based on set-valued mapping. ChineseQuarterly Journal of Mathematics. 23, 390-396.
  3. Ganter, B, and Wille, R (1999). Formal Concept Analysis: Mathematical Foundations. Springer, Berlin.
  4. Jin, J, Qin, K, and Pei, Z (2006). Reduction-based approaches towards constructing Galois (concept) lattices. RoughSets and Knowledge Technology. Heidelberg: Springer, pp. 107-113 https://doi.org/10.1007/1179513116
    CrossRef
  5. Wille, R (1992). Concept lattices and conceptual knowledge systems. Computers & Mathematics with Applications. 23, 493-515. https://doi.org/10.1016/0898-1221(92)90120-7
    CrossRef
  6. Belohlavek, R (2004). Concept lattices and order in fuzzy logic. Annals of Pure and Applied Logic. 128, 277-298. https://doi.org/10.1016/j.apal.2003.01.001
    CrossRef
  7. Medina, J, Ojeda-Aciego, M, and Ruiz-Calvino, J (2009). Formal concept analysis via multi-adjoint concept lattices. Fuzzy Sets and Systems. 160, 130-144. https://doi.org/10.1016/j.fss.2008.05.004
    CrossRef
  8. Pei, Z, Ruan, D, Meng, D, and Liu, Z (2013). Formal concept analysis based on the topology for attributes of a formal context. Information Sciences. 236, 66-82. https://doi.org/10.1016/j.ins.2013.02.027
    CrossRef
  9. Wang, L, Liu, X, and Cao, J (2010). A new algebraic structure for formal concept analysis. Information Sciences. 180, 4865-4876. https://doi.org/10.1016/j.ins.2010.08.020
    CrossRef
  10. Yao, Y, and Zhao, Y (2008). Attribute reduction in decision theoretic rough set models. Information Sciences. 178, 3356-3373. https://doi.org/10.1016/j.ins.2008.05.010
    CrossRef
  11. Zhang, W, Wei, L, and Qi, J (2005). Attribute reduction theory and approach to concept lattice. Science in China Series F: Information Sciences. 48, 713-726. https://doi.org/10.1360/122004-104
    CrossRef
  12. Molodtsov, D (1999). Soft set theory: first results. Computers & Mathematics with Applications. 37, 19-31. https://doi.org/10.1016/S0898-1221(99)00056-5
    CrossRef
  13. Ali, MI, Feng, F, Liu, X, Min, WK, and Shabir, M (2009). On some new operations in soft set theory. Computers & Mathematics with Applications. 57, 1547-1553. https://doi.org/10.1016/j.camwa.2008.11.009
    CrossRef
  14. Maji, PK, Biswas, R, and Roy, A (2003). Soft set theory. Computers & Mathematics with Applications. 45, 555-562. https://doi.org/10.1016/S0898-1221(03)00016-6
    CrossRef
  15. Min, WK, and Kim, YK (2019). Soft concept lattice for formal concept analysis based on soft sets: theoretical foundations and applications. Soft Computing. 23, 9657-9668. https://doi.org/10.1007/s00500-018-3532-z
    CrossRef
Biography

Won Keun Min received the M.S. and the Ph.D. degrees in mathematics from Korea University, Seoul, Korea in 1983 and 1987, respectively. He is currently a professor in the Department of Mathematics, Kangwon National University. His research interests include general topology, fuzzy topology and soft set theory.

E-mail: wkmin@kangwon.ac.kr