# Interest Measures for Fuzzy Association Rules Based on Expectations of Independence

Authors: Michal Burda
Journal: Advances in Fuzzy Systems
 (2014)

---

## Abstract

Lift, leverage, and conviction are three of the best commonly known interest measures for crisp association rules. All of them are based on a comparison of observed support and the support that is expected if the antecedent and consequent part of the rule were stochastically independent. The aim of this paper is to provide a correct definition of lift, leverage, and conviction measures for fuzzy association rules and to study some of their interesting mathematical properties.


---

## Body

## 1. Introduction

Searching for association rules is a broadly discussed, developed, and accepted data mining technique [1, 2]. An association rule is an expression X⇀Y, where antecedent X and consequent Y are conditions, the former usually in the form of elementary conjunction and the latter being usually atomic. Such rules are usually interpreted as the following implicational statement: “if X is satisfied then Y is true very often too.”Naturally, analysts are interested only in such rules that are somehow interesting, unusual, or exceptional. To assess rule interestingness objectively, there have been developed many measures of rule interest or intensity. Among the most essential,support andconfidence are traditionally considered. An objective of association rules mining is to find rules withsupport andconfidence above some user-defined thresholds.Searching for association rules fits particularly well on binary or categorical data and many have been written on that topic [1–4]. For association analysis on numeric data, a prior discretization is proposed, for example, by Srikant and Agrawal [5]. Another alternative is to take an advantage of fuzzy logic [6].The use of fuzzy logic in connection with association rules has been motivated by many authors (see e.g., [7] for recent overview). Fuzzy association rules are appealing also because of the use of vague linguistic terms such as “small” and “very big” [8–11].In this paper, we focus on three measures of rule intensity that are all based on comparison between the observed support and the support that is expected under the assumption of independence of the rule’s antecedent and consequent. These measures arelift,leverage, andconviction. All of them were initially developed for nonfuzzy (i.e., “crisp”) association rules.Lift was firstly described in [12] under its original name “interest.” It was well studied for association rules on binary data in [13, 14]. Lift is defined as a ratio of observed support X∧Y to the support that is expected under the assumption of independence of X and Y.On the other hand,leverage [15] measures the difference of observed and expected supports. (Hence, it is very similar to lift.)Conviction [12] is defined as a ratio of expected and observed support of X∧¬Y. Although it is very similar to lift, its properties are more similar to confidence. Lallich et al. [16] provide a nice overview of many other crisp rule measures.As quite many have been written about these measures for crisp association rules, not so much has been done with respect to fuzzy rules. Unfortunately, simplicity of definitions for crisp rules sometimes led to oversimplified definitions for fuzzy rules. Some authors believe the generalization of those crisp measures for fuzzy data is as trivial as substituting crisp terms with analogous fuzzy terminology inside of crisp-case definitions; see, for example, [17, 18]. Unfortunately, as discussed in this paper, such oversimplification may lead to erroneous outputs. In order to preserve some nice mathematical properties, one must take care of the type of the t-norms being used.In Section2, a brief theoretical background for both binary and fuzzy association rules is provided. Section 2.3 discusses shortly naive definitions of lift, leverage, and conviction and shows a simple example where the rational interpretations of these measures become broken. Before providing corrected definitions in Section 4, an essential notion ofexpected support is analysed in Section 3. Finally, Section 5 concludes the paper with summarization of the achieved goals and drawings of the possible directions of future research.


## 2. Theoretical Background

### 2.1. Binary Association Rules

LetO:={o1,o2,…,on}, n>0, be a finite set of objects and let A:={a1,a2,…,am}, m>0, be a finite set of attributes (features). Each attribute can be considered as a logical predicate: ai(oj) is true (or false) accordingly to whether the ith attribute applies (or does not apply) to object oj. For a subset X⊆A of attributes, let us define a new predicate of a logical conjunction of the attributes contained in X as follows:(1)X(oj):≡∀ai∈X:ai(oj).Moreover, let us define a negated predicate¬X(oj) as follows:
(2)¬X(oj):≡∃ai∈X:¬ai(oj).An association rule is a formulaX⇀Y, where X⊂A is anantecedent, Y⊂A is aconsequent, and X∩Y=∅. (Typically, |X|≥1 and |Y|=1.) Both X and Y are sometimes calleditemsets. Please consider the following rule as an example:
(3){tequila,salt}⟶{lemon}.Thesupport andconfidence are defined as follows [2, 19]:
(4)supp⁡(X):=|{o∈O∣X(o)}|n,(5)supp⁡(X⇀Y):=|{o∈O∣X(o)∧Y(o)}|n,(6)conf(X⇀Y):=supp⁡(X⇀Y)supp⁡(X),
where n=|O|. Evidently, supp⁡(¬X)=1-supp⁡(X).IfO is a random sample, then observing o∈O is a random event. Then also a random event X may be defined on the basis of the truth value of the predicate X(o) and support supp⁡(X) becomes an estimate of a probability P(X). Then also supp⁡(¬X) would correspond to the probability P(X-), where X- is complementary event to X. Confidence conf(X⇀Y) would then be an estimate of conditional probability P(Y∣X).Lift [12],leverage [15], andconviction [12] for binary data are defined as follows:
(7)lift(X⇀Y):=supp⁡(X⇀Y)supp⁡(X)·supp⁡(Y)=conf(X⇀Y)supp⁡(Y);(8)lever(X⇀Y):=supp⁡(X⇀Y)-supp⁡(X)·supp⁡(Y);(9)conv(X⇀Y):=supp⁡(X)·supp⁡(¬Y)supp⁡(X⇀¬Y)=1-supp⁡(Y)1-conf(X⇀Y).IfX and Y are stochastically independent, P(X∧Y)=P(X)·P(Y); that is, the expression supp⁡(X)·supp⁡(Y) is an estimation of support supp⁡(X⇀Y) under the assumption of X and Y being independent.Hence, liftlift(X⇀Y) is a ratio of observed support to the support that is expected under the assumption of independence, leverage lever(X⇀Y) is a difference of observed and expected support, and conviction is a ratio of the expected support of X appearing without Y to the observed support supp⁡(X⇀¬Y).IfX and Y are independent, lift(X⇀Y)≃1, conv(X⇀Y)≃1, and lever(X⇀Y)≃0. The values of lift(X⇀Y)>1, conv(X⇀Y)>1, and lever(X⇀Y)>0 indicate positive relationship, while lift(X⇀Y)<1, conv(X⇀Y)<1, and lever(X⇀Y)<0 indicate negative relationship.


### 2.2. Fuzzy Association Rules

For fuzzy association rules, domain of each fuzzy attributea∈A is not binary (or “crisp”) {0,1} but graded (or “fuzzy”), that is, interval [0,1]. That is, for each a∈A and o∈O, a(o)∈[0,1]. For a subset X⊆A of fuzzy attributes, we define a new predicate of a logical conjunction (similarly to binary case (1)) by using a t-norm ⊗ as
(10)X(oj):=⨂a∈Xa(oj).T-norm
⊗ is a generalized logical conjunction, that is, a function [0,1]×[0,1]→[0,1] which is associative, commutative, and monotone increasing (in both places) and which satisfies the boundary conditions α⊗0=0 and α⊗1=α for each α∈[0,1]. Some well-known examples of t-norms are as follows:(i)
productt-norm: ⊗prod(α,β)=αβ;(ii)
minimumt-norm: ⊗min⁡⁡(α,β)=min⁡⁡(α,β);(iii)
Łukasiewiczt-norm: ⊗Łuk(α,β)=max⁡⁡(0,α+β-1).Negation of fuzzy predicatea is often defined for any o∈O as ¬a(o):=1-a(o). Then, we can define (similarly to (2)) a negated predicate ¬X as follows:
(11)¬X(oj)≔1-X(oj).Leta∈A, o∈O, n=|O|, n>0, X,Y⊂A, X≠∅, Y≠∅, and X∩Y=∅. Several intensity measures may be defined as follows:
(12)fsupp(X):=∑o∈OX(o)n,fsupp(X⇀Y):=∑o∈O(X(o)⊗Y(o))n,fconf(X⇀Y):=fsupp(X⇀Y)fsupp(X).Convention 1.
Throughout this text, we assume⊗ is an arbitrary (but fixed) t-norm. Where it is important to explicitly specify a concrete t-norm, say ⊗prod, we put ⊗prod in subscript and write, for example, fsupp⊗prod(X⇀Y) instead of fsupp(X⇀Y) or X⊗prod(o) instead of X(o).Convention 2.
For the sake of simplicity, we will sometimes express a fuzzy attribute as a vector of membership degrees. For instance, supposea∈A is a fuzzy attribute on a set of objects O={o1,o2,o3}. Then, instead of writing a(o1):=0.3, a(o2):=0.9, and a(o3):=1, we will use a much concise form: a:=(0.3,0.9,1).Example 1.
Leta:=(a1,a2,a3), b:=(b1,b2,b3), and c:=(c1,c2,c3) be fuzzy attributes. Then,
(13)fsupp⊗prod({a,b}⇀{c})=13∑i=13‍(ai⊗prodbi⊗prodci).


### 2.3. Naive Definition of Lift, Leverage, and Conviction for Fuzzy Association Rules

A naive approach for introducing lift, leverage, and conviction into the fuzzy association rules framework is to use simply their definitions (7), (8), and (9) for binary rules and replace binary support (4) and (5) and confidence (6) with their fuzzy alternatives (12) as, for example, in [17, 18]. Unfortunately, that approach works well only for ⊗ being the product t-norm. As indicated in the following experiment, using minimum or Łukasiewicz t-norms may lead to erroneous interpretations.Experiment 1.
Two vectorsX and Y of size n=2000 were randomly generated from the uniform distribution on the interval [0,1] so that they are stochastically independent. Above-described naive versions of lift, leverage, and conviction of a rule X⇀Y were computed with using minimum, product, and Łukasiewicz t-norms as ⊗; see Table 1 for results.
As discussed in Section2.1, stochastically independent data are expected to result in lift and conviction being close to 1 while leverage is expected to be close to 0. As can be seen, this is the case only for product t-norm.Table 1
Comparison of lift, leverage, and conviction computed with differentt-norms on stochastically independent data generated randomly from uniform distribution.
Naive lift
Naive leverage
Naive conviction
Łukasiewiczt-norm
0.675
−0.081
1.544
Productt-norm
1.012
0.003
1.012
Minimumt-norm
1.353
0.088
0.755The values of naive lift and naive leverage wrongly indicate positive (resp., negative) relationship, if the minimum (resp., Łukasiewicz)t-norm is used. Paradoxically, naive conviction indicates opposite sign of relationship.


## 2.1. Binary Association Rules

LetO:={o1,o2,…,on}, n>0, be a finite set of objects and let A:={a1,a2,…,am}, m>0, be a finite set of attributes (features). Each attribute can be considered as a logical predicate: ai(oj) is true (or false) accordingly to whether the ith attribute applies (or does not apply) to object oj. For a subset X⊆A of attributes, let us define a new predicate of a logical conjunction of the attributes contained in X as follows:(1)X(oj):≡∀ai∈X:ai(oj).Moreover, let us define a negated predicate¬X(oj) as follows:
(2)¬X(oj):≡∃ai∈X:¬ai(oj).An association rule is a formulaX⇀Y, where X⊂A is anantecedent, Y⊂A is aconsequent, and X∩Y=∅. (Typically, |X|≥1 and |Y|=1.) Both X and Y are sometimes calleditemsets. Please consider the following rule as an example:
(3){tequila,salt}⟶{lemon}.Thesupport andconfidence are defined as follows [2, 19]:
(4)supp⁡(X):=|{o∈O∣X(o)}|n,(5)supp⁡(X⇀Y):=|{o∈O∣X(o)∧Y(o)}|n,(6)conf(X⇀Y):=supp⁡(X⇀Y)supp⁡(X),
where n=|O|. Evidently, supp⁡(¬X)=1-supp⁡(X).IfO is a random sample, then observing o∈O is a random event. Then also a random event X may be defined on the basis of the truth value of the predicate X(o) and support supp⁡(X) becomes an estimate of a probability P(X). Then also supp⁡(¬X) would correspond to the probability P(X-), where X- is complementary event to X. Confidence conf(X⇀Y) would then be an estimate of conditional probability P(Y∣X).Lift [12],leverage [15], andconviction [12] for binary data are defined as follows:
(7)lift(X⇀Y):=supp⁡(X⇀Y)supp⁡(X)·supp⁡(Y)=conf(X⇀Y)supp⁡(Y);(8)lever(X⇀Y):=supp⁡(X⇀Y)-supp⁡(X)·supp⁡(Y);(9)conv(X⇀Y):=supp⁡(X)·supp⁡(¬Y)supp⁡(X⇀¬Y)=1-supp⁡(Y)1-conf(X⇀Y).IfX and Y are stochastically independent, P(X∧Y)=P(X)·P(Y); that is, the expression supp⁡(X)·supp⁡(Y) is an estimation of support supp⁡(X⇀Y) under the assumption of X and Y being independent.Hence, liftlift(X⇀Y) is a ratio of observed support to the support that is expected under the assumption of independence, leverage lever(X⇀Y) is a difference of observed and expected support, and conviction is a ratio of the expected support of X appearing without Y to the observed support supp⁡(X⇀¬Y).IfX and Y are independent, lift(X⇀Y)≃1, conv(X⇀Y)≃1, and lever(X⇀Y)≃0. The values of lift(X⇀Y)>1, conv(X⇀Y)>1, and lever(X⇀Y)>0 indicate positive relationship, while lift(X⇀Y)<1, conv(X⇀Y)<1, and lever(X⇀Y)<0 indicate negative relationship.


## 2.2. Fuzzy Association Rules

For fuzzy association rules, domain of each fuzzy attributea∈A is not binary (or “crisp”) {0,1} but graded (or “fuzzy”), that is, interval [0,1]. That is, for each a∈A and o∈O, a(o)∈[0,1]. For a subset X⊆A of fuzzy attributes, we define a new predicate of a logical conjunction (similarly to binary case (1)) by using a t-norm ⊗ as
(10)X(oj):=⨂a∈Xa(oj).T-norm
⊗ is a generalized logical conjunction, that is, a function [0,1]×[0,1]→[0,1] which is associative, commutative, and monotone increasing (in both places) and which satisfies the boundary conditions α⊗0=0 and α⊗1=α for each α∈[0,1]. Some well-known examples of t-norms are as follows:(i)
productt-norm: ⊗prod(α,β)=αβ;(ii)
minimumt-norm: ⊗min⁡⁡(α,β)=min⁡⁡(α,β);(iii)
Łukasiewiczt-norm: ⊗Łuk(α,β)=max⁡⁡(0,α+β-1).Negation of fuzzy predicatea is often defined for any o∈O as ¬a(o):=1-a(o). Then, we can define (similarly to (2)) a negated predicate ¬X as follows:
(11)¬X(oj)≔1-X(oj).Leta∈A, o∈O, n=|O|, n>0, X,Y⊂A, X≠∅, Y≠∅, and X∩Y=∅. Several intensity measures may be defined as follows:
(12)fsupp(X):=∑o∈OX(o)n,fsupp(X⇀Y):=∑o∈O(X(o)⊗Y(o))n,fconf(X⇀Y):=fsupp(X⇀Y)fsupp(X).Convention 1.
Throughout this text, we assume⊗ is an arbitrary (but fixed) t-norm. Where it is important to explicitly specify a concrete t-norm, say ⊗prod, we put ⊗prod in subscript and write, for example, fsupp⊗prod(X⇀Y) instead of fsupp(X⇀Y) or X⊗prod(o) instead of X(o).Convention 2.
For the sake of simplicity, we will sometimes express a fuzzy attribute as a vector of membership degrees. For instance, supposea∈A is a fuzzy attribute on a set of objects O={o1,o2,o3}. Then, instead of writing a(o1):=0.3, a(o2):=0.9, and a(o3):=1, we will use a much concise form: a:=(0.3,0.9,1).Example 1.
Leta:=(a1,a2,a3), b:=(b1,b2,b3), and c:=(c1,c2,c3) be fuzzy attributes. Then,
(13)fsupp⊗prod({a,b}⇀{c})=13∑i=13‍(ai⊗prodbi⊗prodci).


## 2.3. Naive Definition of Lift, Leverage, and Conviction for Fuzzy Association Rules

A naive approach for introducing lift, leverage, and conviction into the fuzzy association rules framework is to use simply their definitions (7), (8), and (9) for binary rules and replace binary support (4) and (5) and confidence (6) with their fuzzy alternatives (12) as, for example, in [17, 18]. Unfortunately, that approach works well only for ⊗ being the product t-norm. As indicated in the following experiment, using minimum or Łukasiewicz t-norms may lead to erroneous interpretations.Experiment 1.
Two vectorsX and Y of size n=2000 were randomly generated from the uniform distribution on the interval [0,1] so that they are stochastically independent. Above-described naive versions of lift, leverage, and conviction of a rule X⇀Y were computed with using minimum, product, and Łukasiewicz t-norms as ⊗; see Table 1 for results.
As discussed in Section2.1, stochastically independent data are expected to result in lift and conviction being close to 1 while leverage is expected to be close to 0. As can be seen, this is the case only for product t-norm.Table 1
Comparison of lift, leverage, and conviction computed with differentt-norms on stochastically independent data generated randomly from uniform distribution.
Naive lift
Naive leverage
Naive conviction
Łukasiewiczt-norm
0.675
−0.081
1.544
Productt-norm
1.012
0.003
1.012
Minimumt-norm
1.353
0.088
0.755The values of naive lift and naive leverage wrongly indicate positive (resp., negative) relationship, if the minimum (resp., Łukasiewicz)t-norm is used. Paradoxically, naive conviction indicates opposite sign of relationship.


## 3. Expected Support of a Conjunction of Fuzzy Attributes under the Assumption of Independence

As indicated in Experiment1 presented in Section 2.3 above, naive lift, leverage, and conviction no more behave like their alternatives for crisp data: they no more represent a ratio of what is observed to what is expected under the assumption of independence. To recover their definitions, independency of fuzzy attributes must be treated correctly. Only then a proper definitions of lift, leverage, and conviction can be formulated.Given setsX and Y of fuzzy attributes, what support of X∧Y is expected if X and Y are independent? Moreover, what does independency of fuzzy attributes mean?For the sake of simplicity, let us assumeX and Y are sets containing a single fuzzy attribute; that is, |X|=|Y|=1. For more complex cases, a new attribute can be created from the set of fuzzy attributes by using (10).IfO is a set of randomly selected objects, one can consider membership values X(o) and Y(o) as random variables X and Y and treat the independence of fuzzy attributes as stochastic independence of random variables X and Y.Two random variablesX,Y are stochastically independent, if the combined random variable (X,Y) has a joint probability density as
(14)fX,Y(x,y)=fX(x)fY(y).
If X and Y are two independent random variables from interval [0,1], then
(15)σ(x,y):=x⊗yn
is a random variable with probability density function fσ(x,y)=fX,Y(x,y).By definition,expected valueE[Z] of a random variable Z is a weighted average of all possible values. More formally,
(16)E[Z]=∫-∞∞‍zfZ(z)dz,
where fZ is a probability density function of random variable Z.Similarly, an expected valueE[σ(x,y)] is a weighted average of all possible (x,y) pairs, namely,
(17)E[σ(x,y)]=∬01σ(x,y)fσ(x,y)dxdy.In real setting,fσ(x,y) is unknown but we can estimate its values from data (i.e., from objects O and their fuzzy attributes A) by using the assumption of independence (14) as follows:
(18)fσ(x,y)=fX(x)fY(y)≈countX(x)n·countY(y)n,
where countA(a) is the number of objects from O that belong to A∈A with degree a; that is, countA(a)=|{o∈O∣A(o)=a}|.Assumingx∈{X(o)∣o∈O} and y∈{Y(o)∣o∈O}, we obtain, from (15), (17), and (18),
(19)E[σ(x,y)]≈∬01(x⊗y)·countX(x)·countY(y)n3dxdy=∑i=1n‍∑j=1n‍X(oi)⊗Y(oj)n3.SinceX and Y are independent, E[fsupp(X⇀Y)]=n·E[σ(x,y)] and hence expected value of fsupp(X⇀Y) is
(20)E[fsupp(X⇀Y)]≈∑i=1n‍∑j=1n‍X(oi)⊗Y(oj)n2.Now, we are ready to define notions ofexpected support andexpected confidence.Definition 2.
Let⊗ be a t-norm, and let X,Y be sets of fuzzy attributes such that fsupp(X)>0 and n>0. Then, theexpected fuzzy supportfsupp⁡^(X⇀Y) and theexpected fuzzy confidencefconf^(X⇀Y) are defined as follows:
(21)fsupp⁡^(X⇀Y):=∑i=1n‍∑j=1n‍X(oi)⊗Y(oj)n2,fconf^(X⇀Y):=fsupp⁡^(X⇀Y)fsupp(X).Proposition 3.
LetX,Y be sets of fuzzy attributes. Then, (1)
iffsupp(X⇀Y)>0, then fsupp^(X⇀Y)>0,(2)
fsupp^(X⇀Y)≤min⁡⁡(fsupp(X),fsupp(Y)).Proof.
(1) Iffsupp(X⇀Y)>0, then
(22)∑i=1n‍X(oi)⊗Y(oi)>0
and hence
(23)∑i=1n‍∑j=1n‍X(oi)⊗Y(oj)>0.
Therefore also fsupp⁡^(X⇀Y)>0.
(2) For anyt-norm ⊗ holds that X(oi)⊗Y(oj)≤Y(oj). Therefore,
(24)∑i=1n‍∑j=1n‍X(oi)⊗Y(oj)n2≤∑i=1n‍∑j=1n‍Y(oj)n2=fsupp(Y)
and similarly for fsupp(X). Hence, fsupp⁡^(X⇀Y)≤min⁡(fsupp(X),fsupp(Y)).Remark 4.
Note that the reverse direction of the first implication of Proposition3 is not generally true. For example, for X:=(1,0) and Y:=(0,1), we have fsupp⁡^(X⇀Y)=1/4 but fsupp(X⇀Y)=0.Proposition 5.
LetX,Y be sets of fuzzy attributes and let ⊗:=⊗prod; that is, the product t-norm is being used as a conjunction. Then,
(25)fsupp^(X⇀Y)=fsupp(X)·fsupp(Y).Proof.
If⊗:=⊗prod, fsupp⁡^(X⇀Y) equals
(26)∑i=1n‍∑j=1n‍X(oi)·Y(oj)n2=1n2∑i=1n‍X(oi)∑i=1n‍Y(oi)=fsupp(X)·fsupp(Y).Proposition 6.
LetX,Y be sets of fuzzy attributes and let ⊗:=⊗min⁡; that is, the minimum t-norm is being used as a conjunction. Then,
(27)fsupp(X)·fsupp(X)≤fsupp^(X⇀Y)≤fsupp(X)⊗min⁡fsupp(Y).Proof.
Let⊗:=⊗min⁡⁡. The first inequality follows from the fact that ⊗min⁡⁡(x,y)≥x·y as
(28)fsupp⁡^(X⇀Y)=∑i=1n‍∑j=1n‍X(oi)⊗min⁡⁡Y(oj)n2≥∑i=1n‍∑j=1n‍X(oi)·Y(oj)n2=fsupp(X)·fsupp(Y).
The second inequality follows directly from Proposition 3.Proposition 7.
LetX,Y be sets of fuzzy attributes and let ⊗:=⊗Łuk; that is, the Łukasiewicz t-norm is being used as a conjunction. Then,
(29)fsupp(X)⊗Łukfsupp(Y)≤fsupp^(X⇀Y)≤fsupp(X)·fsupp(Y).Proof.
Let⊗:=⊗Łuk, sX:=fsupp(X), and sY:=fsupp(Y). To prove the first inequality, it suffices to prove
(30)fsupp⁡^(X⇀Y)≥max⁡⁡(0,sX+sY-1)
which is obvious for sX+sY≤1. Let us therefore assume sX+sY>1; then, (30) can be rewritten as
(31)∑i=1n‍∑j=1n‍X(oi)⊗ŁukY(oj)n2≥sX+sY-1.
Then,
(32)∑i=1n‍∑j=1n‍X(oi)⊗ŁukY(oj)=∑i=1n‍∑j=1n‍(X(oi)+Y(oj))-∑∀k‍(tk)-|r|,
where t is a sequence of numbers (X(oi)+Y(oj)∣X(oi)+Y(oj)<1) and r={(i,j)∣X(oi)+Y(oj)≥1}, for i,j∈{1,2,…,n}. Since |t|+|r|=n2 and each tk<1, we can immediately see that
(33)∑i=1n‍∑j=1n‍X(oi)⊗ŁukY(oj)≥∑i=1n‍∑j=1n‍(X(oi)+Y(oj))-n2=n2sX+n2sY-n2=n2(sX+sY-1);
hence, (30) holds.
The second inequality follows from⊗Łuk(x,y)≤x·y because then we have
(34)fsupp⁡^(X⇀Y)=∑i=1n‍∑j=1n‍X(oi)⊗ŁukY(oj)n2≤∑i=1n‍∑j=1n‍X(oi)·Y(oj)n2=sX·sY.


## 4. Correct Definition of Lift, Leverage, and Conviction for Fuzzy Association Rules

Now, we are ready to provide a correct definition of lift, leverage, and conviction in the framework of fuzzy association rules.Definition 8.
LetX,Y be sets of fuzzy attributes with n:=|O|>0. Then, lift, leverage, and conviction of a fuzzy association rule X⇀Y are defined as follows:
(35)flift(X⇀Y):=fsupp(X⇀Y)fsupp⁡^(X⇀Y);flever(X⇀Y):=fsupp(X⇀Y)-fsupp⁡^(X⇀Y);fconv(X⇀Y):=fsupp⁡^(X⇀¬Y)fsupp(X⇀¬Y).Let us now study some interesting properties of the newly defined notions.Proposition 9.
LetX,Y be sets of fuzzy attributes. Then, (1)
flift(X⇀Y)=flift(Y⇀X);(2)
flift(X⇀Y)=fconf(X⇀Y)/fconf^(X⇀Y);(3)
0≤flift(X⇀Y)≤n;(4)
iffsupp(X⇀Y)>0, then flift(X⇀Y)>0.Proof.
(1) and (2) directly follow from the definitions and from the fact thatt-norms are commutative.
(3) Since the membership degrees are defined on interval[0,1], their sums cannot be negative either. Hence, flift(X⇀Y)≥0. Next, assume to the contrary that flift(X⇀Y)>n as follows:
(36)flift(X⇀Y)=n∑i=1nX(oi)⊗Y(oi)∑i=1n∑j=1nX(oi)⊗Y(oj)>n;
therefore,
(37)∑i=1n‍X(oi)⊗Y(oi)>∑i=1n‍∑j=1n‍X(oi)⊗Y(oj),
which is a contradiction.
(4) Iffsupp(X⇀Y)>0, then, from Proposition 3, we know that also fsupp⁡^(X⇀Y)>0. Therefore, flift(X⇀Y) exists and is greater than 0.Proposition 10.
LetX,Y be sets of fuzzy attributes. Then, (1)
flever(X⇀Y)=flever(Y⇀X),(2)
flever(X⇀Y)=fsupp(X)(fconf(X⇀Y)-fconf^(X⇀Y)),(3)
1/n-1≤flever(X⇀Y)≤fsupp(X⇀Y)(1-1/n).Proof.
(1) and (2) directly follow from the definitions and from the fact thatt-norms are commutative.
(3) Letu:=∑∀iX(oi)⊗Y(oi) and r:=∑∀i∑∀j≠iX(oi)⊗Y(oj). Evidently, fsupp(X⇀Y)=u/n and fsupp⁡^(X⇀Y)=(u+r)/n2. Then, flever(X⇀Y)=u/n-(u+r)/n2. Obviously, 0≤u≤n and 0≤r≤n2-n. Therefore,
(38)-n2-nn2=1n-1≤flever(X⇀Y)≤un-un2=fsupp(X⇀Y)(1-1n).Proposition 11.
LetX,Y be sets of fuzzy attributes. Then, (1)
fconv(X⇀Y)=1/flift(X⇀¬Y);(2)
fconv(X⇀Y)=fconv(¬Y⇀¬X);(3)
fconv(X⇀Y)=fconf^(X⇀¬Y)/fconf(X⇀¬Y);(4)
1/n≤fconv(X⇀Y).Proof.
Everything directly follows from Definition8 and Proposition 9.Corollary 12.
LetX,Y be sets of fuzzy attributes and let ⊗:=⊗prod; that is, the product t-norm is being used as a conjunction. Then,
(39)flift(X⇀Y)=fsupp(X⇀Y)fsupp(X)·fsupp(Y)=fconf(X⇀Y)fsupp(Y);flever(X⇀Y)=fsupp(X⇀Y)-fsupp(X)·fsupp(Y);fconv(X⇀Y)=fsupp(X)·fsupp(¬Y)fsupp(X⇀¬Y)=1-fsupp(Y)1-fconf(X⇀Y).Proof.
Everything directly follows from Definitions2 and 8, from Proposition 5, and from the fact that fsupp(¬Y)=1-fsupp(Y).Corollary12 copies properties that are well known for crisp variants of lift, leverage, and conviction. In practice, the use of these equations is much more convenient than the original ones from Definition 8. However, note that Corollary 12 holds only if product t-norm ⊗prod is used. For other t-norms such as minimum ⊗min⁡⁡ or Łukasiewicz ⊗Łuk, Definition 8 must not be oversimplified that way. See the subsequent corollaries for more details.Corollary 13.
LetX,Y be sets of fuzzy attributes and let ⊗:=⊗min⁡; that is, the minimum t-norm is being used as a conjunction. Then,
(40)sXYsX⊗min⁡sY≤flift(X⇀Y)≤sXYsX·sY,sXY-sX⊗min⁡sY≤flever(X⇀Y)≤sXY-sX·sY,sX·sY-sXY-≤fconv(X⇀Y)≤sX⊗min⁡sY-sXY-,wheresX:=fsupp(X),sY:=fsupp(Y),sY-:=fsupp(¬Y),sXY:=fsupp(X⇀Y), and sXY-:=fsupp(X¬Y).Proof.
Everything directly follows from Definitions2 and 8 and from Propositions 6 and 11.Corollary 14.
LetX,Y be sets of fuzzy attributes and let ⊗:=⊗Łuk; that is, the Łukasiewicz t-norm is being used as a conjunction. Then,
(41)sXYsX·sY≤flift(X⇀Y)≤sXYsX⊗ŁuksY;sXY-sX·sY≤flever(X⇀Y)≤sXY-sX⊗ŁuksY;sX⊗ŁuksY-sXY-≤fconv(X⇀Y)≤sX·sY-sXY-,
where sX:=fsupp(X),sY:=fsupp(Y),sY-:=fsupp(¬Y),sXY:=fsupp(X⇀Y), and sXY-:=fsupp(X⇀¬Y).Proof.
Everything directly follows from Definitions2 and 8 and from Propositions 7 and 11.Experiment 2.
The same data as in Experiment1 were processed accordingly to correct definitions of lift, leverage, and conviction (see Definition 8). The results can be found in Table 2. Since the data are randomly generated from uniform distribution, they are stochastically independent; hence, lift and conviction should be close to 1 and lift should be close to 0 regardless of t-norm being used. As one can see, the results in Table 2 are perfectly in compliance with our expectations.Table 2
Comparison of lift, leverage, and conviction computed with differentt-norms on stochastically independent data generated randomly from uniform distribution.
Naive lift
Naive leverage
Naive conviction
Łukasiewiczt-norm
1.022
0.004
1.021
Productt-norm
1.012
0.003
1.012
Minimumt-norm
1.010
0.003
1.011


## 5. Conclusion

Lift is a ratio of observed support (resp., confidence) to the support (resp., confidence) that is expected under the assumption of independence. Leverage is similar to lift, since it is a difference between observed and expected support. Conviction is often treated as an alternative to confidence; nevertheless, it is defined on the basis of observed and expected support too.In this paper, a correct definition of lift, leverage, and conviction for fuzzy data was provided. It should be stressed here that there already exist some research papers that use incorrect (a.k.a. “naive”) definition of fuzzy lift (e.g., [18]) that is also discussed here.The naive definition does not preserve interpretation of positive/negative relationship. For crisp lift and conviction (resp., leverage), the stochastically independent attributesX and Y yield lift(X⇀Y)≈1, conv(X⇀Y)≈1, and lever(X⇀Y)≈0. As shown in Experiment 1, this is no more the case for naive definitions of these measures. On the other hand, Experiment 2 shows that correct definitions of lift, leverage, and conviction again recover that feature for fuzzy data.All the lift, leverage, and conviction definitions are similar to their “crisp” alternatives (i.e., definitions for binary data) if thet-norm being used is the product ⊗prod. For Łukasiewicz ⊗Łuk and minimum ⊗min⁡⁡  t-norms, a more complicated computation takes place.In [20], an algorithm was developed in for fast evaluation of fuzzy lift. A future research will therefore address improvements of association rules search algorithms by introducing fast computations of other measures, adding pruning heuristics based on boundary conditions provided by Corollaries 13 and 14. Also, other interest measures may be studied and their applicability to fuzzy rules may be considered.



---

*Source: 197876-2014-10-07.xml*