HTILDE-RT: An Algorithm for Learning Relational Regression Trees in Large Datasets

• Glauber M. C. Menezes UFRJ
• Gerson Zaverucha UFRJ

Abstract

Currently, modern organizations store their data under the form of relational databases which grow faster than hardware capacities. However, extracting information from such databases has become crucial. In this work we propose HTILDE-RT, an algorithm to learn relational regression trees efficiently from huge databases. It is based on the ILP system TILDE and the propositional system VFDT learner. The algorithm uses Hoeffding bound to scale up the learning process. We compared HTILDE-RT with TILDE-RT in two large datasets, each with two million examples, yielding more than three times faster learning times with no statistically significant difference in Pearson correlation coefficient.

References

Blockeel, H., Dehaspe, L., Demoen, B., Janssens, G., mon, J., and Vandecasteele, H. (2002). Improving the efficiency of inductive logic programming through the use of query packs. Journal of Artificial Intelligence Research, 16:135–166.

Blockeel, H. and Raedt, L. D. (1998). Top-down induction of first-order logical decision trees. Artificial Intelligence, 101(1-2):285–297.

Blockeel, H., Raedt, L. D., Jacobs, N., and Demoen, B. (1999). Scaling up inductive logic programming by learning from interpretations. Data Mining and Knowledge Discovery, 3(1):59–93.

Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Chapman & Hall, New York, NY.

Dietterich, T. G. (1998). Approximate statistical test for comparing supervised classification learning algorithms. Neural Computation, 10(7):1895–1923.

Domingos, P. and Hulten, G. (2000). Mining high-speed data streams. In Knowledge Discovery and Data Mining, pages 71–80.

H. Blockeel, L. D. J. R. J. S. A. V. A. C. V. and Fierens, D. (2005). The ACE Data Mining System - User’s Manual.

Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. 58:13–30.

Hulten, G., Spencer, L., and Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 97–106, San Francisco, CA. ACM Press.

Ikonomovska, E., Gama, J., and Džeroski, S. (2011). Learning model trees from evolving data streams. Data Mining and Knowledge Discovery, 23:128–168. DOI: 10.1007/s10618-010-0201-y.

Lopes, C. and Zaverucha, G. (2009). Htilde: scaling up relational decision trees for very large databases. In Proceedings of the 2009 ACM Symposium on Applied Computing (SAC), Honolulu, Hawaii, USA, pages 1475–1479.

Mitchell, T. (1997). Machine Learning. McGraw-Hill, New York.

Muggleton, S. (1991). Inductive logic programming. New Generation Computing, 8(4):295–318.

Nadeau, C. and Bengio, Y. (2003). Inference for the generalization error. Machine Learning, 52(3):239–281.

Vens, C., Ramon, J., and Blockeel, H. (2006). Remauve: A relational model tree learner. In Muggleton, S., Otero, R. P., and Tamaddoni-Nezhad, A., editors, ILP, volume 4455 of Lecture Notes in Computer Science, pages 424–438. Springer.

Witten, I. H. and Frank, E. (2005). Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann Series in Data Management Sys. Morgan Kaufmann, second edition.