Mining Optimized Association Rules with Categorical and Numeric Attributes.
AbstractMining association rules on large data sets has received considerable attention in recent years. Association rules are useful for determining correlations between attributes of a relation and have applications in marketing, financial, and retail sectors. Furthermore, optimized association rules are an effective way to focus on the most interesting characteristics involving certain attributes. Optimized association rules are permitted to contain uninstantiated attributes and the problem is to determine instantiations such that either the support or confidence of the rule is maximized. In this paper, we generalize the optimized association rules problem in three ways: 1) association rules are allowed to contain disjunctions over uninstantiated attributes, 2) association rules are permitted to contain an arbitrary number of uninstantiated attributes, and uninstantiated attributes can be either categorical or numeric. Our generalized association rules enable us to extract more useful information about seasonal and local patterns involving multiple attributes. We present effective techniques for pruning the search space when computing optimized association rules for both categorical and numeric attributes. Finally, we report the results of our experiments that indicate that our pruning algorithms are efficient for a large number of uninstantiated attributes, disjunctions, and values in the domain of the attributes.
Introduction
Association rules, introduced in [1], provide a useful
mechanism for discovering correlations among the underlying
data. In its most general form, an association
rule can be viewed as being defined over attributes of
a relation, and has the form C
are conjunctions of conditions, and each condition
is either A are values
from the domain of the attribute A i ). Each rule has
an associated support and confidence. Let the support
of a condition C i be the ratio of the number of tuples
satisfying C i and the number of tuples in the relation.
The support of a rule of the form C is then the
same as the support of C 1 - C 2 , while its confidence
is the ratio of the supports of conditions C 1 - C 2 and
. The association rules problem is that of computing
all association rules that satisfy user-specified minimum
support and minimum confidence constraints,
and schemes for this can be found in [1, 2, 6, 10, 11].
For example, consider a relation in a telecom service
provider database that contains call detail infor-
mation. The attributes of the relation are date, time,
src city, src country, dst city, dst country and duration.
A single tuple in the relation thus captures information
about the two endpoints of each call, as well as
the temporal elements of the call. The association rule
(dst country = France) would satisfy
the user-specified minimum support and minimum
confidence of 0.05 and 0.3, respectively, if at least 5%
of total calls are from NY to France, and at least 30%
of the calls that originated from NY are to France.
The optimized association rules problem, motivated
by applications in marketing and advertising, was introduced
in [5]. An association rule R has the form
tribute, l 1 and u 1 are uninstantiated variables, and
only instantiated conditions (that
is, the conditions do not contain uninstantiated vari-
ables). The authors propose algorithms for determining
values for the uninstantiated variables l 1 and u 1
for each of the following cases:
ffl Confidence of R is maximized and support of the
condition is at least the user-specified
support (referred to as the optimized confidence
rule).
ffl Support of the condition
maximized and confidence of R is at least the user-specified
confidence (referred to as the optimized
support rule).
Optimized association rules are useful for unraveling
ranges for numeric attributes where certain trends
or correlations are strong (that is, have high support
or confidence). For example, suppose the telecom service
provider mentioned earlier was interested in offering
a promotion to NY customers who make calls
to France. In this case, the timing of the promotion
may be critical - for its success, it would be advantageous
to offer it close to a period of consecutive days
in which at least a certain minimum number of calls
from NY are made and the percentage of calls from
NY to France is maximum. The framework developed
in [5] can be used to determine such periods.
Consider, for example, the association rule (date 2
dst
a minimum support of 0.03, the optimized confidence
rule results in the period for which calls from NY in
the period are at least 3% of the total number of calls,
and the percentage of calls from NY that are directed
to France is maximum. With a minimum confidence
of 0.5, the optimized support rule results in the period
during which at least 50% of the calls from NY are to
France, and the number of calls originating in NY is
maximum.
A limitation of the optimized association rules dealt
with in [5] is that only a single optimal interval for
a single numeric attribute can be determined. How-
ever, in a number of applications, a single interval
may be an inadequate description of local trends in
the underlying data. For example, suppose the telecom
service provider is interested in doing upto k promotions
for customers in NY calling France. For this
purpose, we need a mechanism to identify upto k periods
during which a sizable number of calls from NY to
France are made. If association rules were permitted
to contain disjunctions of uninstantiated conditions,
then we could determine the optimal k (or fewer) periods
by finding optimal instantiations for the rule:
(date
dst France. The above framework can be
further strengthened by enriching association rules
to contain more than one uninstantiated attribute,
and permitting attributes to be both numeric (e.g.,
date and duration) as well as categorical (e.g., src city,
dst country). Thus, optimal instantiations for the rule
dst France would yield
valuable information about cities and periods with a
fairly high outward call volume, a substantial portion
of which is directed to France. Alternately, information
about cities and specific dates can be obtained from
the rule (src
dst country = France. This information
can be used by the telecom service provider to
determine the most suitable geographical regions and
dates for offering discounts on international long distance
calls to France.
In this paper, we generalize the optimized association
rules problem, described in [5], in three ways - 1)
association rules are permitted to contain disjunctions
over uninstantiated attributes, 2) association rules are
allowed to contain an arbitrary number of uninstantiated
attributes, and uninstantiated attributes can
be either categorical or numeric. We first show that
the problem of computing optimized support and optimized
confidence association rules in our framework is
NP-hard. We then present a general depth first search
algorithm for exploring the search space. The algorithm
searches through the space of instantiated rules
in the decreasing order of the weighted sums of their
confidences and supports, and uses branch and bound
techniques to prune the search space effectively. For
categorical attributes, we also present a graph search
algorithm that, in addition, uses intermediate results
to reduce the search. Finally, for numeric attributes,
we develop techniques to eliminate certain instantiated
rules prior to searching through them. Experimental
results indicate that our schemes perform well for
a large number of uninstantiated attributes, disjunctions
and values in the domain of the uninstantiated
attributes. Proofs of theorems presented in the paper
can be found in [9].
Related Work
Association rules for a set of transactions in which
each transaction is a set of items bought by a customer,
were first studied in [1]. These association rules for
sales transaction data have the form
and Y are disjoint sets of items. Efficient algorithms
for computing them can be found in [2, 7, 6, 10, 11, 3].
In [10, 6], the generalization of association rules to
multiple levels of taxonomies over items is studied.
Association rules containing quantitative and categorical
attributes are studied in [8] and [11]. The work
in [8] restricts association rules to be of the form
suggest ways to extend
their framework to have a range (that is, A
rather than a single value in the left hand side of a
rule. To achieve this, they partition numeric attributes
into intervals. However, they do not consider merging
neighboring intervals to generate a larger interval. In
[11], the authors use a partial completeness measure
in order to determine the partitioning of numeric attributes
into intervals.
The optimized association rule problem was introduced
in [5]. The authors permit association rules to
contain a single uninstantiated condition A 1
on the left hand side, and propose schemes to determine
values for variables l 1 and u 1 such that the confidence
or support of the rule is maximized. In [4], the
authors extend the results in [5] to the case in which
rules contain two uninstantiated numeric attributes on
the left hand side. They propose algorithms that discover
optimized gain, support and confidence association
rules for two classes of regions - rectangles and
admissible regions (for admissible regions, the algorithms
compute approximate, not optimized, support
and confidence rules). However, their schemes only
compute a single optimal region. In contrast, our algorithms
are general enough to handle more than two
uninstantiated attributes, which could be either categorical
or numeric. Furthermore, our algorithms can
generate an optimal set of rectangles rather than just a
single optimal rectangle (note that we do not consider
admissible regions or the notion of gain in this paper).
This enables us to find more interesting patterns.
3 Preliminaries
In this section, we define the optimized association
rule problem addressed in the paper. The data is assumed
to be stored in a relation defined over categorical
and numeric attributes. Association rules are
built from atomic conditions each of which has the
could be either categorical or nu-
meric), and A i 2 [l (only if A i is numeric). For
the atomic condition A a value from the
domain of A i , the condition is referred to as instanti-
ated; else, if v i is a variable, we refer to the condition as
uninstantiated. Likewise, the condition A i 2 [l
referred to as instantiated or uninstantiated depending
on whether l i and u i are values or variables.
Atomic conditions can be combined using operators
- or - to yield more complex conditions. Instantiated
association rules, that we study in this paper,
have the form C are arbitrary
instantiated conditions. Let the support for an
instantiated condition C, denoted by sup(C), be the
ratio of the number of tuples satisfying the condition C
and the total number of tuples in the relation. Then,
for the association rule R: C defined
as is defined as sup(C1-C2 )
Note that our definition of sup(R) is different from
the definition in [1] where sup(R) was defined to be
Instead, we have adopted the definition
used in [5] and [4]. Also, let minSup and minConf
denote the user-specified minimum support and minimum
confidence, respectively.
The optimized association rule problem requires optimal
instantiations to be computed for an uninstantiated
association rule which has the form: U-C
where U is a conjunction of m uninstantiated atomic
conditions over m distinct attributes, and C 1 and C 2
are arbitrary instantiated conditions. Let U i denote an
instantiation of U - thus, U i is obtained by replacing
variables in U with values. An instantiation U i can be
mapped to a rectangle in m-dimensional space - there
is a dimension for each attribute and the co-ordinates
for the rectangle in a dimension are identical to the
values for the corresponding attribute in U i . Two instantiations
U 1 and U 2 are said to be non-overlapping
if the two (m-dimensional) rectangles defined by them
do not overlap (that is, the intersection of the two rectangles
is empty).
Having defined the above notation for association
rules, we present below, the formulations of the optimized
association rule problems.
Optimized Confidence Problem: Given k
and an uninstantiated rule U - C
non-overlapping instantiations U
of U with l - k such that sup(R) -
minSup and conf(R) is maximized, where R is
the rule (U
ffl Optimized Support Problem: Given k and
an uninstantiated rule U - C
non-overlapping instantiations U
of U with l - k such that conf(R) -
minConf and sup(R) is maximized, where R is
the rule (U
The problem of computing optimized association
rules required instantiations U l to be determined
such that the rule R :
satisfies user-specified constraints. Suppose for an instantiation
U i of U , I i is the instantiated rule U
for a set of instantiated rules,
sup(S) and conf(S) are defined as follows.
Then, we have
conf(R). Thus, since (1) for every instantiated rule (or
alternatively,
can be computed by performing a single pass over the
relation, and (2) these, in turn, can be used to compute
supports and confidences for sets of instantiations, the
optimized association rule problem reduces to the following

Optimized Confidence Problem: Given k,
and sup(I i ) and conf(I i ) for every instantiation
I i , determine a set S containing at
most k non-overlapping instantiations such that
sup(S) -minSup and conf(S) is maximized.
ffl Optimized Support Problem: Given k, and
instantiation I i ,
determine a set S containing at most k non-overlapping
instantiations such that conf(S) -
minConf and sup(S) is maximized.
In the remainder of the paper, we use the above
formulations instead to develop algorithms for the optimized
association rule problems.
4 Categorical Attributes
In this section, we present algorithms for computing
optimized support and confidence sets when rules
contain only uninstantiated conditions of the form
v. Thus, the results of this section are only
applicable to categorical attributes and numeric attributes
restricted to A (conditions of the form
is a numeric attribute, are dealt
with in the next section). An example of such a rule
is dst France
(in the rule, date is a numeric attribute while src city
is categorical).
Due to the above restriction, any two arbitrary instantiations
are always non-overlapping. This property
is essential for the correctness of the pruning technique
used by the graph search algorithm presented in Section
4.4.
4.1 NP-Hardness Result
The problem of computing optimized sets, given
instantiation I i , can be
shown to be intractable, and follows from the following
theorem.
Theorem 4.1: Given sup(I i ) and conf(I i ) for every
instantiation I i , determining if there is a set S containing
an arbitrary number of instantiations such that
conf(S) - minConf and sup(S) - minSup is NP-hard.
In the following subsections, we present schemes for
computing optimized sets that employ techniques for
pruning the search space in order to overcome the complexity
of the problem. In each subsection, we first
present the scheme for computing optimized confidence
sets, and then briefly describe the modifications to the
scheme in order to compute optimized support sets.
1 Note that if the domain of the numeric attribute A i is large,
then it can be partitioned into a sequence of n i intervals, and
successive intervals can be mapped to consecutive integers in the
interval between 1 and n i .
procedure optConfNaive(curSet, curLoc):
1. for i := curLoc to n do f
2. S := curSet [ finstArray[i]g
3. if sup(S) - minSup and conf(S) ? conf(optSet)
4. optSet := S
5. if
7. g

Figure

1: Naive Alg. for Optimized Confidence Set
4.2 Naive Algorithm
Optimized Confidence Set: We begin by presenting
a naive algorithm for determining the optimized
confidence set of instantiations (see Figure 1). In a
nutshell, the algorithm employs depth first search to
enumerate all possible sets containing k or less instan-
tiations, and returns the set with the maximum confidence
and support at least minSup.
The algorithm assumes that instantiations are
stored in the array instArray. The number of instantiations
is is the number
of values in the domain of A i . The algorithm is
initially invoked with arguments
Loc=1. The variable optSet is used to keep track of the
optimized set of instantiations encountered during the
execution of the algorithm. The algorithm enumerates
all possible subsets of size k or less by recursively invoking
itself (Step 6) and sets optSet to a set with a greater
confidence than the current optimized set (steps 3 and
4). Each invocation accepts as input curSet, the set
of instantiations to be further extended, and curLoc,
the index of the first instantiation in instArray to be
considered for extending curSet (all instantiations between
curLoc and n are considered). The extended
state is stored in S, and if the number of instantiations
in S is less than k, the algorithm calls itself recursively
to further extend S with instantiations whose index is
greater than the index of all the instantiations in S.
The complexity of the naive algorithm is \Sigma k
When k - n, the complexity of the algorithm becomes
O(n k ). However, as we showed earlier, if there is no
restriction on the size of the optimized set (that is,
n), the problem is NP-hard.
Optimized Support Set: The naive algorithm for
computing the optimized support set is similar to opt-
ConfNaive, except that the condition in Step 3 which
tries to maximize confidence is replaced with the following
sup(optSet).
4.3 Pruning Using the Current Optimized
The naive algorithm exhaustively enumerates all
possible sets with at most k instantiations - this results
in high complexity. However, in the naive algorithm illustrated
in Figure 1, if we know that the confidence of
any set satisfying minimum support and obtained as a
result of extending curSet cannot exceed the confidence
of the current optimized set (that is, optSet), then we
can stop extending curSet immediately and reduce the
search space significantly. In this section, we develop
branch and bound pruning techniques that, with the
aid of the current optimized set, considerably reduce
the overhead of exploring the entire search space.
For our pruning techniques to be effective, it is imperative
that we find a set close to the optimized set
early - since it can then be used to eliminate a larger
number of sub-optimal sets. It may seem logical that
for the optimized confidence problem, since we are trying
to maximize confidence, considering instantiations
with high confidences first may cause the search to converge
on the optimized set more rapidly. However, this
may not be the case since the support of the optimized
confidence set has to be at least minSup. For a high
minimumsupport, it may be better to explore instantiations
in the decreasing order of their supports. Thus,
the order in which instantiations must be considered
by the search algorithm is a non-trivial problem. In order
to investigate this idea of pruning curSet early, we
introduce the notion of the weight of an instantiation
I (denoted by w(I)) and define it below.
In the definition, w 1 and w 2 are positive real con-
stants. Thus, the weight of an instantiation is the
weighted sum of both, its confidence and support. Our
search algorithms can then consider instantiations with
higher weights first, and by using different values of
vary the strategy for enumerating sets. In
the remainder of this section, we propose algorithms
that store instantiations in instArray in the decreasing
order of their weights and explore instantiations with
higher weights first. We also present techniques that
exploit the sort order of instantiations to prune the
search space. The variables maxConf and maxSup are
used to store the maximum confidence and maximum
support of all the instantiations in instArray, respectively

Optimized Confidence Set: Suppose the current
set of instantiations, curSet, is only extended with
instantiations belonging to the set comprising of
instArray[i], for some i, and instantiations following it
in instArray. The key idea is that we can stop extending
curSet if among instantiations being considered to
extend curSet, there does not exist a set of instantiations
S such that (1) sup(curSet[S) - minSup, and
In order to determine whether a set S satisfying
the above conditions (1) and (2) exists, we first derive
the constraints that such a set S must satisfy. If
the constraints are unsatisfiable with the remaining instantiations
that are candidates for extension, a set S
satisfying the conditions (1) and (2) does not exist and
we can stop extending curSet immediately. Let variables
s and c denote sup(S) and conf(S), respectively,
and In the following, we derive
the constraints on s that must be satisfied by any
set S that could be used to extend curSet such that
conditions (1) and (2) hold. Due to the condition (2),
we have the following constraint.
Re-arranging the terms yields the following constraint.
s
(1)
Also, since the set curSet[S must satisfy minimum
support, and a set S can consist of at most l instantiations
we require s to satisfy the following two constraints

Note that since the confidence of set S can be
at most maxConf, we have the following constraint:
maxConf. Combining this constraint with Constraint
(1) results in the following constraint which, if
satisfied by s, ensures that there exists a c that does
not exceed maxConf and at the same time, causes the
confidence of curSet[S to be at least conf(optSet).
Finally, we exploit the fact that instantiations are
sorted in the decreasing order of their weights and only
instantiations that follow instArray[i] are used to extend
curSet. We utilize the following property of sets
of instantiations.
Theorem 4.2: For an arbitrary set of instantiations
there exists an instantiation I 2 S such that
Thus, since S contains only instantiations with
weights at most w(instArray[i]), and S can contain at
most l instantiations, due to Theorem 4.2, we obtain
the following constraint on s and c.
l
Re-arranging the terms, we get
w(instArray[i])   l \Gamma w2   s
l   w1
Since c, the confidence of S, must be at least 0, substituting
for c in the above equation results in the
following constraint that prevents s from getting so
procedure optConfPruneOpt(curSet, curLoc):
1. for i := curLoc to n do f
2. [minS,maxS] := optConfRange(curSet, i)
3. if minS ? maxS
4. break
5. S := curSet [ finstArray[i]g
6. if sup(S) - minSup and conf(S) ? conf(optSet)
7. optSet := S
8. if
9.

Figure

2: Depth first alg. for optimized confidence set
large that c would have to become negative to satisfy
the above constraint.
w(instArray[i])   l
Finally, constraints (1) and (5) can be combined
to limit s to values for which a corresponding value
of c can be determined such that the confidence of
curSet[S does not drop below conf(optSet), and
the weights of instantiations in S do not exceed
w(instArray[i]).
w(instArray[i])   l \Gamma w2   s
w1   l
s
Any set S used to extend curSet to produce a better
set for optimized confidence must satisfy the constraints
(on its support). Thus, if there exists
a value of s satisfying constraints (2)-(7), then curSet
must be extended. Otherwise, it can be pruned without
extending it further.
The procedure for computing the optimized confidence
set, illustrated in Figure 2, is similar to the
naive algorithm except that it invokes optConfRange
to determine if there exists an S that curSet can be
extended with to yield the optimized set. It stops extending
curSet if the range of values [minS, maxS] for
the support of such a set is empty (which happens
when minS ? maxS).
The procedure optConfRange computes the range
[minS, maxS] which is the range of values for s that
satisfy the above constraints. If there does not exist
an s that satisfies constraints (2)-(7), then a range for
which minS ? maxS is returned for convenience. Thus,
for the returned range from optCon-
fRange, we can stop extending curSet. The procedure
takes as input curSet and the index i (in instArray)
of the next instantiation being considered to extend
curSet. A detailed derivation of the ranges satisfying
the above constraints and a description of the procedure
optConfRange can be found in [9].
Optimized Support Set: For optimized support
sets, constraints on s are similar to constraints (1)-
(7) except that conf(optSet) and minSup are replaced
with minConf and sup(optSet), respectively. In other
words, the confidence of curSet [ S must be at least
minConf and the support of curSet [ S should be no
smaller than that of optSet. Thus, optSupRange, the
procedure to compute the range of values for s that
satisfy constraints (1)-(7), is similar to optConfRange
with all occurrences of conf(optSet) and minSup replaced
with minConf and sup(optSet). Also, optSup-
PruneOpt, the procedure for computing optimized sets
invokes optSupRange instead. Note that if
maxConf, then optSupRange always returns [1,0] for
convenience. However, this is a special case for which
the optimized support set can be computed directly
and is simply the set of all instantiations with confidence
maxConf.
4.4 Pruning using Intermediate Sets
The pruning technique presented in the previous
subsection used the current optimized set to reduce
the search space of the depth-first algorithm for computing
optimized sets. A different class of algorithms,
graph search algorithms, maintain a list of intermediate
sets, and in each step, extend one of them. In this
case, not only the current optimized set but also the
intermediate sets can be used for pruning. The graph
search algorithms, however, do incur additional storage
overhead since they have to keep track of intermediate
sets. In this section, we present new techniques for
pruning using intermediate sets.
Optimized Confidence Set: The algorithm, after
the p th step, keeps track of, for the p instantiations
with the highest weight, (1) the current optimized set,
and (2) intermediate sets involving some subset of the
instantiations. The intermediate sets are those that
have the potential to be further extended with the remaining
instantiations to yield the optimized set. In
the p+1 th step, it extends every intermediate set using
the instantiation with the next highest weight, thus
generating new intermediate sets. If any of the new
intermediate sets is better than the current optimized
set, then optSet is replaced. Next, since instantiations
in instArray are stored in the decreasing order of their
weights, procedure optConfRange from the previous
subsection (that used the current optimized set for
pruning) is used to eliminate those intermediate sets
that can never be candidates for the optimized set.
Furthermore, consider two intermediate sets S 1 and
set S of instantiations that can be used to extend
in a set with confidence at least that of
optSet and support at least minSup),
minSup and conf(S 1 [ Due to
it is the case that S 1 [S
contains no more instantiations than
since there is no overlap between any two arbitrary
instantiations, for some set S if S 2 [S could be an optimized
confidence set, then S 1 [S is also an optimized
set. Consequently, it follows that deleting S 2 from the
list of intermediate sets does not affect the ability of
our algorithm to discover the optimized confidence set.
The range of supports for a set S that can be used to
extend S 2 to result in a set with support minSup and
confidence as good as the current optimized set can
be obtained using the procedure optConfRange. Fur-
thermore, if s and c are the support and confidence of
set S, respectively, is the
index of the next instantiation to be considered for extending
the intermediate sets, then due to constraints
(1) and (5) from the previous section, the confidence
of S satisfies the following inequality.
s
w(instArray[i])   l \Gamma w2   s
l   w1
Suppose, in addition, we compute the range of supports
for a set S which when used to extend S 1 causes
its support to be at least minSup and for all values of
c satisfying Constraint (8), the confidence of
is at least that of S 2 [ S. Now, if the former range
of supports for set S is contained within the latter,
then it implies that for every set S (with support s
and confidence c satisfying Constraint (8) above) that
can be used to extend S 2 to yield an optimized set,
the same set S can also be used to extend S 1 resulting
in a set with support at least minSup and confidence
greater than or equal to that of S [ S 2 . Thus, S 2 can
be pruned. The challenge is to determine the latter
range, which we compute below, as follows. We required
the support of S 1 [ S to be at least minSup -
this translates to the following constraint on s.
In addition, we required that for all values of c satisfying
Constraint (8), conf(S 1 [S) - conf(S 2 [S). Thus
s must satisfy the following constraint for all values of
c satisfying Constraint (8).
It can be shown that if sup(S 1
a given value of s, the above constraint holds for all
values of c (satisfying Constraint (8)) if it holds for
s and the leftmost term in Constraint (8).
Similarly, if sup(S
of s, Constraint (10) holds for all values of c (satisfy-
ing Constraint (8)) if it holds for s and
rightmost term in Constraint (8). Thus, the range of
values for s that we are interested in are those that
satisfy Constraint (9), and either Constraint (10) with
c replaced with c min if sup(S 1
Constraint (10) with results
in two separate equations of the form A   s 2 +B   s+C -
with values of A, B and C. The range of values
for s that satisfy the equations can be determined by
procedure optConfPruneInt(intList, curLoc):

Figure

3: Graph search alg. for optimized confidence
set
solving the quadratic inequality equation. Due to lack
of space, the procedure optConfCanPrune to decide
whether an intermediate set S 1 can prune another intermediate
set S 2 with the next instantiation to extend
both intermediate sets is presented in [9].
The overall procedure for computing optimized confidence
sets is described in Figure 3. The procedure
accepts as input parameters intList which is a list of
intermediate sets for the first curLoc-1 instantiations
in instArray, and curLoc which is the index of the instantiation
(in instArray) to be considered next for
extending the intermediate sets in intList. The procedure
is initially invoked with arguments intList=;
and curLoc=1, and it recursively invokes itself with
successively increasing values for curLoc.
The procedure begins by extending every set in
intList with instArray[curLoc] and forms a new list
newList containing finstArray[curLoc]g and the extended
sets (steps 1-7). Furthermore, if an extended
set in newList is found to have support at least minSup
and higher confidence than the currently stored optimized
set, then optSet is set to the extended set. In
steps 10-24, those intermediate sets that cannot be extended
further to result in the optimized set are deleted
from intList. These include sets already containing k
instantiations and sets S for which optConfRange(S,
curLoc+1) returns an empty range. In addition, for
any two intermediate sets S 1 and S 2 in intList that can
be extended to result in an optimized set, if one can
prune the other, then the other is deleted (steps 14-
21). Finally, steps 25-27 contain conditions that enable
the algorithm to terminate early - even though
curLoc may be less than n. This occurs when there
are no intermediate sets to expand (that is, intList
;) and the weight of instArray[curLoc+1] is less than
minWeight, the minimum weight required to generate
the optimized set (follows from Theorem 4.2).
In this section, we present algorithms for computing
optimized sets when association rules contain uninstantiated
conditions of the form A
a numeric attribute. Thus, unlike the previous section,
in which an instantiation was obtained by instantiating
each uninstantiated attribute with a single value
in its domain, in this section each uninstantiated attribute
is instantiated with an interval in its domain.
Thus, each instantiation corresponds to a rectangle in
m-dimensional space (in the previous section, each instantiation
corresponded to a point in m-dimensional
space).
Permitting association rules to contain uninstantiated
numeric attributes in conditions of the form
complicates the problem of computing optimized
sets in several ways. First, unlike the categorical
attribute case in which two distinct instantiations
had no overlap (since each instantiation corresponded
to a point), two distinct instantiations may overlap.
This makes it impossible to use intermediate sets for
pruning as described in Section 4.4. For instance, when
computing optimized confidence sets, consider two intermediate
sets S 1 and S 2 such that for every set S
of instantiations that can be used to extend S 2 (to result
in a set with confidence at least that of optSet
and support at least minSup),
and
conf(S may not qualify
to be the optimized set since instantiations in S may
overlap with instantiations in S 1 . However, there may
be no overlap between S and S 2 , and thus it may still
be possible to extend S 2 to result in the optimized set.
As a result, S 1 cannot prune S 2 . This is not a problem
for categorical attributes since there is no overlap
between any pair of instantiations.
The depth first algorithm in Section 4.3, how-
ever, can be modified to compute optimized confidence
sets. Since the optimized set can contain only
non-overlapping instantiations, we must not extend
curSet with an overlapping instantiation instArray[i]
- this cannot result in the optimized set. For a set
S of instantiations and an instantiation I, let the
function overlap(S; I) return true if the rectangle for
some instantiation in S and the rectangle for I over-
lap. Then the modification to optConfPruneOpt is to
have the statement "if overlap(curSet,
false" between steps 1 and 2, and the body of this
if-statement includes the steps 2-8.
The next complication is that if there are m uninstantiated
attributes A 1 , A 2 in conditions of
the form A and the domain of A i ranges between
1 and n i , then the total number of instantiations
is In contrast, the number of
possible instantiations if every attribute was categorical
would be n 1 . Thus, the number of
instantiations to be examined by our search algorithms
increases dramatically for optimized association rules
with uninstantiated conditions of the form A
In the remainder of this section, we propose a pruning
technique for the optimized confidence problem
that reduces the number of instantiations stored in
instArray, but still guarantees optimality. Reducing
the number of instantiations allows us to lower the
overhead of storing (that is, appending) the instantiations
to instArray, and to incur smaller costs when
sorting the instantiations in the decreasing order of
their weights. More importantly, it can also considerably
reduce the input size to our search algorithms.
Key Observation: As we mentioned earlier, the
number of instantiations for numeric attributes
increases significantly as the number of uninstantiated
attributes increases. An instantiation
for m numeric attributes can be represented as
where the interval
for the uninstantiated numeric attribute A i is bounded
by x i below and y i above. Thus, the x
determine the bounds for the rectangle for the instantiation
along each of the m axis. For instantiations
I
I we say that I 1
is contained in I 2 if u (that
is, the rectangle for I 1 is contained in the rectangle for
I 2 ).
The following theorem provides the basis for pruning
instantiations in instArray when computing optimized
confidence sets.
Theorem 5.1 : Let I 1 and I 2 be two instantiations
such that I 1 is contained in I 2 . If both I 1 and I 2 have
support at least minSup and conf(I 1
there exists an optimized confidence set that does not
contain I 2 .
Instantiation I 2 can be deleted since I 2 's rectangle
is the outer rectangle. Thus, if the optimized
set were to contain I 2 , then replacing I 2 with I 1 results
in an optimized set with at least the same confidence
and no overlapping instantiations. However,
the above pruning rule does not work for optimized
support sets since that would require I 1 to be pruned
(when I 1 's rectangle is contained in I 2 's rectangle and
Thus, if the optimized
set were to contain I 1 , then replacing I 1 with
I 2 results in an optimized set with as high confidence
and support - however, it could contain overlapping
instantiations.
Due to lack of space, we do not report in this pa-
per, the details of the algorithm that uses the above
pruning rule for pruning instantiations from instArray
before optConfPruneOpt is executed. The algorithm,
including an analysis of its time and space complexity,
can be found in [9]. In [9], we show that the time complexity
of the algorithm is O(m   n 2
m is the number of numeric attributes considered and
n i is the number of values for attribute A i .
6 Experimental Results
In this section, we study the performance of our algorithms
for computing optimized confidence and support
sets. From our experimental results, we establish
that
ffl Our pruning techniques improve the performance
of both, depth first and graph search algorithms,
significantly.
ffl The values for w 1 and w 2 play an important role
in reducing the search times of our algorithms.
ffl Pruning instantiations prior to performing search,
whenever possible, can result in further improvements
in performance.
ffl The low execution times of our algorithms in a
large number of cases make them suitable to be
used in practice.
Since naive algorithms that exhaustively enumerate
all possible sets are obviously too expensive, we do not
consider them. Also, the data file is read only once at
the beginning of each algorithm (in order to generate
instantiations). The time for this, in most cases, constitutes
a tiny fraction of the total execution time of
our algorithms. Thus, we do not include the time spent
on reading the data file in our results. Furthermore,
note that the performance of our algorithms does not
depend on the number of tuples in the data file - it
is more sensitive to the number of attributes and the
sizes of their domains.
We performed extensive experiments using a Sun
Ultra-2/200 machine with 512 MB of RAM and running
Solaris 2.5. However, due to lack of space, we do
not report all our experimental results - these can be
found in [9].
Synthetic Datasets: The association rule that we
experimented with, has the form U-C
contains m uninstantiated attributes (see Section 3).
For simplicity, we assume that the domains of the uninstantiated
attributes consist of integers ranging from 1
to n. We consider two forms for U . The first, U 0 , has
the form A can be used for
both categorical and numeric attributes. The second,
U 00 , has the form A 1
and can be used only for numeric attributes. Every
instantiation of U (and thus, every point
in m-dimensional space) is assigned a randomly generated
confidence between 0 and 1 with uniform dis-
tribution. Each instantiation of U
assigned a randomly generated support between 0 andn m with uniform distribution.
6.1 Pruning Prior to Search
We begin by studying the effectiveness of pruning
instantiations from instArray prior to performing
search. This technique applies only to optimized confidence
sets when U has the form U 00 - it was introduced
in Section 5 and the detailed algorithm and experimental
result can be found in [9]. In our experiment, the
best execution time for the algorithm without prior
pruning is greater than the best execution time for the
prior pruning algorithm. As a result, in subsequent
experiments, we only use the prior pruning algorithm.
6.2 Sensitivity to w 1 and w 2
Optimized Confidence Sets: For optimized confidence
sets, we fix w 1 at 1 and vary w 2 . When
the support of each instantiation is very low (the average
support of an instantiation is 1
In contrast,
when instantiations with larger rectangles
have larger supports - as a matter of fact, the instantiation
with the largest rectangle has support 1. Thus,
for only low values for minSup are mean-
ingful, and (2) only large values for w 2 impact the performance
of our search algorithms.
We first describe the results for Figure 4-
(a) presents the execution times for both the depth
first as well as the graph search algorithms for values
of minSup between 0.002 and 0.0038. For most minSup
values, both algorithms perform the best when w
- that is, when instantiations are sorted by confidence
only. When minSup is very high (e.g., 0.00038), the algorithms
with w 2 of 500 (that is, the highest value for
that we selected) perform as well or better. The
reason for this is that for a majority of the support
values, the optimized confidence set comprises mainly
of instantiations with high confidences. When instAr-
ray is sorted by confidence, these instantiations are
considered first by the algorithms, allowing a rapid
convergence to the optimized confidence set. As we
increase the value of w 2 , instantiations with higher
confidences are pushed to the end of instArray by instantiations
with larger supports (and possibly smaller
confidences). Thus, the algorithms need to enumerate
more sets before the optimized set is reached, and
this makes them perform poorly. Higher values of w 2 ,
however, are better for large minSup values when the
optimized confidence set contains instantiations with
both high supports and high confidences.
Once instantiations are sorted such that those belonging
to the optimized set are toward the front of
instArray, then the graph search algorithm that uses
intermediate sets for pruning is faster than the depth
first algorithm that uses only the current optimized set.
One of the reasons for this is that the graph search algorithm
prunes the search space more effectively. The
other reason is that the graph search algorithm initially
concentrates on finding the optimized set using
instantiations at the front of instArray and gradually
considers instantiations toward the end. In contrast,
the depth first search algorithm may have to generate
sets containing instantiations located at the end of in-
stArray before all of the instantiations at the front of
instArray have been considered.
Now, we turn our attention to In Figure
4-(b), we plot execution times for the depth first
algorithm with prior pruning as minSup is varied from
0.1 to 0.35. For typically instantiations with
large supports have small confidences and the ones
with high confidences have low supports. This explains
why (1) for all values of w 2 , execution times
for the algorithm increases with minSup, and (2) for
0:75, the algorithm performs the best. As minSup
is increased, the supports for instantiations that
are possible candidates for the optimized set increases.
Thus, with increasing minSup, a larger number of instantiations
need to be considered by the search algo-
rithms, and their performance degrades.
Furthermore for small values of w 2 (e.g., 0), instAr-
ray is sorted by confidence and instantiations with low
supports and high confidences are at the front of in-
stArray. These instantiations, however, cannot be in
the optimized set if minSup is large - thus, the algorithm
performs the worst when w
high. On the other hand, for large values of w 2 (e.g.,
2), instantiations with very high supports and low confidences
move up in instArray causing the algorithm
perform poorly for smaller values of minSup. The algorithm
performs the best for a wide range of minSup
values when w 0:75 since this results in instantiations
with moderately high values for both supports
and confidences making it to the top in instArray.
6.3 Sensitivity to size of domain
For we found that for a given k, increasing
the size of the domain n for attributes actually
causes the search times to decrease since there are a
lot more instantiations with higher supports and confidences
(supports and confidences are uniformly distributed
across the instantiations). However, when
even though the number of instantiations
with high supports and confidences increases, a disproportionately
larger number of instantiations (1) with
high confidences have low supports (e.g., points), and
(2) with high supports have low confidences (e.g., instantiations
with large rectangles). The detailed result
can be found in [9].
6.4 Sensitivity to k
Due to the lack of space, we present results in [9].
7 Concluding Remarks
In this paper, we generalized the optimized association
rules problem proposed in [5] in three ways - 1)
association rules are permitted to contain disjunctions
over uninstantiated attributes 2) association rules are
allowed to contain an arbitrary number of uninstantiated
attributes and uninstantiated attributes can
be either categorical or numeric. Since the problem
of computing optimized rules is intractable, we had
to develop effective mechanisms for both, exploring as
well as pruning the search space. We assigned a weight
to each instantiation, and our search algorithms considered
instantiations in the decreasing order of their
weights. Thus, based on input parameters (e.g., minimum
support, number of disjunctions), by appropriately
assigning weights to instantiations, the exploration
of the search space can be guided to be effi-
cient. In addition, we proposed a general depth first
algorithm that keeps track of the current optimized
rule and uses it to prune the search space. For categorical
attributes, we also proposed a graph search
algorithm that uses intermediate results to eliminate
Execution
minSup
m=4, k=20, n=10, w1=1
Opt, w2=0
Opt, w2=100
Opt, w2=500
Int, w2=500101000100000
Execution
Time
minSup
k=5, m=1, n=200
(a)

Figure

4: Sensitivity to w 1 and w 2 (optimized confidence sets)
paths that cannot result in the optimized rule. For numeric
attributes, we developed an algorithm for pruning
instantiated rules prior to performing the search
for the optimized confidence rule. Finally, we reported
the results of our experiments that demonstrate the
practicality of the proposed algorithms.

Acknowledgments

We would like to thank Phil Gibbons and Jeff Vitter
for their valuable insights that led to Theorem 4.2 and
its proof. We would also like to thank Narain Gehani,
Hank Korth and Avi Silberschatz for their encouragement
and for their comments on earlier drafts of this
paper. Without the support of Yesook Shim, it would
have been impossible to complete this work.



--R

Mining association rules between sets of items in large databases.
Fast algorithms for mining association rules.
Advances in Knowledge Discovery and Data Mining.
Data mining using two-dimensional optimized association rules: Scheme
Mining optimized association rules for numeric attributes.
Discovery of multiple-level association rules from large databases
Efficient algorithms for discovering association rules.

Mining optimized association rule for categorical and numeric attributes.
Mining generalized association rules.
Mining quantitative association rules in large relational tables.
--TR

--CTR
Mehmet Kaya , Reda Alhajj, Novel approach to optimize quantitative association rules by employing multi-objective genetic algorithm, Proceedings of the 18th international conference on Innovations in Applied Artificial Intelligence, p.560-562, June 22-24, 2005, Bari, Italy
Hye-Jung Lee , Won-Hwan Park , Doo-Soon Park, An efficient algorithm for mining quantitative association rules to raise reliance of data in large databases, Design and application of hybrid intelligent systems, IOS Press, Amsterdam, The Netherlands,
Hui Xiong , Shashi Shekhar , Pang-Ning Tan , Vipin Kumar, Exploiting a support-based upper bound of Pearson's correlation coefficient for efficiently identifying strongly correlated pairs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Yiping Ke , James Cheng , Wilfred Ng, Mining quantitative correlated patterns using an information-theoretic approach, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Sameep Mehta , Srinivasan Parthasarathy , Hui Yang, Toward Unsupervised Correlation Preserving Discretization, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1174-1185, September 2005
Yen-Liang Chen , Kwei Tang , Ren-Jie Shen , Ya-Han Hu, Market basket analysis in a multiple store environment, Decision Support Systems, v.40 n.2, p.339-354, August 2005
Antonin Rozsypal , Miroslav Kubat, Association mining in time-varying domains, Intelligent Data Analysis, v.9 n.3, p.273-288, May 2005
algorithm;knowledge discovery;data mining;optimized association rules