Search

Mining frequent tree patterns have many useful applications in XML mining, bioinformatics, network routing, etc. Most of the frequent subtree mining algorithms (i.e. FREQT, TreeMiner and CMTreeMiner) use anti-monotone property in the phase of candidate subtree generation. However, none of these algorithms have verified the correctness of this property in tree structured data. In this research it is shown that anti-monotonicity does not generally hold, when using weighed support in tree pattern discovery. As a result, tree mining algorithms that are based on this property would probably miss some of the valid frequent subtree patterns in a collection of trees. In this paper, we investigate the correctness of anti-monotone property for the problem of weighted frequent subtree mining. In addition we propose W3-Miner, a new algorithm for full extraction of frequent subtrees. The experimental results confirm that W3-Miner finds some frequent subtrees that the previously proposed algorithms are not able to discover., {"references":["Y. Chi, S. Nijssen, R.R. Muntz, J. N. Kok, \"Frequent Subtree Mining An\nOverview,\" Fundamental Informatics, Special Issue on Graph and Tree\nMining, 2005.","M.J. Zaki, \"Efficiently Mining Frequent Trees in a Forest: Algorithms\nand Applications,\" in IEEE Transaction on Knowledge and Data\nEngineering, vol. 17, no. 8, pp. 1021-1035, 2005.","H. Tan, T.S. Dillon, L. Feng, E. Chang, F. Hadzic, \"X3-Miner: Mining\nPatterns from XML Database,\" In Proc. Data Mining '05. Skiathos,\nGreece, 2005.","K. Abe, S. Kawasoe, T. Asai, H. Arimura, and S. Arikawa, \"Optimized\nSubstructure Discovery for Semi-structured Data,\" In Proc. PKDD-02,\n1-14, LNAI 2431, 2002.","M. J Zaki,.. Efficient Mining of Trees in the Forest. SIGKDD '02,\nEdmonton, Alberta, Canada, ACM. 2002.","M. J. Zaki and C. C. Aggarwal. XRules: An effective structural classifier\nfor XML data. In Proc. of the 2003 Int. Conf. Knowledge Discovery and\nData Mining, 2003.","T. Asai, H. Arimura, T. Uno, and S. Nakano. Discovering frequent\nsubstructures in large unordered trees. In Proc. of the 6th Intl. Conf. on\nDiscovery Science, 2003.","Y. Chi, Y. Yang, and R. R. Muntz. Mining frequent rooted trees and free\ntrees using canonical forms. Technical Report CSD-TR No. 030043,\nUCLA, 2003.","R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Inkeri\nVerkamo, \"Fast Discovery of Association Rules,\" Advances in\nKnowledge Discovery, and Data Mining, U. Fayyad et al., eds.,pp. 307-\n328, Menlo Park, Calif.: AAAI Press, 1996.\n[10] M.J. Zaki, \"Fast Vertical Mining Using Diffsets,\" In. Proc. of Int. Conf.\nKnowledge Discovery and Data Mining (SIGKDD-03), 2003.\n[11] M. Zaki. Efficiently mining frequent embedded unordered trees.\nFundamental Informatics, 65:1-20, 2005.\n[12] B. Shapiro and K. Zhang, \"Comparing Multiple RNA Secondary\nStructures Using Tree Comparisons,\" Computer Applications in\nBiosciences, vol. 6, no. 4, pp. 309-318, 1990."]}

High utility pattern mining is an emerging research topic in the data mining field. Unlike frequent pattern mining, high utility pattern mining deals with non-binary databases, in which the information about purchased quantities of items is maintained. Due to the non-existence of anti-monotone property among the utilities of itemsets, utility mining becomes a big challenge. Moreover, discovering useful patterns from the huge number of potential patterns is a mining bottleneck. However, the compact (Closed and Maximal) high utility pattern mining moderately lessens the number of patterns, but it does not solve it. Recently, an efficient framework called GUIDE, was proposed in the literature to address this issue. Though, GUIDE effectively reduced the number of high utility patterns, yet the quality of few mined patterns and their utilities are not exact. In view of this, we propose a modified MGUIDELM algorithm to improve the quality and determine exact utilities of maximal patterns.