Research paper 2-3 pages , Discussion

johndavid

chap5-association_analysis.pptx

Home >Computer Science homework help >Research paper 2-3 pages , Discussion

Data Mining

Chapter 5

Association Analysis: Basic Concepts

Introduction to Data Mining, 2nd Edition

Tan, Steinbach, Karpatne, Kumar

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Association Rule Mining

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

Market-Basket transactions

Example of Association Rules

{Diaper}  {Beer}, {Milk, Bread}  {Eggs,Coke}, {Beer, Bread}  {Milk},

Implication means co-occurrence, not causality!

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Definition: Frequent Itemset

Itemset

A collection of one or more items

Example: {Milk, Bread, Diaper}

k-itemset

An itemset that contains k items

Support count ()

Frequency of occurrence of an itemset

E.g. ({Milk, Bread,Diaper}) = 2

Support

Fraction of transactions that contain an itemset

E.g. s({Milk, Bread, Diaper}) = 2/5

Frequent Itemset

An itemset whose support is greater than or equal to a minsup threshold

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Definition: Association Rule

Example:

Association Rule

An implication expression of the form X  Y, where X and Y are itemsets

Example: {Milk, Diaper}  {Beer}

Rule Evaluation Metrics

Support (s)

Fraction of transactions that contain both X and Y

Confidence (c)

Measures how often items in Y appear in transactions that contain X

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Association Rule Mining Task

Given a set of transactions T, the goal of association rule mining is to find all rules having

support ≥ minsup threshold

confidence ≥ minconf threshold

Brute-force approach:

List all possible association rules

Compute the support and confidence for each rule

Prune rules that fail the minsup and minconf thresholds

 Computationally prohibitive!

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Computational Complexity

Given d unique items:

Total number of itemsets = 2d

Total number of possible association rules:

If d=6, R = 602 rules

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Mining Association Rules

Example of Rules:

{Milk,Diaper}  {Beer} (s=0.4, c=0.67) {Milk,Beer}  {Diaper} (s=0.4, c=1.0)

{Diaper,Beer}  {Milk} (s=0.4, c=0.67)

{Beer}  {Milk,Diaper} (s=0.4, c=0.67) {Diaper}  {Milk,Beer} (s=0.4, c=0.5)

{Milk}  {Diaper,Beer} (s=0.4, c=0.5)

Observations:

All the above rules are binary partitions of the same itemset: {Milk, Diaper, Beer}

Rules originating from the same itemset have identical support but can have different confidence

Thus, we may decouple the support and confidence requirements

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Mining Association Rules

Two-step approach:

Frequent Itemset Generation

Generate all itemsets whose support  minsup

Rule Generation

Generate high confidence rules from each frequent itemset, where each rule is a binary partitioning of a frequent itemset

Frequent itemset generation is still computationally expensive

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Frequent Itemset Generation

Given d items, there are 2d possible candidate itemsets

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Frequent Itemset Generation

Brute-force approach:

Each itemset in the lattice is a candidate frequent itemset

Count the support of each candidate by scanning the database

Match each transaction against every candidate

Complexity ~ O(NMw) => Expensive since M = 2d !!!

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Frequent Itemset Generation Strategies

Reduce the number of candidates (M)

Complete search: M=2d

Use pruning techniques to reduce M

Reduce the number of transactions (N)

Reduce size of N as the size of itemset increases

Used by DHP and vertical-based mining algorithms

Reduce the number of comparisons (NM)

Use efficient data structures to store the candidates or transactions

No need to match every candidate against every transaction

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Reducing Number of Candidates

Apriori principle:

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

Apriori principle holds due to the following property of the support measure:

Support of an itemset never exceeds the support of its subsets

This is known as the anti-monotone property of support

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Found to be Infrequent

Illustrating Apriori Principle

Pruned supersets

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Illustrating Apriori Principle

Minimum Support = 3

Items (1-itemsets)

If every subset is considered,

6C1 + 6C2 + 6C3

6 + 15 + 20 = 41

With support-based pruning,

6 + 6 + 4 = 16

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Illustrating Apriori Principle

Minimum Support = 3

If every subset is considered,

6C1 + 6C2 + 6C3

6 + 15 + 20 = 41

With support-based pruning,

6 + 6 + 4 = 16

Items (1-itemsets)

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Illustrating Apriori Principle

Items (1-itemsets)

Pairs (2-itemsets)

(No need to generate candidates involving Coke or Eggs)

Minimum Support = 3

If every subset is considered,

6C1 + 6C2 + 6C3

6 + 15 + 20 = 41

With support-based pruning,

6 + 6 + 4 = 16

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Illustrating Apriori Principle

Items (1-itemsets)

Pairs (2-itemsets)

(No need to generate candidates involving Coke or Eggs)

Minimum Support = 3

If every subset is considered,

6C1 + 6C2 + 6C3

6 + 15 + 20 = 41

With support-based pruning,

6 + 6 + 4 = 16

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Illustrating Apriori Principle

Items (1-itemsets)

Pairs (2-itemsets)

(No need to generate candidates involving Coke or Eggs)

Triplets (3-itemsets)

Minimum Support = 3

If every subset is considered,

6C1 + 6C2 + 6C3

6 + 15 + 20 = 41

With support-based pruning,

6 + 6 + 4 = 16

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Illustrating Apriori Principle

Items (1-itemsets)

Pairs (2-itemsets)

(No need to generate candidates involving Coke or Eggs)

Triplets (3-itemsets)

Minimum Support = 3

If every subset is considered,

6C1 + 6C2 + 6C3

6 + 15 + 20 = 41

With support-based pruning,

6 + 6 + 4 = 16

6 + 6 + 1 = 13

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Apriori Algorithm

Fk: frequent k-itemsets

Lk: candidate k-itemsets

Algorithm

Let k=1

Generate F1 = {frequent 1-itemsets}

Repeat until Fk is empty

Candidate Generation: Generate Lk+1 from Fk

Candidate Pruning: Prune candidate itemsets in Lk+1 containing subsets of length k that are infrequent

Support Counting: Count the support of each candidate in Lk+1 by scanning the DB

Candidate Elimination: Eliminate candidates in Lk+1 that are infrequent, leaving only those that are frequent => Fk+1

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Candidate Generation: Brute-force method

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Candidate Generation: Merge Fk-1 and F1 itemsets

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Candidate Generation: Fk-1 x Fk-1 Method

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Candidate Generation: Fk-1 x Fk-1 Method

Merge two frequent (k-1)-itemsets if their first (k-2) items are identical

F3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE}

Merge(ABC, ABD) = ABCD

Merge(ABC, ABE) = ABCE

Merge(ABD, ABE) = ABDE

Do not merge(ABD,ACD) because they share only prefix of length 1 instead of length 2

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Candidate Pruning

Let F3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE} be the set of frequent 3-itemsets

L4 = {ABCD,ABCE,ABDE} is the set of candidate 4-itemsets generated (from previous slide)

Candidate pruning

Prune ABCE because ACE and BCE are infrequent

Prune ABDE because ADE is infrequent

After candidate pruning: L4 = {ABCD}

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Alternate Fk-1 x Fk-1 Method

Merge two frequent (k-1)-itemsets if the last (k-2) items of the first one is identical to the first (k-2) items of the second.

F3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE}

Merge(ABC, BCD) = ABCD

Merge(ABD, BDE) = ABDE

Merge(ACD, CDE) = ACDE

Merge(BCD, CDE) = BCDE

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Candidate Pruning for Alternate Fk-1 x Fk-1 Method

Let F3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE} be the set of frequent 3-itemsets

L4 = {ABCD,ABDE,ACDE,BCDE} is the set of candidate 4-itemsets generated (from previous slide)

Candidate pruning

Prune ABDE because ADE is infrequent

Prune ACDE because ACE and ADE are infrequent

Prune BCDE because BCE

After candidate pruning: L4 = {ABCD}

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Illustrating Apriori Principle

Items (1-itemsets)

Pairs (2-itemsets)

(No need to generate candidates involving Coke or Eggs)

Triplets (3-itemsets)

Minimum Support = 3

If every subset is considered,

6C1 + 6C2 + 6C3

6 + 15 + 20 = 41

With support-based pruning,

6 + 6 + 1 = 13

Use of Fk-1xFk-1 method for candidate generation results in

only one 3-itemset. This is eliminated after the support counting step.

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting of Candidate Itemsets

Scan the database of transactions to determine the support of each candidate itemset

Must match every candidate itemset against every transaction, which is an expensive operation

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting of Candidate Itemsets

To reduce number of comparisons, store the candidate itemsets in a hash structure

Instead of matching each transaction against every candidate, match it against candidates contained in the hashed buckets

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting: An Example

Suppose you have 15 candidate itemsets of length 3:

{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}

How many of these itemsets are supported by transaction (1,2,3,5,6)?

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting Using a Hash Tree

2 3 4

5 6 7

1 4 5

1 3 6

1 2 4

4 5 7

1 2 5

4 5 8

1 5 9

3 4 5

3 5 6

3 5 7

6 8 9

3 6 7

3 6 8

1,4,7

2,5,8

3,6,9

Hash function

Suppose you have 15 candidate itemsets of length 3:

{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}

You need:

Hash function

Max leaf size: max number of itemsets stored in a leaf node (if number of candidate itemsets exceeds max leaf size, split the node)

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting Using a Hash Tree

1 5 9

1 4 5

1 3 6

3 4 5

3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash Function

Candidate Hash Tree

Hash on 1, 4 or 7

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting Using a Hash Tree

1 5 9

1 4 5

1 3 6

3 4 5

3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash Function

Candidate Hash Tree

Hash on 2, 5 or 8

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting Using a Hash Tree

1 5 9

1 4 5

1 3 6

3 4 5

3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash Function

Candidate Hash Tree

Hash on 3, 6 or 9

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting Using a Hash Tree

1 5 9

1 4 5

1 3 6

3 4 5

3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1 2 3 5 6

1 +

2 3 5 6

3 5 6

2 +

5 6

3 +

1,4,7

2,5,8

3,6,9

Hash Function

transaction

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting Using a Hash Tree

1 5 9

1 4 5

1 3 6

3 4 5

3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash Function

1 2 3 5 6

3 5 6

1 2 +

5 6

1 3 +

1 5 +

3 5 6

2 +

5 6

3 +

1 +

2 3 5 6

transaction

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Support Counting Using a Hash Tree

1 5 9

1 4 5

1 3 6

3 4 5

3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash Function

1 2 3 5 6

3 5 6

1 2 +

5 6

1 3 +

1 5 +

3 5 6

2 +

5 6

3 +

1 +

2 3 5 6

transaction

Match transaction against 11 out of 15 candidates

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Rule Generation

Given a frequent itemset L, find all non-empty subsets f  L such that f  L – f satisfies the minimum confidence requirement

If {A,B,C,D} is a frequent itemset, candidate rules:

ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABC AB CD, AC  BD, AD  BC, BC AD, BD AC, CD AB,

If |L| = k, then there are 2k – 2 candidate association rules (ignoring L   and   L)

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Rule Generation

In general, confidence does not have an anti-monotone property

c(ABC D) can be larger or smaller than c(AB D)

But confidence of rules generated from the same itemset has an anti-monotone property

E.g., Suppose {A,B,C,D} is a frequent 4-itemset: c(ABC  D)  c(AB  CD)  c(A  BCD)

Confidence is anti-monotone w.r.t. number of items on the RHS of the rule

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Rule Generation for Apriori Algorithm

Lattice of rules

Pruned Rules

Low Confidence Rule

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Algorithms and Complexity

Association Analysis: Basic Concepts and Algorithms

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Factors Affecting Complexity of Apriori

Choice of minimum support threshold

lowering support threshold results in more frequent itemsets

this may increase number of candidates and max length of frequent itemsets

Dimensionality (number of items) of the data set

more space is needed to store support count of each item

if number of frequent items also increases, both computation and I/O costs may also increase

Size of database

since Apriori makes multiple passes, run time of algorithm may increase with number of transactions

Average transaction width

transaction width increases with denser data sets

This may increase max length of frequent itemsets and traversals of hash tree (number of subsets in a transaction increases with its width)

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Factors Affecting Complexity of Apriori

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Compact Representation of Frequent Itemsets

Some itemsets are redundant because they have identical support as their supersets

Number of frequent itemsets

Need a compact representation

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Maximal Frequent Itemset

Border

Infrequent Itemsets

Maximal Itemsets

An itemset is maximal frequent if it is frequent and none of its immediate supersets is frequent

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

What are the Maximal Frequent Itemsets in this Data?

Minimum support threshold = 5

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Support threshold (by count) : 5

Frequent itemsets: ?

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

Support threshold (by count) : 5

Frequent itemsets: {F}

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Support threshold (by count) : 5

Frequent itemsets: {F}

Support threshold (by count): 4

Frequent itemsets: ?

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

Support threshold (by count) : 5

Frequent itemsets: {F}

Support threshold (by count): 4

Frequent itemsets: {E}, {F}, {E,F}, {J}

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Support threshold (by count) : 5

Frequent itemsets: {F}

Support threshold (by count): 4

Frequent itemsets: {E}, {F}, {E,F}, {J}

Support threshold (by count): 3

Frequent itemsets: ?

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

Support threshold (by count) : 5

Frequent itemsets: {F}

Support threshold (by count): 4

Frequent itemsets: {E}, {F}, {E,F}, {J}

Support threshold (by count): 3

Frequent itemsets:

All subsets of {C,D,E,F} + {J}

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

Support threshold (by count) : 5

Frequent itemsets: {F}

Maximal itemsets: ?

Support threshold (by count): 4

Frequent itemsets: {E}, {F}, {E,F}, {J}

Maximal itemsets: ?

Support threshold (by count): 3

Frequent itemsets:

All subsets of {C,D,E,F} + {J}

Maximal itemsets: ?

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

Support threshold (by count) : 5

Frequent itemsets: {F}

Maximal itemsets: {F}

Support threshold (by count): 4

Frequent itemsets: {E}, {F}, {E,F}, {J}

Maximal itemsets: ?

Support threshold (by count): 3

Frequent itemsets:

All subsets of {C,D,E,F} + {J}

Maximal itemsets: ?

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

Support threshold (by count) : 5

Frequent itemsets: {F}

Maximal itemsets: {F}

Support threshold (by count): 4

Frequent itemsets: {E}, {F}, {E,F}, {J}

Maximal itemsets: {E,F}, {J}

Support threshold (by count): 3

Frequent itemsets:

All subsets of {C,D,E,F} + {J}

Maximal itemsets: ?

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

An illustrative example

Support threshold (by count) : 5

Frequent itemsets: {F}

Maximal itemsets: {F}

Support threshold (by count): 4

Frequent itemsets: {E}, {F}, {E,F}, {J}

Maximal itemsets: {E,F}, {J}

Support threshold (by count): 3

Frequent itemsets:

All subsets of {C,D,E,F} + {J}

Maximal itemsets:

{C,D,E,F}, {J}

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Another illustrative example

Support threshold (by count) : 5

Maximal itemsets: {A}, {B}, {C}

Support threshold (by count): 4

Maximal itemsets: {A,B}, {A,C},{B,C}

Support threshold (by count): 3

Maximal itemsets: {A,B,C}

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Transactions

Items

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Closed Itemset

An itemset X is closed if none of its immediate supersets has the same support as the itemset X.

X is not closed if at least one of its immediate supersets has support count as X.

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Maximal vs Closed Itemsets

Transaction Ids

Not supported by any transactions

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Maximal vs Closed Frequent Itemsets

Minimum support = 2

# Closed = 9

# Maximal = 4

Closed and maximal

Closed but not maximal

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

What are the Closed Itemsets in this Data?

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example 1

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

Itemsets	Support (counts)	Closed itemsets
{C}	3
{D}	2
{C,D}	2

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example 1

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

Itemsets	Support (counts)	Closed itemsets
{C}	3	
{D}	2
{C,D}	2	

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example 2

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

Itemsets	Support (counts)	Closed itemsets
{C}	3
{D}	2
{E}	2
{C,D}	2
{C,E}	2
{D,E}	2
{C,D,E}	2

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example 2

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

Itemsets	Support (counts)	Closed itemsets
{C}	3	
{D}	2
{E}	2
{C,D}	2
{C,E}	2
{D,E}	2
{C,D,E}	2	

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example 3

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

Closed itemsets: {C,D,E,F}, {C,F}

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example 4

	A	B	C	D	E	F	G	H	I	J
1
2
3
4
5
6
7
8
9
10

Items

Transactions

Closed itemsets: {C,D,E,F}, {C}, {F}

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Maximal vs Closed Itemsets

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example question

Given the following transaction data sets (dark cells indicate presence of an item in a transaction) and a support threshold of 20%, answer the following questions

What is the number of frequent itemsets for each dataset? Which dataset will produce the most number of frequent itemsets?

Which dataset will produce the longest frequent itemset?

Which dataset will produce frequent itemsets with highest maximum support?

Which dataset will produce frequent itemsets containing items with widely varying support levels (i.e., itemsets containing items with mixed support, ranging from 20% to more than 70%)?

What is the number of maximal frequent itemsets for each dataset? Which dataset will produce the most number of maximal frequent itemsets?

What is the number of closed frequent itemsets for each dataset? Which dataset will produce the most number of closed frequent itemsets?

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Pattern Evaluation

Association rule algorithms can produce large number of rules

Interestingness measures can be used to prune/rank the patterns

In the original formulation, support & confidence are the only measures used

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Computing Interestingness Measure

Given X  Y or {X,Y}, information needed to compute interestingness can be obtained from a contingency table

	Y	Y
X	f11	f10	f1+
X	f01	f00	fo+
	f+1	f+0	N

Contingency table

f11: support of X and Y f10: support of X and Y f01: support of X and Y f00: support of X and Y

Used to define various measures

support, confidence, Gini, entropy, etc.

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Drawback of Confidence

	Coffee	Coffee
Tea	15	5	20
Tea	75	5	80
	90	10	100

Association Rule: Tea  Coffee

Confidence  P(Coffee|Tea) = 15/20 = 0.75

Confidence > 50%, meaning people who drink tea are more likely to drink coffee than not drink coffee

So rule seems reasonable

Customers	Tea	Coffee	…
C1	0	1	…
C2	1	0	…
C3	1	1	…
C4	1	0	…
…

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Drawback of Confidence

	Coffee	Coffee
Tea	15	5	20
Tea	75	5	80
	90	10	100

Association Rule: Tea  Coffee

Confidence= P(Coffee|Tea) = 15/20 = 0.75

but P(Coffee) = 0.9, which means knowing that a person drinks tea reduces the probability that the person drinks coffee!

Note that P(Coffee|Tea) = 75/80 = 0.9375

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Measure for Association Rules

So, what kind of rules do we really want?

Confidence(X  Y) should be sufficiently high

To ensure that people who buy X will more likely buy Y than not buy Y

Confidence(X  Y) > support(Y)

Otherwise, rule will be misleading because having item X actually reduces the chance of having item Y in the same transaction

Is there any measure that capture this constraint?

Answer: Yes. There are many of them.

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Statistical Independence

The criterion confidence(X  Y) = support(Y)

is equivalent to:

P(Y|X) = P(Y)

P(X,Y) = P(X)  P(Y)

If P(X,Y) > P(X)  P(Y) : X & Y are positively correlated

If P(X,Y) < P(X)  P(Y) : X & Y are negatively correlated

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Measures that take into account statistical dependence

lift is used for rules while interest is used for itemsets

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example: Lift/Interest

	Coffee	Coffee
Tea	15	5	20
Tea	75	5	80
	90	10	100

Association Rule: Tea  Coffee

Confidence= P(Coffee|Tea) = 0.75

but P(Coffee) = 0.9

Lift = 0.75/0.9= 0.8333 (< 1, therefore is negatively associated)

So, is it enough to use confidence/lift for pruning?

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Lift or Interest

	Y	Y
X	10	0	10
X	0	90	90
	10	90	100

	Y	Y
X	90	0	90
X	0	10	10
	90	10	100

Statistical independence:

If P(X,Y)=P(X)P(Y) => Lift = 1

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

There are lots of measures proposed in the literature

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Comparing Different Measures

10 examples of contingency tables:

Rankings of contingency tables using various measures:

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Property under Variable Permutation

Does M(A,B) = M(B,A)?

Symmetric measures:

support, lift, collective strength, cosine, Jaccard, etc

Asymmetric measures:

confidence, conviction, Laplace, J-measure, etc

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Property under Row/Column Scaling

	Female	Male
High	2	3	5
Low	1	4	5
	3	7	10

	Female	Male
High	4	30	34
Low	2	40	42
	6	70	76

Grade-Gender Example (Mosteller, 1968):

Mosteller: Underlying association should be independent of the relative number of male and female students in the samples

10x

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Property under Inversion Operation

Transaction 1

Transaction N

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example: -Coefficient

-coefficient is analogous to correlation coefficient for continuous variables

	Y	Y
X	60	10	70
X	10	20	30
	70	30	100

	Y	Y
X	20	10	30
X	10	60	70
	30	70	100

 Coefficient is the same for both tables

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Property under Null Addition

Invariant measures:

support, cosine, Jaccard, etc

Non-invariant measures:

correlation, Gini, mutual information, odds ratio, etc

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Different Measures have Different Properties

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Simpson’s Paradox

=> Customers who buy HDTV are more likely to buy exercise machines

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Simpson’s Paradox

Working adults:

College students:

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Simpson’s Paradox

Observed relationship in data may be influenced by the presence of other confounding factors (hidden variables)

Hidden variables may cause the observed relationship to disappear or reverse its direction!

Proper stratification is needed to avoid generating spurious patterns

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Effect of Support Distribution on Association Mining

Many real data sets have skewed support distribution

Support distribution of a retail data set

Rank of item (in log scale)

Few items with high support

Many items with low support

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Effect of Support Distribution

Difficult to set the appropriate minsup threshold

If minsup is too high, we could miss itemsets involving interesting rare items (e.g., {caviar, vodka})

If minsup is too low, it is computationally expensive and the number of itemsets is very large

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Cross-Support Patterns

milk

caviar

A cross-support pattern involves items with varying degree of support

Example: {caviar,milk}

How to avoid such patterns?

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

A Measure of Cross Support

Given an itemset,, with items, we can define a measure of cross support,r, for the itemset where ) is the support of item

Can use to prune cross support patterns, but not to avoid them

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Confidence and Cross-Support Patterns

milk

caviar

Observation:

conf(caviarmilk) is very high

but

conf(milkcaviar) is very low

Therefore,

min( conf(caviarmilk), conf(milkcaviar) ) is also very low

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

H-Confidence

To avoid patterns whose items have very different support, define a new evaluation measure for itemsets

Known as h-confidence or all-confidence

Specifically, given an itemset

h-confidence is the minimum confidence of any association rule formed from itemset

hconf( ) = min( conf(1→ 2) ), where , , For example:

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

H-Confidence …

But, given an itemset

What is the lowest confidence rule you can obtain from ?

Recall conf(→) = s() / support()

The numerator is fixed: s() = s(X )

Thus, to find the lowest confidence rule, we need to find the X1 with highest support

Consider only rules where is a single item, i.e.,

{}  – {}, {}  – {}, …, or {}  – {}

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Cross Support and H-confidence

By the anti-montone property of support

Therefore, we can derive a relationship between the h-confidence and cross support of an itemset

Thus,

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Cross Support and H-confidence …

Since, we can eliminate cross support patterns by finding patterns with h-confidence < hc, a user set threshold

Notice that

Any itemset satisfying a given h-confidence threshold, hc, is called a hyperclique

H-confidence can be used instead of or in conjunction with support

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Properties of Hypercliques

Hypercliques are itemsets, but not necessarily frequent itemsets

Good for finding low support patterns

H-confidence is anti-monotone

Can define closed and maximal hypercliques in terms of h-confidence

A hyperclique X is closed if none of its immediate supersets has the same h-confidence as X

A hyperclique X is maximal if and none of its immediate supersets, Y, have

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Properties of Hypercliques …

Hypercliques have the high-affinity property

Think of the individual items as sparse binary vectors

h-confidence gives us information about their pairwise Jaccard and cosine similarity

Assume and are any two items in an itemset X

f(X)/2

f(X)

Hypercliques that have a high h-confidence consist of very similar items as measured by Jaccard and cosine

The items in a hyperclique cannot have widely different support

Allows for more efficient pruning

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

Example Applications of Hypercliques

Hypercliques are used to find strongly coherent groups of items

Words that occur together in documents

Proteins in a protein interaction network

In the figure at the right, a gene ontology hierarchy for biological process shows that the identified proteins in the hyperclique (PRE2, …, SCL1) perform the same function and are involved in the same biological process

02/14/2018 Introduction to Data Mining, 2nd Edition ‹#›

TID Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke

4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

TID	Items
1	Bread, Milk
2	Bread, Diaper, Beer, Eggs
3	Milk, Diaper, Beer, Coke
4	Bread, Milk, Diaper, Beer
5	Bread, Milk, Diaper, Coke

TID Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke

4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

TID	Items
1	Bread, Milk
2	Bread, Diaper, Beer, Eggs
3	Milk, Diaper, Beer, Coke
4	Bread, Milk, Diaper, Beer
5	Bread, Milk, Diaper, Coke

Beer}

{

}

Diaper

Milk

{

)

Beer

Diaper,

Milk

(

)

Diaper

Milk

(

)

Beer

Diaper,

Milk,

(

TID Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke

4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

TID	Items
1	Bread, Milk
2	Bread, Diaper, Beer, Eggs
3	Milk, Diaper, Beer, Coke
4	Bread, Milk, Diaper, Beer
5	Bread, Milk, Diaper, Coke

TID Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke

4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

TID	Items
1	Bread, Milk
2	Bread, Diaper, Beer, Eggs
3	Milk, Diaper, Beer, Coke
4	Bread, Milk, Diaper, Beer
5	Bread, Milk, Diaper, Coke

null

ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

ABCD

ABCE

ABDE

ACDE

BCDE

ABCDE

TID Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke

4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

Transactions

List of

Candidates

N�

w�

M�

List of Candidates�

)

(

)

(

)

(

null

ABACADAEBCBDBECDCEDE

ABCDE

ABCABDABEACDACEADEBCDBCEBDECDE

ABCDABCEABDEACDEBCDE

ABCDE

null

ABACADAEBCBDBECDCEDE

ABCDE

ABCABDABEACDACEADEBCDBCEBDECDE

ABCDABCEABDEACDEBCDE

ABCDE

null�

AB�

AC�

AD�

AE�

BC�

BD�

BE�

CD�

CE�

DE�

ABC�

ABD�

ABE�

ACD�

ACE�

ADE�

BCD�

BCE�

BDE�

CDE�

A�

B�

C�

D�

E�

ABCD�

ABCE�

ABDE�

ACDE�

BCDE�

ABCDE�

null�

AB�

AC�

AD�

AE�

BC�

BD�

BE�

CD�

CE�

DE�

ABC�

ABD�

ABE�

ACD�

ACE�

ADE�

BCD�

BCE�

BDE�

CDE�

A�

B�

C�

D�

E�

ABCD�

ABCE�

ABDE�

ACDE�

BCDE�

ABCDE�

TID Items

1 Bread, Milk

2 Beer, Bread, Diaper, Eggs

3 Beer, Coke, Diaper, Milk

4 Beer, Bread, Diaper, Milk

5 Bread, Coke, Diaper, Milk

Item Count

Bread 4

Coke 2

Milk 4

Beer 3

Diaper 4

Eggs 1

TID	Items
1	Bread, Milk
2	Beer, Bread, Diaper, Eggs
3	Beer, Coke, Diaper, Milk
4	Beer, Bread, Diaper, Milk
5	Bread, Coke, Diaper, Milk

Item	Count
Bread	4
Coke	2
Milk	4
Beer	3
Diaper	4
Eggs	1

Item Count

Bread 4

Coke 2

Milk 4

Beer 3

Diaper 4

Eggs 1

TID	Items
1	Bread, Milk
2	Beer, Bread, Diaper, Eggs
3	Beer, Coke, Diaper, Milk
4	Beer, Bread, Diaper, Milk
5	Bread, Coke, Diaper, Milk

Item	Count
Bread	4
Coke	2
Milk	4
Beer	3
Diaper	4
Eggs	1

Item Count

Bread 4

Coke 2

Milk 4

Beer 3

Diaper 4

Eggs 1

Itemset

{Bread,Milk}

{Bread, Beer }

{Bread,Diaper}

{Beer, Milk}

{Diaper, Milk}

{Beer,Diaper}

Item	Count
Bread	4
Coke	2
Milk	4
Beer	3
Diaper	4
Eggs	1

Itemset

{Bread,Milk}

{Bread, Beer }

{Bread,Diaper}

{Beer, Milk}

{Diaper, Milk}

{Beer,Diaper}

Item Count

Bread 4

Coke 2

Milk 4

Beer 3

Diaper 4

Eggs 1

Itemset Count

{Bread,Milk} 3

{Beer, Bread} 2

{Bread,Diaper} 3

{Beer,Milk} 2

{Diaper,Milk} 3

{Beer,Diaper} 3

Item	Count
Bread	4
Coke	2
Milk	4
Beer	3
Diaper	4
Eggs	1

Itemset	Count
{Bread,Milk}	3
{Beer, Bread}	2
{Bread,Diaper}	3
{Beer,Milk}	2
{Diaper,Milk}	3
{Beer,Diaper}	3

Itemset Count

{Bread,Milk} 3

{Bread,Beer} 2

{Bread,Diaper} 3

{Milk,Beer} 2

{Milk,Diaper} 3

{Beer,Diaper} 3

Itemset

{ Beer, Diaper, Milk}

{ Beer,Bread,Diaper}

{Bread, Diaper, Milk}

{ Beer, Bread, Milk}

Item	Count
Bread	4
Coke	2
Milk	4
Beer	3
Diaper	4
Eggs	1

Itemset	Count
{Bread,Milk}	3
{Bread,Beer}	2
{Bread,Diaper}	3
{Milk,Beer}	2
{Milk,Diaper}	3
{Beer,Diaper}	3

Itemset

{ Beer, Diaper, Milk}

{ Beer,Bread,Diaper}

{Bread, Diaper, Milk}

{ Beer, Bread, Milk}

Itemset Count

{ Beer, Diaper, Milk}

{ Beer,Bread, Diaper}

{Bread, Diaper, Milk}

{Beer, Bread, Milk}

Item	Count
Bread	4
Coke	2
Milk	4
Beer	3
Diaper	4
Eggs	1

Itemset	Count
{Bread,Milk}	3
{Bread,Beer}	2
{Bread,Diaper}	3
{Milk,Beer}	2
{Milk,Diaper}	3
{Beer,Diaper}	3

Itemset

Count

{ Beer, Diaper, Milk}

{ Beer,Bread, Diaper}

{Bread, Diaper, Milk}

{Beer, Bread, Milk}

Itemset Count

{Bread, Diaper, Milk}

Item	Count
Bread	4
Coke	2
Milk	4
Beer	3
Diaper	4
Eggs	1

Itemset	Count
{Bread,Milk}	3
{Bread,Beer}	2
{Bread,Diaper}	3
{Milk,Beer}	2
{Milk,Diaper}	3
{Beer,Diaper}	3

Itemset

Count

{Bread, Diaper, Milk}

TID	Items
1	Bread, Milk
2	Beer, Bread, Diaper, Eggs
3	Beer, Coke, Diaper, Milk
4	Beer, Bread, Diaper, Milk
5	Bread, Coke, Diaper, Milk

Itemset

{ Beer, Diaper, Milk}

{ Beer,Bread,Diaper}

{Bread, Diaper, Milk}

{ Beer, Bread, Milk}

TID Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke

4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

Transactions

Hash Structure

Buckets

N�

k�

Buckets�

Hash Structure�

1 2 3 5 6

Transaction, t

2 3 5 613 5 62

5 61 33 5 61 261 55 62 362 5

5 63

1 2 3

1 2 5

1 2 6

1 3 5

1 3 6

1 5 6

2 3 5

2 3 6

2 5 63 5 6

Subsets of 3 items

Level 1

Level 2

Level 3

63 5

1 2 3 5 6�

Transaction, t�

2 3 5 6�

3 5 6�

2�

1�

5 6�

1 3�

3 5 6�

1 2�

6�

1 5�

5 6�

2 3�

6�

2 5�

5 6�

3�

1 2 3�1 2 5�1 2 6�

1 3 5�1 3 6�

1 5 6�

2 3 5�2 3 6�

2 5 6�

3 5 6�

Subsets of 3 items�

Level 1�

Level 2�

Level 3�

6�

3 5�

ABCD=>{ }

BCD=>AACD=>BABD=>CABC=>D

BC=>ADBD=>ACCD=>ABAD=>BCAC=>BDAB=>CD

D=>ABCC=>ABDB=>ACDA=>BCD

ABCD=>{ }

BCD=>AACD=>BABD=>CABC=>D

BC=>ADBD=>ACCD=>ABAD=>BCAC=>BDAB=>CD

D=>ABCC=>ABDB=>ACDA=>BCD

ABCD=>{ }�

BC=>AD�

BD=>AC�

CD=>AB�

AD=>BC�

AC=>BD�

AB=>CD�

D=>ABC�

C=>ABD�

B=>ACD�

A=>BCD�

ACD=>B�

ABD=>C�

ABC=>D�

BCD=>A�

ABCD=>{ }�

BC=>AD�

BD=>AC�

CD=>AB�

AD=>BC�

AC=>BD�

AB=>CD�

D=>ABC�

C=>ABD�

B=>ACD�

A=>BCD�

ACD=>B�

ABD=>C�

ABC=>D�

BCD=>A�

TIDA1A2A3A4A5A6A7A8A9A10B1B2B3B4B5B6B7B8B9B10C1C2C3C4C5C6C7C8C9C10

1111111111

00000000000000000000

1111111111

00000000000000000000

1111111111

00000000000000000000

1111111111

00000000000000000000

1111111111

00000000000000000000

60000000000

1111111111

0000000000

70000000000

1111111111

0000000000

80000000000

1111111111

0000000000

90000000000

1111111111

0000000000

100000000000

1111111111

0000000000

1100000000000000000000

1111111111

1200000000000000000000

1111111111

1300000000000000000000

1111111111

1400000000000000000000

1111111111

1500000000000000000000

1111111111

null

ABACADAEBCBDBECDCEDE

ABCDE

ABCABDABEACDACEADEBCDBCEBDECDE

ABCDABCEABDEACDEBCDE

ABCD

null�

AB�

AC�

AD�

AE�

BC�

BD�

BE�

CD�

CE�

DE�

ABC�

ABD�

ABE�

ACD�

ACE�

ADE�

BCD�

BCE�

BDE�

CDE�

A�

B�

C�

D�

E�

ABCD�

ABCE�

ABDE�

ACDE�

BCDE�

ABCDE�

TIDItems

1{A,B}

2{B,C,D}

3{A,B,C,D}

4{A,B,D}

5{A,B,C,D}

ItemsetSupport

{A}4

{B}5

{C}3

{D}4

{A,B}4

{A,C}2

{A,D}3

{B,C}3

{B,D}4

{C,D}3

ItemsetSupport

{A,B,C}2

{A,B,D}3

{A,C,D}2

{B,C,D}2

{A,B,C,D}2

Sheet1

	TID	Items
	1	{A,B}
	2	{B,C,D}
	3	{A,B,C,D}
	4	{A,B,D}
	5	{A,B,C,D}

Sheet2

Sheet3

Sheet1

	Itemset	Support
	{A}	4
	{B}	5
	{C}	3
	{D}	4
	{A,B}	4
	{A,C}	2
	{A,D}	3
	{B,C}	3
	{B,D}	4
	{C,D}	3

Sheet2

Sheet3

Sheet1

	Itemset	Support
	{A,B,C}	2
	{A,B,D}	3
	{A,C,D}	2
	{B,C,D}	2
	{A,B,C,D}	2

Sheet2

Sheet3

TIDItems

1ABC

2ABCD

3BCE

4ACDE

5DE

null

ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

ABCD

ABCE

ABDE

ACDE

BCDE

ABCDE

124

123

1234

245

345

124

123

Sheet1

TID	Items
1	ABC
2	ABCD
3	BCE
4	ACDE
5	DE

null

ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

ABCD

ABCE

ABDE

ACDE

BCDE

ABCDE

124

123

1234

245

345

124

123

Frequent

Itemsets

Closed

Frequent

Itemsets

Maximal

Frequent

Itemsets

Frequent Itemsets�

Closed Frequent Itemsets�

Maximal Frequent Itemsets�

)]

(

)[

(

)]

(

)[

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

coefficien

Interest

Lift

)

)(

(

Lift

)

)(

(

Lift

Example

E18123834241370

E2833026221046

E3948194127298

E43954308052961

E52886136313204431

E6150020005006000

E74000200010003000

E84000200020002000

E91720712151154

E1061248347452

Sheet1


Example
E1	8123	83	424	1370	10000	1.1581671343
E2	8330	2	622	1046	10000	1.116800672
E3	9481	94	127	298	10000	1.030581565
E4	3954	3080	5	2961	10000	1.4198707063
E5	2886	1363	1320	4431	10000	1.6148802655
E6	1500	2000	500	6000	10000	2.1428571429
E7	4000	2000	1000	3000	10000	1.3333333333
E8	4000	2000	2000	2000	10000	1.1111111111
E9	1720	7121	5	1154	10000	1.127815235
E10	61	2483	4	7452	10000	3.6889211418

Sheet2

Sheet3

(a)

(b)

(c)

5238

s + k

120

)

Yes}

Machine

Exercise

{

No}

HDTV

({

180

)

Yes}

Machine

Exercise

{

Yes}

HDTV

({

)

Yes}

Machine

Exercise

{

No}

HDTV

({

)

Yes}

Machine

Exercise

{

Yes}

HDTV

({

)

Yes}

Machine

Exercise

{

No}

HDTV

({

170

)

Yes}

Machine

Exercise

{

Yes}

HDTV

({