key: cord-0047129-8eam2s2r
authors: Benítez-Caballero, M. José; Medina, Jesús; Ramírez-Poussa, Eloísa
title: Fuzzy FCA Attribute Reduction Properties in Rough Set Theory
date: 2020-06-10
journal: Rough Sets
DOI: 10.1007/978-3-030-52705-1_24
sha: 657b5b00931402537184ecf5659d90f6cafc485f
doc_id: 47129
cord_uid: 8eam2s2r

Formal concept analysis and rough set theory are two of the most important mathematical tools for the treatment of information collected on relational systems. In particular, the idea of reducing the size of a database is widely studied in both theories separately. There are some papers that studied the reduction of a formal context by means of reducts from rough set. In this paper, we are focused in the reduction obtained in an information system considering the FCA reduction mechanism.

Databases have been used in order to collect and store information in many fields of the everyday life as medicine, industry, criminology and more. The importance of databases has led to the development of mathematical tools for their study and management. Two powerful and useful mathematical tools are Formal Concept Analysis (FCA) [11] and Rough Set Theory (RST) [14] . Moreover, these two frameworks can be connected, among other ways, through the way in which databases are represented. Relational systems are composed by a set of attributes, a set of objects and a relationship between them.

One of the most important goal in both theories is the reduction of the size of databases. In order to do that, the notion of reduct arose. As a general definition, a reduct is a minimal subset of attributes keeping the original information. In a FCA framework, a reduct is a subset of attributes with which an isomorphic lattice to the original one is constructed [6, 9, 10] . In the case of RST, the minimal subset of attributes keeping the indiscernibility objects is called a reduct [8, 16, 17] . There are some papers connecting the reduction mechanisms in Partially supported by the the 2014-2020 ERDF Operational Programme in collaboration with the State Research Agency (AEI) in projects TIN2016-76653-P and PID2019-108991GB-I00, and with the Department of Economy, Knowledge, Business and University of the Regional Government of Andalusia. in project FEDER-UCA18-108612, and by the European Cooperation in Science & Technology (COST) Action CA17124 both theories. A new reduction mechanism in FCA by means of reducts of RST is proposed in [2] . In the aforementioned paper, the results and properties are developed in a classical environment. Additionally, this study was extended in paper [3] to a fuzzy environment. Furthermore, a comparative study with other mechanism is presented. In these papers, the process starts in a context, an associated information system is constructed and the reductions in such information system are computed. Then, the lattice of reduced context with the calculated reducts is built. Therefore, these reduction mechanism provides a reduction in FCA considering the reducts of RST.

On the other hand, a reduction mechanism in an information system considering the FCA philosophy is studied in [1] . In this paper, we will define a fuzzy formal context and frame associated with an information system and the fuzzy environment for reduction in the associated context will be applied. Moreover, different properties will be studies in order to improve the FCA classification theorems in the RST framework.

Since this paper is focused on extend the study presented in [1] , we recall the notions and results needed in Sect. 2. After that, the main contributions are presented in Sect. 3. Finally, in Sect. 4, we summarize the results in the conclusions and we present our future work.

RST and FCA are the two mathematical tools considered in this paper in order to reduce the size of a relational database. Also, the relation between the reduction procedure in these frameworks is studied. Due to this fact, the notions and results needed from these two environments will be recalled in this section.

Rough Set Theory was developed in order to treat and manage incomplete information. In this framework, information systems and decision systems are used to present the data [14, 15] . These systems are composed by a set of objects, a set of attributes and a relation between them. In the particular case of the decision system, an specific attribute is considered to make an action over the objects. Since information systems are the only one considered in this paper, its definition is recalled:

. , x n } and the set of attributes A = {a 1 , a 2 , . . . , a m } are finite and non-empty sets. Each a ∈ A corresponds to a mappingā : U → V a , where V a is the value set of the attribute a over U .

Moreover, for every subset D of A, the D-indiscernibility relation, Ind(D), is defined by the following equivalence relation:

where each equivalence class is written as

The following definition presents a useful tool for selecting the attributes which discern two objects [15] , the discernibility matrix.

Definition 2. Given an information system (U, A), its discernibility matrix is a matrix with order |U | × |U |, denoted by M A , in which the element M A (x, y) for each pair of objects (x, y) is defined by:

Moreover, in order to generalize this notions to a fuzzy environment, a fuzzy indiscernibility relationship can be considered to compare the objects instead of a classical one. This indiscernibility relation can be defined over any poset P , that is, R : U × U → P , as it was introduced in [8] . Due to the study if this paper is focused on the properties of the fuzzy FCA reduction to RST, the interval [0, 1] will be considered as the poset used to define the indiscernibility relation.

From this point forward, we are going to consider the definition of the information system presented in Definition 1 together with the fuzzy indiscernibility relation R : U × U → [0, 1] defined as:

for every pair of objects x i , x j ∈ U , where @ : [0, 1] n → [0, 1] is an aggregation operator and R a k : U × U → [0, 1] is a tolerance relation with respect to the attribute a k , for all k ∈ {1, . . . , n}.

The considered operators in order to define the concept-forming operators are the adjoint triples, which are generalizations of a triangular norm and its residuated implication [12] . Definition 3. Let (P 1 , ≤ 1 ), (P 2 , ≤ 2 ), (P 3 , ≤ 3 ) be posets and & : P 1 × P 2 → P 3 , : P 3 × P 2 → P 1 , : P 3 × P 1 → P 2 be mappings, then (&, , ) is an adjoint triple with respect to P 1 , P 2 , P 3 if the following double equivalence holds:

for all x ∈ P 1 , y ∈ P 2 and z ∈ P 3 . This double equivalence is called adjoint property.

Next, we will present the boundaries properties verified by operators of an adjoint triple.

Given an adjoint triple (&, , ) with respect to the posets (P 1 , ≤ 1 , ⊥ 1 , 1 ), (P 2 , ≤ 2 , ⊥ 2 , 2 ) and (P 3 , ≤ 3 , ⊥ 3 , 3 ), the following boundary conditions are hold:

The following result presents a relation between boundary conditions which was proved in [4] .

have that the following equivalence is provided:

In the concept lattice settings, we need to consider that (P 1 , ≤ 1 ) and (P 2 , ≤ 2 ) are complete lattices [13] . In the following, we are going to recall the notion of multi-adjoint frame.

A multi-adjoint frame L is a tuple:

Multi-adjoint frames are denoted as (L 1 , L 2 , P, &1, . . . , &n).

Given a frame, a multi-adjoint context is a tuple consisting of sets of objects, attributes and a fuzzy relation among them; in addition, the multi-adjoint approach also includes a function which assigns an adjoint triple to each pair of objects and attributes. Given a multi-adjoint frame and a context for that frame, the conceptforming operators are denoted as ↑σ :

1 denote the set of fuzzy subsets g : B → L 2 and f : A → L 1 , respectively, and are defined, for all g ∈ L B 2 , f ∈ L A 1 and a ∈ A, b ∈ B, as:

These two arrows form a Galois connection [13] . Hence, the notion of concept is defined as usual: a multi-adjoint concept is a pair g, f satisfying that g ∈ L B 2 , f ∈ L A 1 and that g ↑σ = f and f ↓ σ = g; with ( ↑σ , ↓ σ ) being the Galois connection defined above.

Given g ∈ L B 2 (resp. f ∈ L A 1 ), we will call the concept g ↑σ↓ σ , g ↑σ (resp. f ↓ σ , f ↓ σ ↑σ ) the concept generated by g (resp. f ). Definition 6. The multi-adjoint concept lattice associated with a multi-adjoint frame (L 1 , L 2 , P, &1, . . . , &n) and a context (A, B, R, σ) is the set

in which the ordering is defined by

The ordering just defined above provides M with the structure of a complete lattice [13] . From now on, in order to simplify the notation, we will write ↑ and ↓ instead of ↑σ and ↓ σ , respectively.

A theory for attribute reduction in multi-adjoint concept lattices will be introduced. From now on, a multi-adjoint frame (L 1 , L 2 , P, &1, . . . , &n) and a context (A, B, R, σ) will be fixed.

The following definition presents the most natural extension of a consistent set in the multi-adjoint framework, keeping the definitions considered in Rough Set Theory [14] .

The core of (A, B, R, σ) is the intersection of all the reducts of (A, B, R, σ).

The main idea in attribute reduction in formal concept analysis is to classify the attributes from the irreducible elements in the concept lattice. Therefore, the definition of irreducible element of a lattice must be introduced. is called meet-irreducible (∧-irreducible) element of L. Condition (2) is equivalent to 2 . If x < y and x < z, then x < y ∧ z, for all y, z ∈ L.

Hence, if x is ∧-irreducible, then it cannot be represented as the infimum of strictly greatest elements.

A join-irreducible (∨-irreducible) element of L is defined dually.

A characterization of the meet-irreducible elements of a multi-adjoint concept lattice is introduced in this section. A similar result can be given to the joinirreducible elements.

Hence, we will consider a multi-adjoint concept lattice (M, ) associated with a multi-adjoint frame (L 1 , L 2 , P, &1, . . . , &n), a context (A, B, R, σ) , where L 1 , L 2 , P , A and B are finite and the following specific family of fuzzy subsets of L A 1 :

For each a ∈ A, the fuzzy subsets of attributes φ a,x ∈ L A 1 defined, for all x ∈ L 1 , as

will be called fuzzy-attributes. The set of all fuzzy-attributes will be denoted as

Note that these mappings are generalizations of the crisp attributes and they were also assumed in the proof of representation theorem of several fuzzy concept lattices.

Once the technical results are introduced, the characterization of the ∧irreducible elements of multi-adjoint concept lattices can be proven. This theorem shows that the ∧-irreducible elements are concepts generated by fuzzyattributes and no more concepts can be ∧-irreducible elements.

Theorem 1 [5] . The set of ∧-irreducible elements of M, M F (A, B, R, σ), is:

where is the maximum element in L 2 and g : B → L 2 is the fuzzy subset defined as g (b) = , for all b ∈ B.

The following definition presents a notion needed to classify the attributes of a context by means of the attributes used to generate a concept.

Given a multi-adjoint frame (L 1 , L 2 , P, &1, . . . , &n), a context (A, B, R, σ) associated with the concept lattice (M, ) and a concept C of (M, ), the set of attributes generating C is defined as the set:

a,x , φ ↓↑ a,x = C} As in this paper we are using the philosophy of fuzzy FCA in order to reduce the set of attributes, we will need some results that characterize the attributes from the meet-irreducible elements of the multi-adjoint concept lattice. The results presented are an adaptation of the attribute classification theorems introduced in [5] , by using the Definition 10. This improvement in results simplifies the notation and facilitates its application. The following result characterizes the absolutely necessary attributes, by means of Definition 10.

Theorem 2 [7] . Given an attribute a ∈ A, then a ∈ C f if and only if there exists a meet-irreducible concept C of (M, ) satisfying that a ∈ Atg(C) and card(Atg(C)) = 1.

Finally, the next proposition shows the characterization of the absolutely unnecessary attributes considering the attributes generating a concept. To this group belong those attributes that are neither absolutely necessary nor relatively necessary.

Theorem 3 [7] . Given an attribute a ∈ A, then a ∈ I f if and only if, for any C ∈ M F (A), a / ∈ Atg(C), or if a ∈ Atg(C) then A \ Atg(C) ∪ {a} is not a consistent set.

This section will recall some notions and results presented in [1] and will study some properties of the attribute reduction of an information system provided by the FCA mechanism. First of all, we define a formal context from an information system, due to the fact that we are starting in a rough set framework.

Definition 11. Given an information system (U, A) and the indiscernibility relation R : U × U → L defined on (U, A), the associated fuzzy context is the context (U, U, R).

Usually, L is the unit interval, although it can be, for example, a non-linear lattice or a granularity of the unit interval, such as [0, 1] = {0, 1 /100, . . . , 99 /100, 1}. Additionally, we need to fixe an associated framework (L 1 , L 2 , P, &1, . . . , &n). In this case, the lattices L 1 and L 2 should be equal since they will represent the truth values associated with the elements of the same set. Moreover, we will need the adjoint conjunctors &i, for all i ∈ {1, . . . , n}, satisfy the boundary condition with the top element:

Although this condition may seem very strict, there are really many adjoint triples that satisfy it, like t-norms (e.g., Gödel, Lukasiewicz and product) and other more general operators such as x & y = x 2 · y.

Furthermore, since Proposition 2 will be used later, we also need that L 1 = P . As a consequence, the sets L 1 , L 2 , P must be equal and depending on the truth values set considered in the indiscernibility relation R. In this paper, we will consider linear lattices.

The following example shows how to obtain an associated fuzzy context from a given information system. This example will be used in order to illustrate the properties presented in this paper. Example 1. In this example, we will consider the information system (U, A) presented in [1] , composed of the set of objects U = {x 1 , x 2 , x 3 , x 4 , x 5 }, the set of attributes A = {a 1 , a 2 , a 3 , a 4 } and the following table showing the relation between attributes and objects, by a truth value in [0, 1] 100 : In order to build the discernibility matrix needed to define the relation in the context, we will consider the following fuzzy tolerance relation between objects for any attribute a i ∈ A:

Then, we will take into account the aggregation operator @(l 1 , l 2 .l 3 , l 4 ) = 1 6 (l 1 + l 2 + 2(l 3 + l 4 )) to compute the values of the discernibility relation, which compares every couple of objects x, y ∈ U as follows:

Therefore, the following discernibility matrix is obtained: In order to stress the usefulness of the proposed attribute reduction mechanism in RST, based on FCA, diverse interesting properties will be studied next, relating elements of FCA and RST. The first result presents the value taken by the intent over the attribute generating the fuzzy-attribute over a general context. (A, B, R, σ) be a multi-adjoint context, a multi-adjoint frame (L 1 , L 2 , P, &1, . . . , &n), an attribute a ∈ A and a truth value β ∈ L 1 . If the inequality β ≤ R(a, b) holds, for all b ∈ B, then

Proof. Taking into account the definitions of concept-forming operators presented in Expressions (2) and (3), we have for an attribute a ∈ A and a truth value β ∈ L 1 that:

In order to justify Equality ( * ) in the above chain of equalities, we know that β ≤ R(a, b) , and considering the boundary condition presented in Eq. (4), we have that β & 1 ≤ R(a, b) . Then, taking into consideration the adjoint property described in Expression (1), we obtain that 1 ≤ R(a, b) β, that is, R(a, b) β = 1.

On the other hand, we have Equality ( * * ) thanks to Proposition 2 and boundary condition (4) . Hence, we obtain that

The following example illustrates this idea using the context presented in Example 1.

Let us consider the formal context and the multi-adjoint frame presented in Example 1. Let us consider the attribute x 2 ∈ U and the truth value β = 0.5. We have that 0.5 ≤ R(x 2 , x i ), for all i ∈ {1, 2, 3, 4, 5}, we will calculate φ ↓↑ x2,0.5 (x 2 ). By definition of concept-forming operator presented in Expression 3, we have that:

Applying the same calculations for all the objects, we obtain that φ ↓ x2,

Considering now, the definition of the other concept-forming operator represented in Expression 2, we have that:

The following result highlights the important role the relationship R have for computing intents of formal concepts. (A, B, R, σ) , a multi-adjoint framework (L 1 , L 2 , P, &1, . . . , &n), an attribute a ∈ A and two truth values

Proof. Given an attribute a ∈ A, if we consider the truth values β, β ≤ R(a, b), we have that R(a, b) . Analogously, taking into account the truth value β , we have that φ ↓↑ a,β (a ) = inf{R(a , b) | b ∈ B} Therefore, for all a ∈ A, we have that

Hence, we obtain that φ ↓↑ a,β = φ ↓↑ a,β .

From now on, we will consider the associated context from an information system (U, A), obtained as Definition 11 describes. Notice that, as R is built with the indiscernibility relation, the relation R verifies the reflexive property.

Let us consider an information system (U, A), its associated fuzzy context (U, U, R), its associated frame (L, L, L, &) and an object

Proof. By definitions of the concept-forming operator presented in Expressions (2) and (3), given x, x 1 ∈ U , we have that

we obtain by Proposition 2 and boundary condition (4) that:

which proves the result.

Next, the following proposition characterizes the value taken by the relation over two objects which generate the same intent of a concept. Proposition 6. Let (U, A) be an information system, (U, U, R) its associated fuzzy context, its associated frame (L, L, L, &), two objects x i , x j ∈ U and two truth values β, β ∈ L. If the equality φ ↓↑ xi,β = φ ↓↑ xj ,β holds, then

Proof. By Proposition 5 and the hypothesis, evaluating over the object x j , we have that

Therefore, the result holds by the symmetry of R.

The following consequence from the proposition above and Proposition 3 shows interesting lower and upper bounds associated with intents generated by different objects. (U, A) , its associated fuzzy context (U, U, R), its associated frame (L, L, L, &), two objects x i , x j ∈ U and two truth values β, β ∈ L, verifying that φ ↓↑ xi,β = φ ↓↑ xj ,β , then, the following chain of inequalities holds

The upper truth value threshold can be determined to every object.

Let us consider an information system (U, A), its associated fuzzy context (U, U, R), its associated frame (L, L, L, &), two objects x i , x j ∈ U and two truth values β, β ∈ L. If the equality φ ↓↑ xi,β = φ ↓↑ xj ,β holds, then we have that

Proof. Follows from Proposition 5, the equality φ ↓↑ xi,β1 (x) = φ ↓↑ xj ,β2 (x), for all x ∈ U , and the transitivity property of R.

As a consequence, the following corollary arises.

Let (U, A) be an information system, (U, U, R) its associated fuzzy context, its associated frame (L, L, L, &), two objects x i , x j ∈ U and two truth values β, β ∈ L. If the equality φ ↓↑ xi,β = φ ↓↑ xj ,β holds, then

x j ) By Proposition 6 we have that if x i , x j ∈ Atg(C), then the values β, β ∈ L, such that φ ↓↑ xi,β = φ ↓↑ xj ,β must be less or equal to R(x i , x j ). Therefore, since

we cannot establish a relationship between α-block and the classification of attributes, as it was given in [1] . We can provide the following improvement of the FCA attribute classification on the RST framework.

Corollary 3. Let (U, A) be an information system, (U, U, R) its associated fuzzy context, an object x i ∈ U . If φ ↓↑ xi,R(xi,x) (x i ) = R(x i , x), for all x ∈ U , then

This consequence notably reduce the number of computations in order to know whether an object is absolutely necessary. Another reduction for checking whether an object is a core element is the following. Corollary 4. Let (U, A) be an information system, x i ∈ U , and (U, U, R) its associated fuzzy context. If there exists β ≤ sup{R(x i , x) | x ∈ U }, such as, φ ↓↑ xi,β is the intent of a meet-irreducible, that is, φ ↓↑ xi,β = Ext(C), with C ∈ M F (U, U, R), then x i ∈ C f . Therefore, in order to apply Theorem 2 we need to begin from the values β ≤ sup{R(x i , x) | x ∈ U }. This computation does not provide extra calculations but already required ones, and offers a sufficient condition to ensure whether x i ∈ C f . More improvements will be detailed in the future.

In this paper, we have deepened in the study of the properties that the mechanism of reduction of an information system possesses considering the philosophy of FCA presented in [1] . We have proved different boundary properties, where the fuzzy relation (indiscernibility relation when RST is considered) plays an important role. For example, relevant boundary results have been proven in the particular case of two different objects generate the same formal concept, such as the upper bound is given by the relationship between both objects. As a consequence of these properties, we have provided several improvements over the attribute classification theorems [5] .

As future work, more enhancements in the classification theorems over the objects will be studied, in order to provide a size reduction in an information system using the reduction mechanism of FCA. Also, we will study other ways to connect the reduction mechanism in FCA and RST, as the consideration of the bireducts of RST to reduce the size of a relational database of FCA.

FCA attribute reduction in information systems

A computational procedure for variable selection preserving different initial conditions

Rough-setdriven approach for attribute reduction in fuzzy formal concept analysis. Fuzzy Sets Syst

A comparative study of adjoint triples

Attribute reduction in multiadjoint concept lattices

Attribute and size reduction mechanisms in multi-adjoint concept lattices

Characterizing reducts in multiadjoint concept lattices

Multi-adjoint fuzzy rough sets: definition, properties and attribute selection

Introduction to Lattices and Order

A methodology for analysis of concept lattice reduction

Formal Concept Analysis: Mathematical Foundation

Metamathematics of Fuzzy Logic

Formal concept analysis via multiadjoint concept lattices

Information systems theoretical foundations

Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory

Attribute reduction in decision-theoretic rough set models

Data analysis based on discernibility and indiscernibility