Efficiency-conscious propositionalization for relational learning

Filip Železný

Kybernetika (2004)

  • Volume: 40, Issue: 3, page [275]-292
  • ISSN: 0023-5954

Abstract

top
Systems aiming at discovering interesting knowledge in data, now commonly called data mining systems, are typically employed in finding patterns in a single relational table. Most of mainstream data mining tools are not applicable in the more challenging task of finding knowledge in structured data represented by a multi-relational database. Although a family of methods known as inductive logic programming have been developed to tackle that challenge by immediate means, the idea of adapting structured data into a simpler form digestible by the wealth of AVL systems has been always tempting to data miners. To this end, we present a method based on constructing first-order logic features that conducts this kind of conversion, also known as propositionalization. It incorporates some basic principles suggested in previous research and provides significant enhancements that lead to remarkable improvements in efficiency of the feature-construction process. We begin by motivating the propositionalization task with an illustrative example, review some previous approaches to propositionalization, and formalize the concept of a first-order feature elaborating mainly the points that influence the efficiency of the designed feature-construction algorithm.

How to cite

top

Železný, Filip. "Efficiency-conscious propositionalization for relational learning." Kybernetika 40.3 (2004): [275]-292. <http://eudml.org/doc/33700>.

@article{Železný2004,
abstract = {Systems aiming at discovering interesting knowledge in data, now commonly called data mining systems, are typically employed in finding patterns in a single relational table. Most of mainstream data mining tools are not applicable in the more challenging task of finding knowledge in structured data represented by a multi-relational database. Although a family of methods known as inductive logic programming have been developed to tackle that challenge by immediate means, the idea of adapting structured data into a simpler form digestible by the wealth of AVL systems has been always tempting to data miners. To this end, we present a method based on constructing first-order logic features that conducts this kind of conversion, also known as propositionalization. It incorporates some basic principles suggested in previous research and provides significant enhancements that lead to remarkable improvements in efficiency of the feature-construction process. We begin by motivating the propositionalization task with an illustrative example, review some previous approaches to propositionalization, and formalize the concept of a first-order feature elaborating mainly the points that influence the efficiency of the designed feature-construction algorithm.},
author = {Železný, Filip},
journal = {Kybernetika},
keywords = {machine learning; inductive logic programming; propositionalization; machine learning; inductive logic programming; propositionalization},
language = {eng},
number = {3},
pages = {[275]-292},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Efficiency-conscious propositionalization for relational learning},
url = {http://eudml.org/doc/33700},
volume = {40},
year = {2004},
}

TY - JOUR
AU - Železný, Filip
TI - Efficiency-conscious propositionalization for relational learning
JO - Kybernetika
PY - 2004
PB - Institute of Information Theory and Automation AS CR
VL - 40
IS - 3
SP - [275]
EP - 292
AB - Systems aiming at discovering interesting knowledge in data, now commonly called data mining systems, are typically employed in finding patterns in a single relational table. Most of mainstream data mining tools are not applicable in the more challenging task of finding knowledge in structured data represented by a multi-relational database. Although a family of methods known as inductive logic programming have been developed to tackle that challenge by immediate means, the idea of adapting structured data into a simpler form digestible by the wealth of AVL systems has been always tempting to data miners. To this end, we present a method based on constructing first-order logic features that conducts this kind of conversion, also known as propositionalization. It incorporates some basic principles suggested in previous research and provides significant enhancements that lead to remarkable improvements in efficiency of the feature-construction process. We begin by motivating the propositionalization task with an illustrative example, review some previous approaches to propositionalization, and formalize the concept of a first-order feature elaborating mainly the points that influence the efficiency of the designed feature-construction algorithm.
LA - eng
KW - machine learning; inductive logic programming; propositionalization; machine learning; inductive logic programming; propositionalization
UR - http://eudml.org/doc/33700
ER -

References

top
  1. Agrawal R., Srikant R., Fast algorithms for mining association rules, In: Proc. 20th Internat. Conference Very Large Data Bases, VLDB, Morgan Kaufmann, xxxxxxx 1994 pp. 487–499 (1994) 
  2. Alphonse E., Rouveirol C., Lazy propositionalization for relational learning, In: Proc. 14th European Conference on Artificial Intelligence (ECAI’2000) (W. Horn, ed.), IOS Press 2000, pp. 256–260 
  3. Blatǎk J., Popelínský L., Feature construction with RAP, In: Proc. of the Work-in-Progress Track at the 13th Internat. Conference on Inductive Logic Programming. University of Szeged 2003 
  4. Clark P., Niblett T., 10.1007/BF00116835, Mach. Learning 3 (1989), 261–283 (1989) DOI10.1007/BF00116835
  5. Džeroski S., Numerical constraints and learnability in inductive logic programming, Ph.D. Thesis. Faculty of Electrical Engineering and Computer Science, University of Ljubljana 1995 
  6. Džeroski S., (eds.) N. Lavrač, Relational Data Mining, Springer–Verlag, Berlin 2001 Zbl1003.68039
  7. Emde W., Wettschereck D., Relational instance based learning, In: Machine Learning – Proc. 13th Internat. Conference on Machine Learning, Morgan Kaufmann, xxxxxxx 1996, pp. 122–130 (1996) 
  8. Hájek P., Mechanizing Hypothesis Formation, Springer–Verlag, Berlin 1966 Zbl0371.02002
  9. Kietz J. U., Some lower bounds for the computational complexity of inductive logic programming, In: Machine Learning: ECML-93, Proceedings of the European Conference on Machine Learning, volume 667, Springer–Verlag, Berlin 1993, pp. 115–123 (1993) MR1235394
  10. Knobbe A. J., Haas, M. de, Siebes A., Propositionalisation and aggregates, In: Proc. Fifth European Conference on Principles of Data Mining and Knowledge Disovery (PKDD). Springer–Verlag, Berlin 2001 Zbl1009.68749
  11. Kramer S., Lavrač, N., Flach P. A., Propositionalization Approaches to relational data mining, In: Relational Data Mining (N. Lavrač and S. Džeroski, eds.), Springer–Verlag, Berlin 2001 
  12. Krogel M. A., Rawles S., Železný F., Flach P. A., Lavrač, N., Wrobel S., Comparative evaluation of approaches to propositionalization, In: Proc. 13th Internat. Conference on Inductive Logic Programming. Springer–Verlag, Berlin 2003 
  13. Krogel M. A., Wrobel S., Transformation-based learning using multirelational aggregation, In: Proc. 11th Internat. Conference on Inductive Logic Programming (ILP), Springer–Verlag, Berlin 2001, pp. 142–155 Zbl1006.68519
  14. Lavrač N., Flach P. A., 10.1145/383779.383781, ACM Trans. Comput. Logic 2 (2001), 4, 458–494 DOI10.1145/383779.383781
  15. Lavrač N., Džeroski S., Inductive Logic Programming: Techniques and Applications, Ellis Horwood, 1993 Zbl0830.68027
  16. Lavrač N., Železný, F., Flach P. A., RSD: Relational subgroup discovery through first-order feature construction, In: Proc. 12th Internat. Conference on Inductive Logic Programming (ILP). Springer–Verlag, Berlin 2002 Zbl1017.68523
  17. Liu H., Motoda H., Feature Selection for Knowledge Discovery and Data Mining, Kluwer, Dordrecht 1998 Zbl0908.68127
  18. Maloberti J., Sebag M., Theta-subsumption in a constraint satisfaction perspective, In: Proc. 11th Internat. Conference on Inductive Logic Programming (ILP) (Lectures Notes in Artificial Intelligence 2157), Springer–Verlag, Berlin 2001, pp. 164–178 Zbl1006.68517MR1906956
  19. Muggleton S., 10.1007/BF03037227, New Generation Computing, Special issue on Inductive Logic Programming 13 (1995), 3–4, 245–286 (1995) DOI10.1007/BF03037227
  20. Pfahringer B., Holmes G., Propositionalization through stochastic discrimination, In: Proc. of the Work-in-Progress Track at the 13th Internat. Conference on Inductive Logic Programming. University of Szeged 2003 
  21. Quinlan J. Ross, C4, 5: Programs for Machine Learning. Morgan Kaufmann, xxxxxxx 1992 
  22. Sebag M., Rouveirol C., Tractable induction and classification in first-order logic via stochastic matching, In: Proc. 15th Internat. Joint Conference on Artificial Intelligence, Morgan Kaufmann, xxxxxxx 1997, pp. 888–893 (1997) 
  23. Srinivasan A., Muggleton S. H., Sternberg M. J. E., King R. D., 10.1016/0004-3702(95)00122-0, Artificial Intelligence 85 (1996), 1, 2, 277–299 (1996) DOI10.1016/0004-3702(95)00122-0
  24. Witten I. H., Frank E., Trigg L., Hall M., Holmes, G., Cunningham, Sally Jo, Weka: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, xxxxxxx 1999 
  25. Zucker J. D., Ganascia J. G., Representation changes for efficient learning in structural domains, In: Internat. Conference on Machine Learning 1996, pp. 543–551 (1996) 
  26. Železný F., Lavrač, N., Džeroski S., Constraint-based relational subgroup discovery, In: Proc. Multi-Relational Data Mining Workshop at KDD 2003, Washington 2003 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.