Digital editions of newspapers cause information over ow and users have problems choosing what they want to read. Systems which recommend news articles are suitable to solve such problems. Nevertheless, they face challenges unknown to the systems recommending books or movies such as a frequency of producing the new content. CLEF NewsREEL challenge enables to compare and evaluate news recommendation systems in an online and o ine task focused on recommending articles to real users and tuning of algorithms respectively. This paper deals with an approach based on association rules acting as a classi er. In our approach we experimented with settings that allows to reduce the amount of rules used for the classi cation and increase the performance that is crucial for real recommendations. We evaluated our approach in both tasks of the CLEF NewsREEL 2017 challenge.
The enormous number of available news causes information over ow resulting in users having problems choosing what they want to read. News recommendation systems should solve this problem and o er them an article or a collection of articles which they could nd worth a read. Systems which recommend news articles face challenges unknown to the systems recommending books or movies. Typical example of such a challenge is coping with the frequency with which the new content is produced. While a movie or a book is released once a few months (and can be read or watched multiple times), the news are produced every minute (and read once).
The CLEF NewsREEL 1 challenge enables to compare and evaluate news
recommendation systems both o ine and online. This challenge is split into
two tasks: NewsREEL Live[
tra c to a recommender system of a participant in the challenge. NewsREEL
Replay [
Over the years, many di erent approaches to news recommendation have
been developed. Frequently used algorithms include recommending the most read
articles or recommending the most recent articles, including their modi cations
e.g. most read articles in their respective categories [
Recommending articles using association rules was already tried by Kliegr et
al [
This paper is structured as follows: our approach based on association rules is described in Section 2. Results of its o ine and online evaluation are presented in Section 3, while Section 4 concludes the paper. 2 2.1
A news recommender system implementing the provided interface (Open Recommendation Platform - ORP2) interface has to handle four types of messages: recommendation requests, item updates, event noti cations and error messages.
The recommendation request indicates that the participated recommender system should return recommendations from the same domain as mentioned in the request. The recommendations are in the form of a list of identi ers and only identi ers of valid articles should be returned. Item updates signal an addition of a new item or an update including in-validations of items. Error messages are used to inform the system about possible errors that could occur such as network problems or a wrong format of the provided recommendations. Event
noti cation arrives when a user visits an article (impression) or when the user clicks on a recommendation (click ).
With the exception of error messages and item updates, all of aforementioned message types contain contextual information about the reader or the article being read. Examples of such features include a user location, user income, user age, article keywords or article category. 2.2
In our approach we decided to mainly use the contextual information about the reader or the article being read. During o ine evaluation, we made several experiments to explore which features would perform best. Based on these experiments measuring in uence of attributes on the quality of recommendations, we selected twelve attributes for the online evaluation (category, keyword, income, age, geo user, geo user zip, weather, device, isp, browser, recommended id and position - see ORP documentation 3 for more details about attributes).
The reasoning behind the use of rules was following: If a certain number of user interactions with an item often include values of attributes repeating themselves, they may be interesting either for users sharing these attributes or for users reading articles sharing these attributes. In order to provide an example: if an article was read frequently during evening hours, it may be interesting to someone reading news late at night.
Listing 1.1: Examples of association rules created from interactions { browser : 40052 , geo_user_zip : 61958} => { itemId : 341743113}
supp = 0.02 , conf = 1.0 { isp : 6, category : 420949} => { itemId : 367259468}
supp = 0.01 , conf = 1.0 { browser : 16064801 , device : 504182} => { itemId : 315791779}
supp = 0.1 , conf = 0.7 {} => { itemId : 322334534}
supp = 0.01 , conf = 0.01
Each rule is composed from a left-hand side (LHS), right-hand side (RHS)
and its described by its quality measures: support and con dence. The process
of extracting of these rules (algorithms Apriori, FP-Growth, Eclat [
To prefer certain rules over other, we sort rules in the same way as in CBA according to the con dence (decreasingly), support (decreasingly) and length of the LHS of each rule (increasingly - shorter is better). Since the amount of rules returned by the standard implementation can be huge, we use the rule pruning: it removes rules that can be never used for subsequent classi cation, usually due to their redundancy, lower signi cance etc. The advantage is that the amount of rules is signi cantly lower and thus the classi er can provide recommendations much faster.
Our algorithm works as follows: an article with identi er equal to itemId
is recommended only when values of attributes contained in the left hand side
of a rule are equal to values of attributes in the recommendation request. If
there are more matching rules, we use all unique article identi ers as a list of
recommended articles. If no recommendation was made using a matching rule,
implementation of baseline algorithm provided by organizers of CLEF
NewsREEL was used. However, in every domain there was a rule with an empty left
hand side called the default rule. This means that every recommendation request
from this domain matched it, and so at least one recommendation was always
made using association rules. The baseline algorithm is thus used only in very
speci c situations related to addressing the cold start problem. The overall
complexity of the algorithm is in uenced by existing algorithms for the rule mining,
pruning and matching of rules with recommendation requests [
To be able to communicate with the platform, we decided to use the Java SDK implementation of ORP interface provided by CLEF NewsREEL organizers4. Main implementations of rule mining algorithms and corresponding operations are available for the programming language R5, we thus created a set of scripts for R. Binary server Rserve6 is used to provide communication between Java and R.
The incoming interactions were stored in a thread-safe collection in Java. The
size of collection was limited by a constant that is con gurable via a con guration
parameters. It is worth noting that this number should be neither too big nor
too small. While big numbers cause taking into account the history and fail in
situations the users are mostly interested in newer content, small numbers do
not provide su cient data for mining reliable association rules. After n minute
interval elapsed (e.g. 30 minute), thread which mined the rules was noti ed. This
triggered the start of a rule mining process. The combination of the number of
stored interactions together with the interval of updates focuses on addressing
issues with the short item lifecycle. To create association rules from interactions
between users and news articles arules library for R was used [
Following parameters: maximum number of interactions being stored, support, con dence, minimum and maximum rule length thresholds were available via a con guration le. This enabled to experiment with these values during run time end evaluations.
Description In our scenario both news recommender system and the environment replaying data stream and sending recommendation requests ran on the same machine. This set-up did not enable to detect possible errors caused by any network problems. It is also important to underline that the stream of recorded data is being replayed in the o ine evaluation. This means that speci c situations can occur: e.g. when recommender system provides recommendation that was not provided in original interaction. This recommendation counts as an unsuccessful one, but it is also possible that the user would nd it interesting if he had seen it.
O ine evaluation was done on a laptop with processor Intel Core i3 3217U with 8GB RAM and Ubuntu 16.04 as operating system.
We selected two subsets of the full dataset provided by organizers for the o ine evaluation. First subset contains rst 100 000 lines from the dataset and the second one contains rst 500 000 lines. We also experimented with other subsets from middle regions of the dataset, but no signi cant changes in results were discovered. We did not experimented with the whole dataset due to the performance and time requirements of experiments for multiple runs of our algorithm with many settings. However, even this limited evaluation allows to get insights into the quality of our algorithm and also allows tuning of parameters.
The datasets contain interactions from six di erent domains. It is worth noting that out of three possible types of ORP messages (event noti cation, recommendation request and item update) recommendation request is represented most prominently. For our rst dataset, this unusual distribution may be caused by the fact that most of the interactions come from late evening hours. Results Prediction accurracy (also known as the o ine click-through rate) was used as a metric to determine the overall quality of partial experiments. The prediction accuracy is de ned as a proportion of the number of recommended items that have been clicked by the user and number of all recommendations. The prediction accuracy of baseline algorithm provided by organizers of CLEF NewsREEL can be seen in Table 1a. Comparing these results to results of our algorithm (Table 1b with parameter values in Table 2), it can be seen that our algorithm performed better in every domain. Results of the baseline algorithm and our algorithm for the second dataset can be seen in Table 3a and in Table 3b. Once again, our algorithm performed better than the baseline.
We decided to experiment with settings of rules updating frequency, con dence, support, maximum rule length, maximum number of stored interactions and attributes selected for rule mining. Results of experiments to ne tune our algorithm and nd values of parameters with the best prediction accuracy can be seen in Table 4 and 5 (the default values are in Table 2).
Several conclusions were drawn from these experiments. The prediction accuracy increased together with increasing of maximum length of association rule only up to a certain length. Increasing the maximum number of clicks did not increase the prediction accuracy. Disabling pruning of rules can bring better results, but at a cost of higher number of rules leading to higher number of erroneous responses and longer computing time. Description In the online evaluation, news publishers forward their users' article interactions to the recommendations provider who in turn forwards it to participant recommender systems taking part in the NewsREEL challenge. Open Recommendation Platform serves as an interface between di erent publishers and participants. Publishers get from ORP recommended articles within partial participants recommendation requests.
Our algorithm was deployed on a dedicated server and communication with the Open Recommendation Platform was established using the ORP protocol and the provided SDK. Results Online evaluation in CLEF NewsREEL consisted of two test periods and an evaluation period. Our algorithm took part in the second test period and in the evaluation period. The click-through rate was used as a metric to evaluate the quality during the online evaluation. Click-through rate is de ned as a number of recommended items that the user visits divided by the total number of recommendations.
Results from the 10th of April, when second test period was in progress, are presented in Table 6. WIRG is the name under which our algorithm was registered. BL2beat is to the best of our knowledge the baseline algorithm provided by the organizers. Names of other teams were anonymized. Click-through rate from evaluation period is presented in Table 7a and o cial results from organizers are presented in Table 7b. Names of other teams were anonymized too.
Drop in of the click-through rate during the rst days of the evaluation was caused by multiple interruptions of the tra c from ORP. We presume that these interruptions were caused by network problems and not by erroneous content of recommendations.
Using the click-through rate as the main metric, our algorithm took 13th place of 21 contestants. We were able to beat the baseline. Since we do not know any details about other participating algorithms, it is not possible to state any conclusions yet. The important fact is that our algorithm was able to handle all incoming messages, process data and provide recommendations. The recommendations are at the same time easily explainable. 4
In this paper our news recommender system based on association rules was examined. The main idea of the algorithm is to build a rule based classi er, use the pruning to signi cantly reduce the amount of rules while the recommendations can be provide faster and quality of recommendations remains comparable. The advantage is that the recommendations are explainable if needed. Our algorithm took part in both tasks of the CLEF NewsREEL 2017 challenge. The algorithm showed better results in the o ine evaluation with higher rate of prediction accuracy than the provided baseline algorithm. During the o ine evaluation we also experimented wit several setting of algorithm parameters. In the online evaluation, our algorithm managed to beat baseline. Our algorithm nished above baseline and above most of other contestants in the second test period. During the evaluation period, results of our algorithm were not that impressive. While still nishing slightly above baseline, its overall results were on the 13th place.
In our future work we would like to address the detected issues and limitations of our solution. We will focus on the evaluation of the approach using larger subsets of the dataset and on recommendations in other domains. One aspect that we would like to also try to overcome is the need for repetitive computation of models on the background using stream-based version of the rule mining algorithm.
This research was supported by Faculty of Informatics, Czech Technical University in Prague.