In this paper we extend previously developed approach to FCA-based machine learning with discrete attributes to the case with objects described by continuous attributes. We combine the logistic regression with an entropy-based separation of attribute values, which is similar to Quinlan's approach to dealing with continuous attributes. We apply Cox-Snell and McFadden significance criteria to logistic regression. Finally, we present the results of applying the new version of FCA-based learning system to the analysis of Wine Quality dataset from UCI Machine Learning Repository.
In [8] the author extended some FCA ideas [1] by developing a probabilistic approach to Machine Learning (ML) based on similarity operation. FCA provides a very efficient representation for training objects by means of bitsets (fixed length strings of bits) with bit-wise multiplication as a similarity between them. The previous version of the ML program (called ’VKF system’ in honor to Prof. V.K. Finn) was applicable to objects described by discrete attributes only. However, a variety of interesting data needs both discrete and continuous attributes for their representation. The first step to include continuous cases to VKF system is an analogue of J.R. Quinlan’s approach to similar problem for C4.5 decision tree algorithm [5]. He splits the whole domain of a continuous attribute into several intervals to reach minimal mean entropy.
To obtain bitset representation from such division we introduce indicator variables and combine their values. The main result asserts that bit-wise multiplication corresponds to a convex hull of intervals of values under similarity, which was studied in [2] and [4] in terms of interval pattern structures within, an FCA-based approach to analysis of data with continuous attributes. A more important problem is to discover complex combinations of continuous attributes. ? partially supported by RFBR grant 18-29-03063mk.
Since our main goal is to discover a classifier, we apply Bayes Machine Learning ideas to generate such complex attributes through well-known logistic regression.
tions) between pairs of attributes. Hence, we apply well-known Cox-Snell and
The structure of the paper is as follows. In Section 1 we recall general definitions and some facts from FCA. Section 2 covers main algorithms of VKFmethod. Section 3 describes new results. Subsection 3.1 reproduces Quinlan’s technique to separate continuous feature domain into several intervals. It also introduces a representation of the occurrence of an attribute value in some interval by bitset. Subsection 3.2 introduces a logistic regression approach to discovering relationships between continuous features. 1
Formal Concept Analysis (FCA) A (finite) context is a triple (G, M, I) where G and M are finite sets and I ⊆ G × M . The elements of G and M are called objects and attributes, respectively. As usual, we write gIm instead of hg, mi ∈ I to denote that object g has attribute m.
For A ⊆ G and B ⊆ M , define
A0 = {m ∈ M |∀g ∈ A(gIm)},
B0 = {g ∈ G|∀m ∈ B(gIm)}; so A0 is the set of attributes common to all the objects in A and B0 is the set of objects possessing all the attributes in B. The maps (·)0 : A 7→ A0 and (·)0 :
If we fix attribute subsets {g1}0 ⊂ M and {g2}0 ⊂ M for objects g1 ∈ G and g2 ∈ G, respectively, with corresponding bitsets, then the derivation operator on a pair of objects corresponds to bit-wise multiplication, since {g1, g2}0 = {g1}0 ∩ {g2}0. More generally, the polars correspond to the iteration of bit-wise multiplication (in arbitrary order) of corresponding bitset-represented objects and attributes, respectively. The last remark is important, since bit-wise multiplication is a basic operation of modern CPU and GPGPU. The aim of the article is to invent a bitset representation of continuous features in such a way that bit-wise multiplication of resulting bitsets has clear meaning with respect to original values!
A ⊆ G, B ⊆ M , A0 = B, and B0 = A. The first component A of the concept (A, B) is called the extent of the concept, and the second component B is called its intent. The set of all concepts of the context (G, M, I) is denoted by L(G, M, I).
Definition 1. For (A, B) ∈ L(G, M, I), g ∈ G, and m ∈ M define
CbO((A, B), g) = ((A ∪ {g})00, B ∩ {g}0),
CbO((A, B), m) = (A ∩ {m}0, (B ∪ {m})00).
(
The well-known example (S, S, 6=) of context for Boolean algebra demonstrates difficulties of brute force approach. For Boolean algebra of all subsets of n elements the context uses n2 bits, and all the concepts need n · 2n bits. For n = 32 the first number is 1 Kb (or 128 bytes) and the second one is 16
randomized algorithms to generate a random subset of the lattice. The author introduced and investigated mathematical properties of several algorithms of this kind, the best of which are variants of coupling Markov chains.
of probabilistic approach to machine learning based on FCA (VKF-method).
Data: context (G+, M, I), external function CbO( , ) Result: random concept (A, B) ∈ L(G+, M, I) X := G t M ; (A, B) := (M 0, M ); (C, D) = (G, G0); while ((A 6= C) ∨ (B 6= D)) do select random element x ∈ X; (A, B) := CbO((A, B), x); (C, D) := CbO((C, D), x); end
(
the while loop of Algorithm 1 is defined by Lemma 2.
For Boolean lattice (contranomial) context the author [8] computed the mean length of trajectory of Algorithm 1 as n Pn j=1 n1 and proved strong concentration of length of arbitrary trajectory about its mean. For n = 32 the mean is ≤ 130, hence every trajectory generates about 260 (since two concepts is a state of the coupling Markov chain) subsets. Hence, only a small fraction of concepts occurs during computation of a moderate size subset of the Boolean algebra. We have in mind that there are 4,294,967,296 elements of Boolean algebra on 32 attributes.
Algorithm 1 to generate a random formal concept (A, B) ∈ L(G+, M, I). The program saves the concept (A, B) if there is no obstacle (counter-example) o ∈
G+ := (+)-examples, M := attributes; I ⊆ G+ × M is a formal context for (+)-examples; G− := (-)-examples; S := ∅; i := 0; while (i < N ) do
Generate concept (A, B) by Algorithm 1; hasObstacle := false; for (o ∈ G−) do if (B ⊆ o0) then
hasObstacle := true; end end if (hasObstacle = false) then
S := S ∪ {(A, B)}; i := i + 1; end end
(A, B) into the intent of counter-example o.
and compares the results of prediction with the original target value.
Data: random sample S of concepts, list Gτ of test objects Result: prediction of target class of Gτ elements for (o ∈ Gτ ) do
P redictP ositively(o) := false; for ((A, B) ∈ S+) do if (B ⊆ o0) then
P redictP ositively(o) := true; end end end
Theorem 1. For n = |M | and for any ε > 0 and 1 > δ > 0 random sample S of concepts of cardinality
N ≥
2 · (n + 1) − 2 · log2 δ
ε
(
vonenkis [7] from Computational Learning Theory (here n + 1 corresponds to log2 d, where d is a VC-dimension).
3 3.1
Continuous attributes
Entropy approach Let G = G+ ∪ G− be a disjoint union of training examples G+ and counterexamples G−. Interval [a, b) ⊆ IR of values of continuous attribute V : G → IR generates three subsets
G+[a, b) = {g ∈ G+ : a ≤ V (g) < b}, .
Definition 2. Entropy of interval [a, b) ⊆ IR of values of continuous attribute V : G → IR is ent[a, b) = − |G|G+[a[a,,bb))|| · log2 |G+[a, b)| |G[a, b)| − |G|G−[a[a,,bb))|| · log2 |G−[a, b)| |G[a, b)|
Mean information for partition a < r < b of interval [a, b) ⊆ IR of values of continuous attribute V : G → IR is
inf[a, r, b) = ||EE[[aa,, rb))|| · ent[a, r) + ||EE[[ar,, bb))|| · ent[r, b).
Threshold is a value V = r with minimal mean information.
G−[a, b) = {g ∈ G− : a ≤ V (g) < b},
G[a, b) = {g ∈ G : a ≤ V (g) < b}
For continuous attribute V : G → IR denote a = min V by v0 and let vl+1 be an arbitrary number greater then b = max V . Thresholds {v1 < . . . < vl} are computed sequentially by splitting the largest entropy subinterval.
Definition 3. For each 1 ≤ i ≤ l indicator (Boolean) variables corresponds to (10) (11) (12) (13) δiV (g) = 1 ⇔ V (g) ≥ vi σiV (g) = 1 ⇔ V (g) < vi
Then string δ1V (g) . . . δlV (g)σ1V (g) . . . σlV (g) is a bitset-representation of continuous attribute V on element g ∈ G.
Lemma 3. Let δ1(
bitset representations is a convex hull of its arguments’ intervals.
pX,K (x, k) = pX (x) · pK|X (k | x), where pX (x) is a marginal distribution of objects and pK|X (k | x) is a conditional distribution of marks on given object, i.e. for every x ∈ IRd the following pK|X (k | x) = IP{K = k | X = x} holds.
Error probability of classifier c : IRd → {0, 1} is
R(c) = IP {c(X) 6= K} .
Bayes classifier b : IRd → {0, 1} with respect to pK|X (k | x) corresponds 1 b(x) = 1 ⇔ pK|X (1 | x) > 2 > pK|X (0 | x) to
pK|X (1 | x) = Theorem 2. The Bayes classifier b has the minimal error probability: ∀c : IRd → {0, 1} [R(b) = IP{b(X) 6= K} ≤ R(c)] 1 + ppXX||KK((xx||01))··IIPP{{KK==01}}
pX|K (x | 1) · IP{K = 1} pX|K (x | 1) · IP{K = 1} + pX|K (x | 0) · IP{K = 0}
1 1 = = 1 + exp{−a(x)} = σ(a(x)) = where a(x) = log ppXX||KK((xx||10))··IIPP{{KK==10}} and σ(y) = 1+exp{−y} is the well-known 1 logistic function.
b(x) = 1 ⇔ a(x) > 0
Let approximate unknown a(x) = log ppXX||KK((xx||10))··IIPP{{KK==10}} by linear combination wT · ϕ(x) of basis functions ϕi : IRd → IR (i = 1, . . . , m) with respect to unknown weights w ∈ IRm.
For training sample hx1, k1i, . . . , hxn, kni introduce tj = 2kj − 1. Then n " m # log{p(t1, . . . , tn | x1, . . . , xn, w)} = − X log 1 + exp{−tj X wiϕi(xj)} . j=1 i=1 Lemma 4. log [1 + exp{−t · Pim=1 wiϕi}] is a convex function of w. (14) (15) (16)
L(w1, . . . , wm) = − n " m X log 1 + exp{−tj X wiϕi(xj )} j=1 i=1 # → max is concave.
wt+1 = wt − (∇wT ∇wL(wt))−1 · ∇wL(wt).
Use sj = 1+exp{tj·(1wT ·Φ(xj))} we obtain
∇L(w) = −ΦT diag(t1, . . . , tn)s, ∇∇L(w) = ΦT RΦ, where R = diag(s1(1 − s1), s2(1 − s2), . . . , sn(1 − sn)) is diagonal matrix with elements s1(1 − s1), s2(1 − s2), . . . , sn(1 − sn) and diag(t1, . . . , tn)s is vector with coordinates t1s1, t2s2, . . . , tnsn.
wt+1 = wt + ΦT RΦ −1 ΦT diag(t)s = (ΦT RΦ)−1ΦT Rz, (19) where z = Φwt + R−1diag(t1, . . . , tn)s are iterative calculated weights.
wt+1 = (ΦT RΦ + λ · I)−1 · (ΦT Rz).
Criterion of Cox-Snell declares attribute Vk significant, if
R2 = 1 − exp{2(L(w0, . . . , wk−1) − L(w0, . . . , wk−1, wk))/n} ≥ σ. McFadden criterion declares attribute Vk significant, if (17) (18) (20) (21) 1 −
L(w0, . . . , wk−1, wk)
L(w0, . . . , wk−1) ≥ σ.
We have extended the ’VKF system’ approach to FCA-based machine learning on examples with both discrete and continuous attributes.
tation. Lemma 3 gives a condition of non-triviality of similarity on values of continuous attribute: if the corresponding part of the resulting bitset is nonvoid, then the values V (B0) belong to a common interval.
Lemma 5. Disjunction xi1 ∨ . . . ∨ xik of Boolean variables holds, if and only if xi1 + . . . + xik ≥ σ holds for any 0 < σ < 1.
Positive (but slightly different) weights correspond to different scaling of various attributes. So we have not only conjuction of attributes by also a disjunction. Similar case is a relationship between ’citric acid’ and ’alcohol’.The situation with the pair (’pH’, ’alcohol’) is radically different. The alcohol’s weight is positive, whereas pH’s weight is negative. With the help of aforementioned lemma and standard logic we obtain the implication (’pH’⇒’alcohol’).
The author would like to thank Prof. S.O. Kuznetsov for motivation and support. He is also grateful to his colleagues from Dorodnicyn Computing Center of Federal Research Center ”Computer Science and Control” of Russian Academy of Science and Russian State University for Humanities for long-term support and useful discussions. Finally, the author is grateful to anonymous reviewers, whose comments helped to significantly improve the presentation.