Search

Most algorithms to mine graph patterns, during the searching process, require a pattern to be identical to its occurrences, relying on the graph isomorphism problem. However, in recent years, there has been interest in the case in which it is acceptable to have some differences between a pattern and its occurrences, whether these differences are in labels or in structure. Allowing some differences and using inexact matching to measure the similarity between graphs lead to the discovery of new patterns, but some important challenges, such as the increment on the number of found patterns, make the post-mining analysis harder. In this work we focus on two extensions of the AGraP algorithm, which mines inexact patterns, addressing the issue of reducing the output pattern set while trying to retain the useful information gained through the use of inexact matching. First, exploring a traditional approach, we propose the CloseAFG algorithm that focuses on closed patterns. Then, we propose the IntAFG algorithm to find a subset of patterns covering the original pattern set, while lessening redundancy among selected patterns. We show the performance of our approaches through some experiments on synthetic databases; additionally, we also show the usefulness of the reduced pattern sets for image classification. [ABSTRACT FROM AUTHOR]

Abstract: Most of the current algorithms for mining association rules assume that two object subdescriptions are similar when they are exactly equal, but in many real world problems some other similarity functions are used. Commonly these algorithms are divided in two steps: Frequent pattern mining and generation of interesting association rules from frequent patterns. In this work, two algorithms for mining frequent similar patterns using similarity functions different from the equality are proposed. Additionally, the GenRules Algorithm is adapted to generate interesting association rules from frequent similar patterns. Experimental results show that our algorithms are more effective and obtain better quality patterns than the existing ones. [Copyright &y& Elsevier]

Contrast patterns, which lie in the core of most understandable classifiers, are frequently evaluated by quality measures. Since many different quality measures are available, they should be compared to select the most appropriate for each applications. This paper introduces a method to compare quality measures, using a set of mined patterns and a collection of objects not used for mining. The comparison is performed by correlating quality values with a quality estimation of the patterns. Additionally, a meta-learning study is performed to show that combining quality measures could be better than using the best single measures in isolation. The results of this paper can help researchers to create new quality measures or to find new combinations of quality measures to create better understandable classification systems. [ABSTRACT FROM AUTHOR]

Frequent pattern mining is considered a key task to discover useful information. Despite the quality of solutions given by frequent pattern mining algorithms, most of them face the challenge of how to reduce the number of frequent patterns without information loss. Frequent itemset mining addresses this problem by discovering a reduced set of frequent itemsets, named closed frequent itemsets , from which the entire frequent pattern set can be recovered. However, for frequent similar pattern mining , where the number of patterns is even larger than for Frequent itemset mining, this problem has not been addressed yet. In this paper, we introduce the concept of closed frequent similar pattern mining to discover a reduced set of frequent similar patterns without information loss. Additionally, a novel closed frequent similar pattern mining algorithm, named CFSP-Miner , is proposed. The algorithm discovers frequent patterns by traversing a tree that contains all the closed frequent similar patterns. To do this efficiently, several lemmas to prune the search space are introduced and proven. The results show that CFSP-Miner is more efficient than the state-of-the-art frequent similar pattern mining algorithms, except in cases where the number of frequent similar patterns and closed frequent similar patterns are almost equal. However, CFSP-Miner is able to find the closed similar patterns, yielding a reduced size of the discovered frequent similar pattern set without information loss. Also, CFSP-Miner shows good scalability while maintaining an acceptable runtime performance. [ABSTRACT FROM AUTHOR]