Multi-Relational Model Tree Induction Tightly : Coupled with a Relational Database

• Autorzy: Appice, A. , Ceci, M. , Malerba, D.
• Języki publikacji: EN

Abstrakty

EN

Multi-Relational Data Mining (MRDM) refers to the process o f discovering implicit, previously unknown and potentially useful information fro m data scattered in multiple tables of a relational database. Following the mainstream of MRDM rese arch, we tackle the regression where the goal is to examine samples of past experience with known c ontinuous answers (response) and generalize future cases through an inductive process. Mr-S MOTI, the solution we propose, resorts to the structural approach in order to recursively partitio n data stored into a tightly-coupled database and build a multi-relational model tree which captures the l inear dependence between the response variable and one or more explanatory variables. The model tr ee is top-down induced by choosing, at each step, either to partition the training space or to intro duce a regression variable in the linear mod- els with the leaves. The tight-coupling with the database ma kes the knowledge on data structures (foreign keys) available free of charge to guide the search i n the multi-relational pattern space. Ex- periments on artificial and real databases demonstrate that in general Mr-SMOTI outperforms both SMOTI and M5’ which are two propositional model tree inducti on systems, and TILDE-RT which is a state-of-art structural model tree induction system

Słowa kluczowe

EN

data mining; mining methods and algorithms; regression; relational model trees; relational DBMS coupling; lookahead in model tree induction

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 3
• Strony: 193--224
• Opis fizyczny: Bibliogr. 41 poz., rys., tab.

Twórcy

autor

Appice, A.

• Dipartimento di Informatica, Università degli Studi Aldo Moro di Bari, Italy,

autor

Ceci, M.

• Dipartimento di Informatica, Università degli Studi Aldo Moro di Bari, Italy,

autor

Malerba, D.

• Dipartimento di Informatica, Università degli Studi Aldo Moro di Bari, Italy,

Bibliografia

• [1] Appice, A., Ceci, M., Malerba, D.: Mining Model Trees: A Multi-relational Approach, in: Proc. of the 13th International Conference on Inductive Logic Programming, ILP 2003, vol. 2835 of LNAI, Springer-Verlag, 2003, 4–21.
• [2] Appice, A., Ceci, M., Malerba, D.: MR-SMOTI: A Data Mining System for Regression Tasks Tightly-Coupled with a Relational Database, KDID (J.-F. Boulicaut, S. Dzeroski, Eds.), Rudjer Boskovic Institute, Zagreb, Croatia, 2003, ISBN 953-6690-34-9.
• [3] Atramentov, A., Leiva, H., Honovar, V.: A Multi-relational Decision Tree Learning Algorithm, in: Proceedings of the 13th International Conference on Inductive Logic Programming, ILP 2003, vol. 2835 of LNAI, Springer-Verlag, 2003, 38–56.
• [4] Blockeel, H.: Top-down induction of first order logical decision trees, Ph.D. Thesis, Department of Computer Science, Katholieke Universiteit, Leuven, Belgium, 1998.
• [5] Blockeel, H., Sebag, M.: Scalability and efficiency in multi-relational data mining, SIGKDD Explorations Newsletters, 5(1), 2003, 17–30.
• [6] Botta, M., Giordana, A., Saitta, L., Sebag, M.: Relational learning: Hard problems and phase transition, in: Congress of the Italian Association for Artificial Intelligence, AIIA 1999, vol. 1792 of LNAI, Springer-Verlag, 2000, 178–189.
• [7] Catlett, J.: On changing continuous attributes into ordered discrete attributes, Proceedings of the Fifth European Working Session on Learning, 1991.
• [8] Chaudhuri, S., Das, G., Narasayya, V., Datar, M., Motwani, R.: Overcoming Limitations of Sampling for Aggregation Queries, Proc. of the 17th International Conference on Data Engineering, ICDE 2001, IEEE Computer Society, 2001.
• [9] Draper, N. R., Smith, H.: Applied regression analysis, Wiley, 1982.
• [10] Driessens, K., Džeroski, S.: Combining model-based and instance-based learning for first order regression, Proceedings of the 22th International Conference on Machine Learning, ICML 2005, ACM, 2005.
• [11] Džeroski, S., Blockeel, H., Kramer, S., Kompare, B., Pfahringer, B., Van Laer,W.: Experiments in predicting biodegradability, in: International Workshop on Inductive Logic Programming ILP 1999, vol. 1634 of LNAI, Springer-Verlag, 1999, 80–91.
• [12] Džeroski, S., Todoroski, L., Urbancic, T.: Handling real numbers in inductive logic programming: A step towards better behavioural clones, in: European Conference of Machine Learning, ECML 1995, vol. 912 of LNAI, Springer-Verlag, 1995, 283–286.
• [13] Freitas, A. A., Lavington, S. H.: Using SQL primitives and parallel DB servers to speed up knowledge discovery in large relational databases, Proceedings of the 13th European Meeting on Cybernetics and Systems Research, Cybernetics and Systems 1996, 1996.
• [14] Helft, N.: Progress in Machine Learning, chapter Inductive generalization: a logical framework, Sigma Press, 1987, 149–157.
• [15] Ikonomovska, E., Džeroski, S.: Regression on evolving multi-relational data streams, Proceedings of the 2011 Joint EDBT/ICDT Ph.D. Workshop, PhD ’11, ACM, New York, NY, USA, 2011, ISBN 978-1-4503-0696-6.
• [16] Karalic, A.: Linear regression in regression tree leaves, Proceedings of International School for Synthesis of Expert Knowledge, ISSEK 1992, 1992.
• [17] Karalic, A., Bratko, I.: First Order Regression, Machine Learning, 26, 1997, 147–176.
• [18] Karwath, A., De Raedt, L.: Predictive Graph Mining, Proc. of the 2nd International Workshop on Mining Graphs, Trees and Sequences, 2004.
• [19] Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A. S.: The Web as a Graph: Measurements, Models and Methods, LNCS, 1627, 1999, 1–17.
• [20] Klosgen, W., May, M.: Spatial Subgroup Mining Integrated in an Object-Relational Spatial Database, in: Proc. of the 6th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2002, vol. 2431 of LNAI, Springer-Verlag, 2002, 275–286.
• [21] Kramer, S.: Structural regression trees, Proc. of the National Conference on Artificial Intelligence, 1996.
• [22] Kramer, S.: Relational Learning vs. Propositionalization: Investigations in Inductive Logic Programming and Propositional Machine Learning, Ph.D. Thesis, Vienna University of Technology, Vienna, Austria, 1999.
• [23] Kramer, S.: Demand-Driven Construction of Structural Features in ILP, in: Proc. of the 11th International Conference on Inductive Logic Programming, ILP 2001, vol. 2157 of LNAI, Springer-Verlag, 2001, 132–141.
• [24] Kramer, S., Lavrač, N., Flach, P.: Relational Data Mining, chapter Propositionalization Approaches to Relational Data Mining, LNAI, Springer-Verlag, 2001, 262–291.
• [25] Kramer, S., Widmer, G.: Relational Data Mining, chapter Inducing Classification and Regression Trees in First Order Logic, LNAI, Springer-Verlag, 2001, 140–156.
• [26] Lavrač, N., Džeroski, S.: Inductive Logic Programming: Techniques and Applications, Ellis Horwood, 1994.
• [27] Leiva, H. A.: MRDTL: A multi-relational decision tree learning algorithm, Master Thesis, University of Iowa, 2002.
• [28] Malerba, D.: A relational perspective on spatial data mining, IJDMMM, 1(1), 2008, 103–118.
• [29] Malerba, D., Esposito, F., Ceci, M., Appice, A.: Top Down Induction of Model Trees with Regression and Splitting Nodes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(5), 2004, 612–625.
• [30] Mehta, M., Agrawal, R., Rissanen, J.: SLIQ: A fast scalable classifier for data mining, Proc. of the 5th International Conference on Extending Database Technology, 1996.
• [31] Morik, K., Scholz, M.: The MiningMart Approach to Knowledge Discovery in Databases, Handbook of Intelligent IT, 2003.
• [32] Ordonez, C., Cereghini, P.: SQLEM: Fast Clustering in SQL using the EM Algorithm, Proc. of the ACM SIGMOD 2000, 29, 2000.
• [33] Page, D., Craven, M.: Biological applications of multi-relational data mining, SIGKDD Explor. Newsl, 5(1), 2003, 69–79, ISSN 1931-0145.
• [34] Raedt, L. D.: Attribute-Value Learning Versus Inductive Logic Programming: The Missing Links (Extended Abstract), Proc. of the 8th International Workshop on Inductive Logic Programming, ILP 1998, 1446, Springer-Verlag, 1998, ISBN 3-540-64738-4.
• [35] Raedt, L. D., Idestam-Almquist, P., Sablon, G.: Theta-Subsumption for StructuralMatching, Proc. of the 9th European Conference on Machine Learning, ECML 1997, 1224, Springer-Verlag, 1997, ISBN 3-540-62858-4.
• [36] Sarawagi, S., Thomas, S., Agrawal, R.: Integrating Mining with Relational Database Systems: Alternatives and Implications, Proc. of ACM SIGMOD 1998, 1998.
• [37] Sattler, K., Dunemann, O.: SQL Database Primitives for Decision Tree Classifiers, Proc. of the 10th ACM International Conference on Information and Knowledge Management, ACM CIKM 2001, 2001.
• [38] Scott, J. P.: Social Network Analysis: A Handbook, Sage Publications, 2005.
• [39] Srinivasan, A., Muggleton, S., King, R. D., Sternberg, M. J. E.: Mutagenesis: ILP experiments in a nondeterminate biological domain, Proc. of the 4th Inductive Logic Programming Workshop, ILP 1994, GMDStudien, 1994.
• [40] Van Laer,W., De Raedt, L.: Relational Data Mining, chapter How to Upgrade Propositional Learners to First Order logic: A Case Study, LNAI, Springer-Verlag, 2001, 235–261.
• [41] Vens, C., Ramon, J., Blockeel, H.: ReMauve: A Relational Model Tree Learner, Proc. of the 16th International Conference on Inductive Logic Programming, ILP 2006, 4455, Springer-Verlag, 2006, ISBN 978-3-540-73846-6.

Identyfikatory

DOI

10.3233/FI-2014-969