Relational Data Mining

Data mining, the central activity in the process of knowledge discovery in databases, is concerned with finding patterns in data. This chapter introduces and illustrates the most common types of patterns considered by data mining approaches and gives rough outlines of the data mining algorithms that are most frequently used to look for such patterns. It also briefly introduces relational data mining, starting with patterns that involve multiple relations and laying down the basic principles common to relational data mining algorithms. An overview of the contents of this book is given, as well as pointers to literature and Internet resources on data mining.

Data Mining and Knowledge Discovery in Databases (KDD) promise to play an important role in the way people interact with databases, especially decision support databases where analysis and exploration operations are essential. Inductive logic programming can potentially play some key roles in KDD. We define the basic notions in data mining and KDD, define the goals, present motivation, and give a high-level definition of the KDD Process and how it relates to Data Mining. We then focus on data mining methods. Basic coverage of a sampling of methods will be provided to illustrate the methods and how they are used. We cover two case studies of successful applications in science data analysis, one of which is the classification of cataloging of a major astronomy sky survey covering 2 billion objects in the northern sky. The system can outperform human as well as classical computational analysis tools in astronomy on the task of recognizing faint stars and galaxies. We conclude with a listing of research challenges and we outline the areas where ILP could play some important roles in KDD.

Inductive logic programming (ILP) is concerned with the development of techniques and tools for relational data mining. Besides the ability to deal with data stored in multiple tables, ILP systems are usually able to take into account generally valid background (domain) knowledge in the form of a logic program. They also use the powerful language of logic programs for describing discovered patterns. This chapter introduces the basics of logic programming and relates logic programming terminology to database terminology. It then defines the task of relational rule induction, the basic data mining task addressed by ILP systems, and presents some basic techniques for solving this task. It concludes with an overview of other relational data mining tasks addressed by ILP systems.

Three companion systems, Claudien, ICL and Tilde, are presented. They use a common representation for examples and hypotheses: each example is represented by a relational database. This contrasts with the classical inductive logic programming systems such as Progol and Foil. It is argued that this representation is closer to attribute value learning and hence more natural. Furthermore, the three systems can be considered first order upgrades of typical data mining systems, which induce association rules, classification rules or decision trees respectively.

In this chapter, we present a system that enhances the representational capabilities of decision and regression tree learning by extending it to first-order logic, i.e., relational representations as commonly used in Inductive Logic Programming. We describe an algorithm named Structural Classification and Regression Trees (S-Cart), which is capable of inducing first-order trees for both classification and regression problems, i.e., for the prediction of either discrete classes or numerical values. We arrive at this algorithm by a strategy called upgrading — we start from a propositional induction algorithm and turn it into a relational learner by devising suitable extensions of the representation language and the associated algorithms. In particular, we have upgraded Cart, the classical method for learning classification and regression trees, to handle relational examples and background knowledge. The system constructs a tree containing a literal (an atomic formula or its negation) or a conjunction of literals in each node, and assigns either a discrete class or a numerical value to each leaf. In addition, we have extended the Cart methodology by adding linear regression models to the leaves of the trees; this does not have a counterpart in Cart, but was inspired by its approach to pruning. The regression variant of S-Cart is one of the few systems applicable to Relational Regression problems. Experiments in several real-world domains demonstrate that the approach is useful and competitive with existing methods, indicating that the advantage of relatively small and comprehensible models does not come at the expense of predictive accuracy.

This chapter describes the theory and use of CProgol4.4, a state-ofthe-art Inductive Logic Programming (ILP) system. After explaining how to download the source code, the reader is guided through the development of Progol input files containing type definitions, mode declarations, background knowledge, examples and integrity constraints. The theory behind the system is then described using a simple example as illustration. The main algorithms in Progol are given and methods of pruning the search space of possible hypotheses are discussed. Next the application of built-in procedures for estimating predictive accuracy and statistical significance of Progol hypotheses is demonstrated. Lastly, the reader is shown how to use the more advanced features of CProgol4.4, including positive-only learning and the use of metalogical predicates for pruning the search space.

Within KDD, the discovery of frequent patterns has been studied in a variety of settings. In its simplest form, known from association rule mining, the task is to discover all frequent item sets, i.e., all combinations of items that are found in a sufficient number of examples. We present algorithms for relational association rule discovery that are well-suited for exploratory data mining. They offer the flexibility required to experiment with examples more complex than feature vectors and patterns more complex than item sets.

We describe a methodology for upgrading existing attribute-value learners towards first-order logic. This method has several advantages: one can profit from existing research on propositional learners (and inherit its efficiency and effectiveness), relational learners (and inherit its expressiveness) and PAC-learning (and inherit its theoretical basis). Moreover there is a clear relationship between the new relational system and its propositional counterpart. This makes the ILP system easy to use and understand by users familiar with the propositional counterpart. We demonstrate the methodology on the ICL system which is an upgrade of the propositional learner CN2.

This chapter surveys methods that transform a relational representation of a learning problem into a propositional (feature-based, attribute-value) representation. This kind of representation change is known as propositionalization. Taking such an approach, feature construction can be decoupled from model construction. It has been shown that in many relational data mining applications this can be done without loss of predictive performance. After reviewing both general-purpose and domaindependent propositionalization approaches from the literature, an extension to the Linus propositionalization method that overcomes the system’s earlier inability to deal with non-determinate local variables is described.

Boosting, a methodology for constructing and combining multiple classifiers, has been found to lead to substantial improvements in predictive accuracy. Although boosting was formulated in a propositional learning context, the same ideas can be applied to first-order learning (also known as inductive logic programming). Boosting is used here with a system that learns relational definitions of functions. Results show that the magnitude of the improvement, the additional computational cost, and the occasional negative impact of boosting all resemble the corresponding observations for propositional learning.

This chapter gives an overview of applications of relational learning and inductive logic programming to data mining problems in a variety of areas. These include bioinformatics, where successful applications come from drug design, predicting mutagenicity and carcinogenicity, and predicting protein structure and function, including genome scale prediction of protein functional class. Other application areas include medicine, environmental sciences and monitoring, mechanical and traffic engineering. Applications of relational learning are also emerging in business data analysis, text and Web mining, and miscellaneous other fields, such as the analysis of musical performances.

Since the late 1980s there has been a sustained research effort directed at investigating the application of Inductive Logic Programming (ILP) to problems in biology and chemistry. This essay is a personal view of some interesting issues that have arisen during my involvement in this enterprise. Many of the concerns of the broader field of Knowledge Discovery in Databases manifest themselves during the application of ILP to analyse bio-chemical data. Addressing them in this microcosm has given me some directions on the wider application of ILP, and I present these here in the form of four suggestions and one rule. Readers are invited to consider them in the context of a hypothetical Recommended Codes and Practices for the application of ILP.

The aim of this chapter is to review ILP resources available on the Internet. These are especially important due to the growing interest for applying ILP methods to knowledge discovery in databases (KDD) and data mining problems. They also play an important role in connecting the ILP research community with potential end users of ILP methods. Most of the chapter is dedicated to the ILP Internet resources gathered and maintained in the ILPnet and ILPnet2 projects. Some other ILP and KDD related Internet resources are briefly reviewed as well.