Inductive logic programming for relational knowledge discovery

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP, presents selected ILP techniques for relational knowledge discovery and reviews selected ILP applications. Nada Lavrač, Ph.D.: She is a senior research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1978) and a visiting professor at the Klagenfurt University, Austria (since 1987). Her main research interest is in machine learning, in particular inductive logic programming and intelligent data analysis in medicine. She received a BSc in Technical Mathematics and MSc in Computer Science from Ljubljana University, and a PhD in Technical Sciences from Maribor University, Slovenia. She is coauthor of KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems, The MIT Press 1989, and Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994, and coeditor of Intelligent Data Analysis in Medicine and Pharmacology, Kluwer 1997. She was the coordinator of the European Scientific Network in Inductive Logic Programming ILPNET (1993–1996) and program cochair of the 8th European Machine Learning Conference ECML’95, and 7th International Workshop on Inductive Logic Programming ILP’97. Sašo Džeroski, Ph.D.: He is a research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1989). He has held visiting researcher positions at the Turing Institute, Glasgow (UK), Katholieke Universiteit Leuven (Belgium), German National Research Center for Computer Science (GMD), Sankt Augustin (Germany) and the Foundation for Research and Technology-Hellas (FORTH), Heraklion (Greece). His research interest is in machine learning and knowledge discovery in databases, in particular inductive logic programming and its applications and knowledge discovery in environmental databases. He is co-author of Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994. He is the scientific coordinator of ILPnet2, The Network of Excellence in Inductive Logic Programming. He was program co-chair of the 7th International Workshop on Inductive Logic Programming ILP’97 and will be program co-chair of the 16th International Conference on Machine Learning ICML’99. Masayuki Numao, Ph.D.: He is an associate professor at the Department of Computer Science, Tokyo Institute of Technology. He received a bachelor of engineering in electrical and electronics engineering in 1982 and his Ph.D. in computer science in 1987 from Tokyo Institute of Technology. He was a visiting scholar at CSLI, Stanford University from 1989 to 1990. His research interests include Artificial Intelligence, Global Intelligence and Machine Learning. Numao is a member of Information Processing Society of Japan, Japanese Society for Artificial Intelligence, Japanese Cognitive Science Society, Japan Society for Software Science and Technology and AAAI.     

归纳逻辑程序设计综述

归纳逻辑程序设计是由机器学习与逻辑程序设计交叉所形成的一个研究领域,是机器学习的前沿研究课题。该文首先从归纳逻辑程序设计的问题背景、类型划分和搜索程序子句三个方面介绍了归纳逻辑程序设计系统的概貌;然后结合实验室的相关研究工作,回顾了归纳逻辑程序设计研究的发展;之后介绍了归纳逻辑程序设计领域中需要深入研究的若干问题,并提出了新的解决思路;最后是总结,以引起读者对归纳逻辑程序设计领域研究的进一步关注。     

Cautious induction: An alternative to clause-at-a-time hypothesis construction in inductive logic programming

Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set. This paper formulates and analyses an alternative method for constructing hypotheses. The method, calledcautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm. We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems. Simon Anthony, BEng.: Simon, perhaps better known as “Mr. Cautious” in Inductive Logic Programming (ILP) circles, completed a BEng in Information Engineering at the University of York in 1995. He remained at York as a research student in the Intelligent Systems Group. Concentrating on ILP, his research interests are Cautious Induction and developing number handling techniques using Constraint Logic Programming. Alan M. Frisch, Ph.D.: He is the Reader in Intelligent Systems at the University of York (UK), and he heads the Intelligent Systems Group in the Department of Computer Science. He was awarded a Ph. D. in Computer Science from the University of Rochester (USA) in 1986 and has held faculty positions at the University of Sussex (UK) and the University of Illinois at Urbana-Champaign (USA). For over 15 years Dr. Frisch has been conducting research on a wide range of topics in the area of automated reasoning, including knowledge retrieval, probabilistic inference, constraint solving, parsing as deduction, inductive logic programming and the integration of constraint solvers into automated deduction systems.     

Rough Problem Settings for ILP Dealing With Imperfect Data

This paper applies rough set theory to Inductive Logic Programming (ILP, a relatively new method in machine learning) to deal with imperfect data occurring in large real-world applications. We investigate various kinds of imperfect data in ILP and propose rough problem settings to deal with incomplete background knowledge (where essential predicates/clauses are missing), indiscernible data (where some examples belong to both sets of positive and negative training examples), missing classification (where some examples are unclassified) and too strong declarative bias (hence the failure in searching for solutions). The rough problem settings relax the strict requirements in the standard normal problem setting for ILP, so that rough but useful hypotheses can be induced from imperfect data. We give simple measures of learning quality for the rough problem settings. For other kinds of imperfect data (noise data, too sparse data, missing values, real-valued data, etc.), while referring to their traditional handling techniques, we also point out the possibility of new methods based on rough set theory.     

基于统计归纳的状态知识发现算法与实现

反映所研究对象的状态、变态和发展变化趋势及其相互之间关系的知识一直受到人们的关注,尤其是利用数据挖掘和知识发现的方法来获取这一类知识。文章基于归纳逻辑的统计归纳和语言场与语言值结构,提出这类知识的发现方法和实现算法,并通过实验验证了算法的有效性。该方法可适用于科学和工程数据库以及事务数据库的知识发现。     

知识发现状态空间模型及其在图像挖掘中的应用*

提出了知识发现状态空间统一模型,将结构化数据挖掘与复杂类型数据挖掘联系起来,成为知识发现领域的一种统一框架理论,为复杂类型数据挖掘提供理论指导,并给出了该模型在图像挖掘中的应用实例。     

基于不完备信息系统的粗糙分类研究

基于传统的不分明关系的粗糙集理论是无法处理不完备信息系统的。针对不完备的信息,研究了基于不完备信息系统的粗糙分类的方法,通过实例,有效地分析、处理了含有缺省数据和不精确数据的信息系统。     

归纳逻辑程序设计方法综述

归纳逻辑程序设计是机器学习与逻辑程序设计交叉所形成的一个研究领域,克服了传统机器学习方法的两个主要限制：即知识表示的限制和背景知识利用的限制,成为机器学习的前沿研究课题。首先从归纳逻辑程序设计的产生背景、定义、应用领域及问题背景介绍了归纳逻辑程序设计系统的概貌,对归纳逻辑程序设计方法的研究现状进行了总结和分析,最后探讨了该领域的进一步的研究方向。     

Selecting potentially relevant records using re-identification methods

This work proposes re-identification algorithms to select records that are interesting from the point of view of giving new information. Instead of focusing on re-identified elements, we focus on non re-identified records (non linked records) as they are the ones that potentially supply new and relevant information. Moreover, these relevant characteristics can correspond to chances for improving the knowledge of a system.To evaluate our approach, we have applied it to a example using publicly available data from the UCI repository. We have used the data of theionosphere data base to build a re-identification problem for 35 non-common variables.We show that the use of a simple heuristic rule base can effectively select potentially interesting records.     

基于属性分类和回归模式的知识发现研究

该文针对目前数据挖掘的研究状况,理论上提出了将基于属性分类方法和多元线形回归算法相结合的算法,首先使用基于属性分类的方法将原始数据库进行属性分类,化简,去掉次要的条件属性,最后得出一个简化的表格,找出影响决策属性的主要因素,根据此表,可以得出简单的ifthen规则;然后使用多元线形回归求出它们之间的近似定量关系,得出一个最优回归方程。     

模糊聚类分析在KDD中的应用研究

应用模糊聚类算法确定关键条件属性集，探索教师教学质量评估数据库中评估等级同评估项目之间的规则知识。     

数据采掘与知识发现综述

来自应用、社会、经济等各方面的迫切需求，以及不断升温的研究兴趣，使知识发现和数据采掘成为目前一个不断发展的领域。本文介绍了知识发现和数据采掘技术的产生背景、基本任务、方法及其应用，同时还简要介绍了目前已有的成熟的KDD系统及其将来的发展。     

Pruning Algorithms for Rule Learning

Pre-pruning and Post-pruning are two standard techniques for handling noise in decision tree learning. Pre-pruning deals with noise during learning, while post-pruning addresses this problem after an overfitting theory has been learned. We first review several adaptations of pre- and post-pruning techniques for separate-and-conquer rule learning algorithms and discuss some fundamental problems. The primary goal of this paper is to show how to solve these problems with two new algorithms that combine and integrate pre- and post-pruning.     

Advantages of decision lists and implicit negatives in Inductive Logic Programming

This paper demonstrates the capabilities offoidl, an inductive logic programming (ILP) system whose distinguishing characteristics are the ability to produce first-order decision lists, the use of an output completeness assumption as a substitute for negative examples, and the use originally motivated by the problem of learning to generate the past tense of English verbs; however, this paper demonstrates its superior performance on two different sets of benchmark ILP problems. Tests on the finite element mesh design problem show thatfoidl’s decision lists enable it to produce generally more accurate results than a range of methods previously applied to this problem. Tests with a selection of list-processing problems from Bratko’s introductory Prolog text demonstrate that the combination of implicit negatives and intensionality allowfoidl to learn correct programs from far fewer examples thanfoil. This research was supported by a fellowship from AT&T awarded to the first author and by the National Science Foundation under grant IRI-9310819. Mary Elaine Califf: She is currently pursuing her doctorate in Computer Science at the University of Texas at Austin where she is supported by a fellowship from AT&T. Her research interests include natural language understanding, particularly using machine learning methods to build practical natural language understanding systems such as information extraction systems, and inductive logic programming. Raymond Joseph Mooney: He is an Associate Professor of Computer Sciences at the University of Texas at Austin. He recerived his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 1988. His current research interests include applying machine to natural language understanding, inductive logic programming, knowledge-base and theory refinement, learning for planning, and learning for recommender systems. He serves on the editorial boards of the journalNew Generation Computing, theMachine Learning journal, theJournal of Artificial Intelligence Research, and the journalApplied Intelligence.     

一个通用型知识发现系统中数据预处理的实现

介绍了一个通用型知识发现系统的数据预处理部分的主要设计思想和实现方法。该系统的数据预处理部分运用了视图机制、主题管理、语言场理论等思想方法,对基于各种关系型数据库的知识发现工具的实现进行了有益的尝试,并对未来的工作做了展望。     

时序规则发现及其算法

该技术先把要考察的时间序列转换成子时间序列数据,然后对这些子时间序列数据进行挖掘, 从中提取关联规则。给出了时间序列关联规则的挖掘算法, 并举例说明该算法是有效的和可行的。     

多关系关联规则算法综述

多关系数据挖掘是借鉴ILP技术,并结合机器学习方法所提出的数据挖掘新课题。多关系关联规则是多关系方法在概念描述任务中最具代表性的研究方向之一,此类方法在发挥多关系方法的模式表达能力与利用背景知识能力的同时,借鉴成熟的关联规则方法的思想与优化策略,取得了较高的性能与表达复杂模式的能力,同时在面向复杂结构数据的应用中获得了较好的效果。在简述多关系方法的基础上,通过分析与比较目前具有代表性的多关系关联规则算法,总结了各算法的优势与不足,并指出了该领域目前的主要热点问题。     

Web挖掘在考试系统中应用

阐述了在考试系统的研究和应用中,利用Web挖掘技术,有效地对考生考试过程中的数据记录到日志文件中,并对日志文件进行有效地分析和挖掘;利用Apriori改进算法FT-树增长算法,找出对考试系统及基于Web的其他教学和管理工作 有指导作用的关联规律。     

CBRDI:一种基于范例推理的数据集成方法

设计并实现了基于范例推理的数据集成系统CBRDI,能够通过积累的领域知识即范例进行有效的数据集成操作。CBRDI采用框架网络表示范例,并通过聚类方法对源范例进行组织和索引,提高了范例搜索的效率。CBRDI系统实现简单,并具有较强的自学习的能力,推理效率高。