The uncertainty in the environment typically generates noisy concept alternatives and leads to an overpopulated concept lattice. From a computational point of view, a straightforward ltering of the noisy concept lattice will su er from an exponential-size computational overkill, and from a semantical one { will face numerous ambiguities due to an over tting. We managed to bypass the ltering problem by applying a sort of probabilistic approach. We developed a probabilistic generalization of formal concepts which seems to avoid a monstrous combinatorial complexity of a complete context lattice construction. The theoretical base for this method is described, as well as a ready-to-work noise resistant algorithm. The algorithm has been tested and showed a moderate precision and recall rate on various datasets, including a toy one presented with the presence of a 2, 3 or 5% random noise.
Formal concepts may be successfully used as classi cation units [
There are some attempts to get rid of noise in data by concepts selection or
ltering. E.g. measures of the concept stability has been shown to pick out the
most reliable formal concepts [
Nevertheless, this is still not enough for uncertain environments [
Approaches based on the hypothesis-making has been analyzed: performance
of a model still su ers in the practical tasks environment [
In the paper we reconsider the problem of handling a possible noise in data
by means of probability and logic. The origin of the probabilistic pattern for
formal concepts lies in cognitive science, where they are closely related to the
"natural classes" [
The rst step has been made in [
This section suggests a brief overview for a formal concept analysis framework
[
A dataset is represented by an attribute-value cross-table. Formally speaking,
On the formal context (or simply context) a derivation operator 0 is de ned:
G, B
1. A0 = fm 2 M j 8g 2 A; (g; m) 2 Ig 2. B0 = fg 2 G j 8m 2 B; (g; m) 2 Ig 3. The pair (A; B) is called a formal concept if A0 = B and B0 = A.
Generally speaking, formal concepts analysis concentrates on a concept lattice arising on concept extents from the natural subset order. However, we aim to avoid considering a concept lattice and exploit the intrinsic properties of the data. The implication is a core notion.
B ! C. The implication B ! C is true on K = (G; M; I), if 8g 2 G(B * g0 or C g0). We denote the set of all true implications as Imp(K).
Implications are not only the forms a conceptual bridge from FCA to logic structures, but are an essential way of reasoning within a machine logic and prediction task particularly.
inference fL that adds all conclusions of applicable implications: fL(X) = X [ fC j B
X; B ! C 2 Lg
The following theorem characterizes concepts by means of xed points.
M , fImp(K)(B) = B , B00 = B.
The theorem application may be illustrated on a simple formal context.
We can reformulate concept lattice construction task by means of implications and an inference operator. It can be easily found out from Table 1 that attributes m1 and m3 determine the class of an object. In fact, m1 implies m2 and so does m3. This is written as m1 ! m2 and m3 ! m2. The sets fm1; m2g, fm2; m3g and fm1; m2; m3g are the formal concepts, so do xed points of the direct inference operator. For example, fm1g fImp(K) ! fm1; m2g fImp(K) ! fm1; m2g Thus indeed, fm1; m2g is a xed point and a formal concept simultaneously. 3
Let us add some noise on K0. We also extend K0, by adding redundant objects duplicates. It will help to keep the noise level rather low in order to make a concept recovery practically possible.
Every single altering will change a concept lattice a lot. The rst context is
equivalent to K0 above and has the same concept lattice. However, the second one
generates a lot of side concepts, provoked by noise: the sets fm2g and fm1; m3g
also become formal concepts. The amount of side concepts is increasing as more
noise is incoming { the dependency tends to be asymptotically exponential [
The stability may be obtained in various ways. The most obvious way is
computing some stability index in order to evaluate, does the concept from
noisy context is good enough, either does it is produced by noise [
The other one may be based on a di erent subject: instead of measuring a stability of concepts, a stability of implications is measured. An essential way to do this is to exploit a likelihood of attribute implications, but we will also generalize them up to logical formulas. { LK is a letters set and includes any m 2 M as well as their negations :m; {
any ; 2 K products of ^ ; _ ; ! ; : are formulas, too; Remark 1. For brevity, we assume V L = :L = f:P j P 2 Lg.
^ P (or V L = 1 if L = ?). Similarly,
P 2L
For every object fgg, a logic model of the object Kg is de ned. We say that the object g respects the formula 2 K , if the formula is true for the model Kg. We will write this fact as g , Kg . The set G = fg 2 G j g g is called the support of .
:
K ! [0; 1]; ( ) = (fg j g g):
The most common understanding of formula probability may be linked with a well-known con dence index for context implications: conf(X ! Y ) = jsujspupp(pX(X[Y)j)j . The formula probability will express exactly the same, if we keep things simple and assume to be a counting measure: (fgg) = j G1j .
For practical applications, here and further we will suppose that G is nite and does not contain any objects of a zero measure, i.e. 8g 2 G; (fgg) 6= 0. De nition 7. The set of attributes M is compatible, if M 0 6= ?. The same may be expressed as (V M ) > 0.
Now let us consider the set L = fmi; mgi=1:::k LK . The formula m1 ^ m2::: ^ mk ! m will look like the classical context implication (fmig; fmg), except when it is possible to include negations of attributes, like in this one: m1 ^ :m2::: ^ mk ! :m. The concept of the implication as a formula is rei ed in de nition of the rule: De nition 8. Let C; Hi 2 LK , C 2= fH1; H2; :::Hkg; k 0. Then: 1. The rule R = (H1; H2:::; Hk ! C) is an implication (H1 ^ H2::: ^ Hk ! C); 2. The premise R of a rule R is a set of letters fH1; H2:::; Hkg; 3. The conclusion is R! = C; 4. If R1 = R2 and R1! = R2!, then R1 = R2.
(R) = (R! j R ) = (R
^ R!) (R )
Keeping eye on K0, let us try to watch what is happening on Knoise with the implications m1 ! m3 and m1 ! m3. They stopped to be contextual tautologies, but we still can stick to the corresponding rules with reasonable likelihoods: (m1 ! m2) = 45 and (m3 ! m2) = 65 .
The core idea of the approach is to exploit Theorem 1. An operator of a direct inference could be easily adapted to employing probabilistic rules in contrast to formal context implications.
follows: on the set of the rules R works as R(L) = L [ fC j 9R 2 R : R L; R! = Cg:
4
Note, that the de nition 10 accepts any set of rules. To produce a relevant
and consistent set of generalized concepts, additional restrictions for this set are
needed. Following the [
De nition 13 (re nement). R1 > R2, if R2 @ R1 and (R1) > (R2). For example, the rule m1 !
m2 from Knoise has the only unconditional rseulbartuiolen:: (?(?!!mm2)2@) =(m1180 != m45 2=). This could not be considered as a re nement (m1 ! m2). However, (m3 ! m2) > (? ! m2) because (? ! m2) = 180 < 56 = (m3 ! m2).
The class M1 requires that the rules have a greater conditional probability than an unconditional probability of C, i.e. the rule is guaranteed to be useful in reasoning: De nition 14. R 2 M1(C) ,
(R) > (R!); R! = C.
The class M2 requires a rule to be speci c { we cannot improve probability by re ning the rule: De nition 15. R 2 M2(C) , R 2 M1(C) and [R @ R~ ) (R~) (R)]
The rule (m3 ! m2) could be re ned up to the (:m1 ^ m3 ! m2) due to the inequality: (m3 ! m2) = 56 < 1 = 33 = (:m1 ^ m3 ! m2). The last rule satis es all M2 conditions, and thus (:m1 ^ m3 ! m2) 2 M2(m2).
The class Imp contains all exact implications. So does any contextual tautology: De nition 16. R 2 Imp(C) , R!(R) = C and (R) = 1
We also consider compound classes for entire set of letters: De nition 17. M1 = S M1(C)
C2LK Remark 2. M2 and Imp are de ned similarly.
All exact implications are indeed necessary to ensure a completeness property for the prediction operator. In turn, a set of rules must consist only from the M2 rules in order to obtain a consistency property. The set of the letters L is called consistent, if it does not contain an atom C and its negation :C.
R, then the set of rules R is called complete.
De nition 19. By a system of the rules, we will call any R M2. 5
De nition 20. The set of attributes M is consistent, if L 2 M ) :L 2= M .
R must avoid inconsistent inferences [
ible and consistent for any system of the rules R.
R(L) is also compat
Somewhat more di cult, but still solvable, is the question of the inconsistency of prediction closures. Let us assume R to be a complete set of rules and R to be the corresponding prediction operator. It is important to note that the rule systems containing M2 are always complete.
R(L) is inconsistent and incompatible.
The xed points of a prediction operator are clear to be the candidates for
concept intents. What about concept extents? The principles proposed in [
For example, let Ksquares be a context depicted as two disjoint squares (which are two independent formal concepts). To bring extra complexity, we also alter some entries:
Note that the most speci c rules referring to M2 are (mi=1:::4 ! :mj=5:::8), however rule m5 ! :mi=1:::4 is not. There is a more speci c rule for the last one: (m5 ^ m6 ! :m1) = 1 > 45 = (m5^ ! :m1). This is how noise is handled being encapsulated in probability and re nement.
To pick up the rst object from Ksquares, rstly, the prediction operator computes a closure: (g10) = fm1; m2; m3; m4; :m5; :m6; :m7; :m8g. And secondly, all objects with the same closure are composed into a concept with the extent fg1; g2; g3; g4g.
De nition 21. By a probabilistic formal concept on K = (G; M; I) we mean any pair (A; B) which satis es (B) = B; A =
[ C B; (C)=B
GC
Our selection is also justi ed by the following statement, relating probabilistic and ordinary formal concepts on the same context.
concepts C, such that N =
A: 7
For practical applications, a computational problem should be solved. It is still exponentially hard if we require a full M2 set enumeration.
A semantic probabilistic inference as an enumeration procedure has been
described in details in [
The rules extraction routine is based on exploiting a Semantic Probabilistic Inference (SPI) approach. It requires each path in the inference graph to be a sequence of semantic inferences:
R0 = ? and Rm is the strongest probabilistic law.
Now let us assume that some system of the rules R on a context K has already been discovered by semantic probabilistic inference. The probabilistic concept de nition implies the following closure-search procedure. 1. Set the step counter k = 1 and generate the set C(0) = f R(R ) j R 2 Rg.
In fact, this may be an arbitrary family of letter sets to be extended up to their probabilistic concepts closures. The set C(0) is almost always redundant, but it should be enough to cover all statistically signi cant attribute sets; 2. On the step k > 1 in case C(k) = ? the algorithm nishes the execution and outputs a list of detected probability concepts; 3. On the step k > 1 the set A = fg 2 G j R(g0 \ B) = Bg is computed for each B 2 C(k). If A 6= ?, the pair (A; B) is added to the list of the found concepts. It corresponds to a join operation on the concept lattice and subsequently climbs to superordinate levels of the lattice; 4. The set C(k+1) = f R(B [ C) j B; C 2 C(k)g n C(k) is generated. In fact, actual prediction closures are computed on this step; 5. Let k := k + 1 and go to the step 2.
The algorithm could be applied to a context recovery task as well as to a wide variety of data mining problems, such as classi cation and clusterisation tasks. In the nal section we will focus on handling noise in a toy, a rather hard context recovery task. 8
Earlier we considered the Ksquares context very simple but illustrative. A more sophisticated example should contain more interactions between concepts, both in extent and intent components. Also more noise should be produced.
To measure some performance issues, we will set up several modi cations of a single context. Modi cations di er at levels of a noise and there may be a number of data duplicates, when producing more data is necessary. An initial context has been composed from rectangle blocks, easy to be recognized as formal concepts (let them be denoted as "solid" concepts).
A set of experiments was based on: 1. Kexp { the initial context, depicted on Fig. 1. 2. Kx3 { similar to Kexp, except it contains 3 duplicates of each Kexp object; 3. Kx3:n05 = Kx3 + randomly in icted binary noise, Bernoulli distributed with p = 0:05 4. Kx3:n04 = Kx3 + noise, p = 0:04 5. Kx3:n03 = Kx3 + noise, p = 0:03
The primary characteristics of the datasets are presented in Table 5.
Context jGj jM j # Concepts # Solid # Logical Noise Kexp 61 8 5 + 4 + 2 5 6 + 4 0 Kx3 183 8 5 + 4 + 2 5 6 + 4 0 Kx3:n05 183 8 5 + 4 + 2 5 6 + 4 0.05 Kx3:n04 183 8 5 + 4 + 2 5 6 + 4 0.04
Kx3:n03 183 8 5 + 4 + 2 5 6 + 4 0.03
The rst stage in executing a closure-search procedure is a rules extraction routine. According to the method discussed in Section 7, a computer program was implemented to perform a semantical probabilistic inference. For each context a set of rules has been obtained and has eventually been used in a closure-search procedure.
While increasing a noise level, a context becomes less and less clear and requires more and more rules for describing attribute associations. A minor noise produces an insigni cant e ect and a ords to solve the problem almost exactly.
Following [
jEj jOj
The experiment results are presented in Table 7. In addition to the performance indexes, the data are presented separately for the solid concepts and the join-concepts.
Context jOj jO \ Ej jO n Ej jE n Oj Precision Recall
Kx3 6 + 4 6 + 4 0 + 0 0 + 0 1.0 + 1.0 1.0 + 1.0 Kx3:n03 6 + 4 6 + 4 0 + 0 0 + 0 1.0 + 1.0 1.0 + 1.0 Kx3:n04 6 + 4 6 + 1 0 + 3 0 + 0 1.0 + 1.0 1.0 + 0.25
Kx3:n05 6 + 4 6 + 3 0 + 1 0 + 1 1.0 + 0.75 1.0 + 0.75
It was rather easy for a closure-search procedure to determine all formal concepts without noise.
However, even on noisy contexts the algorithm has been able to restore the
original set of concepts with a moderate accuracy. All probabilistic concepts
encountered by the algorithm may be essentially associated with the original images
in ordinary concepts, while some non-primal concepts have been leaked.
Nevertheless, it seems that probabilistic formal concepts perform more accurately, in
comparison with a stability approach [
Indeed, the main advantage may not even be the method accuracy: probabilistic formal concepts are able to discover concepts on big data frames. The estimated computational complexity for SPI is jM jd+2 jGj, and one for a closuresearch seems to be j j jM jc jGj, where 3 < c < 4 (the estimation is empirical and still needs to be checked). Noise induces extra complexity but using a Pentium 4 2-core 2.4GHz computer is enough to solve a 321x26 context with 10% noise in about 10 minutes, while it takes 5 minutes to complete a 3% noise task. 9
The introduced method has been experimentally and theoretically proven to
be correct and accurate. Some extra experiments have been proposed in earlier
works [