In the Apriori algorithm, we can use a hash tree data structure to efficiently c
ID: 3594165 • Letter: I
Question
In the Apriori algorithm, we can use a hash tree data structure to efficiently count the support of candidate itemsets. Consider the hash tree for candidate 3-itemsets shown in Figure 6.32. (a) Based on this figure, how many candidate 3-itemsets are there in total? (b) Given a transaction that contains items (2, 5, 6, 8, 9], which of the hash tree leaf nodes will be visited when finding the candidate 3-itemsets contained in the transaction? (c) Use the visited leaf nodes in part (b) to determine the candidate itemsets that are contained in the transaction (2, 5, 6, 8, 9) 1,4,7 3,6,9 2,5,8 1,4,7 3,6,9 1,4,7 3,6,9 3,6,9 11 2,5,8 1,4,7 2,5.8 2,5,8 L1 7 L5 L6 (168) 246 258 568 3,6,9 L8 L9 12 (145) 1178) 346)(356 367) (379) (689) 678) 278) 289) 1,4,7 /2,5,8 2 3 4 (127)1125(459) 1457) 158) 456) (458) (789) Figure 6.32. An example of a hash tree structure.Explanation / Answer
Amswer A
Given d items, there are 2^d possible itemsets
4
Answer B
{2,5,6,8,9}
L1,L2,L3,L9,L11
Answer C
{3,5,6} {6,8,9} and {1,2,7}