No Access

Efficient Mining of Frequent Itemsets and a Measure of Interest for Association Rule Mining

Kwang-Il Ahn

Department of Industrial Engineering, Hanyang University, Korea

Search for more papers by this author

and

Jae-Yearn Kim

Department of Industrial Engineering, Hanyang University, Korea

Search for more papers by this author

https://doi.org/10.1142/S0219649204000869Cited by:32 (Source: Crossref)

Abstract

Association rule mining is an important research topic in data mining. Association rule mining consists of two steps: finding frequent itemsets and then extracting interesting rules from the frequent itemsets. In the first step, efficiency is important since discovering frequent itemsets is computationally time consuming. In the second step, unbiased assessment is important for good decision making.

In this paper, we deal with both the efficiency of the mining algorithm and the measure of interest of the resulting rules. First, we present an algorithm for finding frequent itemsets that uses a vertical database. We also introduce a modified vertical data format to reduce the size of the database and an itemset reordering strategy to reduce the size of the intermediate tidsets. Second, we present a new measure to evaluate the interest of the resulting association rules. Our performance analysis shows that our proposed algorithm reduces the size of the intermediate tidsets that are generated during the mining process. The smaller tidsets make intersection operations faster. Using our interest-measuring test helps to avoid the discovery of misleading rules.

Keywords:

References

R. Agrawal, T. Imielinski and A. N. Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM-SIGMOD International Conference on Management of Data (1993) pp. 207–216. Google Scholar
R. Agrawal and R. Srikant, Fast algorithms for mining association rules in large databases, Proceedings of the 20th International Conference on Very Large Data Bases (1994) pp. 487–499. Google Scholar
R. J. Bayardo, Efficiently mining long patterns from databases, Proceedings of the 1998 ACM-SIGMOD International Conference on Management of Data (1998) pp. 85–93. Google Scholar
M. Berry and G. Linoff , Data Mining Techniques for Marketing, Sales, and Customer Support ( John Wiley & Sons, Inc , New York , 1997 ) . Google Scholar
F. Berzalet al., A new framework to assess association rules, Proceedings of the 4th International Conference on Intelligent Data Analysis (2001) pp. 95–104. Google Scholar
S. Brinet al., Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM-SIGMOD International Conference on Management of Data (1997) pp. 255–264. Google Scholar
B. Dunkel and N. Soparkar, Data organization and access for efficient data mining, Proceedings of the 15th International Conference on Data Engineering (1999) pp. 522–529. Google Scholar
J. Han, J. Pei and Y. Yin, Mining frequent patterns without candidate generation, Proceedings of the ACM-SIGMOD International Conference on Management of Data (2000) pp. 1–12. Google Scholar
C. O. Kimet al., Journal of the Korean Institute of Industrial Engineers 27(1), 30 (2001). Google Scholar
B. Liu, W. Hsu and Y. Ma, Identifying non-actionable association rules, Proceedings of the International Conference on Knowledge Discovery and Data Mining (2001) pp. 329–334. Google Scholar
B. Padmanabhan and A. Tuzhilin, Decision Support Systems 27, 303 (1999), DOI: 10.1016/S0167-9236(99)00053-6. Crossref, Web of Science, Google Scholar
B. Padmanabhan and A. Tuzhilin, Small is beautiful: Discovering the minimal set of unexpected patterns, Proceedings of the International Conference on Knowledge Discovery and Data Mining (2000) pp. 54–63. Google Scholar
J. S. Park, M. S. Chen and P. S. Yu, An effective hash based algorithm for mining association rules, Proceedings of the 1995 ACM-SIGMOD International Conference on Management of Data (1995) pp. 175–186. Google Scholar
N. Pasquieret al., Discovering frequent closed itemsets for association rules, Proceedings of the 7th International Conference on Database Theory (1999) pp. 398–416. Google Scholar
J. Pei, J. Han and R. Mao, CLOSET: An efficient algorithm for mining frequent closed itemsets, ACM-SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (2000) pp. 21–30. Google Scholar
S. Sarawagi, S. Thomas and R. Agrawal, Integrating association rule mining with relational database systems: Alternatives and implications, Proceedings of the 1998 ACM-SIGMOD International Conference on Management of Data (1998) pp. 343–354. Google Scholar
P. Shenoy, J. R. Haritsa and S. Sudarshan, Turbocharging vertical mining of large databases, Proceedings of 2000 ACM-SIGMOD International Conference on Management of Data (2000) pp. 22–23. Google Scholar
A. Silberschatz and A. Tuzhilin, On subjective measures of interestingness in knowledge discovery, Proceedings of the 1st International Conference on Knowledge Discovery and Data Mining (1995) pp. 275–281. Google Scholar
A. Silberschatz and A. Tuzhilin, IEEE Transactions on Knowledge and Data Engineering 8(6), 970 (1996), DOI: 10.1109/69.553165. Crossref, Web of Science, Google Scholar
C. Silverstein, S. Brin and R. Motwani, Data Mining and Knowledge Discovery 2(1), 39 (1998), DOI: 10.1023/A:1009713703947. Crossref, Web of Science, Google Scholar
Y. G. Sucahyo and R. P. Gopalan, CT-ITL: Efficient frequent item set mining using a compressed prefix tree with pattern growth, Proceedings of the Australasian Database Conference (2003) pp. 95–104. Google Scholar
P.-N. Tan, V. Kumar and J. Srivastava, Selecting the right interestingness measure for association patterns, Proceedings of the 8th International Conference on Knowledge Discovery and Data Mining (2002) pp. 32–41. Google Scholar
M. J. Zaki, IEEE Transactions on Knowledge and Data Engineering 12(3), 372 (2000), DOI: 10.1109/69.846291. Crossref, Web of Science, Google Scholar
M. J. Zaki and K. Gouda , Fast vertical mining using diffsets , Proceedings of the 9th International Conference on Knowledge Discovery and Data Mining ( 2003 ) . Google Scholar