CobMiner: mineração de Padrões Arborescentes com restrições

Abstract

Most work on pattern mining focus on simple data structures like itemsets or sequences of itemsets. However, a lot of recent applications dealing with complex data like chemical compounds, protein structure, social network, XML and Web Log databases, require much more sophisticated data structures (trees or graphs) for their specification. Here, interesting patterns involve not only frequent object values (labels) appearing in the trees (or graphs) but also frequent specific topologies found in these structures. Mining frequent tree patterns have been extensively studied, motivated by the increasing interest and applicability in different areas (Web Mining, Bioinformatics, etc). However, conventional tree mining systems normally consider only minimum support criterium as a mechanism for filtering patterns to be mined. After mining process, hard work is requiring to filter patterns concerned with user interests.

In this dissertation, we propose CobMiner, Constrained-based Miner, a tree pattern mining algorithm which incorporates tree automata into the mining process in order to restrict the mining scope and to generate frequent patterns more closely related to user interests. We compare two methods for introducing user constraints into the discovery process: the first one is CobMiner which incorporates tree automata constraints as an intra-mining mechanism, the second one is TreeMinerPP which consists of a well-known tree pattern mining algorithm, TreeMiner, followed by a post-processing phase, where patterns are filtered using a tree automatum.

An extensive set of experiments executed over synthetic and real data (XML documents) allow us to conclude that incorporating constraints during the mining process is far better effective than filtering the frequent and interesting patterns after the mining process.