Data ming：Concept and Techniques.docx

Chapter?5Mining?Frequent Patterns, Associations, and Correlations5.7 Exercises1. 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 con?dence of the rule “s ? (l ? s )” cannot be more than the con?dence of “s ? (l ? s)”, where s is a subset of s. (d) A partitioning variation of Apriori subdivides the transactions of a database D into n nonoverlapping partitions. Prove that any itemset that is frequent in D must be frequent in at least one partition of D.Answer: (a) Prove that all nonempty subsets of a frequent itemset must also be frequent. Let s be a frequent itemset. Let min sup be the minimum support. Let D be the task-relevant?data, a set of database transactions. Let |D| be the number of transactions in D. Since s is a frequent itemset support count(s) = min sup × |D|. Let s be any nonempty subset of s. Then any transaction containing itemset s will also contain itemset s . Therefore, support count(s’) ≥ support count(s) = min sup×|D|. Thus, s is also a frequent itemset. (b) Prove that the support of any nonempty subset s of itemset s must be as great as the support of s. Let D be the task-relevant?data, a set of database transactions. Let |D| be the number of transactions in D. By de?nition, support count(s) . support(s) = |D| Let s be any nonempty subset of s. By de?nition, support(s’) = support count(s’)|D|From part (a) we know that support(s ) ≥ support(s). This proves that the support of any nonempty subset s of itemset s must be as great as the support of s. (c) Given frequent itemset l and subset s of l, prove that the con?dence of the rule “s ? (l ? s )” cannot be more than the con?dence of “s ? (l ? s)”, where s is a subset of s. Let s be a subset of l. Then con?dence(s?(