We propose a new approach for Collaborative ltering which is based on Boolean Matrix Factorisation (BMF) and Formal Concept Analysis. In a series of experiments on real data (Movielens dataset) we compare the approach with the SVD- and NMF-based algorithms in terms of Mean Average Error (MAE). One of the experimental consequences is that it is enough to have a binary-scaled rating data to obtain almost the same quality in terms of MAE by BMF than for the SVD-based algorithm in case of non-scaled data.
Recently Recommender Systems is one of the most popular subareas of Machine Learning. In fact, the recommender algorithms based on matrix factorisation techniques (MF) has become industry standard.
Among the most frequently used types of Matrix Factorisation we de nitely
should mention Singular Value Decomposition (SVD) [
The aim of this paper is to compare recommendation quality of some of the aforementioned techniques on real datasets and try to investigate the methods' interrelationship. It is especially interesting to conduct experiments on comparison of recommendations quality in case of an input matrix with numeric values and in case of a Boolean matrix in terms of Precision and Recall as well as MAE. Moreover, one of the useful properties of matrix factorisation is its ability to keep reliable recommendation quality even in case of dropping some insu cient factors. For BMF this issue is experimentally investigated in section 4.
The novelty of the paper is de ned by the fact that it is a rst time when
BMF based on Formal Concept Analysis [
The practical signi cance of the paper is determined by demands of the recommender systems' industry, that is to gain reliable quality in terms of Mean Average Error (MAE), Precision and Recall as well as time performance of the investigated method.
The rest of the paper consists of ve sections. The second section is an introductory review of the existing MF-based recommender approaches. In the third section we describe our recommender algorithm which is based on Boolean matrix factorisation using closed sets of users and items (that is FCA). Section 4 contains methodology of our experiments and results of experimental comparison of di erent MF-based recommender algorithms by means of cross-validation in terms of MAE, Precision and Recall. The last section concludes the paper. 2
In this section we brie y describe di erent approaches to the decomposition of both real-valued and Boolean matrices. Among the methods of the SVD group we describe only SVD. We also discuss nonnegative matrix factorization (NMF) and Boolean matrix factorization (BMF). 2.1
Singular Value Decomposition (SVD) is a decomposition of a rectangular matrix A 2 Rm n(m > n) into the product of three matrices
A = U 0
V T ;
(1)
where U 2 Rm m and V 2 Rn n are orthogonal matrices, and 2 Rn n is
a diagonal matrix such that = diag( 1; : : : ; n) and 1 2 : : : n 0.
The columns of the matrix U and V are called singular vectors, and the numbers
i are singular values [
In the context of recommendation systems rows of U and V can be interpreted as vectors of the user's and items's loyalty (attitude) to a certain topic (factor), and the corresponding singular values as the importance of the topic among the others. The main disadvantage is in the fact that the matrix may contain both positive and negative numbers; the last ones are di cult to interpret.
The advantage of SVD for recommendation systems is that this method allows to obtain the vector of its loyalty to certain topics for a new user without SVD decomposition of the whole matrix.
The evaluation of computational complexity of SVD according to [
Consider as an example the following table of movie ratings: A = BBBB 00 00 00 45 44 05 03 CCCC : U = BBBB 00::2597
It can be seen that the greatest weight have the rst three singular values, which is con rmed by the calculations: Non-negative Matrix Factorization (NMF) is a decomposition of non-negative matrix V 2 Rn m for a given number k into the product of two non-negative matrices W 2 Rn k and H 2 Rk m such that
V
W H: (2)
NMF is widely used in such areas as nding the basis vectors for images,
discovering molecular structures, etc. [
Consider the following matrix of ratings:
Its decomposition into the product of two non-negative matrices for k = 3 can be, for example, like this: Basic FCA de nitions. Formal Concept Analysis (FCA) is a branch of applied mathematics and it studies (formal) concepts and their hierarchy. The adjective \formal" indicates a strict mathematical de nition of a pair of sets, called, the extent and intent. This formalisation is possible because the use of the algebraic lattice theory.
Definition 1. Formal context K is a triple (G; M; I), where G is the set of objects, M is the set of attributes , I G M is a binary relation.
The binary relation I is interpreted as follows: for g 2 G, m 2 M we write gIm if the object g has the attribute m.
For a formal context K = (G; M; I) and any A G and B M a pair of mappings is de ned:
A0 = fm 2 M j gIm for all g 2 Ag;
B0 = fg 2 G j gIm for all m 2 Bg;
these mappings de ne Galois connection between partially ordered sets (2G; )
and (2M ; ) on disjunctive union of G and M . The set A is called closed set, if
A00 = A [
Definition 2. A formal concept of the formal context K = (G; M; I) is a pair (A; B), where A G, B M , A0 = B and B0 = A. Set A is called the extent, and B is the intent of the formal concept (A; B).
It is evident that extent and intent of any formal concept are closed sets.
The set of formal concepts of a context K is denoted by B(G; M; I). Description of FCA-based BMF Boolean matrix factorization (BMF) is a decomposition of the original matrix I 2 f0; 1gn m, where Iij 2 f0; 1g; into a Boolean matrix product P Q of binary matrices P 2 f0; 1gn k and Q 2 f0; 1gk m for the smallest possible number of k: We de ne boolean matrix product as follows: (P
Q)ij = k _ Pil Qlj ; l=1 where W denotes disjunction, and conjunction.
Matrix I can be considered as a matrix of binary relations between set X objects (users), and the set Y attributes (items that users have evaluated). We assume that xIy i user x estimated object y. The triple (X; Y; I) is clearly composes a formal context.
Consider the set F B(X; Y; I), a subset of all formal concepts of context
(X; Y; I), and introduce the matrices PF and QF :
(PF )il =
1; i 2 Al;
0; i 2= Al;
(QF )lj =
1; j 2 Bl;
0; j 2= Bl:
We can consider the decomposition of the matrix I into binary matrix product
PF and QF as described above. The following theorems are proved in [
F B(X; Y; I), such that I = PF QF :
Theorem 2. (Optimality of formal concepts as factors). Let I = P Q for n k
and k m binary matrices P and Q. Then there exists a F B(X; Y; I)
of formal concepts of I such that jF j k and for the n jF j and jF j m
binary matrices PF and QF we have I = PF QF :
There are several algorithms for nding PF and QF by calculating formal
concepts based on these theorems [
The algorithm we use (Algoritm 2 from [
Transform the matrix of ratings described above, to a boolean matrix, as follows: 0 4 4 5 0 0 0 0 1 0 1 1 1 0 0 0 0 1 B 5 5 3 4 3 0 0 C B 1 1 1 1 1 0 0 C BB 0 0 0 4 4 0 0 CC BB 0 0 0 5 4 5 3 CC ) BBBB 00 00 00 11 11 10 10 CCCC = I: The decomposition of the matrix I into the Boolean product of I = AF the following: BF is 0 1 1 1 0 0 0 0 1 B 1 1 1 1 1 0 0 C BBBB 00 00 00 11 11 01 01 CCCC = BBBB 00 11 01 CCCC Once the matrix of rates is factorized we need to learn how to compute recommendations for users and to evaluate whether a particular method handles well with this task.
For factorized matrices the already well-known algorithm based on the similarity of users can be applied, where for nding K nearest neighbors we use not the original matrix of ratings A 2 Rm n, but the matrix U 2 Rm f , where m is a number of users, and f is a number of factors. After selection of K users, which are the most similar to a given user, based on the factors that are peculiar to them, it is possible, based on collaborative ltering formulas to calculate the projected rates for a given user.
After formation of the recommendations the performance of the recommendation system can be estimated by measures such as Mean Absolute Error (MAE), Precision and Recall.
kNN-based algorithm Collaborative recommender systems try to predict the utility of items for a particular user based on the items previously rated by other users.
Denote u(c; s) the utility of item s for user c. u(c; s) is estimated based on the utilities u(ci; s) assigned to item s by those users ci 2 C who are \similar" to user c. For example, in a movie recommendation application, in order to recommend movies to user c, the collaborative recommender system nds the users that have similar tastes in movies with c (rate the same movies similarly). Then, only the movies that are most liked by those similar users would be recommended.
Memory-based recommendation system, which are based on the previous history of the ratings, are one of the key classes of collaborative recommendation systems.
Memory-based algorithms make rating predictions based on the entire
collection of previously rated items by the users. That is, the value of the unknown
rating rc;s for user c and item s is usually computed as an aggregate of the
ratings of some other (usually, the K most similar) users for the same item s:
rc;s = aggrc02Cbrc;s;
where Cb denotes the set of K users that are the most similar to user c , who
have rated item s. For example, function aggr may has the following form [
rc0;s; c02Cb where k serves as a normalizing factor and selected as k = 1= P sim(c; c0). c02Cb
The similarity measure between users c and c0, sim(c; c0), is essentially a distance measure and is used as a weight, i.e., the more similar users c and c0 are, the more weight rating rc0;s will carry in the prediction of rc;s:
The similarity between two users is based on their ratings of items that both users have rated. The two most popular approaches are correlation and cosine-based. One common strategy is to calculate all user similarities sim(x; y) in advance and recalculate them only once in a while (since the network of peers usually does not change dramatically in a short time). Then, whenever the user asks for a recommendation, the ratings can be calculated on demand using precomputed similarities.
To apply this approach in case of FCA-based BMF recommender algorithm we simply consider as an input the user-factor matrices obtained after factorisation of the initial data. 3.2
In order to move from a matrix of ratings to a Boolean matrix, and use the results of Boolean matrix factorization, scaling is required. It is well known that scaling is a matter of expert interpretation of original data. In this paper, we use several variants of scaling and compare the results in terms of MAE. 1. Iij = 1 if Rij > 0, else Iij = 0 (user i rates item j). 2. Iij = 1 if Rij > 1; else Iij = 0: 3. Iij = 1 if Rij > 2; else Iij = 0. 4. Iij = 1 if Rij > 3, else Iij = 0: 4
To test our hypotheses and study the behavior of recommendations based on the factorization of a ratings matrix by di erent methods we used MovieLens data. We used the part of data, containing 100,000 ratings, while considered only users who have given over 20 ratings.
User ratings are split into two sets, a training set consisting of 80 000 ratings, and test set consisting of 20 000 ratings. Original data matrix is 943 1682, where the number of rows is the number of users and the number of columns is the number of rated movies (each lm has at least one vote). 4.1
The number of factors that cover p% of evaluations in an input data for SVD and BMF The main purpose of matrix factorization is a reduction of matrices dimensionality. Therefore we examine how the number of factors varies depending on the method of factorization, and depending on p % of the data that is covered by factorization. For BMF the coverage of a matrix is calculated as the ratio of the number of ratings covered by Boolean factorization to the total number of ratings.
MAE-based recommender quality comparison of SVD and BMF for various levels of evaluations coverage The main purpose of matrix factorisation is a reduction of matrices dimensionality. As a result some part of the original data remains uncovered, so it was interesting to explore how the quality of recommendations changes based on different factorisations, depending on the proportion of the data covered by factors.
Two methods of matrix factorisation were considered: BMF and SVD. The fraction of data covered by factors for SVD was calculated as and for BMF as
PK i2 p% = iP=1 i2
100%; p% = jcovered ratingsj 100%:
jall ratingsj
Fig. 1 shows that M AESV D60, calculated for the model based on 60% of factors, is not very di erent from M AESV D80, calculated for the model built for 80% factors. At the same time, for the recommendations based on a Boolean factorization covering 60% and 80% of the data respectively, it is clear that increasing the number of factors improves MAE, as shown in Fig. 2.
Table 3 shows that the MAE for recommendations built on a Boolean factorisation covering 80 % of the data for the number of neighbors less than 50 is better than the MAE for recommendations built on SVD factorization. It is also easy to see that M AESV D80 and M AEBMF 80 are di erent from M AEall in no more than 1 7%.
Comparison of kNN-based approach and BMF by Precision and Recall Besides comparison of algorithms using MAE other evaluation metrics can also be exploited, for example
Recall = jobjects in recommendation \ objects in testj ; jobjects in testj P recision = jobjects in recommendation \ objects in testj
jobjects in recommendationj and
It is widely spread belief that the larger Recall, Precision and F1 are, the better is recommendation algorithm.
Figures 3, 4 and 5 show the dependence of relevant evaluation metrics on the percentage of the data covered by BMF-decomposition, and the number of nearest neighbors. The number of objects to recommend was chosen to be 20. The gures show that the recommendation based on the Boolean decomposition, is worse than recommendations built on the full matrix of ratings.
Scaling in uence on the recommendations quality for BMF in terms of MAE Another thing that was interesting to examine was the impact of scaling described in 3.2 on the quality of recommendations. Four options of scaling were considered: 1. I0;ij = 1 if Aij > 0, else Iij = 0 (user rates an item). 2. I1;ij = 1 if Aij > 1; else Iij = 0: 3. I2;ij = 1 if Aij > 2; else Iij = 0. 4. I3;ij = 1 if Aij > 3, else Iij = 0:
For each of the boolean matrices we calculate its Boolean factorisation, covering 60 % and 80 % of the data. Then recommendations are calculated just like in 4.2. It can be seen that for both types of data coverage M AE1 is almost the same as M AE0, and M AE2;3 is better than M AE0.
ltering on MAE for BMF kNN-based Besides the ability to search for K nearest neighbors not in the full matrix of ratings A 2 Rn m, but in the matrix U 2 Rm f , where m is a number of users, and f is a number of factors, Boolean matrix factorization can be used to data ltering. Because the algorithm returns as an output not only matrices usersfactors and factors-objects, but also the ratings that were not used for factoring, we can try to search for users, similar to the user, on the matrix consisting only of ratings used for the factorization.
Just as before to nd the nearest neighbors cosine measure is used, and the predicted ratings are calculated as the weighted sum of the ratings of nearest users. Figure 9 shows that the smaller the data we use for ltering the bigger is MAE. Figure 10 shows that the recommendations built on user-factor matrix, are better then recommendations, constructed on matrix of ratings ltered with boolean factorization.
In the paper we considered main methods of Matrix Factorisation which are suitable for Recommender Systems. Some of these methods were compared on real datasets. We investigated BMF behaviour as part of recommender algorithm. We also conducted several experiments on recommender quality comparison with numeric matrices, user-factor and factor-item matrices in terms of Recall, Precision and MAE. We showed that MAE of our BMF-based approach is not greater than MAE of SVD-based approach for the same number of factors on the real data. For methods that require the number of factors as an initial parameter in the user or item pro le (e.g., NMF), we proposed the way of nding this number with FCA-based BMF. We also have investigated how data ltering, namely scaling, in uences on recommendations' quality.
As a further research direction we would like to investigate the proposed
approaches in case of graded and triadic data [