The paper explores a utilization of Boolean factorization as a method for data preprocessing in classification of Boolean data. In previous papers, we demonstrated that data preprocessing consisting in replacing the original Boolean attributes by factors, i.e. new Boolean attributes that are obtained from the original ones by Boolean factorization, improves the quality of classification. The aim of this paper is to explore the question of how the various Boolean factorization methods that were proposed in the literature impact the quality of classification. In particular, we compare three factorization methods, present experimental results, and outline issues for future research.
In classification of Boolean data, the objects to classify are described by Boolean
(binary, yes-no) attributes. As with the other classification problems, one may
be interested in preprocessing of the input attributes to improve the quality of
classification. With Boolean input attributes, we might want to limit ourselves
to preprocessing with a clear semantics. Namely, as it is known, see e.g. [
We use the following notation. We denote by X = {1, . . . , n} a set of objects which are given along with their input Boolean attributes which form the set Y = {1, . . . , m}, and a class attribute c. The input attributes are described by an n × m Boolean matrix I with entries Iij (entry at row i and column j), i.e. Iij ∈ {0, 1} for every i, j. Alternatively, I may be considered as a representation of a binary relation between X and Y and, hence, we may speak of a formal context hX, Y, Ii, etc. Since there is no danger of confusion, we conveniently switch between the matrix and relational way of looking at things. The class attribute c may be conceived as a mapping c : X → C assigning to every object i ∈ X its class label c(i) in the set C of all class tables (note that C may contain more than two labels).
The preprocessing method along with the three particular methods of Boolean matrix factorization is described in Section 2. Section 3 describes the experiments and provides their results. In Section 4 we conclude the paper and provide some directions for future research. 2 2.1
Boolean Matrix Factorization and Its Utilization
We denote by {0, 1}n×m the set of all n × m Boolean matrices and by Ii and I j the ith row and jth column, respectively, of matrix I. In BMF, the general aim is to find for a given I ∈ {0, 1}n×m (and possibly other parameters, see Problem 1 and Problem 2) matrices A ∈ {0, 1}n×k and B ∈ {0, 1}k×m for which
I is (approximately) equal to A ◦ B, with ◦ being the Boolean matrix product given by k (A ◦ B)ij = _ Ail · Blj ,
l=1
where W denotes the maximum and · the ordinary product. Such an exact or
approximate decomposition of I into A◦B corresponds to a discovery of k factors
(new Boolean variables) that exactly or approximately explain the data. Namely,
factor l = 1, . . . , k, may be represented by A l (column l of A) and Bl (row l
of B): Ail = 1 indicates that factor l applies to object i while Blj indicates that
(1)
(2)
attribute j is a particular manifestation of factor l (think of person A as object,
“being fluent in English” as attribute, and “having good education” as factor).
The least k for which an exact decomposition I = A ◦ B exists is called the
Boolean (or Schein) rank of I [
The matrices I, A, and B are usually called the object-attribute matrix,
the object-factor (or usage) matrix, and the factor-attribute (or basis vector)
matrix [
E(C, D) = ||C − D|| = Pim=,1n,j=1 |Cij − Dij |. (3) E(I, A ◦ B) may be used to asses how well the product A ◦ B approximates the input matrix I.
input: I ∈ {0, 1}n×m, positive integer k
output: A ∈ {0, 1}n×k and B ∈ {0, 1}k×m minimizing ||I − A ◦ B||.
This problem is called the discrete basis problem (DBP) in [
input: I ∈ {0, 1}n×m, positive integer ε output: A ∈ {0, 1}n×k and B ∈ {0, 1}k×m with k as small as possible such that ||I − A ◦ B|| ≤ ε.
The two problems reflect two important views on BMF, the first one
emphasizing the importance of the first k (presumably most important) factors,
the second one emphasizing the need to account for (and thus to explain) a
prescribed portion of data. Note that the problem of finding an exact decomposition
of I with the least number k of factors possible is a particular instance of
Problem 2 (put ε = 0). Note also that it follows from the known results that both
Problem 1 and Problem 2 are NP-hard optimization problems, see e.g. [
The idea may be described as follows. For a given set X of objects, set Y of attributes, Boolean matrix I, and class attribute c, we compute n × k and k × m Boolean matrices A and B, respectively, for which A ◦ B approximates I reasonably well (either according to the scenario given by Problem 1 or Problem 2). Then, instead of the original instance hX, Y, I, ci of the classification problem, we consider a new instance given by hX, F, A, ci, with F = {1, . . . , k} denoting the factors, i.e. new Boolean attributes. Any classification model developed for hX, F, A, ci may then be used to classify the objects described by the original Boolean attributes from Y . Namely, one may utilize natural transformations g : {0, 1}m → {0, 1}k and h : {0, 1}k → {0, 1}m between the space of the original attributes and the space of factors which are given by (g(P ))l = Vjm=1(Blj → Pj ) and
k
(h(Q))j = Wl=1(Ql · Blj )
for P ∈ {0, 1}m and Q ∈ {0, 1}k (V and → denote minimum and implication).
These transformations are described in [
Note that since the number k of factors of I is usually smaller than the
number m of attributes (see [
Three Methods for Boolean Matrix Factorization Used in Our
Experiments
Asso [
Experiments
We performed a series of experiments to evaluate the impact of the three Boolean
matrix factorization methods described in Section 2.3 on classification of Boolean
data when using factors as new attributes. The experiments consisted in
comparing the classification accuracy of learning models created by selected machine
learning (ML) algorithms from the data with the original attributes replaced by
factors. The factors are computed from the input data by the three selected
factorization methods. The ML algorithms used in the comparison are: the reference
decision tree algorithms ID3 and C4.5 (entropy and information gain based), an
instance based learning method (Nearest Neighbor, NN), Naive Bayes learning
(NB) and a multilayer perceptron neural network trained by back propagation
(MLP) [
The experiments were done on selected public real-world datasets from UCI
Machine Learning Repository [
The results are depicted in Figures 1 to 5. Each figure contains five graphs for the five ML algorithms used. The graphs show the average percentage rates of correct classifications on the preprocessed data, i.e. the data hX, F, A, ci described by factors instead of hX, Y, I, ci described by the original attributes, cf. Sections 2.2 and 2.3 for each of the three Boolean matrix factorization methods. The percentage rates of GreEssQ, GreConD, and Asso are depicted by the dashed, dot-and-dashed, and dotted lines, respectively. The x-axis corresponds to the factor decompositions obtained by the algorithms and, in particular, measures the quantity |hi, ji ; Iij = 1 and (A ◦ B)ij = 0| |hi, ji ; Iij = 1| , i.e. the relative error w.r.t. 1s of the input matrix I that are left uncovered in A ◦ B for the computed factorization given by A and B. The values on the x-axis range from 0.9 (corresponding to a factorization with a small number of factors that leave 90 % of the 1s in I uncovered) to 0 (corresponding to the number of factors which decompose I exactly, i.e. I = A ◦ B). The average percentage rate of correct classification for the original data hX, Y, I, ci is depicted in each graph by a constant solid line. All the graphs are computed for the testing parts of the datasets used in the evaluation of classification only.
We can clearly see from the graphs for all datasets but breast-cancer that the
best results (average percentage rates of correct classifications) for preprocessed
data are obtained, for all ML algorithms used, by the GreEssQ algorithm,
outperforming both GreConD and, quite significantly, the Asso algorithm. GreConD
outperforms the Asso algorithm, again for all ML algorithms used, for datasets
kr-v-kp and mushroom, but not for the vote dataset. We can also see from the
graphs that sometimes the preprocessed data lead to a better classification
accuracy than the original data even with a few factors covering less than 100 % of
input data. This can be seen for instance for the kr-vs-kp dataset and Nearest
Neighbor and MLP or the mushroom dataset and ID.3, Naive Bayes and MLP.
See [
Particularly interesting seem the results for the breast-cancer dataset. As we can see, the preprocessed data with factors instead of the original attributes are (much) better classified compared to the original data and that this is observable for all ML algorithms used except for Naive Bayes. Furthermore, the number of factors leading to the best average percentage rates of correct classifications is such that the factors cover just 40 % (which corresponds to 0.6 on the x-axis) of input data! This indicates either many superfluous attributes or large noise in the input data that is overcome by using the factors. The GreEssQ and GreConD algorithms are of comparable performance here, both outperforming the Asso algorithm.
0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15 relative decomposition error threshold 0 0 0 0 0 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15 relative decomposition error threshold 0 0 0 0 0 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold 0 0 0 0 0 0.75 0.6 0.45 0.3 0.15
relative decomposition error threshold
We presented an experimental study which shows that when Boolean matrix
factorization is used as a preprocessing technique in Boolean data classification in
the scenario proposed in [
An extended version of this paper will include further factorization
algorithms in the experimental comparison (let us note in this respect that a
technical problem with some such algorithms is that they are poorly described in the
literature). Furthermore, we intend to investigate and utilize further appropriate
transformation functions between the attribute and the factor spaces, in
particular those suitable for approximate factorizations. A comparison with other data
dimensionality techniques, see e.g. the references in [