Association FINAL

Question 1

Association Rules interested in

Answer 1

Observing which objects occur together

Question 2

Association rules recommending or co-occur?

Answer 2

Seeing which items co-occur

Question 3

Association Rule Mining

Answer 3

Given a set of transactions, find the rules that will predict the occurrence of an item based on the occurrences of other items in the transaction

Question 4

Does implications mean casuality?

Answer 4

No, means co-occurrence

Question 5

{} -> {}

Answer 5

Antecedent -> Consequent

Question 6

3 types of database

Answer 6

Binary, Transaction, Vertical

Question 7

Items

Answer 7

I = {x1, x2, …, xm}

Question 8

A set X within the set of items

Answer 8

Itemset

Question 9

An itemset of cardinality k

Answer 9

k-itemset

Question 10

I^(k)

Answer 10

set of all k-itemsets

Question 11

Transaction identifiers, tids

Answer 11

T = {t1, t2, …, tn}

Question 12

t within T

Answer 12

tidset

Question 13

Transaction

Answer 13

Tuple in the form (t, X) where t is a unique transaction identifier and X is an itemset

Question 14

Support

Answer 14

The support of an itemset X in a dataset D denoted sup(X, D) is the number of transactions in D that contain X

Question 15

Relative Support

Answer 15

The relative support of X is the fraction of transactions that contain X: sup(X,D)|D|

Question 16

We use F to

Answer 16

denote the set of all itemsets

Question 17

We use F^(k)

Answer 17

to denote the set of k-itemsets

Question 18

Itemset mining problem

Answer 18

Given a minimum support threshold (minsup), find all itemsets X s.t. sup(x) >= minsup

Question 19

Frequent itemsets

Answer 19

An itemset X is frequent if sup(x) >= minsup where minsup is a user specified minimum support threshold (if minsup is fraction, then relative support is implied)

Question 20

Total possible subset

Answer 20

2^|I|

Question 21

Naive approach to generate all itemsets that are frequent

Answer 21

For all x in I:
compute support
if support >= minsup
add to list

Question 22

The brute force method

Answer 22

Explores the entire itemset search space, regardless of minsup

Question 23

Goal of Association Rule Mining

Answer 23

Given a set of transactions T, find all the rules having:
support >= minsup
confidence >= mincond

Question 24

Apriori principle

Answer 24

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

Question 25

Apriori principle 2

Answer 25

If an itemset if infrequent, then all of its supersets must be infrequent as well

Question 26

A rule is frequent if

Answer 26

the itemset XY is frequent, sup(XY) >= minsup

Question 27

A rule is strong if

Answer 27

conf >= minconf

Question 28

Rules are pruned using

Answer 28

confidence

Question 29

confidence (x->y)

Answer 29

sup(XY)/sup(x)

Question 30

Unlike support, confidence does not exhibit

Answer 30

the monotone property

Question 31

If a rule x -> y\x does not satisfy the confidence threshold, then

Answer 31

any rule x’->y\x’, where x’ within X, must not satisfy the confidence threshold as well

Question 32

What happens if misnup is too high

Answer 32

we may miss interesting low-support items ex: such items may correspond to expensive products that are rarely purchased by customers, but whose patterns are interesting to mine for the retailer

Question 33

What happens if minsup is too low

Answer 33

We get information overload: too many frequent itemsets and too many spurious rules

Question 34

How can some high confidence rules be misleading?

Answer 34

High confidence might not imply a meaningful relationship if the consequent is already common in the dataset, irrespective of the antecedent

Question 35

Confidence measure ignores

Answer 35

the support of the itemset appearing in the rule consequent

Question 36

which metric accounts for the consequent

Answer 36

lift

Question 37

lift

Answer 37

conf(x->y)/rsup(y)

Question 38

value of lift close to 1 implies

Answer 38

that the support of the rule is expected

Question 39

Good lifts, bad lifts

Answer 39

> 1, «1