Association Analysis

Question 1

Which application areas can benefit from detecting

co-occurrence relationships?

Answer 1

Marketing: Identify items that are bought together for marketing purposes

Inventory Management: Identify parts that are often needed together for repairs to equip the repair vehicle

Usage Mining: Identify words that frequently appear together in search queries to offer auto-completion

Question 2

Describe correlation analysis and give an example which technique can be used for continuous variables and binary variables?

Answer 2

• Measure the degree of dependency between two variables

Continuous variable: Pearsons correlation coefficient
Binary variable: Phi coefficient

Value range:

1: positive correlation
0: independent variable
- 1: negative correlation

Question 3

What is the shortcoming with correlations between products in shopping baskets?

Answer 3

• Correlation can find relationships of items only between two items but not between multiple items

Question 4

What is the benefit of association analysis compared to correlations?

Answer 4

• Association analysis can find multiple item
  co-occurrence relationships (descriptive method)
• focuses on occurring items

Question 5

What can association analysis not find?

Answer 5

• Causal relationships

Question 6

What is a itemset?

Answer 6

• collection of one or more items (e.g. in a transaction)

- k-itemset: An itemset that contains k items

Question 7

Define Support count

Answer 7

• frequency of occurrence of an itemset

Question 8

Define Support

Answer 8

• fraction of transaction that contain an itemset

Question 9

Define frequent itemset

Answer 9

• an itemset whose support is >= minimal support (minsup)

Question 10

What is the difference between the rule evaluation metrics Support and Confidence?

Answer 10

X (Condition) -> Y (Consequent)
Support:
- fraction of transactions that contain both X and Y

Confidence:
- how often items in Y appear in transaction that contain X

Question 11

What are the main challenges of association analysis?

Answer 11

1) Mining associations from large amounts of data can be computationally expensive (need to apply smart pruning strategies)
2) Algorithms often discover a large number of associations (many are irrelevant or redundant, user needs to select the relevant subset)

Question 12

What is the goal of association rule mining?

Answer 12

• Find all rules that have support >= the minsup threshold and confidence >= the minconf threshold

Question 13

Explain the Brute Force Approach for Association Rule mining

Answer 13

1) List all possible association rules
2) compute support and confidence for each rule
3) remove rules that fail the threshold of minsup and minconf

Attention: Computationally prohibitive due to large number of candidates!

Question 14

What happens with rules that originate from the same itemset?

Answer 14

• The rules have the same support but can have different confidence

Question 15

Explain the two-step approach of rule generation; is this approach computationally better compared to the brute force approach?

Answer 15

1) Frequent itemset generation (all itemsets whose support >= minsup)
2) Rule generation (high confidence rules from each frequent itemset, each rule is a binary partitioning of a frequent itemset)

-> Frequent itemset generation is still computationally expensive

Question 16

What is the difference between a frequent itemset and a candidate itemset?

Answer 16

• Frequent itemset has support >= minsup

- Candidate itemset is potentially a frequent itemset (only if support is >= minsup)

Question 17

Explain the Brute Force Approach

Answer 17

• Each itemset is a candidate frequent itemset
• Count the support of each candidate by scanning the database (match each transaction against every candidate)

Complexity is O(NMw)
-> expensive because M = 2^d (d= items)

Question 18

Explain why the brute force approach is not feasible (with the example of amazon)

Answer 18

• Amazon has 10 million books
• 2^10.000.000 possible itemsets
• > Most itemsets will not be relevant (books on inuit cooking and data mining bought together)
• > Intuition for the algorithm is necessary: All itemsets containing inuit cooking are likely infrequent

Question 19

Explain the Apriori principle in regard to frequent itemsets

Answer 19

If an itemset is frequent, then all of its subsets must also be frequent

Question 20

What is the anti-monotone property of support?

Answer 20

• Support of an itemset never exceeds the support of its subsets

Question 21

How can you use the apriori principle for pruning?

Answer 21

• If an itemset is infrequent then all of its supersets must also be infrequent
• Prune supersets if an itemset that is infrequent

Question 22

Explain the Apriori Algorithm for frequent itemset generation

Answer 22

1. K=1
2. Generate frequent itemsets of length 1
3. Repeat till no new frequent itemsets are identified
4. 1 Generate length k+1 candidate itemsets from length k frequent itemsets
5. 2 Prune candidate itemsets according to apriori principle
6. 3 Count the support of each candidate (scan the DB)
7. 4 Elminate candidates that are infrequent

Question 23

Briefly state what the FP-Growth frequent itemset generation method is

Answer 23

A itemset generation algorithm that compresses data into tree structure in memory

Question 24

How can you apply the frequent itemsets in e commerce?

Answer 24

• Take the top-k frequent itemsets of size 2 that contain item A
• Rank second item according to (profit made by selling item, if you want to reduce stock of item B, knowledge about customer preferences)
• Offer special price for combination with top-ranked second item

Question 25

Briefly explain how rules a generated

Answer 25

- Given a frequent itemset, find all subsets that satisfy the minimum confidence requirement

Question 26

Explain the challenge with large number of candidate rules

Answer 26

- Frequent Itemset {A,B,C,D} - Candidate association rules: (2^k) - 2 - -> Large Number of candidate rules for large frequent itemsets - > (ignores the association rules that are empty on the condition and consequent side)

Question 27

Explain Anti-monotone confidence

Answer 27

Anti-monotone confidence = Moving items from the condition to the consequent side can't increase confidence - Generally, confidence does not have an anti-monotone property (confidence of subset can be larger or smaller than confidence of frequent itemset) - Confidence of rules generated from the same itemset have an anti monotone property (If a customer bought 3 books its likely he will buy the fourth book; if he only bought 1 book its unlikely that he will buy the three other books from the frequent itemset

Question 28

How can you efficiently prune candidate rules?

Answer 28

- By using the anti-monotone property of confidence we know that moving elements from the left to right cannot increase the confidence - If a rule with many items on the left side and one item on the right side is a low confidence rule, you can prune all rules that are a sub rule of that rule

Question 29

How can you generate candidate rules within the apriori algorithm?

Answer 29

1) Merge two rules that share the same prefix in the rule consequent (CD->AB and BD-> AC results in D->ABC) 2) Prune rule D->ABC if one of its parent rules does not have high confidence (e.g. AD->BC) Possible because: - all required information for confidence computation has been created in itemset generation - Thus, no need to scan the transaction data T any more

Question 30

How can you handle categorical attributes in association analysis?

Answer 30

- Transform categorical attributes into asymmetric binary values (new "item" for each distinct attribute value pair) attributes: color = green, color = blue, ....

Question 31

What is the issue with the transformation of categorical attributes into asymmetric binary variables?

Answer 31

- If a attribute has many possible values, many of them will have very low support potential solution: aggregate low-support attribute values - If the distribution of attribute values is highly skewed drop the highly frequent item (e.g. 95% of visitors have Buy = no so most of items will be associated with Buy = No)

Question 32

How can you handle continuous attributes for association analysis?

Answer 32

- Transform continuous attributes into binary variables with discretization (equal-width / equal-frequency binning)

Question 33

What is the issue with the discretization of continuous attributes?

Answer 33

- Size of the discretization intervals affects support & confidence - If intervals are too small -> may not have enough support - If intervals are too large -> rules may not have enough confidence

Question 34

Why do you need further interestingness measures to improve the results of an association rule?

Answer 34

- Association rule algorithms tend to produce too many rules (many are uninteresting or redundant) - Interestingness depends on application area - Interestingness measures can be used to prune or rank rules (Originally, only support & confidence were the only interestingness measures)

Question 35

In which case can confidence be misleading to get good rules?

Answer 35

- Confidence of a rule can be high - But support of the consequent can be higher - > Rule is then misleading because the condition reduces probability of > We want c(X->Y) > support (>)

Question 36

What is the lift measure?

Answer 36

Lift = c(X->Y) / s(Y) - Confidence normalized by support of consequent Interpretation: - Lift > 1 then X and > are positively correlated - Lift = 1 then X and Y are independent - Lift < 1 then X and > are negatively correlated

Question 37

For which task does the human always account for when doing association analysis?

Answer 37

- Human needs to interpret the results based on the knowledge about the application domain - Which patterns are meaninungful / surprising?