代做CPSC 8650 Homework Assignment #5代做留学生SQL语言

日期：2024-04-10 07:51

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	hot dogs	Σrow
hamburgers	2000	500	2500
hambuTgeTs	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?