Week 2

Question 1

What is a “pattern”?

Answer 1

What is a “pattern”? A structure of attributes that represents the intrinsic and important properties of data objects.

Question 2

What is a pattern in itemset data?

Answer 2

What is a pattern in itemset data? A frequent subset of items An association rule A correlation of two items

Question 3

How is a subset defined?

Answer 3

How is a subset defined? Two itemsets X1 and X2 If every item in X1 is also in X2, the X1 is a subset of X2.

Question 4

How is a superset defined?

Answer 4

How is a superset defined? Two itemsets X1 and X2 If every item in X1 is also in X2 (X1 is in X2), then X1 is a subset of X2; Therefore X2 is a superset of X1 (X2 contains X1).

Question 5

What is a Frequent Itemset?

Answer 5

What is a Frequent Itemset? A k-itemset: X = {x1, x2, …, xk} Itemset X contains exactly k items.

Question 6

How is Support defined?

Answer 6

How is Support defined? Support is the frequency of X in a dataset (database).

Question 7

What are the two types of Support?

Answer 7

What are the two types of Support? Absolute Support: the number of transactions that contain X. Relative Support: the fraction of transactions that contain X.

Question 8

What is the formal, mathematical definition of Support?

Answer 8

What is the formal, mathematical definition of Support? An itemset if frequent if its support sup(X) is no less than a threshold of min_sup.

Question 9

Support examples:

Answer 9

Support examples: if {a} appears in 4 of 5 items of an itemset, then the level of support is 0.8 or 80% if {a, b} appears in 3 of 5 items of an itemset, then the level of support is 0.6 or 60% if {a, b, c} appears in 2 of 5 items of an itemset, then the level of support is 0.4 or 40% if min_sup = 0.5 then examples 1 and 2 above are frequent whereas 3 is not.

Question 10

What is an Association rule?

Answer 10

What is an Association rule? X -> Y The Association rule is a measure of association between two itemsets.

Question 11

How is support defined for an Association?

Answer 11

How is support defined for an Association? X -> Y Support is the (marginal) probability that a transaction contains both X and Y. P( X and Y) Confidence is the conditional probability that a transaction which contains X also contains Y. P(Y | X)

Question 12

Association examples:

Answer 12

Association examples: {a} = 0.8 sup {b} = 0.8 sup {a, b} = 0.6 sup {a} -> {b}: Of the items that contain {a} how many also contain {b} (3 of 4 for example) confidence = 0.75 [0.6, 0.75] Book recommendations on Amazon are a perfect example of support and confidence.

Question 13

How do we find frequent itemsets?

Answer 13

How do we find frequent itemsets? 1. Scan every transaction in the database. 2. Enumerate the possible subsets. 3. Check whether their frequency is above the minimal support value. 4. For frequent itemsets calculate the confidence of associations.

Question 14

What is the Downward Closure Property?

Answer 14

What is the “Downward Closure Property?” A: any subset of a frequent itemset must be frequent. if {a, b, c} is frequent then {a, b} must also be frequent.

Question 15

What is the Apriori Pruning Principle?

Answer 15

What is the Apriori Pruning Principle (APP)? (Apriori: candidate generation and test) A: If any itemset is infrequent, none of its supersets need to be considered.

Question 16

Describe the Apriori Algorithm.

Answer 16

Describe the Apriori Algorithm. 1. Scan the database once to get frequent 1-itemsets. 2. Generate size k+1 candidate itemsets from length k frequent itemsets 3. Test (count) the candidate against the database. 4. Terminate when no frequent or candidate itemset can be generated.

Question 17

Apriori Algorithm Example Step 1

Answer 17

Apriori Algorithm Example Step 1 Items: {b,m,w}, {b,s,m,l}, {m,b,l}, {m,s}, {r,b,l} Minimum Support = 2 Data: {b}=4, {m}=4, {l}=3, {s}=2, {w}=1, {r}=1 Frequent 1-itemsets that meet the min_support: {b}=4, {m}=4, {l}=3, {s}=2

Question 18

Apriori Algorithm Example Step 2

Answer 18

Apriori Algorithm Example Step 2 Items: {b,m,w}, {b,s,m,l}, {m,b,l}, {m,s}, {r,b,l} Generate Candidate 2-itemsets (self-join) (nCr) {b, m}, {b, l}, {b, s}, {m, s}, {m, l}, {s, l} Rescan database for occurrences of 2-itemsets {b, m}=3, {b, s}=1, {b, l}=3, {m, s}=2, {m, l}=2, {s, l}=1 Only 4 of the 6 itemsets meet the minimum support.

Question 19

Apriori Algorithm Example Step 3

Answer 19

Apriori Algorithm Example Step 3 Items: {b,m,w}, {b,s,m,l}, {m,b,l}, {m,s}, {r,b,l} {b, m}=3, {b, l}=3, {m, s}=2, {m, l}=2 Generate Candidate 3-itemsets (self-join) (nCr) {b,m,l}, {b,m,s}, {m,s,l} Rescan database for occurrences of 3-itemsets {b,m,l}=2, {b,m,s}=1, {m,s,l}=1 One 3-itemset, the algorithm will terminate

Question 20

What are some of the challenges to the Apriori Algorithm?

Answer 20

What are some of the challenges to the Apriori Algorithm? -Needs multiple scans of the database -Huge number of candidates (most are not) -Tedious workload of counting the frequency of every candidate

Question 21

What are some of the improvements being attempted to improve the Apriori algorithm?

Answer 21

What are some of the improvements being attempted to improve the Apriori algorithm? -Reduce the number of passes on the database -Shrink the number of candidates -Sampling and approximation -Distributed counting (e.g. Map-Reduce) -See Textbook Chapters 6, 7

Question 22

What is a Closed pattern?

Answer 22

What is a Closed pattern? Closed pattern: An itemset X is closed if X is frequent and there exists no super-pattern with the same support as X. Every Max pattern is Closed but not all Closed patterns are Max.

Question 23

What is a Max pattern?

Answer 23

What is a Max pattern? Max pattern: An itemset X is a max pattern if X is frequent and there exists no super-pattern that is also frequent. Every Max pattern is Closed but not all Closed patterns are Max.

Question 24

What is the benefit of finding Closed and Max patterns?

Answer 24

What is the benefit of finding Closed and Max patterns? By searching for max and closed patterns, many shorter patterns can be eliminated as they are just subsets of longer frequent patterns.

Question 25

What is the numeric definition of Jaccard Similarity?

Answer 25

What is the numeric definition of Jaccard Similarity? J(A, B) = (number of items in the intersection of two sets) / (number of items in the union of two sets)

Question 26

What is Similarity?

Answer 26

What is Similarity? Similarity is a measure of how much two data objects are alike.

Question 27

How does Distance differ from Similarity?

Answer 27

How does Distance differ from Similarity? Distance measures the opposite; the greater the distance the greater the dissimilarity.

Question 28

When comparing two sets, how is the interesting measure of Lift calculated?

Answer 28

When comparing two sets, how is the interesting measure of Lift calculated?

P(X, Y) = joint probability

Lift = P(Y|X) / P(Y) = P(X, Y) / P(X)P(Y)

Question 29

When comparing two sets, how is Expected Count calculated?

Answer 29

When comparing two sets, how is Expected Count calculated? EC = (Row Total) * (Column Total) / (Sample Size)

Question 30

When comparing two sets, how is Chi² calculated?

Answer 30

When comparing two sets, how is Chi² calculated?

Chi2 = sum( (observed-expected)² / expected )

Question 31

What does Mutual Information inform?

Answer 31

What does Mutual Information inform?

Mutual information measures the mutual dependence between two random variables (X, Y)

Question 32

The amount of information obtained about X through observing Y comes from what field of study?

Answer 32

The amount of information obtained about X through observing Y comes from what field of study? This is one the of the classical concepts in Information Theory.

Question 33

What do Chi² and Mutual information not inform about the correlation of variables?

Answer 33

What do Chi² and Mutual information not inform about the correlation of variables? The direction of the correlation.