Solution Manual for Data Mining Chapter 6

Chapter 6 Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods 6.1 Exercises 1. Suppose you have the set C of all frequent closed itemsets on a data set D, as well as the support count for each frequent closed itemset. Describe an algorithm to determine whether a given itemset X is frequent or not, and the support of X if it is frequent. Answer: Algorithm: Itemset Freq Tester. Determine if an itemset is frequent. Input: C, set of all frequent closed itemsets along with their support counts; test itemset, X . Output: Support of X if it is frequent, otherwise -1. Method: (1) (2) (3) (4) (5) (6) (7) (8) (9) s = ∅; for each itemset, l ∈ C if X ⊂ l and (length(l) < length(s) or s = ∅) then { s = l; } if s = ∅ then { return support(s); } return -1; 2. An itemset X is called a generator on a data set D if there does not exist a proper sub-itemset Y ⊂ X such that support(X) = support(Y ). A generator X is a frequent generator if support(X) passes the minimum support threshold. Let G be the set of all frequent generators on a data set D. (a) Can you determine whether an itemset A is frequent and the support of A, if it is frequent, using only G and the support counts of all frequent generators? If yes, present your algorithm. Otherwise, what other information is needed? Can you give an algorithm assuming the information needed is available? (b) What is the relationship between closed itemsets and generators? Answer: (a) Can you determine whether an itemset A is frequent and the support of A, if it is frequent, using only G and the support counts of all frequent generators? If yes, present your algorithm. Otherwise, what other information is needed? Can you give an algorithm assuming the information needed is available? No, the frequent generators alone do not provide enough information to represent the complete set of frequent itemsets. We need information such as the ”positive border” of the frequent generators, that is, all itemsets l such that l is frequent, l is not a frequent generator, and all proper subsets of l are frequent generators. With this information we may use the following algorithm: Algorithm: InferSupport. Determine if an itemset is frequent. Input: • l is an itemset; • F G is the set of frequent generators; • P Bd(F G) is the positive border of F G; Output: Support of l if it is frequent, otherwise -1. Method: (1) if l ∈ F G or l ∈ P Bd(F G) then { (2) return support(l); (3) } else { for all l′ ⊂ l and l′ ∈ P Bd(F G) (4) (5) Let a be the item such that l′′ = l′ − {a} and l′′ ∈ F G and support(l′′ ) = support(l′ ); (6) l = l − {a}; (7) if l ∈ F G or l ∈ P Bd(F G) then { (8) return support(l); (9) } else { (10) return -1; (11) } (12) } Reference: LIU, G., LI, J., and WONG, L. 2008. A new concise representation of frequent itemsets using generators and a positive border. Knowledge and Information Systems 17, 35-56. (b) Very generally, they can be considered as opposites. This is because a closed itemset has no proper super-itemset with the same support, while a generator has no proper sub-itemset with the same support. 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. (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 definition, support count(s) support(s) = . |D| Let s′ be any nonempty subset of s. By definition, 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 confidence of the rule “s′ ⇒ (l − s′ )” cannot be more than the confidence of “s ⇒ (l − s)”, where s′ is a subset of s. support(l) Let s be a subset of l. Then confidence(s⇒(l − s)) = support(s) . Let s′ be any nonempty subset of s. Then confidence(s′ ⇒(l − s′ )) = support(l) . support(s′ ) From Part (b) we know that support(s′ ) ≥ support(s), therefore, confidence(s′ ⇒(l − s′ )) ≤ confidence(s⇒(l − s)). That is, the confidence of the rule “s′ ⇒(l − s′ )” cannot be more than the confidence of the rule “s⇒(l − 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. Any itemset that is frequent in D must be frequent in at least one partition of D. Proof by Contradiction: Assume that the itemset is not frequent in any of the partitions of D. Let F be any frequent itemset. Let D be the task-relevant data, a set of database transactions. Let C be the total number of transactions in D. Let A be the total number of transactions in D containing the itemset F . Let min sup be the minimum support. F is a frequent itemset which means that A = C × min sup. Let us partition D into n nonoverlapping partitions, d1 , d2 , d3 , . . . , dn . Then D = d1 d2 d3 . . . dn . Let c1 , c2 , c3 , . . . , cn be the total number of transactions in partitions d1 , d2 , d3 , . . . , dn , respectively. Then C = c1 + c2 + c3 + . . . + cn . Let a1 , a2 , a3 , . . . , an be the total number of transactions in partitions d1 , d2 , d3 , . . . , dn containing the itemset F, respectively. Then A = a1 + a2 + a3 + . . . + an . We can rewrite A = C × min sup as (a1 + a2 + a3 + ... + an ) = (c1 + c2 + c3 + . . . + cn ) × min sup. Because of the assumption at the start of the proof, we know that F is not frequent in any of the partitions d1 , d2 , d3 , . . . , dn of D. This means that a1 < c1 ×min sup; a2 < c2 ×min sup; a3 < c3 × min sup; . . . ; an < cn ×min sup. Adding up all of these inequalities we get (a1 +a2 +a3 +. . .+an ) < (c1 + c2 + c3 + . . . + cn ) × s or simply A < C × min sup, meaning that F is not a frequent itemset. But this is a contradiction since F was defined as a frequent itemset at the beginning of the proof. This proves that any itemset that is frequent in D must be frequent in at least one partition of D. 4. Let c be a candidate itemset in Ck generated by the Apriori algorithm. How many length-(k − 1) subsets do we need to check in the prune step? According to your answer to the above question, can you give an improved version of procedure has infrequent subset in Figure 6.4? Answer: Because c was generated from two length-(k − 1) frequent itemsets, we do not need to check these two subsets. That is, even though there are k length-(k − 1) subsets of c, we only need to check k − 2 of them. One way to push this into has infrequent subset would be to additionally pass l1 and l2 , and prevent searching Lk−1 for these because we already know they are frequent. 5. Section 6.2.2 describes a method for generating association rules from frequent itemsets. Propose a more efficient method. Explain why it is more efficient than the one proposed there. (Hint: Consider incorporating the properties of Exercise 6.3(b) and 6.3(c) into your design.) Answer: An algorithm is given in the following algorithm: An algorithm for generating strong rules from frequent itemsets. Algorithm 1 (Rule Generator) Given a set of frequent itemsets, this algorithm outputs all its strong rules. Input: l, set of frequent itemsets; minimum confidence, min conf. Output: Strong rules of itemsets in l. Method: 1) for each frequent itemset, l 2) rule generator helper(l, l, min conf); procedure rules generator helper(s: current subset of l; l: original frequent itemset; min conf) 1) k = length(s); 2) if (k > 1) then { 4) Generate all the (k − 1)-subsets of s; 5) for each (k − 1)-subset x of s 6) if (support count(l) / support count(x) = min conf) then { 7) output the rule “x⇒(l − x)”; 8) rule generator helper(x, l, min conf); 8) } 9) // else do nothing since each of x’s subsets will have at least as much // support as x, and hence never have greater confidence than x 10) } This method is more efficient than the method proposed in Section 6.2.2 because it generates and tests only necessary subsets. If a subset x of length k does not meet the minimum confidence, then there is no point in generating any of its nonempty subsets since their respective confidences will never be greater than the confidence of x (see Exercise 6.1 (b) and (c)). However, if x meets the minimum confidence then we generate and test its (k − 1)-subsets. Using this criteria, we start with the (n − 1)-subsets of an n-itemset and progressively work our way down to the 1-subsets. The method in Section 6.2.2, on the other hand, is a brute-force method that generates all the nonempty subsets of a frequent itemset l and then tests all of them for potential rules. This is inefficient because it may generate and test many unnecessary subsets (i.e., subsets whose superset did not meet the minimum confidence). Consider the following worst-case scenario: We have a k-itemset (let’s call it b) where k is very large (e.g., k = 1000). Imagine that none of b’s (k − 1)-subsets meet the minimum confidence. The method of Section 6.2.2 would still unnecessarily generate all of b’s nonempty subsets and then test all of them for potential rules. The new method, on the other hand, would only generate b’s (k − 1)-subsets. Upon determining that none of the rules from b’s (k − 1)-subsets meet the minimum confidence, it would avoid generating and testing any more subsets, thereby saving a great deal of unnecessary computation. 6. A database has 5 transactions. Let min sup = 60% and min conf = 80%. TID T100 T200 T300 T400 T500 items bought {M, O, N, K, E, Y} {D, O, N, K, E, Y } {M, A, K, E} {M, U, C, K, Y} {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 of 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”, etc.): ∀x ∈ transaction, buys(X, item1 ) ∧ buys(X, item2 ) ⇒ buys(X, item3 ) [s, c] Answer: (a) Find all frequent itemsets using Apriori and FP-growth, respectively. Compare the efficiency of the two mining processes. i. For Apriori, one finds the following frequent itemsets, and candidate itemsets (after deletion as a result of has infrequent subset): L1 = {E, K, M, O, Y} C2 = {EK, EM, EO, EY, KM, KO, KY, MO, MY, OY} L2 = {EK, EO, KM, KO, KY} C3 = {EKO} L3 = {EKO} C4 = ∅ L4 = ∅ Finally resulting in the complete set of frequent itemsets: {E, K, M, O, Y, EK, EO, KM, KO, KY, EKO} ii. For FP-growth, one finds the following: Note: CPB(item) denotes the Conditional Pattern Base of that item, and CFPT(item) denotes the Conditional FP-Tree of that item. L = {{E: 4}, {K: 4}, {M: 3}, {O: 3}, {Y: 3}} CP B(Y ) = {{E,K,M,O: 1}, {E,K,O: 1}, {K,M: 1}} CF P T (Y ) = ⟨K: 3⟩ Generates FPs: {K,Y: 3} CP B(O) = {{E,K,M: 1}, {E,K: 2}} CF P T (O) = ⟨E: 3, K: 3⟩ Generates FPs: {E,K,O: 3}, {K,O: 3}, {E,O: 3} CP B(M ) = {{E,K: 2}, {K: 1}} CF P T (M ) = ⟨K: 3⟩ Generates FPs: {K,M: 3} CP B(K) = {{E: 4}} CF P T (K) = ⟨E: 4⟩ Generates FPs: {E,K: 4} Which finally results in the complete set of frequent itemsets: { {E: 4}, {K: 4}, {M: 3}, {O: 3}, {Y: 3}, {K,Y: 3}, {E,K,O: 3}, {K,O: 3}, {E,O: 3}, {K,M: 3}, {E,K: 4} } The student should identify that FP-growth is more efficient because it is able to mine in the conditional pattern bases, which may substantially reduce the sizes of the data sets to be searched. However, when working with small data sets like the one given (especially when working by hand) the student may feel like Apriori is more ”efficient.” (b) List all of 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”, etc.): ∀x ∈ transaction, buys(X, item1 ) ∧ buys(X, item2 ) ⇒ buys(X, item3 ) The following strong association rules are found: ∀X ∈ transaction, buys(X, E)∧buys(X, O) ⇒ buys(X, K) buys(X, O) ⇒ buys(X, E) [60%, 100%] [s, c] [60%, 100%] ∀X ∈ transaction, buys(X, K)∧ 7. (Implementation project) Implement three frequent itemset mining algorithms introduced in this chapter: (1) Apriori [AS94], (2) FP-growth [HPY00], and (3) Eclat [Zak00] (mining using vertical data format), using a programming language that you are familiar with, such as C++ or Java. Compare the performance of each algorithm with various kinds of large data sets. Write a report to analyze the situations (such as data size, data distribution, minimal support threshold setting, and pattern density) where one algorithm may perform better than the others, and state why. Answer: Implementations and responses will vary by student. 8. A database has four transactions. Let min sup = 60% and min conf = 80%. cust ID 01 02 01 03 TID T100 T200 T300 T400 items bought (in the form of brand-item category) {King’s-Crab, Sunset-Milk, Dairyland-Cheese, Best-Bread} {Best-Cheese, Dairyland-Milk, Goldenfarm-Apple, Tasty-Pie, Wonder-Bread} {Westcoast-Apple, Dairyland-Milk, Wonder-Bread, Tasty-Pie} {Wonder-Bread, Sunset-Milk, Dairyland-Cheese} (a) At the granularity of item category (e.g., itemi could be “Milk”), for the following rule template, ∀X ∈ transaction, buys(X, item1 ) ∧ buys(X, item2 ) ⇒ buys(X, item3 ) [s, c] list the frequent k-itemset for the largest k, and all of 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 following rule template, ∀X ∈ customer, buys(X, item1 ) ∧ buys(X, item2 ) ⇒ buys(X, item3 ) list the frequent k-itemset for the largest k (but do not print any rules). Answer: (a) At the granularity of item category (e.g., itemi could be “Milk”), for the following rule template, ∀X ∈ transaction, buys(X, item1 ) ∧ buys(X, item2 )⇒buys(X, item3 ) [s, c] list the frequent k-itemset for the largest k and all of the strong association rules (with their support s and confidence c) containing the frequent k-itemset for the largest k . k = 3 and the frequent 3-itemset is {Bread, Milk, Cheese}. The rules are Bread ∧ Cheese ⇒ M ilk, Chees ∧ M ilk ⇒ Bread, Chees⇒M ilk ∧ Bread, [75%, 100%] [75%, 100%] [75%, 100%] (b) At the granularity of brand-item category (e.g., itemi could be “Sunset-Milk”), for the following rule template, ∀X ∈ customer, buys(X, item1 ) ∧ buys(X, item2 )⇒buys(X, item3 ) list the frequent k-itemset for the largest k. Note: do not print any rules. k = 3 and the frequent 3-itemset is {(Wheat-Bread, Dairyland-Milk, Tasty-Pie), (Wheat-Bread, Sunset-Milk, Dairyland-Cheese)}. 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. Answer: An algorithm to mine global association rules is as follows: • Find the local frequent itemsets in each store. Let C F be the union of all of the local frequent itemsets in the four stores. • In each store, find the local (absolute) support for each itemset in C F . • Now we must determine the global (absolute) support for each itemset in CF . This can be done by summing up, for each itemset, the local support of that itemset in the four stores. Doing this for each itemset in CF will give us their global supports. Itemsets whose global supports pass the support threshold are global frequent itemsets. • Derive strong association rules from the global frequent itemsets. 10. Suppose that frequent itemsets are saved for a large transactional database, DB. Discuss how to efficiently mine the (global) association rules under the same minimum support threshold, if a set of new transactions, denoted as ∆DB, is (incrementally) added in? Answer: We can treat ∆DB and DB as two partitions. • For itemsets that are frequent in DB, scan ∆DB once and add their counts to see if they are still frequent in the updated database. • For itemsets that are frequent in ∆DB but not in DB, scan DB once to add their counts to see if they are frequent in the updated DB. 11. Most frequent pattern mining algorithms consider only distinct items in a transaction. However, multiple occurrences of an item in the same shopping basket, such as four cakes and three jugs of milk, can be important in transactional data analysis. How can one mine frequent itemsets efficiently considering multiple occurrences of items? Propose modifications to the well-known algorithms, such as Apriori and FP-growth, to adapt to such a situation. Answer: When extending the Apriori algorithm to mine frequent itemsets considering multiple occurrences of items, we need to take the count value into consideration when generating frequent items and itemsets. That is, we need to treat each item with different count value as different items (e.g., A:1 and A:2, that is, A with single count or 2 counts, as different items), and check if the minimal support is met. Then we can construct frequent 2-itemsets, 3-itemsets, etc., the same way as we do in Apriori. We need to take the count into consideration when checking the generated itemsets to decide if they are indeed frequent or not. When extending the FPgrowth algorithm, we also need to take the count values into consideration when generating frequent items and itemsets. That is, when we do projected DBs, we will need to project on the itemsets where each item can be associated with different counts. Further optimization is possible in a similar way as mining closed itemsets. 12. (Implementation project) Many techniques have been proposed to further improve the performance of frequent-itemset mining algorithms. Taking FP-tree-based frequent pattern-growth algorithms (such as FP-growth) as an example, implement one of the following optimization techniques. Compare the performance of your new implementation with the unoptimized version. (a) The frequent pattern mining method of Section 6.2.4 uses an FP-tree to generate conditional pattern bases using a bottom-up projection technique, i.e., project onto the prefix path of an item p. However, one can develop a top-down projection technique, that is, project onto the suffix path of an item p in the generation of a conditional pattern-base. Design and implement such a top-down FP-tree mining method. Compare its performance with the bottom-up projection method. (b) Nodes and pointers are used uniformly in an FP-tree in the design of the FP-growth algorithm. However, such a structure may consume a lot of space when the data are sparse. One possible alternative design is to explore array-and pointer- based hybrid implementation, where a node may store multiple items when it contains no splitting point to multiple sub-branches. Develop such an implementation and compare it with the original one. (c) It is time- and space- consuming to generate numerous conditional pattern bases during patterngrowth mining. An interesting alternative is to push right the branches that have been mined for a particular item p, that is, to push them to the remaining branch(es) of the FP-tree. This is done so that fewer conditional pattern bases have to be generated and additional sharing can be explored when mining the remaining branches of the FP-tree. Design and implement such a method and conduct a performance study on it. Answer: Implementations and responses will vary by student. 13. Give a short example to show that items in a strong association rule may actually be negatively correlated. Answer: Consider the following table: B B Σcol A A Σrow 65 40 105 35 10 35 100 50 150 Let the minimum support be 40%. Let the minimum confidence be 60%. A⇒B is a strong rule because it satisfies minimum support and minimum confidence with a support of 65/150 = 43.3% and 0.433 a confidence of 65/100 = 61.9%. However, the correlation between A and B is corrA,B = 0.700×0.667 = 0.928, which is less than 1, meaning that the occurrence of A is negatively correlated with the occurrence of B . 14. The following contingency table summarizes supermarket transaction data, where hot dogs refers to the transactions containing hot dogs, hotdogs refers to the transactions that do not contain hot dogs, hamburgers refers to the transactions containing hamburgers, and hamburgers refers to the transactions that do not contain hamburgers. hamburgers hamburgers Σcol hot dogs 2000 1000 3000 hotdogs 500 1500 2000 Σrow 2500 2500 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? (c) Compare the use of the all confidence, max confidence, Kulczynski, and cosine measures with lift and correlation on the given data. Answer: (a) Suppose that the association rule “hotdogs ⇒ hamburgers” is mined. Given a minimum support threshold of 25% and a minimum confidence threshold of 50%, is this association rule strong? For the rule, support = 2000/5000 = 40%, and confidence = 2000/3000 = 66.7%. Therefore, the association rule is strong. (b) Based on the given data, is the purchase of hotdogs independent of the purchase of hamburgers? If not, what kind of correlation relationship exists between the two? corr{hotdog,hamburger} = P({hot dog, hamburger})/(P({hot dog}) P({hamburger}))=0.4/(0.5 × 0.6) = 1.33 > 1. So, the purchase of hotdogs is NOT independent of the purchase of hamburgers. There exists a POSITIVE correlation between the two. 15. (Implementation project) The DBLP data set (http://www.informatik.uni-trier.de/∼ley/db/) consists of over one million entries of research papers published in computer science conferences and journals. Among these entries, there are a good number of authors that have coauthor relationships. (a) Propose a method to efficiently mine a set of coauthor relationships that are closely correlated (e.g., often coauthoring papers together). (b) Based on the mining results and the pattern evaluation measures discussed in this chapter, discuss which measure may convincingly uncover close collaboration patterns better than others. (c) Based on the study above, develop a method that can roughly predict advisor and advisee relationships and the approximate period for such advisory supervision. Answer: Implementations and responses will vary by student. 6.2 Supplementary Exercises 1. No question is added yet