Association

Question 1

Define support and confidence formulas

Answer 1

Support(ABC) = o(ABC) / o(N) Confidence(AB->C) = o(ABC) / o(AB)

Question 2

What do you know about (AB->C), (A->BC), (AC->B) and (ABC -> C)

Answer 2

Top 3, numerators are all the same. Bottom, doesn’t make sense.

Question 3

Apriori Principle

Answer 3

If support of a superset is large, the subsets must be large. If a subset is small, the supersets must be small.

Question 4

Anti-monotone principle

This phenom is called what?

Use the books word and describe monotone and anti-monotone.

Answer 4

Similar if not identical to apriori, we know if we find all subsets that are “interesting”, we don’t have to worry about supersets being more interesting.

Upward closed.

Monotone: if a subset satisfies a constraint, so does supersets.

Anti-monotone: if a subset violates, so does supersets.

Question 5

How many database scans does an association using the Apriori method require?

Answer 5

Without apriori, As many as your largest k-item set. With apriori, as many as largest ‘interesting’ k-itemset.

Question 6

4 ways to Generate candidate k-itemsets.

Which require pruning?

Answer 6

1. Brute force: Generate every possible k-itemset. Prune.
2. SQL Join: Join the DB table of k-1 itemsets to itself. Join logic: first two items identical, third item different. Sounds familiar.
3. F_k-1 x F₁ : Combine each candidate k-1 item with each candidate F1 item.Avoid duplicates by ordering each set of sets into lexicographical order.Prune.
4. F_k-1 x F_k-1: Merge candidate F_k-1 sets only if thier first k-2 items are identical and the last item different.

All methods require pruning because all run the risk of generating too many candidates.

Question 7

An itemset is closed if…

An itemset is maximal if…

Answer 7

Closed: X is closed if all supersets have less support.

Closed sets will be saved. Non-closed sets can be discarded for convenience.

Maximal: X is maximal if none of its supeersets are frequent.

Question 8

Given, this list of closed frequent itemsets:

{C} = 0.3 , {A,C} = 0.2

{B,E} = 0.3 , {B,C,E} = 0.2

What do you know about:

E? EC? D? A? B?

Answer 8

E = .3

EC = .3

A = B = 0.2

D we don’t know.

Question 9

What benefit comes from knowing maximal itemsets?

Answer 9

From it, you can derive all frequent itemsets.

You don’t know their support, but you know they are “important”.

Question 10

Confidence based pruning:

Which of these do we care about?

ABC->D > threshold (pass)

ABC-D < threshhold

C->ABD > threshold

C->ABD < threshold

Answer 10

ABC->D under threshold.

We can prune all other sub-sets of ABC.

AB->CD, AC->BD, BC->AD is OUT.

Question 11

How to implement Multiple Minimum Supports?

What does this do to your monotonoisity?

Answer 11

Minimum support based on 1-itemsets.

MST(Coke) = 3%

MST(Diamonds) = 0.1%

MST(Coke, Diamonds) = min(mst(coke),mst(diamonds)) = 0.1%

Result is no longer anti-monotone.

Question 12

Give examples of constraints that are monotone and anti-monotone.

Answer 12

Sum and LessThan are anti-monotone

Question 13

What datatypes are common for attributes?

Answer 13

Boolean (binomail)

Discrete (binomial)

Integer like age

Ordinal - ordered

Question 14

Whats an eager classification method?

What is the other type, give examples of both

Answer 14

Eager methods produce the decision tree in advance.

Eager:

Hunt’s recursive decision tree algorithm.

Lazy:

Naive Bayes

Question 15

Name some preprocessing steps

Answer 15

Fusing daa from multiple sources

Cleaning: Remove duplicates and noise

Selecting relevant records

Question 16

Whats post processing

Answer 16

Usually data visualization

Verify good data, statistical measures and hypothosys testing

“Ensures only valid and useful results enter Decision Support System

Question 17

Classification Vocab.

Give descriptive terms for atttributes in classification.

Answer 17

Target variable, is sometimes called dependent variable.

The other attributes are called explanitory or independent variables.

Question 18

What are two major methods used in cluster analysis

Answer 18

K-Means: (sounds similar to genetic programming)

Hierarchical: make like a family tree

Density Method

Question 19

What is usually larger? Support ratio or Confidence Ratio?

Answer 19

Confidence always.

Support = o(ab)/Total

Confidence = o(ab)/o(a)

Question 20

Name some places where anti-monotonicity is handy

Answer 20

Obviously, apriori support counting.

Rule generation (if abc->d doesn’t satisfy, then ab->cd won’t).

Candidate generation phase for Constraints Mining

Question 21

Discuss why infrequent itemsets can be important.

Answer 21

If X+Y is infrequent, especially if minsup is very low,

That makes it likely that mixed itemsets X-Y or Y-X or -Y-X is interesting.

Question 22

Define lift, and how you screwed up the homework

Answer 22

Lift of X->Y is

sup(XY)

sup(X) *sup(Y)

There’s an exttra N in there. sup(XY)and sup(X) both have an N, so they cancel, but sup(Y) has an N.

Question 23

How is suppport and confidence effected as you go down a hirearchy,

say from Computer to Laptop to Dell

For Computer -> Printer

Answer 23

Support decreases, there are less dells out there than printers.

Confidence increases, the denominator shrinks.

Question 24

How does decreasing support threshold increase computational complexity?

Answer 24

Two ways:

You get more frequent candidates, so more counting.

You get larger itemsets, so more passes over the data.

Question 25

What 3 factors effect association computational complexity?

Answer 25

Number of items

Number of transactions

Average Transaction Width

Question 26

3 factors we use to descrbe itemset generation algorithms (and more!)

Answer 26

Complete: finds all the itemsets

Sound: finds only interesting itemsets.

Efficient. Avoids generating same itemset twice.