Theory of dependence values.
A new model to evaluate dependencies in data mining problems is presented and discussed. The well-known concept of the association rule is replaced by the new definition of dependence value, which is a single real number uniquely associated with a given itemset. Knowledge of dependence values is sufficient to describe all the dependencies characterizing a given data mining problem. The dependence value of an itemset is the difference between the occurrence probability of the itemset and a corresponding maximum independence estimate. This can be determined as a function of joint probabilities of the subsets of the itemset being considered by maximizing a suitable entropy function. So it is possible to separate in an itemset of cardinaltiy k the dependence inherited    from its subsets of cardinality (k  1) and the specific inherent dependence of that itemset. The absolute value of the difference between the probability p(i) of the event i that indicates the prescence of the itemset {a,b,... } and its maximum independence estimate is constant for any combination of values of Q  &angl0; a,b,...  &angr0; Q. In1p addition, the Boolean function specifying the combination of values for which the dependence is positive is a parity function. So the determination of such combinations is immediate. The model appears to be simple and powerful.
INTRODUCTION
A well known problem in data mining is the search for association rules, a powerful
and intuitive conceptual tool to represent the phenomena that are recurrent in a
data set. A number of interesting solutions of that problem has been proposed in
the last five years together with as many powerful algorithms [Agrawal et al. 1993b;
Agrawal et al. 1995; Agrawal and Srikant 1994; A.Savasere et al. 1995; Han and
Fu 1995; Park et al. 1995; H.Toivonen 1996; Brin et al. 1997; I.Lin and M.Kedem
1998]. They are used in many application fields, such as analysis of basket data of
supermarkets, failures in telecommunication networks, medical test results, lexical
features of texts, and so on.
An association rule is an expression of the form X ) Y, where X and Y are
sets of items which are often found together in a given collection of data. For
example, the expression f milk, coffee g ) f bread, sugar g might mean that
a customer purchasing milk and coffee is likely to also purchase bread and sugar.
The validity of an association rule has been based on two measures. The first
measure, called support, is the percentage of transactions of the database containing
both X and Y. The second one, called confidence, is the probability that, if X is
purchased, also Y is purchased. In the case of the previous example, a value of
2% of support and a value of 15% of confidence would mean that 2% of all the
customers buy milk, coffee, bread and sugar, and that 15% of the customers that
buy milk and coffee also buy bread and sugar.
Recently, Silverstein, Brin and Motwani [Silverstein et al. 1998] have presented
a critique of the concept of association rule and the related framework support-
confidence. They have observed that the association rule model is well-suited to the
market basket problem, but that it does not address other data mining problems. In
place of association rules and the support-confidence framework, Silverstein, Brin
and Motwani propose a statistical approach based on the chi-squared measure and
a new model of rules, called dependence rules.
This work can be viewed as a continuation of the line of the rules, even if the
model and the tools here proposed are rather different and in particular the concept
of dependence rules has been replaced by the concept of dependence values.
This paper is organized as follows. Section 2 contains a summary of the main
results of earlier work, the emphasis being placed on the framework support-
confidence, the critique of this model by Silverstein, Brin and Motwani and the
concept of dependence rules in opposition to the one of association rules. Section 3
contains the definition of dependence value and other basic definitions of the model
here proposed as well as the theorems following from these definitions. These theorems
suggest an easy and quick way to determine the dependence values, which
is described in Section 5, whereas Section 4 discusses the use of the well known
concept of entropy as a tool to evaluate the relevance of a dependence rule. Finally,
Section 6 draws the conclusions.
2. ASSOCIATION RULES AND DEPENDENCE RULES
As mentioned, this Section contains a summary of earlier work on association rules.
For ease of reference, the notation used by Silverstein, Brin and Motwani in their
paper will be adopted here.
Theory of Dependence Values \Delta 3
2.1 Association Rules
be a set of k elements, called items. Basket of items is any
subset of I. For example, in the market basket application, I =fmilk, coffee,
bread, sugar, tea, . g contains all the items stocked by a supermarket and a
basket of items such as f milk, coffee, bread, sugarg is the set of purchases from
one register transaction. As a second example, in the document basket application,
I is the set of all the dictionary words and each basket is the set of all the words
used in a given document.
An association rule X ) Y, where X and Y are disjoint subsets of I, was defined
by Agrawal, Imielinski and Swami [Agrawal et al. 1993b] as follows.
is a subset of at least s% (the support) of all
the baskets, and of all the baskets containing all the items of X at least c% (the
confidence) contain all the items of Y.
The concept of association rules and the related support-confidence framework
are very powerful and useful, but they suffer from some limitation, especially when
the absence of items is considered. An interesting example proposed by Silverstein,
Brin and Motwani is the following.
Consider the purchase of tea (t) and coffee (c) in a grocery store and assume the
following probabilities:
where c and t denote the events "coffee not purchased" and "tea not pur-
chased", respectively.
According to the preceding definitions, the potential rule tea ) coffee has a
support equal to 20% and a confidence equal to 80%, and therefore can be considered
as a valid association rule. However, a deeper analysis shows that a customer
buying tea is less likely to also buy coffee than a customer not buying tea (80%
against more than 90%). We would write tea ) coffee, but, on the contrary, the
strongest positive dependence is between the absence of coffee and the presence of
tea.
2.2 Dependence Rules
Silverstein, Brin and Motwani propose a view of basket data in terms of boolean
indicator variables, as follows.
be a set of k boolean variables called attributes. A set of baskets
bng is a collection of the n k-tuples from fTRUE, FALSEg k which
represent a collection of value assignments to the k attributes. Assigning the value
TRUE to an attribute variable I j in a basket represents the presence of item i j in
the basket.
The event a denotes A=TRUE, or equivalently, the presence of the corresponding
item a in a basket. The complementary event a denotes A=FALSE, or, the absence
of item a from a basket.
The probability that item a appears in a random basket will be denoted by
P(a)=P(A=TRUE). Likewise, will be the probability
that item a is present and item b is absent.
Silverstein, Brin and Motwani have proposed the following definitions of independence
and dependence of events and variables.
Definition 1. Two events x and y are independent if P(x "
Definition 2. Two variables A and B are independent if
for all possible values hv a , v b 2 fTRUE, FALSEgi.
Definition 3. Events, or variables, that are not independent are dependent.
Definition 4. Let I be a set of attribute variables. We say that the set I is a
dependence rule if I is dependent.
The following Theorem 1 is based on the preceding Definitions 1-4.
Theorem 1. If a set of variables I is dependent, so is every superset of I.
Theorem 1 is important in the dependence rule model, because it makes it possible
to restrict the attention to the set of minimally dependent itemsets, where a
minimally dependent itemset I is such if it is dependent, but none of its subsets is
dependent.
Silverstein, Brin and Motwani have proposed using the X 2 test for independence
to identify dependence rules. X 2 statistic is upward-closed with respect to the
lattice of all possible itemsets, as well as dependence rules. In other terms, if a set
I of items is deemed dependent at significance level ff, then all supersets of I are
also dependent at the same significance level ff and, therefore, they do not need to
be examined for dependence or independence.
3. DEPENDENCE VALUES
In this Section the new model based on the concept of dependence values is presented
and discussed. A Theorem proved in this section will provide the basic tools
to evaluate the dependence rules of a certain itemset. To simplify the presentation,
we shall procede from the most simple cases towards the most complex ones, in
the order of increasing cardinality of itemsets. In other terms, we shall discuss
dependence rules first for pairs of items, then for triplets of items, and finally for
m-plets of arbitrary cardinality m.
3.1 Dependence Rules for Pairs of Items
Assume we know the occurrence probabilities of all the items:
The evaluation of such probabilities is the first problem of data mining, but it is
seldom considered because of its simplicity. Generally, the maximum likelihood
estimate is adopted according which P(a) is assumed equal to O(a)/n, where O(a)
Theory of Dependence Values \Delta 5
is the number of baskets containing a and n is the total number of baskets. However,
more complex computations based on Bayes's Theorem, might also be used.
In the absence of specific determinations, if we know only
formulate the following conjectures:
These conjectures are equivalent to the assumption that variables A and B are
independent.
Assume that the exact determination of P(a,b), evaluated as O(a,b)/n (where
O(a,b) is the number of baskets containing both a and b), is different from the
conjecture
It is easy to prove the following Theorem.
Theorem 2 (Unicity of the value for second-order probabilities). If
P(A=TRUE) and P(B=TRUE) are known, determination of a single value
is sufficient to evaluate all the second-order joint probabilities P(a; b); P(a; b); P(a; b).
Proof. The proof is contained in the following simple relationships:
Analogously,
and
The fact that a single datum \Delta contains the whole information pertaining joint
probabilities of pair fA, Bg suggests the following Definitions.
Definition 5. (Dependence value of a pair) The dependence value of the pair
fA,Bg will be defined as the difference
Definition 6. (Dependence state of a pair) If the absolute value of
exceeds a given threshold th, A and B are said "dependent". If \Delta ? th dependence is
defined as "positive"; otherwise, it is defined as "negative". The following notations
will be adopted to indicate a positive dependence, a negative one or no dependence,
respectively.

Figure

1 shows that the difference between the joint probability P(a
(with
a
a or a
a and b
b) and the corresponding "a-priori" estimate
P(a
has always the same absolute value but a different sign in the various
cells of the Karnaugh's map of variables A and B. To represent this fact, we need
another definition and a new Theorem.
A
A
Fig. 1. The joint probabilities of P(a,b) in the cells of Karnaugh's map of fA,Bg.
Definition 7. (Dependence function of two variables) The boolean function of
variables A and B, whose minterms correspond to the values hv A ,v B
i for which
P(A=v A
will be called the dependence function of variables
A and B.
Theory of Dependence Values \Delta 7
Theorem 3 (Parity of two variables dependence functions). If
the dependence function of variables A and B is:
which is the parity function with parity odd (Figure 2).
If D 2
the dependence function of variables A and B is:
which is the parity function with parity even (Figure 3).
Fig. 2. The dependence function of variables A and B if D 2 (A,B)AE 0.
Fig. 3. The dependence function of variables A and B if D 2 (A,B) 0.
As a simple example, consider the case of purchases of coffee (c) and tea (t),
which was discussed in [Silverstein et al. 1998] to show the weakness of the traditional
support-confidence framework (Subsection 2.1). If
P(c,t)=0.2
then
Therefore P(c)\DeltaP(t)=0.225 and which shows
that dependence is negative (D 2 (C,T) 0).
One might wonder whether the usual notation X adopted in the well known
papers on data mining does make still sense and how to indicate a negative dependence
like The answer is
simple:
simply, D 2 (c; t)  0 contain all information on the
second-order dependencies. However, one might argue that \Delta is more significant
for the events having a lower probability. In the case of coffee and tea,
is the lowest probability in the cells of the dependence function; therefore, it
is not completely unreasonable to write: C ) T.
3.2 Dependence Rules for Triplets of Items
This Subsection is devoted to the generalization of Definitions and Theorems presented
in previous Subsection 3.1 to the case of triplets of items. As we shall see,
such generalization implies some new problems.
Consider the case of a triplet of the boolean variables A, B and C, and assume we
know the first- and second-order joint probabilities such as
and others.
We are interested in determining the third-order joint probabilities of triplets
such as P(a,b,c), P(a,b,c), and so on, from which also the third-order conditional
probabilities such as directly.
The following Theorem shows that the knowledge of a single third-order probability
is sufficient to determine all the third-order probabilities.
Theorem 4 (Unicity of the value for third-order probabilities). All
the third-order joint probabilities can be calculated as functions of first- and second-order
joint probabilities and a single datum such as a third-order joint probability.
Proof. Assume, for example, we know P(a,b,c). The other joint probabilities
can be determined as follows:
Theorem 4 may be viewed as an extension of Theorem 2 on the unicity of the
value for second-order probabilities shown in previous Subsection 3.1. However,
Theorem 2 makes reference to the differences between the determined P(a
and the estimated P(a
which correspond to the conjecture of independence
of a and b. In the case of triplets, the condition of independence is more difficult
to be identified. Our proposal is contained in the following considerations.
The relationships written in the proof of Theorem 4 can also be formulated in
the following form:
Theory of Dependence Values \Delta 9
They express the values of all the third-order joint probabilities as functions of the
known second-order probabilities P(a,b), and the unknown third-order
probability
Now consider the entropy
This function of the unknown x is the average amount of information needed to
know a, b and c. The maximum value of E(x) is reached when a, b and c are
at the maximum level of independency compatible with the dependencies imposed
by the second-order joint probabilities. This consideration explains the following
Definition 8.
Definition 8. (Maximum independence estimate for third-order probabilities) If
first- and second-order joint probabilities are known but no information is available
on the third-order probabilities, the conjecture x of P(a,b,c) maximizing the joint
entropy of A, B, C:
P(a; b; c) \Delta log P(a; b; c)
(where the sum is to be extended to all the combinations of values of a, b and c)
will be defined as the maximum independence estimate. Such maximum independence
estimate will be denoted with the symbol P(a,b,c)MI .
Analogously, for any combination x
i of values of a, b, c, we shall
define P(a
)MI as the value of P(a
) for which E(x   ) is maximum.
Notice that in virtue of Theorem 4, for any combination of values ha   ,b   ,c   i of a,
b, c, P(a   ,b   ,c   )MI can be computed in terms of second-order joint probabilities
and P(a,b,c)MI by applying the following relationships
The meaning of Definition 8 is rather important for the model presented in this
paper. If D 2 (A,B) or D 2 (A,C) or D 2 (B,C) are AE 0 or  0, A, B, C are not in-
dependent, but they could own only the dependence inherited from the second-order
dependencies or their dependence might be stronger. In the former case,
P(a   ,b   ,c   ) is equal to P(a   ,b   ,c   )MI and there is no real third-order depen-
dence. In the latter, there is an evidence of a third-order dependence whose value
and sign depend on the differences between P(a   ,b   ,c   ) and P(a   ,b   ,c   )MI , as
shown in the following analysis.
Notice that in the case of the pairs of items the Definition 8 of maximum independence
coincides with the more known definitions of independence cited in previous
Subsection 3.1. Indeed, in this case, as is shown in Figure 1, the joint entropy of A
and B is
where x=P(a,b). It is easy to prove that function E has a maximum for
By applying the same algorithm, it is easy to prove the analogous results:
Unfortunately, in the case of triplets and k-plets the determination of the maximum
independence estimates is not so simple. However, as will be seen later, it
is not necessary to know all the estimates P(i 1
but one of them
is sufficient to determinate all the other ones. Besides, the numerical evaluation of
this estimate can be performed very quickly by applying the method which will be
described in Section 5.
The definition of maximum independence estimate is applied in the following
Theorem, which can be viewed as a specification of Theorem 4 on the unicity of
value for third-order probabilities and as the natural extension of the Theorem 2
proved in previous Subsection 3.1.
Theorem 5. If the first- and second-order joint probabilities and the third-order
maximum independence estimate are known, a single number \Delta defined as the difference
P(a,b,c) - P(a,b,c)MI is sufficient to specify all the third-order joint
probabilities.
Proof. Theorem 5 is a direct consequence of Theorem 4 on the unicity of the
value. Indeed, from the knowledge of the first- and second-order joint probabilities
we can obtain P(a,b,c)MI and from this
according to Theorem 4, the knowledge of P(a,b,c) is sufficient to determine all
the third-order joint probabilities.
Theory of Dependence Values \Delta 11
In virtue of Theorem 5, we can state the following Definitions which are an
extension of Definitions 5 and 6.
Definition 9. (Dependence value of a triplet) The dependence value of the triplet
fA,B,Cg will be defined as the difference
Definition 10. (Dependence state of a triplet) If the dependence value of fA,B,Cg
exceeds a given threshold th, A, B and C are defined
as "connected by a third-order dependence". If \Delta ? th, dependence is defined as
otherwise, it is defined as "negative".
The following notations
will be used to indicate the existence or not of a third-order dependence and its
sign.
Notice that in the model proposed by Silverstein, Brin and Motwani, the existence
of one or more second-order dependencies implies the existence of the third-order
dependence, whereas in our model D 2 (A,B), D 2 (A,C), D 2 (B,C) and D 3 (A,B,C) are
independent, in the sense that any combination of their values is possible. For
example, even if all the three second-order dependencies are positive, D 3 (A,B,C)
might be zero or negative. In Subsection 3.3 an example about the purchase of a
triplet of items is discussed and the differences with respect to the other models
are discussed.
The following Definition 11 on the dependence function of three variables and
Theorem 6 extend the statements of Definition 7 on the dependence function for
pairs and Theorem 3 on the parity function to third-order dependencies.
Definition 11. (Dependence function of three variables) The boolean function of
variables A, B and C, whose minterms correspond to the values hv A ,v B ,v C
i for which
P(A=v A
"C=v C )MI will be called the dependence function
of variables A, B and C.
Theorem 6 (Parity of three variables dependence functions). If
the dependence function of variables A, B and C is
that is the parity function with parity even (Figure 4). If D 3 (A,B,C)  0, the
dependence function is
that is the parity function with parity odd and the complementary function of the
preceding one (Figure 5).
Proof. By definition
Fig. 4. The dependence function when D 3 (A,B,C) AE 0.
Fig. 5. The dependence function when D 3 (A,B,C)  0.
From analogous computations the values presented in Figure 6 follow. From these
ones, it is immediate to derive the two maps of Figure 4 and 5, when D 3
or D 3
A P(a,b,c)MI P(a,b,c)MI P(a,b,c)MI P(a,b,c)MI
A P(a,b,c)MI P(a,b,c)MI P(a,b,c)MI P(a,b,c)MI
Fig. 6. The dependence function for the three variables A, B and C.
3.2.1 Justification of the maximum independence definition. The idea of maximum
independence introduced in this paper is not intuitively obvious and needs
some further justification.
First consider the simple case of two variables A and B. In this case, as shown
above, the definition of maximum independence coincides with the well known
definition of absolute independence, according which A and B are independent if,
and only if, P(A=v A ,B=v B any combination of values of A
and B.
It is well known that the joint entropy of A and B E(A,B)=E(A)+E(BjA)=
E(B)+E(AjB) where E(BjA) and E(AjB) are the equivocation of B with respect
to A and the equivocation of A with respect to B, respectively. Therefore, the maximum
value of E(A,B) is reached when E(BjA) (or E(AjB)) is maximum. When A
and B are independent, the amount of information needed to know B, if A is known,
Theory of Dependence Values \Delta 13
or to know A, if B is known, is maximum. Notice that in this case E(AjB)=E(A)
and E(BjA)=E(B). These equalities will not hold in the case of three variables.
Now consider the case of three variables A, B and C. In general, if the probabilities
of A, B and C, and the second-order joint probabilities P(A,B), P(B,C) and P(A,C)
have been assigned, there is no assignment of the probability P(A,B,C) for which A,
and C are independent, that is, P(A=v A ,B=v B ,C=v C
for any combination of values of v A
and v C
However, it makes sense to search the value of P(A,B,C) for which the joint
entropy E(A,B,C) is maximum and to define that condition as the one of the
maximum level of independence compatible with the dependencies imposed by the
second-order joint probabilities. Indeed,
Therefore, since E(A,B), E(A,C) and E(B,C) depend only on the values of
second-order probabilities, E(A,B,C) reaches its maximum for that assignment of
P(A,B,C) for which also E(CjA,B), E(BjA,C) and E(AjB,C) reach their maximum
values. In other terms, the maximum independency level corresponds to the condition
in which the maximumamount of information is needed to know the value of a
variable, the other two being known. However, in general, since A, B and C are not
independent,
and this is different from the case of pairs of variables for which the concepts of
maximum independence and absolute independence coincide.
3.3 The lattice of dependencies
Since the knowledge of the dependence value of an itemset of cardinality k, together
with the values of the joint probabilities of all its subsets of cardinality k-1,
is sufficient to know the probabilites of all the combinations of its values, the lattice
of the itemsets can be adopted to describe the whole system of dependencies of a
given database. Of course, in such a lattice every node should be labelled with its
associated dependence value. Besides, the nodes at the top of the lattice representing
the itemsets of cardinality 1 will be labelled with the values of the differences
between the probability estimates, P(a)=O(a)/n, so on, and
the corresponding starting estimates (typically, and in absence of other estimates,
equal to 0.5).
By way of example, Figure 7 represents the dependence lattice relative to the
sample reported by Silverstein, Brin and Motwani in their paper.
The following are the data of purchases of coffee (c), tea (t), and doughnuts (d)
and their combinations proposed by those authors:
c t d
ct cd td
ctd
Fig. 7. The lattice relative to the purchases of coffee (c), tea (t) and doughnuts (d).
P(c,t,d)=0.4
The dependence values of the nodes of the lattice have been calculated as follows.
\Delta(c)=P(c)-P(c) MI=O(c)/n-0.5=0.93-0.5=+0.43
\Delta(t)=P(t)-P(t) MI=O(t)/n-0.5=0.21-0.5=-0.29
\Delta(d)=P(d)-P(d) MI=O(d)/n-0.5=0.51-0.5=+0.01
\Delta(c,t)=P(c,t)-P(c,t) MI=O(c,t)/n-P(c)\DeltaP(t)=0.18-0.19=-0.01
\Delta(c,d)=P(c,d)-P(c,d) MI=O(c,d)/n-P(c)\DeltaP(d)=0.48-0.47=+0.01
\Delta(t,d)=P(t,d)-P(t,d) MI=O(t,d)/n-P(t)\DeltaP(d)=0.09-0.1=-0.01
\Delta(c,t,d)=P(c,t,d)-P(c,t,d) MI=O(c,t,d)/n-0.078=0.08-0.078=+0.002
P(c,t,d)MI has been computed maximizing the entropy E(x) with x=P(c,t,d)
as suggested in Definition 8 on the maximum independence estimate.
Notice that from the value of \Delta(c,t,d) and from Definition 10 on the state of
dependencies it follows, for example, that the dependence of itemset fc,t,dg is
positive, whereas, by adopting the model proposed by Silverstein, Brin and Mot-
wani, the same dependence, evaluated as P(a;b;c)
P(a)\DeltaP(b)\DeltaP(c)
would be negative. This is due
to the fact that in the model by Silverstein, Brin and Motwani, the dependencies
which the subset fc,t,dg has inherited by the subsets fc,tg, fc,dg and ft,dg are
not distinguished from the specific inherent dependence. The complete dependence
table showing the sign of dependence function for all the values of hc,t,di is shown
in

Figure

8.
The dependence lattice can also be viewed as an useful tool to display the results
of a data mining investigation on a given database. Of course, it will be convenient
Theory of Dependence Values \Delta 15
TD TD TD TD
Fig. 8. The sign of dependence function for the example of the purchases of coffee (variable C),
tea (variable T) and doughnuts (variable D).
to display only the sub-lattice of the nodes having sufficient support and positive
or negative dependencies - anyway different from zero in a significant way. Often,
the dependence value is not necessary, it being sufficient to introduce the indication
of the dependence state in the lattice produced.
3.4 Dependence Rules for k-plets of Items of Arbitrary Cardinality
The case of triplets discussed in previous Subsection 3.2 is absolutely general. How-
ever, for the sake of completeness, the Definitions and the Theorems presented in
Subsection 3.2 will be extended in this Subsection to the more general case of k-
plets of arbitrary cardinality. For the sake of brevity, the proofs of the Theorems
will be omitted, with the exception of Theorem 7 which needs a specific proof.
Consider the case of a k-plet of boolean variables I 1 , I assume we
know all the joint probabilities up to the order (k-1):
We want to determine the k-th-order joint probabilities like P(i 1
on. The following Theorem shows that the knowledge
of a single k-th-order joint probability is sufficient to determine all the k-th-order
probabilities.
Theorem 7 (Unicity of the value). All the k-th-order joint probabilities can
be calculated as functions of the joint probabilities of the orders less than k and a
single k-th-order joint probability.
Proof. Assume, for example, we know P(i 1 ,
First, we determine
Analogously, we determine all the other joint probabilities related to elementary
conditions in which a single literal is complemented:
and so on.
Then, we compute all the joint probabilities referring to elementary conditions
in which two literals appear complemented:
and so on.
In general, in order to determine all the joint probabilities related to elementary
conditions containing m complemented literals, we apply the following relationship
in which a 1 6= a
P(i a 1
,i a 2
P(i a 1
,i a 3
,i a2 ,i a 3
where at most (m-1) complemented literals appear in the right size.
Definition 12. (Maximum independence estimate) If the joint probabilities up to
order k-1 are known but no information is available on the joint probabilities of
order k, then the conjecture on P(i



maximizing the joint entropy
of I 1 ,I


will be considered as the maximum independence estimate. For any fi
the maximum independence estimate will be indicated with the symbol

Definition 13. (Dependence value) The difference
will be defined as the dependence value of the itemset fi 1 , g.
Theorem 8 (Unicity of the value). If the joint probabilities up to the order
are known, the knowledge of the dependence value P(i 1 ,
is sufficient to describe all the k-th order joint probabilities.
Definition 14. (Dependence state) If the absolute value of the dependence value
exceeds a given threshold th, I 1 , I 2 ,: : :, I k are defined as
connected by a dependence of order k. If \Delta ? th, the dependence is defined as
positive; otherwise, it is defined as negative.
The following notations:
will be used to indicate the existence or not of a dependence of order k and its sign.
Definition 15. (Dependence function) The boolean function of variables I 1 , I
I k , whose minterms correspond to the values hv
I will be called
the dependence function of variables I 1 , I
Theorem 9 (Parity of dependence functions). If D k
0, the dependence function of variables I 1 , I , that is
the parity function with even parity.
Theory of Dependence Values \Delta 17
the dependence function of variables I 1 , I
I 1
, that is the parity function with odd parity.
In both cases, and for all the values of I 1 , I I k the difference P(i 1 ,
has an absolute value equal to \Delta.
4. ENTROPY AND DEPENDENCIES
A less intuitive but for some aspects more effective approach to determine dependencies
can be based on the concept of entropy. In this Section only a summary of
a possible entropy based theory of dependencies is presented, the task being left to
the reader of developing such a theory following the scheme of Section 3.
First consider the case of the pairs of items. Assume P(a), P(a), P(b), P(b)
are known. The entropy of A
is the measure of the average information content of the events a j A=TRUE and
a j A=FALSE. An analogous meaning can be attributed to
Consider now the mutual information
a   ;b   P(a   , b   )\Delta logP(b   ja   ).
is a measure of the average information content carried by b
on the value of A,
and viceversa, and therefore, it can be assumed as an indication of independence
of A and B. Unfortunately, mutual information I(A;B) is always positive; so it is
necessary to verify whether P(a,b) ? P(a)\DeltaP(b) or not, in order to determine the
sign of dependence. Therefore, we propose the following definition:
Definition 16. (Entropy based second-order dependence) If I(A;B) exceeds a given
threshold, we shall state that D 2 (A,B) AE 0 or D 2 (A,B)  0 according to whether
not. If I(A;B) does not exceed that threshold, we shall
state that D 2 (A,B)  0.
The extension of such definition to triplets is not immediate, since the ternary
mutual information I(A;B;C) defined in information theory does not own the meaning
we need now. Therefore we suggest the following one:
Definition 17. (Entropy based third-order dependence) If both E(AjB) - E(AjB,C)
and E(AjC) - E(AjB,C) exceed a given threshold, we state that D 3 (A,B,C) AE 0
when P(a,b,c) is larger than all the following estimates:
P(a)\DeltaP(b,c)
P(b)\DeltaP(a,c)
or D 3 (A,B,C)  0 when P(a,b,c) is less than all the three preceding estimates;
otherwise, D 3 (A,B,C)  0.
Definition 17 might seem asymmetric with respect to variables A, B and C. In
order to understand the reasons for which the relationships written in Definition 17
are symmetric, remember that, for example, if E(AjB)-E(AjB,C)?th then also
E(CjB)-E(CjA,B)?th. Besides, E(AjB,C) != E(AjB) and E(AjB,C) != E(AjC).
When, for example, E(AjB,C), E(AjB,C) is maximum and, therefore,
(maximum independence condi-
tion). It follows that also E(BjA,C) and E(CjA,B) take their maximumvalues, equal
to E(BjA) or E(BjC) and to E(CjA) or E(CjB).
An analogous definition can be introduced to evaluate dependencies in k-plets
with arbitrary k.
Definition 18. (Entropy based general dependence) Let E k
MIN
the minimum of all
the conditional entropies
are the subsets of (k-2) variables of the set
of (k-1) variables.
MIN
exceeds a given threshold,
larger than the maximum of the estimates
we state that D k (A, B,
If the same difference E k
MIN
exceeds the given threshold and
smaller than the minimum of the estimates
we state that D k (A,B,C,: : :,Z)  0.
If none of the two above specified conditions holds, we state that D k (A,B,C,: : :,Z)
Theory of Dependence Values \Delta 19
Notice that the computation of entropies can be simplified by applying the following
Theorem.
Theorem 10. If the entropies of order k-1 are known, a single entropy needs
to be determined in order to calculate all the entropies of order k.
Proof. Assume we know E(I 1 j I 2 , I 3 First we determine E(I 2 j
I 1 , I 3 observing that:
where only the last entropy is unknown. A similar method can be applied to
determine all the others conditional entropies of the type
E(I j
I j+1
(with 2  j  k).
Finally, any other entropy can be easily calculated in terms of the already calculated
ones. For example:
E(I 1
I 4
I 4
5. THE DETERMINATION OF THE DEPENDENCE VALUES
The analysis developed in this paper refers essentially to the concept of confidence
and does not concern the principles of support. Almost all the algorithms so far
proposed for data mining are based on a first step aimed at determining the k-plets
having a sufficient support, namely, a sufficient statistical relevance. Such solutions
are compatible with the following algorithm for determining all the relevant
dependencies up to a certain order.
(1) Determination of the k-plets having a sufficient support.
Most algorithms for determining the k-plets having a sufficient support proceed
in the order of increasing cardinalities. In other terms, they first determine the
single items, then the pairs of items, the triplets, and so on. Such algorithms
are well suited to the following procedure. Other algorithms should be modified
in order to examine a k-plet P after the (k-1)-plets contained in P.
The program which has been specifically developed to verify the ideas described
in this paper is based on an algorithm for the determination of the k-plets (also
called itemsets) having sufficient support [Meo 1999] which has been chosen in
virtue of its speed, but which produces the list of itemsets organized in a family
of trees. However, this data structure, as any other, can be transformed into a
lattice suitable to the above described computations in a relatively short time.
Notice that it is not necessary that the complete lattice of all the itemsets
having sufficient support is represented in the main memory at the same time.
What is really needed is that at the starting point every node of the structure,
that is every analyzed itemset, is represented by two sets of data:
a) the values of the joint probabilities describing that itemset;
b) the pointers to its parents.
For the sake of simplicity, the program here described is characterized, as concerns
preceding point a), by the choice of describing an itemset with a single
datum, as is possible in virtue of Theorem 7 on the unicity of the value. The
chosen datum is the number of occurrences n ab:::z of that itemset, which is proportional
to its probability P(a,b,: : :,z) (see Figure 9 where ptr x denotes
the pointer to itemset x).
abc
abc
ptr ab
ptr ac
ptr bc
bc
ptr c
bc
ac
ptr a
ptr c
ac
ab
ptr a
ab
a
a
c
c
Fig. 9. The data structure of the itemsets.
This choice makes it possible to store millions of itemsets in the main memory
at the same time and to perform all the following computations without storing
any partial results in the mass memory.
(2) Determination of all the joint probabilities of an itemset.
The computation of the joint probabilities P(i
k ) for all the combinations
of values of i
k can be performed recursively applying the
relationships presented in the proof of Theorem 7 on the unicity of the value.
Of course, recursion proceeds towards the parents and the grandparents. For
example, in the case of Figure 9,
where only the probabilities directly connected to the numbers of occurrences
introduced in Figure 9 appear.
Theory of Dependence Values \Delta 21
(3) Determination of maximum independence estimates.
The determination of the value x for which the joint entropy


takes its maximum value can be performed numerically, at the desired level of
accuracy, with conventional interpolation techniques.
(4) Computation of the dependence value and states.
A direct application of Definitions 13 and 14 leads to the final results.
5.1 Experimental Evaluation
The proposed approach has been verified with an implementation in C++ using
the Standard Template Library. The program has been run on a PC Pentium II,
with a 233 Mhz clock, 128 MB RAM and running Red Hat Linux as the operating
system. We have worked on a class of databases that has been taken as benchmark
by most of data mining algorithms on association rules. It is the class of synthetic
databases that project Quest of IBM has generated for its experiments (see [Agrawal
and Srikant 1994] for detailed explanations).
We have made many experiments on several databases with different values of
the main parameters and of the minimum support, but the obtained results are
all similar to the ones here proposed. In particular, the experiments have been
run with the value of minimum support equal to 0.2% and with a precision in the
computation of the dependence values equal to 10 \Gamma6 .
In the generation of the databases we have adopted the same parameter settings
proposed for synthetic databases: D, the number of transactions in the database
has been fixed to 100 thousands; N, the total number of items, fixed to 1000. T, the
average transaction length, has been fixed to 10, since its value does not influence
the program behaviour. On the contrary, I, the average length of the frequent
itemsets, has been varied, since its value really determines the depth of the lattice
to be generated. Each database contains itemsets with sufficient support having a
different average length (3,4,: : :,8). The extreme values of the interval [2-10] have
been discarded for the reasons that follow.
The low value has been discarded because it does not make much sense to maximize
the entropy related to itemsets having only two items: the direct approach,
that compares the probability of such an itemset with the product of the probabilities
of the two items, has been adopted in this case. The high values have been
avoided in consideration of the fact that longer are the itemsets the more probability
they have to occur under the threshold of minimum support. In this case too
few itemsets reveal to be over the threshold and the comparison of the different
experiments is no more fair.
Thus, it happens that even if the "nominal" average itemsets length is increased
the actual average length of the itemsets with sufficient support reveals to be significantly
lower. Table 10 reports the total number of itemsets with sufficient support
and their nominal and actual average lengths in the experiments.
In

Figure

11 two execution times are shown. T 1 is the CPU execution time needed
for the identification of all the itemsets with sufficient support; T 2 is the time for the
computation of the dependence values of the itemsets previously identified. Both
22 \Delta R. Meo
Total number nominal average actual average
of itemsets itemset length itemset length
Fig. 10. The number of itemsets and their average lengths in the experiments.
the times have been normalized with respect to the total number of itemsets, since
this one changes considerably in the different experiments.0.0050.0150.0250.0350.0452.81 3.28 3.67 4.05 4.82 4.96
CPU
time[s]
Average itemset length
Execution times per itemset
Fig. 11. Experimental results.
You can notice that time T 1 decreases with the actual average itemset length.
This is a particularity of the algorithm adopted (called Seq) for the first step,
because this one builds, during its execution, temporary data structures that does
not depend on the itemset length. Furthermore, Seq has been proved to be suitable
to very long databases and to searches characterized by very low values of resolution.
On the contrary, time T 2 increases with the average itemset length, since the
depth of the resulting lattice increases. Thus, this fact is not surprising. On the
other side, you can observe that the increments are moderate with the exception of
the experiment having the average itemset length equal to 4.82 (corresponding to a
nominal average itemset length equal to 6). In that experiment, as Table 10 reports,
the total number of itemsets that exceed the minimumsupport threshold, compared
Theory of Dependence Values \Delta 23
to the itemsets length, grows suddenly: in these conditions, the generated lattice
is very heavily populated. Therefore, the high dimension of the output explains
the result. Finally, these experiments demonstrate that this new approach to the
discovery of knowledge on the itemsets dependencies is feasible and suitable to the
high resolution researches that are typical of data mining.
6. CONCLUSIONS
In this paper it has been shown that a single real - the dependence value - contains
all the information on dependencies relative to a given itemset. Besides, by
virtue of the Theorem stating that dependence functions are always parity func-
tions, the determination of the combinations of values for which dependencies are
positive or negative is immediate. Furthermore, the feasibility of this new theory
is demonstrated in practical cases on a set of experiments on different databases.
Some themes are worth being developed further. The first one concerns the maximum
independence estimates. Is it possible to find a closed formula giving the
maximum independence probability of a given itemset as a function of the lower
level probabilities? The second theme to be developed is the definition of the confidence
levels. Which percentage of the probability P(a,b,: : :) must be exceeded by
the dependence value in order to state that dependence is strong? This question has
been discussed adequately neither in the known framework support-confidence, but
probably the model here introduced is more suitable to a sound theoretical analysis.
A third area of investigation concerns the algorithms for determining the dependence
values. The method proposed in this paper assumes that the itemset having
sufficient support have been determined by adopting one of the known methods
and on these ones performs the computation of the dependence values. However,
it is likely that an integrated method combining the two steps is more rapid and
effective. Theoretical analysis based on probability and information theory and the
development of new algorithms should be combined and integrated in this area of
research.



--R

Online generation of association rules.
Database mining: A performance perspective.
Mining association rules between sets of items in large databases.

Fast discovery of association rules.
Fast algorithms for mining association rules in large databases.
An efficient algorithm for mining association rules in large databases.

Knowledge discovery in databases: An attribute-oriented approach



Sampling large databases for association rules.

From file mining to database mining.
A statistical perspective on kdd.
Practitioner problems in need of database research: Research directions in knowledge discovery.
A new approach for the discovery of frequent itemsets.
An effective hash based algorithm for mining association rules.
Mining quantitative association rules in large relational tables.
Beyond market baskets: generalizing association rules to dependence rules.
Mining generalized association rules.
--TR
Practitioner problems in need of database research
Mining association rules between sets of items in large databases
An effective hash-based algorithm for mining association rules
Mining quantitative association rules in large relational tables
Dynamic itemset counting and implication rules for market basket data
Fast discovery of association rules
Beyond Market Baskets
Database Mining
Pincer Search
Online Generation of Association Rules
Set-Oriented Mining for Association Rules in Relational Databases
Knowledge Discovery in Databases
Fast Algorithms for Mining Association Rules in Large Databases
Discovery of Multiple-Level Association Rules from Large Databases
An Efficient Algorithm for Mining Association Rules in Large Databases
Mining Generalized Association Rules
Sampling Large Databases for Association Rules
A New Approach for the Discovery of Frequent Itemsets

--CTR
Alexandr Savinov, Mining dependence rules by finding largest itemset support quota, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Elena Baralis , Paolo Garza, Associative text categorization exploiting negated words, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Peter Fule , John F. Roddick, Experiences in building a tool for navigating association rule result sets, Proceedings of the second workshop on Australasian information security, Data Mining and Web Intelligence, and Software Internationalisation, p.103-108, January 01, 2004, Dunedin, New Zealand
Elena Baralis , Silvia Chiusano, Essential classification rule sets, ACM Transactions on Database Systems (TODS), v.29 n.4, p.635-674, December 2004
entropy;dependence rules;variables independence;association rules