SaM - Frequent Item Set Mining

Download

Description

A program to find frequent item sets (also closed and maximal) with a split and merge algorithm (Split and Merge), which combines a depth-first traversal of the subset lattice with a horizontal transaction representation. The main strength of this algorithm is not its speed (although it is not slow, but even outperforms apriori and eclat on some data sets), but the simplicity of its structure. Basically all the work is done in one recursive function of about fairly few lines of code. In addition, it only uses a simple array as the only data structure.

Papers that describe this algorithm:

• Simple Algorithms for Frequent Item Set Mining
  Christian Borgelt
  Chapter 16 of: J. Koronacki, Z.W. Raz, S.T. Wierzchon, and J.K. Kacprzyk (eds.)
  Advances in Machine Learning II (Studies in Computational Intelligence 263), 351-369
  Springer-Verlag, Berlin, Germany 2010
  doi:10.1007/978-3-642-05179-1_16 www.springerlink.com
  simple.pdf (416 kb) simple.ps.gz (261 kb) (18 pages)
• (Approximate) Frequent Item Set Mining Made Simple with a Split and Merge Algorithm
  Christian Borgelt and Xiaomeng Wang
  Scalable Fuzzy Algorithms for Data Management and Analysis: Methods and Design, Chapter 10
  IGI Global, Hershey, PA, USA 2009
  sam.pdf (511 kb) sam.ps.gz (325 kb) (19 pages)
• SaM: A Split and Merge Algorithm for Fuzzy Frequent Item Set Mining
  Christian Borgelt and Xiaomeng Wang
  Proc. 13th Int. Fuzzy Systems Association World Congress and 6th Conf. of the European Society for Fuzzy Logic and Technology (IFSA/EUSFLAT'09, Lisbon, Portugal), 968-973
  IFSA/EUSFLAT Organization Committee, Lisbon, Portugal 2009
  ifsa_09.pdf (442 kb) ifsa_09.ps.gz (276 kb) (6 pages)

More information about frequent item set mining, implementations of other algorithms as well as test data sets can be found at the Frequent Itemset Mining Implementations Repository.