key: cord-0044863-qdk2fap8
authors: Benítez-Caballero, M. José; Medina, Jesús; Ramírez-Poussa, Eloísa
title: Towards a Classification of Rough Set Bireducts
date: 2020-05-16
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50153-2_56
sha: 0261056f80c5174c5ed627a75df33d1a9b69cdd9
doc_id: 44863
cord_uid: qdk2fap8

Size reduction mechanisms are very important in several mathematical fields. In rough set theory, bireducts arose to reduce simultaneously the set of attributes and the set of objects of the considered dataset, providing subsystems with the minimal sets of attributes that connect the maximum number of objects preserving the information of the original dataset. This paper presents the main properties of bireducts and how they can be used for removing inconsistencies.

Rough Set Theory (RST) is one of the most useful mathematical tools to treat and manage datasets. In particular, RST was proposed by Pawlak in [7] , to analyze datasets containing incomplete information. The main idea of this theory is to determine a set from two approximations. These approximations are called upper approximation and lower approximation.

In this theory, a relational database can be represented from two different point of view, as an information system or as a decision system. In the case of information system, the database is simulated by a set of objects and a set of attributes characterizing the objects. On the other hand, a decision system is a particular case of information system adding a new attribute that describes an action over the objects, which is called decision attribute.

Due to the size of databases has increased in late decades, size reduction mechanisms became into one of the main goals of different mathematical theories. In the particular case of RST, a reduct is a minimal subset of attributes preserving the same knowledge as the original set. This notion is deeply studied in many papers [4] [5] [6] 11, 12] . Therefore, reducts are focused on the reduction of the set of attributes. In order to reduce also the set of objects, the notion of bireduct arose [1] [2] [3] 9, 10] . In a general point of view, the main idea underlying bireducts is to choose the maximal consistent information subsystem. Moreover, as all the bireducts are computed, the user can choose the bireduct consistent subsystem that best suits their needs.

In this paper, we study some properties of bireducts. We will prove that the set of reducts can be obtained from the set of bireducts. We will analyze the relation between bireducts and the discernibility classes of the objects of the dataset. We will also inspect how bireducts can be used for detecting inconsistencies contained in the considered database. The presented study will be carried out for information systems, as well as for decision systems. All the presented results will be illustrated by means of examples.

The paper is organized as follows: the notions and results needed in this study are recalled in Sect. 2. Afterwards, Sect. 3 presents the contribution of this paper together with some examples. Finally, the conclusions and future works are presented in Sect. 4.

This section recalls the main notions associated with information and decision systems and the characterizations of reducts and bireducts. More detailed information related to these notions can be found in [3] .

We will recall the notions and results needed to carry out the attribute reduction in information systems. First of all, we present the definition of information system and the considered indiscernibility relation.

x n } and A = {a 1 , a 2 , . . . , a m } are finite, non-empty sets of objects and attributes, respectively. Each a ∈ A corresponds to a mappingā : U → V a , where V a is the value set of the attribute a over U . For every subset D of A, the Dindiscernibility relation, Ind(D), is defined by the following equivalence relation

These equivalence classes are called indiscernibility class. Ind(D) provides a par-

In order to be able to reduce an information system, the notions of consistent set and reduct are fundamental. The following definition presents the idea of discernibility matrix and discernibility function. In particular, the discernibility matrix is a useful tool which is used to represent the attributes in which the objects differ.

Definition 3. 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:

and the discernibility function of (U, A) is defined by:

The discernibility function of an information system is a powerful tool which is used in the following result in order to describe a method to obtain all reducts from an information system [3, 8] . Next, we introduce an example, which will be developed throughout the paper. Table 1 . If we compare the objects, considering the indiscernibility relation presented in Definition 1, we can build the following discernibility matrix:

Now, we will use the discernibility matrix to build the unidimensional discernibility function:

Therefore, by Theorem 1, we obtain two reducts:

The idea of bireducts arose as a path to prevent incompatibilities and eliminate noise in the original data by means of a reduction in the set of objects and the set of attributes, simultaneously.

where X ∈ U is a subset of objects and D ∈ A is a subset of attributes. We say that (X, D) is an information bireduct if and only if every pair of objects i, j ∈ X are discernible by D and the following properties hold: -There is no subset C D such that C discerns every pair of objects of X. -There is no subset of objects X Y such that D discern every pair of objects of Y .

Since we will work simultaneously with reducts and bireducts of an information system, we will use the notation (X, B) to denote bireducts in order to distinguish the subset of attributes from reducts and bireducts.

In order to generalize the mechanism to obtain reducts presented in Theorem 1, we need to improve the idea of discernibility function as follows:

Now, we can introduce the following theorem, in which a mechanism to obtain all the bireducts of an information system is presented. We are going to compute all the bireducts from the information system described in Example 1. In order to do that, we consider the discernibility matrix described in Expression (1), obtaining the following bidimensional discernibility function:

Now, we compute the reduced disjunctive normal form of τ bi obtaining

Therefore, there are 47 bireducts in the information system (U, A). Some of them are described in Table 2 

In this section, we recall the main notions and results we will need in the framework of decision systems. First of all, we present the formal definition of a decision system. 

As we did in an information system, we use the notions of discernibility matrix an function in order to compute all reducts [8] . Therefore, the discernibility matrix of a decision system (U, A ∪ {d}) is a square and symmetric matrix defined as:

Therefore, there are two possibilities of obtaining the empty set: objects have the same decision value or are indiscernible by characteristic attributes. In addition, the discernibility function of (U, A∪{d}) is the map τ :

It can be shown that the prime implicants of f constitute exactly all the decision reducts of (U, A ∪ {d}), as the generalization of Theorem 1 to a decision system. Now, we present the definition of decision bireduct of a decision system: 1. There is no subset C B such that C discern every pair

In order to generalize the process to compute all bireducts, we consider the discernibility function:

The corresponding characterization theorem for bireducts from the discernibility function is as follows.

Now that all the needed notions and results have been presented, we present the different kinds of bireducts that we can find in an information and decision systems.

This section highlights the main properties of bireducts. First of all, the following result shows that the reducts of an information system are particular cases of bireducts.

Proof. This proof is straightly obtained from Definitions 2 and 4.

Moreover, we can assert that the decision reducts of a decision system are also decision bireducts due to the definitions of these notions.

The following example illustrates this result by means of the information system given in Example 1.

Let us focus in the bireduct (X 1 , B 1 ) and (X 2 , B 2 ) obtained in Example 2, due to they have the whole set of objects. If we compare the set of attributes from the bireducts and the set of attributes described by the reducts of Example 1, we have that D 1 = B 2 = {fever, cough, muscle ache} D 2 = B 1 = {fever, cough, tonsil inflam.} A special type of bireduct appears when the subset of attributes is the empty set, that is, there are no attribute to distinguish the elements in the subset of objects. Therefore, the objects are indiscernible. The following result formalizes this idea. (X , B) the family of bireducts from the information system. If a bireduct (X, B) verifies that B = ∅, then X is the indiscernibility class of the objects x ∈ X.

Proof. As (X, B) is a bireduct and B = ∅, we have that there is no attribute distinguishing all objects in the set X. Therefore, for every object x ∈ X, we have thatā(x) =ā(x j ), for all attribute a ∈ A and any object x j ∈ X. Consequently,

which is the definition of [x] A presented in Definition 1. Therefore, X ⊆ [x] A . By the maximality of X, we obtain that X must be [x] A .

In this example, we present the connection between the indiscernibility classes of the objects in an information system and the bireducts with no attributes.

Example 4. Let us continue the study of the information system in Example 1. If we consider the bireducts (X i , B i ), with i ∈ {5, . . . , 9}, we have that B i = ∅, for all i ∈ {5, . . . , 9}.

On the other hand, if we compute the indiscernibility classes of the objects of the considered information system, we obtain that:

Comparing these subsets of objects with the bireducts (X i , B i ), with i ∈ {5, . . . , 9}, we obtain a correspondence between the sets X i , with i ∈ {5, . . . , 9} and the indiscernibility classes [x] A , for all x ∈ U .

In the particular case of a decision system, if the subset of attributes of a birreduct is empty, the subset of objects of that bireduct is the decision class provided by the decision attribute.

Proof. By definition of bireduct in a decision system, B = ∅ if and only if the value of the decision attribute is the same for all the objects in X. In this case, since two objects with the same decision attribute value are not compared further, the assumption B = ∅ automatically implies that all objects are in the same decision class, that is X = [x] d , for every object x ∈ X.

Moreover, bireducts remove inconsistencies in the data, that is the cases when two objects have different decision value, but they are indiscernible by the attributes in A.

, if x, y ∈ U satisfy that d(x) = d(y) andā(x) =ā(y), for all a ∈ A, then x and y do not belong to the same subset X, for any bireduct (X, B).

Proof. By the definition of discernibility function of decision systems, given in Expression 4, if x, y ∈ U , such that d(x) = d(y), the conjunctive normal form τ bir will contain the clause

Sinceā(x) =ā(y), for all a ∈ A, the set {a ∈ A |ā(x) =ā(y)} is empty and so, the clause is x ∨ y.

Therefore, every cube of the obtained reduced disjunctive normal form will contain x or y. As a consequence, by Theorem 3, we have that, for every bireduct (X, B), the set X cannot contain x and y simultaneously, which proves the result.

As a consequence of this result, all bireducts are consistent and so, the obtained information from these subsystems is also consistent. The following example illustrates the previous notions and results in the particular case of a decision system.

Example 5. From the information system (U, A) in Example 1, we will add a decision attribute. This decision attribute will represent whether a patient has flu or not. The relation is shown in Table 3 . Table 3 . Relation of Example 5.

R fever(f) cough(c) tonsil inflam.(t) muscle ache(a) flu? As we can see in Table 3 , the objects 3 and 4 have different values in the decision attribute but the values of these objects coincide for the rest of the attributes. Therefore, objects 3 and 4 represent an inconsistency in the data. Now, if we compare the objects considering the indiscernibility relation presented in Definition 1, we can build the following discernibility matrix: ⎛

There exist two cases to obtain the empty set as an element of the discernibility matrix: the objects have the same value in the decision attribute or, having different values in the decision attribute, the objects are indiscernible. Therefore, considering the discernibility matrix, we obtain the unidimensional discernibility function:

Therefore, we obtain two decision reducts:

Now, we will compute all bireducts of the decision system (U, A ∪ {d}) from Theorem 2, that is, throughout the following bidimensional discernibility function.

From the formula above, the reduced disjunctive normal form is computed.

Hence, we obtain 18 decision bireducts, some of them listed in Table 4 . If we observe the reducts in Table 2 , we detect that bireducts (X 3 , B 3 ), (X 4 , B 4 ) and (X 5 , B 5 ) have the same subsets of attributes as the reducts D 1 and D 2 , listed in Expression 6. Notice that the subsets of objects in these three bireducts are not the whole set A. This is due to objects 3 and 4 present an inconsistence in the data, as Proposition 4 asserts, they cannot belong to the same subset of objects of any bireduct. Therefore, when the considered dataset presents inconsistencies, a decision reduct is represented as a bireduct with the set of objects as large as possible without inconsistencies.

On the other hand, bireducts (X 6 , B 6 ) and (X 7 , B 7 ) do not consider any attribute. Comparing with the classes, we obtain that: [2] 

In this paper, we have studied some properties of bireducts and highlighted specific obtained bireducts. Mainly, we have identified the bireducts that provide the indiscernibility classes of the objects of the considered dataset. Moreover, it has been proved that the reducts of information systems and decision systems can also be obtained from bireducts. Furthermore, in the particular case of decision systems, we have proven that inconsistencies can be detected with bireducts and that they consider the largest consistent subsets of objects.

As a future work, we will continue the study of the properties obtained from the reduction of a formal context by means of bireducts. Also, we will use this study in order to reduce the number of attribute implications in FCA. In addition, the notion of fuzzy bireduct will be investigated.

Delta-information reducts and bireducts

Reducing information systems considering similarity relations

Bireducts with tolerance relations

Attribute selection with fuzzy decision reducts

Rough set methods for attribute clustering and selection

Relating attribute reduction in formal, object-oriented and propertyoriented concept lattices

Rough sets

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

Ensembles of bireducts: towards robust classification and simple representation

Recent advances in decision bireducts: complexity, heuristics and streams

Attribute reduction in decision-theoretic rough set models

Data analysis based on discernibility and indiscernibility