We propose a new algorithm for recommender systems with numeric ratings which is based on Pattern Structures (RAPS). As the input the algorithm takes rating matrix, e.g., such that it contains movies rated by users. For a target user, the algorithm returns a rated list of items (movies) based on its previous ratings and ratings of other users. We compare the results of the proposed algorithm in terms of precision and recall measures with Slope One, one of the state-of-theart item-based algorithms, on Movie Lens dataset and RAPS demonstrates the best or comparable quality.
Formal Concept Analysis (FCA)[
The task of recommending items to users according to their preferences expressed
by ratings of previously used items became extremely popular during the last decade
partially because of famous NetFlix 1M$ competition [
The paper is organised as follows. In Section 2, basic FCA definitions and interval pattern structures are introduced. Section 3 describes SlopeOne [13] and RAPS with examples. In Section 4, we provide the results of experiments with time performance and precision-recall evaluation for MovieLens dataset. Section 5 concludes the paper. 2
Formal Concept Analysis. First, we recall several basic notions of Formal Concept
Analysis (FCA) [
B0 = fg 2 G j gIm for all m 2 Bg:
The pair (A; B), where A G, B M, A0 = B, and B0 = A is called a (formal) concept (of the context K) with extent A and intent B (in this case we have also A00 = A and B00 = B).
The concepts, ordered by (A1; B1) (A2; B2) () A1 A2 form a complete lattice, called the concept lattice B(G; M; I).
Pattern Structures. Let G be a set of objects and D be a set of all possible object descriptions. Let u be a similarity operator. It helps to work with objects that have non-binary attributes like in traditional FCA setting, but those that have complex descriptions like intervals or graphs. Then (D; u) is a meet-semi-lattice of object descriptions. Mapping d : G ! D assigns an object g the description d 2 (D; u).
A triple (G; (D; u); d ) is a pattern structure. Two operators ( ) define Galois connection between (2G; ) and (D; u):
A = l d (g) for A
G g2A d = fg 2 Gjd v d (g)g for d 2 (D; u); where
d v d (g) () d u d (g) = d:
For a set of objects A operator 2 returns the common description (pattern) of all objects from A. For a description d operator 3 returns the set of all objects that contain d.
A pair (A; d) such that A G and d 2 (D; u) is called a pattern concept of the pattern structure (G; (D; u); d ) iff A = d and d = A. In this case A is called a pattern extent and d is called a pattern intent of a pattern concept (A; d). Pattern concepts are partially ordered by (A1; d1) (A2; d2) () A1 A2( () d2 v d1). The set of all pattern concepts forms a complete lattice called a pattern concept lattice. Intervals as patterns. It is obvious that similarity operator on intervals should fulfill the following condition: two intervals should belong to an interval that contains them. Let this new interval be minimal one that contains two original intervals. Let [a1; b1] and [a2; b2] be two intervals such that a1; b1; a2; b2 2 R, a1 b1 and a2 b2, then their similarity is defined as follows:
Therefore
[a1; b1] u [a2; b2] = [min(a1; a2); max(b1; b2)]: [a1; b1] v [a2; b2] () [a1; b1] u [a2; b2] = [a1; b1] ()
min(a1; a2); max(b1; b2) = [a1; b1] () a1 a2 and b1 b2 () [a1; b1]
Interval vectors as patterns. Let us call p-adic vectors of intervals as interval vectors. In this case for two interval vectors of the same dimension e = h[ai; bi]ii2[1;p] and f = h[ci; di]ii2[1;p] we define similarity operation via the intersection of the corresponding components of interval vectors, i.e.:
e u f = h[ai; bi]ii2[1;p] u h[ci; di]ii2[1;p] () e u f = h[ai; bi] u [ci; di]ii2[1;p]
e v f () h[ai; bi]ii2[1;p] v h[ci; di]ii2[1;p] () [ai; bi] v [ci; di] for all i 2 [1; p]. 3 3.1
Slope One Slope One is one of the common approaches to recommedations based on collaborative filtering. However, it demonstrates comparable quality with more complex and resource demanding algorithms [13]. As it was shown in [14], SlopeOne has the highest recall on MovieLens and Netflix datasets and acceptable level of precision: “Overall, the algorithms that present the best results with these metrics are SVD techniques, tendenciesbased and slope one (although its precision is not outstanding).”
We use this algorithm for comparison purposes.
Slope One deals with rating matrices as input data. In what follows the data contains movies ratings by different users. That is M = fm1; m2; : : : ; mng is a set of movies, U = fu1; u2; : : : ; ukg is a set of users. The rating matrix can be represented by manyvalued formal context (U; M; R; I), where R = f1; 2; 3; 4; 5; g is a set of possible ratings and a triple (u; m; r) 2 I means that the user u marked by the rating r the movie m. Whenever it is suitable we also use ri j notation for rating of movie m j by user ui.
In case a user u has not rated a movie m, we use m(u) = r = , i.e. missing rating.
Let us describe the algorithm step by step. 1. The algorithm takes a many valued context of all users’ ratings, the target user ut for which it generates recommendations. It also requires le f t_border and right_border for acceptable level of ratings, i.e. if one wants to receive all movies with ratings between 4 and 5, then left and right borders should be 4 and 5 respectively. The last pair of parameters: one needs to set up minimal and maximal scores (min_border and max_border) that are acceptable for our data. It means that if the algorithm predicts rating 6.54 as a score and maximal score is bounded by 5, then 6.54 should be treated as 5. 2. The algorithm finds the set of all movies evaluated by the target user S(ut ). 3. For every non-evaluated movie m j 2 M n S(ut ) by ut execute step 4), and by so doing calculate the predicted rating for the movie m j. After that go to step 5). 4. For every evaluated movie mi 2 S(ut ) by ut calculate S j;i(U n fut g), the set of users that watched and evaluated movies mi and m j. In case S j;i(U n fut g) is non-empty, that is jS j;i(U n fut g)j > 0, calculate the deviation: dev j;i = uk2S j;iå(Unfut g) jS j;rik(;Uj nfrku;tig)j and add i to R j.
After all current deviations found, calculate the predicted rating: P(ut ) j = jR1jj i2R j å (dev j;i + rt;i), where R j = fijmi 2 S(ut ); i 6= j; jS j;i(U n fut g)j > 0g. In case R j is empty, the algorithm cannot make a prediction. 5. By this step Slope One found all predicted ratings P(ut ) for movies from M n S(ut ).
The algorithm recommends all movies with predicted ratings in the preferred range le f t_border P(ut ) j right_border, taking into account minimal and maximal allowed values.
If one needs top-N ranked items, she can sort the predicted scores from the resulting set in decreasing order and select first N corresponding movies.
Example 1.
Consider execution of Slope One on the dataset from Table 1. 1. Let le f t_border = 4, right_border = 5, min_border = 1, and max_border = 5. 2. We find S(u3) = fm2; m3g, the set of evaluated movies by the target user. 3. M n S(u3) = fm1g 4. S1;2(U n fu3g) = fu1; u2g dev1;2 = (r1;1 (rj1f;2u)1+;u(2rg2;j1) r2;2) = ((5 3) + (3 4))=2 = 0:5 S1;3(U n fu3g) = fu1g dev1;3 = (r1;1 r1;3)=(jfu1gj) = (5 2)=1 = 3 R1 = f2; 3g
P(u3)1 = 1=jR jj(dev1;2 + r3;2 + dev1;3 + r3;3) = 1=2(0:5 + 2 + 3 + 5) = 5:25 5. Taking into account the maximal rating boundary, the algorithm predicts 5 for movie m1, and therefore recommends user u3 to watch it. 1. It takes the context (U; M; R; I) with all ratings, and a target user ut . It also requires le f t_border and right_border for preferred ratings, i.e. if one wants to get all movies rated in range from 4 to 5, then le f t_border = 4 and right_border = 5. 2. Define the set of movies Mt = fmt1 ; : : : ; mtq g that the target user ut liked, i.e. the ones that she evaluated in the range [le f t_border; right_border]. 3. For each movie mti 2 Mt apply eq. 3. and find the set of users that liked the movie Ati = [le f t_border; right_border]mti for 1 i q. As a result one has the set of user subsets: fAt1 ; : : : ; Atq g. 4. For each Ati ; 1 i q apply eq. 2 to find its description; in our case it is a vector of intervals dti = Ati = h[at1i ; bt1i ]; : : : ; [atni ; btni ]i for 1 i q. Note that, in case a particular user ux from Ati has not rated my, i.e. rx;y = , then the algorithm does not take it into account. 5. At the last step compute the vector r = (R1; : : : ; Rn) 2 Nn (or Rn in general case), where
R j = jfij1 i q; [atji ; btji ]
[le f t_border; right_border]gj , i.e. for each movie m j the algorithm counts how many of its descriptions [a ji ; btji ] are in t [le f t_border; right_border]. If R j > 0, then the algorithm recommends watching the movie.
Top-N movies with the highest ratings can be selected in similar way.
Let us shortly discuss the time computational complexity. Step 2 requires O(jMj) operations, steps 3, 4 and 5 perform within O(jMjjU j) each. Therefore, the algorithm time complexity is bounded by O(jMjjU j).
Example 2 Consider execution of RAPS on the tiny dataset from Table 2.
Let us find a recommendation for user u7. d1 = A1 = h[a11; b11]; [a21; b21]; [a31; b31]; [a41; b41]; [a51; b51]; [a61; b61]i =
= h[4; 5]; [3; 4]; [1; 4]; [3; 5]; [4; 5]; [3; 4]i
[a61; b61] = [min(r1;6; r2;6; r3;6; r5;6); max(r1;6; r2;6; r3;6; r5;6)] =
= [min(3; 3; 4; ); max(3; 3; 4; )] = [min(3; 3; 4); max(3; 3; 4)] = [3; 4]: The rest intervals are found in similar way.
d2 = A2 = h[3; 4]; [4; 4]; [1; 5]; [5; 5]; [4; 4]; [3; 3]i 5. Taking into account the left and right bounds, the algorithm recommends movies m1 and m5 from d1 and m2, m4 and m5 from d2. Therefore R = (1; 1; 0; 1; 2; 0), i.e. without already assessed movies by u7, we recommend her to watch m4 and m5. 4 4.1
Data
For our experimentation we have used freely available data from MovieLens website1. The data collection was gathered within The GroupLens Research Project of Minnesota University in 1997–1998. The data contains 100000 ratings for 1682 movies by 943 different users. Each user rated no less than 20 movies. That is we have 100000 tuples in the form: user id | item id | rating | timestamp.
Each tuple shows user id, movie id, the rating she gave to the movie and time when
it happened.
1 http://grouplens.org/datasets/movielens/
Firstly, for quality assessment of Slope One and RAPS we used precision and recall
measures. Note that we cannot use Mean Absolute Error (MAE) directly, since RAPS
actually assume a whole interval like [
There is a more general testing scheme based on bimodal cross-validation from [15], which seems to us the most natural and realistic: users from the test set keep only x% of their rated movies, and the remaining y% of their ratings are hidden. Thus, by considering each test user in this way, we model a real user whose ratings to other movies are not yet clear, but at the same time we have all ratings’ information about the training set of users. In other words, we hide only rectangle of size x% of test users by y% of hidden items. One can vary x and y during the investigation of the behaviour of methods under comparison, where the size of top-N recommended list is set to be equal to y%. The part of hidden items can be selected randomly or by timestamp (preferably for realistic scenario). Note that there is no a gold standard approach to test recommender systems, however, there are validated sophisticated schemes [16]. The main reason is the following: with only off-line data in hands we cannot verify whether the user will like a not yet seen movie irrespective of assumption that she has seen our recommendation. However, for real systems there is a remedy such as A/B testing, which is applicable only in online setting [17].
The adjusted precision and recall are defined below: precision = jfrelevant moviesg \ fretrieved moviesg \ ftest moviesgj jfretrieved moviesg \ ftest moviesgj recall = jfrelevant moviesg \ fretrieved moviesg \ ftest moviesgj jfrelevant moviesg \ ftest moviesgj (4) (5)
These measures allow us to avoid the uncertainty since we do not know how actually a particular user would assess a recommended movie. However, in real recommender system, we would rather ask a user whether the recommendation was relevant, but in our off-line quality assessment scheme we cannot do that. In other words, we assume that for a test user at the moment of assessment there are no movies except the training and test ones.
Another issue, which is often omitted in papers on recommender systems, is how to avoid uncertainty when denominators in Precision and Recall are equal to zero (not necessarily simultaneously).
To define the mesaures precisely based on the peculiarities of recommendation task and common sense, we use two types of the definitions for cases when the sets of retrieved and relevant movies for particular user and recommender are empty.
Precision and Recall of the first type are defined as follows: – If the sets of relevant movies and retrieved ones are empty, then Precision = 0 and
Recall = 1. – If the set of relevant movies is empty, but the set of retrieved ones is not, then
Precision = 0 and Recall = 1. – If we have the non-empty set of relevant movies, but the set of retrieved movies is empty, then Precision = 0 and Recall = 0.
Precision of the second type is less tough, but Recall remains the same: – If the sets of relevant movies and retrieved ones are empty, then Precision = 1 (since we should not recommend any movie and the recommender has not recommended anything). – If the set of relevant movies is empty, but the set of retrieved ones is not, then
Precision = 0. – If we have the non-empty set of relevant movies, but the set of retrieved movies is empty, then Precision = 1 (since the recommender has not recommended anything, its output does not contain any non-relevant movie). 4.3
Results
We have performed three series of tests:
1. A movie is worth to watch if its predicted mark is 5 (i.e. it is [
All the tests are performed in OS X 10.9.3 with Intel Core i7 2.3 GHz and 8 Gb of memory. The algorithm were implemented in MATLAB – R2013a. The results are presented in Table 3. Note that the reported Precision and Recall are of the first type.
The criteria are average execution time in seconds, average precision and recall.
From the table one can see RAPS is drastically better than Slope One by the whole set of
criteria in [
However, since the compared approaches are different from the output point view (RAPS provides the user with an interval of possible ratings but SlopeOne does it by a single real number), we perform thorough comparison varying the lower bound of acceptable recommendations and using both types of the adjusted precision and recall measures.
From Fig. 1 one can conclude that RAPS dominates SlopeOne in most cases by
Recall. As for Precision, even though for [
From Fig. 2 one can see that SlopeOne is significantly better in terms of
precision. Only on the interval [
4
SlopeOne there are more cases when fretrieved moviesg = 0/ irrespective of the size of frelevant moviesg. Remember that in such cases Precision of the second type is equal to 1. In other words SlopeOne is really more precise (or even concise): in such cases it just does not recommend anything. However, it can be hardly judged in movie recommendation domain that a recommender is good when it does not recommend.
We can conclude that the proposed recommender technique based on pattern structures has its right to be used. Since the Slope One algorithm was exploited in real recommender systems [13], we can suggest our technique for usage as well. 5
In this paper we proposed the technique for movie recommendation based on Pattern Structures (RAPS). Even though this algorithm is oriented to movie recommendations, it can be easily used in other recommender domains where users evaluate items.
The performed experiments (RAPS vs Slope One) showed that recommender system based on Pattern Structures demonstrates acceptable precision, better recall in most cases and reasonable execution time.
Of course, in future RAPS should be compared with other recommender techniques to make a final conclusion about its applicability. An interplay between interval-based recommendations and regression-like ones deserves a more detailed treatment as well.
The further work can be continued in the following directions: 1. Further modification and adjustment of RAPS. 2. Development of the second variant of Pattern Structures based recommender. There is a conjecture that for the second derivation operation (operator Galois from eq.3) being applied to more than one movie with high marks we may obtain relevant predictions as well. 3. Comparison with existing popular techniques, e.g. SVD and SVD++. Acknowledgments We would like to thank Mehdi Kaytoue, Sergei Kuznetsov and Sergei Nikolenko for their comments, remarks and explicit and implicit help during the paper preparations. The first author has been supported by the Russian Foundation for Basic Research grants no. 13-07-00504 and 14-01-93960 and made a contribution within the project “Data mining based on applied ontologies and lattices of closed descriptions” supported by the Basic Research Program of the National Research University Higher School of Economics. We also deeply thank the reviewers for their comments and remarks that helped. 13. Lemire, D., Maclachlan, A.: Slope one predictors for online rating-based collaborative filtering. In: Proceedings of the 2005 SIAM International Conference on Data Mining. 471–475 14. Cacheda, F., Carneiro, V., Fernández, D., Formoso, V.: Comparison of collaborative filtering algorithms: Limitations of current techniques and proposals for scalable, high-performance recommender systems. ACM Trans. Web 5(1) (February 2011) 2:1–2:33 15. Ignatov, D.I., Poelmans, J., Dedene, G., Viaene, S.: A new cross-validation technique to evaluate quality of recommender systems. In Kundu, M.K., Mitra, S., Mazumdar, D., Pal, S.K., eds.: Perception and Machine Intelligence - First Indo-Japan Conference, PerMIn 2012, Kolkata, India, January 12-13, 2012. Proceedings. Volume 7143 of Lecture Notes in Computer Science., Springer (2012) 195–202 16. Cremonesi, P., Koren, Y., Turrin, R.: Performance of recommender algorithms on top-n recommendation tasks. In: Proceedings of the Fourth ACM Conference on Recommender Systems. RecSys ’10, New York, NY, USA, ACM (2010) 39–46 17. Radlinski, F., Hofmann, K.: Practical online retrieval evaluation. In Serdyukov, P., Braslavski, P., Kuznetsov, S.O., Kamps, J., Rüger, S.M., Agichtein, E., Segalovich, I., Yilmaz, E., eds.: Advances in Information Retrieval - 35th European Conference on IR Research, ECIR 2013, Moscow, Russia, March 24-27, 2013. Proceedings. Volume 7814 of Lecture Notes in Computer Science., Springer (2013) 878–881