Over the past decade, the two most fundamental Boolean matrix factorization (BMF) algorithms, GreCon and GreConD, were proposed. Whereas GreConD has become one of the most popular algorithms, GreCon-an algorithm on which the GreConD was build-is somewhat forgotten. Although GreCon may produce better results than GreConD, computing BMF via this algorithm is time consuming. We show that the reasons for not using GreCon algorithm are no longer truth. We revise the algorithm and on various experiments we demonstrate that the revised version is competitive to current BMF algorithms in term of running time. Moreover, in some cases GreCon outperforms GreConD-the fastest BMF algorithm. Additionally, we argue that a search strategy of GreConD, notwithstanding it provides a good result, is limited. Furthermore, we show that our novel approach to GreCon opens a new door to further BMF research.
Boolean Matrix Factorization (BMF), also known as Boolean matrix decomposition, is a well-established and widely used tool in data-mining and data processing of Boolean (1/0) data.
In the last decade there was a huge effort dedicated to a BMF research. In
many works (e.g. [
In the pioneer work [
GreConD come from later works. factors. From these candidates the final factors are selected via a greedy choice. A detailed description of these two algorithms is provided in Section 2.
While the GreConD has become extremely popular, mainly due to its simple
architecture and performance—in a fact GreConD is one of the fastest BMF
algorithms and according to various experimental evaluations (see e.g. results in
[
The main aim of this paper is to show that the reasons for not using GreCon algorithm are no longer valid—thanks to the development of algorithms for FCA and, paradoxically, thanks to the development of the GreConD algorithm. The main aim can be summarized as follows: (i) We reimplemented the GreCon algorithm and on various experiments we demonstrate that the revised version is competitive in term of running time with existing BMF algorithms. Moreover, the new implementation in some cases outperforms GreConD. (ii) We show, that the search strategy used by GreConD, despite it provides a good result, is limited. In the paper, we compare the search spaces of GreCon and GreConD and we briefly address the comparison of the results provided by both of them. (iii) Last but not least, the massive speed up of GreCon presented in the paper opens a new door to further BMF research. Namely, we utilize the GreCon search strategy on a restricted set of formal concepts. Although this is not a completely new idea, its application was limited, because of the speed of existing algorithms. Moreover, in an experimental evaluation we show that this approach may provides better results.
The rest of the paper is organized as follows. In Section 2, we provide a brief introduction to BMF, overview of related works and a description of the basic algorithms, GreCon and GreConD. Then, in Section 3, a comparison of GreCon and GreConD is discussed. Section 4 provides a description and a pseudocode of the redesign GreCon algorithm. In Section 5, we present results from various experimental evaluations. Section 6 summarizes the paper and outlines a further research directions. 2
A good overview of BMF and related topics can be found e.g. in [
A general aim of BMF is for a given Boolean matrix I ∈ {0, 1}m×n to find matrices A ∈ {0, 1}m×k and B ∈ {0, 1}k×n for which
I ≈ A ◦ B
(1)
where ◦ is Boolean matrix multiplication, i.e. (A ◦ B)ij = maxlk=1 min(Ail, Blj ),
and ≈ represents an approximate equality. This approximate equality is assessed
by || · || (i.e. by number of 1s) and with the corresponding metric E which is
defined for matrices I ∈ {0, 1}m×n, A ∈ {0, 1}m×k, and B ∈ {0, 1}k×n by
E(I, A ◦ B) = ||I
(A ◦ B)||,
(2)
where is Boolean subtraction which is the normal matrix subtraction with an
alternative definition 0 − 1 = 0. In other words, function E is a number of 1s
in I that are not in (A ◦ B). The metric (2), or its variant, is generally used to
assess the quality of factorization [
A decomposition of I into A◦B may be interpreted as a discovery of k factors that exactly or approximately describe the data: interpreting I, A, and B as the object-attribute, object-factor, and factor-attribute matrices. The model (1) can be interpreted as follows: the object i has the attribute j, i.e. Iij = 1, if and only if there exists factor l such that l applies to i and j is one of the particular manifestations of l. 2.1
We already mentioned that the BMF is closely connected to FCA. The formal context hX, Y, Ii with m objects and n attributes can be seen as a Boolean matrix I ∈ {0, 1}m×n where Iij = 1 if hx, yi ∈ I, and vice versa. To every I ∈ {0, 1}n×m one may associate a pair h↑, ↓i of arrow operators assigning to sets C ⊆ X = {1, . . . , m} and D ⊆ Y = {1, . . . , n} the sets C↑ ⊆ Y and D↓ ⊆ X defined by
C↑ = {j ∈ Y | ∀i ∈ C : Iij = 1},
D↓ = {i ∈ X | ∀j ∈ D : Iij = 1}.
A pair hC, Di for which C↑ = D and D↓ = C is called a formal concept. The set of all formal concepts for formal context hX, Y, Ii is defined as follows
B(X, Y, I) = {hC, Di | C ⊆ X, D ⊆ Y, C↑ = D, D↓ = C}.
For the sake of simplicity, we denote the set of all formal concepts for Boolean matrix I by B(I). The set of all concepts can be equipped with a partial order ≤ such that hA, Bi ≤ hC, Di iff A ⊆ C (or D ⊆ B). The whole set of partially ordered formal concepts is called the concept lattice of I.
The set of formal concepts that is generated by single object (denoted by O(I)) is called the set of object concepts, i.e. O(I) = {hi↑↓, i↑i | ∀i ∈ X}, and the set that is generated by single attribute (denoted A(I)) is called the set of attributes concepts, i.e. A(I) = {hj↓, j↓↑i | ∀j ∈ Y }.
Now, we explain the connection between a set of formal concepts and the BMF. Every set F = {hC1, D1i, . . . , hCk, Dki} ⊆ B(I), with a fixed indexing of the formal concepts hCl, Dli induces the m × k and k × n Boolean matrices AF and BF by and (AF )il = (BF )lj = 1, if i ∈ Cl, 0, if i 6∈ Cl, 1, if j ∈ Dl, 0, if j 6∈ Dl, for l = 1, . . . , k. That is, the lth column of AF and lth row BF are the characteristic vectors of Cl and Dl, respectively. The set F is called a set of factor concepts. The entry Iij = 1 is covered by formal concept hA, Bi if i ∈ A and j ∈ B. 2.2
The GreCon2 algorithm [
One of the most successful algorithms for BMF is the GreConD3 algorithm [
In what follows, we demonstrate differences between the search strategies of GreConD and GreCon. Let us consider matrix I, depicted below, with rows {1, 2, 3, 4, 5} and columns {a, b, c, d, e, f } and two sets of factor concepts F1 and F2 that are computed via GreConD and GreCon respectively. The corresponding matrices are:
The search space, in each iteration of GreCon, is the set of all formal concepts. Namely, in each the iteration all formal concepts in the concept lattice of I (depicted in Figure 1) are considered as candidates for factors, in order in they were generated.
The search space of GreConD is different. GreConD always starts with attributes concepts. Then it extends the selected concept via some promising attributes, i.e. GreConD search space is limited to chains in the corresponding concept lattice and the selection of a particular chain is driven by the greedy choice. Note, the columns of the input matrix are considered in a fixed order. As a consequence of this GreConD may stop in some local maximum.
In a fact, this is true for the first iteration on our example data matrix I. GreConD starts with attribute a which generates h{3, 4}, {a, e}i. All remaining candidates (attribute concepts) have smaller or equal size as the first concept. Then, h{3, 4}, {a, e}i is extended by some attributes to obtain a potentially better candidate (candidate which covers more not yet covered entries of I), namely attributes b, d, f are considered, meanwhile c is skipped because a, c, e do not generate any formal concept. The concepts considered as candidates for factors in the first iteration of GreConD are depicted by black nodes in Figure 1. As a consequence of this GreConD is not able to discover the best choice h{1, 4, 5}, {d, e}i.
Despite the differences between the algorithms, the results produced by them are comparable—GreConD produces slightly worse results than GreCon—in terms of the overall coverage which is evaluated by the metric (2). The comparison of the coverage is shown in Figure 2. Note, the coverage is computed as 1 − E(I|,|AI|◦|B) .
1.0 0.8 aeg0.6 r e v oC0.4 0.2 Fig. 2: Comparison of coverage produced by factorization obtained via GreCon and GreConD on selected real-word data.
This observation—in fact results presented in Figure 2 are standard in BMF—
was confirmed by previous works e.g. [
In [
104 105 100 101 103
104
One may easily see, that the difference between factorizations may be very large despite small differences in Figure 2. In case of Customers dataset (Figure 3b) the datapoints are gathered close to the diagonal which means that there is a small difference between the corresponding factors. In contrast with this a significant difference between GreCon and GreConD on DNA dataset (Figure 3c) may be observed.
Now we describe a basic idea of redesigning the GreCon algorithm. We call the redesigned version of the algorithm GreCon2 because it is mainly an efficient implementation of the original GreCon algorithm.
Differently from GreCon, GreCon2 does not need repeatedly compute the number of not yet covered entries for each formal concept—which is the most time consuming task in GreCon. Instead of this the actual cover for all formal concepts is maintained for the entire running time. For this purpose, a convenient data structure which enables an additional speed up is used. Additionally, GreCon2 does not iterate over all the formal concepts (i.e. data structure) but only over the numbers (integers). A pseudocode of GreCon2, which accepts as an input Boolean matrix I ∈ {0, 1}m×n, is depicted in Algorithm 1.
Input: Boolean matrix I ∈ {0, 1}m×n
Output: Set F of factor concepts. 1 concepts ← B(I); 2 foreach hAl, Bli ∈ concepts do 3 covers[l] ← ||Al|| · ||Bl|| 4 foreach (i, j) ∈ hAl, Bli do 5 append l to list cell[i · n + j] 6 end 7 end 8 while AF ◦ BF 6= I do 9 add hAl, Bli which maximizes covers[l] to F 10 foreach (i, j) ∈ hAl, Bli do 11 foreach k ∈ cell[i · n + j] do 12 covers[k] ← covers[k] − 1 13 end 14 delete list cell[i · n + j] 15 end 16 end
In the first phase, GreCon2 computes the set of all formal concepts B(I) (line 1). Then the algorithm computes a coverage for each concept—stores in array covers (line 3)—and for each Iij constructs a list of concepts that cover Iij (lines 4–6). These lists are stored in array cell on a corresponding indexes (line 5). Note that accessing the entries of arrays covers and cell requires a constant time.
In the second phase, GreCon2 performs linear search in array covers and adds to F concept hAl, Bli for which the value of cover[l] is maximal (line 9). For each Iij covered by hAl, Bli GreCon2 decrease values in array covers for each concept that covers Iij (lines 10–13) and deletes the list for Iij (line 14). The second phase is repeated until all the entries of the input data matrix are covered or, equivalently, there is no covers[l] > 0.
In this section, we present results of an experimental comparison of GreCon, GreConD and GreCon2. We implemented4 all three algorithms in the Swift programming language with the same level of optimization to make the comparison fair. 5.1
We used eight real-world datasets, namely Advertisement, Mushroom, Tic Tac
Toe from [
Table 2 shows that in all cases GreCon2 significantly outperforms original GreCon algorithm. Moreover, in most cases GreCon2 outperforms GreConD. GreConD performs well on datasets where the number of attributes 4 All implementations together with scripts that performs all presented experiments are available on the GitHub https://github.com/rvyjidacek/experiments-cla2020 is rather small. This is the reason why GreConD outperforms GreCon2 on Mushroom dataset which has a larger number of concepts and only a small number of attributes.
Note that our implementation of GreCon2 may be improved. Namely the construction phase of the algorithm (lines 2–6 in Algorithm 1) can be a part of FCbO algorithm (line 1). We decide to keep these two parts separated to make the comparison between GreCon and GreCon2 fair. A significant speed up provided by GreCon2 allows us to consider the set of all formal concepts as a set of candidates for factors. Despite considerable speedup, the set may be still too large (like in the case of Mushroom dataset). As a very promising research direction seems to be a restriction of the set of formal concepts, i.e. skip formal concepts that are potentially not a good candidates for factors. To demonstrate this idea, we consider in GreCon2 the set O(I) ∪ A(I) instead of B(I). We perform the same experiments as above and compare GreCon2 with the restricted search space and unchanged GreConD.
From the results shown in Table 3, we observe that GreCon2 significantly outperforms GreConD in therm of running times. Moreover, in this case GreCon2 produces slightly better results in terms of overall coverage (see Figure 4) and in some cases a smaller number of factors than GreConD (see Table 3).
GreCon2
GreConD 100 200 300 400 500 600 700
Number of Factors (a) Advertisement 0 25 50 75 Num1b0e0r of Factors 150 175 200
125 (b) Americas small GreCon2 GreConD 100 We proposed a revised version of GreCon algorithm which significantly outperforms the original algorithm and which is competitive to the fastest BMF algorithms. Additionally, we show that our approach enables us to consider a larger search space than one of the most popular BMF algorithms, which in the past has caused that GreCon to be forgotten in BMF research.
Further research shall include an efficient implementation of the approach; a deep investigation of how the set of all formal concepts may be restricted without affecting the outcome quality; and last but not least, a parallelization of the approach.
Supported by Junior research Grant No. JG 2020 003 of the Palacky´ University Olomouc. Support by Grant No. IGA PrF 2020 030 of IGA of Palacky´ University is also acknowledged.