Associative categorization of frequent patterns based on the probabilistic graphical model

Abstract

Discovering the hierarchical structures of different classes of object behaviors can satisfy the requirements of various degrees of abstraction in association analysis, behavior modeling, data preprocessing, pattern recognition and decision making, etc. In this paper, we call this process as associative categorization, which is different from classical clustering, associative classification and associative clustering. Focusing on representing the associations of behaviors and the corresponding uncertainties, we propose the method for constructing a Markov network (MN) from the results of frequent pattern mining, called item-associative Markov network (IAMN), where nodes and edges represent the frequent patterns and their associations respectively. We further discuss the properties of a probabilistic graphical model to guarantee the IAMN’s correctness theoretically. Then, we adopt the concept of chordal to reflect the closeness of nodes in the IAMN. Adopting the algorithm for constructing join trees from an MN, we give the algorithm for IAMN-based associative categorization by hierarchical bottom-up aggregations of nodes. Experimental results show the effectiveness, efficiency and correctness of our methods.

Keywords

frequent pattern / behavior association / associative categorization / Markov network / hierarchical aggregation

References

[1] LiuW, YueK, WuT, WeiM. An approach for multi-objective categorization based on the game theory and Markov process. Applied Soft Computing, 2011, 11(6): 4087-4096

[2] AgrawalR, ImielinskiT, SwamiA. Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 1993, 207-216

[3] HanJ, KamberM. Data Mining: Concepts and Techniques. 1st ed. Morgan Kaufmann, 2000

[4] HanJ, ChengH, XinD, YanX. Frequent pattern mining: current status and future directions. Data Mining and Knowledge Discovery, 2007, 15(1): 55-85

[5] ChaojiV, A I HasanM, SalemS, ZakiM. An integrated, generic approach to pattern mining: data mining template library. Data Mining and Knowledge Discovery, 2008, 17(1): 457-495.

[6] SudhamathyG, VenkateswaranC. An efficient hierarchical frequent pattern analysis approach for web usage mining. International Journal of Computer Applications, 2012, 43(15): 1-7

[7] JiL, TanK, TungA. Compressed hierarchical mining of frequent closed patterns from dense data sets. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(9): 1175-1187

[8] CuiP, LiuZ, SunL, YangS. Hierarchical visual event pattern mining and its applications. Data Mining and Knowledge Discovery, 2011, 22(1): 467-492.

[9] NguyenV, YamamotoA. Mining of closed frequent subtrees from frequently updated databases. Intelligent Data Analysis, 2012, 16(6): 953-967

[10] JainA. Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 2010, 31(8): 651-666

[11] ForestierG, GancarskiP, WemmertC. Collaborative clustering with background knowledge. Data and Knowledge Engineering, 2010, 69(2): 211-228

[12] ThabtahF. A review of associative classification mining. The Knowledge Engineering Review, 2007, 22(1): 37-65

[13] BaralisE, GarzaP. I-prune: item selection for associative classification. International Journal of Intelligent Systems, 2012, 27(1): 279-299

[14] WangX, YueK, NiuW, ShiZ. An approach for adaptive associative classification. Expert Systems with Applications, 2011, 38(9): 11873-11883

[15] LucasJ, LaurentA, MorenoM, TeisseireM. A fuzzy associative classification approach for recommender systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2012, 20(4): 579-617

[16] SinkkonenJ, NikkiläJ, LahtiL, KaskiS. Associative clustering. Lecture Notes in Computer Science, 2004, 3201: 396-406

[17] KaskiS, NikkilaJ, SinkkonenJ, LahtiL, KnuuttilaJ, RoosC. Associative clustering for exploring dependencies between functional genomics data sets. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2005, 2(1): 203-216

[18] PearlJ. Probabilistic Reasoning in Intelligent Systems: Network of Plausible Inference. San Mateo: Morgan Kaufmann, 1988

[19] WongS, ButzC. Constructing the dependency structure of a multiagent probabilistic network. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 395-415.

[20] GeorgeD, HawkinsJ. A hierarchical Bayesian model of invariant pattern recognition in the visual cortex. In: Proceedings of the 2005 IEEE International Joint Conference on Neural Networks. 2005, 3: 1812-1817

[21] HuC, WuX, HuX, YaoH. Computing and pruning method for frequent pattern interestingness based on Bayesian networks. Journal of Software, 2011, 22(12): 2934-2950

[22] BowesJ, NeufeldE, GreerJ, CookeJ. A comparison of association rule discovery and Bayesian network causal inference algorithms to discover relationships in discrete data. Lecture Notes in Computer Science, 2000, 1822: 326-336

[23] JaroszewiczS, SchefferT. Fast discovery of unexpected patterns in data, relative to a Bayesian network. In: Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. 2005, 118-127

[24] MalhasR, AghbariZ. Interestingness filtering engine: mining Bayesian networks for interesting patterns. Expert Systems with Applications, 2009, 36(1): 5137-5145

[25] FauréC, DelpratS, BoulicautJ, MilleA. Iterative Bayesian network implementation by using annotated association rules. Lecture Notes in Computer Science, 2006, 4248: 326-333

[26] YuK, WuX, DingW, WangH, YaoH. Causal associative classification. In: Proceedings of the 11th IEEE International Conference on Data Mining. 2011, 914-923

[27] ScienceDirect. 2012

[28] ChengJ, BellD. LiuW. Learning Bayesian network from data: an efficient approach based on information theory. In: Proceedings of the 1997 Conference on Information and Knowledge Management. 1997, 325-331

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg