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]

Measuring the quality of a contrast pattern is an active and relevant area of pattern recognition and data mining. Quality measures are important tools in very different scenarios like supervised classification, pattern based clustering, and association rule mining. Consequently, and due to the large collection of available measures, it is important to perform comparative studies for each particular context. Most published studies comparing quality measures are theoretical and in the context of association rule evaluation. In this paper, we present an empirical comparison of the behavior of 33 quality measures in the context of supervised classification and contrast pattern filtering. A comprehensive experimentation using several databases compares the behavior of these measures in three different contexts: as aggregation value, as pattern evaluation for classification, and as pattern evaluation for filtering. Experiments also show that top-accurate quality measures for classification have a deceptive performance for pattern filtering, because they cannot distinguish among patterns with zero support in the negative class. [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]

Contrast pattern-based classifiers are an important family of both understandable and accurate classifiers. Nevertheless, these classifiers do not achieve good performance on class imbalance problems. In this paper, we introduce a new contrast pattern-based classifier for class imbalance problems. Our proposal for solving the class imbalance problem combines the support of the patterns with the class imbalance level at the classification stage of the classifier. From our experimental results, using highly imbalanced databases, we can conclude that our proposed classifier significantly outperforms the current contrast pattern-based classifiers designed for class imbalance problems. Additionally, we show that our classifier significantly outperforms other state-of-the-art classifiers not directly based on contrast patterns, which are also designed to deal with class imbalance problems. [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]