Extending FuzAtAnalyzer to approach the management of classical negation

Extending FuzAtAnalyzer to approach the management of classical negation Rodriguez-Jimenez, J.M., Cordero, P., Enciso, M., Mora, A. jmro[email protected], p[email protected], [email protected], [email protected] Universidad de M´alaga, Andalucia Tech, Spain Published in CMMSE 2015 Abstract. FuzAtAnalyzer was conceived as a Java framework which goes beyond of classical tools in formal concept analysis. Specifically, it successfully incorporated the management of uncertainty by means of methods and tools from the area of fuzzy formal concept analysis. One limitation of formal concept analysis is that they only consider the presence of properties in the objects (positive attributes) as much in fuzzy as in crisp case. In this paper, a first step in the incorporation of negations is presented. Our aim is the treatment of the absence of properties (negative attributes). Specifically, we extend the framework by including specific tools for mining knowledge combining crisp positive and negative attributes. 1 Introduction We create a tool called FuzAtAnalyzer since we have the need to explore fuzzy functional dependencies mining in datasets because there not exists other tools that covers the theory that we develope. Our first implementation was Simplification Logic with fuzzy functional dependencies [4] followed by the algorithms related with Fuzzy Attribute Tables [5, ?]. Simplification Logic was adapted for working with crisp implications (without degrees)[8], that was the previous step before we study implications in Formal Concept Analysis. In this section, the basic notions related with Formal Concept Analysis (FCA) [14] and attribute implications are briefly presented. See [10] for a more detailed explanation. A formal context is a triple K=hG, M, Iiwhere Gand Mare finite non-empty sets and I⊆G×Mis a binary relation. The elements in G are named objects, the elements in Mattributes and hg, mi ∈ Imeans that the object ghas the attribute m. From this triple, two mappings ↑: 2G→2Mand ↓: 2M→2G, named concept-forming operators, are defined as follows: for any X⊆Gand Y⊆M, X↑={m∈M|for each g∈X:hg, mi ∈ I}(1) Y↓={g∈G|for each m∈Y:hg, mi ∈ I}(2) X↑is the subset of all attributes shared by all the objects in Xand Y↓is the subset of all objects that have the attributes in Y. The pair (↑,↓) constitutes a Galois connection between 2Gand 2Mand, therefore, both compositions are closure operators. A pair of subsets hX, Y iwith X⊆Gand Y⊆Msuch X↑=Yand Y↓=X is named a formal concept.Xis named the extent and Ythe intent of the concept. These extents and intents coincide with closed sets wrt the closure operators because X↑↓ =Xand Y↓↑ =Y. Thus, the set of all the formal concepts is a lattice, named concept lattice, with the relation hX1, Y1i≤hX2, Y2iif and only if X1⊆X2(or equivalently, Y2⊆Y1) (3) Focusing the attention in relationships among sets of attributes is a second way in which the information can be summarized. Agrawal et al.[1] introduced association rules for discovering regularities between attributes. For this purpose, the concepts support and confidence were introduced. Support is defined for any subset Y⊆M,supp(Y) = |Y↓|/|G|and confidence for association rule Y1→Y2is defined as conf(Y1→Y2) = supp(Y1∪Y2)/supp(Y1). We have to remark that a fuzzy functional dependency and an association rule are different elements with different degrees. In first case, the degree indicates the relation between set of attributes, whereas association rules have a statistical degree. These relationships among attribute sets where confidence = 1 are described in terms of attribute implications. The concept lattice can be also characterized in terms of attribute implications. An attribute implication is an expression A→Bwhere A, B ⊆Mand it holds in a formal context if A↓⊆B↓. That is, any object that has all the attributes in Ahas also all the attributes in B. It is well known that the sets of attribute implications that are satisfied by a context satisfies the Armstrong’s Axioms: [Ref] Reflexivity: If B⊆Athen `A→B. [Augm] Augmentation: A→B`A∪C→B∪C. [Trans] Transitivity: A→B, B →C`A→C. A set of implications Bis an implicational basis for Kif: (1) any implication from Bholds in Kand (2) any implication that Ksatisfies follows (can be inferred by using Armstrong’s Axioms from B. One of the most cited kind of basis is the so-called Duquenne-Guigues (or stem) base [11]. The premises of the implications in the Duquenne-Guigues basis are pseudo-intents: P⊆Mis a pseudo-intent if Pis not an intent (P↓↑ 6=P) and Q↓↑ ⊆Pholds for every pseudo-intent Q P. The Duquenne-Guigues base for Kis {P→(P↓↑ rP)|Pis a pseudo-intent for K}(4) and satisfies that its cardinality is minimum among all the bases. It is well-known the NextClosure Algorithm [10] that computes all the pseudo-intents and intents, and therefore the Duquenne-Guigues base for a context. This algorithm is based in the lectic order among sets of attributes that coincides with the usual order for binary numbers when set of attributes are represented by bit-maps. Classical FCA only discover knowledge limited to positive attributes in the context, but it does not consider information relative to the absence of properties (attributes). Thus, the Duquenne-Guigues basis obtained from Table 1 is {e→ bc, d →c, bc →e, a →b}. Moreover, the implications b→ceither b→ddo not hold in Table 1 and therefore they can not be derived from the basis by using the inference system. Nevertheless, both implications correspond with different situations. In the first case, some objects have attributes band c(e.g. objects o1 and o3) whereas another objects (e.g. o2) have the attribute band do not have c. By the other side, in the second case, any object that has the attribute bdoes not have the attribute d. I a b c d e o1× × × o2× × o3× × × o4× × Table 1. A formal context A more general framework is necessary to deal with this kind of information. In [12], we have tackled this issue focusing on the problem of mining implication with positive and negative attributes from formal contexts. As a conclusion of that work we emphasized the necessity of a full development of an algebraic framework. First, we begin with the introduction of an extended notation that allows us to consider the negation of attributes. From now on, the set of attributes is denoted by M, and its elements by the letter m, possibly with subindexes. That is, the lowercase character mis reserved for positive attributes. We use mto denote the negation of the attribute mand Mto denote the set {m|m∈M} whose elements will be named negative attributes. Arbitrary elements in M∪Mare going to be denoted by the first letters in the alphabet: a,b,c, etc. and adenotes the opposite of a. That is, the symbol a could represent a positive or a negative attribute and, if a=m∈Mthen a=m and if a=m∈Mthen a=m. Capital letters A,B,C. . . denote subsets of M∪M. If A⊆M∪M, then A denotes the set of the opposite of attributes {a|a∈A}and the following sets are defined: –Pos(A) = {m∈M|m∈A} –Neg(A) = {m∈M|m∈A} –Tot(A) = Pos(A)∪Neg(A) Note that Pos(A),Neg(A),Tot(A)⊆M. Once we have introduced the notation, we are going to summarize some results concerning the mining of knowledge from contexts in terms of implications with negative and positive attributes. In [12], we have developed a method to mine mixed implications whose main goal has been to avoid the management of the large (K|K) contexts, so that the performance of the corresponding method has a controlled cost. First, we extend the definitions of derivation operators, formal concept, association rule and attribute implication. Definition 1. Let K=hG, M, Iibe a formal context. We define the operators ⇑: 2G→2M∪Mand ⇓: 2M∪M→2Gas follows: for X⊆Gand Y⊆M∪M, X⇑={m∈M| hg, mi ∈ Ifor all g∈X} ∪ {m∈M| hg, mi 6∈ Ifor all g∈X}(5) Y⇓={g∈G| hg, mi ∈ Ifor all m∈Y} ∩ {g∈G| hg, mi 6∈ Ifor all m∈Y}(6) Definition 2. Let K=hG, M, Iibe a formal context. A mixed formal concept in Kis a pair of subsets hX, Y iwith X⊆Gand Y⊆M∪Msuch X⇑=Yand Y⇓=X. To extending association rules to mixed attributes, we have to change the definition of support and, consequently, the confidence. For any subset Y⊆ M∪M,supp(Y) = |Y⇓|/|G|. Definition 3. Let K=hG, M, Iibe a formal context and let A, B ⊆M∪M, the context Ksatisfies a mixed attribute implication A→B, denoted by K|= A→B, if A⇓⊆B⇓. For example, in Table 1, as we previously mentioned, two different situations were presented. Thus, in this new framework we have that K6|=b→dand K|=b→dwhereas K6|=b→ceither K6|=b→c. In [12], we tackled this issue focusing on the problem of mining implication with positive and negative attributes from formal contexts. As a conclusion of that work we emphasized the necessity of a full development of the algebraic framework. A first step in this line was introduced in [13]. Although FuzAtAnalyzer deals with both, classical and fuzzy implications, in this paper we concentrate on classical implications as the target element to include negative attributes. Thus, in this first step our intention is to develop a tool which carries out the knowledge discovering of the full information in the system limited to the crisp case. Having said that, in this work we also allows the treatment of association rules. The main reason is to consider as much information as possible relaxing the implication semantics. Thus, association rules provides us more information without a significant change in the theoretical background model as fuzzy implications demands. In this paper, we present how we incorporate these results to our tool, extending our previous work about fuzzy attributes implications and fuzzy data tables. This is a previous step in the extension of these results to fuzzy case. 2 FuzAtAnalyzer Related to our research project, we develope a JAVA program called FuzAtAnalyzer that was initially used with fuzzy functional dependencies [?] and Fuzzy Attribute Tables [5]. Datasets are imported from Microsoft Excel archives (using Java Excel API[16]) where there is a degree between 0 and 1 that represents the relation of an object with an attribute. It is writed 1 if and object has an attribute and 0 if it has not in the case of Formal Concept Analysis with crisp data. In the original version we focus our attention to obtaining implicational systems and the knowledge related to them implementing algorithms that appear in [5, ?,?,?,?,?] Fig. 1. Screen capture of FuzAtAnalyzer We adapt this tool for working with datasets used in Formal Concept Analysis, implementing different algorithms like the former NextClosure [10]. In a first step, we use only positive attributes but, applying the theory that appears in [12], we extend the study to mixed attributes. To the previous options that generates (fuzzy) formal concepts and implications with positive attributes, we add an option that generates mixed attributes implications and mixed concepts implementing the algorithm 3 in [12], adapting it to extract mixed concepts too. This can be do with other programs like Concept Explorer [15] using the apposition {K|K}but this implementation allow us to generate the results in an easy and efficient way from an imported dataset. Also, we add options that generate the mixed lattice and the implicational system in latex that allows to export the results to different documents. The lattice is generated using the package XYPic[17] of latex, distributing the concepts by levels based in the number of attributes, positives and negatives, in the intents of the concepts. In a specific section for detecting errors, we adapt the methods for obtaining association rules that works with negative attributes too. This adaption allows us to compare these association rules with implications obtaining knowledge about the confidence and support for the subsets of mixed attributes. We can classify by relevance the mixed implications in order of the support of the subsets of mixed attributes that compose these implications. 3 Example We are going to use an example with 9 objects and 5 attributes that corresponds to the dataset represented in the context in Table 2. I a b c d e o11 1 1 1 1 o20 1 0 1 1 o30 1 1 1 0 o40 1 1 0 1 o50 1 0 1 0 o61 0 1 0 0 o70 1 0 0 0 o81 0 1 0 1 o90 0 0 0 0 Table 2. A formal context From this dataset, in a simple step, we can calculate the implicational system and the mixed concepts and we can export this data automatically to a latex archive with the representation of the lattice. The mixed implicational system is {d→b,de →c,c→a,cde →ab, be →a,bd →a,bcd →a,bcde →a,ae →b,ac →b}that extends the original implicational system with positive attributes {d→b,bcde →a,a→c, abc →de}. The 2 first implications are included in the mixed implicational system and the others can be deduced from it. The 48 concepts of the mixed concepts lattice associated with the context of Table 2 are represented in Figure 2. The file over the bottom concept is conformed with atoms, whereas the concepts represented with a square are the meet-irreducible elements. All the elements of the mixed concepts lattice can be represented as infimum of meeet-irreducible elements and supremum of joinirreducible elements (atoms). 0 123456 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 Fig. 2. Mixed concept lattice. In a second phase, we examine association rules with a minimun value 0.4 of confidence. This means that, at least, one attribute or his negative appears in the subsets of single attributes. In the case of considering only positives attributes, {X⊆M|supp(X)> 0.4}={b, c, d, e, bd}. The association rules that we can obtain are d→b and b→dwhich confidences are 1 and 0.67 respectively. Adding the negative and mixed attributes, we have that {X⊆M∪M|supp(X)>0.4}= {a, b, c, c, d, d, e, e, ab, ae, bd, ac}and the new mixed association rules are b→ a, a →bwith confidences 0.83, e→awith confidence 0.8, a→ewith confidence 0.67, c→awith confidence 1 and a→cwith confidence 0.67. With this study of minimun supports of antecedents and consequents of each association rule with confidence 1, we can define the relevance of the implication asociated to it and how a mixed rule could be more representative that a positive one. Acknowledgements References 1. R. Agrawal, T. Imieli´ nski and A. Swami,Mining Association Rules Between Sets of Items in Large Databases, SIGMOD Rec.,22,207–216,1993 2. W. Armstrong,Dependency structures of data base relationships, Proc. IFIP Congress. North Holland, Amsterdam,580–583,1974 3. K. Bertet and B. Monjardet,The multiple facets of the canonical direct unit implicational basis, Theor. Comput. Sci.,411, 22-24,2010,2155-2166 4. P. Cordero, M. Enciso, A. Mora, I. Perez de Guzm´ an and J. M. Rodr´ ıguez-Jim´ enez,An Efficient Algorithm for Reasoning about Fuzzy Functional Dependencies, Advances in Computational Intelligence - International WorkConference on Artificial Neural Networks (IWANN),2,412–420,2011 5. P. Cordero, M. Enciso, A. Mora, I. Perez de Guzman and J. M. Rodr´ ıguez-Jim´ enez,Specification and inference of fuzzy attributes, Proceedings of the IEEE Symposium on Foundations of Computational Intelligence, FOCI 2011, part of the IEEE Symposium Series on Computational Intelligence 2011, Paris, France,107–114 6. A. Mora, M. Enciso and P.Cordero,Closure via functional dependence simplification, International Journal of Computer Mathematics, 89 4, 510–526, 2012 7. P. Cordero, M. Enciso, A. Mora and M. Ojeda-Aciego,Computing Minimal Generators from Implications: a Logic-guided Approach, CLA,187–198,2012 8. P. Cordero, M. Enciso, A. Mora and J. M. Rodr´ ıguez-Jim´ enez,Computing non-redundant sets of functional dependencies via simplification, IEEE Symposium on Foundations of Computational Intelligence (FOCI),9–14,2013 9. P. Cordero, M. Enciso, A. Mora and J. M. Rodr´ ıguez-Jim´ enez,Automated Inference with Fuzzy Functional Dependencies over Graded Data, Advances in Computational Intelligence - International Work-Conference on Artificial Neural Networks (IWANN),2254–265,2013 10. B. Ganter,Two basic algorithms in concept analysis,Technische Hochschule, Darmstadt, 1984 11. J.L. Guigues and V. Duquenne,Familles minimales d implications informatives resultant d un tableau de donnees binaires,Mathematiques et Sciences Sociales,95, 5–18, 1986. 12. J. M. Rodr´ ıguez-Jim´ enez, P. Cordero, M. Enciso, and A. Mora,Negative attributes and implications in formal concept analysis,Procedia Computer Science, 31(0):758 – 765, 2nd International Conference on Information Technology and Quantitative Management, ITQM 2014 13. J. M. Rodr´ ıguez-Jim´ enez, P. Cordero, M. Enciso and A. Mora,A generalized framework to consider positive and negative attributes in formal concept analysis, CLA,267–278, 2014 14. R. Wille. Restructuring lattice theory: an approach based on hierarchies of concepts, Rival, I. (ed.): Ordered Sets, 445–470. Boston, 1982. 15. http://conexp.sourceforge.net/ 16. http://jexcelapi.sourceforge.net/ 17. https://tug.org/applications/Xy-pic/Xy-pic.html