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

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.