Constructing a Decision Tree for Graph-Structured Data and its Applications

Issue title: Advances in Mining Graphs, Trees and Sequences

Article type: Research Article

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

Affiliations: Institute of Scientific and Industrial Research, Osaka University, Japan. {warodom;yoshida;ohara;motoda}@ar.sanken.osaka-u.ac.jp | Division for Medical Informatics, Chiba University Hospital, Japan. yokoi@telemed.ho.chiba-u.ac.jp;takaba@ho.chiba-u.ac.jp

Note: [] Address for correspondence: Institute of Scientific and Industrial Research, Osaka University, 8-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

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.

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

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