Open Access Open Access  Restricted Access Subscription or Fee Access

Classification in Multiple Heterogeneous Database Relations: A Tuple ID Predication Approach

K. Parish Venkata Kumar, K. Anji Reddy, J. Ravi

Abstract


Relational databases are the most fashionable repository for structured data, in a relational database many relations are linked together via E-R links. Multirelational classification is the procedure of building a classifier based on data stored in multiple relations and making predictions with it. Existing approaches of Inductive Logic Programming (recently, also known as Relational Mining) have proven effective with high accuracy in multirelational classification. Unfortunately, the most of them suffer from scalability problems with regard to the number of relations present in databases. In this paper, we propose a new approach, called Tuple ID Predication, which includes a set of novel and powerful methods for multirelational classification, including 1) tuple ID propagation, an efficient and flexible method for virtually joining relations, 2) new definitions for predicates and decision-tree nodes, which involve aggregated information to provide essential statistics for classification, and 3) a selective sampling method for improving scalability with regard to the number of tuples. Based on these techniques, we propose two scalable and accurate methods for multirelational classification: Tuple ID Predication Rule, a rule-based method and Mine-Tree, a decision-tree-based method. Our comprehensive experiments on both real and synthetic data sets demonstrate the high scalability and accuracy. It is very useful in effective decision making.

Keywords


Classification, Tuple ID, Data Mining, Decision Making, Relational Databases, Predication, Relations

Full Text:

PDF

References


A. Appice, M. Ceci, and D. Malerba, “Mining Model Trees: A Multi-Relational Approach,” Proc. 2003 Int’l Conf. Inductive Logic Programming, Sept. 2003.

J.M. Aronis, F.J. Provost, “Increasing the Efficiency of Data Mining Algorithms with Breadth-First Marker Propagation,” Proc. 2003 Int’l Conf. Knowledge Discovery and Data Mining, 1997.

H. Blockeel, L. De Raedt, and J. Ramon, “Top-Down Induction ofLogical Decision Trees,” Proc. 1998 Int’l Conf. Machine Learning (ICML ’98), Aug. 1998.

H. Blockeel, L. De Raedt, N. Jacobs, and B. Demoen, “Scaling UpInductive Logic Programming by Learning from Interpretations,” Data Mining and Knowledge Discovery, vol. 3, no. 1, pp. 59-93, 1999.

H. Blockeel, L. Dehaspe, B. Demoen, G. Janssens, J. Ramon, and H.Vandecasteele, “Improving the Efficiency of Inductive Logic Programming through the Use of Query Packs,” J. Artificial Intelligence Research, vol. 16, pp. 135-166, 2002.

C.J.C. Burges, “A Tutorial on Support Vector Machines for Pattern Recognition,” Data Mining and Knowledge Discovery, vol. 2, pp. 121- 168, 1998.

P. Clark and R. Boswell, “Rule Induction with CN2: Some Recent Improvements,” Proc. 1991 European Working Session on Learning (EWSL ’91), Mar. 1991. Sets,” Proc. 1998 Int’l Conf. Very Large Data Bases (VLDB ’98), Aug.1998.

N. Lavrac and S. Dzeroski, Inductive Logic Programming: Techniques and Applications. Ellis Horwood, 1994.

H. Liu, H. Lu, and J. Yao, “Identifying Relevant Databases for Multidatabase Mining,” Proc. Pacific-Asia Conf. Knowledge Discovery and Data Mining, 1998.

T.M. Mitchell, Machine Learning. McGraw Hill, 1997.

S. Muggleton, Inductive Logic Programming. New York: Academic Press, 1992.

S. Muggleton, “Inverse Entailment and Progol,” New Generation Computing, special issue on inductive logic programming, 1995.

S. Muggleton and C. Feng, “Efficient Induction of Logic Programs,” Proc. 1990 Conf. Algorithmic Learning Theory, 1990.

J. Neville, D. Jensen, L. Friedland, and M. Hay, “Learning Relational Probability Trees,” Proc. 2003 Int’l Conf. Knowledge Discovery and Data Mining, 2003.

A. Popescul, L. Ungar, S. Lawrence, and M. Pennock, “Towards Structural Logistic Rregression: Combining Relational and Statistical Learning,” Proc. Multi-Relational Data Mining Workshop, 2002.

J.R. Quinlan, C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.