Binary factor analysis (BFA, also known as Boolean Factor Analysis) is a nonhierarchical analysis of binary data, based on reduction of binary space dimension. It allows us to find hidden relationships in binary data, which can be used for data compression, data mining, or intelligent data comparison for information retrieval. Unfortunately, we can't effectively use classical (i.e. non-binary) factor analysis methods for binary data. In this article we show an approach based on utilizing formal concept analysis to compute nonhierarchical BFA. Computation of a concept lattice is a computationally expensive task too, still it helps us to speed up the BFA computation.
Binary data are one of the basic stones of computers. In the ancient age of computer science even non-binary information was forcibly transformed into and stored in binary form, usually because of technical limitations. Today we can still see binary data on a physical level, but not on a logical level. Instead, majority of information is usually recorder and stored in its native or nearly native form, which is non-binary in most cases. Sometimes, it goes even further - with the help of fuzzy computing, even vague information can be processed successfully. From one particular point of view, the vagueness can be understood as a counterpart of the strictly binary data.
Data analysis and searching for important, but often hidden information isn’t a new theme, it was already subject of statistics (statistology) long time before informatics become an independent science. Although data analysis is in no way new theme, it’s still very current one. From computer science point of view, it’s important especially because of rapidly growing importance of Internet, or as a consequence of general emphasis on economics and economical achievements.
In this point we realize, that with the current boom of new kinds of data analysis and data mining, binary data is no more in the main focus. Although people perceive the majority of real world quantities as non-binary, some information still has got binary nature. In poetic words: ”Binariness can occur.” We can use non-binary data analysis techniques for binary data as well, but these techniques are usually based on linear algebra, approximation or finding of global minima/maxima, and those don’t work well in the binary world. They all fail because of the specific nature of binary data, which also requires specific analytical methods.
Our goal is the research in the filed of binary factor analysis (BFA). BFA is a nonlinear analysis of binary data, where neither classical linear algebra, nor mathematical (functional) analysis can be used. In the past, it was repeatedly experimentally proven that classical non-binary methods followed by the alignment of the results into binary or other dichotomous values give ill results. This resulted in creation of some new methods, which use boolean (binary) algebra. These binary methods were published in last 8 years, and are based on neural networks, combinatorial searching, genetic algorithms, and transformation to the problem of concept lattices. This paper focuses to the approach based on formal concepts. 2 2.1
To describe the problem of Binary Factor Analysis (BFA) we can paraphrase
BMDP’s documentation (Bio-Medical Data Processing, see [
BFA is a factor analysis of dichotomous (binary) data. This kind of analysis
differs from the classical factor analysis (see [
The goal of BFA is to express p variables (x1, x2, . . . , xp) by m factors (f1, f2, . . . , fm), where m p (m is considerably smaller than p). The model can be written as
X = F
A x1,1 . . . x1,p f1,1 . . . f1,m ... . . . ... = ... . . . ... where is binary matrix multiplication. For n cases, data matrix X, factor scores matrix F, and factor loadings matrix A. The elements of all matrices are valued 0 or 1 (i.e. binary). Binary factor analysis uses boolean algebra, so matrices of factor scores and loadings are both binary. See the following example: The result is 2 in classical algebra but it’s 1 when using boolean algebra. [1 1 0 1] · 10 = 1 · 1 + 1 · 1 + 0 · 0 + 1 · 0 = 2 [1 1 0 1] · 10 = 1 · 1 ⊕ 1 · 1 ⊕ 0 · 0 ⊕ 1 · 0 = 1
Sign ⊕ marks disjunction (logical sum), and sign · mars conjunction (logical conjunction). Note that since we focus to binary values, the logical conjunction is actually identical to the classic product.
In classical factor analysis, the score for each case, for a particular factor, is a linear combination of all variables: variables with large loadings all contribute to the score. In boolean factor analysis, a case has a score of one if it has a positive response for any of the variables dominant in the factor (i.e. those not having zero loadings) and zero otherwise. 2.3
Obviously, not every X can be expressed as F A. The success of BFA is measured by comparing the observed binary responses (X) with those estimated by multiplying the loadings and the scores (Xˆ = F A). We count both positive and negative discrepancies. Positive discrepancy is when the observed value (in X) is one and the analysis (in Xˆ) estimates it to be zero, and reversely negative discrepancy is when the observed value is zero and the analysis estimates it to be one. Total count of discrepancies d is a suitable measure of difference between observed values xi,j and calculated values xˆi,j .
n p
d = X X
Let’s summarize the terminology we use. Data to be analyzed are in matrix X.
Its columns xj represent variables, whereas its rows xi represent cases. The
factor analysis comes out from the generic thesis saying that variables, we can
observe, are just the effect of the factors, which are the real origin. (You can
find more details in [
The result is the pair of matrices. Matrix of factor scores F expresses the input data by factors instead of variables. Matrix of factor loadings A denfies the relation between variables and factors, i.e. each row ai defines one particular factor.
As a basic example (see [
BFA can be also used to analyse a collection of text documents. In that case the data matrix X is built up of a collection of text documents D represented as pdimensional binary vectors di, i ∈ 1, 2, . . . , n. Columns of X represent particular words. Particular cell xi,j equals to one when document i contains word j, and zero otherwise. In other words, data matrix X is built in a very intuitive way.
It should be noted that some kind of smart (i.e. semantic) preprocessing
could be made in order to let the analysis make more sense. For example we
usually want to take world and worlds as the same word. Although the binary
factor analysis has no problems with nfiding this kind similarities itself, it is
computationally very expensive, so any kind of preprocessing which can decrease
the size of input data matrix X is very useful. We can also use WordNet, or
thesaurus to combine synonyms. For additional details see [
In classic factor analysis, we don’t even try to find 100% perfect solution,
because it’s simply impossible. Fortunately, there are many techniques that give a
good suboptimal solution (see [
You can find the basic BFA solver in BMDP – Bio-Medical Data Processing
software package (see [
One interesting suboptimal BFA method comes from Hu´sek, Frolov et al.
(see [
Although the mentioned neural network based solver is promising, we actually didn’t have any one really exact method, which could be used to proof the other (suboptimal) BFA solvers. So we started to work on it. 4
The very basic algorithm blindly searches among all possible combinations of F and A. This is obviously 100% exact, but also extremely computational expensive, which makes this kind of solver in its basic implementation simply unusable.
To be more exact, we can express the limits of blind search solver in units
current computers. of n, p and m. Since we need to express matrix X as the product of matrices F
m and m × p in size, we need to try on all combinations of m · (n + p) bits. And this is very limiting, even when trying to nfid only 10 data set (m
= 3, n = 10, p = 10), we end up with computational complexity of 2m· (n+p) = 260, which is quite behind the scope of
Although the blind search algorithm can be optimized (see [
B ⊆ Y and (A, B) ∈ R.
For subsets A ⊆
X and B ⊆ Y , we define Another method of solving BFA problem is based on concept lattices. This section gives minimum necessary introduction to concept lattices, and especially formal concepts, which are the key part of the algorithm.
Triple (X, Y, R), where X and Y are sets, and R is a binary relation R ⊆ is called formal context. Elements of X are called objects, and elements of X × Y , Y are called attributes. We say ”object A has attribute B”, just when A ⊆ A↑ = {b ∈ B | ∀a ∈ A : (a, b) ∈ R} B↓ = {a ∈ A | ∀b ∈ B : (a, b) ∈ R} X, tu tu
In other words, A↑ is the set of attributes common to all objects of A, and similarly B↓ is the set of all objects, which have all attributes of B. Note: We just denfied two operators ↑ and ↓: ↑ : P (X) → P (Y ) ↓ : P (Y ) → P (X) where P (X) and P (Y ) are sets of all subsets of X and Y respectively.
Let (X, Y, R) be a formal context. Then pair (A, B), where A ⊆ A↑ = B and B↓ = A, is called formal concept of (X, Y, R). X, B ⊆
Set A is called extent of (A, B), and set B is called intent of (A, B).
Let (A1, B1) and (A2, B2) be formal concepts. Then (A1, B1) is called subconcept of (A2, B2), just when A1 ⊆
A2 (which is equivalent to B1 ⊇ (A1, B1) ≤ (A2, B2). We can also say that (A2, B2) is superconcept of (A1, B1). B1). We write
In this article we just need to know the basics of concepts and their meaning.
For more detailed, descriptive, and well understandable introduction to Formal
Concept Analysis and Concept Lattices, see [
Y , tu tu 6
If we want to speed up the simple blind-search algorithm, we can try to find
some factor candidates, instead of checking out all possible bit-combinations.
The technique which can help us significantly is Formal Concept Analysis (FCA,
see [
We can still use some good parts of the blind-search program (matrix optimizations, optimized bitwise operations using boolean algebra, etc.), but instead of checking out all possible bit combinations, we work with concepts as the factor candidates. In addition, we can adopt some strategy optimizations (as discussed above) to concepts, so the nfial algorithm is quite fast; its strength actually relies on the concept-building algorithm we use.
So the BFA algorithm is then as follows: algorithm.) 1. Compute all concepts of X. (We use a standalone program based on Lindig’s 2. Import the list of concepts, and optimize it, so it correspond to our optimized data matrix X. (This is simple. We just merge objects and attributes the same way, as we merged duplicate rows and columns of X respectively.) 3. Remove all concepts with too many one’s. (The number of one’s per factor is one of our starting constraints.) 4. Use the remaining concepts as the factor candidates, and nfid the best melement subset (according to discrepancy formulae).
This way we can nfid the BFA solution quite fast, compared to the blind search algorithm. Although the algorithm described here looks quite simple2, there is a couple of things, we must be aware of. 6.2
The most important FCA consequence is that 100% correct BFA solution can
always be found among all subsets of concepts. This is very important, because
it is the main guarantee of the correctness of the concept based BFA solver.
(This is Keprt’s theorem, rfistly published in [
Other important feature of FCA based concepts is that they never directly
generate any negative discrepancy. It is a direct consequence of FCA qualities,
and affects the semantic sense of the result. As we discussed above (and see also
[
The absence of negative discrepancies coming from concepts applies to A matrix only. It doesn’t apply to F matrix, we still can use any suitable values for it. In consequence, we always start with concepts not generating negative discrepancy, which are semantically better, and end up with best suitable factor scores F, which give the lowest discrepancy. So it seems to be quite good feature. 6.3
It’s clear that the data matrix X is usually quite large, and makes the nfiding of the formal concepts the main issue. Currently we use the standalone CL (concept lattice) builder. It is optimized for nfiding concept lattices, but that’s not right what we need. In the future, we should consider adopting some kind of CL building algorithm directly into BFA solver. This will save a lot of time when working with large data sets, because we don’t need to know the concept hierarchy.
We don’t even need to know all the formal concepts, because the starting constraints limit the maximum number of one’s in a factor, which is directly applicable to CL building. 2 Everything’s simple, when you know it.
Here we present three experiments using typical data sets taken from other
papers discussing BFA (see [
Data set p3 is a representative of the simplest data. It is a sparse matrix, 100× 100 bits in size. This data matrix can be expressed with just 5 factors, what leads to searching for two 500-bit matrices. Due to the sparseness of the p3 data set, the computation complexity is quite low, and allows us to use simple blind search.
Data set p2 is the same in size, but this one is not a sparse data set. Its theoretical complexity based on its size is the same as the complexity of p3, but the real complexity makes it impossible to be solved with simple blind search. In other words, our new algorithm based on formal concepts is the only way to compute exact BFA on p2 data set.
The results are shown in table 1. Data set p3 is rather simple, its factor loadings (particular rows of A) all contain just 3 one’s. The first row in the table shows that it takes over 61 minutes to find these factors, when we search among all combinations with 2, 3 or 4 one’s per factor. If we knew that there are just 3 one’s per factor, we could specify it as a constraint, and got the result in just 12 seconds (see table 1, row 2). Indeed we usually don’t know it in real situations.
Third row shows that when using formal concepts, we can nfid all factors in just 0 seconds, even when we search all possible combinations with 1 to 10 one’s per factor. You can see the concept lattice in gfiure 1, with factors expressively circled.
Data set p2 is much more complex, because it is created from factors containing 6 one’s each. In this case the blind-search algorithm was able to nfid just 2 factors. It took almost 12 minutes, and discrepancy was 743. In addition, the two found factors are wrong, which is not a surprise according to the fact that there are actually 5 factors, and factors can’t be searched individually. It was 3a 39 13o 1a 77 77o not possible to nfid more factors using blind-search algorithm. Estimated times for computing 3 to 5 factors with the same constraints (limiting number of one’s per factor to 6) are shown in table 2. It shows that it would take up to 3.5× 109 years to nfid all factors.
As you can see at the bottom of table 1, we can find all 5 factors of p2 easily in just 7 seconds, searching among candidates containing 1 to 10 one’s. The time can be reduced to 0 seconds once again, if we reduce searching to the range of 6 to 8 one’s per factor. You can see the concept lattice in figure 2, with factors marked as well. As you can see, the factors are non-overlapping, i.e. they are not connected to each other. Note that in general factors can arbitrarily overlap. Berry’s data set is an example of real data. It is a set of text documents describing occurrences of 18 words in 14 documents, i.e. X is 14 × 18 bits in size. We can’t even try to find the factors with simple blind search, because it would take years to find just a few of them. On the other side, we can nfid 10 or more factors with help of formal concepts.
Binary Factor Analysis with 9a 279 31o 10a 190 19o 8a 288 36o 9a 270 30o 13a 260 20o
This data set is interesting in that it needs 14 factors to be successfully expressed as F A. You can see all factors in figure 3, with all 14 factors circled.
This paper presented an idea of exploiting theory of formal concept analysis to do a nonhierarchical analysis of binary data, namely binary factor analysis. The experiments revealed that this approach is a big step forward from the usual simple blind search.
Still, we don’t understand this approach as a nfial step. It is quite fast on
small data sets, but the complexity quickly increases as data set becomes larger.
Formal concepts-based algorithm can be also used as a reference algorithm for
testing the promising neural network-based solver (see [