Improving session-based temporal recommendation by using dynamic clustering

Abstract

Modelling users’ dynamic preference for personalized temporal recommendation has been a hot research topic. Traditional dynamic recommendation models divide a user’s interaction history into fixed-sized windows to learn the user’s evolving preference. This strategy however worsens the issue of data sparsity in that some sessions may have very little or even no interaction for preference inference. To alleviate the data sparsity issue and avoid errors due to data imputation that is commonly adopted by existing models, a novel session-based dynamic recommendation model that divides a user’s interaction history with dynamic window size is proposed. An empirical study on the users’ activity life cycles using real-world dataset is conducted to demonstrate the nonuniformness and aggregation of the users’ behavior patterns on the time dimension. Based on the study, a user’s interaction history is divided with dynamic temporal window size by using dynamic clustering. The user’s evolving profile is then constructed by modeling her preference in each session using Latent Dirichlet Allocation (LDA) and a time sensitive weighting scheme. Our dynamic model is designed for two major recommendation tasks: (1) top-N recommendation, which is provided by measuring the relevance of probabilistic topic distribution between the user’s profile in the next temporal domain and each candidate item, (2) rating prediction that is achieved by finding $K$ nearest user/item neighbors based the similarity of probabilistic topic distribution between users/items. Extensive empirical experiments over two real datasets demonstrate the effectiveness and superiority of our method by comparing to representative temporal dynamic methods.

Keywords

Dynamic clustering temporal context Latent Dirichlet Allocation time window

1. Introduction

With the rapid growth of the Internet, huge amount of information is generated every moment on the Web. By retrieving useful information, personalized recommendation has become a popular method to handle information overload. Existing recommendation models can be classified into three categories: (1) Content-based filtering, which compares correlations between the content of items and a user’s preference and recommend items similar to the user’s consumption history [1]. (2) Collaborative filtering (CF), which is the most successful recommendation algorithm, aims at predicting a target user’s preference based on similar users’ or items’ feedback information [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. (3) Hybrid methods, which combine the content-based and collaborative filtering methods in different ways [12, 13, 14, 15, 16, 17, 18].

Traditional recommendation models assume static user preference patterns. However, in real-world recommender systems, users’ preference may drift over time. For instance, in movie recommendation scenario, a user who is fond of action movies may change his preference to romance movies due to various factors, e.g., having a new relationship. Time is thus an important factor in capturing users’ dynamic preference for personalized recommendation. Quite a few works [19, 20, 21] considering temporal dynamics have been proposed in recent years. Some methods [19, 20] introduced time as a universal dimension shared by all users. However this assumption may not always make sense because the time dimension is a local effect. Koren [21] modeled time factor for each user separately in a factorization mode, but the performance improvement was not significant. On the other hand, session-based CF [22] split a user’s interaction history into fixed-sized time windows (sessions) to capture the user’s behavior patterns. Particularly, some works [23, 24, 25, 26] combined Latent Dirichlet Allocation (LDA) with session-based CF, where the probabilistic topic distribution for each session was derived to model users’ dynamic preference for recommendation. However, dividing users’ behavior histories into fixed-sized windows further worsen the data sparsity issue, which refers to the corresponding user-item rating matrix is prevail with missing values because most users rate only a small number of items and a popular item is rated by a few users. That leads to some sessions may have very little or even no interaction information for model building. To handle this issue, cross-domain CF was applied to leverage knowledge across different domains. For instance, in [27], the authors proposed a rating-matrix generative model for effective cross-domain CF to fill the missing rating for both existing and new users. However, the shared knowledge across multiple related domains may be well hidden and not easily obtained. Moreover, filling missing interaction information inevitably introduces noisy data which may influence the accuracy of the model.

In order to alleviate the data sparsity and avoid errors due to data imputation, in this paper, by combining temporal contexts, LDA and dynamic clustering [28], we model session-based temporal dynamic recommendation where a user’s interaction history is segmented using dynamic temporal window size. We first provide an experimental study on users’ activity life cycles using real-world datasets and demonstrate that dynamic clustering is a promising approach to divide users’ interaction histories due to the nonuniformness and aggregation of the users’ behavior patterns on the time dimension. Then, we conduct dynamic clustering on each user’s consumption history based on the dynamic temporal window size, and determine the best number and partition of sessions for each user. We construct a user’s profile based on probabilistic topic distribution by using LDA for each session and a time sensitive weighting scheme. The topics are latent factors that represent a user’s preference on particular items. Specifically, we treat the user set as the corpus, and each user corresponds to a document; for each document, the interacted items of the target user are treated as words, and the corresponding ratings are used as the frequency.

Our model is implemented for two common collaborative filtering tasks: top-N recommendation, which measures the relevance of probabilistic topic distribution of a user in the next temporal domain and that of each candidate item, and rating prediction, which finds $K$ nearest user/item neighbors by using the similarity of probabilistic topic distribution between users/items.

The contributions of our work are summarized as follows:

•
We demonstrate the nonuniformness and aggregation of users’ behavior patterns on the time dimension by studying real datasets. The analysis shows that it is unreasonable to divide the entire interaction history with fixed-sized time windows which can worsen the data sparsity issue.
•
We apply dynamic clustering to find the optimal session number to divide a user’s interaction history, and derive the user preference drift and trend patterns over time by using LDA in each session and the weighted time framework. This approach is able to alleviate data sparsity issue and avoid the limitation of data imputation methods that try to fill the missing interaction information from different domains.
•
Comprehensive experiments conducted over real world datasets demonstrate that our model significantly outperforms the state-of-the-art dynamic recommendation models.

The remainder of this paper is organized as follows. In Section 2, we provide a brief overview of related works for recommender system in general and temporal dynamic recommendation models. Section 3 presents our novel algorithm for temporal domain division based on dynamic clustering with unfixed time window size. Section 4 elaborates the user profiling generation based on temporal domain division by using LDA. The methods for top-N recommendation and rating prediction are introduced in Section 5. In Section 6, we conduct real data based experiments to evaluate the performance of our approach, followed by conclusions and future works outline in Section 7.
2. Related works

In this section, we briefly review recommendation models, which can be categorized into three groups: content-based filtering, collaborative filtering and hybrid methods. We also discuss the techniques of recommendation considering the temporal dynamics and highlight the difference between our proposed method and other existing works.

2.1 Content-based recommendation

Content-based filtering [29] tried to recommend items similar to a user’s interacted items. The similarity was typically measured using content information such as texts. For instance, based on texts, items were represented using the vector space model (e.g. TF-IDF) [30, 31], or probabilistic topic distributions obtained by language models, e.g. probabilistic latent semantic indexing (PLSI) and LDA [23]. However, recommendation purely based on content-based filtering approaches suffer from many drawbacks such as strong dependence on the availability of content, constant user preference (over-specialization) and so on.

2.2 Collaborative filtering

Typical CF approaches collectively model past feedback information, and recommend new items to a user based on the feedback information of other similar users and/or items. Memory-based methods [2, 3] found $K$ -nearest neighbors similar to the target user or item. Model-based methods learned preference model to predict unobserved feedback data [4]. There were many other recommendation methods such as clustering model [5], fuzzy method [6], probabilistic relational model [7], bayesian hierarchy model [9], etc. To handle data sparsity issue, matrix factorization (MF) based methods [10, 11, 32, 33], which learned low-rank latent representation for feedback matrix approximation have been proposed.

2.3 Hybrid filtering

Hybrid filtering [13, 14, 15, 16, 17, 18] explored different strategies to combine content-based filtering and collaborative filtering for performance improvement. In [14], a tag recommender system was proposed by fusing collaborative filtering and content-based recommendation technique. The former exploited the user’s and the community’s tagging behavior for producing recommendations, while the latter exploited heuristics to extract tags directly from the textual content of resources. In [16], the authors proposed a hybrid approach for movie recommendation. The recommendation is generated by triggering either a content-based prediction or a collaborative filtering prediction based on the monitoring of certain model parameters.

2.4 Recommendation with temporal context

Contextual information such as location, time, emotion, environmental conditions have been widely used to describe and characterize the items we like. Time is an important factor that influences recommendation accuracy. Most time-aware models add temporal aspects into the collaborative filtering model. For example, in [19], Sun et al. introduced time as a universal dimension shared by all users. In [20], the authors treated temporal domain as the third dimension to construct a user-item-time tensor, where tucker decomposition was applied to factorize the tensor. Khoshneshin and Street [34] dynamically assigned users/items to different clusters based on evolutionary co-clustering. Ding and Li [35] proposed a framework to compute the time different weights of diverse items. Koren [21] proposed to track the time changing behavior throughout the life span of the data and modeled time factor for each user separately via CF. Liang et al. modeled long-term and short-term preferences simultaneously by using session-based temporal graph [36]. Lathia et al. [37] investigated the temporal diversity of items to generate top-N recommendations.

In order to model user-interest distribution over items, one possible approach was to use probabilistic topic models, e.g. Latent factor model (LFM), PLSI and LDA [38]. Session-based CF [22] used session information to capture sequence and repetitiveness in the process. In [39], Zheleva et al. developed a session-based hierarchical graphical model using LDA. In [25], Li et al. selected news groups using long-term profile and recommended candidates based on the short-term user profile by comparing probabilistic topic distribution using LDA and increased the diversity of news list by using absorbing random walk model. In reference [40], Hong et al. formalized a user’s long-term preference using the item taxonomy, which identified the exact stage of user and provided an item list to the user through other similar user within the same stage by using clustering-based and graph-based recommendation method.

Most session-based methods divided a user’s interaction history into some sessions using fixed temporal domain size, which however suffered from serious data sparsity. To handle this issue, a line of research rely on data imputation techniques was proposed. In [27], Li et al. proposed a rating-matrix generative model (RMGM) for effective cross-domain collaborative filtering to fill the missing rating for both existing and new users. In [38], the authors modeled user-interest profile drift over time by using RMGM to fill missing scores over temporal domains and adopted the cross-domain CF framework to share the static group-level rating matrix across temporal domains. LDA based user-interest distribution over item groups was designed to drift slightly between successive temporal domains. These models were built based on the assumption that each user has multiple counterparts over temporal domains and successive counterparts were closely related. However, due to the influence of external factors, the user interest in the adjacent temporal domains may change dramatically. Moreover, the shared knowledge across multiple related domains may be well hidden and not available.

Different from existing approaches, in our work we split a user’s interaction history by using dynamic clustering, which flexibly creates sessions with variable time window lengths. Users’ dynamic preference in different sessions is represented and learned using LDA and a decreasing time framework.

3. Temporal domain division based on dynamic clustering

3.1 Analysis of users’ behavior patterns

We choose two datasets, i.e., the Movielens dataset and the Eachmovie dataset that are widely used in recommender systems community to analyze users’ behavior. The Movielens dataset records 14,111 users’ ratings to 9,180 movies from January 1st, 2006 to January 5th, 2009. Eachmovie dataset contains 36,658 users’ ratings to 1,613 movies from January 9th, 1995 to September 15th, 1997. Note that for both datasets, the users with less than 20 ratings are removed.

Figure 1.

Users’ activity life cycle.

We analyze users’ daily activities, which are measured by the number of watched items in their life cycles. Based on statistical analysis of users’ behavior characteristics in the time dimension, users can be divided into three categories according to the length of active time of the user after we split the user’s interaction history into sessions with a temporal window: Short Period Active User (SPAU), Middle Period Active User (MPAU) and Long Period Active User (LPAU). The three kinds of users are shown in Fig. 1 using Movielens dataset. We observe that the active periods of most SPAU (line one) are very short and their interaction behavior is concentrated in 1 to 2 sessions while other sessions have little interactions. The active periods of MPAU (line two) are distributed into 3 to 6 sessions if we divide the user’s interaction history into 9 sessions with temporal size of 120 days. The difference of movie number for each temporal domain is bigger and each user’s life cycle is different from each other. Finally, the active periods of LPAU (line three) are distributed across the whole history (the number of sessions are greater than 7) which is longer and the number of watched movies in each session is relatively stable. In reality, the fraction of LPAU is very small and most users are SPAU and MPAU. Specifically, SPAU, MPAU and LPAU are 12,329, 1,525 and 257 in Movielens; 34,938, 1,407 and 313 in Eachmovie respectively. The above analysis shows that users’ interaction information is extremely sparse in time dimension because most users are active only in a few temporal domains. It is thus important to flexibly segment a user’s interaction history with variable time window size to better model the user’s dynamic preference. Of course, the category of a user belonged to will be varied with the change of user interaction behavior and regularly update the results of dynamic clustering offline. The classification of a user can be changed from SPAU to MPAU or even LPAU if the user’s interactive behavior gradually increase. On the contrary, it is possible that the category of a user will be changed from LPAU to MPAU or even SPAU if the user has no new interaction. In the next subsection, we elaborate our dynamic clustering based method.

3.2 Temporal domain division based on dynamic clustering

We ignore the temporal domains without interaction information when we model a user’s preference. Specifically, in our problem, it is not trivial to derive the answer for how many sessions for each user are appropriate. Therefore, in our method, we employ dynamic clustering to find the best segmentation for each user, in which the optimal number of cluster is not simply predefined, but is determined by computing item density and dynamic merging items when the size of the smallest temporal domain is given. First, we set the smallest temporal domain with the size of $\delta$ . Then for each user we select a watched item as an active item and calculate item density of it, which is the number of items the user watched and the watched time intervals with the active item are smaller than $\delta$ , and sort the densities of all items the user has watched in descending order. Next, we select the largest density point as the first cluster center and compute the distance between the existing center and other points in descending order. if the distance is greater than $\delta$ , this point will be considered as a new clustering center. This process continues until no point whose distance to any existing cluster center is greater than $\delta$ . We cluster all data points of a user based on the $m$ initial cluster centers obtained from the last step. The two clusters will be merged if the distance between them is less than $\delta$ and the distances among new clusters are recalculated and the process is continues until the results of two adjacent clustering are not changed. This whole process should be updated offline at regular intervals $T$ . During this period, if a user has new interaction behavior, we find the minimum distance between it and the existing cluster center. If it is less than $\delta$ , the new point will be merged into that classification, othwewise, it will be seen as a new clustering. Then we should recalculate the probabilistic topic distribution by using LDA in session where the user interactions have changed. For a new user, we adopt a similar method to deal with his interactions. Algorithm 1 presents the detailed procedures of the proposed dynamic clustering.

[h]

Temporal domain division based on dynamic clustering Input:the interaction history for all users $H=\{H_{u_{1}},H_{u_{2}},\cdots,H_{u_{n}}\}$ the smallest temporal domain size $\delta$ Output:the division results in time dimension for each user $S=\{S_{u_{1}},S_{u_{2}},\cdots,S_{u_{n}}\}$ the cluster results $C=\{C_{u_{1}},C_{u_{2}},\cdots,C_{u_{n}}\}$ 1:for each user $u_{i}\in\{u_{1},u_{2},\cdots,u_{n}\}$ do2: Calculate item density $D=(d(I_{u_{i}}^{1}),d(I_{u_{i}}^{2}),\cdots,d(I_{u_{i}}^{n_{u_{i}}}))$ with radius $\delta$ , and sort them3: in descending order;4: Select the maximum density point as the first cluster center $c_{u_{i}}^{1}$ 5: while the distance between a point in $D$ and all existing cluster center $\geqslant$ $\delta$ do6: calculate the distance between the existing cluster center and the other points in $D$ 7: with the density decreasing order8: if the distance $\geqslant$ $\delta$ then9: this point will be regarded as a new clustering center10: end if11: end while12: Cluster and calculate the distance between classes regarding $m$ points as the initial 13: cluster center14: while the distances between classes $<$ $\delta$ do15: the two classes will be merged and recalculate the distances between classes16: end while17: return the cluster number $n_{u_{i}}$ and the result $C_{u_{i}}$ 18: Cluster all points with the cluster number $n_{u_{i}}$ and get the cluster result $C_{u_{i}}^{now}$ 19: if $C_{u_{i}}^{now}=C_{u_{i}}$ then20: $C_{u_{i}}\leftarrow C_{u_{i}}^{now}$ 21: $t_{u_{i}}\leftarrow t_{u_{i}}$ 22: else23: goto 1424: end if25:end for26:return $S=\{S_{u_{1}},S_{u_{2}},\cdots,S_{u_{n}}\}$ and $C=\{C_{u_{1}},C_{u_{2}},\cdots,C_{u_{n}}\}$

4. User profile generation based on temporal domain division

After segmenting a user’s interaction history, in this section, we introduce the user profile generation based on probabilistic topic distribution by using LDA and the time-weighting scheme. Our first goal is to segment a user’s interaction history into multiple time frames based on the results of dynamic clustering, and then build the user profile using a deceasing time weight framework. Such a user profile enable us to capture the user’s dynamic preference, which can help us to predict the probabilistic topic distribution in the next temporal domain for recommendation.

4.1 The probabilistic topic distribution for each user by using LDA

Latent Dirichlet Allocation (LDA) is one of the most popular probabilistic topic models, which has been widely used in different contexts to uncover the hidden structure in large text corpora. While in recommender system a user’s preference is influenced by some latent factors. In our proposed method, we employ LDA as the language model to detect the probabilistic topic distribution for each user which represents the latent factors influencing the user’s preference. The general framework has a natural interpretation when dealing with users’ preference data: the set of users define the corpus, each user is considered as a document, the items purchased are considered as words, the ratings are considered as the appeared frequency and finally the topics correspond to the latent factors that influence users’ behavior with respect to items, i.e., users’ preference.

Formally, we define a set of users as $U=\{u_{1},u_{2},\cdots,u_{n}\}$ , a set of items as $I=\{i_{1},i_{2},\cdots,i_{m}\}$ . The division results in time dimension based on dynamic clustering for each user is denoted by $S=\{S_{u_{1}},S_{u_{2}},\cdots,S_{u_{n}}\}$ . Given the interaction history $H_{u_{i}}$ of the user $u_{i}$ , $H_{u_{i}}$ can be divided into multiple segments based on the result of dynamic clustering $S$ : $H_{u_{i}}=\{H_{u_{i}}^{t_{1}},H_{u_{i}}^{t_{2}},\cdots,H_{u_{i}}^{t_{|t_{u_{i}% }|}}\}$ , where $|t_{u_{i}}|$ is the stage number obtained by using dynamic clustering in the whole interaction history for $u_{i}$ , $t_{|t_{u_{i}}|}$ is the latest interaction stage. For each stage $t_{l}(l=1,2,\cdots,|t_{u_{i}}|)$ for the active user $u_{i}$ , we can extract the interaction data $I_{u_{i}}^{t_{l}}$ and the corresponding rating $R_{u_{i}}^{t_{l}}$ , Therefore, the user $u_{i}$ in interaction stage $t_{l}$ can be seen as a set of interacted items $I_{u_{i}}^{t_{l}}$ , each item is regarded as the observed variable $I_{u_{i},j}^{t_{l}}(j=1,2,\cdots,N_{t_{l}})$ , $N_{t_{l}}$ is the items number of $I_{u_{i}}^{t_{l}}$ , then each item $I_{u_{i},j}^{t_{l}}$ can be described by LDA from the perspective of complete probability:

$\displaystyle P(I_{u_{i},j}^{t_{l}})=\Sigma_{k=1}^{K}P(I_{u_{i},j}^{t_{l}}|T_{% i}=k)P(T_{i}=k),$ (1)

where $K$ is the number of topic. To simplify the notation, we denote $\Phi_{ij}^{t_{l}}=P(I_{u_{i},j}^{t_{l}}|T_{i}=k)$ as the multinomial distribution over $I_{u_{i},j}^{t_{l}}$ for topic $k$ and $\theta_{ij}^{t_{l}}=P(T_{i}=k)$ refers to the multionmial distribution over topics for user $u_{i}$ . The parameters $\Phi_{ij}^{t_{l}}$ and $\theta_{ij}^{t_{l}}$ indicate which items are important for which topic and which topics are important for a particular user, respectively (follow Dirichlet distribution). $\Phi_{ij}^{t_{l}}$ and $\theta_{ij}^{t_{l}}$ are hidden variables generated by observed interacted items, which are estimated by using Gibbs sampling. Then, we can obtain the probability $\Phi_{ij}^{t_{l}}$ of each topic $T_{j}$ on item $I_{i}$ and the probability $\theta_{ij}^{t_{l}}$ of each user $u_{i}$ on topic $T_{j}$ in each stage $t_{l}$ :

$\displaystyle\Phi_{ij}^{t_{l}}=P(I_{i}|T_{j},t_{l})=\frac{C_{ij}^{NK}+\beta}{% \Sigma_{n=1}^{N}C_{ij}^{NK}+N\beta}$ (2) $\displaystyle\theta_{ij}^{t_{l}}=P(T_{j}|u_{i},t_{l})=\frac{C_{ij}^{MK}+\alpha% }{\Sigma_{k=1}^{K}C_{ik}^{MK}+K\alpha}$ (3)

Here, $C^{NK}$ and $C^{MK}$ is the $N\times K$ and $M\times K$ dimension matrix respectively. $\alpha$ and $\beta$ are hyper parameters of $\theta_{ij}^{t_{l}}$ and $\Phi_{ij}^{t_{l}}$ . In practice, the default values of $\alpha$ and $\beta$ are typically set to $50/K$ and 0.01 respectively. $C^{NK}$ represents the times of $T_{j}$ given item $I_{i}$ in interaction stage $t_{l}(l=1,2,\cdots,|t_{u_{i}}|)$ , $C_{ij}^{MK}$ represents the number of $T_{j}$ given the user $u_{i}$ in interaction stage $t_{l}(l=1,2,\cdots,|t_{u_{i}}|)$ . Then we can obtain the probabilistic topic distribution vector $P_{u_{i}}^{t_{l}}$ by using LDA on $I_{u_{i}}^{t_{l}}$ and $R_{u_{i}}^{t_{l}}$ . Finally, we can obtain the probabilistic topic distribution vector $P_{u_{i}}=\{P_{u_{i}}^{t_{1}},P_{u_{i}}^{t_{2}},\cdots,P_{u_{i}}^{t_{|t_{u_{i}% }|}}\}$ of user $u_{i}$ in the whole interaction history.

4.2 The user profile generation

Since the latest stage represents a user’s current preference, the probabilistic topic distribution of this stage should carry more importance than the older ones to recommend new items for user. We thus define a monotonic decreasing function $f(t)$ , which reduces uniformly with time $t$ and constrains the function value in the range $[0,1]$ . There are many functions which can satisfy our need, such as sigmoid function,exponential function, Piecewise linear function and so on. In [22], the authors have analyzed the effects of different time functions and concluded that not only the ratio of precision and recall of the exponential function are better than the others, but also the performance distribution of it is more compact. So we select the exponential function as our time function, which is able to describe the gradual decay of the importance of past interaction histories as time goes:

$\displaystyle f_{u_{i}}(t_{n})=e^{-\frac{1}{|t_{u_{i}}|}(|t_{u_{i}}|-n)},$ (4)

where $n=1,2,\cdots,|t_{u_{i}}|$ . $\frac{1}{|t_{u_{i}}|}$ represents the decay rate. The higher the value of $\frac{1}{|t_{u_{i}}|}$ , the faster old interaction histories decay and the lower the importance of the historical information compared to more recent profiles. $|t_{u_{i}}|-n$ represents the stage number between objective temporal domain and historical temporal domain. The higher the stage number, the smaller the impact is on the user preference model. So, we can obtain the user profile vector $P_{u_{i}}=\{f_{u_{i}}(t_{1})P_{u_{i}}^{t_{1}},f_{u_{i}}(t_{2})P_{u_{i}}^{t_{2}% },\cdots,f_{u_{i}}(t_{|t_{u_{i}}|})P_{u_{i}}^{t_{|t_{u_{i}}|}}\}$ of user $u_{i}$ in the whole interaction history after considering the time decay effects.

5. Collaborative filtering tasks

Once we obtain the user profile, we can easily derive a user’s recent preference, and then make recommendation. In this section, we implement our dynamic recommendation model for two major collaborative filtering tasks, i.e., top-N recommendation and rating prediction.

5.1 Top-N recommendation

Based on the topic distribution in each stage, we can predict the probabilistic topic distribution of $u_{i}$ in the next temporal domain, which is the weighted sum of topic distribution in each stage, where the weight is the corresponding time decay effect:

$\displaystyle P_{u_{i}}^{t_{|t_{u_{i}}|}+1}=f_{u_{i}}(t_{1})P_{u_{i}}^{t_{1}}+% f_{u_{i}}(t_{2})P_{u_{i}}^{t_{2}}+\cdots+f_{u_{i}}(t_{|t_{u_{i}}|})P_{u_{i}}^{% t_{|t_{u_{i}}|}}$ (5)

By considering the probabilistic topic distribution $P_{u_{i}}=\{P_{u_{i}}^{t_{1}},P_{u_{i}}^{t_{2}},\cdots,P_{u_{i}}^{t_{|t_{u_{i}% }|}}\}$ of user $u_{i}$ in the whole interaction history and the interest distribution on item $\Phi_{ij}^{t_{l}}$ (see Section 4.1), we derive the topic existence probability in the interaction stage $t_{l}$ which represents the probability distribution on topics $T_{j}$ of all users, that is to say, it is the ratio of the times of $T_{j}$ and the times of all topics given by all items rated by all users in the interaction stage $t_{l}$ :

$\displaystyle P(T_{j}|t_{l})=\frac{\Sigma_{i=1}^{M}C_{ij,t_{l}}^{MK}+\alpha}{% \Sigma_{j=1}^{K}\Sigma_{i=1}^{M}C_{ij,t_{l}}^{MK}+K\alpha}$ (6)

The item probabilistic distribution on topic $\varphi$ can be derived according to Bayesian posterior probabilities:

$\displaystyle\varphi_{ij}^{t_{l}}=P(T_{j}|I_{i},t_{l})=\frac{P(I_{i}|T_{j},t_{% l})P(T_{j}|t_{l})}{P(I_{i},t_{l})}=\frac{\Phi_{ij}P(T_{j}|t_{l})}{\sum_{k=1}^{% K}P(T_{k}|t_{l})\Phi_{ik}}$ (7)

For a given user, our method automatically calculates the cosine similarity between the probabilistic topic distribution $P_{u_{i}}^{t_{|t_{u_{i}}|}+1}$ and $P(T_{j}|I_{i},t_{l})$ and selects the top-N ranked items. In the experiments we will demonstrate the recommendation results with different $N$ .

5.2 Rating prediction

We can obtain the probabilistic topic distribution of all users in the next session and then calculate the cosine similarity between all users. So we can easily find the maximum correlation similar user set for a given user. We can then predict user $u_{i}$ ’s rating to a new item $k$ by leveraging User-based CF:

$\displaystyle\hat{r}_{u_{i},k}=\bar{r}_{u_{i}}+\frac{\sum_{{u_{j}}\in{N(u_{i})% }}\textit{sim}(u_{i},u_{j})(r_{u_{j},k}-\bar{r}_{u_{j}})}{\sum_{{u_{j}}\in{N(u% _{i})}}\textit{sim}(u_{i},u_{j})}$ (8)

$N(u_{i})$ represent the next $|t_{u_{i}}|+1$ temporal domain neighbors for the active user $u_{i}$ , $\bar{r}_{u_{i}}$ and $\bar{r}_{u_{j}}$ respectively represent the average rating of user $u_{i}$ and $u_{j}$ , $r_{u_{j},k}$ denotes user $u_{j}$ ’s rating to item $k$ , $\textit{sim}(u_{i},u_{j})$ is the cosine similarity between the user $u_{i}$ and $u_{j}$ .

5.3 Complexity analysis

The process of temporal recommendation based on dynamic clustering consists of three steps. The first step is to find the optimal cluster number and interaction history segmentation for each user by using dynamic clustering. Then, we obtain the probabilistic distribution by using LDA for each user in each stage. At last, we get the items recommendation results. Supposed that there are $M$ users, $N$ items and the average cluster number for each user is $\hat{t}$ , the total number of interacted items and those in each stage for each user are respectively $\bar{N}_{u}$ and $\bar{N}_{t}$ . For each user, the optimal $\delta$ is obtained by $\bar{r}$ iterations. The computational complexity to calculate the density is $O(\bar{N}_{u}\times\bar{N}_{t})$ , to sort the density and find the clustering center is $O(\bar{N}_{u}^{2}+\hat{t})$ and then the total complexity of dynamic clustering is $O(M\bar{r}(\bar{N}_{u}\times\bar{N}_{t}+\bar{N}_{u}^{2}+\hat{t}))$ . The computational complexity of topic distribution by using LDA for each user in each temporal domain is $O(N\times K\times l)$ and $K$ is the number of topic, $l$ is the number of iterations of Gibbs sampling. So the total computational complexity of topic distribution by using LDA is $O(M\times\hat{t}\times N\times K\times l)$ . The computational complexity of TOP-N recommendation and rating prediction are respectively $O(M\times N\times K)$ and $O(M\times M\times K)$ . So the total complexity of our model is $O(M+M\times N+M^{2})$ because $\hat{t}$ , $\bar{N}_{u}$ , $\bar{N}_{t}$ , $\bar{r}$ , $K$ and $l$ are significantly smaller than $M$ and $N$ . In practical application, the LDA process, the relevance between users and the relevance between users and items can be periodically updated in offline mode. The ranking formation and rating prediction can be operated in online mode, which can be realized efficiently.

6. Experimental evaluation

In this section, we conduct comprehensive experimental evaluation to show the efficacy and effectiveness of our proposed method. In Section 6.1, we introduce the experimental settings including the datasets used in the experiments, the existing approaches that are compared with our model and the metrics for performance comparison. In Section 6.2, we present the experimental results including key parameters finding, model validation and comparison studies.

6.1 Experimental settings

6.1.1 Datasets

We use the MovieLens dataset and Eachmovie dataset to evaluate all recommendation models. For both datasets, we select users with more than 20 ratings and movies with more than 5 ratings for experiment, That is the usual way in recommendation. The MovieLens dataset consists of 2,254,501 ratings provided by 14,111 users on 9,180 movies, whose ratings are from 0 to 5 with the interval 0.5. The Eachmovie dataset records 2,580,245 ratings from 36,658 users to 1,613 movies, whose ratings are from 0 to 1 with the interval 0.2. Each entry contains a user and movie ID, the rating and a timestamp indicating when the movie was watched. The biggest problem of them is that it is unreasonable to rate many items by some users in a very short period, which does not affect the subsequent recommendation process. Therefore, all ratings were simply standardized into 1 to 10 in the data preprocessing stage to the consistency of results.

6.1.2 Comparison

We evaluate the proposed method by comparing with other state-of-the-art temporal recommendation algorithms:

•
TItemKNN [35]: A time-weighted item-based collaborative filtering method that reduces the influence of old data when predicting users’ future behavior.
•
TUserKNN: A time-aware user-based collaborative filtering that reduces the influence of nearest neighbours who rated the target item in the early time when predicting users’ future behavior.
•
TimeSvd++ [21]: A matrix factorization model that incorporates temporal dynamics, where user bias, item bias and user latent factors are modeled as functions of time.
•
LDA-based with the equal temporal window size (E-LDA) [23, 25]: This approach divides users’ interaction history with fixed sized temporal domains and obtains the probabilistic topic distribution for a user by using LDA after filling sparse data with matrix generation algorithm.

6.1.3 Metrics

Now, a recommendation performance can be evaluated from many perspectives, such as accuracy, diversity, novelty and coverage. Accuracy is the basic criteria for evaluating recommender systems, which measures the degree of users like to recommended items. It cab be classified into prediction accuracy, prediction ratings correlation, classification accuracy and ranking accuracy. Based on the recommendation process of our method, we use two widely used metrics, Mean Absolute Error (MAE) and Root Mean Square Error (RMSE), to measure the performance of rating prediction. Top-N recommendation is measured using precision (denoted by $P$ ), which is the ratio of the successfully predicted items to the top- $N$ recommendations, recall (denoted by $R$ ), which is the ratio of the successfully predicted items to the total items to be predicted, and f-score (denoted by $F$ ), which is defined by combining precision and recall:

$\displaystyle F=\frac{2PR}{P+R}.$ (9)

6.2 Experimental results

6.2.1 Selection of the size of the smallest temporal domain $\delta$

Accuracy and computational complexity are the two criteria when we decided the temporal domain size $\delta$ . Accuracy means select a proper temporal domain $\delta$ to generate a more accurate recommendation. The complexity of recommendation is higher because of the smaller size of $\delta$ , which lead to the larger number of temporal domains. So when recommendations have similar accuracy with different size $\delta$ , we should choose the larger one under the condition of guaranteeing normal partition of interaction history. To observe the impact of temporal domain size on recommendation accuracy, we did experiments on Movielens and Eachmovie datasets using different threshold values (see Fig. 2).

Figure 2.

Impact of temporal domain size.

We observe that the MAE of Movielens is basically decreasing with the increase of the temporal domain size. For Eachmovie, the MAE also decreases gradually but when the temporal window size is roughly 140, the MAE starts increasing.

Figure 3.

Impact of the temporal domain size in the maximum session number.

The maximum session number that is determined according to $\delta$ is shown in Fig. 3. We notice that the larger the value $\delta$ , the less session number and the lower computation complexity is. Figures 2 and 3 indicate that the threshold values that lead to better MAE results and smaller computational complexity are 280 and 140 for Movielens data and Eachmovie data respectively.

Figure 4 illustrates the number of users whose interaction histories are divided into the same number of sessions after dynamic clustering with different $\delta$ . From Fig. 4, we observe that the number of users decreases rapidly with the increase of session number. For most users, their histories are divided into 1 to 3 sessions, which indicates that most users are only active in short periods and not active for long time. This again proves that data sparse issue is particularly for conventional session-based approaches that rely on fixed-sized time windows for preference modeling.

Figure 4.

Number of users with the same number of sessions.

Figure 5.

Impact of the topic number.

6.2.2 Selection of the number of topics

K

Since the topic is latent variable in LDA, the optimal number of topics $K$ used in the LDA-based recommendation is often not learned from the data, but is pre-defined, e.g., by cross-validation. We use MAE as the criteria with different $K$ values when $\delta$ is set to the optimal value. As shown in Fig. 5, the best performance is achieved when $k=$ 400 and 300 for Movielens data and Eachmovie data respectively. Therefore, we set $k=$ 400 and 300 for the following experiments.

6.2.3 Model validation: Top-N recommendation

To validate the performance of our model in terms of top-N recommendation, we choose the recall and precision as our criteria and recommend items (top@10, top@20, top@30) to a set of randomly selected users (100 users) by using the top-N recommendation model presented in Section 5.1. We plot the averaged precision and recall over 5 times running in Fig. 6. We can see that both precision and recall are improved with the increase of the recommended size. Moreover, the performance distributions are more compact, demonstrating the effectiveness and stability of our method. $\diamondsuit$ depicts the performance of Eachmovie, and the other is that of Movielens. The averaged performance of Eachmovie outperforms that of Movielens. This shows that our method may be better suitable for the dataset like Eachmovie which has more users, but fewer movies.

Figure 6.

Precision-recall plot for different datasets.

6.2.4 Model validation: Rating prediction

In this experiment, we choose MAE and RMSE as criteria to measure the accuracy of rating prediction of the method presented in Section 5.2. In the neighborhood-based algorithms, the number of similar neighbors $n$ is essential. We calculate MAE for the active users with different value of $n$ , shown in Fig. 7. We notice that MAE decreases when the number of neighbors is increasing. Specifically, for Movielens and Eachmovie data, the performance becomes stable when $n=$ 300 and $n=$ 400 respectively. In the following experiments, we will use such optimal number of neighbors for our approach.

Figure 7.

Performance with different nearest neighbor size.

Figure 8.

Performance comparison with different $\alpha$ . The performance of E-LDA is plotted when the number of sessions is 9 (left figure) and 5 (right figure).

Table 1

Comparison of top-N recommendation results

Datasets	Method	Top@10			Top@20			TOP@30
		P	R	F	P	R	F	P	R	F
Movielens	TItemKNN	0.1157	0.0478	0.0677	0.1441	0.0936	0.1135	0.1750	0.1641	0.1690
	TUserKNN	0.1326	0.1185	0.1252	0.1680	0.1341	0.1491	0.2041	0.1640	0.1821
	TimeSvd++	0.1986	0.1687	0.1824	0.2168	0.2291	0.2227	0.2517	0.2589	0.2552
	E-LDA	0.1701	0.1427	0.1552	0.2148	0.1891	0.2011	0.2060	0.2233	0.2143
	D-LDA	0.2130	0.1961	0.2042	0.2332	0.2421	0.2376	0.2716	0.2874	0.2793
Eachmovie	TItemKNN	0.1366	0.1034	0.1177	0.1841	0.1364	0.1568	0.2230	0.1631	0.1880
	TUserKNN	0.2210	0.1569	0.1835	0.2811	0.1816	0.2205	0.3270	0.2121	0.2570
	TimeSvd++	0.2930	0.0890	0.1365	0.2600	0.1568	0.1956	0.2370	0.2101	0.2227
	E-LDA	0.2478	0.1141	0.1562	0.2222	0.2044	0.2129	0.1962	0.2708	0.2276
	D-LDA	0.3223	0.2160	0.2587	0.2805	0.3242	0.3001	0.2469	0.3869	0.3014

Figure 9.

Rating prediction performance comparison.

6.3 Comparison with other methods

To evaluate the effectiveness of our method (called D-LDA in the experiments), we compare our method with several representative baselines (see Section 6.1.2).

We first compare our D-LDA with another session-based method E-LDA. Remind that $\alpha$ denotes the smallest clustering number by using dynamic clustering. The smaller the value of $\alpha$ , the greater sparsity of the data and the less historical data we can use. To better capture how the recommendation result is influenced by $\alpha$ , we segment a user’s interaction history by using dynamic clustering (i.e., for D-LDA) and fixed-sized window size (i.e., for E-LDA) when $\delta=$ 120. The session number for E-LDA is 9 and 5 when Movielens data and Eachmovie data is used respectively. For D-LDA, we adopt the minimal session number from 2 to 8 and from 2 to 4 for Movielens data and Eachmovie data respectively. We calculate the F-score for all users and plot the averaged F-score for each $\alpha$ , the results are shown in Fig. 8. We can see that the higher the value of $\alpha$ , the larger the F-score of D-LDA is. The performance of E-LDA is basically equal to the performance of D-LDA when the value of $\alpha$ is small.

The results demonstrate that D-LDA obviously outperforms E-LDA in the same degree of data sparsity, which proves that our approach D-LDA can better handle data sparsity issue.

Table 1 summarizes the performance of all methods when different datasets are used. For each approach, we compute precision (P), recall (R) and F-score (F) to measure the performance of top- $N$ recommendation, where we set $N=$ 10, 20 and 30 respectively.

We observe that LDA-based methods outperform KNN-based methods in terms of precision, recall and F-score. TItemKNN and TUserKNN perform similarly. It is evident that users’ profile can be better captured by using LDA. This is because LDA represents or characterizes users’ interest using latent factors which deeply reflect and model interaction relationships between users and items, but KNN-based methods only rely on rating information, which is less informative. The performance of D-LDA is superior to that of E-LDA, which is straightforward since we use the dynamic window size, which alleviates the data sparsity issue and avoids the error caused by data imputation. TimeSvd++ generally outperforms KNN-based methods because similar to LDA-based methods, TimeSvd++ exploits the ’latent structure’ in users’ feedback information, which better capture users’ preference. Although TimeSvd++ is consistently outperformed by our D-LDA, it is similar to E-LDA (with slight improvement), because in both models, users’ interaction histories is divided into sessions with fixed temporal window size.

We also show MAE and RMSE for rating prediction in Fig. 9. The results have similar trends with precision, recall and F-score. We observe that MAE and RMSE of E-LDA, D-LDA and TimeSvd++ are smaller than that of TItemKNN and TUserKNN. Our approach D-LDA further outperforms E-LDA and TimeSvd++. Although the results on different datasets slightly vary, the general tendency is consistent.

7. Conclusions

In this paper, we first provide an analysis of users’ behavior patterns in real-world movie recommendation systems to demonstrate that traditional session-based recommendation models that rely on fixed-sized time windows suffer from serious data sparsity. To handle this issue, we propose a novel method that automatically divides a user’s interaction history into sessions with variable sizes by using dynamic clustering. LDA is then used to model the user’s preference in different sessions to capture his dynamic preference. The proposed method is instantiated for two major collaborative filtering tasks, i.e., top-N recommendation and rating prediction. The experimental results on two real datasets show that our method can not only achieve better recommendation performance, but also tackle the sparsity problem.

As for future work, we intend to build the temporal association graph on users and items according to the relevance of their probabilistic topic distributions, and employ personalized random walk to adaptively select new items. In this way, our model can not only capture users’ preference drifting over time, but also increase the novelty of recommendation.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (U1533104; 61301245), Tianjin Natural Science Foundation (No. 14JCZDJC32500), Hebei Province Natural Science Foundation (No. E2016202341), Research Project of Science and Technology for Hebei Province Higher Education Institutions (No. BJ2014013) and the Fundamental Research Funds for the Central Universities (ZXH2012P009).

References

Balabanovic

and Shoham

, Content-based collaborative recommendation, Communication of the ACM 40(3) (1997), 66–72.

Sarwar

Karypis

Konstan

and Riedl

, Item-based collaborative filtering recommendation algorithms, in: Proc. of the 10th International World Wide Wed Conference, 2001.

Adomavicius

and Tuzhilin

, Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions, IEEE Transactions On Knowledge and Data Engineering 17(16) (2005), 734–749.

H.L.

X.D.

and Yan

B.P.

, Comparison study of Internet recommendation system, Journal of Software 20(2) (2009), 350–362.

Aytekin

and Karakaya

M.Ö.

, Clustering-based diversity improvement in top-N recommendation, Journal of Intelligent Information System 42(1) (2014), 1–18.

Dubois

Huellermeier

and Prade

, Fuzzy methods for cased-based recommendation and decision support, Journal of Intelligent Information System 27(2) (2006), 95–115.

Getoor

and Sahami

, Using probabilistic relational models for collaborative filtering, Workshop on Web Usage Analysis and User Profiling (2000), 83–96.

Hofmann

, Collaborative filtering via gaussian probabilistic latent semantic analysis, in: Proc. of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2003, pp. 259–266.

Chen

Y.H.

and George

E.I.

, A Bayesian model for collaborative filtering, in: International Workshop on Artificial Intelligence and Statistics, 1999.

10.

Srebo

and Jaakkola

, Weighted low-rank approximations, in: Proc. of the 20th International Conference on Machine Learning, Vol. 2, 2003, pp. 720–727.

11.

Salakhutdinov

and Mnih

, Bayesian Probabilistic matrix factorization using Markov Chain Monte Carlo, in: Proc. of the 25th International Conference on Machine Learning, 2008, pp. 880–887.

12.

Luo

and Jin

, Flexible mixture model for collaborative filtering, in: Proc. of the 20th International Conference on Machine Learning, 2003, pp. 704–711.

13.

Dooms

Audenaert

and Fostier

, In-memorydistributed, content-based recommender system, Journal of Intelligent Information System 42(3) (2014), 645–669.

14.

Lops

de Gemmis

and Semmeraro

, Content-based and collaborative techniques for tag recommendation, Journal of Intelligent Information System 40(1) (2013), 41–61.

15.

Chu

and Park

, Personalized recommendation on dynamic content using predictive bilinear models, in: Proc. of the 18th International Conference on World Wide Web, 2009, pp. 691–700.

16.

Lekakos

and Caravelas

, A hybrid approach for movie recommendation, Multimedia Tools and Applications 36(1) (2008), 55–70.

17.

Rao

Jia

Feng

and Zhao

, Personalized news recommendation using ontologies harvested from the web, in: Proc. of 14th International Conference on Web-age Information Management, Vol. 7923, 2013, pp. 781–878.

18.

Albanese

Chianese

D’Acierno

Moscato

and Picariello

, A multimedia recommender integrating object features and user behavior, Multimedia Tools and Applications 50(3) (2010), 563–585.

19.

Sun

Faloutsos

Papadimitriou

and Yu

P.S.

, GraphScope: parameter-free mining of large time-evolving graphs, in: Proc. of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, pp. 687–696.

20.

Liang

Chen

Huang

T.K.

Schneider

and Carbonell

J.G.

, Temporal collaborative filtering with Bayesian probabilistic tensor factorization, in: Proc. of the 10th SIAM International Conference on Data Mining, 2010, pp. 211–222.

21.

Koren

, Collaborative filtering with temporal dynamics, in: Proc. of the 15th ACM SIGKDD International Conference on knowledge Discovery and Data Mining, 2009, pp. 447–455.

22.

Park

S.E.

Lee

and Lee

S.G.

, Session-Based Collaborative Filtering for Predicting the Next Song, in: Proceedings of 1st ACIS/JNU International Conference on Computes, 2011, pp. 353–358.

23.

Porteous

Bart

and Welling

, Multi-HDP: A non parametric Bayesian model for tensor factorization, in: Proc. of the 23rd National Conference on Artificial Intelligence, Vol. 3, 2008, pp. 1487–1490.

24.

Ricardo

and Fonseca

M.J.

, Improving music recommendation in session-based collaborative filtering by using temporal context, in: Proc. of IEEE 25th International Conference on Tools with Artificial Intelligence, 2013, pp. 783–788.

25.

Zheng

Yang

and Li

, Modeling and broadening temporal user interest in personalized news recommendation, Expert Systems with Applications 41 (2014), 3168–3177.

26.

Steyvers

and Griffiths

, Probabilistic topic models, In handbook of Latent Semantic Analysis: A Road to Meaning. Lawrence Erlbaum, 2007.

27.

Yang

and Xue

, Transfer learning for collaborative filtering via a Rating-Matrix generative model, in: Proc. of the 26th International Conference on Machine Learning, 2009, pp. 617–624.

28.

Andrea

Ernestina

and Santiago

, Dynamic clustering process to calculate affinity degree of users as basis of a social network recommender, in: Proc. of Web Information Systems Engineering, Vol. 7652, 2013, pp. 215–225.

29.

Lops

Gemmis

and Semeraro

, Content-based recommender systems? State of the art and trends, Recommender Systems Handbook (2011), 73–105.

30.

Ren

and Feng

, A concept-centric web news recommendation system, in: Proc. of 14th International Conference Wed-age Information Management, Vol. 7923, 2013, pp. 796–798.

31.

Capelle

Frasincar

Moerland

and Hogenboom

, Semantics-based news recommendation, in: Proc. of the 2nd International Conference on Web Intelligence, Mining and Semantics, 2012.

32.

Salakhutdinov

and Mnih

, Bayesian probabilistic matrix factorization using Markov chian Monte Carlo, in: Proc. of the 25th International Conference on Machine Learning, 2008.

33.

Lawrence

N.D.

and Urtasum

, Non-Linear matrix factorization with Gaussian processes, in: Proc. of the 26th International Conference on Machine Learning, 2009, pp. 601–608.

34.

Khoshneshin

and Street

W.N.

, Incremental collaborative filtering via evolutionary co-clustering, in: Proc. of the 4th ACM Conference on Recommender Systems, 2010, pp. 325–328.

35.

Ding

and Li

, Time weight collaborative filtering, in: Proc. of the 14th ACM International Conference on Information and Knowledge Management, 2005, pp. 485–492.

36.

Liang

Yuan

Zhao

and Li

, Temporal recommendation on graphs via long-and short-term preference fusion, in: Proc. of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010, pp. 723–731.

37.

Lathia

Hailes

Capra

and Amatriain

, Temporal diversity in recommender systems, in: Proc. of the 33rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2010, pp. 210–217.

38.

Zhu

Zhang

Xue

and Wu

, Cross-Domain Collaborative Filtering over Time, in: Proc. of the 22th International Joint Conference on Artificial Intelligence, 2012, pp. 2293–2298.

39.

Zheleva

Guiver

Mendes

R.E.

and Milic-Frayling

, Statistical models of music-listening sessions in social media, in: Proc. of 19th International Conference on World Wide Web, 2010, pp. 1019–1028.

40.

Hong

and Li

, Product recommendation with temporal dynamics, Expert Systems with Applications 39 (2012), 12398–12406.

Improving session-based temporal recommendation by using dynamic clustering

Abstract

Keywords

1. Introduction

2.1 Content-based recommendation

2.2 Collaborative filtering

2.3 Hybrid filtering

2.4 Recommendation with temporal context

3. Temporal domain division based on dynamic clustering

3.1 Analysis of users’ behavior patterns

4. User profile generation based on temporal domain division

4.1 The probabilistic topic distribution for each user by using LDA

5.1 Top-N recommendation

6. Experimental evaluation

6.1 Experimental settings

6.1.1 Datasets

6.1.2 Comparison

6.2.1 Selection of the size of the smallest temporal domain δ

6.2.3 Model validation: Top-N recommendation

7. Conclusions

Footnotes

Acknowledgments

References

6.2.1 Selection of the size of the smallest temporal domain $\delta$