Abstract
The paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focussed on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. As a solution, in this paper we introduce the new paradigm of pattern discovery based on Soft Constraints. Albeit simple, the proposed paradigm overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery.
Chapter PDF
Similar content being viewed by others
References
Agrawal, R., Srikant, R.: Fast Algorithms for Mining Association Rules in Large Databases. In: Proceedings of the Twentieth International Conference on Very Large Databases, VLDB 1994 (1994)
Bellone, J., Chamard, A., Pradelles, C.: Plane - an evolutive planning system for aircraft production. In: Proc. 1st Interantional Conference on Practical Applications of Prolog, PAP 1992 (1992)
Bistarelli, S.: Semirings for Soft Constraint Solving and Programming. LNCS, vol. 2962. Springer, Heidelberg (2004)
Bistarelli, S., Codognet, P., Rossi, F.: Abstracting soft constraints: Framework, properties, examples. Artificial Intelligence 139, 175–211 (2002)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Solving and Optimization. Journal of the ACM 44(2), 201–236 (1997)
Bonchi, F., Giannotti, F., Mazzanti, A., Pedreschi, D.: ExAMiner: Optimized level-wise frequent pattern mining with monotone constraints. In: Proceedings of the Third IEEE International Conference on Data Mining, ICDM 2003 (2003)
Bonchi, F., Giannotti, F., Mazzanti, A., Pedreschi, D.: ExAnte: Anticipated data reduction in constrained pattern mining. In: Lavrač, N., Gamberger, D., Todorovski, L., Blockeel, H. (eds.) PKDD 2003. LNCS (LNAI), vol. 2838, pp. 59–70. Springer, Heidelberg (2003)
Bonchi, F., Lucchese, C.: On closed constrained frequent pattern mining. In: Proceedings of the Fourth IEEE International Conference on Data Mining. ICDM 2004 (2004)
Bonchi, F., Lucchese, C.: Pushing tougher constraints in frequent pattern mining. In: Ho, T.-B., Cheung, D., Liu, H. (eds.) PAKDD 2005. LNCS (LNAI), vol. 3518, pp. 114–124. Springer, Heidelberg (2005)
Borning, A., Maher, M., Martindale, A., Wilson, M.: Constraint hierarchies and logic programming. In: Proc. 6th International Conference on Logic Programming (1989)
Bucila, C., Gehrke, J., Kifer, D., White, W.: DualMiner: A dual-pruning algorithm for itemsets with constraints. In: Proceedings of the 8th ACM International Conference on Knowledge Discovery and Data Mining, SIGKDD 2002 (2002)
Dubois, D., Fargier, H., Prade, H.: The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In: Proc. IEEE International Conference on Fuzzy Systems, pp. 1131–1136. IEEE, Los Alamitos (1993)
Freuder, E., Wallace, R.: Partial constraint satisfaction. AI Journal 58 (1992)
Frühwirth, T., Brisset, P.: Optimal planning of digital cordless telecommunication systems. In: Malyshkin, V.E. (ed.) PaCT 1997. LNCS, vol. 1277. Springer, Heidelberg (1997)
Han, J., Lakshmanan, L.V.S., Ng, R.T.: Constraint-based, multidimensional data mining. Computer 32(8), 46–50 (1999)
Hilderman, R., Hamilton, H.: Knowledge Discovery and Measures of Interest. Kluwer Academic, Boston (2002)
Kramer, S., Raedt, L.D., Helma, C.: Molecular feature mining in hiv data. In: Proceedings of the 7th ACM International Conference on Knowledge Discovery and Data Mining, SIGKDD 2001 (2001)
Lakshmanan, L.V.S., Ng, R.T., Han, J., Pang, A.: Optimization of constrained frequent set queries with 2-variable constraints. In: Proceedings of the ACM International Conference on Management of Data, SIGMOD 1999 (1999)
Moulin, H.: Axioms for Cooperative Decision Making. Cambridge University Press, Cambridge (1988)
Ng, R.T., Lakshmanan, L.V.S., Han, J., Pang, A.: Exploratory mining and pruning optimizations of constrained associations rules. In: Proceedings of the ACM International Conference on Management of Data. SIGMOD 1998 (1998)
Orlando, S., Palmerini, P., Perego, R., Silvestri, F.: Adaptive and Resource-Aware Mining of Frequent Sets. In: Proc. of the 2002 IEEE Int. Conference on Data Mining (ICDM 2002), Maebashi City, Japan, December 2002, pp. 338–345 (2002)
Pei, J., Han, J.: Can we push more constraints into frequent pattern mining? In: Proceedings of the 6th ACM International Conference on Knowledge Discovery and Data Mining. SIGKDD 2000 (2000)
Ruttkay, Z.: Fuzzy constraint satisfaction. In: Proc. 3rd IEEE International Conference on Fuzzy Systems, pp. 1263–1268 (1994)
Sahar, S.: Interestingness via what is not interesting. In: Proc. of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. SIGKDD 1999 (1999)
Srikant, R., Vu, Q., Agrawal, R.: Mining association rules with item constraints. In: Proceedings of the 3rd ACM International Conference on Knowledge Discovery and Data Mining. SIGKDD 1997 (1997)
Tan, P.-N., Kumar, V., Srivastava, J.: Selecting the right interestingness measure for association patterns. In: Proc. of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. SIGKDD 2002 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bistarelli, S., Bonchi, F. (2005). Interestingness is Not a Dichotomy: Introducing Softness in Constrained Pattern Mining. In: Jorge, A.M., Torgo, L., Brazdil, P., Camacho, R., Gama, J. (eds) Knowledge Discovery in Databases: PKDD 2005. PKDD 2005. Lecture Notes in Computer Science(), vol 3721. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564126_8
Download citation
DOI: https://doi.org/10.1007/11564126_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29244-9
Online ISBN: 978-3-540-31665-7
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.