Removing redundancy for attribute implications in data with grades

Removing redundancy for attribute implications in data with grades E. Rodr´ ıguez-Lorenzo, Pablo Cordero, Manuel Enciso, ´ Angel Mora 1Universidad de M´ alaga. Andaluc´ ıa Tech. Spain {estrellarodlor,amora}@ctima.uma.es,{pcordero,enciso}@uma.es Extended abstract Reasoning with if-then rules –in particular, with those taking from of implications between conjunctions of attributes– is crucial in many disciplines ranging from theoretical computer science to applications. One of the most important problems regarding the rules is to remove redundancies in order to obtain equivalent implicational sets with lower size. This problem, which has been widely studied in the classical setting, is partially addressed in [4] for the case of attribute implications in data with grades. In this work, we tackle this problem using the so-called Fuzzy Attribute Simplification Logic, FASL, which has been introduced in [1]. This logic leads to an automatic reasoning method for implications in data with grades. FASL manages formulas A⇒Bwhere Aand Bare fuzzy sets over an alphabet Ωwhose elements are named attributes. Interpretations are fuzzy formal contexts and, informally, an implication such as {a,0.5/b} ⇒ {0.9/c}means every object that has attribute ato degree 1 (i.e. fully possesses a), and attribute bto degree 0.5, has attribute cto degree at least 0.9. Specifically, truthfulness structures in FASL are tuples hL,∨,∧,⊗,→,r,∗,0,1iwhere hL,∨,∧,⊗,→,0,1iis a complete residuated lattice, ∗is an hedge (a “very true” function [2]) and ris a binary operation satisfying the following adjointness property: arb≤cif and only if a≤b∨cfor all a,b,c∈L. As a consequence, arb=V{c∈L|a≤b∨c}. In particular, when the lattice is linearly ordered, we have arb=a,if a>b, 0,otherwise. (1) These operations are pointwise extended to fuzzy sets. For a fuzzy formal context K=hX,Y,Iisuch that Y=Ω, the degree in which A⇒Bis true in Kis defined as follows: kA⇒BkK=^ x∈X^ y∈Y (A(y)→I(x,y))∗→^ y∈Y (B(y)→I(x,y))(2) The axiomatic system in FASL is defined as follows: for all A,B,C,D∈LΩand c∈L, [Ax]infer A∪B⇒A(Axiom) Supported by project TIN2014-59471-P of the Science and Innovation Ministry of Spain, co-funded by the European Regional Development Fund (ERDF). XVIII Congreso Espa˜ nol sobre Tecnolog´ ıas y L´ ogica Fuzzy (ESTYLF 2016) 134 [Mul]from A⇒Binfer c∗⊗A⇒c∗⊗B(Multiplication) [Sim]from A⇒Band C⇒Dinfer A∪(CrB)⇒D(Simplification) The soundness and completeness are ensured when we assume that both Land Ωare finite. In addition, for any A,B,C,D∈LY, the following equivalences hold true: (DeEq){A⇒B}≡{A⇒BrA}; (UnEq){A⇒B,A⇒C}≡{A⇒B∪C}; (SiEq) If A⊆Cthen {A⇒B,C⇒D}≡{A⇒B,A∪(CrB)⇒DrB}. In [4], V. Vychodil consider globalization as hedge and provides a polynomial algorithm for computing a non-redundant equivalent set for a given implicational set. An implicational set Tis said to be non-redundant if no implications in Tcan be inferred from others implications. The main goal here is in the same direction, but considering an arbitrary hedge and using FASL. As a first stage in this line, we propose the use of (DeEq), (UnEq) and (SiEq) for removing redundant information in an implicational set. Specifically, the method here proposed crosses the sets of implications (quadratic complexity) taking pairs of implications and applies the above mentioned equivalences. For instance, consider h{0,0.5,1},∨,∧,⊗,→,r,∗,0,1ibeing the three-element equidistant subchain of the standard Łukasiewicz algebra with ∗being the identity and ras described in (1). For the implicational set T1={0.5/x,y,0.5/z}⇒{x,0.5/y,0.5/z},{0.5/y}⇒{0.5/x,0.5/y,z}, {0.5/x,0.5/y}⇒{y,z},{x,z}⇒{0.5/x,y,0.5/z},{z}⇒{0.5/x} in [4], the author obtains T2={0.5/y}⇒{x,y,z},{z}⇒{0.5/x}{x,z}⇒{0.5/x,y,0.5/z} However, our method, which has been implemented in PROLOG, renders the following equivalent set: T3={0.5/x}⇒{x},{0.5/y}⇒{0.5/x,y,z},{z}⇒{y} References [1] Radim Belohlavek, Pablo Cordero, Manuel Enciso, ´ Angel Mora, Vilem Vychodil: Automated prover for attribute dependencies in data with grades. International Journal of Approximate Reasoning. Vol. 70 (2016) 51–67. [2] Radim Belohlavek, Vilem Vychodil. Attribute implications in a fuzzy setting. Lecture Notes in Computer Science. Vol. 3874, 45–60. [3] Radim Belohlavek, Vilem Vychodil. Attribute implications in a fuzzy setting. Lecture Notes in Computer Science. Vol. 3874, 45–60. Vilem Vychodil. On minimal sets of graded attribute implications, Information Sciences. Vol. 294, 478–488. [4] Vilem Vychodil: On minimal sets of graded attribute implications. Information Sciences. Vol. 294 (2015) 478–488. XVIII Congreso Espa˜ nol sobre Tecnolog´ ıas y L´ ogica Fuzzy (ESTYLF 2016) 135