How to cite this WIREs title:
WIREs Data Mining Knowl Discov

Filtered‐top‐ k association discovery

Opinion

Geoffrey I. Webb

Published Online: Apr 05 2011

DOI: 10.1002/widm.28

How to cite this article
Download citation
Contact the editor about this article
Authors: submit updates and notes
Comment on this article
Share

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Association mining has been one of the most intensively researched areas of data mining. However, direct uptake of the resulting technologies has been relatively low. This paper examines some of the reasons why the dominant paradigms in association mining have not lived up to their promise, and argues that a powerful alternative is provided by top‐k techniques coupled with appropriate statistical and other filtering. © 2011 John Wiley & Sons, Inc. WIREs Data Mining Knowl Discov 2011 1 183–192 DOI: 10.1002/widm.28

References

1 Agrawal, R,Srikant, R.%22Fast algorithms for mining association rules%22. In:Jorge, B,Bocca, MJ,Carlo, Z, eds. Proceedings of the 20th International Conference on Very Large Databases VLDB `94.Santiago, Chile: Morgan Kaufmann;1994,487–499.
2 Agresti, A.Categorical data analysis.New York: Wiley‐Interscience;2002.
3 Cohen, E,Datar, M,Fujiwara, S,Gionis, A,Indyk, P,Motwani, R,Ullman, JD,Yang, C.%22Finding interesting associations without support pruning%22.Knowledge and Data Engineering.2001, 13:64–78.
4 Webb, GI.Magnum Opus.Melbourne: GI Webb %26 Associates;2010.
5 Blackard, JA,Dean, DJ.Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables.Comput Electron Agric1999,24:131–151.
6 Piatetsky‐Shapiro, G.%22Discovery, analysis, and presentation of strong rules%22. In:Piatetsky‐Shapiro, G,Frawley, J, eds. Knowledge Discovery in Databases.Menlo Park, CA: AAAI/MIT Press;1991,229–248.
7 Silberschatz, A,Tuzhilin, A. What makes patterns interesting in knowledge discovery systems. IEEE Trans Knowledge Data Eng 1996, 8:970–974.
8 Bayardo, JRJ,Agrawal, R.Mining the most interesting rules.Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD‐99)1999:145–154.
9 Freitas, AA.On rule interestingness measures.Knowledge‐Based Syst1999, 12:309–315.
10 Klemettinen, M,Mannila, H,Ronkainen, P,Toivonen, H,Verkamo, A.Finding interesting rules from large sets of discovered association rules.Proceedings of the Third International Conference on Information and Knowledge Management1999:401–407.
11 Liu, B,Hsu, W,Chen, S,Ma Y.Analyzing the subjective interestingness of association rules.IEEE Intell Syst2000, 15:47–55.
12 Sese, J,Morishita, S.Answering the most correlated N association rules efficiently.Proceedings of the Sixth European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD`02)2002:410–422.
13 Tan, PN,Kumar, V,Srivastava, J.%22Selecting the right interestingness measure for association patterns%22.Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD‐2002).Alberta, Canada: Edmonton;2002,491–502.
14 Calders, T,Goethals, B.Non‐derivable itemset mining.Data Mining Knowledge Discov2007, 14:171–206.
15 Jaroszewicz, S,Scheffer, T,Simovici, D.Scalable pattern mining with Bayesian networks as background knowledge.Data Mining Knowledge Discov2009,18:56–100.
16 Hämäläinen, W.%22Efficient discovery of the top‐k optimal dependency rules with the Fisher`s exact test of significance%22. In:Webb, GI,Liu, B,Zhang, C,Gunopulos, D,Wu, X, eds. Proceedings of the Tenth IEEE International Conference on Data Mining. Sydney, Australia;2010,196–205.
17 Wu, T,Chen, Y,Han, J.Re‐examination of interestingness measures in pattern mining: a unified framework.Data Mining Knowledge Discov2010,21:371–397.
18 Bastide, Y,Pasquier, N,Taouil, R,Stumme, G,Lakhal, L.%22Mining minimal non‐redundant association rules using frequent closed itemsets%22.First International Conference on Computational Logic – CL 2000.Berlin: Springer‐Verlag;2000,972–986.
19 Zaki, MJ.Mining non‐redundant association rules.Data Mining Knowledge Discov2004, 9:223–248.
20 Webb, GI.%22Discovering significant rules%22. In: Ungar, L,Craven, M,Gunopulos, D,Eliassi‐Rad, T, eds.Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD‐2006. The Association for Computing Machinery;2006,434–443.
21 Webb, GI.Discovering significant patterns.Machine Learn2007, 68:1–33.
22 Webb, GI.OPUS: an efficient admissible algorithm for unordered search.J Artif Intell Res1995, 3:431–465.
23 Webb, GI.%22Efficient search for association rules%22.Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD‐2000).Boston, MA: The Association for Computing Machinery;2000, 99–107.
24 Webb, GI,Zhang, S.%22Further pruning for efficient association rule discovery%22.Proceedings of the 14th Australian Joint Conference on Artificial Intelligence.Berlin: Springer;2001,605–618.
25 Han, J,Wang, J,Lu, Y,Tzvetkov, P.Mining top‐k frequent closed patterns without minimum support.Int Conf Data Mining 2002,211–218.
26 Webb, GI,Zhang, S.%22Removing trivial associations in association rule discovery%22.Proceedings of the First International NAISO Congress on Autonomous Intelligent Systems.Geelong: NAISO Academic Press;2002.
27 Webb, GI,Zhang, S.K‐optimal rule discovery.Data Mining Knowledge Discov 2005,39–79.
28 Wang, J,Han, J,Lu, Y,Tzvetkov, P.TFP: an efficient algorithm for mining top‐k frequent closed itemsets.IEEE Trans Knowledge Data Eng 2005,652–664.
29 Fu, AWC,Renfrew, WK,Tang, J.Mining n‐most interesting itemsets.Proceedings of the 12th International Symposium on Foundations of Intelligent Systems2000,59–67.
30 Pietracaprina, A,Riondato, M,Upfal, E,Vandin, F.Mining top‐k frequent itemsets through progressive sampling.Data Mining Knowledge Discov2010,21:310–326.
31 Webb, GI.Layered critical values: a powerful direct‐adjustment approach to discovering significant patterns.Machine Learn2008, 71:307–323.
32 Holm, S.A simple sequentially rejective multiple test procedure.Scand J Stat1979, 6:65–70.
33 Megiddo, N,Srikant, R.%22Discovering predictive association rules%22.Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD‐98).Menlo Park, CA: AAAI Press;1998,27–78.
34 Gionis, A,Mannila, H,Mielikinen, T,Tsaparas, P.Assessing data mining results via swap randomization.ACM Trans Knowledge Discov Data (TKDD)2007, 1:11–32.
35 Asuncion, A,Newman, DJ.UCI machine learning repository.Irvine, California: University of California, School of Information and Computer Sciences;2010.
36 Han, J,Pei, J,Yin, Y.%22Mining frequent patterns without candidate generation%22.Proceedings 2000 ACM‐SIGMOD International Conference on Management of Data (SIGMOD`00).Dallas, TX;2000,1–12.
37 Pei, J,Han, J,Mao, R.%22CLOSET: an efficient algorithm for mining frequent closed itemsets%22.Proceedings 2000 ACM‐SIGMOD International Workshop on Data Mining and Knowledge Discovery (DMKD`00).Dallas, TX;2000,21–30.
38 Gouda, K,Zaki, MJ.%22Efficiently mining maximal frequent itemsets%22.First IEEE International Conference on Data Mining.San Jose, CA;2001,163–170.
39 Pasquier, N,Bastide, Y,Taouil, R,Lakhal, L.%22Discovering frequent closed itemsets for association rules%22.Proceedings of the Seventh International Conference on Database Theory (ICDT`99).Jerusalem, Israel;1999,398–416.
40 Zaki, MJ,Hsiao, CJ.CHARM: an efficient algorithm for closed itemset mining.Proceedings of the Second SIAM International Conference on Data Mining2002,457–473.
41 Savasere, A,Omiecinski, E,Navathe, S.%22An efficient algorithm for mining association rules in large databases%22. In:Proceedings of the 21st International Conference on Very Large Data Bases.San Francisco: Morgan Kaufmann;1995,432–444.
42 Agrawal, R,Mannila, H,Srikant, R,Toivonen, H,Verkamo, AI.%22Fast discovery of association rules%22. In: Fayyad, UM,Piatetsky‐Shapiro, G,Smyth, P,Uthurusamy, R, eds.Advances in Knowledge Discovery and Data Mining.Menlo Park, CA: AAAI Press;1996,307–328.
43 Goethals, B,Muhonen, J,Toivonen, H.Mining non‐derivable association rules.Proceedings of the Fifth SIAM International Conference on Data Mining SDM‐052005,239–249.
44 Liu, B,Hsu, W,Ma, Y.%22Identifying non‐actionable association rules%22.Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD‐2001).San Francisco, CA;2001,329–334.
45 Webb, GI.Self‐sufficient itemsets: an approach to screening potentially interesting associations between items.Trans Knowledge Discov Data.2010,3:1–3.
46 Tatti, N.Maximum entropy based significance of itemsets.Knowledge Inform Syst2008,17:57–77.
47 Tatti, N,Mampaey, M.Using background knowledge to rank itemsets.Data Mining Knowledge Discov2010,21:293–309.
48 Liu, B,Hsu, W,Ma, Y.%22Integrating classification and association rule mining%22.Proceedings of the Fourth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD‐98).New York: AAAI;1998,80–86.
49 Guha, S,Rastogi, R,Shim, K.Rock: a robust clustering algorithm for categorical attributes.Inform Syst2000,25:345–366.
50 Flach, P,Lavrac, N.%22The role of feature construction in inductive rule learning%22. In: Raedt, LD,Kramer, S, eds.Proceedings of the ICML2000 Workshop on Attribute‐Value and Relational Learning: Crossing the Boundaries.2000,1–11.

blog comments powered by Disqus

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

Article Title	Filtered‐top‐ k association discovery
* Name
* E-mail
* Note

Filtered‐top‐ k association discovery

Browse by Topic

Access to this WIREs title is by subscription only.

The latest WIREs articles in your inbox