Abstract
A model of learning from positive and negative examples is naturally described in terms of Formal Concept Analysis (FCA). In these terms, result of learning consists of two sets of intents (closed subsets of attributes): the first one contains intents that have only positive examples in the corresponding extents. The second one contains intents such that the corresponding extents contain only negative examples. On the one hand, we show how the means of FCA allows one to realize learning in this model with various data representation, from standard object-attribute one to that with labeled graphs. On the other hand, we use the language of FCA to give natural descriptions of some standard models of Machine Learning such as version spaces and decision trees. This allows one to compare several machine learning approaches, as well as to employ some standard techniques of FCA in the domain of machine learning. Algorithmic issues of learning with concept lattices are discussed. We consider applications of the concept-based learning, including Structure-Activity Relationship problem (in predictive toxicology) and spam filtering.
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
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I.: Fast Discovery of Association Rules. In: Advances in Knowledge Discovery and Data Mining, pp. 307–328 (1996)
Baader, F., Molitor, R.: Building and Structuring Description Logic Knowledge Spaces Using Least Common Subsumers and Concept Analysis. In: Ganter, B., Mineau, G.W. (eds.) ICCS 2000. LNCS (LNAI), vol. 1867, pp. 292–305. Springer, Heidelberg (2000)
Bahler, D., Bristol, D.W.: The induction of rules for predicting chemical cancerogenesis in rodents. In: Hunter, L., Searls, D., Shavlik, J. (eds.) Intelligent Systems for Molecular Biology, pp. 29–37. AAAI/MIT Press, Menlo Park, CA (1993)
Blinova, V.G.: Results of Application of the JSM-method of Hypothesis Generation to Problems of Analyzing the Relation “Structure of a Chemical Compound - Biological Activity”. Autom. Docum. Math. Ling. 29(3), 26–33 (1995)
Blinova, V.G., Dobrynin, D.A., Finn, V.K., Kuznetsov, S.O., Pankratova, E.S.: Toxicology analysis by means of the JSM-method. Bioinformatics 19, 1201–1207 (2003)
Botta, M., Giordana, A., Saitta, L., Sebag, M.: Relational Learning as Search in a Critical Region. Journal of Machine Learning Research 4, 431–463 (2003)
Budunova, A.P., Poroikov, V.V., Blinova, V.G., Finn, V.K.: The JSM-method of hypothesis generation: Application for analysis of the relation “Structure - hepatoprotective detoxifying activity”. Nauchno-Tekhnicheskaya Informatsiya (7), 12–15 (1993) (in Russian)
Carpineto, C., Romano, G.: A Lattice Conceptual Clustering System and Its Application to Browsing Retrieval. Machine Learning 24, 95–122 (1996)
Chaudron, L., Maille, N.: Generalized Formal Concept Analysis. In: Ganter, B., Mineau, G.W. (eds.) ICCS 2000. LNCS, vol. 1867, pp. 357–370. Springer, Heidelberg (2000)
Data Mining Cup (DMC), http://www.data-mining-cup.de
Dehaspe, L., De Raedt, L.: Mining Association Rules in Multiple Relations. In: Džeroski, S., Lavrač, N. (eds.) ILP 1997. LNCS (LNAI), vol. 1297, pp. 125–132. Springer, Heidelberg (1997)
De Raedt, L., van Laer, W.: Inductive Constraint Logic. In: Zeugmann, T., Shinohara, T., Jantke, K.P. (eds.) ALT 1995. LNCS, vol. 997, pp. 80–94. Springer, Heidelberg (1995)
Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P.: From Data Mining to Knowledge Discovery: An Overview. In: Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.) Advances in Knowledge Discovery and Data Mining, pp. 3–33. AAAI Press, Menlo Park (1996)
Férré, S., Ridoux, O.: A Logical Generalization of Formal Concept Analysis. In: Ganter, B., Mineau, G.W. (eds.) ICCS 2000. LNCS (LNAI), vol. 1867, Springer, Heidelberg (2000)
Férré, S., Ridoux, O.: The Use of Associative Concepts in the Incremental Building of a Logical Context. In: Priss, U., Corbett, D.R., Angelova, G. (eds.) ICCS 2002. LNCS (LNAI), vol. 2393, pp. 299–313. Springer, Heidelberg (2002)
Finn, V.K.: On Machine-Oriented Formalization of Plausible Reasoning in the Style of F. Backon–J. S. Mill. Semiotika Informatika 20, 35–101 (1983) (in Russian)
Finn, V.K.: Plausible Reasoning in Systems of JSM Type, Itogi Nauki i Tekhniki. Seriya Informatika 15, 54–101 (1991) (in Russian)
Ganascia, J.G.: CHARADE: A rule system learning system. In: Proc. of the 10th International Joint Conference on Artificial Intelligence (IJCAI 1987), Milan, Italy, August 23-28, pp. 345–347 (1987)
Ganter, B., Kuznetsov, S.: Formalizing Hypotheses with Concepts. In: Ganter, B., Mineau, G.W. (eds.) ICCS 2000. LNCS (LNAI), vol. 1867, pp. 342–356. Springer, Heidelberg (2000)
Ganter, B., Kuznetsov, S.: Pattern Structures and Their Projections, Proc. 9th Int. Conf. on Conceptual Structures. In: Delugach, H.S., Stumme, G. (eds.) ICCS 2001. LNCS (LNAI), vol. 2120, pp. 129–142. Springer, Heidelberg (2001)
Ganter, B., Kuznetsov, S.O.: Hypotheses and Version Spaces. In: Ganter, B., de Moor, A., Lex, W. (eds.) ICCS 2003. LNCS, vol. 2746, pp. 83–95. Springer, Heidelberg (2003)
Ganter, B., Reuter, K.: Finding all closed sets: a general approach. Order 8, 283–290 (1991)
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, Heidelberg (1999)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Grigoriev, P.A., Yevtushenko, S.A.: Elements of an Agile Discovery Environment. In: Grieser, G., Tanaka, Y., Yamamoto, A. (eds.) DS 2003. LNCS (LNAI), vol. 2843, pp. 309–316. Springer, Heidelberg (2003)
Grigoriev, P.A., Yevtushenko, S.A., Grieser, G.: QuDA, a data miner’s discovery enviornment, Tehcnical Report AIDA 03 06, FG Intellektik, FB Informatik, Technische Universitaet Darmstadt (September 2003), http://www.intellektik.informatik.tu-darmstadt.de/peter/QuDA.pdf
Gunter, C.A., Ngair, T.-H., Subramanian, D.: The Common Order-Theoretic Structure of Version Spaces and ATMSs. Artificial Intelligence 95, 357–407 (1997)
Helma, C., King, R.D., Kramer, S., Srinvasan, A.: Proc. of the Workshop on Predictive Toxicology Challegnge at the 5th Conference on Data Mining and Knowledge Discovery (PKDD 2001), Freiburg, Germany, September 7 (2001), http://www.predictive-toxicology.org/ptc/
Hereth, J., Stumme, G., Wille, R., Wille, U.: Conceptual Knowledge Discovery and Data Analysis. In: Ganter, B., Mineau, G.W. (eds.) ICCS 2000. LNCS (LNAI), vol. 1867, pp. 421–437. Springer, Heidelberg (2000)
Hirsh, H.: Generalizing Version Spaces. Machine Learning 17, 5–46 (1994)
Hirsh, H., Mishra, N., Pitt, L.: Version Spaces Without Boundary Sets. In: Proc. of the 14th National Conference on Artificial Intelligence (AAAI 1997), AAAI Press/MIT Press (1997)
King, R.D., Srinivasan, A., Dehaspe, L.: WARMR: A Data Mining tool for chemical data. J. Computer-Aided Molecular Design 15, 173–181 (2001)
Kramer, S.: Structural Regression Trees. In: Proc. 13th National Conference on Artificial Intelligence (AAAI 1996), pp. 812–819. AAAI Press, Menlo Park (1996)
Kuznetsov, S.O.: Interpretation on Graphs and Complexity Characteristics of a Search for Specific Patterns. Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.) (1), 23–27 (1989)
Kuznetsov, S.O.: JSM-method as a machine learning method. Itogi Nauki i Tekhniki, ser. Informatika 15, 17–50 (1991) (in Russian)
Kuznetsov, S.O., Finn, V.K.: On a model of learning and classification based on similarity operation. Obozrenie Prikladnoi i Promyshlennoi Matematiki 3(1), 66–90 (1996) (in Russian)
Kuznetsov, S.O.: Learning of Simple Conceptual Graphs from Positive and Negative Examples. In: Żytkow, J.M., Rauch, J. (eds.) PKDD 1999. LNCS (LNAI), vol. 1704, pp. 384–392. Springer, Heidelberg (1999)
Kuznetsov, S.O.: On Computing the Size of a Lattice and Related Decision Problems. Order 18(4), 313–321 (2001)
Kuznetsov, S.O., Obiedkov, S.A.: Comparing performance of algorithms for generating concept lattices. J. Exp. Theor. Artif. Intell. 14(2-3), 189–216 (2002)
Liquiere, M., Sallantin, J.: Structural Machine Learning with Galois Lattice and Graphs. In: Proc. Int. Conf. Machine Learning ICML 1998 (1998)
Maier, D.: The Theory of Relational Databases. Comput. Sci. Press, Potomac (1983)
Luxenburger, M.: Implications partielle dans un contexte. Math. Sci. Hum. (1991)
Njiwoua, P., Mefu Nguifo, E.: Forwarding the choice of bias. LEGAL-F: Using Feature Selection to Reduce Complexity of LEGAL. In: Proc. of BENELEARN 1997, pp. 89–98 (1997)
Mitchell, T.: Version Space: An Approach to Concept Learning, PhD thesis, Stanford University (1978)
Mitchell, T.: Generalization as Search. Artificial Intelligence 18(2) (1982)
Mitchell, T.: Machine Learning. The McGraw-Hill Companies, New York (1997)
Muggleton, S.: Inverse Entailment and Progol, New Generation Computing. Special Issue on Inductive Logic Programming 13(3-4), 245–286 (1995)
Nienhuys-Cheng, S.-H., de Wolf, R.: Foundations of Inductive Logic Programming. LNCS, vol. 1228. Springer, Heidelberg (1997)
Oosthuizen, G.D., McGregor, D.R.: Induction Through Knowledge Normalization. In: Proc. 8th. European Conference on Artificial Intelligence, Munich (1988)
Oosthuizen, G.D.: The use of of a lattice in Knowledge Processing, PhD Thesis, University of Strathclyde, Glasgow (1988)
Oosthuizen, G.D.: The application of Concept Lattices to Machine Learning, Univeristy of Pretoria, Tech. Rep. CSTR 94/01 (1994)
Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Efficient Minining of Association Rules Based on Using Closed Itemset Lattices. J. Inf. Systems 24, 25–46 (1999)
Popov, D.V., Blinova, V.G., Pankratova, E.S.: Drug deisgn. JSM-Method of hypothesis generation for predicting antitumor activity and toxic effects forecasts with respect to plant products. In: Proc. 5th Int. Conf. on Chemistry and Biotechnology of Biologically Active Natural Products, Varna (Bulgaria), September 18-23, vol. 2, pp. 437–440 (1989)
Quinlan, J.R.: Induction on Decision Trees. Machine Learning 1(1), 81–106 (1986)
Sahami, M.: Learning Classification Rules Using Lattices. In: Lavrac, N., Wrobel, S. (eds.) ECML 1995. LNCS, vol. 912, pp. 343–346. Springer, Heidelberg (1995)
Sebag, M.: Using Constraints to Building Version Spaces. In: de Raedt, L., Bergadano, F. (eds.) ECML 1994. LNCS, vol. 784, pp. 257–271. Springer, Heidelberg (1994)
Sebag, M.: Delaying the Choice of Bias: A Disjunctive Version Space Approach. In: Saitta, L. (ed.) Proc. of the 13th International Conference on Machine Learning, pp. 444–452. Morgan Kaufmann, San Francisco (1996)
Sebag, M., Rouveroil, C.: Tractable induction and classification in first-order logic via stochastic matching. In: Proc. 15th International Joint Conference on Artificial Intelligence, pp. 888–893. Morgan Kaufmann, San Francisco (1997)
Smirnov, E.N., Braspenning, P.J.: Version Space Learning with Instance-Based Boundary Sets. In: Prade, H. (ed.) Proc. of 13th European Conference on Artificial Intelligence, pp. 460–464. J. Wiley, Chichester (1998)
Srinivasan, S.H., Muggleton, M.J.E.: Theories for mutagenicity: a study in first order and feature-based induction. Artificial Intelligence 85, 277–299 (1996)
Stumme, G., Wille, R., Wille, U.: Conceptual Knowledge Discovery in Databases Using Formal Concept Analysis Methods. In: Żytkow, J.M. (ed.) PKDD 1998. LNCS (LNAI), vol. 1510, pp. 450–458. Springer, Heidelberg (1998)
Wille, R.: Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts. In: Rival, I. (ed.) Ordered Sets, pp. 445–470. Reidel, Dordrecht (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kuznetsov, S.O. (2004). Machine Learning and Formal Concept Analysis. In: Eklund, P. (eds) Concept Lattices. ICFCA 2004. Lecture Notes in Computer Science(), vol 2961. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24651-0_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-24651-0_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21043-6
Online ISBN: 978-3-540-24651-0
eBook Packages: Springer Book Archive