CPSC 8650 Homework Assignment #5
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CPSC 8650 Homework Assignment #5
6.3. The Apriori algorithm makes use of prior knowledge of subset support properties.
(a) Prove that all nonempty subsets of a frequent itemset must also be frequent.
(b) Prove that the support of any nonempty subset s′of itemset s must be at least as great as the support of s.
(c) Given frequent itemset l and subset s of l, prove that the confidence of the rule “s ′⇒ (l - s ′)” cannot be more than the confidence of “s ⇒ (l - s)”, where s ′is a subset of s.
6.6. A database has five transactions. Let min_sup = 60% and min_conf = 80%.
|
TID |
Items_bought |
|
T100 |
{M, O, N, K, E, Y} |
|
T200 |
{D, O,N,K, E, Y} |
|
T300 |
{M, A, K, E} |
|
T400 |
{M, U, C, K, Y} |
|
T500 |
{C, O, O, K, I, E} |
a) Find all frequent itemsets using Apriori and FP-growth, respectively. Compare the efficiency of the two mining processes.
b) List all the strong association rules (with support s and confidence c) matching the following
metarule, where X is a variable representing customers, and itemi denotes variables representing items (e.g., “A”, “B”):
∀x ∈ tTansaction, buys (x, item1)^buys (x, item2) => buys (x, item3) [s, c]
6.8. A database has four transactions. Let min_sup = 60% and min_conf = 80%
|
cust_ID |
TID |
items_bought (in the form of brand-item_category) |
|
01 |
T100 |
{King’s-Crab, Sunset-Milk, Dairyland-Cheese, Best-Bread} |
|
02 |
T200 |
{Best-Cheese, Dairyland-Milk, Goldenfarm-Apple, Tasty-Pie, Wonder- Bread} |
|
01 |
T300 |
{Westcoast-Apple, Dairyland-Milk, Wonder-Bread, Tasty-Pie} |
|
03 |
T400 |
{Wonder-Bread, Sunset-Milk, Dairyland-Cheese} |
a) At the granularity of item_category (e.g., itemi could be “Milk”), for the rule template,
∀x ∈ tTansaction, buys (x, item1 )^ buys (x, item2 ) => buys (x, item3 ) [s, c],
List the frequent k-itemset for the largest k, and all the strong association rules (with their support s and confidence c) containing the frequent k-itemset for the largest k.
b) At the granularity of brand-item_category (e.g., itemi could be “Sunset-Milk”), for the rule template,
∀x ∈ customeT, buys (x, item1 )^ buys (x, item2 ) => buys (x, item3 ),
List the frequent k-itemset for the largest k (but do not print any rules).
6.9. Suppose that a large store has a transactional database that is distributed among four locations.
Transactions in each component database have the same format, namely Tj : {i1, . . . , im}, where Tj is a transaction identifier, and ik (1 ≤k ≤m) is the identifier of an item purchased in the transaction.
Propose an efficient algorithm to mine global association rules. You may present your algorithm in the form of an outline. Your algorithm should not require shipping all of the data to one site and should not cause excessive network communication overhead.
6.14. The following contingency table summarizes supermarket transaction data, where hot dogs refers to the transactions containing hot dogs, hot dogs refers to the transactions that do not contain hot dogs, hamburgers refers to the transactions containing hamburgers, and hambuTgeTs refers to the transactions that do not contain hanburgers.
|
|
hot dogs |
|
Σrow |
|
hamburgers |
2000 |
500 |
2500 |
|
|
1000 |
1500 |
2500 |
|
Σcol |
3000 |
2000 |
5000 |
a) Suppose that the association rule “hot dogs => hamburgers” is mined. Given a minimum support threshold of 25% and a minimum confidence threshold of 50%, is this association rule strong?
b) Based on the given data, is the purchase of hot dogs independent of the purchase of hamburgers?
If not, what kind of correlation relationship exists between the two?
2024-04-10