Graph-Based Concept Discovery

Graph-Based Concept Discovery

Alev Mutlu (Kocaeli University, Turkey), Pinar Karagoz (Middle East Technical University, Turkey) and Yusuf Kavurucu (Turkish Naval Research Center Command, Turkey)
Copyright: © 2018 |Pages: 10
DOI: 10.4018/978-1-5225-2255-3.ch171


Multi-relational data mining (MRDM) is concerned with discovering hidden patterns from multiple tables in a relational database. One of the most commonly addressed tasks in MRDM is concept discovery in which the problem is inducing logical definitions of a specific relation, called target relation, in terms of other relations, called background knowledge. Inductive Logic Programming-based and graph-based approaches are two main competitors in this research. In this paper, we aim to introduce concept discovery problem and compare state-of-the-art methods in graph-based concept discovery by means of data representation, search method, and concept descriptor evaluation mechanism.
Chapter Preview


Multi-relational data mining is concerned with inducing patterns hidden in data stored in relational model, i.e. in a relational database. Traditional data mining algorithms are designed to work on flat files and cannot directly be work on such data. Two main directions in mining relational data are (i) converting the relational data into single table and then employing propositional learners (Kramer, Lavrač, & Flach, 2001), and (ii) developing new algorithms that can directly work on relational data (Džeroski, 2003). The main disadvantage of the first approach is the possible loss of information during propositionalization process. Most of the algorithms that belong to the second direction have their roots in ILP. ILP is concerned with inducing general theories from examples. It was first proposed for learning binary classification rules, but now can model more complex data mining problems.

Key Terms in this Chapter

Depth-First Search: Depth first search is a graph traversal method where a brunch is traversed as deep as possible without visiting any neighbor nodes.

Inductive Logic Programming: Given a set of observations, Inductive Logic Programming is concerned inducing general patterns that explain the observations.

Covering: Learning is an iterative process and at each rules possible with high accuracy and low coverage are induced. Removing learnt instances instances from the training set is called covering.

Breadth-First Search: Breadth-first search is a graph traversal method where firstly neighbor nodes are visited rather than sibling nodes.

Concept Discovery: Given a set of fact, concept discovery is the problem of learning definitions of a fact in terms of other facts.

Complete Chapter List

Search this Book: