Relational Data Mining

by Dzeroski, Saso; Lavrac, Nada

• ISBN13: 9783540422891
• ISBN10: 3540422897
• Format: Hardcover
• Copyright: 2001-10-01
• Publisher: Springer Verlag

Summary

As the first book devoted to relational data mining, this coherently written multi-author monograph provides a thorough introduction and systematic overview of the area. The first part introduces the reader to the basics and principles of classical knowledge discovery in databases and inductive logic programming; subsequent chapters by leading experts assess the techniques in relational data mining in a principled and comprehensive way; finally, three chapters deal with advanced applications in various fields and refer the reader to resources for relational data mining. This book will become a valuable source of reference for R&D professionals active in relational data mining. Students as well as IT professionals and ambitioned practitioners interested in learning about relational data mining will appreciate the book as a useful text and gentle introduction to this exciting new field.

Table of Contents

Part I. Introduction
Data Mining in a Nutshell	3	(25)
Saso Dzeroski
Introduction	3	(1)
Data mining tasks	4	(4)
Patterns	8	(8)
Basic algorithms	16	(6)
Relational data mining	22	(3)
Data mining literature and Internet resources	25	(1)
Summary	26	(2)
Knowledge Discovery in Databases: An Overview	28	(20)
Usama Fayyad
Introduction	28	(1)
From transactions to warehouses to KDD	29	(2)
Why data mining?	31	(1)
KDD and data mining	32	(2)
Data mining methods: An overview	34	(3)
Applications in science data analysis	37	(4)
Research challenges for KDD	41	(2)
ILP and KDD: Prospects and challenges	43	(2)
Concluding remarks	45	(3)
An Introduction to Inductive Logic Programming	48	(26)
Saso Dzeroski
Nada Lavrac
Introduction	48	(1)
Logic programming and databases	49	(2)
Logic programming in a nutshell	51	(4)
The basic ILP task: Relational rule induction	55	(3)
Structuring the space of clauses	58	(2)
Searching the space of clauses	60	(2)
Bounding the search for clauses	62	(5)
Transforming ILP problems to propositional form	67	(2)
Relational data mining tasks addressed by ILP	69	(1)
ILP literature	70	(1)
Summary	71	(3)
Inductive Logic Programming for Knowledge Discovery in Databases	74	(31)
Stefan Wrobel
Introduction	74	(7)
ILP: Relational analysis technology	81	(3)
ILP subgroup discovery: MIDOS	84	(9)
Using MIDOS and other ILP methods in KEPLER	93	(6)
Conclusion	99	(6)
Part II. Techniques
Three Companions for Data Mining in First Order Logic	105	(35)
Luc De Raedt
Hendrik Blockeel
Luc Dehaspe
Wim Van Laer
Introduction	105	(1)
Representation	106	(8)
ICL: Inductive classification logic	114	(2)
TILDE: Top-down induction of logical decision trees	116	(1)
CLAUDIEN: Clausal discovery	117	(2)
Practical use: Getting started	119	(14)
Sample application: Mutagenesis	133	(3)
An exercise	136	(1)
Conclusions and practical info	137	(3)
Inducing Classification and Regression Trees in First Order Logic	140	(20)
Stefan Kramer
Gerhard Widmer
Introduction	140	(2)
Tree induction in logic	142	(3)
Structural classification and regression trees (S-CART): The to level algorithm	145	(1)
Growing a tree in first-order logic	145	(5)
Model selection by error/cost complexity pruning	150	(2)
First-order model trees	152	(1)
Applications	153	(1)
Related work	154	(2)
Conclusion	156	(4)
Relational Rule Induction with CPROGOL4.4: A Tutorial Introduction	160	(29)
Stephen Muggleton
John Firth
Introduction	160	(1)
How to obtain CPROGOL4.4	161	(1)
Developing an input file for CPROGOL4.4	162	(5)
The theory	167	(12)
Estimating accuracy and significance	179	(3)
Declarative bias	182	(3)
Setting resource bounds	185	(1)
Debugging PROGOL input files	186	(1)
Summary	187	(2)
Discovery of Relational Association Rules	189	(24)
Luc Dehaspe
Hannu Toivonen
Introduction	189	(1)
From association rules to query extensions	190	(4)
Evaluation measures	194	(4)
Declarative language bias	198	(3)
Query (extension) discovery with WARMR	201	(5)
A sample run	206	(2)
Discussion	208	(5)
Distance Based Approaches to Relational Learning and Clustering	213	(22)
Mathias Kirsten
Stefan Wrobel
Tamas Horvath
Introduction	213	(2)
A first-order distance measure	215	(5)
Instance-based learning with RIBL2	220	(1)
Hierarchical agglomerative clustering with RDBC	221	(2)
FORC- k-means for multirelational data	223	(2)
A case study in mRNA signal structures	225	(5)
Conclusion	230	(5)
Part III. From Propositional to Relational Data Mining
How to Upgrade Propositional Learners to First Order Logic: A Case Study	235	(27)
Wim Van Laer
Luc De Raedt
Introduction	235	(1)
Knowledge representation	236	(4)
The propositional learner CN2	240	(1)
Upgrading CN2	241	(11)
Some experimental results with ICL	252	(4)
Related work and conclusions	256	(6)
Propositionalization Approaches to Relational Data Mining	262	(30)
Stefan Kramer
Nada Lavrac
Peter Flach
Introduction	262	(3)
Background and definition of terms	265	(2)
An example illustrating a simple propositionalization	267	(4)
Feature construction for general-purpose propositionalization	271	(3)
Special-purpose feature construction	274	(3)
Related transformation approaches	277	(2)
A sample propositionalization method: Extending LINUS to handle non-determinate literals	279	(7)
Concluding remarks	286	(6)
Relational Learning and Boosting	292	(15)
Ross Quinlan
Introduction	292	(1)
Boosting	293	(1)
FOIL	294	(3)
Overview of FFOIL	297	(2)
Boosting FFOIL	299	(1)
Experiments	300	(4)
Summary	304	(3)
Learning Probabilistic Relational Models	307	(32)
Lise Getoor
Nir Friedman
Daphne Koller
Avi Pfeffer
Introduction	307	(2)
Probabilistic models	309	(3)
Relational models	312	(3)
Probabilistic relational models	315	(6)
Learning PRMs	321	(4)
Experimental results	325	(4)
Discussion and related work	329	(2)
Extensions	331	(2)
Conclusions	333	(6)
Part IV. Applications and Web Resources
Relational Data Mining Applications: An Overview	339	(26)
Saso Dzeroski
Introduction	339	(1)
Drug design	340	(3)
Predicting mutagenicity and carcinogenicity	343	(3)
Predicting protein structure and function	346	(3)
Medical applications	349	(1)
Environmental applications	350	(3)
Mechanical engineering applications	353	(3)
Traffic engineering applications	356	(1)
Text mining, Web mining, and natural language processing	357	(1)
Business data analysis	358	(1)
Miscellaneous applications	359	(1)
Summary and discussion	360	(5)
Four Suggestions and a Rule Concerning the Application of ILP	365	(10)
Ashwin Srinivasan
Introduction	365	(1)
Background	366	(1)
When and why ILP?	367	(1)
Encoding background knowledge	368	(3)
Utility mismatch	371	(1)
Comprehensibility	371	(1)
From nursery slopes to Darwin's rule	372	(3)
Internet Resources on ILP for KDD	375	(14)
Ljupco Todorovski
Irene Weber
Nada Lavrac
Olga Stepankova
Saso Dzeroski
Dimitar Kazakov
Darko Zupanic
Peter Flach
Introduction	375	(1)
Brief history on ILP Internet resources	376	(1)
ILPnet2 Internet resources	377	(6)
Other ILP-related Internet resources	383	(2)
KDD related Internet resources	385	(1)
Conclusion	385	(4)
Author Index	389	(2)
Subject Index	391