The news recommendation problem poses a number of specific challenges that established recommendation techniques, successful in other settings, do not tackle adequately. For example, unlike in other domains, the relevance of news articles drops significantly over time, and the order in which users visit news articles matters greatly. Furthermore, in the context of breaking news, user interests can change rapidly, and there is a need to generate recommendations on-the-fly, taking into account recently published articles and the latest trends among users' preferences. To address these issues, we use a form of sequential pattern mining to generate up-todate news recommendations on a click-by-click basis. In this approach, patterns are mined incrementally from the incoming clickstream so that new items and trends are considered. Our experimental evaluation demonstrates that our method compares favorably with existing techniques and outperforms them on a variety of metrics.
Each recommendation scenario has its own particular
characteristics, which call for diferent approaches in designing
recommender systems (RS). Thus far, numerous technical
approaches have been proposed for generating
recommendations, including data mining techniques, such as sequential
pattern mining (SPM) methods [
News is a peculiar application domain of RS for a number
of reasons. For example, users mostly read news articles in
the first two days after publication, after which the relevance
of articles dramatically decreases [
Copyright ' 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
It is, therefore, necessary to update news recommendation models immediately, which is not possible with most state-ofthe-art recommendation approaches, such as those based on latent factors. Instead, a news recommendation model needs to allow for incremental updates based on every new click. In this paper, we propose a news recommendation approach based on the above-mentioned design goals. The algorithm mines patterns from ongoing user sessions incrementally and subsequently adds the patterns to a tree-based model. This model can be scanned eficiently for patterns that match a given user’s current click session, and recommendations can, consequently, be generated in real-time based on the most recent information available. 2
In the field of recommender systems, modeling temporal
dynamics of user behavior and the evolution of items are
challenging issues [
Other approaches use contextual information, such as the
time of day or the user’s location [
Recently, deep learning techniques, specifically Recurrent
Neural Networks (RNN), have also been used to model
shortterm user behavior, leading to promising results in
sessionbased news recommendation scenarios [
In contrast, traditional nearest neighbor schemes, which
do not need to train extensive models, have recently been
shown to be a strong baseline in the news domain and other
recommendation scenarios where short-term interests are
important [
Another traditional approach used to generate
recommendations in a number of domains is SPM [
In this section, we first give a brief overview of the basics of sequential pattern mining. We then explain the proposed tree-based model and the recommendation mechanism. 3.1
Sequential pattern mining is a well-established field in data
mining. In the traditional setting, given a database of
sequences, the goal is to discover which (sub)sequences occur
often in the data [
Our setting is well-suited for SPM. The data consists of user sessions, each of which can be represented as a sequence of clicks, with its associated subsequences. Consequently, a frequent sequential pattern is an often encountered sequence of clicks. For example, the frequent sequential pattern {A, B, C} indicates that many users have first clicked on A, then on B, and, finally, on C. Therefore, if we know that the current user has clicked on A and then on B, we could recommend item C to the user. We require the patterns to be frequent, i.e., based on a high number of previous sessions, in order for the recommendations to be reliable. 3.2
Our proposed algorithm uses a tree-based model to store mined patterns, which allows us to easily update the recommendation model based on each incoming session. In the following, the tree model is described based on an example. Let two sessions be 1 and 2, where 1 contains clicks on items {A, B} and 2 includes clicks on items {A, C}.1 To capture all (sub)sequences in the session, we first calculate the power set of the items in the session. For 1 the power set would be {{A}, {B}, {A, B}}, and for 2 it would be {{A}, {C}, {A, C}}. Next, we build the tree model based on the power sets. For all sets in the power set, we traverse the tree and increment the counter of the respective last node. For example, for the set {A, B}, the algorithm starts from the root and traverses through node A and then B. Reaching B, it increments the node’s frequency counter by one. If there 1We show the clicks of a user in the current session in set notation. However, the order of items in the set is important in our model. S1 A B S2 A C {A} {B} {A, B} {A} {A, C} {C}
A / 2
B / 1
C / 1 B / 1
C / 1
Data: * = *1, *2, . . . , *: current (partial) user session Used subroutines : (): creates the (full) power set of Result: * : partial power set *− 1 := * ∖ *; ◁ remove (latest click) * := (− 1); ◁ create power set of *− 1 foreach Set * ∈ * do
* := * ∪ ; ◁ add to each subset end return * ; are items in the set for which no nodes exist in the tree, new nodes are created on-the-fly. This process is applied to all sets of the power set. Figure 1 shows the tree-based model after processing the two sessions from our example.
Since the number of subsets in a power set grows exponentially based on the session length, it is important to limit the power set size. Thus, we introduce an adjustable parameter called sliding window which limits the number of clicks in a pattern. If a user has a session longer than clicks, the power set of the first items is calculated. Then, the window slides by one, and the power set from the 2nd item to the +1st item is calculated, and so on. Thus, we are even able to process patterns from longer sessions eficiently. 3.3
In reality, complete user sessions do not become available for processing right away, but instead click-by-click. However, waiting for a session to “finish”, e.g., when a user has not clicked on an article for 20 minutes, is also not an option, as this would result in an inherently outdated model. The algorithm, therefore, needs to build the power set () of each session incrementally. To this end, when the th click is added to a session, the algorithm creates a partial power set * . The idea is that, in combination with the previously created partial power sets of that session, the complete power set will be assembled as 1* ∪ 2* ∪ . . . ∪ * = (). In this way, the subpatterns in the partial power sets can already be applied to the tree model while the user session is still ongoing.
The subroutine for creating a partial power set * based on an ongoing session * is given in Algorithm 1. We explain this subroutine with an example. Assuming that, so far, a user clicked on items A and B in an ongoing session, the algorithm will iteratively process the partial sessions 1* = {} and 2* = {, }. Thus, when processing the first session snapshot 1* , the algorithm would simply produce the empty set {{}} and then add , resulting in
1* = {}. This partial power set would then be applied to the pattern tree. When processing 2* in the next step, the algorithm needs to produce a partial power set 2* that does not overlap with the previously created 1* , as this information is already stored in the tree model. The algorithm will, thus, first build 2* as {{}, {}} and then add to each subset, to create 2* as {{}, {, }}. Together, these partial power sets 1* and 2* form the complete power set of the user’s clicks session {A, B} as 1* ∪ 2* = () = {{}, {}, {, }}. 3.4
As mentioned, in news recommendation, it is paramount to keep track of recent user interests. To focus on more recent interest trends, while also reducing the volume of patterns in the model, we remove stale patterns from the tree based on a queue implementation of adjustable size (). As clicks occur, the respective session snapshots are added to this queue, and, once the queue is full, the oldest session snapshot is removed. The snapshot is then processed again to revert its efect on the pattern tree. That is, frequencies of (sub)sequences originating from this old session are decremented, and, in case a node’s frequency is reduced to zero, the node is completely removed from the tree. Consequently, only the most recent clicks have an efect on the model, and the tree, thus, represents only the most recent interest trends among users. 3.5
To generate recommendations, the score for each candidate item from the set of all available items is calculated as follows:
score = ∑︀ ∈() conf( ), with ︂{ ( ∪ )/( ) if ( ∪ ) ≥ ∧ ( ∪ )/( ) ≥ conf( ) =
0 otherwise where () is the power set of the current user session , and ( ) is a function that returns the frequency of a sequence in the tree model. As can be seen from the formula, for each subset of the power set (), the pattern tree is scanned for a matching pattern as well as a continuation of that pattern by the candidate item , i.e., ∪. The confidence score conf(· ) for this tree branch is then calculated as the frequency of the pattern continuation ( ∪ ) divided by the frequency of its parent pattern ( ). Additionally, two threshold parameters are introduced to filter patterns of low potential usefulness. On the one hand, if the pattern continuation appears less than times in the data, it is not considered. On the other hand, if the confidence score is less than , the pattern is also not included in the calculation. This process is then continued for each tree branch that matches with a subset of the current session’s power set. Finally, the items are ranked based on their accumulated confidence scores. 4
In this section, we elaborate on the design and results of an empirical evaluation of the proposed recommendation approach.2 4.1
We design our experiments based on an open-source
framework, called StreamingRec [
To demonstrate the efectiveness of our proposed approach,
we compare it with a variety of algorithms implemented in the
StreamingRec framework including a popularity baseline, an
item-based co-occurrence scheme, and a session-based nearest
neighbor method. The popularity baseline (Pop.) works by
simply recommending the articles that were clicked most
often in the data set. The recently popular algorithm (R. Pop.)
ranks candidates by their popularity within the recent past
(20 minutes in our setting). The co-occurrence method
(CoOcc.), on the other hand, selects recommendation candidates
based on how often they occurred together in other sessions
with items from the target user’s session. The nearest
neighbor scheme (V-SkNN) performed best in previous evaluations
with the StreamingRec framework [
We evaluate our approach on two real-world data sets from
Plista and Outbrain. The Plista data set contains German
news published by 12 publishers during June 2013 [
F1 Performance. Table 1 shows detailed performance results
on the Plista and Outbrain data sets. In terms of F1, the
baseline algorithms such as Random and Most Popular perform
poorly as they do not consider new items and the recency of
the clickstream. On the other hand, the Co-Occurrence and
Recently Popular methods have relatively reasonable F1
performance, as they utilize the session context. The proposed
Seq approach is the best-performing strategy for both data
sets. The improvement in terms of F1 in comparison with
V-SkNN—the best-performing strategy in previous
experiments [
MRR Performance and Aggregate Diversity. Looking at the Mean Reciprocal Rank measure, the best performing 3https://www.kaggle.com/c/outbrain-click-prediction/data algorithm is V-SkNN, due to its prioritization of items closer to the current click of the user in the session for similarity calculation. All variations of our approach are, however, not far behind V-SkNN in terms of MRR. With respect to aggregate diversity, which measures the number of unique items recommended by each algorithm (RI), the Random strategy scores highest, which is not surprising. However, most of the more advanced algorithms, including Seq, are also able to recommend from a large pool of items.
Runtimes. We also report computation times for each algorithm, i.e., the time it takes, on average, to generate a recommendation list. Here, we can observe that the best method in terms of F1 (Seq) also performs fastest. In addition, as expected, methods that consider recency aspects by filtering “old clicks” are faster compared to methods that build their model based on the whole clickstream history. In contrast, the session-based nearest neighbor method (VSkNN) is not as eficient in creating recommendations as the proposed approach. One possible reason for this could be the large number of sessions that have to be compared with the current session, while the proposed method, in contrast, only has to scan a few branches of the pattern tree.
Effect of Window Size. As already mentioned, our approach features a sliding window constraint that limits the length of patterns to prevent exponential growth of the pattern tree. We experimented with diferent window sizes to observe the efect on accuracy. As expected, longer window sizes lead to better performance, but also slower processing times. However, at a certain point, performance actually decreases with longer window sizes, indicating that after a certain number of user clicks, item relations are much less meaningful. The experiments revealed that a window size of 5 was a good choice on both data sets.
Performance w.r.t. List Length. As a more detailed analysis of the efectiveness of the proposed approach, we evaluated its F1 performance with respect to diferent cut-of thresholds way, we can estimate more clearly how useful the recommendations would be in diferent application scenarios that require, for example, short lists in mobile apps or longer lists on news websites optimized for desktop use. The results for the Outbrain data set show that the F1 performance of Seq remains steady around 0.21 when the list cut-of increases, while V-SkNN’s performance drops (see Figure 2a). Thus, compared to V-SkNN, which can only be applied where short recommendation lists are needed, the proposed Seq approach shows promising results for a wider range of list lengths.
Effect of Recency. Finally, we seek to understand the efect of recency on accuracy. Thus, we investigated diferent queue size settings () for the best method proposed in this work, namely Seq. As shown in Figure 2b, the larger the queue size, the better the performance in terms of F1 becomes. For example, for the Outbrain data set, when only patterns based on the last 500 clicks are considered, the algorithm achieves an F1 of 0.17, while 2000 clicks already produce an F1 of 0.20. However, after a certain point, performance decreases again. Interestingly, our proposed approach performs better than V-SkNN even when we only work with the 400 most recent clicks in the stream. In contrast, V-SkNN needs to consider 4 500 neighboring sessions to achieve its most optimized F1 performance, which still falls behind our approach, highlighting the suitability of a pattern-based strategy for the news domain. 5
The principal aim of our work was to recommend up-to-date news articles that fit user interests in a session-based scheme. To this end, we implemented an algorithm based on sequential pattern mining that extracts patterns incrementally from a continuous clickstream. Our empirical evaluation revealed that the approach’s ability to capture temporal dynamics in user behavior led to improved accuracy compared to state-ofthe-art news recommendation approaches. In addition, the experiments showed that extracting patterns based mainly on the most recent clicks in the data stream is not only more eficient but also leads to higher accuracy.
In the future, we plan to extend our session-based approach by also considering long-term user click sequences to create personalized news recommendations. Additionally, more complex weighting functions based on the position of clicks within sessions are planned. Lastly, we aim to explore the capabilities of our approach in other evaluation settings and domains as well as in online studies.