Tolerant inclusion

Slide1: 

On a Proximity-Based Tolerant Inclusion Patrick Bosc, Allel Hadjali and Olivier Pivert IRISA/ENSSAT France I. Context and objectives II. Preliminaries and background III. Proximity-based tolerant inclusion IV. Application to the division of relations V. Conclusion

Slide2: 

Context and objectives Two types of “fuzzy extensions” of the inclusion have been previously defined: - Boolean inclusion between fuzzy sets (e.g., Zadeh’s proposal) - graded inclusion between fuzzy sets Previous work by the authors [Fuzz-IEEE’05, FSS 2006, FlexDBIST’06]: quantitative-exception-tolerant inclusion based on the relaxation of the quantifier  “almost all of the elements which are in E are in F” idea: to tolerate a certain ratio of exceptions qualitative-exception-tolerant inclusion based on a relaxed fuzzy implication “all of the elements which are in E are almost in F” (i.e., are almost as much in F as they are in E) idea: to ignore (to a certain extent) the “low intensity” exceptions Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide3: 

Context and objectives New idea : to take into account the notion of closeness between the elements of the domain  proximity-based tolerant inclusion Different formulations are possible, among which, the following “simple” one: E pr F iff x  E, either (x  F) or (F contains an element close to x) More “sophisticated” expressions can also be thought of. In the following, only Boolean tolerant inclusions are considered. Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide4: 

Preliminaries and background Boolean inclusion of fuzzy sets (E  F)  ( x  X, mE(x)  mF(x)) (E  F)  ( x  X, (x  E) RG (x  F)) where RG is Rescher-Gaines’ implication (p RG q = 1 if p  q, 0 otherwise) Does not take into account the proximity between the elements of the domain Example: A = {1/a, 0.6/b} B = {1/a, 0.4/b, 0.9/c} According to the formulas above, A is not included in B However, if we know that b is very close to c, it may make sense to say that A  B Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide5: 

Preliminaries and background Proximity-based modifiers Let us consider a tolerance indicator Z, i.e., a fuzzy interval centered in 0 such that: i) Z(r) = Z(-r) ii) Z(0) = 1 iii) the support of Z is of the form [-, ] where  is a positive real number Let us consider a scalar domain U and introduce an absolute proximity relation E[Z] defined as: E[Z]: U  U  [0, 1] (u, v)  E[Z](u, v) = Z(u - v) E[Z] can be used to modify a fuzzy set F into a relaxed fuzzy set EZ (dilation) or a more restricted fuzzy set EZ (erosion) Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide6: 

Preliminaries and background Proximity-based modifiers (cont.) Dilation operation EZ(F)(s) = sup r  U (F(r), E[Z](s, r)) where  is a triangular norm EZ(F) gathers the elements of F and those outside of F which are somewhat close to an element in F (in the sense of E[Z]) Erosion operation EZ(F)(s) = inf r  U (E[Z](s, r)  F(r)) where  is a fuzzy implication EZ(F) gathers the elements of F such that all of their neighbors (i.e., those which are somewhat close to them in the sense of E[Z]) are in F Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide7: 

Preliminaries and background Proximity-based modifiers (cont.) Example (with  = min and  : Kleene-Dienes implication) F = {0.4/46, 0.3/52, 0.6/53, 1/54} Z = (-1, 1, 2, 2) EZ(F)(s) = {0.4/44, 0.4/45, 0.4/46, 0.4/47, 0.4/48, 0.3/50, 0.5/51, 0.6/52, 1/53, 1/54, 1/55, 0.5/56} EZ(F)(s) = {0.3/53} Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division -2 2 1 -1 1 -3 3 Z

Slide8: 

Proximity-based tolerant inclusion One may choose to replace A  B by: 1. EZ(A)  B or by: 2. A  EZ(B) or by: 3. EZ(A)  EZ(B) or by: 4. EZ(A)  B  A  EZ(B) or by: 5. EZ(A)  B  A  EZ(B) In the following, we use the last solution (5). Remark: it is the most drastic one among 3, 4, 5. Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide9: 

Proximity-based tolerant inclusion Tolerant inclusion of crisp sets A Boolean proximity relation must be used, based on a regular interval Z = [-, ] E[Z](u, v) is true if |u - v|  , false otherwise EZ(F)(s) = {s  U |  r  U such that r  F and E[Z](r, s)} EZ(F)(s) = {s  F |  r  U, E[Z](r, s)  r  F} Example. A = {41, 59} B = {40, 48, 60} Z = [-1, 1] EZ(A) =  EZ(B) = {39, 40, 41, 47, 48, 49, 59, 60, 61} EZ(A)  B  A  EZ(B) thus A Z B Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide10: 

Proximity-based tolerant inclusion Tolerant inclusion of fuzzy sets EZ(F)(s) = sup r  U (F(r), E[Z](s, r)) where  is a triangular norm EZ(F)(s) = inf r  U (E[Z](s, r)  F(r)) where  is a fuzzy implication A Z B  EZ(A)  B  A  EZ(B) Question: do the axioms valid for Boolean inclusion still hold for Z ? (A1) A  B  Bc  Ac where Xc denotes the complement of X in the universe U (A2) A  (B  C)  (A  B)  (A  C) (A3) A  B  S(A)  S(B) where S(A)(x) = A(S(x)) with a one-to-one mapping S: U  U Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide11: 

Proximity-based tolerant inclusion Tolerant inclusion of fuzzy sets Remark: A1, A2 and A3 hold when  is replaced by Z and the sets are crisp Axiom A1. A Z B  Bc Z Ac when A and B are fuzzy sets ? Result: A1 holds if the erosion operation uses the S-implication generated by the t-norm  underlying the associated dilation operation Remark: instead of (t-norm, S-impl) it is possible to use (ncc, R-impl) Axiom A2. A Z (B  C)  (A Z B)  (A Z C) when A, B and C are fuzzy sets ? Result: only a weakened form of this axiom holds: A Z (B  C)  (A Z B)  (A Z C) Axiom A3 straightforwardly holds in the generalized case considered. Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide12: 

Application to the division of relations Reminder Let us consider the relations r and s of respective schemas R(A, X) and S(B) where A and B are compatible (sets of) attributes div(r, s A, B) = {x | s  (x)} where (x) = {a | <x, a>  r} Example. suppliers (s) of schema S(#store, #chain, zipcode, turnover) census (c) of schema (city, zipcode, population) Query: find the chains which have a store with a turnover greater than 0.5 k€ in every city from relation c whose population is over 200,000 div(project(select(s, turnover > 0.5), {chain, zipcode}, project(select(c, population > 200,000), {zipcode}, {zipcode}, {zipcode}) Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division

Slide13: 

Application to the division of relations Example (cont.) s c Result of the division = {<32>} Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division #store chain zipc turnover 15 32 75000 1.2 12 32 69000 0.54 34 32 69000 0.25 26 32 13000 0.89 28 7 13000 0.51 78 7 49000 0.37 city zipc pop Paris 75000 2 126 000 Lyon 69000 446 000 Saint-Brieuc 22000 47 000 Marseille 13000 798 000 Angers 49000 152 000

Slide14: 

Application to the division of relations Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division Tolerant division defined as: div(r, s A, B) = {x | s Z (x)} where (x) = {a | <x, a>  r} The notion of proximity between the values of the division attribute(s) is taken into account. Example (cont.) tolerance on the zipcode (the stores are often in the suburbs) Assumption: the difference between the zipcodes reflects the distance between the cities

Slide15: 

Application to the division of relations Example (cont.) s c with Z = (- 900, 900, 0, 0), one gets: Result of the non-tolerant division =  Result of the tolerant division = {32} Remark: the same principle can be used to define a tolerant division of fuzzy relations Context and objectives Preliminaries and background Proximity-based tolerant inclusion Application to the division city zipc pop Paris 75000 2 126 000 Lyon 69000 446 000 Saint-Brieuc 22000 47 000 Marseille 13000 798 000 Angers 49000 152 000

Slide16: 

Conclusion Main results - Definition of a tolerant inclusion that takes into account the proximity between the elements of the domain - study of the properties of such an operator (wrt the axioms of the regular division) - definition of a tolerant division operator in the database context - other potential applications : information retrieval, search engines, ... (tolerant inclusion based on semantic distance between terms) Perspectives study of a graded tolerant inclusion between fuzzy sets Preliminaries and background Proximity-based tolerant division Application to the division Conclusion