Formal Concept Analysis aims at finding clusters (concepts) with given properties in data. Most techniques of concept analysis require a dense matrix with no missing values on the input. However, real data are often incomplete or inaccurate due to the noise or other unforeseen reasons. This paper focuses on using matrix factorization methods to complete the missing values in the input data such that it can be used with arbitrary concept analysis technique. The used matrix factorization model approximates the sparse object-item data matrix by a product of two dense factor matrices, thus, mapping objects and items to a common latent space. The mentioned object-factor and item-factor matrices are obtained by a simple stochastic gradient optimization method. We also investigate how the amount of missing values influences the output of the concept analysis. Two measures, well-known in the information retrieval community, have been used for the evaluation of the proposed framework. Real datasets from the UCI Machine Learning Repository were used in our experiments.
Formal Concept Analysis (FCA) deals with data in the form of a table which
rows represent objects and columns represent attributes of objects. A table entry
corresponding to an object x and an attribute y indicates whether or not the
object x has the attribute y. The clusters on the output of FCA are called
concepts, each of which consists of a set of formal objects and a set of formal
attributes, called the extent and the intent, respectively, of the given concept.
The set of all concepts ordered by ≤ forms a concept lattice [
However, real datasets are often incomplete or inaccurate due to the damage
or inconsistency in the data collection process. Incomplete context was first
introduced by Burmeister and Holzer [
The contribution of this paper follows the latter case described above, namely,
to predict the missing values using a matrix factorization method (MF) in the
pre-processing step such that FCA can be used on the completed data. MF, one
of the useful techniques in data mining, allows the decomposition of a sparse1
matrix into two dense matrices such that the product of these two dense matrices
results in a dense matrix which is an approximation2 of the original, sparse
matrix. We use stochastic gradient descent matrix factorization method (SGD
MF) in this paper, which is fast and effective. It is important to note that we need
to adjust the predicted values since these should be from the input values. The
main reason of it is that the resulting dense matrix is just an approximation
of the original one with specific values, e.g. 0 and 1 or 1, 2, 3, 4, 5, etc. The
resulting dense matrix is then scaled [
We also address the problem of the robustness of formal concepts, i.e. the ability to remain unaffected by small variations in an input table. As far as we know, there is no related work investigating the issue that how the concepts computed from a full table differs from those computed from a pre-processed table, i.e. what happens when we remove some values from the original table, complete them with a pre-processing method and compute the concepts on the pre-processed table? We think that this question is quite important for a real-life application of FCA. 2
One direction of estimating missing values in an input matrix is by the use of
association rule mining techniques consisting of two approaches: The first one
discards instances which contain missing data and generate association rules
from the remaining complete data. However, excluding instances with missing
data can bias the result. The second approach takes into account the presence
of missing values in the rule mining process. Note that two or more association
rules may result to different predicted values, thus the so called conflict problem
have to be tackled here. The large number of association rules and the effort to
reduce the conflict problem have led to the usage of generic bases of association
rules. We refer to [
predicted values for these cells is minimal. A “hidden” problem is the percentage of missing values that these approaches permits to complete.
[
Combinations of MF and FCA are introduced in [
A novel approach to combine matrix decomposition and factor analysis is
presented in [
We will just briefly describe FCA, and focus instead on a more detailed description of the used MF technique in this section since we think it could be more interesting to the FCA community. 3.1
Formal Concept Analysis A formal context is a triple (X, Y, I) consisting of two non-empty sets X and Y and a binary relation I between them. The elements of X are called the objects and the elements of Y are called the attributes. (x, y) ∈ I means that the object x has the attribute y.
For a set A ⊆ X and a set B ⊆ Y , define A′ = {y ∈ Y : (∀x ∈ A)(x, y) ∈ I} and B′ = {x ∈ X : (∀y ∈ B)(x, y) ∈ I}. A′ is the set of attributes common to the objects in A and B′ is the set of object which have all attributes in B.
A formal concept of the context (X, Y, I) is a pair (A, B) of a set A ⊆ X of objects and a set B ⊆ Y of attributes such that A′ = B and B′ = A. A and B are called the extent and the intent of the concept (A, B), respectively. Denote the set of all concepts in (X, Y, I) by B(X, Y, I).
Introduce a relation ≤ on B(X, Y, I) by (A1, B1) ≤ (A2, B2)) ⇔ A1 ⊆ A2 ⇔
B2 ⊆ B1, (A1, B1) is called the subconcept of (A2, B2) and (A2, B2) is called the
superconcept of (A1, B1). The set of concepts B(X, Y, I) ordered by ≤ constitutes
the concept lattice (or Galois lattice) of the context (X, Y, I). The so-called main
theorem of concept lattices characterizes the structure of concept lattices. For
further details we refer to [
Stochastic Gradient Descent Matrix Factorization
Stochastic gradient descent matrix factorization (SGD MF) is one of the most
popular factorization techniques [
The goal of this approach is to approximate a sparse matrix X ∈ R|O|×|I| with a product of two (much smaller) matrices W ∈ R|O|×K and H ∈ R|I|×K such that
X ≈ Xˆ = W HT ,
where |O|, |I| are the number of objects and items, respectively, and K is number
of (latent) factors. The ith row of the matrix W is a vector containing K latent
factors describing the object i, and the jth row in matrix H is a vector containing
K latent factors describing the item j [
The estimate xˆij of a missing value at the row i and column j of the sparse matrix X is computed as
K xˆij = (W HT )ij = X wikhjk k=1 where wik (hjk) is the value of W (H) at the ith (jth) row and kth column.
We are interested in such Xˆ which estimates the missing values of X well.
Since we do not know the missing values, we use the following trick, well-known
in the machine learning community [
Our goal is to find those parameters W and H of the model Xˆ for which the RMSE is minimal. However, we have to keep in mind that Xtest is “hidden”, i.e. it represents the “unknown“ missing values, thus, we have to use3 the data we know, i.e. the train set Xtrain. Since |Xtrain| is constant, minimizing RMSE (3) on Xtrain is equivalent to minimizing the sum of errors Pxij∈Xtrain (xij − xˆij )2. Since RMSE is a (loss) function, we use a stochastic gradient descent (SGD)
optimization method [
X
xij∈Xtrain
(xij − xˆij )2 + λ(kW k2 + kHk2)
(4)
where xˆij is defined as in (2) and λ is a regularization term to prevent the
socalled overfitting (i.e. when a model estimates very well the training data but
poorly the test data [
In the training phase we first initialize two matrices W and H with some random values (for example from the normal distribution N (0, σ2) with mean 0 and standard deviation 0.01) and compute the estimation error err =
X xij∈Xtrain 2 eij
K ei2j = (xij − xˆij )2 = (xij − X wikhjk)2
k=1 δwik δ δ δhjk ei2j = −2eij hjk = −2(xij − xˆij )2hjk ei2j = −2eij wik = −2(xij − xˆij )2wik wi(knew) = wik − β h(jnkew) = hjk − β
δ δwik
δ δhjk ei2j = wik + 2βeij hjk ei2j = hjk + 2βeij wik where
We minimize this error by updating the values of W and H in the following
way [
In the next step we use the computed gradient to update the values of wik and hjk: where β is the learning rate controlling the step sizes.
We update W and H for each value of Xtrain in one iteration. The number of iterations, i.e. the number of passes over the full Xtrain is a hyper-parameter of the factorization technique as well as the regularization term λ, the learn rate β and the number of factors K. 4 Only the vectors wi and hj contribute to ei2j , thus we treat the other vectors (rows of W and H) as constants (which derivatives are zero). (5) (6) (7) (8) (9) (10)
As we see, the quality of the model Xˆ depends on the hyper-parameters
used in the learning phase. Also, it can happen that the split of the data into
the train and the test part was done in a way that these two parts have no
similar characteristics, e.g. one part contains large values while the other the
low ones. To prevent this phenomenon to happen we usually use n-fold cross
validation [
It can happen, that the input matrix X contains an empty line or column
with no values. For those objects (rows) or items (columns) we will not update
the parameters W and H (it follows from the algorithm of SGD MF). In such
cases, estimated missing values could be the global average of non-missing values.
More advanced and sophisticated methods that can improve the estimation in
such cases are listed in [
To illustrate our approach we present a small toy example. Our purpose is to cluster students into groups with respect to their success in solving the tasks. The key problem is that not every student have solved all of the tasks. We will proceed as follows. We predict the success of students in tasks that they have not solved yet (empty values in the input table). After the process of conceptual scaling is completed, we find formal concepts.
The table in the left side of the figure 1 contains five students who have performed several tasks. The total marks that can be scored are 9; 3 marks for each task. Table values represent students’ marks for tasks. The matrix represents a relation between objects and items (which are students and tasks in our case).
Figure 1 shows an example of how we can factorize the students and tasks. After the training phase with K = 2 latent factors (F1 and F2), we get the student-factor matrix W and the factor-task matrix H. Suppose we would like to predict Tom’s (3rd row) performance for the task 2 (2nd column). The prediction is performed using equation 2
Since the predicted value should be included in the input matrix, we round this value to one of the values 1, 2 and 3. We have predicted Tom will achieve average results in task 2. Similarly, we can predict the performance of other
T1 T2 T3 Katie 3 Dean 2 Tom 2 Sam Adam 2 students in tasks which they have not done yet. The full matrix is depicted in the left side of the figure 2.
Now, we would like to cluster students according to their results in solving the
tasks. The table in the left side of the figure 2 represents many-valued context.
Since values are ordered and each value implies the weaker one, we use the ordinal
scale in the right side of the figure 2. Performing a task at the highest level implies
performing the task at the average level, too. The table in the figure 3 is the
result of the conceptual scaling process. For details on many-valued contexts and
conceptual scaling we refer to [
T1 T2 T3 Katie 3 3 2 Dean 2 2 1 Tom 2 2 2 Sam 3 2 2 Adam 2 3 2
The obtained concept lattice contains 6 concepts (clusters) and is depicted in the figure 3. A labeling is simplified by putting down each object and attribute only once. The extent of each concept is formed by collecting all objects which can be reached by descending line paths from the concept. The intent of each concept consists of all attributes located along ascending line paths.
We interpret some of the clusters, here: Each student solved the task 1 and task 2 at least at average level (the top element of the lattice). All students except for Dean achieved at least average results in solving all tasks. Nobody performed good results in every task (the bottom element of the lattice). 5
Experiments were conducted on computing cluster with 7 computing nodes, each of which has 16 cores, running Red Hat Linux. Katie × × × × × × × × Dean × × × × × Tom × × × × × × Sam × × × × × × × Adam × × × × × × × Dean ✉ T10.0, T10.5
T20.0, T20.5, T30.0
Tom ✉T30.5 Sam ✉T11.0
Adam ✉T21.0
✉T31.0 For these experiments, we consider a complete database to act as a reference database, and we randomly introduce missing values with the following different rates : 10%, 20% and 30%. Benchmark datasets used for this experiments are from the UCI Machine Learning Repository5. Characteristics of these datasets are depicted in the table 1.
The data conversion into FCA format was done as follows. Categorical (manyvalued) attributes were converted by creating a formal context attribute for each of the values. Attributes with integer or real types were scaled to create context attributes with ranges of values. We implemented matrix factorization model in Java described in the section 3.2 on our own. We have used 3-fold cross-validation for testing the proposed model: In each of the 3 iterations, one fold was used for testing. The remaining two folds were used for tuning hyper-parameters of the model. Hyper-parameters (number
of factors, number of iterations, learn rate and regularization term) were tuned
using grid search [
Missing values (%) Factors Iterations Learn rate Reg. term Concept lattices from complete data sets were computed, the number of concepts is shown in the table 3.
We propose to use two measures for evaluating the performance of the proposed approach for the missing values completion with respect to mined concepts. Both are well-known in the information retrieval (IR) community. The first one indicates how many concepts of the initial context occur in the set of concepts of the estimated context. The second one determines how many concepts of the estimated context are in the set of concepts of the initial context.
Let (X, Y, I) be the initial formal context and (X, Z, J ) be the estimated formal context. Let O be the set of formal concepts of the initial context and E be the set of formal concepts of the estimated one (O = B(X, Y, I) and E = B(X, Z, J )). We propose to use the following two measures: |O ∩ E|
|E| precision = and recall = |O ∩ E| |O| .
Precision is the fraction of concepts of the estimated context that are in the set of concepts of the initial context. Recall is the fraction of concepts of the initial context that are in the set of concepts of the estimated context. The higher the precision, the more concepts of the estimated context are in the set of concepts of the initial context. The higher the recall, the more concepts of the initial context are in the set of concepts of the estimated context.
Two formal concepts are equal when any formal object in the extent of one is in the extent of the other and vice versa, the same for formal attributes. In this case, precision and recall are computed. From the extent-ional point of view: two concepts are equal when they have the same extent. Analogously, from the point of view of intent, two concepts are equal when they have the same intent. In these cases, we calculate precisione, recalle and precisioni, recalli, respectively.
The results of our experiments are shown in the table 4 and 5.
It is noteworthy that there is a huge difference between precisione and precisioni. We assume that the gap between precisione and precisioni is caused by the fact that the number of objects is greater than the number of attributes.
Moreover, the precision and recall are quite small. The reason is how we have measured the equality of the sets: the sets are not equal if they differ even only in one element. Nevertheless, the proposed measures are useful for experimental comparisons of various techniques used in the pre-processing step. We will focus on finding other measures. We suppose that if we modify measures to use the similarity (of extents, intents and concepts) better results could be achieved. 6
Conclusion and future research directions In this paper we have introduced framework for mining concepts from incomplete datasets. The proposed framework uses stochastic gradient descent matrix factorization (SGD MF) in the pre-processing step and after completing the missing values a formal concept analysis (FCA) is deployed. Using SGD MF we are able to quite precisely predict values from a sparse data matrix without having any background knowledge about the data. Two measures (precision and recall) have been used for evaluating the presented framework.
The experiments on three datasets (with 10, 20 and 30 percent of missing values) showed that the percentage of missing values does not influence the prediction rate, and, that there is a large difference in the precision and recall measures when computed on the extents and the intents of the resulting concepts, respectively.
Our further research will focus on modifying the (precision and recall) measures with using the similarity of extents, intents and concepts instead of their equality. The generation of all concepts from the huge incidence matrix is time consuming and the number of concepts is very large. Using our matrix factorization model we transform input matrix into more smaller latent factor matrices W and H. These matrices describe objects and items according to latent factors. We want to explore these matrices and to use them for reducing the number of concepts.
Even if there are some remaining issues to investigate, experimental results show that the proposed approach is promising and worth of further research. Acknowledgements: This work was supported by the grants VEGA 1/0832/12 and VVGS-PF-2012-22 at the Pavol Jozef Sˇaf´arik University in Koˇsice, Slovakia.