HTILDE-RT: Um algoritmo para aprender Árvores de Regressão Relacionais em grandes conjuntos de dados
Resumo
Atualmente, organizações modernas armazenam seus dados sob a forma de bancos de dados relacionais que crescem numa velocidade superior à capacidade de hardware. Entretanto, extrair informações destas bases tornou-se crucial. Neste trabalho propomos o HTILDE-RT, um algoritmo capaz de aprender árvores de regressão relacionais em grandes massas de dados. O algoritmo é baseado no sistema ILP TILDE e no sistema proposicional VFDT. O algoritmo usa o limitante de Hoeffding para acelerar o aprendizado. Comparamos o HTILDE-RT com o TILDE-RT em dois conjuntos de dados grandes, com dois milhões de exemplos cada, obtendo tempos de aprendizado mais de três vezes mais rápidos sem diferenças significativas no coeficiente Pearson.
Referências
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.
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.
Publicado
19/07/2011
Como Citar
MENEZES, Glauber M. C.; ZAVERUCHA, Gerson.
HTILDE-RT: Um algoritmo para aprender Árvores de Regressão Relacionais em grandes conjuntos de dados. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 8. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 430-441.
ISSN 2763-9061.
