Quantified Concept-Forming Operators?

Abstract

Generalized quantifiers allow to decrease the outermost character of the universal and existential quantifiers. Concept-forming operators in Formal Concept Analysis have a universal character. As a consequence, some noise in the data can dramatically alter the final result. This paper introduces a first approximation to quantified formal-concept operators with the main goal of decreasing this universal character and be less sensitive to noisy data.

Keywords

• Concept lattices
• fuzzy sets
• general quantifier
• adjoint triples

Introduction

Formal Concept Analysis (FCA), introduced by Ganter and Wille in the eighties, has become an appealing research topic both from theoretical [ 18, 22 ] and applicative perspectives [ 1, 16, 17, 19, 24, 26 ]. Specifically, FCA is a mathematical tool in charge of extracting information from databases containing a set of attributes A and a set of objects B related to each other by a binary relation R ⊆ A × B. These pieces of information are called concepts and a hierarchy can be established on them providing an algebraic structure called concept lattice. From the concept lattice, a mathematical development for the conceptual data analysis and processing of knowledge can be carried out. Soon after its introduction, a number of different approaches for its generalization were introduced [ 2, 5, 7 ]. One of the most general fuzzy approaches is the multi-adjoint concept lattice [ 20, 21, 23 ], which will be considered in this paper. The multi-adjoint concept lattice framework considers different adjoint triples in the definition of the concept-forming operations, providing interesting properties [ 11, 13 ].

Generalized quantifiers [ 6, 8, 9, 14, 15, 25 ] have been proposed in order to solve the theoretical drawback of the usual universal and existencial quantifiers. Specifically, these quantifiers try to introduce intermeditate quantifiers between the existential quantifier, where just one element is enough to result the truth, and the universal quantifier, where all elements have to fulfill a given formula in order to result the truth. As a consequence, more proper quantifiers can be used in applications where the outermost quantifiers are very restrictive. For example, notions as “Most” or “Many” can be implemented and so, considered in applications.

This paper is inspired by [ 9, 25 ] in order to develop different notions and results on multi-adjoint concept lattices, based on the monadic quantifiers of type h1i determined by fuzzy measures [ 15 ]. Specifically, we have introduced the definition of generalized quantifier in this general framework as a natural extension, which also satisfies the main properties. Moreover, we have used the extended definition to present a generalization of the usual fuzzy concept-forming operators [ 3, 4, 7, 23 ] in order to decrease the drastic (universal) character of these operators, which are very sensitive to noise data. As a consequence, the new introduced operators offer a complementary alternative to the original conceptforming operators to obtain more robust, stable and valuable information from datasets. Although the new operators generalize the original one, they do not form an antitone Galois connection, in general. Therefore, different sufficient conditions and alternative definitions will be studied in the future in order to ensure Galois connections.

The paper is organized as follows. In the second section, we recall the theory related to multi-adjoint concept lattices. In the third section, we generalize the notion of generalized quantifier by using adjoint triples. In addition, we use the extended definition in order to present a generalization of the usual fuzzy concept-forming operators. In the last section, we list some directions where our approach could be further developed. 2

Preliminaries

To begin with, we will recall the notion of adjoint triple which play an important role in this work. Adjoint triples arise as a generalization of triangular norms and their residuated implications. These operators are the basic calculus operators in different frameworks such as multi-adjoint logic programming, multi-adjoint fuzzy relation equations, multi-adjoint fuzzy rough sets and multi-adjoint concept lattices. It is worth noting that these operators increase the flexibility of the mentioned frameworks, since the conjunctors are not required to be either commutative or associative.

Definition 1. Let (P1, ≤1), (P2, ≤2), (P3, ≤3) be posets and & : P1 × P2 → P3, . : P3 × P2 → P1, - : P3 × P1 → P2 be mappings. We say that (&, ., -) is an adjoint triple with respect to (P1, ≤1), (P2, ≤2), (P3, ≤3) if the following double equivalence is satisfied: x ≤1 z . y iff x & y ≤3 z iff y ≤2 z - x for all x ∈ P1, y ∈ P2 and z ∈ P3. The previous double equivalence is called adjoint property.

The following properties are obtained straightforwardly from the adjoint property [ 10, 12 ].

Proposition 1. Let (&, ., -) be an adjoint triple with respect to the posets (P1, ≤1), (P2, ≤2) and (P3, ≤3), then the following properties are satisfied: 1. & is order-preserving on both arguments. 2. . and - are order-preserving on the first argument and order-reversing on the second argument. 3. ⊥1 & y = ⊥3, >3 . y = >1, for all y ∈ P2, when (P1, ≤1, ⊥1, >1) and (P3, ≤3, ⊥3, >3) are bounded posets. 4. x & ⊥2 = ⊥3 and >3 - x = >2, for all x ∈ P1, when (P2, ≤2, ⊥2, >2) and (P3, ≤3, ⊥3, >3) are bounded posets. 5. z - ⊥1 = >2 and z . ⊥2 = >1, for all z ∈ P3, when (P1, ≤1, ⊥1, >1) and (P2, ≤2, ⊥2, >2) are bounded posets.

Once we have introduced the notion of adjoint triple, we are in a position to present multi-adjoint concept lattices. The philosophy of the multi-adjoint paradigm was applied to the formal concept analysis in order to obtain a new general approach framework that could conveniently accommodate different fuzzy approaches given in the literature. The mentioned general approach is called multi-adjoint concept lattices and their main notions will be recalled below [ 23 ]. Definition 2. A multi-adjoint frame is a tuple (L1, L2, P, &1, . . . , &n) where i (L1, 1) and (L2, 2) are complete lattices, (P, ≤) is a poset and (&i, . , -i) is an adjoint triple with respect to L1, L2, P , for all i ∈ {1, . . . , n}. Definition 3. Let (L1, L2, P, &1, . . . , &n) be a multi-adjoint frame, a context is a tuple (A, B, R, σ) such that A and B are non-empty sets, R is a P -fuzzy relation R : A×B → P and σ : A×B → {1, . . . , n} is a mapping which associates any element in A × B with some particular adjoint triple in the frame.

After fixing a multi-adjoint frame and a context for that frame, the conceptforming operators are denoted as ↑ : LB 1 −→ L2B and are 2 −→ L1A and ↓ : LA defined, for all g ∈ L2B, f ∈ L1A and a ∈ A, b ∈ B, as g↑(a) = ^

b∈B f ↓(b) = ^ a∈A

R(a, b) .σ(a,b) g(b) R(a, b) -σ(a,b) f (a) (1) (2)

A multi-adjoint concept is a pair hg, f i satisfying that g ∈ L2B, f ∈ L1A and that g↑ = f and f ↓ = g. A hierarchy can be defined on the whole set of multiadjoint concepts, which gives rise to the concept lattice.

Definition 4. Given a multi-adjoint frame (L1, L2, P, &1, . . . , &n) and a context (A, B, R, σ), a multi-adjoint concept lattice is the set

M = {hg, f i | g ∈ L2B, f ∈ L1A, g↑ = f, f ↓ = g} in which the ordering is defined by hg1, f1i (equivalently f2 1 f1). hg2, f2i if and only if g1 2 g2

Formal-concept operators with generalized quantifiers

This section will generalize the notion of generalized quantifier given in [ 25 ] by using adjoint triples. Specifically, we will consider adjoint triples defined on the complete lattice ([ 0, 1 ], ≤) assuming that their conjunctors have 1 as left and right identity element.

Before presenting the notion of quantifier, we need to present the concept of fuzzy measure invariant with respect to the cardinality.

Definition 5. Let U be a finite universe and P(U ) be the powerset of U . We will say that the mapping μ : P(U ) → [ 0, 1 ] is a fuzzy measure, if it is an increasing mapping satisfying that μ(∅) = 0 and μ(U ) = 1. We will say that the fuzzy measure μ is invariant with respect to the cardinality, if the following condition holds:

If |A| = |B| then μ(A) = μ(B), for all A, B ∈ P(U ) where | · | denotes the cardinality of a set.

An example of fuzzy measure invariant with respect to the cardinality is given by the mapping μrc : P(U ) → [ 0, 1 ] defined as μrc(A) = |A| , for all A ∈ P(U ). |U| Notice that, if ϕ : [ 0, 1 ] → [ 0, 1 ] is an increasing mapping such that ϕ(0) = 0 and ϕ(1) = 1, then the mapping μϕ : P(U ) → [ 0, 1 ] defined as μϕ(A) = ϕ(μrc(A)), for all A ∈ P(U ), is also a fuzzy measure invariant with respect to the cardinality. The former fuzzy measure μrc is called relative cardinality whereas the latter fuzzy measure μϕ is called relative cardinality modified by ϕ or simply modified relative cardinality. Both fuzzy measures were exemplified in [ 25 ]. Definition 6. Let U be a non-empty finite universe, F(U ) = [ 0, 1 ]U be the set of fuzzy sets of U on [ 0, 1 ], P(U ) be the powerset of U , μ : P(U ) → [ 0, 1 ] be a fuzzy measure invariant with respect to the cardinality and (&, ., -) be an adjoint triple w.r.t ([ 0, 1 ], ≤) such that x & 1 = 1 & x = x, for all x ∈ [ 0, 1 ]. • A mapping Qμ : F(U ) → [ 0, 1 ] defined, for all C ∈ F(U ), as:

is called right quantifier determined by the fuzzy measure μ. • A mapping μQ : F(U ) → [ 0, 1 ] defined, for all C ∈ F(U ), as: is called left quantifier determined by the fuzzy measure μ. (3) (4)

From now on, all results will be formulated with respect to a right quantifier determined by a fuzzy measure μ. For that reason, the right quantifier will be called simply quantifier. Notice that, all presented results can be translated analogously for a left quantifier.

The following proposition shows that the universal and existential quantifiers can be obtained from Definition 6 considering the minimum and maximum fuzzy measures μ∀ and μ∃, respectively, which are defined as follows: μ∀(D) = Proposition 2. Given a non-empty finite universe U , the quantifiers Q∀ and Q∃ determined by the minimum and maximum fuzzy measures μ∀ and μ∃, respectively, we have that Q∀ and Q∃ represent the universal and existencial quantifiers. That is, for all C ∈ F(U ), the following equalities are satisfied: Q∀(C) = ^ C(u)

u∈U Q∃(C) = _ C(u)

u∈U

From a computational point of view, the notion of quantifier given in Equation (3) of Definition 6 is not suitable. This fact is due to the computation over all sets from P(U ) \ {∅} is required. In order to compute the quantifier in a more efficient way, we propose an alternative computation procedure which makes use of the property of being invariant with respect to the cardinality of fuzzy measures.

Theorem 1. Let U = {u1, . . . , un} be a universe, with |U | = n, and Qμ be a quantifier determined by a fuzzy measure μ invariant with respect to the cardinality. Then,

Corollary 1. Let U = {u1, . . . , un} be a universe, ϕ : [ 0, 1 ] → [ 0, 1 ] be an increasing mapping such that ϕ(0) = 0, ϕ(1) = 1 and μ be a fuzzy measure built from the relative cardinality, by using ϕ. Then,

Qμ(C) = n _ C(uπ(i)) & ϕ(i/n), i=1

C ∈ F(U )

After introducing a generalization of the definition of generalized quantifier in the multi-adjoint concept lattices framework and showing its main properties, we will focus on using the extended definition to present a generalization of the usual fuzzy concept-forming operators.

Definition 7. Given a multi-adjoint frame and a context for that frame, μA, μB two fuzzy measures on A and B, respectively, which are invariant with respect to the cardinality and QA, QB two quantifiers determined by the fuzzy measures μA and μB, respectively, the quantified concept-forming operators are denoted as ↑QA : [ 0, 1 ]B −→ [ 0, 1 ]A and ↓QB : [ 0, 1 ]A −→ [ 0, 1 ]B, where [ 0, 1 ]B and [ 0, 1 ]A denote the set of fuzzy subsets g : B → [ 0, 1 ] and f : A → [ 0, 1 ], respectively, and are defined, for all g ∈ [ 0, 1 ]B, f ∈ [ 0, 1 ]A and a ∈ A, b ∈ B, as: g↑QB (a) = f ↓QA (b) = _ _ X∈P(B)\{∅} b∈X Y ∈P(A)\{∅} a∈Y ^ R(a, b) .σ(a,b) g(b) ^ R(a, b) -σ(a,b) f (a) ! ! & μB(X) & μA(Y )

Applying Corollary 1, we obtain the following characterization of the quantified concept-forming operators, where the fuzzy measures μA and μB are defined from two fuzzy sets ϕA and ϕB, as follows: (5) (6) (7) (8) for all subset {a1, ..., aj } ⊆ A, {b1, ..., bi} ⊆ B, with |A| = m and |B| = n. Proposition 3. In the framework of Definition 7, the quantified concept-forming operators ↑QA : [ 0, 1 ]B −→ [ 0, 1 ]A and ↓QB : [ 0, 1 ]A −→ [ 0, 1 ]B, satisfy: n g↑QB (a) = _ i=1 m f ↓QA (b) = _ j=1

R(a, bπ(i)) .σ(a,bπ(i)) g(bπ(i)) & ϕB(i/n) R(aλ(j), b) -σ(aλ(j),b) f (aλ(j)) & ϕA(j/m) μA({a1, ..., aj }) = ϕA(j/m) μB({b1, ..., bi}) = ϕB(i/n) for all g ∈ [ 0, 1 ]B, f ∈ [ 0, 1 ]A and a ∈ A, b ∈ B, where π and λ are permutations such as:

R(a, bπ(i+1)) .σ(a,bπ(i+1)) g(bπ(i+1)) ≤ R(a, bπ(i)) .σ(a,bπ(i)) g(bπ(i)) R(aλ(j+1), b) -σ(aλ(j+1),b) f (aλ(j+1)) ≤ R(aλ(j), b) -σ(aλ(j),b) f (aλ(j))

The next result shows that the quantified concept-forming operators ↑QA and ↓QB form an antitone Galois connection when the quantifiers QA and QB are determined by the minimum fuzzy measure μ∀.

Proposition 4. Given the quantifiers Q∀A and Q∀B determined by the minimum fuzzy measure μ∀ on the universes A and B, respectively, then the pair (↑Q∀B , ↑Q∀A ) is an antitone Galois connection.

However, this result does not need to be satisfied for arbitrary quantifiers. Hence, it would be interesting to study sufficient conditions to ensure that the pair (↑QB , ↑QA ) be an antitone Galois connection. 4

Conclusions and future work

In this paper, we have introduced the monadic quantifiers of type h1i determined by fuzzy measures [ 15 ] in the general framework of multi-adjoint lattices. Moreover, we have proven that the new definitions also have the universal and existential quantifiers as particular cases. The second important result is the simplification of the generalized quantifier definition taking into account that fuzzy measures are invariant with respect to the cardinality. This result allows to develop more simple and efficient proofs in this framework. Finally, the natural and simple expressions of the quantified concept-forming operators have been presented, and we have also shown that they form a Galois connection when the minimum fuzzy measure is considered. However, this is not true in general. Hence, in the future, sufficient conditions or new definitions will be studied in order to provide Galois connections.

References

1. C. Alcalde , A. Burusco , H. Bustince , A. Jurio , and J. A. Sanz . Evolution in time of L-fuzzy context sequences . Information Sciences , 326 : 202 - 214 , 2016 .

2. L. Antoni , S. Krajci , O. Kridlo , B. Macek , and L. Piskova´. On heterogeneous formal contexts . Fuzzy Sets and Systems , 234 : 22 - 33 , 2014 .

3. L. Antoni , S. Krajˇci, and O. Kr ´ıdlo. Constraint heterogeneous concept lattices and concept lattices with heterogeneous hedges . Fuzzy Sets and Systems , 303 : 21 - 37 , 2016 .

4. R. Bˇelohla´vek. Lattices of fixed points of fuzzy Galois connections . Mathematical Logic Quartely , 47 ( 1 ): 111 - 116 , 2001 .

5. R. Bˇelohl´avek, T. Funiokova, and V. Vychodil . Galois connections with hedges . In Proc. IFSA 2005 World Congress, volume II , pages 1250 - 1255 . Springer, 2005 .

6. P. Bosc , L. Lietard , and O. Pivert . Flexible database querying and the division of fuzzy relations . Scientia Iranica , 2 ( 4 ):-, 1996 .

7. A. Burusco and R. Fuentes-Gonza´lez. Construction of the L-fuzzy concept lattice . Fuzzy Sets and Systems , 97 ( 1 ): 109 - 114 , 1998 .

8. N. Cao , M. Holˇcapek, and M. Sˇtˇepniˇcka. Extensions of fuzzy relational compositions based on generalized quantifiers . Fuzzy Sets and Systems , 339 : 73 - 98 , 2018 . Theme: Algebra and Set Theory .

9. N. Cao , M. Stepnicka , and M. Burda . Fuzzy quantifiers and compositions of partial fuzzy relations employing dragonfly algebras . In 2019 IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2019 , New Orleans , LA, USA, June 23-26, 2019 , pages 1 - 6 . IEEE, 2019 .

10. M. E. Cornejo , J. Medina , and E. Ram ´ırez- Poussa . A comparative study of adjoint triples . Fuzzy Sets and Systems , 211 : 1 - 14 , 2013 .

11. M. E. Cornejo , J. Medina , and E. Ram ´ırez-Poussa. Attribute reduction in multiadjoint concept lattices . Information Sciences , 294 : 41 - 56 , 2015 .

12. M. E. Cornejo , J. Medina , and E. Ram ´ırez-Poussa. Multi-adjoint algebras versus non-commutative residuated structures . International Journal of Approximate Reasoning , 66 : 119 - 138 , 2015 .

13. M. E. Cornejo , J. Medina , and E. Ram ´ırez-Poussa. Characterizing reducts in multi-adjoint concept lattices . Information Sciences , 422 : 364 - 376 , 2018 .

14. M. Delgado , D. Sa´nchez, and M. A. Vila . Fuzzy cardinality based evaluation of quantified sentences . International Journal of Approximate Reasoning , 23 ( 1 ): 23 - 66 , 2000 .

15. A. Dvoˇra ´k and M. Holˇcapek. L-fuzzy quantifiers of type h1i determined by fuzzy measures . Fuzzy Sets and Systems , 160 ( 23 ): 3425 - 3452 , 2009 . Theme: Computer Science.

16. A. Formica . Concept similarity in fuzzy formal concept analysis for semantic web . International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems , 18 ( 2 ): 153 - 167 , 2010 .

17. B. Galitsky and J. D. L. Rosa . Concept-based learning of human behavior for customer relationship management . Information Sciences , 181 ( 10 ): 2016 - 2035 , 2011 .

18. O. Kr´ıdlo, S. Krajˇci, and L. Antoni . Formal concept analysis of higher order . International Journal of General Systems , 45 : 116 - 134 , 2016 .

19. B. Li , X. Sun , and H. Leung . Combining concept lattice with call graph for impact analysis . Advances in Engineering Software , 53 ( 0 ): 1 - 13 , 2012 .

20. J. Medina and M. Ojeda-Aciego. Multi-adjoint t-concept lattices . Information Sciences , 180 ( 5 ): 712 - 725 , 2010 .

21. J. Medina and M. Ojeda-Aciego . On multi-adjoint concept lattices based on heterogeneous conjunctors . Fuzzy Sets and Systems , 208 : 95 - 110 , 2012 .

22. J. Medina , M. Ojeda-Aciego , J. Po´cs, and E. Ram ´ırez-Poussa. On the DedekindMacNeille completion and formal concept analysis based on multilattices . Fuzzy Sets and Systems , 303 : 1 - 20 , 2016 .

23. J. Medina , M. Ojeda-Aciego , and J. Ruiz-Calvin˜o. Formal concept analysis via multi-adjoint concept lattices . Fuzzy Sets and Systems , 160 ( 2 ): 130 - 144 , 2009 .

24. J. M. Rodr ´ıguez-Jim´enez , P. Cordero, M. Enciso , and A. Mora . Data mining algorithms to compute mixed concepts with negative attributes: an application to breast cancer data analysis . Mathematical Methods in the Applied Sciences , 39 ( 16 ): 4829 - 4845 , 2016 .

25. M. Sˇtˇepniˇcka and M. Holˇcapek . Fuzzy relational compositions based on generalized quantifiers . In A. Laurent , O. Strauss , B. Bouchon-Meunier , and R. R . Yager, editors, Information Processing and Management of Uncertainty in KnowledgeBased Systems , pages 224 - 233 , Cham, 2014 . Springer International Publishing.

26. F. J. Valverde-Albacete , J. M. Gonza ´lez- Calabozo , A. Pen˜as, and C. Pel´aezMoreno. Supporting scientific knowledge discovery with extended, generalized formal concept analysis . Expert Systems with Applications , 44 : 198 - 216 , 2016 .