FCA-based classifiers can deal with nonbinary data representation in different ways: use it directly or binarize it. Those algorithms that binarize data use metric information from the initial feature space only as a result of scaling (feature binarization procedure). Metric approach in this area allows one significantly reducing classification refusals number and provides additional information which can be used for classifier training. In this paper we propose an approach which generalizes some of existing FCA classification methods and allows one to modify them. Unlike other algorithms, the proposed classifier model uses initial metric information together with order object-attribute dependencies.
Formal concept analysis (FCA) is a branch of applied lattice theory allowing one
to formalize some machine learning models. It provides tools to solve various
tasks in many domains of computer science, such as knowledge representation
and management, data mining, including classification and clustering. There are
many FCA-based classification algorithms known [
In what follows we keep to standard lattice theory and FCA definitions. Therefore here we briefly describe some basic definitions, classifiers and introduce the notation which is used further. Let G and M be an arbitrary sets called the set of objects and the set of attributes respectively and I ⊆ G × M be a binary relation. The triple K = (G, M, I) is called a formal context. The following (·)′ mappings define a Galois connection between 2G and 2M sets partially ordered by set-theoretic inclusion:
A′ = {m ∈ M | gIm for all g ∈ A} , B′ = {g ∈ G | gIm for all m ∈ B} . A pair (A, B), such that A ⊆ G, B ⊆ M and A′ = B, B′ = A is called a formal concept of K with formal extent A and formal intent B. For object g ∈ G we write g′ instead of {g}′. Define the “projection” mappings ext : (A, B) 7→ A and int : (A, B) 7→ B. Formal concepts of a given context K form a complete lattice denoted by B(K). It is called the concept lattice of a context K. Let hL, ∧, ∨i be a lattice and x ∈ L. By x▽ (x△) we denote the order ideal (filter) generated by x. By At(L), J (L) and M (L) we denote the set of all atoms, join-irreducible and meet-irreducible elements of L respectively. The function f : L → R is called supermodular if f (x) + f (y) 6 f (x ∨ y) + f (x ∧ y) for all x, y ∈ L.
A concept C is called consistent if all objects in ext(C) belong to the same
class. Both GALOIS classification procedures are described in [
Let K = (G, M, I) be a context and w ∈/ M be a target attribute. The input
data for classification 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
undefined context Kτ = (Gτ , M, Iτ ). G−, G+ and Gτ are sets of positive, negative
and undefined objects respectively. Iǫ ⊆ Gǫ × M , where ǫ ∈ {−, +, τ } are binary
relations that define structural attributes. Galois operators in these contexts are
denoted by (·)+, (·)−, and (·)τ respectively. A formal concept of a positive
context is called a positive concept. Negative and undefined concepts are defined
similarly. If the intent B+ of a positive concept (A+, B+) is not contained in the
intent g− of any negative example g ∈ G−, then it is called a positive
hypothesis with respect to the property w. A positive intent B+ is called falsified if
B+ ⊆ g− for some negative example g ∈ G−. Negative hypotheses are defined
similarly. By “hypotheses-based classifier” we mean the classification procedure
from [
Generalization and Modification of Algorithms The common drawback of the FCA-based classifiers using binary features after scaling is that they forget the initial feature space metric structure. The main idea of this paper is to use this metric information together with ordertheoretic relations between objects and attributes provided by a concept lattice. It is important that F and Bn spaces with additional structures (metric and formal context) are being used at the same time, providing more possibilities for classifier training methods. 2.1
Metric estimates Denote by H+ and H− the sets of concepts constructed from a training set, which intents are positive and negative hypotheses respectively. We assume that (F , ρ) is a metric space, and let S(x, A) be the similarity measure (based on the metric from F , see examples in Section 3) between an object x and a set of objects A. Let us define the estimates for positive and negative classes: Γ+(x) =
X I(x, C)S(x, ext(C)), Γ−(x) =
X I(x, C)S(x, ext(C)), C∈H+
C∈H− where I(x, C) = [int(C) ⊆ x′] and [·] is the indicator function. Then the classifier will have the following form: a(x) = sign Γ (x) = sign(Γ+(x) − Γ−(x)). Proposition 1. If hypotheses-based classifier correctly predicts class label for an object then a(x) = sign Γ (x) does the same.
In comparison with hypotheses-based classifier the number of classification refusals is reduced, but the total error rate can increase. 2.2
Analogy with algorithms based on estimate calculations To calculate the estimates in the method above we use positive and negative hypotheses sets, i.e. special subsets of concept lattice. Such calculation of estimates can be generalized to an arbitrary concept lattice subsets somehow characterizing individual classes y ∈ Y .
Let C be the set of concepts which we call the support concepts system. Suppose that each concept from C characterizes only one class y ∈ Y , that is C = Fy∈Y Cy, where Y is the set of classes. Then define the estimate of object x for class y as follows: Γy(x) = X S(x, C).
C∈Cy
The classifier will have the following form: a(x) = arg maxy∈Y Γy(x). The
estimates of this type are similar to the estimates used in estimate calculations
methods [
Consider specific examples of support concepts system C, similarity measure S(x, C) and analyze corresponding classifiers: 1. C = H+ F H− are positive and negative hypotheses sets,
S(x, C) = [int(C) ⊆ x′]Sˆ(x, ext(C)), where Sˆ(x, ext(C)) is the given similarity measure. The corresponding classifier was described above. 2. C = Fy∈Y Cy is the consistent concepts set.
If S(x, C) = | (M \ int(C)) ∪ x′| we get modified GALOIS(1) algorithm.
If S(x, C) = [int(C) ⊆ x′] we get GALOIS(2) algorithm. 2.3
Analogy with metric classifiers Let C = {C1, . . . , Cn} be the support concepts system. Suppose that there is the distance measure ρ in F space. Sort C in increasing order w.r.t. the values of the distance ρ(x, Ci) between object x and concepts Ci:
ρ(x, Cx(1)) 6 ρ(x, Cx(2)) 6 · · · 6 ρ(x, Cx(n)), where Cx(i) is the i-th neighbour of x among C, yx(i) is the class, characterized by Cx(i) concept. Define the estimate of object x for class y:
n Γy(x) = X wi(x)[yx(i) = y],
i=1 wi(x) is x i-th neighbour weight (positive function non-increasing w.r.t. i).
The defined estimates are completely analogous to the metric classifiers estimates, except that the neighbours here are not objects but support concepts.
Thus choosing the suitable weights wi(x) we get analogs of all known metric
classifiers (kNN, Parzen window, potential functions and others), but in terms
of concepts. For example:
– wi(x) = [i 6 k] is k nearest neighbours method;
– wi(x) = [i 6 k]wi is k weighted nearest neighbour method (wi depends only
on the neighbour number);
– wi(x) = K( ρ(xh,(Cxx()i)) ) is Parzen window method (K(z) is non-increasing
positive-valued function defined on [
All the proposed methods are the generalizations of the existing methods and can be used for their modifications. They use both metric information from F and object-attribute dependencies provided by concept lattice. This allows to reduce the number of classification refusals and error rate. 2.4
Pseudometric on the set of concepts
Another approach which uses the notion of similarity in FCA algorithms is to
define a distance function on the set of concepts. In Rulearner algorithm ([
Consider arbitrary finite lattice hL, ∧, ∨i, non-empty subset D ⊆ L and a function f : L → Z+, defined as follows: f (x) = |D(x)|, where D(x) = D ∩ x▽. Proposition 2. The function f (x) is isotone and supermodular. Proof. The isotone property of f follows from the following chain of implications: x 6 y ⇒ x▽ ⊆ y▽ ⇒ D(x) ⊆ D(y) ⇒ f (x) = |D(x)| 6 |D(y)| = f (y).
f (x)+f (y) = |D(x)|+|D(y)| = |D(x)∪D(y)|+|D(x)∩D(y)| 6 f (x∨y)+f (x∧y). To prove the last inequality observe that D(x) ∪ D(y) ⊆ D(x ∨ y) follows from the following inclusions:
x 6 x ∨ y ⇒ D(x) ⊆ D(x ∨ y), y 6 x ∨ y ⇒ D(y) ⊆ D(x ∨ y).
The equality D(x) ∩ D(y) = D(x ∧ y) follows from x▽ ∩ y▽ = (x ∧ y)▽. ⊓⊔
Thus, according to the theorem above, the function f (x) induces the pseudometric df (x, y) on the lattice, defined by the following equality: df (x, y) = f (x) + f (y) − 2f (x ∧ y).
Proposition 3. df (x, y) = |D(x) ⊕ D(y)|, where A ⊕ B = (A \ B) ∪ (B \ A). Proof. From the proof of the proposition above we conclude that the equality D(x) ∩ D(y) = D(x ∧ y) holds. Consider the chain of equalities: f (x) + f (y) − 2f (x ∧ y) = |D(x)| + |D(y)| − 2|D(x ∧ y)| = = |D(x)| + |D(y)| − 2|D(x) ∩ D(y)| = = |D(x) ∪ D(y)| + |D(x) ∩ D(y)| − 2|D(x) ∩ D(y)| = = |D(x) ∪ D(y)| − |D(x) ∩ D(y)| = |D(x) ⊕ D(y)|. ⊓⊔ Corollary 1. If hL, ∧, ∨i is a finite Boolean algebra and D is the set of all atoms of L, then df (x, y) is exactly the Hamming distance.
In order to compare formal concepts it is reasonable to choose D = J (L) or D = At(L). In terms of this pseudometric two concepts are the closer, the less object concepts are covered by only one of them. Moreover, the cover(u) and df (x, y) functions are tied: cover(u) = df (u, V L). One of the drawbacks of the defined distance measure is that the number of elements from D covered by x ∧ y is not taken into account. In some cases it may lead to inadequate distance estimates.
Possible modifications: 1. Various normalizations to take the number of elements into account, e.g.: 2. Weighting elements of D, e.g. let D = J (L) and we be the proportion of the hypotheses covering e = (g′′, g′). Then d(x, y) will have the following form: d(x, y) = |D(x) ⊕ D(y)| |D(x) ∪ D(y)|
. d(x, y) =
X
we.
e∈D(x)⊕D(y)
The distance between concepts can be applied to modify the classification algorithms mentioned above. For example, let an object x be classified with hypotheses-based algorithm. Suppose there are two positive hypotheses H1+, H2+ and two negative hypotheses H1−, H2− for the classification of x. In this case the algorithm refuses to classify x. Suppose we know the concept distances d(H1+, H2+), d(H1−, H2−) and also d(H1+, H2+) ≫ d(H1−, H2−). Then it is natural to classify x as positive, because the distant concepts (in terms of the proposed measure) are less ”correlated” (since they cover many distinct object concepts), and hence their answers are more significant. Distance between concepts can also be used for reducing the size of concepts system (used by classifier, e.g. consistent concepts) in order to improve generalization ability of classifier, reduce the overfitting and remove concepts based on noisy data. 3
In this section the experimental results are presented. The algorithms have been
tested on two data sets taken from UCI Machine Learning Repository [
K1(r, a) =
1 1 + exp(ar)
K2(r, a) =
1 r + a
. ρ1(x, C) = inf ρ(x, c), c∈C ρ2(x, C) = ρ3(x, C) = sup ρ(x, c).
c∈C
We introduce the following notation: νc is the proportion of classified objects, νr = 1 − νc is the proportion of refused classifications, et is total error rate (including refusals), er is the error rate among classified objects.
Algorithm νc νr et er GALOIS(1) 1 0 0.1604 0.1604 Modified GALOIS(1) 1 0 0.0856 0.0856 GALOIS(2) 1 0 0.0802 0.0802 Rulearner 0.7487 0.2513 0.2727 0.0286 Hypotheses-based 0.5936 0.4064 0.6150 0.1842 K = K1, a = 0.0125, ρ = ρ1 0.8021 0.1979 0.3155 0.1467 K = K1, a = 0.0125, ρ = ρ2 0.8021 0.1979 0.2888 0.1133 K = K1, a = 0.0125, ρ = ρ3 0.8021 0.1979 0.2834 0.1067 K = K1, a = 1, ρ = ρ2 0.7273 0.2727 0.3422 0.0956 K = K2, a = 1, ρ = ρ1 0.8021 0.1979 0.2941 0.1200
K = K2, a = 1, ρ = ρ2 0.8021 0.1979 0.3209 0.1533
The aim of the experiments was to compare FCA classification methods
and not to achieve low error rate in solving particular tasks. Hence we used
simple scaling procedure: normalizing all attributes to [
In this paper we have formally described and experimentally studied a new approach to classification which encompasses the usage both of metric information provided by the initial feature space and the order object-attribute dependencies. Also we have defined the pseudometric on arbitrary finite lattice, which has intelligeble interpretation in terms of concepts and hence can be used for comparing concepts in order to improve FCA classification methods. Further developments can be focused on studying of classifiers obtained from the proposed model by fixing the support concepts system C and the similarity measure S(x, C) and on the possibilities of choosing such support concepts system that allows to construct only a part of concept lattice.