Fundamenta Informaticae - Volume 66, issue 1-2

Authors: Washio, Takashi | De Raedt, Luc | Kok, Joost N.

Article Type: Other

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. v-viii, 2005

Authors: Ferré, Sébastien | King, Ross D.

Article Type: Research Article

Abstract: Many application domains make use of specific data structures such as sequences and graphs to represent knowledge. These data structures are ill-fitted to the standard representations used in machine learning and data-mining algorithms: propositional representations are not expressive enough, and first order ones are not efficient enough. In order to efficiently represent and reason on these data structures, and the complex patterns that are related to them, we use domain-specific logics. We show these logics can …be built by the composition of logical components that model elementary data structures. The standard strategies of top-down and bottom-up search are ill-suited to some of these logics, and lack flexibility. We therefore introduce a dichotomic search strategy, that is analogous to a dichotomic search in an ordered array. We prove this provides more flexibility in the search, while retaining completeness and non-redundancy. We present a novel algorithm for learning using domain specific logics and dichotomic search, and analyse its complexity. We also describe two applications which illustrates the search for motifs in sequences; where these motifs have arbitrary length and length-constrained gaps. In the first application sequences represent the trains of the East-West challenge; in the second application they represent the secondary structure of Yeast proteins for the discrimination of their biological functions. Show more

Keywords: Data structures, domain-specific logics, search algorithm, dichotomy, formal concept analysis, concept learning, pattern mining, bioinformatics

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. 1-32, 2005

Authors: Zaki, Mohammed J.

Article Type: Research Article

Abstract: Mining frequent trees is very useful in domains like bioinformatics, web mining, mining semi-structured data, and so on. In this paper we introduce SLEUTH, an efficient algorithm for mining frequent, unordered, embedded subtrees in a database of labeled trees. The key contributions of our work are as follows: We give the first algorithm that enumerates all embedded, unordered trees. We propose a new equivalence class extension scheme to generate all candidate trees. We extend the notion …of scope-list joins to compute frequency of unordered trees. We conduct performance evaluation on several synthetic and real datasets to show that SLEUTH is an efficient algorithm, which has performance comparable to TreeMiner, that mines only ordered trees. Show more

Keywords: Tree Mining, Embedded Trees, Unordered Trees

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. 33-52, 2005

Authors: Inokuchi, Akihiro | Washio, Takashi | Motoda, Hiroshi

Article Type: Research Article

Abstract: The derivation of frequent subgraphs from a dataset of labeled graphs has high computational complexity because the hard problems of isomorphism and subgraph isomorphism have to be solved as part of this derivation. To deal with this computational complexity, all previous approaches have focused on one particular kind of graph. In this paper, we propose an approach to conduct a complete search for various classes of frequent subgraphs in a massive dataset of labeled graphs within …a practical time. The power of our approach comes from the algebraic representation of graphs, its associated operations and well-organized bias constraints to limit the search space efficiently. The performance has been evaluated using real world datasets, and the high scalability and flexibility of our approach have been confirmed with respect to the amount of data and the computation time. Show more

Keywords: Data Mining, Graph Mining, Frequent Subgraph, Bias, Canonical Form, Subgraph Isomorphism

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. 53-82, 2005

Authors: Holder, Lawrence | Cook, Diane | Coble, Jeff | Mukherjee, Maitrayee

Article Type: Research Article

Abstract: We describe an approach to learning patterns in relational data represented as a graph. The approach, implemented in the Subdue system, searches for patterns that maximally compress the input graph. Subdue can be used for supervised learning, as well as unsupervised pattern discovery and clustering. We apply Subdue in domains related to homeland security and social network analysis.

Keywords: Graphs, relational learning, security

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. 83-101, 2005

Authors: Habrard, Amaury | Bernard, Marc | Sebban, Marc

Article Type: Research Article

Abstract: In front of the large increase of the available amount of structured data (such as XML documents), many algorithms have emerged for dealing with tree-structured data. In this article, we present a probabilistic approach which aims at a priori pruning noisy or irrelevant subtrees in a set of trees. The originality of this approach, in comparison with classic data reduction techniques, comes from the fact that only a part of a tree (i.e. a subtree) can …be deleted, rather than the whole tree itself. Our method is based on the use of confidence intervals, on a partition of subtrees, computed according to a given probability distribution. We propose an original approach to assess these intervals on tree-structured data and we experimentally show its interest in the presence of noise. Show more

Keywords: data reduction, tree-structured data, noisy data, stochastic tree automata

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. 103-130, 2005

Authors: Geamsakul, Warodom | Yoshida, Tetsuya | Ohara, Kouzou | Motoda, Hiroshi | Yokoi, Hideto | Takabayashi, Katsuhiko

Article Type: Research Article

Abstract: A machine learning technique called Graph-Based Induction (GBI) efficiently extracts typical patterns from graph-structured data by stepwise pair expansion (pairwise chunking). It is very efficient because of its greedy search. Meanwhile, a decision tree is an effective means of data classification from which rules that are easy to understand can be obtained. However, a decision tree could not be constructed for the data which is not explicitly expressedwith attribute-value pairs. This paper proposes a method called …Decision Tree Graph-Based Induction (DT-GBI), which constructs a classifier (decision tree) for graph-structured data while simultaneously constructing attributes for classification using GBI. Substructures (patterns) are extracted at each node of a decision tree by stepwise pair expansion in GBI to be used as attributes for testing. Since attributes (features) are constructed while a classifier is being constructed, DT-GBI can be conceived as a method for feature construction. The predictive accuracy of a decision tree is affected by which attributes (patterns) are used and how they are constructed. A beam search is employed to extract good enough discriminative patterns within the greedy search framework. Pessimistic pruning is incorporated to avoid overfitting to the training data. Experiments using a DNA dataset were conducted to see the effect of the beam width and the number of chunking at each node of a decision tree. The results indicate that DT-GBI that uses very little prior domain knowledge can construct a decision tree that is comparable to other classifiers constructed using the domain knowledge. DT-GBI was also applied to analyze a real-world hepatitis dataset as a part of evidence-based medicine. Four classification tasks of the hepatitis data were conducted using only the time-series data of blood inspection and urinalysis. The preliminary results of experiments, both constructed decision trees and their predictive accuracies as well as extracted patterns, are reported in this paper. Some of the patterns match domain experts experience and the overall results are encouraging. Show more

Keywords: graphmining, graph-based induction, decision tree, beamsearch, evidence-basedmedicine

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. 131-160, 2005

Authors: Chi, Yun | Muntz, Richard R. | Nijssen, Siegfried | Kok, Joost N.

Article Type: Research Article

Abstract: Mining frequent subtrees from databases of labeled trees is a new research field that has many practical applications in areas such as computer networks, Web mining, bioinformatics, XML document mining, etc. These applications share a requirement for the more expressive power of labeled trees to capture the complex relations among data entities. Although frequent subtree mining is a more difficult task than frequent itemset mining, most existing frequent subtree mining algorithms borrow techniques from the relatively …mature association rule mining area. This paper provides an overview of a broad range of tree mining algorithms. We focus on the common theoretical foundations of the current frequent subtree mining algorithms and their relationship with their counterparts in frequent itemset mining. When comparing the algorithms, we categorize them according to their problem definitions and the techniques employed for solving various subtasks of the subtree mining problem. In addition, we also present a thorough performance study for a representative family of algorithms. Show more

Keywords: frequent subtree mining, canonical representation, a priori, enumeration tree, subtree isomorphism

Citation: Fundamenta Informaticae, vol. 66, no. 1-2, pp. 161-198, 2005