Abstract
This paper presents a novel approach to Conceptual Clustering in First Order Logic (FOL) which is based on the assumption that candidate clusters can be obtained by looking for frequent association patterns in data. The resulting method extends therefore the levelwise search method for frequent pattern discovery. It is guided by a reference concept to be refined and returns a directed acyclic graph of conceptual clusters, possibly overlapping, that are subconcepts of the reference one. The FOL fragment chosen is \(\mathcal{AL}\)-log, a hybrid language that merges the description logic \(\mathcal{ALC}\) and the clausal logic Datalog. It allows the method to deal with both structural and relational data in a uniform manner and describe clusters determined by non-hierarchical relations between the reference concept and other concepts also occurring in the data. Preliminary results have been obtained on Datalog data extracted from the on-line CIA World Fact Book and enriched with a \(\mathcal{ALC}\) knowledge base.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berners-Lee, T., Hendler, J., Lassila, O.: The Semantic Web. Scientific American (May, 2001)
Bisson, G.: Conceptual Clustering in a First Order Logic Representation. In: Neumann, B. (ed.) ECAI 1992. Proceedings of the 10th European Conference on Artificial Intelligence, pp. 458–462. John Wiley & Sons, Chichester (1992)
Bournaud, I., Ganascia, J.-G.: Conceptual Clustering of Complex Objects: A Generalization Space based Approach. In: Ellis, G., Rich, W., Levinson, R., Sowa, J.F. (eds.) ICCS 1995. LNCS, vol. 954, pp. 173–187. Springer, Heidelberg (1995)
Ceri, S., Gottlob, G., Tanca, L.: Logic Programming and Databases. Springer, Heidelberg (1990)
Clerkin, P., Cunningham, P., Hayes, C.: Ontology discovery for the semantic web using hierarchical clustering. In: Stumme, G., Hotho, A., Berendt, B. (eds.) Working Notes of the ECML/PKDD-2001 Workshop on Semantic Web Mining, pp. 1–12 (2001)
Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: \(\mathcal{AL}\)-log: Integrating Datalog and Description Logics. Journal of Intelligent Information Systems 10(3), 227–252 (1998)
Fanizzi, N., Iannone, L., Palmisano, I., Semeraro, G.: Concept Formation in Expressive Description Logics. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) ECML 2004. LNCS (LNAI), vol. 3201, pp. 99–110. Springer, Heidelberg (2004)
Gennari, J.H., Langley, P., Fisher, D.: Models of incremental concept formation. Artificial Intelligence 40(1-3), 11–61 (1989)
Han, J., Fu, Y.: Mining multiple-level association rules in large databases. IEEE Transactions on Knowledge and Data Engineering 11(5) (1999)
Ketterlin, A., Gançarski, P., Korczak, J.J.: Conceptual Clustering in Structured Databases: A Practical Approach. In: Proceedings of the First International Conference on Knowledge Discovery and Data Mining, pp. 180–185 (1995)
Kietz, J.-U., Morik, K.: A polynomial approach to the constructive induction of structural knowledge. Machine Learning 14(1), 193–217 (1994)
Lisi, F.A., Esposito, F.: Efficient Evaluation of Candidate Hypotheses in \(\mathcal{AL}\)-log. In: Camacho, R., King, R., Srinivasan, A. (eds.) ILP 2004. LNCS (LNAI), vol. 3194, pp. 216–233. Springer, Heidelberg (2004)
Lisi, F.A., Malerba, D.: Ideal Refinement of Descriptions in \(\mathcal{AL}\)-log. In: Horváth, T., Yamamoto, A. (eds.) ILP 2003. LNCS (LNAI), vol. 2835, pp. 215–232. Springer, Heidelberg (2003)
Lisi, F.A., Malerba, D.: Inducing Multi-Level Association Rules from Multiple Relations. Machine Learning 55, 175–210 (2004)
Maedche, A., Zacharias, V.: Clustering Ontology-Based Metadata in the Semantic Web. In: Elomaa, T., Mannila, H., Toivonen, H. (eds.) PKDD 2002. LNCS (LNAI), vol. 2431, pp. 348–360. Springer, Heidelberg (2002)
Mannila, H., Toivonen, H.: Levelwise search and borders of theories in knowledge discovery. Data Mining and Knowledge Discovery 1(3), 241–258 (1997)
Michalski, R.S., Stepp, R.E.: Learning from observation: Conceptual clustering. In: Michalski, R.S., Carbonell, J.G., Mitchell, T.M. (eds.) Machine Learning: an artificial intelligence approach, vol. I. Morgan Kaufmann, San Mateo, CA (1983)
Nienhuys-Cheng, S.-H., de Wolf, R.: Foundations of Inductive Logic Programming. LNCS, vol. 1228. Springer, Heidelberg (1997)
Quan, T.T., Hui, S.C., Fong, A.C.M., Cao, T.H.: Automatic generation of ontology for scholarly semantic web. In: McIlraith, S.A., Plexousakis, D., van Harmelen, F. (eds.) ISWC 2004. LNCS, vol. 3298, pp. 726–740. Springer, Heidelberg (2004)
Schmidt-Schauss, M., Smolka, G.: Attributive concept descriptions with complements. Artificial Intelligence 48(1), 1–26 (1991)
Semeraro, G., Esposito, F., Malerba, D., Fanizzi, N., Ferilli, S.: A logic framework for the incremental inductive synthesis of Datalog theories. In: Fuchs, N.E. (ed.) LOPSTR 1997. LNCS, vol. 1463, pp. 300–321. Springer, Heidelberg (1998)
Stepp, R.E., Michalski, R.S.: Conceptual clustering of structured objects: a goal-oriented approach. Artificial Intelligence 28(1), 43–69 (1986)
Thomson, K., Langley, P.: Concept formation in structured domains. In: Fisher, D.H., Pazzani, M.J., Langley, P. (eds.) Concept Formation: Knowledge and Experience in Unsupervised Learning. Morgan Kaufmann, San Francisco (1991)
Vrain, C.: Hierarchical conceptual clustering in a first order representation. In: Michalewicz, M., Raś, Z.W. (eds.) ISMIS 1996. LNCS, vol. 1079, pp. 643–652. Springer, Heidelberg (1996)
Xiong, H., Steinbach, M., Ruslim, A., Kumar, V.: Characterizing pattern based clustering. Technical Report TR 05-015, Dept. of Computer Science and Engineering, University of Minnesota, Minneapolis, USA (2005)
Xiong, H., Steinbach, M., Tan, P.-N., Kumar, V.: Hicap: Hierarchical clustering with pattern preservation. In: Berry, M.W., Dayal, U., Kamath, C., Skillicorn, D.B. (eds.) Proc. of the 4th SIAM Int. Conference on Data Mining (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lisi, F.A. (2006). A Pattern-Based Approach to Conceptual Clustering in FOL. In: Schärfe, H., Hitzler, P., Øhrstrøm, P. (eds) Conceptual Structures: Inspiration and Application. ICCS 2006. Lecture Notes in Computer Science(), vol 4068. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11787181_25
Download citation
DOI: https://doi.org/10.1007/11787181_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35893-0
Online ISBN: 978-3-540-35902-9
eBook Packages: Computer ScienceComputer Science (R0)