Abstract
Frequent pattern mining from uncertain data has been paid closed attention due to most of the real life databases contain data with uncertainty. Several approaches have been proposed for mining high significance frequent itemsets over uncertain data, however, previous algorithms yield many redundant frequent itemsets and require to set an appropriate user specified threshold which is difficult for users. In this paper, we formally define the problem of top-k minimal redundancy probabilistic frequent pattern mining, which targets to identify top-k patterns with high-significance and low-redundancy simultaneously from uncertain data. We first design uncertain pattern correlation based on Pearson correlation coefficient, which considers pattern uncertainty. Moreover, we present a new algorithm, UTFP, to mine top-k minimal redundancy frequent patterns of length no less than minimum length \(min\_l\) without setting threshold. We further propose a set of strategies to prune and reduce search space. Experimental results demonstrate that the proposed algorithm achieves good performance in terms of finding top-k frequent patterns with low redundancy on probabilistic data. Our method represents the first research endeavor for probabilistic data based top-k correlated pattern mining.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
References
Aggarwal, C.C., Li, Y., Wang, J.: Frequent pattern mining with uncertain data. In: SIGKDD, pp. 29–38 (2009)
Bernecker, T., Kriegel, H.P., Renz, M., Verhein, F., Zuefle, A.: Probabilistic frequent itemset mining in uncertain databases. In: SIGKDD (2009)
Chui, C.-K., Kao, B., Hung, E.: Mining frequent itemsets from uncertain data. In: Zhou, Z.-H., Li, H., Yang, Q. (eds.) PAKDD 2007. LNCS (LNAI), vol. 4426, pp. 47–58. Springer, Heidelberg (2007)
Tong, Y., Chen, L., Yurong, Y., Yu, P.S.: Mining frequent itemsets over uncertain databases. In: VLDB, pp. 1650–1661 (2012)
Zhou, W., Xiong, H.: Volatile correlation computation: a checkpoint view. In: KDD, pp. 848–856 (2008)
Liu, C., Chen, L., Zhang, C.: Summarizing probabilistic frequent patterns. In: KDD, pp. 527–535 (2013)
Liu, C., Chen, L., Zhang, C.: Mining probabilistic representative frequent patterns from uncertain data. In: SDM, pp. 73–81 (2013)
Pan, S., Zhu, X.: Continuous top-k query for graph streams. In: CIKM, pp. 2659–2662 (2012)
Xin, D., Cheng, H., Yan, X., Han, J.: Extracting redundancy-aware top-k patterns. In: KDD, pp. 444–453 (2006)
Pei, J., Han, J., Lu, H., Nishio, S., Tang, S., Yang, D.: H-mine: hyper-structure mining of frequent patterns in large databases. In: ICDM, pp. 441–448 (2001)
Sun, L., Cheng, R., Cheung, D.W., Cheng, J.: Mining uncertain data with probabilistic guarantees. In: SIGKDD, pp. 273–282 (2010)
Bayardo Jr., R.: Efficiently mining long patterns from databases. In: SIGMOD, pp. 85–93 (1998)
Calders, T., Goethals, B.: Mining all non-derivable frequent itemsets. In: Elomaa, T., Mannila, H., Toivonen, H. (eds.) PKDD 2002. LNCS (LNAI), vol. 2431, pp. 74–85. Springer, Heidelberg (2002)
Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Discovering frequent closed itemsets for association rules. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 398–416. Springer, Heidelberg (1998)
Tzvetkov, P., Yan, X., Han, J.: TSP: mining top-k closed sequential patterns. Knowl. Inf. Syst. 7(4), 438–457 (2005)
Han, J., Wang, J., Lu, Y., Tzvetkov, P.: Mining top-k frequent closed patterns without minimum support. In: ICDM, pp. 211–218 (2002)
Acknowledgement
This work was supported by the Australian Research Council (ARC) Discovery Project under Grant No. DP140102206.
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
Wang, H., Zhang, P., Wu, J., Pan, S. (2015). Mining Top-k Minimal Redundancy Frequent Patterns over Uncertain Databases. In: Arik, S., Huang, T., Lai, W., Liu, Q. (eds) Neural Information Processing. ICONIP 2015. Lecture Notes in Computer Science(), vol 9492. Springer, Cham. https://doi.org/10.1007/978-3-319-26561-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-26561-2_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26560-5
Online ISBN: 978-3-319-26561-2
eBook Packages: Computer ScienceComputer Science (R0)