Formal Concept Analysis (FCA) and Rough Set Theory (RST) are two useful mathematical tools for extracting information, which have diferent philosophies. One important issue in data science is to obtain relationships among the main variables in the considered data set. Both theories, FCA and RST, independently study these relations by means of attribute implications in FCA and decision rules in RST. This paper introduces a preliminary comparison between these approaches, focused on the notions of valid attribute implication in FCA and true decision rule in RST.
Formal Concept Analysis (FCA) was introduced by Wille [19] in the eighties, as a mathematical tool for the extraction of knowledge from datasets, interpreted as a context composed by objects, attributes and a binary relation between them. From this relation and the derivation operators, pieces of information called concepts are obtained, which are pairs composed of a subset of objects and a subset of attributes, where each subset unequivocally determines the other one. An interesting topic in FCA is the study of attribute implications [5, 6, 7, 8, 9, 16] relating the attributes in the dataset (context) for obtaining information from the context, which has a diferent philosophy from decision rules in Rough Set Theory (RST).
RST was proposed by Pawlak [12, 13] also in the eighties as a formal tool to analyze datasets with imprecise or incomplete information. This theory interprets a relational dataset as a decision table, which contains a collection of objects, attributes and mappings characterizing the objects by using the attributes. In RST, the notion of decision rule [10, 14, 15, 18, 20] arises as a useful tool for the management of information from relational datasets, characterizing decision tables and allowing the extraction of significant conclusions thanks to their logical terms. Diferent measures have been defined in order to describe decision rules and provide useful information, such as, the certainty which represents a conditional probability.
Both theories, FCA and RST, have been related in diverse papers [
This section includes some preliminary definitions of Formal Concept Analysis [ 7, 8] and Rough Set Theory [14, 15] in order to make the paper self-contained.
Datasets are represented as formal contexts in FCA. From a formal context, derivation operators are defined in order to characterize a subset of attributes by using a subset of objects and vice versa. These derivation operators are essential to determine the basic units of knowledge of the contexts, that is, the concepts.
Definition 1. A context is a tuple (, , ℛ) such that and are non-empty sets of attributes and objects, respectively, and ℛ is a relation between them.
Definition 2. Given a context (, , ℛ) , the derivation operators (↑,↓ ) are the mappings ↑ ∶ 2 → 2 and ↓ ∶ 2 → 2 defined, for each ⊆ and ⊆ , as: ↑ ↓ = { ∈ ∣ ℛ = { ∈ ∣ ℛ for each ∈ } for each ∈ }
The set ↑ is called intension of and ↓ is called extension of . Given ⊆ will say that ( , ) is a concept if = ↓ and = ↑. and ⊆ , we
From now on, the set of concepts of a given context (, , ℛ) will be denoted as (, , ℛ) . In the following, we recall some important notions related to attribute implications and their validity.
Definition 3. Let Λ be an index set, (, , ℛ) be a context and , , ⊆ . • An attribute implication is denoted as ⇒ . The set is called antecedent of the attribute implication and the set is called consequent. • respects an attribute implication ⇒ , if ⊈ or ⊆ . • ⇒ is a valid attribute implication in { ⊆ ∣ ∈ Λ} , if each respects the attribute implication ⇒ .
The notion of valid attribute implication is extended to formal contexts as it is shown below. Definition 4. Let (, , ℛ) be a context and , ⊆ . We say that ⇒ is a valid attribute implication in (, , ℛ) , if ⇒ is a valid attribute implication in { ↑ ∣ ∈ , ( ↑↓, ↑) ∈ (, , ℛ)}.
Finally, we recall a useful property that allows us to obtain valid attribute implications in a context.
Proposition 1. Let (, , ℛ) be a context and , ⊆ implication in (, , ℛ) if and only if ⊆ ↓↑.
. Then, ⇒ is a valid attribute Datasets are represented as decision tables in RST. Although we will only consider one decision attribute in decision tables, similar studies can be carried out in an analogous way when more than one decision attribute is considered.
Definition 5. Let and be non-empty sets of objects and attributes, respectively. A decision table is a tuple ( , , , ) such that = ∪ {} with ∉ , = { ∣ ∈ }, where is the set of values associated with the attribute ∈ over , and = { ∣̄ ∈ , ∶̄ → }. In this case, the attributes of are called condition attributes and is called a decision attribute.
Decision tables describe decisions in terms of conditions that must be satisfied in order to carry out the decision specified in the decision table [ 15]. In this way, decision tables can be seen as a logical description of approximation of decisions. Furthermore, a set of decision rules can be associated with every decision table, describing the decision table in logical terms. Hence, decision rules allow an easier interpretation of decision tables. In the following, we recall the formal language in which decision rules are based on.
Definition 6. Let = ( , , , ) be a decision table and ⊆ . The set of formulas associated with , denoted as () , is built from attribute-value pairs (, ) , where ∈ and ∈ , by means of the conjunction and disjunction logical connectives, ∧ and ∨, respectively.
For each Φ ∈ () , with Φ = (, ) , the set of objects ∈ that satisfies Φ in is defined as: ‖Φ‖ = ‖(, )‖ = { ∈ ∣ (̄) = }
Given Φ, Ψ ∈ () , the set of objects that satisfies Φ ∧ Ψ in is defined as ‖Φ ∧ Ψ‖ = ‖Φ‖ ∩ ‖Ψ‖ and the set of objects that satisfies Φ ∨ Ψ in is defined as ‖Φ ∨ Ψ‖ = ‖Φ‖ ∪ ‖Ψ‖ .
Once the formal language associated with a subset of attributes has been defined, we can introduce the notion of a decision rule.
Definition 7. Let = ( , , , ) be a decision table and ⊆ . A decision rule in is an expression Φ → Ψ where Φ ∈ (), Ψ ∈ ({}) where and {} are condition and decision attributes, respectively. In addition, we say that an object ∈ satisfies a decision rule Φ → Ψ if ∈ ‖Φ ∧ Ψ‖ .
Finally, we introduce the notion of certainty of a decision rule, which provides us with the conditional probability of the consequent given the antecedent.
Definition 8. with Φ ∈ ()
Let = ( , , , ) be a decision table and Φ → Ψ be a decision rule in , and Ψ ∈ ({}) . We call certainty of the decision rule Φ → Ψ to the value: (Φ, Ψ) = |‖Φ ∧ Ψ‖ | |‖Φ‖ | We will say that Φ → Ψ is a true decision rule, if (Φ, Ψ) = 1. If (Φ, Ψ) = 0, we say that the decision rule is false. Otherwise, it will be called a not entirely true decision rule.
This section focuses on comparing decision rules in RST and attribute implications in FCA, in order to obtain a relationship between them. Before carrying out this comparison, it is convenient to note that given a set of objects and a set of attributes, they are always related in some way in RST, thanks to the value given by the mapping associated to each attribute of the decision table, while an object and an attribute may be related or not in FCA. Moreover, we must take into account that, although FCA can consider multi-valued contexts [8], boolean relations are usually considered in classical FCA. Hence, in this preliminary study, we will consider boolean decision tables, following the translation given in [3] in order to obtain a decision table from a context and vice versa.
Definition 9. Let and be non-empty sets of objects and attributes, respectively. A boolean decision table is a tuple ℬ = ( , , {0, 1}, ) such that = ∪ {} with ∉ and = { ∣̄ ∈ , ∶̄ → {0, 1}} .
Considering Definitions 1 and 9, we can obtain a boolean decision table from a given context as follows. Given a context (, , ℛ) , we construct the boolean decision table ℬ = (, , {0, 1}, ), with an outstanding attribute ∈ , defining the set by means of the mappings ∶̄ → {0, 1} defined, for each ∈ and ∈ , as follows: ()̄ = { 1 if ℛ 0 otherwise
Reciprocally, given a boolean decision table ℬ = ( , , {0, 1}, ) we define the context ( , , ℛ) , where the relation is defined as ℛ , if ()̄ = 1 , for all attribute ∈ and object ∈ .
Once exposed the mechanisms to obtain a boolean decision table from a context and vice versa, we proceed to relate true decision rules in RST to valid attribute implications in FCA. Proposition 2. Let ℬ = (, , {0, 1}, ) be a boolean decision table, (, , ℛ) be a context and , ⊆ , such that = { 1, … , } and = . Given a decision rule Φ → Ψ in ℬ satisfied by at least one object ∈ , where Φ = ( 1, 1) ∧ … ∧ ( , 1) and Ψ = (, 1) , the following equivalence holds:
The decision rules in which all the attributes (conditions and decision attributes) take the value 1 will be called 1-decision rule.
As a consequence of the previous proposition, if a dataset is interpreted as a boolean decision table and a true 1-decision rule is obtained, a valid attribute implication is deduced. In contrast, if the dataset is studied from the FCA perspective and a valid attribute implication is extracted, where at least one object is related with all the attributes of the implication, a true decision rule in RST is obtained. In short, regardless of the framework worked, it is possible to obtain significant conclusions in both of them simultaneously.
On the other hand, it is also possible to relate true 1-decision rules Φ → Ψ = ( 1, 1)∧… ( , 1) → (, 1) to valid attribute implications ⇒ in the case that ↓ ≠ ∅. This occurs since if an object belongs to ↓ then it is related to all the attributes of . Hence, satisfies the antecedent Φ of the decision rule and, whether decision rule Φ → Ψ is true or the attribute implication ⇒ is valid it is obtained that satisfies the consequent Ψ. Then, it is equivalent to require that the decision rule Φ → Ψ is satisfied by at least one object than to require that this object belongs to ↓. As a consequence, the following result arises.
Corollary 1. Let ℬ = (, , {0, 1}, ) be a boolean decision table, (, , ℛ) be a context and , ⊆ , such that = { 1, … , } and = . Given an attribute implication ⇒ with ↓ ≠ ∅, the following equivalence holds:
Notice that, by the philosophy in FCA, only attributes with value 1 can be considered in
decision rules to be compared with attribute implications. Hence, the possibility of taking into
account that decision rules is to consider mixed contexts, that is, positive and negative attributes,
as it is considered in [
Example 1. Consider the context (, , ℛ) where the set of attributes is = { 1, 2, 3, 4, 5}, the set of objects = { 1, 2, 3, 4, 5, 6, 7} and the relation ℛ is given in Table 1.
As it was commented previously, we can obtain diferent boolean decision tables (, , {0, 1}, ), depending on the considered outstanding attribute ∈ . In order to illustrate Proposition 2, the set of attributes = { 1, 2, 4, 5} and the decision attribute = 3 will be fixed. The boolean decision table (, , {0, 1}, ) obtained following the mechanism previously explained is represented in Table 2.
Now, we consider all decision rules of Table 2 by using { 1, 2} as condition attributes and = 3 as decision attribute. One decision rule is extracted for each ∈ . However, the pairs Boolean decision table (, , {0, 1}, ) of Example 1 of objects 1, 2 and 5, 7 generate the same decision rule. Therefore, five decision rules are obtained, which are:
Notice that, both 1 and 4 are satisfied by two objects, and therefore, the number of obtained decision rules are lesser than the number of objects. Attending to the obtained decision rules, we can ensure that 3 is the unique 1-decision rule. In order to illustrate the mentioned proposition, we will compute the certainty of 3, being Φ3 = ( 1, 1) ∧ ( 2, 1) and Ψ3 = (, 1) . By Definition 8, its certainty is ℬ(Φ3, Ψ3) = |‖Φ3 ∧ Ψ3‖ ℬ| |‖Φ3‖ ℬ| 1 1 = = 1 On the other hand, notice that ‖Φ3‖ ℬ = = = ‖( 1, 1) ∧ ( 2, 1)‖ ℬ = ‖( 1, 1)‖ ℬ ∩ ‖( 2, 1)‖ ℬ { ∈ ∣ 1() = 1} ∩ { ∈ ∣
2() = 1} { ∈ ∣ 1ℛ and 2ℛ} = { 1, 2} ↓ obtaining a direct correspondence between ‖Φ3‖ ℬ and { 1, 2}↓. Therefore, that is, an object satisfies
Φ3 in RST if it is related to all of the attributes of { 1, 2} in FCA, { 1, 2}↓↑ = = ({ 1, 2}↓)↑ = (‖Φ3‖ ℬ)
↑ { 4}↑ = { ∈ ∣ ℛ 4} = { 1, 2, 4, }
Since {} ⊆ { 1, 2}↓↑, we can conclude that { 1, 2} ⇒ {} is a valid attribute implication, according to Proposition 1.
Now, we will emphasize the need to require that all of the attributes of the decision rule given in Proposition 2 must take the value 1 in order to obtain an equivalence between true decision rules and valid attribute implications. To show this, we consider a diferent boolean decision table, that is, (, , {0, 1}, ) with = { 1, 2, 3, 4} and = 5 . We consider all of the decision rules of Table 2 by using 4 as condition attribute and = 5 as decision attribute. These decision rules are ′ 1 ′ 2 ′ 3 ∶ ( 4, 1) → (, 0) ∶ ( 4, 0) → (, 1) ∶ ( 4, 0) → (, 0) is not valid since
It is easy to check that 1′ is a true decision rule. However, the attribute implication { 4} ⇒ {} {} ⊈ { 4}↓↑ = { 1, 4, 5}↑ = { 4} This fact is due to the decision rule 1′ is not a 1-decision rule.
Now, we will show that it is also possible to obtain valid attribute implications without requiring the existence of true decision rules. Notice that, by Corollary 1, in order to illustrate this case, no object can be in the extension of the antecedent of the attribute implication. Specifically, we will see that { 4, 5} ⇒ { 2} is a valid attribute implication but the expression ( 4, 1)∧( 5, 1) → ( 2, 1) is not a certain decision rule. In fact, it is not even a decision rule. Furthermore, none of the decision rules obtained from the boolean decision table (, , {0, 1}, ) with = { 1, 3, 4, 5} and = 2, by using as condition attributes { 4, 5}, is true. On the one hand, we obtain
As a result, { 2} ⊆ { 4, 5}↓↑ = . Hence, { 4, 5} ⇒ { 2} is a valid attribute implication. On the other hand, the expression:
{ 4, 5}↓↑ = ∅↑ = ( 4, 1) ∧ ( 5, 1) → (, 1) ″ 1 ″ 2 ″ 3 ″ 4 ″ 5 ″ 6 ∶ ( 4, 1) ∧ ( 5, 0) → (, 1) ∶ ( 4, 0) ∧ ( 5, 1) → (, 1) ∶ ( 4, 0) ∧ ( 5, 0) → (, 0) ∶ ( 4, 1) ∧ ( 5, 0) → (, 0) ∶ ( 4, 0) ∧ ( 5, 0) → (, 1) ∶ ( 4, 0) ∧ ( 5, 1) → (, 0) (1) is not a decision rule if we take into account the condition attributes and decision attribute mentioned above. Even more, computing all the decision rules: and their certainty, collected in Table 3, we can conclude that there are no true decision rules with { 4, 5} as condition attributes and 2 as decision attribute, whereas { 4, 5} ⇒ { 2} is a valid attribute implication. The main reason of this fact is that in the derivation operator ↓ only objects related to the given subset of attributes are taken into account.
As a consequence of Proposition 2 and Corollary 1, we can also conclude that, if the context contains an object with all the attributes, then we have that the set of true 1-decision rules is equal to the set of valid attribute implications.
In this paper, we have related true decision rules in RST and valid attributes implication in FCA. For this purpose, we have taken into account a way of obtaining boolean decision tables from a given context and vice versa. We have explored that a true decision rule is equivalent to a valid attribute implication, when at least one object has the attributes in the antecedent. This hypothesis is equivalent to check whether the object satisfies the 1-decision rule. Moreover, these theoretical results are illustrated with an example.
The obtained consequences show a first and encouraging step to relate both notions, decision rules and attribute implications, with the main goal of each framework takes advantage of the definitions and results developed during the last decades in the other framework. Therefore, as a future work, we will continue studying the relationships among these notions in the classical setting, as well as the well-known notion of functional dependencies in Database Management System (DBMS). There exist important notions to be taken into consideration, such as, association rules, algorithm of decision rules, eficiency, etc. Moreover, mixed contexts with negative attributes will be incorporated in the study. In addition, we are interested in the study of this relationship in the fuzzy setting.
Partially supported by the the 2014-2020 ERDF Operational Programme in collaboration with the State Research Agency (AEI) in project 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. [3] M. J. Benítez-Caballero, J. Medina, E. Ramírez-Poussa, and D. Ślȩzak. Rough-set-driven approach for attribute reduction in fuzzy formal concept analysis. Fuzzy Sets and Systems, 2019. [4] M. J. Benítez-Caballero, J. Medina, and E. Ramírez-Poussa. Attribute reduction in rough set theory and formal concept analysis. Lecture Notes in Computer Science, 10314:513–525, 2017. [5] P. Cordero, M. Enciso, A. Mora, and M. Ojeda-Aciego. Computing left-minimal direct basis of implications. In M. Ojeda-Aciego and J. Outrata, editors, CLA, volume 1062 of CEUR Workshop Proceedings, pages 293–298. CEUR-WS.org, 2013. [6] D. Dubois, J. Medina, H. Prade, and E. Ramírez-Poussa. Disjunctive attribute dependencies in formal concept analysis under the epistemic view of formal contexts. Information Sciences, 2021. [7] B. Ganter, G. Stumme, and R. Wille, editors. Formal Concept Analysis: Foundations and
Applications. Lecture Notes in Computer Science. Springer Verlag, 2005. [8] B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundation. Springer
Verlag, 1999. [9] J.-L. Guigues and V. Duquenne. Familles minimales d’implications informatives résultant d’un tableau de données binaires. Mathématiques et Sciences Humaines, 95:5–18, 1986. [10] J. Li, C. Mei, and Y. Lv. Incomplete decision contexts: Approximate concept construction, rule acquisition and knowledge reduction. International Journal of Approximate Reasoning, 54(1):149–165, 2013. [11] J. Medina. Relating attribute reduction in formal, object-oriented and property-oriented concept lattices. Computers & Mathematics with Applications, 64(6):1992–2002, 2012. [12] Z. Pawlak. Information systems theoretical foundations. Information Systems, 6(3):205 – 218, 1981. [13] Z. Pawlak. Rough sets. International Journal of Computer and Information Science, 11:341–356, 1982. [14] Z. Pawlak. Rough Sets: Theoretical Aspects of Reasoning About Data. Kluwer Academic
Publishers, Norwell, MA, USA, 1992. [15] Z. Pawlak. Rough sets and decision algorithms. In W. Ziarko and Y. Yao, editors, Rough Sets and Current Trends in Computing, pages 30–45, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. [16] J. Rodríguez-Jiménez, P. Cordero, M. Enciso, and A. Mora. Negative attributes and implications in formal concept analysis. Procedia Computer Science, 31:758 – 765, 2014. [17] J. Rodríguez-Jiménez, P. Cordero, M. Enciso, and S. Rudolph. Concept lattices with negative information: A characterization theorem. Information Sciences, 369:51 – 62, 2016. [18] S. Stawicki, D. Ślȩzak, A. Janusz, and S. Widz. Decision bireducts and decision reducts - a comparison. International Journal of Approximate Reasoning, 84:75–109, 2017. [19] R. Wille. Restructuring lattice theory: an approach based on hierarchies of concepts. In
I. Rival, editor, Ordered Sets, pages 445–470. Reidel, 1982. [20] Y. Yao. Three-way decisions with probabilistic rough sets. Information Sciences, 180(3):341 – 353, 2010. [21] Y. Yao. Rough-set concept analysis: Interpreting rs-definable concepts based on ideas from formal concept analysis. Information Sciences, 346-347:442–462, 2016.