Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents a genetic programming-based symbolic regression approach to the construction of relational features in link analysis applications. Specifically, we consider the problems of predicting, classifying and annotating friends relations in friends networks, based upon features constructed from network structure and user profile data. We first document a data model for the blog service LiveJournal, and define a set of machine learning problems such as predicting existing links and estimating inter-pair distance. Next, we explain how the problem of classifying a user pair in a social network, as directly connected or not, poses the problem of selecting and constructing relevant features. We use genetic programming to construct features, represented by multiple symbol trees with base features as their leaves. In this manner, the genetic program selects and constructs features that may not have been originally considered, but possess better predictive properties than the base features. Finally, we present classification results and compare these results with those of the control and similar approaches.

REFERENCES

• 1: H. Bensusan and I. Kuscu. Constructive induction using genetic programming. In T. Fogarty and G. Venturini, editors, ICML'96, Evolutionary computing and Machine Learning Workshop, 1996.
• 2: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 3: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: M. Damo. The social net of digg: Structural analysis and prediction. Master's thesis, Milan Polytechnic, Milan, Italy, 2008.
• 6: Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In International Conference on Machine Learning (ICML), pages 148--156, 1996.
• 7: Lise Getoor, Link mining: a new data mining challenge, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959253]
• 8: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 9: W.H. Hsu, A. King, M.S. Paradesi, T. Pydimarri, and T. Weninger. Collaborative and structural recommendation of friends using weblog-based social network analysis. In AAAI Spring Symposium on Computational Approaches to Analyzing Weblogs (CAAW), volume SS-06-03, pages 55--60, Menlo Park, CA, 2006. The AAAI Press.
• 10: W.H. Hsu, A. King, M.S. Paradesi, T. Pydimarri, and T. Weninger. Structural link analysis from user profiles and friends networks: A feature construction approach. In International Conference on Weblogs and Social Media (ICWSM), pages 75--80, Boulder, CO, 2007.
• 11: D. Koller. Representation, reasoning and learning. IJCAI Computers and Thought Award Lecture, 2001.
• 12: Krzysztof Krawiec, Genetic Programming-based Construction of Features for Machine Learning and Knowledge Discovery Tasks, Genetic Programming and Evolvable Machines, v.3 n.4, p.329-343, December 2002 [doi>10.1023/A:1020984725014]
• 13: R.O.L. Breiman, J. Friedman and C. Stone. Classification and Regression Trees. Chapman and Hall, 1984.
• 14: S. Luke. An EC and GP system in Java, 2001. http://www.cs.umd.edu/projects/plus/ec/ecj/.
• 15: Miroslav Kubat , Robert Holte , Stan Matwin, Learning When Negative Examples Abound, Proceedings of the 9th European Conference on Machine Learning, p.146-153, April 23-25, 1997
• 16: C.J. Matheus and L.A. Rendell. Constructive induction on decision trees. In International Joint Conference on Artificial Intelligence IJCAI, volume 11, pages 645--650. Morgan Kaufmann, 1989.
• 17: C.J. Merz. Learning from Data: Artificial Intelligence and Statistics, chapter Dynamical Selection of Learning Algorithms, pages 289--303. Springer-Verlag, 1995.
• 18: R.S. Michalski. A theory and methodology of inductive learning. Artificial Intelligence, 20:111--161, 1983.
• 19: T.M. Mitchell. Generalization as search. Artificial Intelligence, 18(2):203--226, 1982.
• 20: Thomas M. Mitchell, Machine Learning, McGraw-Hill, Inc., New York, NY, 1997
• 21: Giulia Pagallo , David Haussler, Boolean Feature Discovery in Empirical Learning, Machine Learning, v.5 n.1, p.71-99, Mar. 1990 [doi>10.1023/A:1022611825350]
• 22: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 23: Larry Rendell , Raj Seshu, Learning hard concepts through constructive induction: framework and rationale, Computational Intelligence, v.6 n.4, p.247-270, Nov. 1990 [doi>10.1111/j.1467-8640.1990.tb00298.x]
• 24: Sebastian Thrun, Lifelong learning algorithms, Learning to learn, Kluwer Academic Publishers, Norwell, MA, 1998
• 25: Ricardo Vilalta , Youssef Drissi, A perspective view and survey of meta-learning, Artificial Intelligence Review, v.18 n.2, p.77-95, October 2002 [doi>10.1023/A:1019956318069]
• 26: S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, NY, 2007.
• 27: T. Weninger. Link discovery in very large graphs by constructive induction using genetic programing. Master's thesis, Kansas State University, Manhattan, KS, USA, December 2008.
• 28: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 29: David H. Wolpert, Stacked generalization, Neural Networks, v.5 n.2, p.241-259, 1992 [doi>10.1016/S0893-6080(05)80023-1]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation

General Terms:
Design, Experimentation

Keywords:
classifiation, genetic programming, machine learning