Mining Frequent Patterns with Functional Programming

Authors: Nittaya Kerdprasop, Kittisak Kerdprasop

Abstract:

Frequent patterns are patterns such as sets of features or items that appear in data frequently. Finding such frequent patterns has become an important data mining task because it reveals associations, correlations, and many other interesting relationships hidden in a dataset. Most of the proposed frequent pattern mining algorithms have been implemented with imperative programming languages such as C, Cµ, Java. The imperative paradigm is significantly inefficient when itemset is large and the frequent pattern is long. We suggest a high-level declarative style of programming using a functional language. Our supposition is that the problem of frequent pattern discovery can be efficiently and concisely implemented via a functional paradigm since pattern matching is a fundamental feature supported by most functional languages. Our frequent pattern mining implementation using the Haskell language confirms our hypothesis about conciseness of the program. The performance studies on speed and memory usage support our intuition on efficiency of functional language.

Keywords: Association, frequent pattern mining, functionalprogramming, pattern matching.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062730

References:

[1] R. Agrawal, T. Imielinski, and A. Swami, ''Mining association rules between sets of items in large databases,'' in Proc. ACM SIGMOD Int. Conf. Management of Data, 1993, pp. 207?216.
[2] R. Agrawal and R. Srikant, ''Fast algorithm for mining association rules,'' in Proc. Int. Conf. Very Large Data Bases, 1994, pp. 487-499.
[3] A. Ceglar and J. Roddick, ''Association mining,'' ACM Computing Surveys, vol. 38, no.2, 2006.
[4] J. Han and M. Kamber, Data Mining: Concepts and Techniques (2nd ed.), Morgan Kaufmann, 2006.
[5] P. Hudak, J. Fasel, and J. Peterson, ''A gentle introduction to Haskell,'' Yale University, Technical Report Yale U/DCS/RR-901, 1996.
[6] P. Jones and J. Hughes (eds.), Standard Libraries for the Haskell 98 Programming Languages. Available: http://www.haskell.org/library/.
[7] P. Shenoy, J. Haritsa, S. Sudarshan, G. Bhalotia, M. Bawa, and D. Shah, ''Turbo-charging vertical mining of large databases,'' in Proc. ACM SIGMOD Int. Conf. Management of Data, 2000, pp. 22-33.
[8] P. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining, Addison Wesley, 2005.
[9] S. Thompson, Haskell: The Craft of Functional Programming (2nd ed.), Addison Wesley, 1999.
[10] M. Zaki and K. Gouda, ''Fast vertical mining using diffsets,'' in Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2003, pp. 326-335.