Randomized metric induction and evolutionary conceptual clustering for semantic knowledge bases

ABSTRACT

We present an evolutionary clustering method which can be applied to multi-relational knowledge bases storing semantic resource annotations expressed in the standard languages for the Semantic Web. The method exploits an effective and language-independent semi-distance measure defined for the space of individual resources, that is based on a finite number of dimensions corresponding to a committee of features represented by a group of concept descriptions (discriminating features). We show how to obtain a maximally discriminating group of features through a feature construction method based on genetic programming. The algorithm represents the possible clusterings as strings of central elements (medoids, w.r.t. the given metric) of variable length. Hence, the number of clusters is not needed as a parameter since the method can optimize it by means of the mutation operators and of a proper fitness function. We also show how to assign each cluster with a newly constructed intensional definition in the employed concept language. An experimentation with some ontologies proves the feasibility of our method and its effectiveness in terms of clustering validity indices.

REFERENCES

• 1: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The Description Logic Handbook, Cambridge University Press, New York, NY, 2007
• 2: Bezdek, J., and Pal, N. Some new indexes of cluster validity. IEEE Transactions on Systems, Man, and Cybernetics 28, 3(1998), 301--315.
• 3: Borgida, A., Walsh, T., and Hirsh, H. Towards measuring similarity in description logics. In Working Notes of the International Description Logics Workshop (Edinburgh, UK, 2005), I. Horrocks, U. Sattler, and F. Wolter, Eds., vol. 147 of CEUR Workshop Proceedings.
• 4: Burke, E., and Kendall, G., Eds. Search Methodologies. Springer, 2005, ch. 7. Simulated Annealing, pp. 187--210.
• 5: d'Amato, C., Fanizzi, N., and Esposito, F. Reasoning by analogy in description logics through instance-based learning. In Proceedings of Semantic Web Applications and Perspectives, 3rd Italian Semantic Web Workshop, SWAP2006 (Pisa, Italy, 2006), G. Tummarello, P. Bouquet, and O. Signore, Eds., vol. 201 of CEUR Workshop Proceedings.
• 6: Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. A density-based algorithm for discovering clusters in large spatial databases. In Proceedings of the 2nd Conference of ACM SIGKDD (1996), pp. 226--231.
• 7: Fanizzi, N., d'Amato, C., and Esposito, F. Induction of optimal semi-distances for individuals based on feature sets. In Working Notes of the 20th International Description Logics Workshop, DL2007 (Bressanone, Italy, 2007), D. Calvanese, E. Franconi, V. Haarslev, D. Lembo, B. Motik, A.-Y. Turhan, and S. Tessaris, Eds., vol. 250 of CEUR Workshop Proceedings.
• 8: Fanizzi, N., Iannone, L., Palmisano, I., and Semeraro, G. Concept formation in expressive Description Logics. In Proceedings of the 15th European Conference on Machine Learning, ECML2004 (2004), J.-F. Boulicaut, F. Esposito, F. Giannotti, and D. Pedreschi, Eds., vol. 3201 of LNAI, Springer, pp. 99--113.
• 9: Ghozeil, A., and Fogel, D. Discovering patterns in spatial data using evolutionary programming. In Genetic Programming 1996: Proceedings of the First Annual Conference (Stanford University, CA, USA, 1996), J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, Eds., MIT Press, pp. 521--527.
• 10: Maria Halkidi , Yannis Batistakis , Michalis Vazirgiannis, On Clustering Validation Techniques, Journal of Intelligent Information Systems, v.17 n.2-3, p.107-145, December 2001
• 11: Hall, L. O., Özyurt, I. B., and Bezdek, J. C. Clustering with a genetically optimized approach. IEEE Trans. Evolutionary Computation 3, 2 (1999), 103--112.
• 12: Hirano, S., and Tsumoto, S. An indiscernibility-based clustering method. In 2005 IEEE International Conference on Granular Computing (2005), X. Hu, Q. Liu, A. Skowron, T. Y. Lin, R. Yager, and B. Zhang, Eds., IEEE, pp. 468--473.
• 13: Luigi Iannone , Ignazio Palmisano , Nicola Fanizzi, An algorithm based on counterfactuals for concept learning in the Semantic Web, Applied Intelligence, v.26 n.2, p.139-159, April 2007 [doi>10.1007/s10489-006-0011-5]
• 14: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 15: Kaufman, L., and Rousseeuw, P. Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons, 1990.
• 16: Jörg-Uwe Kietz , Katharina Morik, A Polynomial Approach to the Constructive Induction of Structural Knowledge, Machine Learning, v.14 n.2, p.193-217, Feb. 1994 [doi>10.1023/A:1022626200450]
• 17: Lee, C.-Y., and Antonsson, E. K. Variable length genomes for evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO00 (2000), L. Whitley, D. Goldberg, E. Cantú-Paz, L. Spector, I. Parmee, and H.-G. Beyer, Eds., Morgan Kaufmann, p. 806.
• 18: Lehmann, J. Concept learning in description logics. Master's thesis, Dresden University of Technology, 2006.
• 19: Nasraoui, O., and Krishnapuram, R. One step evolutionary mining of context sensitive associations and web navigation patterns. In Proceedings of the SIAM conference on Data Mining (Arlington, VA, 2002), pp. 531--547.
• 20: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 21: Shan-Hwei Nienhuys-Cheng, Distances and Limits on Herbrand Interpretations, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.250-260, July 22-24, 1998
• 22: Zdzislaw Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Norwell, MA, 1992
• 23: Michèle Sebag, Distance Induction in First Order Logic, Proceedings of the 7th International Workshop on Inductive Logic Programming, p.264-272, September 17-20, 1997
• 24: Robert E. Stepp , Ryszard S. Michalski, Conceptual clustering of structured objects: a goal-oriented approach, Artificial Intelligence, v.28 n.1, p.43-69, Feb. 1986 [doi>10.1016/0004-3702(86)90030-5 ]
• 25: Pavel Zezula , Giuseppe Amato , Vlastislav Dohnal , Michal Batko, Similarity Search: The Metric Space Approach (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2005

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Measurement

Keywords:
conceptual clustering, description logics, evolutionary algorithms, genetic programming, metric learning, randomized optimization, unsupervised learning