Sage Journals: Discover world-class research

Abstract

In this paper we propose a new optimization for Apriori-based association rule mining algorithms where the frequency of items can be encoded and treated in a special manner drastically increasing the efficiency of the frequent itemset mining process. An efficient algorithm, called TFI-Apriori, is developed for mining the complete set of frequent itemsets. In the preprocessing phase of the proposed algorithm, the most frequent items from the database are selected and encoded. The TFI-Apriori algorithm then takes advantage of the encoded information to decrease the number of candidate itemsets generated in the mining process, and consequently drastically reduces execution time in candidate generation and support counting phases. Experimental results on actual datasets – databases coming from applications with very frequent items – demonstrate how the proposed algorithm is an order of magnitude faster than the classical Apriori approach without any loss in generation of the complete set of frequent itemsets. Additionally, TFI-Apriori has a smaller memory requirement than the traditional Apriori-based algorithms and embedding this new optimization approach in well-known implementations of the Apriori algorithm allows reuse of existing processing flows.

Keywords

Frequent pattern mining association rule mining apriori knowledge discovery data mining

Get full access to this article

View all access options for this article.

References

Agrawal

Imielinski

and Swami

, Mining association rules between sets of items in large databases, in: Proceedings 1993 ACM SIGMOD Intl. Conf. on Management of Data, Washington, DC, May 1993, pp. 207–216.

Agrawal

and Srikant

, Fast algorithms for mining association rules, in: Proceedings 20th Intl. Conf. on Very Large Data Bases, Santiago, Chile, September 1994, pp. 487–499.

Toivonen

Vijayaraman

T.M.

Buchmann

A.P.

Mohan

and Sarda

N.L.

, Sampling large databases for association rules, in: proc. 22nd International Conference on Very Large Data Bases, 1996, 134–145.

Hipp

Güntzer

Nakhaeizadeh

, Algorithms for association rule mining – a general survey and comparison, ACM SIGKDD Explorations Newsletter 2(1) (2000), 58–64.

Savasere

Omiecinski

and Navathe

S.B.

, An Efficient Algorithm for Mining Association Rules in Large Databases, in: Proceedings of the 21th International Conference on Very Large Data Bases, 11–15 September 1995, pp. 432–444.

Brin

Motwani

Ullman

J.D.

and Tsur

, Dynamic itemset counting and implication rules for market basket data, in: Proceedings 1997 ACM SIGMOD Intl. Conf. on Management of Data, Tucson, AZ, May 1997, pp. 255–264.

Han

Pei

Yin

and Mao

, Mining frequent pattern without candidate generation: a frequent pattern tree approach, Data Mining and Knowledge Discovery 8 (2004), 53–87.

Chen

Haas

and Scheuermann

, A new two-phase sampling based algorithm for discovering association rules, in: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, 2002, pp. 462–468.

Parthasarathy

, Efficient progressive sampling for association rules, in: Proceeding of 2002 IEEE International Conference on Data Mining, 2002, pp. 354–361.

10.

Borgelt

, Efficient implementations of Apriori and éclat, in: Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI’03), volume 90 of CEUR Workshop proceedings, Melbourne, Florida, USA, 19 November 2003.

11.

Calders

and Goethals

, Mining all non-derivable frequent itemsets, in: Proc. Principles and Practice of Knowledge Discovery in Databases PKDD’02, volume 2431 of LNAI, Helsinki, FIN, Aug. 2002, Springer-Verlag, pp. 74–85.

12.

de la Briandais

, File searching using variable-length keys, in: Western Joint Computer Conference, March 1959, pp. 295–298.

13.

Fredkin

, Trie memory, Communications of the ACM 3(9) (1960), 490–499.

14.

Bodon

, A Fast Apriori Implementation, IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI’03), Melbourne, Florida, USA, 2003.

15.

Bodon

, Surprising Results of Trie-based FIM Algorithm, in: Goethals

Zaki

M.J.

and Bayardo

, editors, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Vol. 90 of CEUR Workshop Proceedings, 2004.

16.

Bodon

, A Survey on Frequent Itemset Mining, Technical Report, Budapest University of Technology and Economic, 2006.

17.

Zaki

M.J.

, Scalable algorithms for association mining, IEEE Transaction on Knowledge Data Engineering 12 (2000), 372–390.

18.

Han

Cheng

Xin

and Yan

, Frequent pattern mining: current status and future directions, Data Mining and Knowledge Discovery Volume 15, 2007, 55–86.

19.

FIMI, Frequent Itemset Mining Dataset Repository, http://fimi.cs.helsinki.fi/data/.

20.

Berzal

Cubero

J.-C.

Marın

and Serrano

J.-M.

, TBAR: an efficient method for association rule mining in relational databases, Data & Knowledge Engineering 37 (2001), 47–64.

21.

Agrawal

Imielinski

and Swami

, Mining association rules between sets of items in large databases, in: Proceedings 1993 ACM SIGMOD Intl. Conf. on Management of Data, Washington, DC, May 1993, pp. 207–216.

22.

Houtsma

and Swami

, Set-oriented data mining in relational databases, Data & Knowledge Engineering 17(3) (December 1995), 245–262.

23.

Bodon

and R’onyai

, Trie: An alternative data structure for data mining algorithms, Mathematical and Computer Modelling 38(7) (October 2003), 739–751(13).

24.

Park

J.S.

Chen

M.-S.

and Yu

P.S.

, Using a Hash-Based Method with Transaction Trimming for Mining Association Rules 9(5) (September 1997), 813–825.

25.

Kumar

Quinlan

J.R.

Ghosh

Yang

Motoda

McLachlan

G.J.

Liu

P.S.

and Zhou

Z.-H.

, Michael Steinbach, David J. Hand, Dan Steinberg, Top 10 algorithms in data mining, Knowledge and Information Systems 14(1) (2008), 1–37.

26.

Brin

Motwani

and Silverstein

, Beyond market baskets: generalizing association rules to correlations, in: Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, 1997, pp. 265–276.

27.

Agrawal

and Srikant

, Mining sequential patterns, in: Proceedings of the 11th International Conference on Data Engineering, 1995, pp. 3–14.

28.

Srikant

and Agrawal

, Mining sequential patterns: generalizations and performance improvements, in: Proceedings of the Fifth International Conference on Extending Database Technology, 1996, pp. 3–17.

29.

Meretakis

Fragoudis

and Likothanassis

, Scalable association-based text classification, in: Proceedings of the Ninth International Conference on Information and Knowledge Management, 2000, pp. 5–11.

30.

Agarwal

R.C.

Aggarwal

C.C.

and Prasad

V.V.V.

, Depth first generation of long patterns, in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000, pp. 108–118.

31.

Burdick

Calimlim

and Gehrke

, MAFIA: a maximal frequent itemset algorithm for transactional databases, in: Proceedings of the 17th International Conference on Data Engineering, 2001, pp. 443–452.

32.

Bayardo

R.J.

, Efficiently mining long patterns from databases, in: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 1998, pp. 85–93.

33.

Pei

Han

and Mao

, CLOSET: an efficient algorithm for mining frequent closed itemsets, ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2000, pp. 11–20.

34.

Zaki

M.J.

and Hsiao

C.J.

, CHARM: an efficient algorithm for closed itemset mining, in: Proceedings of the Second SIAM International Conference on Data Mining, 2002.

35.

Tseng

F.C.

Hsu

C.C.

and Chen

, Mining frequent closed itemsets with the frequent pattern list, in: Proceedings of the IEEE International Conference on Data Mining, 2001, pp. 653–654.

36.

Tsay

Y.J.

and Chiang

J.Y.

, CBAR: an efficient method for mining association rules, Knowledge-Based Systems 18(2–3) (2005), 99–105.

37.

Dong

and Han

, BitTableFI: An efficient mining frequent itemsets algorithm, Knowledge-Based Systems 20(4) (May 2007), 329–335.

38.

Chiang

S.-W.

and Lin

J.-R.

, A new approach to mine frequent patterns using item-transformation methods, Information Systems 32(7) (November 2007), 1056–1072.

39.

Goethals

, Survey on frequent pattern mining, Technical report, Helsinki Institute for Information Technology, 2003.

40.

Bayardo

R.J.

, Efficiently mining long patterns from databases, Proceedings of ACM SIGMOD International Conference on Management of Data, ACM Press, Seattle, Washington, June 1998, pp. 85–93.

41.

Goethals

and Van den Bussche

, A priori versus a posteriori filtering of association rules, 1999 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery 1999.

42.

Lin

K.-C.

Liao

I.-E.

and Chen

Z.-S.

, An Improved frequent pattern growth method for mining association rules, Expert Systems with Applications 38 (2011), 5154–5161.

43.

Moens

Aksehirli

and Goethals

, Frequent Itemset Mining for Big Data, Universiteit Antwerpen, Belgium, IEEE Big Data, 2013.

44.

Ansari

Dastghaibifard

Keshtkaran

and Kaabi

, Distributed frequent itemset mining using trie data structure, IAENG International Journal of Computer Science 35(3) (2008), 377–381.

45.

Pyun

Yun

and Ryu

K.H.

, Efficient frequent pattern mining based on Linear Prefix tree Knowledge-Based Systems, vol. 55, 2014, pp. 125–139.

46.

Jeya Sheela

and Krishnaveni

S.H.

, A Novel Frequent Pattern Mining Approach with OTSP, 2015.

47.

Syed Kousar Niasi

and Kannan

, Multi agent Approach for Evolving Data Mining in Parallel and Distributed Systems using Genetic Algorithms and Semantic Ontology, 2014.

48.

Ansari

Sadreddini

M.H.

and Dastghaybifard

G.H.

, Distributed frequent Itemset Mining using Trie Data Structure, World Applied Sciences Journal 9(12) (2010), 1353–1358.

49.

Gole

and Tidke

, Frequent Itemset Mining for Big Data in social media using ClustBigFIM algorithm, Pervasive Computing (ICPC) 2015 International Conference on, 2015, pp. 1–6.