Database Storage & Design Chapter 7 Association Analysis Advanced Concepts Consider Item Given Concept Hierarchy Let Denote

110 Chapter 7 Association Analysis: Advanced Concepts

(a) Consider an item xin a given concept hierarchy. Let x1,x2,…,xk

denote the kchildren of xin the concept hierarchy. Show that s(x)≤

k

i=1 s(xi), where s(·) is the support of an item. Under what conditions

will the inequality become an equality?

Answer:

(b) Let pand qdenote a pair of items, while ˆpand ˆqare their corresponding

parents in the concept hierarchy. If s({p, q})>minsup,whichofthe

following itemsets are guaranteed to be frequent? (i) s({ˆp, q}), (ii)

s({p, ˆq}), and (iii) s({ˆp, ˆq}).

Answer:

(c) Consider the association rule {p}−→{q}. Suppose the confidence of

the rule exceeds minconf. Which of the following rules are guaranteed

to have confidence higher than minconf?(i){p}−→{ˆq}, (ii) {ˆp}−→

{q}, and (iii) {ˆp}−→{ˆq}.

Answer:

9. (a) List all the 4-subsequences contained in the following data sequence:

<{1,3}{2}{

2,3}{4}>,

assuming no timing constraints.

Answer:

<{1,3}{2}{2}><{1,3}{2}{3}>

(b) List all the 3-element subsequences contained in the data sequence for

part (a) assuming that no timing constraints are imposed.

Answer:

<{1,3}{2}{2,3}><{1,3}{2}{4}>

<{1,3}{3}{4}><{1,3}{2}{2}>

<{1,3}{2}{3}><{1,3}{2,3}{4}>

111

(c) List all the 4-subsequences contained in the data sequence for part (a)

(assuming the timing constraints are ﬂexible).

Answer:

This will include all the subsequences in part (a) as well as the following:

<{1,2,3,4}><{1,2,3}{2}>

<{1,2,3}{3}><{1,2,3}{4}>

(d) List all the 3-element subsequences contained in the data sequence for

part (a) (assuming the timing constraints are ﬂexible).

Answer:

This will include all the subsequences in part (b) as well as the following:

<{1,2,3}{2}{4}><{1,2,3}{3}{4}>

<{1,2,3}{2,3}{4}><{1,2}{2}{4}>

10. Find all the frequent subsequences with support ≥50% given the sequence

database shown in Table 7.15. Assume that there are no timing constraints

imposed on the sequences.

Answer:

<{A}>,<{B}>,<{C}>,<{D}>,<{E}>

11. (a) For each of the sequences w=<e

1e2…e

i…e

i+1 …e

last >given be-

low, determine whether they are subsequences of the sequence

<{1,2,3}{2,4}{2,4,5}{3,5}{6}>

Table 7.15. Example of event sequences generated by various sensors.

Sensor Timestamp Events

S1 1A, B

2 C

3D, E

4 C

S2 1A, B

2C, D

3 E

S3 1 B

2 A

3 B

4D, E

S4 1 C

2D, E

3 C

4 E

S5 1 B

2 A

3B, C

4A, D

subjected to the following timing constraints:

mingap = 0 (interval between last event in eiand first event

in ei+1 is >0)

maxgap = 3 (interval between first event in eiand last event

in ei+1 is ≤3)

maxspan = 5 (interval between first event in e1and last event

in elast is ≤5)

ws = 1 (time between first and last events in eiis ≤1)

•w=<{1}{2}{3}>

•w=<{1,2,3,4}{5,6}>

•w=<{2,4}{2,4}{6}>

•w=<{1}{2,4}{6}>

•w=<{1,2}{3,4}{5,6}>

(b) Determine whether each of the subsequences wgiven in the previous

question are contiguous subsequences of the following sequences s.

113

•s=<{1,2,3,4,5,6}{1,2,3,4,5,6}{1,2,3,4,5,6}>

–w=<{1}{2}{3}>

–w=<{1,2,3,4}{5,6}>

–w=<{2,4}{2,4}{6}>

–w=<{1}{2,4}{6}>

–w=<{1,2}{3,4}{5,6}>

•s=<{1,2,3,4}{1,2,3,4,5,6}{3,4,5,6}>

–w=<{1}{2}{3}>

–w=<{1,2,3,4}{5,6}>

–w=<{2,4}{2,4}{6}>

–w=<{1}{2,4}{6}>

–w=<{1,2}{3,4}{5,6}>

•s=<{1,2}{1,2,3,4}{3,4,5,6}{5,6}>

–w=<{1,2,3,4}{5,6}>

–w=<{2,4}{2,4}{6}>

–w=<{1}{2,4}{6}>

–w=<{1,2}{3,4}{5,6}>

•s=<{1,2,3}{2,3,4,5}{4,5,6}>

–w=<{1}{2}{3}>

–w=<{1,2,3,4}{5,6}>

–w=<{2,4}{2,4}{6}>

–w=<{1}{2,4}{6}>

114 Chapter 7 Association Analysis: Advanced Concepts

–w=<{1,2}{3,4}{5,6}>

12. For each of the sequence w=e1,…,e

lastbelow, determine whether they

are subsequences of the following data sequence:

{A, B}{C, D}{A, B}{C, D}{A, B}{C, D}

subjected to the following timing constraints:

mingap = 0 (interval between last event in eiand first event

in ei+1 is >0)

maxgap = 2 (interval between first event in eiand last event

in ei+1 is ≤2)

maxspan = 6 (interval between first event in e1and last event

in elast is ≤6)

ws = 1 (time between first and last events in eiis ≤1)

(a) w={A}{B}{C}{D}

(b) w={A}{B,C,D}{A}

(c) w={A}{B,C,D}{A}

(d) w={B,C}{A, D}{B, C}

(e) w={A, B, C, D}{A, B, C, D}

13. Consider the following frequent 3-sequences:

<{1,2,3}>,<{1,2}{3}>,<{1}{2,3}>,<{1,2}{4}>,

<{1,3}{4}>,<{1,2,4}>,<{2,3}{3}>,<{2,3}{4}>,

<{2}{3}{3}>,and<{2}{3}{4}>.

(a) List all the candidate 4-sequences produced by the candidate generation

step of the GSP algorithm.

Answer:

(b) List all the candidate 4-sequences pruned during the candidate pruning

step of the GSP algorithm (assuming no timing constraints).

Answer:

115

(c) List all the candidate 4-sequences pruned during the candidate pruning

step of the GSP algorithm (assuming maxgap =1).

Answer:

With timing constraint, only contiguous subsequences of a candidate

14. Consider the data sequence shown in Table 7.16 for a given object. Count

the number of occurrences for the sequence {p}{q}{r} accordingtothe

following counting methods:

Assume that ws =0,mingap =0,maxgap =3,maxspan =5).

Table 7.16. Example of event sequence data for Exercise 14.

Timestamp Events

1p, q

2 r

3 s

4p, q

5r, s

6 p

7 q, r

8 q, s

9 p

10 q, r, s

(a) COBJ (one occurrence per object).

(b) CWIN (one occurrence per sliding window).

(c) CMINWIN (number of minimal windows of occurrence).

(d) CDIST O (distinct occurrences with possibility of event-timestamp over-

lap).

116 Chapter 7 Association Analysis: Advanced Concepts

(e) CDIST (distinct occurrences with no event timestamp overlap allowed).

15. Describe the types of modifications necessary to adapt the frequent subgraph

mining algorithm to handle:

(a) Directed graphs

(b) Unlabeled graphs

(c) Acyclic graphs

(d) Disconnected graphs

For each type of graph given above, describe which step of the algorithm will

be affected (candidate generation, candidate pruning, and support counting),

and any further optimization that can help improve the efficiency of the

algorithm.

Answer:

(a) Adjacency matrix may not be symmetric, which affects candidate gen-

16. Draw all candidate subgraphs obtained from joining the pair of graphs shown

in Figure 7.2. Assume the edge-growing method is used to expand the sub-

graphs.

17. Draw all the candidate subgraphs obtained by joining the pair of graphs

shown in Figure 7.4. Assume the edge-growing method is used to expand the

subgraphs.

18. (a) If support is defined in terms of induced subgraph relationship, show

that the confidence of the rule g1−→ g2can be greater than 1 if g1and

g2are allowed to have overlapping vertex sets.

Answer:

and G3.

Consider the association rule, g2−→ g1. Using the standard definition

of confidence as the ratio between the support of g2∪g1≡g3to the

118 Chapter 7 Association Analysis: Advanced Concepts

b b

a

(b)

b b

a

b a

ac a

Figure 7.4. Graphs for Exercise 17.

b

ba b

ba

b

ba

b

aa b

a

b

bb

ba bb

bb

ba

(b) What is the time complexity needed to determine the canonical label

of a graph that contains |V|vertices?

Answer:

119

b

Subgraph support = 60%

Subgraph support = 40%

Induced subgraph support = 40%

1ae

c

e

1

G1

G5

Subgraph g1

Subgraph g2

Subgraph g3

G2

a

b

e

d

1

d

1

11

1

Graph Data Set

a

d

1

a

e

d

1

Figure 7.6. Computing the support of a subgraph from a set of graphs.

(c) The core of a subgraph can have multiple automorphisms. This will

increase the number of candidate subgraphs obtained after merging two

frequent subgraphs that share the same core. Determine the maximum

number of candidate subgraphs obtained due to automorphism of a core

of size k.

(d) Two frequent subgraphs of size kmay share multiple cores. Determine

the maximum number of cores that can be shared by the two frequent

subgraphs.

19. (a) Consider a graph mining algorithm that uses the edge-growing method

to join the two undirected and unweighted subgraphs shown in Figure

19a.

i. Draw all the distinct cores obtained when merging the two sub-

graphs.

120 Chapter 7 Association Analysis: Advanced Concepts

A A

B

A A

B

A A

A

Figure 7.7. Solution to Exercise 19.

ii. How many candidates are generated using the following core?

A A

20. The original association rule mining framework considers only presence of

items together in the same transaction. There are situations in which itemsets

that are infrequent may also be informative. For instance, the itemset TV,

DVD, ¬VCR suggests that many customers who buy TVs and DVDs do not

buy VCRs.

In this problem, you are asked to extend the association rule framework to

negative itemsets (i.e., itemsets that contain both presence and absence of

items). We will use the negation symbol (¬) to refer to absence of items.

(a) A na¨ıve way for deriving negative itemsets is to extend each transaction

to include absence of items as shown in Table 7.17.

i. Suppose the transaction database contains 1000 distinct items.

What is the total number of positive itemsets that can be gener-

121

Table 7.17. Example of numeric data set.

TID TV ¬TV DVD ¬DVD VCR ¬VCR …

1 1 0 0 1 0 1 …

2 1 0 0 1 0 1 …

ated from these items? (Note: A positive itemset does not contain

any negated items).

ii. What is the maximum number of frequent itemsets that can be

generated from these transactions? (Assume that a frequent item-

set may contain positive, negative, or both types of items)

iii. Explain why such a na¨ıve method of extending each transaction

with negative items is not practical for deriving negative itemsets.

(b) Consider the database shown in Table 7.14. What are the support and

confidence values for the following negative association rules involving

regular and diet soda?

i. ¬Regular −→ Diet.

ii. Regular −→ ¬ Diet.

iii. ¬Diet −→ Regular.

iv. Diet −→ ¬ Regular.

21. Suppose we would like to extract positive and negative itemsets from a data

set that contains ditems.

(a) Consider an approach where we introduce a new variable to represent

each negative item. With this approach, the number of items grows

from dto 2d. What is the total size of the itemset lattice, assuming

that an itemset may contain both positive and negative items of the

same variable?

(b) Assume that an itemset must contain positive or negative items of dif-

ferent variables. For example, the itemset {a, a, b, c}is invalid because

it contains both positive and negative items for variable a. What is the

total size of the itemset lattice?

Answer: d

k=1 d

kk

i=0 k

i=d

k=1 d

k2k=3

d−1.

22. For each type of pattern defined below, determine whether the support mea-

sure is monotone, anti-monotone, or non-monotone (i.e., neither monotone

nor anti-monotone) with respect to increasing itemset size.

(a) Itemsets that contain both positive and negative items such as {a, b, c, d}.

Is the support measure monotone, anti-monotone, or non-monotone

when applied to such patterns?

(b) Boolean logical patterns such as {(a ∨b∨c),d,e}, which may contain

both disjunctions and conjunctions of items. Is the support measure

monotone, anti-monotone, or non-monotone when applied to such pat-

23. Many association analysis algorithms rely on an Apriori -like approach for

finding frequent patterns. The overall structure of the algorithm is given

below.

Algorithm 7.1 Apriori-like algorithm.

1: k=1.

2: Fk={i|i∈I∧σ({i})

N≥minsup}.{Find frequent 1-patterns.}

3: repeat

4: k=k+1.

5: Ck= genCandidate(Fk−1). {Candidate Generation}

6: Ck= pruneCandidate(Ck,Fk−1). {Candidate Pruning}

7: Ck=count(Ck,D). {Support Counting}

8: Fk={c|c∈Ck∧σ(c)

N≥minsup}.{Extract frequent patterns}

9: until Fk=∅

10: Answer = Fk.

Suppose we are interested in finding boolean logical rules such as

{a∨b}−→{c, d},

which may contain both disjunctions and conjunctions of items. The corre-

sponding itemset can be written as {(a∨b),c,d}.

(a) Does the Apriori principle still hold for such itemsets?

(b) How should the candidate generation step be modified to find such

patterns?

(c) How should the candidate pruning step be modified to find such pat-

terns?

123

(d) How should the support counting step be modified to find such pat-

terns?

Answer: