Association Rule Mining [Assignment ]
1. Implement Apriori and FP-growth algorithm in your preferred language ( preferably
python ). Cite any sources helpful to you for implementing the algorithms.
2. Modify the algorithms to achieve the same task (preferably with some improvement) .
Clearly mention the difference in the modified algorithm.
3. What does ‘best rules’ mean in ARM? What criterion is used to decide for the best rules?
4. Draw an enumeration tree for four items A, B, C, D?
5. The following database has five transactions in Table 1. Use Apriori algorithm to find all
the frequent item sets with minimum support 3.
Table 1
6. Answer the following questions:
a) Suppose you are given a task of finding all the association rules in a database whose
supports are between 20% and 80%, and the accuracy of the rules should be above
70%. Change the algorithm scheme of Apriori to find all the rules satisfying the
above requirement.
b) Applying your algorithm to the following dataset and presenting all the rules you
found.
Table 2
7. Compare the difference between association and classification, and discuss how can we
adapt an association algorithm to classification.
8. The following three questions are based on Table 3.
a) Use Bayes’ model to predict the final decision for the new instance (20, low, yes, fair)
b) Propose an algorithm to discretize the numerical attribute ‘age’ first and then
construct a decision tree based on information gain for the new data set.
c) Reconstruct a decision tree based on information gain ratio for the data set in Table 3.
Compare this new decision tree with the one you obtained in (b).
Table 3 (Students)
9. Consider the market basket transactions shown in Table 4.
a) What is the maximum number of association rules that can be extracted from this data
(including rules that have zero support)?
b) What is the maximum size of frequent itemsets that can be extracted (assuming
minsup > 0)?
c) Write an expression for the maximum number of size-3 itemsets that can be derived
from this data set.
d) Find an itemset (of size 2 or larger) that has the largest support.
e) Find a pair of items, a and b, such that the rules {a} −→ {b} and {b} −→ {a} have the
same confidence.
Table 4 (market-basket transactions)
