Classi cation Methods Based on Formal Concept Analysis

Abstract

Formal Concept Analysis (FCA) provides mathematical models for many domains of computer science, such as classi cation, categorization, text mining, knowledge management, software development, bioinformatics, etc. These models are based on the mathematical properties of concept lattices. The complexity of generating a concept lattice puts a constraint to the applicability of software systems. In this paper we report on some attempts to evaluate simple FCA-based classi cation algorithms. We present an experimental study of several benchmark datasets using FCA-based approaches. We discuss di culties we encountered and make some suggestions concerning concept-based classi cation algorithms.

Keywords

• Classi cation
• pattern recognition
• data mining
• formal concept analysis
• biclustering

Introduction

Supervised classi cation consists in building a classi er from a set of examples labeled by their classes or precedents (learning step) and then predicting the class of new examples by using the generated classi ers (classi cation step). Document classi cation is a sub- eld of information retrieval. Documents may be classi ed according to their subjects or according to other attributes (such as document type, author, year of publication, etc.). Mostly, document classi cation algorithms are based on supervised classi cation. Algorithms of this kind can be used for text mining, automatical spam- ltering, language identi cation, genre classi cation, text mining. Some modern data mining methods can be naturally described in terms of lattices of closed sets, i.e., concept lattices [ 1 ], also called Galois lattices. An important feature of FCA-based classi cation methods do not make any assumptions regarding statistical models of a dataset. Biclustering [ 9, 10 ] is an approach related to FCA: it proposes models and methods alternative to classical clustering approaches, being based on object similarity expressed by common sets of attributes. There are several FCA-based models for data analysis and knowledge processing, including classi cation based on learning from positive and negative examples [ 1, 2 ].

In our previous work [ 15 ] the e ciency of a simple FCA-based binary classi cation algorithm was investigated. We tested this method on di erent problems with numerical data and found some di culties in its application. The main purpose of this paper is to investigate critical areas of the FCA method for better understanding of its features. Several advices for developers are also provided. We test hypothesis-based classi cation algorithm and our modi ed FCA-based method on 8 benchmarks. We describe our experiments and compare the performance of FCA-based algorithms with that of SVM-classi cation [ 16 ]. 2

De nitions

Formal Concept Analysis. In what follows we keep to standard FCA de nitions from [ 1 ]. Let G and M be sets, called set of objects and set of attributes, respectively. Let I G M be a binary relation. The triple K = (G; M; I) is called a formal context. For arbitrary A G and B M the mapping (:)0 is de ned as follows:

A0 = fm 2 M j 8g 2 A(gIm)g; B0 = fg 2 G j 8m 2 B(gIm)g: (1) This pair of mappings de nes a Galois connection between the sets 2G and 2M partially ordered by the set-theoretic inclusion. Double application of the operation ( )0 is a closure operator on the union of the sets 2G and 2M . Let a context K be given. A pair of subsets (A; B), such that A G, B M , A0 = B, and B0 = A is called a formal concept of K with formal extent A and formal intent B. The extent and the intent of a formal concept are closed sets. FCA in learning and classi cation. Here we keep to de nitions from [ 2 ] and [ 3 ]. Let K = (G; M; I) be a context and w 62 M a target attribute. In FCA terms, the input data for classi cation may be described by three contexts w.r.t. w: the positive context K+ = (G+; M; I+), the negative context K = (G ; M; I ) , and the unde ned context K = (G ; M; I ) [ 2 ]. G ; G+ and G are sets of positive, negative and unde ned objects respectively, I G M , where 2 f ; +; g are binary relations that de ne structural attributes. Operators ( )0 in these contexts are denoted by A+; A ; A , respectively. For short we write g0; g00; g+; g ; g instead of fgg0; fgg00; fgg+; fgg ; fgg , respectively. A formal concept of a positive context is called a positive concept. Negative and unde ned concepts, as well as extents and intents of the contexts K and K , are de ned similarly. A positive formal intent B+ of (A+; B+) 2 K+ is called a positive or (+) | prehypothesis if is not the formal intent of any negative concept, and it is called a positive or (minimal) (+) | hypothesis if it is not a subset of the intent g for some elementary concept (g; g ) for a negative example g; otherwise it is called a false (+)-generalization.

Negative (or (-) |) prehypotheses, hypotheses, and false generalizations are de ned similarly. The de nitions imply that a hypothesis is also a prehypothesis. Hypotheses are used to classify unde ned examples from the set G . If unclassi ed object g contains a positive but no negative hypothesis, it is classi ed positively, similar for negative. No classi cation happens if the formal intent g does not contain any subsets of either positive or negative hypotheses (insu cient data) or contains both a positive and a negative hypothesis (inconsistent data). Biclustering. The particular case of biclustering [10{12] we have considered is a development of the FCA-based classi cation method. Using FCA methods, we can construct a hierarchical structure of biclusters that re ects the taxonomy of data. Density of bicluster (A; B) of the formal context K = (G; M; I) is de ned as (A; B) = jI \ fA Bgj=(jAj jBj). Specify some value min 2 [0; 1]. The bicluster (A; B) is called dense if (A; B) min. Stability index of a concept (A; B) is given by (A; B) = jC(A; B)j=2jAj; where C(A; B) is the union of the sets C A such that C = B0 [ 13, 21 ]. Biclusters, as well as dense and stable formal concepts (i.e., concepts having stability above a xed threshold), are used to generate hypotheses for clustering problems [ 13 ]. 3

Basic Classi cation Algorithms

Several FCA-based classi cation methods are known [ 19, 15 ]: GRAND [ 31, 17 ], LEGAL [ 26 ], GALOIS [ 25 ], RULELEARNER [ 24 ], CIBLe [ 30 ], CLNN&CLNB [ 27 ], NAVIGALA[ 28 ], CITREC [ 29, 17 ] and classi cation method based on hypotheses [ 8, 7, 2, 3 ]. There are several categories of FCA-based classi cation methods: 1. Hypothesis-based classi cation using the general principle described in

Section 2. 2. Concept lattice based classi cation. A concept lattice can be seen as a search-space in which one can easily pass from a level to another one. The navigation can e.g. start from the top concept with the least intent. Then one can progress concept by concept by taking new attributes and reducing the set of objects. Many systems use lattice-based classi cation, such as GRAND [ 31, 17 ], RULEARNER [ 24 ], GALOIS [ 25 ], NAVIGALA [ 28 ] and CITREC [ 29, 17 ]. The common constraint of these systems is the exponential algorithmic complexity of generating a lattice. For this reason, some systems search in a subset of the set of all concepts. 3. Classi cation based on Galois sub-hierarchies. Systems like CLNN& CLNB [ 27 ], LEGAL [ 26 ] and CIBLe [ 30 ] build Galois sub-hierarchy (ordered set of object and attribute concepts), which drastically reduces algorithmic complexity. 4. Cover-based classi cation. A concept cover is a part of the lattice containing only pertinent concepts. The construction of a cover concept is based on heuristic algorithms which reduce the complexity of learning. The concepts are extracted one by one. Each concept is given by a local optimization of a measure function that de nes pertinent concepts. IPR (Induction of Product Rules) [ 32 ] was the rst method generating a concept cover. Each pertinent concept induced by IPR is given by a local optimization of entropy function. The sets of pertinent generated concepts are sorted from the more pertinent to the less pertinent and each pertinent concept with the associated class gives a classi cation rule.

Classi cation Experiments with Benchmarks

4.1

A Hypothesis-Based Algorithm

The method for constructing concept-based hypotheses described above inspired the following binary classi cation algorithm [ 15 ]. The main steps of the algorithm are as follows: 1. Data binarization. The situation where the attributes are non-binary, but a classi cation method is designed for binary data brings up the problem of attribute binarization, or scaling. This problem is very di cult and a lot of papers are devoted to it. Scaling problem arises also when we use FCA for object classi cation. For speci c tasks scaling is usually carried out empirically by repeatedly solving the problem of classi cation on precedents. It is clear, however, that in a couple of "scaling{recognition method" the determining factor is exactly scaling. Indeed, in the event of its successful application a 'good' transformation of the feature space will be obtained and almost any recognition algorithm will show good results in that space. So that the problem of scaling is a nonspeci c for FCA-recognition methods and the current level of development of these methods unable to point the best technique of scaling focused on their use. That is why our work is not focused on this problem and we use a simple scaling, which, we believe, allowed more clearly to identify the features of FCA-classi cation methods. Hence, we just normalized all attributes to [ 0,1 ] interval and than applied interval-based nominal scaling. The number of intervals is xed and equals 10. The size of intervals is also xed and equals 0.1. 2. Hypothesis generation and classi cation. Algorithm searches common attributes for all objects from the rst class (second class), which are not observed for any objects from the second class ( rst class). Obtained sets of attributes (hypothesis) are used to classify unde ned objects.

The algorithm has been tested on numerical benchmarks. The data for the rst four problems is taken from the UCI Machine Learning Repository1. Problem 5 (Two Norm) involving the separation of two normal 20-dimensional distributions is taken from the University of Toronto site2; the CART classi cation algorithm [ 22 ] produced for this problem an error rate of 22:1% with a training sample of 300 precedents, which is almost a factor of 10 higher than the theoretical minimum for the ideal classi er | the Fisher discriminant function. Problems 6 (Lung Cancer), 7 (Cirrhosis), and 8 (Cloud Seeding) are taken from the StatLib site3. The considered problems come from di erent speci c research areas. For example, in the Liver Disorders problem, the objects are datasets obtained from the tests of six patients. The training sample consists of 345 precedents divided into positive and negative classes with respect to the 1 http://archive.ics.uci.edu/ml 2 http://www.cs.toronto.edu/ delve/data/twonorm/desc.html 3 http://lib.stat.cmu.edu/datasets, pages /veteran, /pbc, and /cloud, respectively target attribute \presence of liver disorder". The experiment results obtained for various problems by using leave-one-out cross-validation are presented below (Table 1). In the table heading, n is the number of attributes, l is the number of objects (the size of the training sample),err is the classi cation error rate and lc is the number of classi ed objects ( l lc = the number of failed classi cations).

Problem n l lc err 1. Liver Disorders 6 345 20 15.00% 2. Glass identi cation 9 146 25 20.00% 3. Wine 13 130 47 08.50% 4. Wine quality 11 310 51 09.80% 5. Two norm 20 354 109 07.30% 6. Lung cancer 8 137 9 11.10% 7. Cirrhosis 19 276 29 34.48% 8. Cloud-seeding 5 108 6 50.00%

The algorithm was updated with the following modi cations in de nitions of hypothesis and classi cation: 1. Hypothesis modi cation: attributes observed for "almost" all objects of the particular class were added to the hypothesis. It was ensured that the ratio of objects which did not comply with the hypothesis in the same class did not exceed the value P (a new algorithm parameter) and obviously there was no guarantee that the hypothesis is not contained in descriptions of objects of the opposite class. 2. Introduction of an inter-object metric and modi cation of the classi cation procedure: the "distance" between objects increases as they reveal di erence in a larger number of coordinates. We compute the distance of the object being classi ed by positive and negative hypotheses and normalize it by the number of attributes (or 1s in binary represenation) in each hypothesis. The object is classi ed to the nearest class in contexts of the metric de ned above. 3. Attribute weighting: an attribute is assigned a weight which increases with the number of 1s in the corresponding column.

The modi ed algorithm was applied to the considered problems. The experimental results for P = 0:2 are given in Table 2. 4.2

Classi cation Using Biclustering

Biclustering can be used for classi cation upon data scaling. For this purpose we select informative objects which are included in biclusters with density greater than threshold min. Hypotheses are generated using these objects. This approach avoids noise e ects during learning step [ 15 ]. The di erence between

Problem n l lc err 1. Liver Disorders 6 345 79 39.2% 2. Glass identi cation 9 146 64 25.00% 3. Wine 13 130 87 14.9% 4. Wine quality 11 310 142 17.60% 5. Two norm 20 354 224 15.10% 6. Lung cancer 8 137 36 36.10% 7. Cirrhosis 19 276 136 33.30% 8. Cloud-seeding 5 108 37 43.20% proposed algorithm and simple FCA algorithm resides only in the second step: hypotheses are now generated using only informative objects selected by biclustering. The method has two adjustable parameters: the bicluster density min and the ratio P of objects which do not satisfy classical hypotheses. The parameter min a ects the generation of hypotheses. If its value is too small, hypothesis generation is tainted by noisy attributes and outliers. If its value is too large, the hypothesis will have to meet excessively stringent requirements. It may be e cient to use a range of values for min and thus focus on the main objects, skipping the marginal ones. This method has been tested, but it failed to produce a signi cant improvement of the classi cation performance, which will be later explained by the speci c features of the particular problem.

The parameter P a ects the ratio of objects which do not satisfy the hypotheses of the same class. When the parameter P is close to zero, hypotheses are generated in accordance with the classical de nitions: they include only the attributes that are observed for all the objects of the given class. The di culty is that hypotheses may become "non-representative" for the given class. If the parameter P is taken too large, the hypotheses will require that the control object has a large number of attributes, which again may impose an excessively stringent requirement on hypotheses. In a certain sense, this is the well-known over tting e ect often observed in pattern recognition.

The experimental results assessed by leave-one-out cross-validation are presented in Table 3 and Table 4. In the table heading, n is the number of attributes, l is the number of objects (the size of the training sample). The columns present the solution results obtained with the algorithm parameters (the threshold and the proportion P ) optimized by two criteria: the classi cation error rate err (Table 3) and the number of classi ed objects lc ( l lc = the number of failed classi cations) (Table 4). The local optimization of the algorithm parameters was carried out by the GaussSeidel method, their optimal values min and P are shown together with err.

According to the experimental results, the lower is the error rate, the smaller is the number of classi ed objects. We can construct an algorithm with zero error rate, but the ratio of classi ed objects will be also small. We apply such an algorithm for all considered objects. The results are shown in Table 5, where Problem n l lc err min P 1. Liver Disorders 6 345 22 13.6% 0.30 0.01 2. Glass identi cation 9 146 28 10.00% 0.15 0.05 3. Wine 13 130 76 02.00% 0.25 0.05 4. Wine quality 11 310 83 08.40% 0.25 0.05 5. Two norm 20 354 206 12.10% 0.15 0.15 6. Lung cancer 8 137 18 05.50% 0.01 0.01 7. Cirrhosis 19 276 33 21.00% 0.05 0.05 8. Cloud-seeding 5 108 7 28.00% 0.15 0.05 lc is the number of classi ed objects (the ratio is in brackets). The e ciency of FCA-based algorithm was compared with that of classical SVM-algorithm [ 16 ]. Each dataset was divided into training sample (80% of objects) and test sample (20% of objects). Table 5 SV M err shows the error rate of the SVM-algorithm, SV M err on lc is the error rate on objects which were classi ed by the rigorous FCA-based method. Zero error rate was attained with classical hypotheses (P =0) from objects with low density ( min 0:25). This rigorous algorithm can be applied to problems with high error costs. It is more likely to refuse classi cation than make wrong decisions.

Conclusions

FCA provides a convenient tool for formalizing symbolic machine learning and classi cation models. We studied hypothesis-based classi cation in di erent areas without special modi cations for each dataset, using a simple binarization (scaling) of numerical data. Our results suggest the following conclusions: 1. Application of biclustering with parameter optimization made a very slight improvement in the quality of classi cation compared to the updated FCA algorithm (only by 3% in problem 1). 2. In all cases there was an unacceptably high rate of classi cation failures. 3. In all cases there was an unacceptably high error rate. 4. Attempts to ne-tune the algorithm parameters with the objective of reducing the failure rate were generally accompanied by increasing in the number of errors, although in some cases (problem 8) the error rate increased only slightly; the number of classi able objects in these cases increased substantially (problem 6). 5. The classical FCA-based algorithm can produce accurate classi cation, but it refuses to classify the majority of test sample.

The analysis of the hypotheses generated with various parameter values and di erent optimization criteria has shown that hypotheses of di erent classes are often included in one another. We can naturally assume that if the classes show less tendency to di use into one another, biclustering and the classical FCA method would produce more impressive results. The relative location of classes is improved in pattern recognition theory by methods that involve transformation of the attribute space. In these cases, data compacti cation methods may be e ectively applied [ 14 ]. We can reasonably assume that another scaling algorithms with oating-size intervals and interval-length optimization may improve classi cation results compared to those we have obtained with the simplest scaling. Our analysis of FCA-based classi cation provides the following conclusions: 1. For the chosen universal scaling procedure the classi cation results are far from being optimal. Individual scaling for each problem may improve classi cation quality. 2. FCA-based classi cation methods without modi cation and/or thorough preprocessing of data are usable only for preliminary classi cation. 3. A well-known idea for the modi cation of the direct FCA approach is to develop hypothesis generation methods. It is useful to allow for the speci c features of the particular subject area and to ne-tune hypotheses and the algorithms by using e.g. parameters min , P*, min. 4. It is also possible to develop and apply sharper classi cation rules, e.g. by weighting objects, attributes, hypotheses, etc. 5. A promising approach is to use FCA-based methods to transform the attribute space, in particular using data compactness estimates. 6. concept-based methods are appropriate for classi cation problems with high error costs, e.g. in medical, security and military applications.

An important step in many data classi cation problems is the selection of a suitable similarity measure. We decided to investigate how di erent similarity metric described in [ 20, 23 ] a ects the quality of hypothesis-based classi cation method. The majority of pattern recognition methods use the metric information about objects: methods based on distances, potential functions, dividing surface, the algebraic approach, etc. In these methods the amount of information about classes either is fairly used at all. The strength of FCA-based classi cation problems is in the identi cation and use of these particular data, but the metric information about the feature space is lost. Thus, in pattern recognition the classic discriminant methods and method based on FCA are at opposite poles w.r.t. metrics. In the FCA the metric information appears in a weak form as the result of scaling, which accounts for \distances" between attributes. It seems that the success in the development of FCA-based recognition methods will be related to the introduction of information about metric properties of feature spaces. Our future work will be focused on developing and applying sharper classi cation rules with modi cations of similarity measure.

References

1. B. Ganter , R. Wille: Formal Concept Analysis: Mathematical Foundations . Springer, Berlin/Heidelberg ( 1999 ).

2. S.O. Kuznetsov: Mathematical aspects of concept analysis . In: Journal of Mathematical Science , Vol. 80 , Issue 2, pp. 1654 { 1698 , ( 1996 ).

3. S.O. Kuznetsov: Complexity of Learning in Concept Lattices from Positive and Negative Examples . Discrete Applied Mathematics , 2004 , No. 142 ( 1 {3), pp. 111 - 125 .

4. G. Birkho : Lattice Theory . AMS, Providence, 3rd edition ( 1967 ).

5. O. Ore : Theory of Graphs. American Mathematical Society , Providence ( 1962 ).

6. S.I. Gurov: Ordered Sets and Universal Algebra [in Russian] , MGU , Moscow ( 2004 ).

7. V.K. Finn: The Synthesis of Cognitive Procedures and the Problem of Induction . Autom. Doc. Math. Linguist., 43 , 149 - 195 ( 2009 ).

8. V.K. Finn: On machine-oriented formalization of plausible reasoning in the style of F. Bacon and D .S. Mill [in Russian], Semiotika i Informatika , 20 , 35{ 101 ( 1983 ).

9. S.C. Madeira and A.L. Oliveira : Biclustering Algorithms for Biological Data Analysis: A Survey . IEEE/ACM Trans. Comput. Biol. Bioinformatics 1 , 24{ 45 ( 2004 ).

10. B.G. Mirkin: Mathematical Classi cation and Clustering. Kluwer ( 1996 ).

11. D.I. Ignatov , S.O. Kuznetsov: Frequent Itemset Mining for Clustering Near Duplicate Web Documents . In: Proc. 17th Int. Conf. on Conceptual Structures (ICCS 2009 ), LNAI (Springer) , Vol. 5662 , 185 { 200 , 2009 .

12. D.I. Ignatov , S.O. Kuznetsov , R.A. Magizov and L.E. Zhukov: From Triconcepts to Triclusters . In: Proc. 13th Int. Conf. on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing (RSFDGrC 2011 ), LNCS (Springer) , Vol. 6743 , 257 { 264 , 2011 .

13. S.O. Kuznetsov: Stability as an Estimate of the Degree of Substantiation of Hypotheses on the Basis of Operational Similarity . In: Nauchno-Tekhnicheskaya Informatsiya , Seriya 2 , Vol. 24 , No. 12 , pp. 21 { 29 , 1990 .

14. S.I. Gurov , N.S. Dolotova , I.N. Fatkhutdinov: Noncompact recognition problems . Circuit design according to E. Gilbert. In: Spectral and Evolution Problems: Proc. 17 th Crimean Autumn Mathematical School-Symposium , Simferopol, Crimean Scienti c Center of Ukrainian Academy of Sciences, 17 , pp. 37 { 44 ( 2007 ).

15. A.A. Onishchenko , S.I. Gurov: Classi cation based on Formal Concept Analysis and Biclustering: possibilities of the approach . In: Computational Mathematics and Modeling , Vol. 23 , No. 3, July , pp. 329 { 336 ( 2012 ).

16. C. Cortes , V. Vapnik: Support{vector networks . In: Machine Learning , September 1995 , Volume 20 , Issue 3, pp. 273 { 297 .

17. N. Meddouri , M. Meddouri: Classi cation Methods based on Formal Concept Analysis , | CLA 2008 (Posters) , pp. 9 { 16 , Palacky University , Olomouc, ( 2008 ).

18. S. I. Gurov : Boolean Algebras, Ordered Sets, Lattices: De nitions, Properties, Examples [in Russian], KRASAND , Moscow ( 2012 ).

19. S.O. Kuznetsov: Machine learning on the basis of formal concept analysis Automation and Remote Control 62 ( 10 ),pp. 1543 { 1564 .

20. F. Alqadah , R. Bhatnagar: Similarity measures in formal concept analysis , Annals of Mathematics and Arti cial Intelligence , 61 ( 3 ), 245 { 256 ( 2011 ).

21. S.O. Kuznetsov : On Stability of a Formal Concept . Annals of Mathematics and Arti cial Intelligence , Vol. 49 , pp. 101 { 115 , 2007 .

22. L. Breiman , J.H. Friedman , R.A. Olsen , and C.J. Stone : Classi cation and Regression Trees , Wadsworth Int . Group, Belmont, CA ( 1984 ).

23. F. Dau , J. Ducrou , P.W. Eklund: Concept Similarity and Related Categories in SearchSleuth . ICCS 2008 : pp. 255 { 268

24. M. Sahami: Learning classi cation Rules Using Lattices . N. Lavrac and S. Wrobel eds., pp. 343 { 346 , Proc ECML , Heraclion, Crete, Greece (Avril 1995 ).

25. C. Caprineto , G. Romano: GALOIS An order-theoretic approach to conceptual clustering . In proceedings of ICML93 , pp. 33 { 40 , Amherst, USA ( July 1993 ).

26. P. Njiwoua , E.M. Nguifo: Forwarding the choice of bias LEGAL-F Using Feature Selection to Reduce the complexity of LEGAL . In Proceedings of BENELEARN-97 , ILK and INFOLAB , Tilburg University, the Netherlands, pp. 89 { 98 , 1997 .

27. Zhipeng Xie , Wynne Hsu, Zongtian Liu, Mong Li Lee: Concept Lattice based Composite Classi ers for high Predictability . Arti cial Intelligence , vol. 139 , pp. 253 { 267 , Wollongong , Australia ( 2002 ).

28. S. Guillas , K. Bertet , J-M. Ogier : Extension of Bordats algorithm for attributes . Concept Lattices and Their Applications: CLA07 , Montpellier, France ( 2007 ).

29. B. Douar , C. Latiri , Y. Slimani: Approche hybride de classi cation supervisee base de treillis de Galois: application la reconnaissance de visages . In: Extraction et Gestion des Connaissances (EGC08) , 309 { 320 , Nice , France ( 2008 ).

30. P. Njiwoua, Mephu Nguifo E.: Ameliorer lapprentissage partir dinstances grace linduction de concepts: le systeme CIBLe, Revue dIntelligence Arti cielle (RIA) , vol. 13 , 2 , 1999 , pp. 413 { 440 , Hermes Science .

31. E.M. Nguifo , P. Njiwoua: Treillis de concepts et classi cation supervise . Technique et Science Informatiques: TSI , Volume 24 , Issue 4, pp. 449 { 488 ( 2005 ).

32. M. Maddouri: Towards a machine learning approach based on incremental concept formation . Intelligent Data Analysis , Volume 8 , Issue 3, pp. 267 { 280 ( 2004 ).