Abstract
In pattern mining, the main challenge is the exponential explosion of the set of patterns. Typically, to solve this problem, a constraint for pattern selection is introduced. One of the first constraints proposed in pattern mining is support (frequency) of a pattern in a dataset. Frequency is an anti-monotonic function, i.e., given an infrequent pattern, all its superpatterns are not frequent. However, many other constraints for pattern selection are not (anti-)monotonic, which makes it difficult to generate patterns satisfying these constraints. In this paper we introduce the notion of projection-antimonotonicity and \(\vartheta -\sum \)o\(\psi \iota \alpha \) algorithm that allows efficient generation of the best patterns for some nonmonotonic constraints. In this paper we consider stability and \(\Delta \)-measure, which are nonmonotonic constraints, and apply them to interval tuple datasets. In the experiments, we compute best interval tuple patterns w.r.t. these measures and show the advantage of our approach over postfiltering approaches.
Chapter PDF
Similar content being viewed by others
References
Vreeken, J., Tatti, N.: Interesting patterns. In: Aggarwal, C.C., Han, J. (eds.) Freq. Pattern Min., pp. 105–134. Springer International Publishing, Heildelberg (2014)
Mannila, H., Toivonen, H., Verkamo, A.I.: Efficient algorithms for discovering association rules. In: Knowl. Discov. Data Min., pp. 181–192 (1994)
Agrawal, R., Srikant, R., et al.: Fast algorithms for mining association rules. In: Proc. 20th Int. Conf. Very Large Data Bases, VLDB, Vol. 1215, pp. 487–499 (1994)
Yao, H., Hamilton, H.J.: Mining itemset utilities from transaction databases. Data Knowl. Eng. 59(3), 603–626 (2006)
Kuznetsov, S.O.: On stability of a formal concept. Ann. Math. Artif. Intell. 49(1–4), 101–115 (2007)
Roth, C., Obiedkov, S.A., Kourie, D.G.: On succinct representation of knowledge community taxonomies with formal concept analysis. Int. J. Found. Comput. Sci. 19(02), 383–404 (2008)
Webb, G.I.: Self-sufficient itemsets. ACM Trans. Knowl. Discov. Data 4(1), 1–20 (2010)
Moerchen, F., Thies, M., Ultsch, A.: Efficient mining of all margin-closed itemsets with applications in temporal knowledge discovery and classification by compression. Knowl. Inf. Syst. 29(1), 55–80 (2011)
Spyropoulou, E., De Bie, T., Boley, M.: Interesting pattern mining in multi-relational data. Data Min. Knowl. Discov., 1–42 (April 2013)
Cao, J., Wu, Z., Wu, J.: Scaling up cosine interesting pattern discovery: A depth-first method. Inf. Sci. (Ny) 266, 31–46 (2014)
Tatti, N., Moerchen, F., Calders, T.: Finding Robust Itemsets under Subsampling. ACM Trans. Database Syst. 39(3), 1–27 (2014)
Yan, X., Cheng, H., Han, J., Yu, P.S.: Mining significant graph patterns by leap search. In: Proc. 2008 ACM SIGMOD Int. Conf. Manag. Data - SIGMOD 2008, pp. 433–444. ACM Press, New York, June 2008
Han, J., Wang, J., Lu, Y., Tzvetkov, P.: Mining top-k frequent closed patterns without minimum support. In: Proceedings. 2002 IEEE Int. Conf. Data Mining, ICDM 2003, pp. 211–218 (2002)
Xin, D., Cheng, H., Yan, X., Han, J.: Extracting redundancy-aware top-k patterns. In: Proc. 12th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. - KDD 2006, p. 444. ACM Press, New York, August 2006
Webb, G.I.: Filtered-top-k association discovery. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 1(3), 183–192 (2011)
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations, 1st edn. Springer, Heildelberg (1999)
Ganter, B., Kuznetsov, S.O.: Pattern structures and their projections. In: Delugach, H.S., Stumme, G. (eds.) ICCS 2001. LNCS (LNAI), vol. 2120, pp. 129–142. Springer, Heidelberg (2001)
Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Efficient Mining of Association Rules Using Closed Itemset Lattices. Inf. Syst. 24(1), 25–46 (1999)
Kuznetsov, S.O., Samokhin, M.V.: Learning closed sets of labeled graphs for chemical applications. In: Kramer, S., Pfahringer, B. (eds.) ILP 2005. LNCS (LNAI), vol. 3625, pp. 190–208. Springer, Heidelberg (2005)
Kaytoue, M., Kuznetsov, S.O., Napoli, A.: Revisiting numerical pattern mining with formal concept analysis. In: Proc. 22nd Int. Jt. Conf. Artif. Intell. Barcelona, IJCAI 2011, Catalonia, Spain, July 16–22, 2011, pp. 1342–1347 (2011)
Yan, X., Han, J., Afshar, R.: CloSpan: mining closed sequential patterns in large databases. In: Proc. SIAM Int’l Conf. Data Min., pp. 166–177 (2003)
Kuznetsov, S.O.: On Computing the Size of a Lattice and Related Decision Problems. Order 18(4), 313–321 (2001)
Buzmakov, A., Kuznetsov, S.O., Napoli, A.: Scalable estimates of concept stability. In: Glodeanu, C.V., Kaytoue, M., Sacarea, C. (eds.) ICFCA 2014. LNCS, vol. 8478, pp. 157–172. Springer, Heidelberg (2014)
Buzmakov, A., Egho, E., Jay, N., Kuznetsov, S.O., Napoli, A., Raïssi, C.: On projections of sequential pattern structures (with an application on care trajectories). In: Proc. 10th Int. Conf. Concept Lattices Their Appl., pp. 199–208 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Buzmakov, A., Kuznetsov, S.O., Napoli, A. (2015). Fast Generation of Best Interval Patterns for Nonmonotonic Constraints. In: Appice, A., Rodrigues, P., Santos Costa, V., Gama, J., Jorge, A., Soares, C. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2015. Lecture Notes in Computer Science(), vol 9285. Springer, Cham. https://doi.org/10.1007/978-3-319-23525-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-23525-7_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23524-0
Online ISBN: 978-3-319-23525-7
eBook Packages: Computer ScienceComputer Science (R0)