Aggregation-based feature invention and relational concept classes

ABSTRACT

Model induction from relational data requires aggregation of the values of attributes of related entities. This paper makes three contributions to the study of relational learning. (1) It presents a hierarchy of relational concepts of increasing complexity, using relational schema characteristics such as cardinality, and derives classes of aggregation operators that are needed to learn these concepts. (2) Expanding one level of the hierarchy, it introduces new aggregation operators that model the distributions of the values to be aggregated and (for classification problems) the differences in these distributions by class. (3) It demonstrates empirically on a noisy business domain that more-complex aggregation methods can increase generalization performance. Constructing features using target-dependent aggregations can transform relational prediction tasks so that well-understood feature-vector-based modeling algorithms can be applied successfully.

REFERENCES

• 1: J. M. Aronis and F. J. Provost. Efficiently constructing relational features from background knowledge for inductive machine learning. In U. Fayyad and R. Uthurusamy, editors, In Working Notes of the AAAI-94 Workshop on Knowledge Discovery in Databases (KDD-94), pages 347--358, 1994.
• 2: Hendrik Blockeel , Luc De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence, v.101 n.1-2, p.285-297, May 1998 [doi>10.1016/S0004-3702(98)00034-4]
• 3: A. P. Bradley. The use of the area under the ROC curve in the evaluation of machine learning algorithms. In Pattern Recognition, volume 30(7), pages 1145--1159, 1997.
• 4: Luc De Raedt , Hendrik Blockeel , Luc Dehaspe , Wim Van Laer, Three companions for data mining in first order logic, Relational Data Mining, Springer-Verlag New York, Inc., New York, NY, 2001
• 5: J. Fürnkranz. Dimensionality reduction in ILP: A call to arms. In Raedt L. and Muggleton S., editors, Proceedings of the IJCAI-97 Workshop on Frontiers of Inductive Logic Programming, 1997.
• 6: David D. Jensen , Paul R. Cohen, Multiple Comparisons in Induction Algorithms, Machine Learning, v.38 n.3, p.309-338, March 2000 [doi>10.1023/A:1007631014630]
• 7: D. Jensen and J. Neville. Data mining in social networks. In Dynamic Social Networks Modeling and Analysis, 2002.
• 8: David Jensen , Jennifer Neville, Linkage and Autocorrelation Cause Feature Selection Bias in Relational Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.259-266, July 08-12, 2002
• 9: Mathias Kirsten , Stefan Wrabel , Tamá Horváth, Distance based approaches to relational learning and clustering, Relational Data Mining, Springer-Verlag New York, Inc., New York, NY, 2001
• 10: Arno J. Knobbe , Marc de Haas , Arno Siebes, Propositionalisation and Aggregates, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.277-288, September 03-05, 2001
• 11: Daphne Koller , Avi Pfeffer, Probabilistic frame-based systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.580-587, July 1998, Madison, Wisconsin, United States
• 12: Stefan Kramer , Nada Lavrač , Peter Flach, Propositionalization approaches to relational data mining, Relational Data Mining, Springer-Verlag New York, Inc., New York, NY, 2001
• 13: Stefan Kramer , Bernhard Pfahringer , Christopher Helma, Stochastic Propositionalization of Non-determinate Background Knowledge, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.80-94, July 22-24, 1998
• 14: P. C. Mahalanobis. On the generalized distance in statistics. In Proc. Natl. Institute of Science of India, volume 12, pages 49--55, 1936.
• 15: Timothy Masters, Practical neural network recipes in C++, Academic Press Professional, Inc., San Diego, CA, 1993
• 16: Eric Charles Mccreath, Induction in first order logic from noisy training examples and fixed example set sizes, 2000
• 17: S. H. Muggleton. Cprogol4.4: a tutorial introduction. In Saso Dzeroski and Nada Lavrac, editors, Relational Data Mining, pages 105--139. Springer-Verlag, 2001.
• 18: S. H. Muggleton and L. DeRaedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19 & 20:629--680, May 1994.
• 19: A. Popescul, L. H. Ungar, S. Lawrence, and D. M. Pennock. Structural logistic regression: Combining relational and statistical learning. In Proceedings of the Workshop on Multi-Relational Data Mining (MRDM-2002), pages 130--141. University of Alberta, Edmonton, Canada, July 2002.
• 20: F. Provost, C. Perlich, and S. Macskassy. Relational learning problems and simple models. In Lise Getoor and David Jensen, editors, Working Notes of the IJCAI-2003 Workshop on Learning Statistical Models from Relational Data, pages 116--120, 2003.
• 21: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 22: J. Ross Quinlan , R. Mike Cameron-Jones, FOIL: A Midterm Report, Proceedings of the European Conference on Machine Learning, p.3-20, April 05-07, 1993
• 23: Murray Smith, Neural Networks for Statistical Modeling, Thomson Learning, 1993
• 24: Ashwin Srinivasan , Ross D. King, Feature Construction with Inductive Logic Programming: A Study of Quantitative Predictions of Biological Activity by Structural Attributes, Selected Papers from the 6th International Workshop on Inductive Logic Programming, p.89-104, August 26-28, 1996

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Keywords:
aggregation, constructive induction, feature construction, propositionalization, relational learning