6
Association Analysis:
Basic Concepts and
Algorithms
1. For each of the following questions, provide an example of an association rule
from the market basket domain that satisfies the following conditions. Also,
describe whether such rules are subjectively interesting.
(a) A rule that has high support and high confidence.
(b) A rule that has reasonably high support but low confidence.
(c) A rule that has low support and low confidence.
(d) A rule that has low support and high confidence.
2. Consider the data set shown in Table 6.1.
(a) Compute the support for itemsets {e},{b, d},and{b, d, e}by treating
each transaction ID as a market basket.
Table 6.1. Example of market basket transactions.
Customer ID Transaction ID Items Bought
10001 {a, d, e}
10024 {a, b, c, e}
(6.1)
(b) Use the results in part (a) to compute the confidence for the association
rules {b, d}−→{e}and {e}−→{b, d}. Is confidence a symmetric
measure?
Answer:
(c) Repeat part (a) by treating each customer ID as a market basket. Each
item should be treated as a binary variable (1 if an item appears in at
least one transaction bought by the customer, and 0 otherwise.)
Answer:
s({e})=4
5=0.8
5=0.8
73
(d) Use the results in part (c) to compute the confidence for the association
rules {b, d}−→{e}and {e}−→{b, d}.
Answer:
(e) Suppose s1and c1are the support and confidence values of an associa-
tion rule rwhen treating each transaction ID as a market basket. Also,
let s2and c2be the support and confidence values of rwhen treating
each customer ID as a market basket. Discuss whether there are any
relationships between s1and s2or c1and c2.
Answer:
3. (a) What is the confidence for the rules ∅−→Aand A−→ ∅ ?
Answer:
(b) Let c1,c2,andc3be the confidence values of the rules {p}−→{q},
{p}−→{q, r},and{p, r}−→{q}, respectively. If we assume that c1,
c2,andc3have different values, what are the possible relationships that
may exist among c1,c2,andc3? Which rule has the lowest confidence?
Answer:
(c) Repeat the analysis in part (b) assuming that the rules have identical
support. Which rule has the highest confidence?
Answer:
74 Chapter 6 Association Analysis
(d) Transitivity: Suppose the confidence of the rules A−→ Band B−→ C
are larger than some threshold, minconf. IsitpossiblethatA−→ C
has a confidence less than minconf?
Answer:
Yes, It depends on the support of items A,B,andC.
4. For each of the following measures, determine whether it is monotone, anti-
monotone, or non-monotone (i.e., neither monotone nor anti-monotone).
Example: Support, s=σ(X)
|T|is anti-monotone because s(X)≥
s(Y) whenever X⊂Y.
(a) A characteristic rule is a rule of the form {p}−→{q1,q
2,…,q
n},where
the rule antecedent contains only a single item. An itemset of size kcan
produce up to kcharacteristic rules. Let ζbe the minimum confidence
of all characteristic rules generated from a given itemset:
c{p1}−→{p2,p
Is ζmonotone, anti-monotone, or non-monotone?
Answer:
ζis an anti-monotone measure because
ζ({A1,A
2,··· ,A
k})≥ζ({A1,A
2,··· ,A
k,A
k+1}) (6.2)
For example, we can compare the values of ζfor {A, B}and {A, B, C}.
c(A−→ B),c(B−→ A)
75
c(A−→ BC),c(B−→ AC),c(C−→ AB)
(b) A discriminant rule is a rule of the form {p1,p
2,…,p
n}−→{q},where
the rule consequent contains only a single item. An itemset of size kcan
produce up to kdiscriminant rules. Let ηbe the minimum confidence
of all discriminant rules generated from a given itemset:
η({p1,p
2,…,p
k})=min
c{p2,p
3,…,p
k}−→{p1},…
c{p1,p
2,…p
k−1}−→{pk}
Is ηmonotone, anti-monotone, or non-monotone?
Answer:
ηis non-monotone. We can show this by comparing η({A, B}) against
η({A, B, C}).
η({A, B})=min
c(A−→ B),c(B−→ A)
=min
s(A, B)
s(A),s(A, B)
s(B)
(c) Repeat the analysis in parts (a) and (b) by replacing the min function
with a max function.
76 Chapter 6 Association Analysis
Answer:
Let
ζ′({A1,A
2,··· ,A
k})=max( c(A1−→ A2,A
3,··· ,A
k),···
c(Ak−→ A1,A
3··· ,A
k−1))
c(A−→ B),c(B−→ A)
5. Prove Equation 6.3. (Hint: First, count the number of ways to create an
itemset that forms the left hand side of the rule. Next, for each size k
itemset selected for the left-hand side, count the number of ways to choose
the remaining d−kitems to form the right-hand side of the rule.)
Answer:
Suppose there are ditems. We first choose kof the items to form the left-
hand side of the rule. There are d
kways for doing this. After selecting the
R=
d
k=1 d
kd−k
i=1 d−k
i
=
d
k=1 d
k2d−k−1
d
d
R=3
Table 6.2. Market basket transactions.
Transaction ID Items Bought
1{Milk, Beer, Diapers}
2{Bread, Butter, Milk}
3{Milk, Diapers, Cookies}
4{Bread, Butter, Cookies}
5{Beer, Cookies, Diapers}
6{Milk, Diapers, Bread, Butter}
7{Bread, Butter, Diapers}
8{Beer, Diapers}
9{Milk, Diapers, Bread, Butter}
10 {Beer, Cookies}
6. Consider the market basket transactions shown in Table 6.2.
(a) What is the maximum number of association rules that can be extracted
from this data (including rules that have zero support)?
(b) What is the maximum size of frequent itemsets that can be extracted
(assuming minsup > 0)?
(c) Write an expression for the maximum number of size-3 itemsets that
can be derived from this data set.
(d) Find an itemset (of size 2 or larger) that has the largest support.
(e) Find a pair of items, aand b, such that the rules {a}−→{b}and
{b}−→{a}have the same confidence.
7. Consider the following set of frequent 3-itemsets:
{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5},{3,4,5}.
Assume that there are only five items in the data set.
(a) List all candidate 4-itemsets obtained by a candidate generation proce-
dure using the Fk−1×F1merging strategy.
79
(b) List all candidate 4-itemsets obtained by the candidate generation pro-
cedure in Apriori.
Answer:
(c) List all candidate 4-itemsets that survive the candidate pruning step of
the Apriori algorithm.
Answer:
8. The Apriori algorithm uses a generate-and-count strategy for deriving fre-
quent itemsets. Candidate itemsets of size k+ 1 are created by joining a pair
of frequent itemsets of size k(this is known as the candidate generation step).
A candidate is discarded if any one of its subsets is found to be infrequent
during the candidate pruning step. Suppose the Apriori algorithm is applied
to the data set shown in Table 6.3 with minsup = 30%, i.e., any itemset
occurring in less than 3 transactions is considered to be infrequent.
Table 6.3. Example of market basket transactions.
Transaction ID Items Bought
1{a, b, d, e}
2{b, c, d}
3{a, b, d, e}
4{a, c, d, e}
5{b, c, d, e}
6{b, d, e}
7{c, d}
8{a, b, c}
9{a, d, e}
10 {b, d}
(a) Draw an itemset lattice representing the data set given in Table 6.3.
Label each node in the lattice with the following letter(s):
•N: If the itemset is not considered to be a candidate itemset by
the Apriori algorithm. There are two reasons for an itemset not to
be considered as a candidate itemset: (1) it is not generated at all
during the candidate generation step, or (2) it is generated during
80 Chapter 6 Association Analysis
the candidate generation step but is subsequently removed during
the candidate pruning step because one of its subsets is found to
be infrequent.
•F: If the candidate itemset is found to be frequent by the Apriori
algorithm.
•I: If the candidate itemset is found to be infrequent after support
counting.
Answer:
The lattice structure is shown below.
null
A B C D E
ABCDE
FF F F F
FIFFFFFFI
F
F
Figure 6.1. Solution.
(b) What is the percentage of frequent itemsets (with respect to all itemsets
in the lattice)?
Answer:
(c) What is the pruning ratio of the Apriori algorithm on this data set?
(Pruning ratio is defined as the percentage of itemsets not considered
to be a candidate because (1) they are not generated during candidate
generation or (2) they are pruned during the candidate pruning step.)
Answer:
81
2,5,8
1,4,7
1,4,7
1,4,73,6,9
3,6,9
3,6,9
2,5,8
2,5,8 1,4,7
3,6,9
2,5,8
L1 L5 L6 L7 L8 L9 L11 L12
(d) What is the false alarm rate (i.e, percentage of candidate itemsets that
are found to be infrequent after performing support counting)?
Answer:
9. The Apriori algorithm uses a hash tree data structure to efficiently count
the support of candidate itemsets. Consider the hash tree for candidate 3-
itemsets shown in Figure 6.2.
(a) Given a transaction that contains items {1,3,4,5,8}, which of the hash
tree leaf nodes will be visited when finding the candidates of the trans-
action?
Answer:
(b) Use the visited leaf nodes in part (b) to determine the candidate item-
sets that are contained in the transaction {1,3,4,5,8}.
Answer:
10. Consider the following set of candidate 3-itemsets:
{1,2,3},{1,2,6},{1,3,4},{2,3,4},{2,4,5},{3,4,6},{4,5,6}
82 Chapter 6 Association Analysis
(a) Construct a hash tree for the above candidate 3-itemsets. Assume the
tree uses a hash function where all odd-numbered items are hashed
to the left child of a node, while the even-numbered items are hashed
to the right child. A candidate k-itemset is inserted into the tree by
hashing on each successive item in the candidate and then following the
appropriate branch of the tree according to the hash value. Once a leaf
node is reached, the candidate is inserted based on one of the following
conditions:
Condition 1: If the depth of the leaf node is equal to k(therootis
assumed to be at depth 0), then the candidate is inserted regardless
of the number of itemsets already stored at the node.
Condition 2: If the depth of the leaf node is less than k, then the
candidate can be inserted as long as the number of itemsets stored
at the node is less than maxsize. Assume maxsize = 2 for this
question.
Condition 3: If the depth of the leaf node is less than kand the
number of itemsets stored at the node is equal to maxsize,then
the leaf node is converted into an internal node. New leaf nodes
are created as children of the old leaf node. Candidate itemsets
previously stored in the old leaf node are distributed to the children
based on their hash values. The new candidate is also hashed to
its appropriate leaf node.
Answer: