Multi-granularity user interest modeling and interest drift detection

Abstract

Since the advent of Web 2.0 culture, there as been an explosion of data on the internet. The traditional service model based on the search engine can no longer meet the increasing demand for personalized service. Taking the Douban film review platform as an example in this paper, we propose a method to model user preferences and detect preference drift. Based on a hierarchical topic tree and tilted time window, we design a hierarchical classification tree, named HAT-tree, to maintain the history of the user’s preferences at multi-topic and multi-time granularity. We identify the user’s primary historical preferences, predict their future primary preferences and also detect user preference drift. The proposed algorithm can find the user’s long-term and short-term preferences, detect the user’s explicit and implicit preference drift, and highlight the importance of the user’s more recent preferences. Many experiments are carried out on multiple data sets, and the experimental results show that the proposed method is more accurate than other similar algorithms of user preference drift detection.

Keywords

User interest model drift detection hierarchical classification multi-granularity

1. Introduction

With the development of information technology and social networking [2, 1, 3], a large number of applications have emerged, such as Twitter, Facebook, Weibo, YouTube, Douban, etc., which brought convenience and greatly enriched our lives. Although we can now enjoy the convenience of the Internet, we frequently spend unnecessary time and energy trying to find the resources we really need in the vast ocean of available data. What’s worse, due to the limitations of the search conditions and algorithms, the results returned by the search engines often fail to meet the user’s needs entirely.

When an application such as those mentioned above is used, certain data about the interaction will be recorded. The time the user logs in or out, the duration of the visit, and the details of the activities will be recorded. These details may include personal opinions, the sharing or forwarding of others’ opinions, as well as ratings given and comments made on published messages. This information about a particular user contains his/her preferences. We identify two possible categories for user preferences. Firstly, a user’s preferences can be categorized by their expected duration. Long-term preference is expected to stay relatively constant over time, while short-term preference might change more frequently [4]. Secondly, user preferences can be categorized by how they are presented. Certain preferences can be expressed explicitly while other, implicit preferences, may be difficult to express directly but present the user’s potential unconscious tendencies [5].

Effectively capturing the dynamic changes of user preference is one of the most critical tasks when building user preference models[6, 7]. Building the user’s time-varying preference model can help to provide more qualified services. For example, timely news can be recommended to users by capturing their changing preferences[8]; analyzing the user’s recent shopping-related activities can also assist in pushing the appropriate advertisements to the user at the right time[9]. These methods often use the forgetting curve model or time decay model to simulate the changing trend of users’ preferences and then predict users’ future preferences and detect their possible preferences drift. However, both the forgetting curve model and the time decay model are forgetting strategies abstracted from the forgetting characteristics of all users, ignoring the personalized characteristics of each user.

Various time-varying preferences of users consist of stable long-term and volatile short-term ones. Long-term preferences are focused on relatively few topics and endure for a long time, while short-term ones are more varied but also more short-lived [10]. In order to quickly capture the changes in users’ preferences, the sliding time window model is also widely used to obtain users’ recent preferences. A longer window can be used to discover a user’s long-term preferences, while a shorter window used to discover a user’s short-term preferences. However, due to the diversity of the changes in users’ preferences, it is difficult to choose a time window of the appropriate size to capture all users’ long-term or short-term preferences.

In detecting user preferences drift, the sparsity of user data leads to the decline of the accuracy of the user preference model and the failure of drift detection, which is one of the most significant challenges researchers face. In order to minimize the problems caused by user data sparseness, many existing methods find similar user groups using clustering methods [11] and detect the preference changes of each user group. Then we can easily judge the drift of user preferences according to whether the preferences of the user group drift. However, judging user interest drift by user group interest drift can improve the accuracy of drift detection to a certain extent, which loses the judgment of personalized user interest drift. In addition, as time goes by and user behavior characteristics change, user groups also need to be adjusted constantly, which will significantly increase the algorithm’s complexity.

In this paper, we comprehensively analyze movie reviews and evaluations on the Douban platform to learn about user preferences at multi-time and multi-topic granularity, and design a hierarchy classification tree named HAT-tree to compressedly maintain user’s preferences and their weights at multi-topic and multi-time granularity. By mining the HAT-tree, we can quickly find user’s long-term and short term preferences, and the explicit and implicit preferences, thus simultaneously detect preference drift and distinguish drift types. Additionally, in order to adapt to different application scenarios, two coefficients $p$ and $q$ are used to adjust the importance of explicit and implicit preference when evaluating the weight of user preference.

The rest of this paper is organized as follows. Section 2 presents work related. Section 3 gives some definitions and proposes our method. Section 4 discusses the preference model at multi-time and multi-topic granularity. Section 5 proposes the method of mining the user’s primary and detecting preferences drift. Section 6 explains the experimental results. Section 7 summarizes the work of this paper.

2. Related works

User preference refers to the psychological tendency to explore a certain subject matter or to engage in a particular activity, usually described by topics. Therefore, the essence of preference drift detection is to find changes in the set of topics that express the user’s interests.

2.1 Concept drift detection

With the development of internet application technology, the quantity of data generated on the Internet shows an explosive growth trend. More and more learning algorithms are designed to classify, and to extract valuable information from the available data. However, as time goes by and hidden environmental changes occur, to a greater or lesser extent the inherent qualities of the data also change. Widmer and Kubat call such changes the concept drift problem [12]. When detecting concept drift, a model is usually used to predict the value of a target variable. The concept is said to drift if the target variable changes over time [13]. The drift detection algorithm can be classified by the approach adopted, of which we identify three: (a) instance selection or window-based approach, (b) weight-based approach, and (c) ensemble of classifiers approach.

The instance selection methods store the most appropriate data in memory and train a classifier for drift detection. Most of these methods use a sliding window model [15, 14] to maintain data within the most recent fixed-size time window and detect possible conceptual drift. The user chooses the size of the sliding window, and a small-sized window is suitable for finding and detecting the short-term concept drift, while a large-sized window is used to detect the long-term concept drift. In order to detect the concept drift within an adaptive window, some researchers have also proposed a size-varied window model [16].

The weight-based methods [17] assign a certain initial weight to the newly generated instance and gradually attenuate the weight of the instance as time passes by [16]. When the weight of an instance is less than a given value or equal to 0, it is deleted from the training data set. Similar to the instance selection methods based on the sliding window model, these methods consider that the new instances play a more important role in concept drift detection than the old ones.

At present, a classification method commonly used in concept drift detection algorithms includes SVM [17], decision trees [18], Bayesian classification [19], clustering [20], and logistic regression [21]. In order to improve the accuracy of the algorithm, many research works also use ensemble classifiers for concept drift detection, that is, they comprehensively analyze the output of multiple classifiers, and finally define a classifier according to the results of different classifications. In order to improve the adaptability of the algorithm, some ensemble classifiers methods also give each classifier a certain weight to adjust the impact of each classifier on the final classification result.

With the rapid development of big data technology, application layers in various industries are emerging, generating a large amount of business data. Due to the diversity of applications, the data in some applications (such as online learning, stock trading, Etc.) appears as a non-stationary dynamic data stream [23, 22]. One of the most critical tasks is to detect concept drift from these dynamic data streams in machine learning [24]. The research on recursive concept drift and concept evolution in the data stream also attracts researchers’ attention [23, 25]. Also, the multilevel imbalance of concept drift is a challenge for many real-world applications [26].

2.2 Preference drift detection

Since the advent of Web 2.0 culture, there as been an explosion of data on the internet. The traditional service model that relies on search engines for data retrieval cannot meet the needs of individual users and is replaced by a personalized recommendation service model based on the user’s preferences [28, 27]. A personalized recommendation system is able to understand a particular user’s needs and push the relevant resources by learning the user’s preferences.

Establishing a preference model for the user is one of the critical tasks of a personalized recommendation system. In recent years, scholars have proposed a variety of methods to establish user preference models according to their implicit and explicit footprints [29]. Li et al. [30] proposed a contextualized and personalized user preference model for location-associated social networks and used multiple logistic regression methods to extract and predict user preferences. Zheng et al. [31] analyzed microblog content to learn user hobbies, and proposed a time topic model to analyze user behavior and predict potential friends. In order to solve the problem of extracting user preference from social media, Kang et al. [32] map the social media information to the relevant categories of news media by using the Wikipedia knowledge system, thereby improving the accuracy of the user preference model.

However, as time goes by and the working and living environment changes, the user’s preferences may also change. One of the essential capabilities of a recommendation system is detecting drift in the user’s preferences and changing the recommendation strategy accordingly. In order to detect the drift in user preference over time and improve the quality of personalized services, David et al. [33] convert email content into themes using WordNet [34] ontology information, analyze the type of concept drift, and then filter the spam. Escoffeo et al. [35] proposed an algorithm to predict the mutations of concepts in the high-speed data stream. Demšar et al. [36] developed a monitoring system to detect conceptual drift on the data stream at multiple levels. In order to reduce the influence of preference drift on recommendation, Sun et al. [11] used a clustering method to find user preferences, and to detect preference drift they used a time impact factor matrix. They subsequently predicted user preference drift using a linear regression method. Zhang et al. [37] considered the uncertainty of time characteristics and user behavior, and used fuzzy set theory to construct a fuzzy user preference consistency model.

With the rapid popularization of intelligent mobile devices and the significant growth in mobile applications, it has become easier to obtain dual information of user behavior history and location trajectory simultaneously. Therefore, the recommendation of interest points [27, 38] based on location service has become a hot topic in current research and plays an increasingly important role in related applications.

3. Definitions

In this section, we will first present several definitions used in this paper and then propose the problem to be discussed.

3.1 Definition of user preference

Generally, an individual’s preference relates to a feeling or an emotion that may cause his/her attention to focus on a certain object, event, or process. While improving the quality of user services, user preference can also create added value for applications. Therefore, it is vital to discover and describe user preference and extract valuable information for real-world applications.

During a certain period of time, a user may be interested in multiple topics simultaneously. Thus a set of topics is customarily used to represent the user’s preferences. The words “topic” and “preference” are not distinguished unless otherwise specified in the following text. The number of times (or duration) that a user participates in activities categorized by a particular preference is thought to be the preference’s weight, indicating the degree to which the user is interested in the topic. Therefore, we define the user’s preference as follows.

.

(User preference) Given a time window $t$ , the preferences of a user can be represented as a set of tuples $\textit{UI}=\{<c_{i},w_{i}>|c_{i}\in C,i=1\to|\textit{UI}|\}$ , where $C$ denotes the universal set of topics that the users might be interested in, and $w_{i}$ is the weight of $c_{i}$ during the period of $t$ .

For example, the set $C=\{\textit{War},\textit{Vietnam War, Police},\ldots\}$ be the topics of all movies on DoubanMovie, and denotes the universal set of users’ preferences. In a time window $t$ , suppose a user has watched ten movies, among which five movies contain the topic “Vietnam War”, then $<\textit{Vietnam War},0.5>$ is one of the user’s preferences in time window $t$ .

Since the number of times (or total time) that users participate in the activities in different time windows may be variable, it is difficult to judge which topic the user is more interested in based only on the participation rate or duration. In order to compare the user’s preferences in different time windows, we first normalize the weights of the user’s preferences in each time window. Given the set of user’s preferences UI in the time window $t$ , the normalized weight $w_{i}$ of an preference topic $c_{i}$ ( $<c_{i},w_{i}>\in\textit{UI}$ ) can be calculated by the Eq. (1).

$\displaystyle w_{i}=\frac{f(c_{i})}{\sum_{j=1}^{|\textit{UI}|}{f(c_{j})}}$ (1)

where $f(c_{i})$ represents the number of times (or cumulative duration) the user participates in activities on $c_{i}$ in the time window $t$ , and $|\textit{UI}|$ is the size of set UI. Therefore, the weight of any preference $c_{i}$ in a time window will range in $(0,1]$ .

.

(Primary/secondary preference) Suppose UI is the preference set of a user in time window $t$ , given a weight threshold $w_{\theta}$ , the preference $c_{i}(c_{i}\in\textit{UI})$ is thought to be a primary preference of the user if $w_{i}\geqslant w_{\theta}$ , or else $c_{i}$ is a secondary preference.

Suppose $<\textit{Vietnam War},0.5>$ and $<\textit{Police},0.2>$ are two preferences of a user in a time window, then we think that $<\textit{Vietnam War},0.5>$ is one of the user’s primary preferences and $<\textit{Police},0.2>$ is a secondary preference if $w_{\theta}$ is set to be 0.3.

There are several techniques we can use to determine a value for the preference weight threshold $w_{\theta}$ . Firstly, a fixed value can be pre-selected and used as the threshold. Alternatively, we can arrange the preferences in UI by weight in descending order and select the weight of the $k^{th}$ preference as the threshold. A user’s preferences and their weights change as time passes, so it is impossible to pre-select a suitable threshold value of user preference weight. In this paper, we choose the weight of the user’s top- $k$ preference as the threshold. According to Definition 2, the primary preference set of a user in $t$ can be defined to be $\textit{PUI}=\{<c_{i},w_{i}>|c_{i}\in\textit{UI},w_{i}>w_{\theta}\}$ .

.

(Preference drift) Assume $t_{i}$ and $t_{j}$ are adjacent two time windows and that $t_{i}$ precedes $t_{j}$ , PUI ${}_{i}$ and PUI ${}_{j}$ are the two collections of user’s primary preferences in time window $t_{i}$ and $t_{j}$ respectively. It is considered that preference drift has occurred if $\textit{PUI}_{i}\neq\textit{PUI}_{j}$ , or some of the elements in PUI ${}_{i}$ and PUI ${}_{j}$ change their positions when they are ordered by weight.

Two cases of preference drift can be identified. (1) If one of the user’s primary preferences changes to a secondary one or changes in the opposite direction, we consider explicit drift in user preference to have occurred. (2) If a user keeps his/her preferences, but some preferences’ weights change, we consider implicit drift to have occurred. In most cases, a user’s preference drift contains both explicit and implicit drift simultaneously.

Suppose that PUI ${}_{i}=\{<\textit{Vietnam War},0.5>,<\textit{Police},0.4>,<\textit{Comedy},0.3% 5>\}$ denotes the user’s preferences in time window $t_{i}$ , and it changes to be PUI ${}_{i}=\{<\textit{Vietnam War},0.5>,<\textit{Romantic}$ , 0.42 $>$ , $<\textit{Police},0.32>\}$ in the next time window $t_{i+1}$ . By observing the change of the user’s preferences from the time window $t_{i}$ to $t_{i+1}$ , we can find that the primary preference “Comedy” becomes a secondary one. At the same time, the secondary interest “Romantic” becomes primary, so we say that the user’s preference has shifted explicitly. In addition, the weight order of the primary preference “Police” in the primary preference set changes, so the user’s preference also has an implicit drift.

4. Preference model with multi-granularity

4.1 Hierarchical classification tree

Generally speaking, before watching a movie, a potential viewer can make a preliminary judgment by considering, for instance, the genre, introduction, director, or actors of the movie and decide whether to watch it or not. In this paper, we extract keywords that accurately describe a movie’s plot from its introduction. Based on a semantic knowledge network similar to Wordnet [34] and Hownet [39], we analyze the semantics of the keywords and their interconnections and classify the keywords hierarchically.

In a hierarchical classification tree, as shown in Fig. 2a, the scope of the topic represented by a parent node contains the scope of the topics represented by all of its child nodes. The topics respectively represented by parent and child nodes could be thought of as the user’s parent preference and child preferences.

.

(Parent/Child preference) Suppose $\textit{node}_{i}$ and $\textit{node}_{j}$ are two nodes in a hierarchical classification tree, and $\textit{ui}_{i}$ and $\textit{ui}_{j}$ are the user preferences represented by $\textit{node}_{i}$ and $\textit{node}_{j}$ respectively. If $\textit{node}_{i}$ is the parent of $\textit{node}_{j}$ , then $\textit{ui}_{i}$ is thought to be the parent preference of $\textit{ui}_{j}$ , and $\textit{ui}_{j}$ is one of the child preferences of $\textit{ui}_{i}$ .

In the hierarchical classification tree of user’s preferences shown in Fig. 2, the node “Military” is the parent of “Vietnam War”. So we call “Military” the parent preference of “Vietnam War”, and “Vietnam War” one of the child preferences of “Military”. Obviously, among a user’s preferences, a parent preference is vague and thought of as the rough understanding of the preference. However, a child preference is subtle and thought of as the precise understanding of the preference. When pushing resources to users, it is necessary to understand the more precise preferences in order to obtain better recommendation effects.

4.2 Computation the preference weight

Usually, a user’s preference weight on a certain topic is synthetically determined by the weight of the user’s explicit and implicit preference for that topic. In the Douban movies, the number of times an individual watches films in specific topic categories reflects the degree to which the user is interested in those topics. The more watching actions in a given time window, the more the user is interested in the topic. In addition, people also watch movies of different topics in different behavioral ways and are willing to evaluate the movies they watch. These evaluations and behavioral characteristics expose the user’s personalized preferences explicitly or implicitly. A positive comment and a high rating means the user is interested in the movie. On the contrary, a negative comment and a low rating means that the user dislikes the movie.

Next, we will discuss the methods to calculate the degree to which a user is interested in a topic based on explicit and implicit information. After that, we propose a quantitative evaluation system to calculate the weights for different topics.

4.2.1 Explicit preference weights

In Douban Movies, a user can intuitively express his/her preferences in a movie by rating. The score reflects the degree to which the user is interested in the movie. Besides that, the user can also express his deep feelings about the movie by making a comment. Text analysis and language understanding technologies are needed to accurately extract the information embedded in the comment to evaluate the user’s opinion.

Douban movies allows the user to express his/her degree of interest on a five tier rating system, denoted as $r=\{0,1,2,3,4,5\}$ , with “1” indicating the lowest score, “5” indicating the highest score, and “0” meaning that the user has not given a rating on the movie. Similarly, the user’s comments can also be divided into five levels denoted as $c=\{0,1,2,3,5\}$ , with“1” means the poorest preference, “5” means the strongest preference, and “0” means the user has not posted a comment. Then the degree that a user is interested in a movie can be judged by comprehensively by analyzing the rating levels and the level of the user’s comment on the movie. Unfortunately, an actual evaluation record might lack either ratings or comments, or both. In addition, even though a user rates and reviews a movie simultaneously, the sentiments expressed by the rating and comment might be severely inconsistent. In this paper, two special situations are discussed to evaluate the levels of the user’s preferences expressed in ratings and comments:

•
When users evaluate a movie, they need to give at least a rating or a comment.
•
If the user gives a rating $r$ but not a comment, then the comment level $c$ is thought to be the same as $r$ . Similarly, it is assumed that $r=c$ if the user posts a comment but no rating.
•
If the user posts a comment and gives a rating on a movie simultaneously, and the rating level $r$ is more significant than the comment level $c$ , then $r$ is reduced to equal to $c$ because generally the user’s comment can more accurately reflect the user’s opinion on the movie.
•
If the user gives both a rating and a comment on a movie, and the rating level $r$ is not greater than the comment level $c$ , the actual values of $r$ and $c$ are used to evaluate the user’s preference weight.

User ratings and comments are two ways that user preference can be expressed explicitly. Therefore, we use the explicit preference index to describe the level of the user’s explicit preference in a movie comprehensively. Given a movie $m$ , and assuming that the levels of a user’s rating and comment on $m$ are $c_{m}$ and $r_{m}$ respectively, when we can learn the user’s explicit preference index on movie $m$ by comprehensively considering the user’s rating and comment. Let $ei_{m}$ denote the user’s explicit preference index on movie $m$ , then $ei_{m}$ can be calculated by Eq. (2).

$\displaystyle ei_{m}=\begin{cases}r_{m}/5,&\textit{if}\ c_{m}=0\\ \big{[}\min(c_{m},r_{m})+c_{m}\big{]}/10,&\text{else}\end{cases}$ (2)

According to the user’s explicit index, we define the weight of the user’s explicit preference on movie $m$ as the Eq. (3) below.

$\displaystyle ew_{m}=q^{ei_{m}}$ (3)

where $q(q\geqslant 1)$ is the coefficient to adjust the influence of explicit preference index on user preference weight.

According to the analysis mentioned above and the Eq. (2), the range of the user’s explicit preference index on movie $m$ can be determined to be [0.2,1]. Then the range of explicit preference weight on movie $m$ will be $[q^{0.2},q]$ . When $q$ is greater than 1, the explicit preference weight obtained by Eq. (3) will be greater than the explicit preference index, which is equivalent to amplifying the influence of the explicit preference index when calculating user preference weight. On the contrary, the value of explicit preference weight is always 1 regardless of the user’s explicit preference index value if $q$ is set to be 1.

Based on the above analysis, we can conclude that the weight of the user’s explicit preference is always no less than the explicit preference index. From this, we can also draw the following two exciting properties.

.

When the value of parameter $q$ is greater than 1, the higher a user’s explicit preference index on a movie is, the higher the weight of the user’s explicit preference in the movie topic is.

.

The greater the value of parameter $q$ , the more significantly a user’s explicit preference index impacts the user’s preference weight.
4.2.2 Implicit preference weight

Besides learning an individual’s explicit preferences from the comments, we can also determine the user’s implicit preferences by analyzing their movie-watching behavior. In general, we can learn about the user’s implicit preferences based on two general principles. First, if a user is more interested in a topic, he/she will watch more movies in that topic category. Secondly, if a user watches movies of a specific topic more frequently and regularly, we believe the user is more interested in the topic. Next, we learn the implicit preference by studying the user’s movie-watching behavior and discuss the method of calculating the weight of implicit preference.

Given two topics $c_{i}$ and $c_{j}$ in which a user is interested, suppose the number of movies the user watches on the two topics in the time window $t$ is $k_{i}$ and $k_{j}$ respectively. According to the two principles discussed above, the user is more interested in topic $c_{i}$ than $c_{j}$ if $k_{i}>k_{j}$ . On the contrary, if there is $k_{i}=k_{j}$ , the user is more interested in the topic with a higher frequency of movie-watching actions. In order to evaluate the influence of the user’s movie-watching behavior on the user’s implicit preference weight, we use the implicit preference index to comprehensively represent the number of movies the user watches and his/her movie-watching frequency. In a time window $t$ , if given the movie-watching log $L(c,t)$ on topic $c$ in $t$ , we can count the number of movies $k_{c}$ the user watches on $c$ and learn the frequency of the watching behavior. Let $ik_{c}$ be the implicit preference index of the user on $c$ in $t$ , then $ik_{c}=\rho(L(c,t))$ . Based on the analysis above, the range of $ik_{c}$ will be $(k_{c}-1,k_{c}]$ .

Generally, the total number of movies a user watches could differ in two time windows of the same size. So the preference weight of the user on two topics might be different even though the numbers of movies watched in the two topic categories are the same. In order to compare the user’s preferences in different time windows, we first use function $\varphi$ to normalize the user’s movie-watching index in each time window to the value range $(0,1]$ . Let $ik_{c}$ be the movie-watching index of a user on topic $c$ , there is $\varphi(ik_{c})\in(0,1]$ .

According to the normalized implicit preference index, we can easily differentiate the weights of the user’s implicit preferences on each topic. Then given a topic $c$ , we define the user’s implicit preference weight on $c$ as follows.

$\displaystyle iw_{c}=p^{\varphi(ik_{c})}=p^{\varphi(\rho(L(c,t)))}$ (4)

where $p(p\geqslant 1)$ is the coefficient to adjust the effect of the movie-watching behavior on the user’s preference weight. Obviously, the range of $iw_{c}$ is $(1,p]$ . Similar to the user’s explicit preference weight, a user’s implicit preference weight is the enlargement of the user’s normalized implicit preference index. Also, we can draw following two basic properties.

.

When the value of parameter $p$ is greater than 1, the higher a user’s implicit preference index on a topic, the higher the weight of the user’s implicit preference on the topic is.

.

The greater the value of parameter $p$ , the more significantly implicit preference impacts preference weight.

4.2.3 Integrated weight

We have discussed the methods to calculate the weight of the user’s explicit preferences based on the ratings and comments and the weight of implicit preferences based on the movie-watching behavior, respectively. Next, we calculate the integrated weight of the user’s preferences on a topic by considering both explicit and implicit preferences for that topic.

Without loss of generality, we can think that a user watches $n$ movies on the same topic if the user watches a movie on $n$ times. Suppose a user watches $k$ movies on topic $c$ in a time window, and $ms_{c}=\{m_{1},m_{2},\ldots,m_{k}\}$ is the set of movies watched, then the integrated weight of the user’s preference can be calculated by the following Eq. (5).

$\displaystyle w_{c}=iw_{c}\times\sum_{m_{i}\in ms_{c}}{ew_{m_{i}}}$ (5)

According to the previous Eqs (3)–(5) can be rewritten as follows Eq. (6)

$\displaystyle w_{c}=p^{\varphi(ik_{c})}\times\sum_{m_{i}\in ms_{c}}{q^{ei_{m_{% i}}}}$ (6)

According to the analysis of the Eqs (3) and (4), the value range of $w_{c}$ will be $(k_{c}q^{0.2},k_{c}pq]$ . Since the values of $p$ and $q$ are integers no less than 1, the inequality $pq\geqslant q^{0.2}\geqslant 1$ always exists.

The integrated weight of a user’s preference on topic $c$ calculated by Eq. (6) contains the weights of the user’s explicit and implicit preferences on $c$ . Moreover, the proportion of explicit preference and implicit preference in the integrated weight can be adjusted by changing the parameters $p$ and $q$ . By selecting different values for $p$ and $q$ , the Eq. (6) can flexibly calculate the weights of the user’s preferences that satisfy different application requirements as follows.

•

If $p=1$ , only the characteristic of the user’s explicit preference is considered without taking the user’s movie-watching behavior into account.

•

If $q=1$ , the user’s personalized characteristics such as ratings and comments on movies are ignored. The user’s explicit preference weight is described only by the number of movies the user watches.

•

If both $p$ and $q$ are equal to 1, then only the number of movies the user watches is taken into account when calculating the integrated weights of the user’s preferences.

•

If $q>p\geqslant 1$ , the user’s explicit preference plays a more crucial role than implicit preference when calculating the user’s integrated preference weight. On the contrary, the user’s implicit preference will play a more important role if $p>q\geqslant 1$ .

4.3 Tilted-time window

In a larger time window, a user might be interested in movies on a range topics. Of these preference topics, the user might be interested in some preferences for only a short time, while other interests may last a long time. In order to discover the user’s long-term and short-term preferences, we first split the user’s movie-watching logs into data segments according to a predefined time window called the unit-time window. Then we can learn the user’s short-term preferences in several contiguous data segments and the long-term preferences in the many successive data segments.

In order to be able to push the interested resources to the user precisely, it is necessary to accurately learn the user’s recent preferences, as well as long-term and short-term preferences. However, it is very costly to keep the weights of a user’s long-term preferences in each time-unit window, because it will take tens or even hundreds of counters. As shown in Fig. 1, we design a tilted-time window model to divide the time window by month into a series of slots, where the last three slots respectively represent the three most recent months, including the current month. The sizes of the time windows represented by the subsequent slots grow at an exponential rate, represent a quarter, a half year, one year, etc. If the user log is monthly divided into batches $B_{1},B_{2},\ldots,B_{n},\ldots$ , where $B_{n}$ is the most current batch and $B_{1}$ the oldest one. For any preference $c_{i}$ , let $w_{c_{i}}(r,r)$ denote the weight of $c_{i}$ in $B_{r}$ .

Figure 1.

Tilted-time window frame with logarithmic-like partition.

The user’s short-term preferences are variable, but the long-term ones are stable. Users can continuously maintain a short-term preference for a short time, perhaps covering only a few individual time windows. However, a long-term preference’s lifetime might cover tens or hundreds of time windows. In order to efficiently maintain the weight of the user’s long and short-term preferences, a time window model, as shown in Fig. 1 is designed to compress the weights of user’s preferences in the time windows with multi-time granularity.

Given two integers $r$ and $s$ and $s\geqslant r$ , let $B(r,s)=\cup_{k=r}^{s}{B_{k}}$ represent the batches from $B_{r}$ to $B_{s}$ , then $w_{c_{i}}(r,s)$ can be used to denote the weight of $c_{i}$ in $B(r,s)$ . Obviously, the weights of $c_{i}$ in the slots shown in Fig. 1 will be $w_{c_{i}}(n,n);w_{c_{i}}(n-1,n-1);w_{c_{i}}(n-2,n-2);$ $w_{c_{i}}(n-3,n-5);w_{c_{i}}(n-6,n-11),\ldots$ . As such, fine-grained time windows are used to keep the weights of the user’s recent short-term preferences, and coarse-grained time windows are used to keep the weights of the user’s long-term preferences in a compressed way. Using this model, the maintenance of preferences in a time window of up to 32 years requires only $\log_{2}(32\times 12)+1\approx 10$ slots instead of $32\times 12=384$ slots, which significantly cuts down on complexity.

4.4 Modeling user’s preferences

In Section 4, we have discussed the hierarchical classification tree used to express the hierarchical relationships of user preference topics. Moreover, a tilted-time window model is designed to compress the weights of the user’s preferences over the historical time window. Based on this, we will design a user preference model named hierarchical classification tree with tilted-time window (abbreviated as HAT-tree), which can dynamically maintain user preferences at multi-time and multi-topic granularity.

Figure 2.

An example of hierarchical classification tree with tilted-time window.

As shown in Fig. 2, in a HAT-tree, all nodes contain four fields: iName, pLink, and tLink, where iName registers which topic this node represents, pLink links to the parent node in the HAT-tree, and tLink links a tilted-time window table which is embedded into the node. In the time window table which is embedded in a tree node on the HAT-tree, there are several entries to store the weights of the user’s interest in the topic represented by the tree node. Each entry contains five fields: tSeqNo, max, min, Weight and stamp. tSeqNo registers a tilted-time window which is represented by the sequence number of the starting time-unit window, max and min register the maximum and minimum time window between two viewing actions of movies associated with the topic represented by iName. Weight registers the explicit weight of user’s preference in the tilted-time window, and stamp registers the last date the table is updated.

When building the user’s preference model using a HAT-tree, the user’s movie-watching behavior log is divided into batches named $B_{1},B_{2},\ldots,B_{i}$ by month firstly, where $B_{i}$ is the batch at the current month. Then the user’s preferences and weights in each month can be discovered by analyzing the data in the corresponding batch, which then are updated into the HAT-tree. Assuming that the HAT-tree already maintains the user’s preferences and their weights in the past batches $B_{1},B_{2},\ldots,B_{i-1}$ , the user’s preference and their weights in the current batch $B_{i}$ can be incrementally processed by Algorithm 2 as the new generated log in $B_{i}$ arrives.

[b] Incrementally updating HAT-tree

logs: newly generated log in current batch $B_{i}$ HT: the HAT-tree after $B_{i-1}$ is processed

Updated HAT-tree with logs being processed. Create a pointer tp to point the root of HT, set $\textit{UI}=\emptyset$ record lg in logs Let ui denotes the topics of movie $m$ , and $\textit{UI}=\textit{UI}\cup ui$ Calculate the explicit preference weight on $m$

topic $c$ in $u i$ Search the node iNode with the same name as $c$ in HT starting from root iNode is not found Create a node iNode to represent $c$ and add it into HT Initial the tilted-time window table linked to iNode Let pointer $t b$ point the tilted-time window table linked to iNode $l g$ is not covered by the time window in $t b$ Insert a new entry into $t b$ and merge the entries if necessary Update the fields in the current slot Let tp point to tp’s parent tp is not the root update the tilted-time window linked to tp

As shown in Algorithm 2, when the current batch of logs is fed into Algorithm 2, the log record is processed one by one, as shown on lines 2–21. As shown in lines 3–4, the algorithm records a user’s evaluation on movie $m$ , then extracts the topics $u i$ contained in $m$ , and calculates the weight of the user’s explicit preference for $m$ . As shown in lines 5–15, for any topic $c$ , it firstly searches the HAT-tree to find a node with the same name as $c$ . If such a node does not exist, it creates a new node, denoted as iNode, to represent topic $c$ and inserts it into the HAT-tree. At the same time, it is necessary to ensure that the relationship between the newly inserted node and its parent is consistent with the hierarchical relationship between the same concepts in the semantic knowledge network, such as Hownet. After that, as shown in lines 12–19, the current slot of the tilted-time window table linked to the node iNode is updated to record the weight of the user’s explicit preference calculated by the Eq. (3). If necessary, some short slots will merge to form a longer slot using the same method as that in. Additionally, concerning the hierarchical relationship between topics, if a user is interested in the topic represented by the node iNode, the user is considered to be interested in the topics represented by the ancestors of iNode. Therefore, as shown in lines 17–20, the ancestors of iNode will be updated to record the weight on the topics represented by those nodes. From the characteristics of the HAT-tree’s structure and its incremental updating, we can derive the following properties regarding user preferences.

.

On a HAT-tree, an ancestor node represents a coarser topic, while a child node represents a more delicate topic. In the tilted-time window table linked to a node in the HAT-tree, more delicate time windows are used to save recent preferences, but coarser time windows are used to keep historical preferences.

.

Supposing that Node ${}_{i}$ and Node ${}_{i}$ are two nodes in a HAT-tree, and Node ${}_{i}$ is one of the ancestor nodes of Node ${}_{j}$ , then the preference weight registered by Node ${}_{i}$ in any time window will always be no less than that registered by Node ${}_{j}$ .

5. Preference drift detection

This section will analyze the user’s historical log and build a user preference model with multi-time and multi-topic granularity. Based on the model, we analyze the trend of a user’s preference and detect the possible preference drift.

5.1 Mining primary preferences

The individual’s preferences are in constant flux. New interests develop from factors such as hobbies, recommendations by friends, and social trends, while the intensity of older interests fade. In any time window, an individual may be interested in a wide range of topics simultaneously. The weights of the preferences that a user is interested in may differ significantly. When recommending resources to the user according to his/her preferences, it is necessary to distinguish between primary and secondary preferences in order to improve the relevance and accuracy of the recommendations.

When a user evaluates the watched movie, the generated log is analyzed and processed by Algorithm 2, and the user’s preferences are incrementally updated to the HAT-tree. Therefore the user’s primary preferences in a given time window can be obtained by mining the user’s HAT-tree using Algorithm 5.1. As shown in line 4–8, all nodes on the HAT-tree are traversed, and the weights of the preferences represented by the nodes in given time window $T$ are calculated. After that the top-k primary preferences can be easily selected.

[ht] Mining top-k primary preferences

$k$ : number of primary preferences $t$ : given time window HT: the latest updated HAT-tree

the top-k primary preferences.

Get the set of tilted-time windows that cover $T$ , and denoted as sNum

Create a set of tuple $<\textit{topic, weight}>$ and denoted as UI

a topic $c$ represented by a node in HAT-tree Calculate the integrated weight on $c$ , denote it as $w_{c}$ Add $<c,w_{c}>$ into UI

Sort UI in descending order of weight UI is not null and flag is true flag = false $i\leftarrow 1$ $k$ $j\leftarrow i$ $k$ $\textit{UI}[i].C$ is an ancestor of $\textit{UI}[j].C$ in HA Remove $\textit{UI}[i]$ from UI flag $=$ true Output the first $k$ preferences in UI

As mentioned in Section 3.1, the user’s primary preferences can be distinguished from secondary ones by a given threshold $w_{\theta}$ or the number $k$ of the user’s desired primary preferences. Algorithm 5.1 demonstrates mining the top $k$ preferences from the HAT-tree according to the desired number of primary preferences. On a Hat-tree, the preference represented by an ancestor node always covers the preferences represented by its child nodes. According to Property 6, the weight of the preference represented by an ancestor node is always no less than the weights of the preferences represented by the child nodes. Therefore, the preference represented by the ancestor node is more likely to be selected as a primary preference than that represented by its child node. However, when pushing resources to the user, applications need to understand the user’s most accurate preferences. To achieve such a goal, as shown in lines 7–18, Algorithm 5.1 always tries to choose the primary preferences with the subtlest topic.

5.2 Predicting preference weight

Studying user preferences and pushing compatible resources is one of the essential tasks of the Douban movie review platform. In the previous section, we discussed mining the user’s primary preferences from a HAT-tree. However, these preferences are always changing. Some primary historical preferences may become less critical, and some secondary or newly generated preferences may become primary interests in the future. In order to detect the possible drift in a user’s preferences in advance, we need to not only mine the user’s current primary preferences from the HAT-tree, but also predict the user’s primary preferences of the future.

Normally, the historical weight of a user’s preference, regardless of its age, will affect the weight of his/her future preference. At the same time, we also believe that current preference weights have a much greater impact on the future weights than historical weights have. Based on these two understandings, a regression analysis method based on EMA (Exponential Moving Average) is presented to predict the weights of the user’s future preferences. Let $c$ be a preference of a user in time window $t_{i}$ , $w_{c}(t_{i})$ be its weight in $t_{i}$ , then the EMA of the weights of $c$ in $t_{i}$ , denoted as $\overline{w_{c}(t_{i})}$ , can be calculated by Eq. (7).

$\displaystyle\overline{w_{c}(t_{i})}=\begin{cases}w_{c}(1),&\text{if}\ t_{i}=1% \\ \alpha\times w_{c}(t_{i})+(1-\alpha)\times\overline{w_{c}(t_{i-1})},&\text{if}% \ t_{i}>1\end{cases}$ (7)

where $\alpha(0<\alpha<1)$ is a coefficient used to decay the historical weight. Obviously, the larger the value of $\alpha$ , the faster the influence of historical weights is decayed.

Simply, we can use $\hat{w}_{c}(t_{i+1})=\overline{w_{c}(t_{i})}$ to predict the weight of $c$ in time window $t_{i+1}$ . If $\overline{w_{c}(t_{i})}$ is replaced with its expansion expression, then we can get the following Eq. (8).

$\displaystyle\hat{w}_{c}(t_{i+1})=\sum_{j=1}^{i}{\alpha(1-\alpha)^{i-j}w_{c}(t% _{j})}$ (8)

When the user’s historical preference weights are known, the current time window’s predictive weight is determined by the coefficient $\alpha$ . In order to ensure the predicted weight is the best, as shown in Eq. (9), a cost function on $\alpha$ is defined to be the sum of the squared errors between the predictive weight and the actual weight.

$\displaystyle\textit{cost}(\alpha)=\frac{1}{2m}\sum_{i=1}^{m}{[\hat{w}_{c_{i}}% (t_{j+1})-w_{c_{i}}(t_{j+1})]^{2}}$ (9)

where $m$ is the size of the sample data.

The optimal solution of $\alpha$ can be solved to minimize the value of the cost function by using a Gradient descent-based approach. Furthermore, the optimal predicted weight of user’s preferences can be obtained by Eq. (8). Then we can get the collection of primary preferences in the future time window $t_{i+1}$ using the same approach as shown in lines 8–17 in Algorithm 5.1. At this point, we can detect possible drift in user preferences.

5.3 Preferences drift detection

As the previous discussion shows, user preferences may drift over time due to various factors. Applications like Douban movies always hope to capture the changes in user preferences to adjust their recommendation strategies on time in order to provide the best service. In this section, we present an efficient algorithm to detect the drift in user preferences.

Suppose PUI ${}_{i}$ is determined to be the collection of primary preferences in a current time window $t_{i}$ by mining the HAT-tree using Algorithm 5.1, and PUI ${}^{\prime}_{i+1}$ is the collection of primary preferences in $t_{i+1}$ predicted by the method present in Section 5, then the possible drift in user preferences can be detected by the following Eq. (10).

$\displaystyle f=\xi(\textit{PUI}_{i},\textit{PUI}^{\prime}_{i+1})+\zeta(% \textit{PUI}_{i},\textit{PUI}^{\prime}_{i+1})$ (10)

where $f$ is an indicator of user preference drift.

Function $\xi$ calculates the difference set of all topics in sets $\textit{PUI}_{i}$ and $\textit{PUI}_{i+1}$ . If the difference set is empty, function $\xi$ returns 0, indicating that user preference has not shifted; otherwise, it means that user preference has shifted explicitly. The function $\zeta$ firstly sorts the preferences in $\textit{PUI}_{i}$ and $\textit{PUI}_{i+1}$ respectively in order of their weights, and secondly compares the preferences of the two sets at the same position individually. Function $\zeta$ returns 1 if there is any inconsistency or returns 0 otherwise. We can conclude that the user’s preference has implicitly drifted if some preferences’ positions are inconsistent or no drift has occurred. Obviously, the value of $\zeta$ will be equal to 1 if $\xi$ returns 1, and the $\xi$ will return 0 if the value of $\zeta$ equals 0. However, it is impossible for the value of function $\xi$ to equal 0 and function $\zeta$ to return 1, because a user’s preferences cannot drift explicitly if none of his/her preferences has even drifted implicitly.

According to the possibility of combinations of $\xi$ and $\zeta$ , the values of the drift indicator $f$ have the following three possibilities, as shown in Table 1.

Table 1

Possibilities of the values of $\xi$ , $\zeta$ and $f$

$\xi$	$\zeta$	$f$	Meaning
0	0	0	No drift
0	1	1	Implicit drift
1	0	Invalid	N/A
1	1	2	Explicit drift

When it is necessary to detect the state of user preference drift, we only need to calculate the value of the drift indicator $f$ and then determine the type of user preference drift according to Table 1.

6. Performance evaluation

In this section, we will first introduce the experimental environment and then discuss the performance of the proposed method, and compare it with similar algorithms.

6.1 Experimental environment and datasets

All of the experiments were performed on a PC with a I7-8550U processor and 16 GB of main memory running on Win10. All programs were written in JDK 1.8.

Two datasets of movie reviews, Douban movie reviews, and MovieLens, were used in the experiment. The former data set, obtained from the Douban movie platform (movie.douban.com), contains user ratings and reviews, while the latter, obtained from the GroupLens platform (grouplens.org/datasets/movielens), only contains user ratings, and no comments.

Douban Movie reviews contains about 1.86 M comments and ratings on 149 k movies given by 398 users from July 31, 2005, to March 2, 2019. According to the annual average number of comments, the Douban Movie reviews platform is divided into three datasets named DS1, DS2, and DS3 respectively, and the annual average in these groups is less than 1000, greater than or equal to 1000 but less than 2000, and not less than 2000 respectively. Table 2 describes the data characteristics of the three datasets.

Table 2
Distribution characteristics of the data sets

Dataset	Users	Movies	Comments	Topics	Comments/topic
DS1	350	52109	45.56M	7.10M	6.42
DS2	37	66666	6.12M	9.14M	6.70
DS3	11	133398	2.39M	0.35M	6.78

As shown in Table 3, two datasets MoiveLens-1M and MoiveLens-10M [40] were also used to compare the proposed method to similar methods. Compared with the dataset of Douban Movie Reviews, the dataset of MovieLens lacks movie introductions and user comments. Therefore, two simplified treatments are applied when conducting the proposed algorithm on MovieLens. First, it is not necessary to extract finer granularity interest topics from the movie’s introduction. Second, the value of $C_{m_{i}}$ was fixed to be 5 when calculating the weight of the user’s interests using Eq. (2).

Table 3

Introduction to the datasets of MovieLens

Dataset	Users	Movies	Ratings	Time spans
MovieLens-1M	6040	3900	1000209	1038 days
MovieLens-10M	71567	10681	10000054	5109 days

6.2 Performance evaluation

This section first introduces the parameters used in the performance evaluation experiments. Then performs a series of experiments on the data set to evaluate the influence of the various parameters on the algorithm’s performance and analyzes the experimental results.

6.2.1 Experiment parameters

In the performance evaluation experiments, we set the values of each parameter of the algorithm in the value range as shown in Table 4, and arbitrarily combined the values of the parameters. Nearly 780,000 experiments were conducted on data set DS1, DS2, and DS3, respectively.

Table 4
Description of the parameter values

Parameter	Value range	Step	Number of values
$\bm{p}$	$1.1\sim 2.0$	0.05	20
$\bm{q}$	$1.1\sim 2.0$	0.05	20
$\bm{n}$	(1,3,6,12,24)	–	5
$\bm{k}$	$5\sim 50$	5	10
$\bm{\alpha}$	$0.02\sim 0.08$	0.02	4
	$0.1\sim 0.9$	0.10	9

6.2.2 Performance evaluation on

p

and

q

According to the analysis in Section 4.2, two factors affect the weight of a particular preference: the user’s movie-watching behavior and comments, which represent implicit and explicit preference respectively. Among these the user’s explicit preference, manifested in the comments made, is the more influential factor. Two parameters, $p$ and $q$ , are respectively used to adjust the influence of the user’s movie-watching behavior and movie evaluations on the weight of preference. Firstly, a series of experiments are conducted to understand parameters $p$ and $q$ on the algorithm’s performance.

Figure 3.

The correctness of drift detection as $p$ and $q$ vary.

As shown in Fig. 3, when the value of the parameter $p$ is about 1.15, the algorithm achieves near-optimal accuracy on all three data sets. From there, with the increase or decrease of the value of $p$ , the algorithm’s accuracy decreases rapidly. Compared with parameter $p$ , the proposed method is less sensitive to changes of parameter $q$ . As shown in Fig. 3, the difference in the value of $q$ has little influence on the algorithm’s accuracy obtained in the two low density data sets, DS1 and DS2. For data set DS3 with high data density, as the value of $q$ increases, the correctness of the algorithm increases in a multistep pattern; however, when the value of $q$ is greater than 2.0, the correctness of the algorithms obtained on the three data sets decreases significantly. The algorithm generally increases in accuracy as $q$ increases above 1.5, but remains less than 2.0.

When changing the value of parameters $p$ and $q$ respectively, the apparent difference in the trends of algorithm correctness is due mainly to the following three factors. Firstly, as shown in Table 1 and Fig. 4, a majority of topics are individually represented by very few viewing actions on the hat-tree. When Eq. (7) is used to calculate user preference weight, the importance of explicit preference is not fully reflected. When the $q$ value increases, the algorithm can find the part of the user’s actual preference that is viewed less frequently, thus improving the algorithm’s accuracy. When the $p$ value increases, it equates to reducing the influence of the user’s actual preference on the preference weight, which leads to a decrease of the algorithm’s correctness. Secondly, in the process of gradually increasing the value of $q$ , the influence of preference weight changes significantly because the change of the $q$ value is small, so the correctness of the algorithm increases with the value $q$ . Thirdly, when the $q$ value is large, many topics with few views are wrongly regarded as primary preferences, which dramatically reduces the correctness of the algorithm.

6.2.3 Performance evaluation on

n

When constructing the hierarchical classification tree of user preferences, we adopt a multi-granularity time window to maintain the weight history of each user preference, which allows us to distinguish between long-term and short-term preferences. Then, both short and long-term preference drift could be detected. We subsequently performed a series of experiments to verify the accuracy of the proposed method in detecting long and short-term preference drift.

Figure 4.

The correctness of drift detection as $n$ and $k$ vary.

In the experiments, we find the user’s long-term or short-term preferences by changing the size of the predictive time window $n$ . As shown in the Fig. 4, when the prediction time window increases, the accuracy of drift detection decreases rapidly. Our analysis of the potential causes shows that there are mainly two: first, with the increase of the forecast window size, the accuracy of the forecast will inevitably decline; Second, the algorithm only predicts the weight of historical preference topics and then determines whether they are primary preferences, and cannot obtain newly generated preference topics in the future time window. In addition, we also observe that only when $n=1$ , the datasets in order of drift detection correctness, from high to low, is DS3, DS2, and DS1. Otherwise, the order of datasets is the inverse. As introduced above, users were divided into three groups according to the annual average number of comments, which constituted three data sets. By analyzing each user’s topic tree of preference and topic rights in the three data sets, we find that users in data set DS3 pay the most attention to their preference areas in a month on average, followed by users in data set DS2 and DS1, respectively.

6.2.4 Performance evaluation on

k

As discussed in Section 3.1, the top- $k$ preferences with the highest weights are regarded as the user’s primary preferences. Compared with secondary preferences, primary preferences represent the user’s most essential preferences in a time window. Moreover, primary preferences are stable and do not drift significantly over time. A series of experiments were also conducted to evaluate the influence of parameter $k$ on the correctness of user preference drift detection, and the experimental results are shown in Fig. 4. As the value of $k$ increases, some topics that do not represent the user’s true preferences are mistakenly thought to be significant. This leads to a decline in drift detection accuracy because the user’s preference for these topics is unstable and likely to drift.

The experimental results also show that the algorithm’s correctness on data set DS3 is always greater than that on data set DS2 and DS1 irrespective of the value of $k$ . The reason is that the users in DS3 watched more movies and posted more comments per time unit than the users in DS1 and DS2, which makes it easier for the algorithm to learn actual user preferences. Moreover, when the value of $k$ is small, the algorithm’s correctness on three data sets decreases rapidly as $k$ increases. When the value of $k$ is greater than 20, the algorithm’s correctness on three data sets changes little with the increase of $k$ . The main reason is that the threshold for being a primary preference is high when the value of $k$ is small. Only a few high-weight topics are selected as the user’s primary preferences, which are real and stable preferences. As the value of $k$ increases, some topics with low weight will be chosen as primary preferences, and the correctness of the algorithm decreases rapidly. As $k$ increases and becomes greater than 20, the user’s primary preference threshold will be smaller. Many topics with even lower weight may be regarded as primary preferences. Meanwhile, some of the original unstable preferences will change to be stable ones because their weights are much larger than the primary preference threshold as the threshold decreases. Thus the correctness of the algorithm will not continue to decrease.

6.2.5 Performance evaluation on $\alpha$

Predicting user preference is one of the most pivotal steps in preference drift detection. Generally speaking, a user’s preferences may drift over time, and when predicting future preferences, the influence of recent preferences is more important than the influence of historical preferences. Therefore, when predicting the weight of preference in the future time window, the algorithm uses the decay factor $\alpha$ to gradually attenuate the weight of historical preference.

The value of $\alpha$ is mainly determined by the changing trend of the time series for the weight of historical preference. Generally, a smaller $\alpha$ can obtain a more accurate prediction when the time series trend is stable. Otherwise, a larger $\alpha$ is required. A series of experiments was conducted to verify the influence of decay factor $\alpha$ on algorithm correctness. As shown in Fig. 5, the influence of $\alpha$ on algorithm correctness is slightly different in the three data sets. By analyzing the sequence of monthly comments and calculating their variance in each of the three data sets, we found that the average variance of DS1 was smaller than the other two data sets.

6.2.6 Accuracy on explicit and implicit preference drift detection

We have discussed that preference drift can be classified as either implicit drift or explicit drift in Section 5.3. Implicit drift refers only to weight changes in the user’s primary preference set, while the elements in the set remains unchanged. These represent moderate changes in the user’s preferences. On the other hand, explicit drift refers to changes in elements of the user’s primary preference set, representing a sharper change in the user’s preference.

In order to evaluate the algorithm’s ability to detect explicit and implicit preference drift, we also performed a set of experiments to analyze the correctness of each user’s explicit and implicit drift in the three sets of data. The average accuracies of explicit and implicit preference drift in the three data sets are shown in Table 5.

Table 5
The accuracy on explicit and implicit preference drift detection

Dataset	Explicit preference	Implicit preference
DS1	75.0%	66.1%
DS2	76.0%	70.6%
DS3	88.2%	79.4%

Figure 5.

The correctness of the proposed method as $\alpha$ varies.

As shown in Table 5, for the three data sets, the accuracy of explicit drift detection is higher than that of implicit drift detection. The user’s primary preferences represent the most important and most stable set of preferences. Generally speaking, the user’s primary preferences are not expected to drift significantly in a short-term time window. However, the weight order of the primary preferences may change slowly over time. Therefore, the correctness of explicit preference drift detection is often takes priority over that of implicit preference drift detection. In addition, the experimental results show that both explicit and implicit drift detection in the DS3 data set is more accurate than for the other two sets. The main reason is that the more movies a user watches and the more reviews the user posts, the easier it is to analyze and learn the user’s true preferences.

6.3 Comparison analysis

In this section, a series of experiments on MovieLens [40] were conducted to compare the proposed method with several similar methods, including two UDD methods [37] and the DTDM [11] method. The internationally accepted measurement metric MAE(Mean Absolute Error) was used in the compare experiments, and the equation to calculate MAE is as follows.

$\displaystyle\textit{MAE}=\frac{\sum_{i=1}^{n}{|p_{i}-r_{i}|}}{n}$ (11)

where $p_{i}$ is the predicted rating on a topic, $r_{i}$ is the actual rating, and $n$ is the total number of the predicted topics. The earliest 80% of the experimental data was used for model training and the most recent 20% for testing.

Some experiments were conducted on the dataset MovieLens-1M to compare the proposed method with the two UDD methods [37], and the experimental results are shown in Table 6. The MAE of the proposed algorithm is slightly poorer than that of the CF-based UDD method but clearly better than that of the Content-based UDD method.

Table 6

MAEs of four methods on MovieLens-1M

Method	MAE
Content-based UDD	0.6948
CF-based UDD	0.6705
Proposed method	0.6734

Both UDD methods construct a fuzzy user preference model based on fuzzy set theory and build the relationship between the movies and the user’s ratings by fuzzifying the movie attributes. In addition, an explicit user rating relationship can be obtained by discarding the noise data beyond given confidence. The content-based UDD method constructs the fuzzy relationship between movies and user’s preferences by calculating the similarity between the movie content and the user comments. However, The data set provides little information, so it is not easy to determine a user’s exact practical preferences. In order to solve the problem of low accuracy caused by the sparsity of the dataset, the CF-based UDD method collaboratively recommends movies to the user based on the similarities between users and so improves the accuracy of prediction. However, the CF-Based UDD method needs to establish the collaboration matrix between the movies and the users and calculate the similarity between the users, which is very taxing and time consuming. While the proposed method can effectively learn the user’s actual preferences by analyzing the explicit and implicit preferences of other users. The importance of the user’s recent preferences can be emphasized by using the Exponential smoothing technique which serves to attenuate the weight of historical preferences. Therefore, the proposed algorithm has an obvious advantages compared with the Content-based UDD method. Although the correctness of the method in this paper is slightly lower than that of the CF-based UDD method, the expansibility and algorithm efficiency of the CF-based UDD method are far lower than that of our method.

Second, the proposed method is also compared to the DTDM method [11] by conducting experiments on both MovieLens-1M and MovieLens-10M. In this experiment, the parameters of the proposed method are the same as those in the first comparison experiment, except that the user’s data in the last five-time windows is used as the test data. The mean absolute errors (MAEs) of two methods on the datasets of MovieLens-1M and MovieLens-10M are shown in Table 7. When the comparative experiments are conducted on MovieLens-1M, the proposed method is obviously better than the DTDM method, but it is slightly inferior to the DTDM method when the experiments are performed on MovieLens-10M.

Table 7

MAEs of two methods on MovieLens-1M and MovieLens-10M

Method	MovieLens 1M	MovieLens 10M
DTDM method	0.7240	0.6440
Proposed method	0.7014	0.6463

A clustering method is used in the DTDM method to find similar user groups in MovieLens, and the user’s interest in the future can be predicted based on the similarities of the users in a group. The correctness of the DTDM method is greatly affected by the characteristics of the data and the correctness of the clustering results. the data in MovieLens is very sparse, which will lead to the low accuracy of the DTDM method. Additionally, after a significant change in the user set or a significant drift in their interests, the users need to be re-clustered to discover the new user interest groups. Therefore, the DTDM method is not suitable for situations where incremental detection drift in user interest is required. In comparison, the proposed method analyzes the explicit and implicit features of user interests and build a user interest model at multiple topic granularities and multiple time granularities. As time passes by, user interests and their weights can be incrementally saved to the model. When it is needed, the weight history of user interest can be quickly obtained from the model, and its weight in the future can ben forecasted by a prediction model based on EMA. In addition, the proposed method can also detect the drift in users’ long-term and short-term interests.

7. Conclusion

On the Douban review platform, users rate and review the movies they watch. By analyzing the user’s movie-watching behavior, comments and ratings, we learn their explicit and implicit preferences, and design a hierarchical classification tree named HAT-tree to maintain these preference characteristics at multi-topic and multi-time granularity. Based on HAT-tree, we mine the user’s primary preferences in continous time window, and then detect possible preference drift. The proposed algorithm can discover the user’s long-term and short-term preferences and detect explicit as well as implicit drift. Experimental results show that this method performs well and has apparent advantages over other similar algorithms.

Footnotes

Acknowledgments

This work was partly supported by the National Natural Science Foundation of China (No. 61962024, 61772245, 61866014, 61806075), and the Jiangxi Province Department of Education Fund under grant (No. GJJ190258, GJJ190254).

References

Zareie

Sheikhahmadi

and Jalili

, Identification of influential users in social networks based on users’ interest, Information Sciences 493 (2019), 217–231.

Zarrinkalam

Fani

and Bagheri

, Extracting, mining and predicting users’ interests from social networks, in: Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, Paris, France, 2019, pp. 1407–1408.

Zarrinkalam

Piao

and Faralli

Bagheri

, Mining user interests from social media, in: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, Virtual, Event, Ireland, 2020, pp. 3519–3520.

Nagar

Khemka

and Arora

, Concept drift detection for multivariate data streams and temporal segmentation of daylong egocentric videos, in: Proceedings of the 28th ACM International Conference on Multimedia, Seattle, WA, USA, 2020, pp. 1065–1074.

Paudel

and Eberle

, An approach for concept drift detection in a graph stream using discriminative subgraphs, ACM Transactions on Knowledge Discovery from Data 14(6) (2020), 70:1–70:25.

Zhou

Zhang

Wang

Ren

Fan

Zhu

and Gai

, Search-based user interest modeling with lifelong sequential behavior data for click-through rate prediction, in: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, Virtual, Event, Ireland, 2020, pp. 2685–2692.

Zarrinkalam

Fani

and Bagheri

, Social user interest mining: Methods and applications, in: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Anchorage, AK, USA, 2019, pp. 3235–3236.

Yan

Sang

and Xu

, Mining cross-network association for youtube video promotion, in: Proceedings of the 22nd ACM international conference on Multimedia, Orlando, Florida, USA, 2014, pp. 557–566.

Sang

Mei

and Xu

, Activity sensor: Check-in usage mining for local recommendation, ACM Transactions on Intelligent Systems and Technology 6 (2015), 1–24.

10.

Sang

and Xu

, A probabilistic framework for temporal user modeling on microblogs, in: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, Melbourne, Australia, 2015, pp. 961–970.

11.

Sun

and Dong

, Dynamic model adaptive to user interest drift based on cluster and nearest neighbors, IEEE Access 5 (2017), 1682–1691.

12.

Widmer

and Kubat

, Learning in the presence of concept drift and hidden contexts, Machine Learning 23 (1994), 69–101.

13.

Sun

Yin

Liu

and Guo

, Meta-learned specific scenario interest network for user preference prediction, in: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, Virtual, Event, Canada, 2021, pp. 1970–1974.

14.

Liao

and Wang

, Rival learner algorithm with drift adaptation for online data stream regression, in: Proceedings of the 2018 International Conference on Algorithms, Computing and Artificial Intelligence, Sanya, China, 2018, pp. 1–5.

15.

Chen

, Mining top-k frequent patterns over data streams sliding window, Journal of Intelligent Information System 42 (2014), 111–131.

16.

Chen

Shu

Xia

and Deng

, Mining frequent patterns in a varying-size sliding window of online transactional data streams, Information Sciences 215 (2012), 15–36.

17.

Sun

Fujita

Chen

and Li

, Dynamic financial distress prediction with concept drift based on time weighting combined with adaboost support vector machine ensemble, Knowledge-Based Systems 120 (2016), 4–14.

18.

Jankowski

and Cyganek

, Learning decision trees from data streams with concept drift, Procedia Computer Science 80 (2016), 1682–1691.

19.

Nguyen

Liew

and Wang

, Variational inference based bayes online classifiers with concept drift adaptation, Pattern Recognition 81 (2018), 280–293.

20.

Song

Zhang

and Lu

, A fuzzy kernel c-means clustering model for handling concept drift in regression, in: Proceedings of the 2017 IEEE International Conference on Fuzzy Systems, Naples, Italy, 2017, pp. 1–6.

21.

Nguyen

Venkatesh

and Phung

, One-pass logistic regression for label-drift and large-scale classification on distributed systems, in: Proceedings of the 2016 IEEE 16th International Conference on Data Mining, Barcelona, Spain, 2016, pp. 1113–1118.

22.

Straat

Abadi

Kan

Göopfert

Hammer

and Biehl

, Supervised learning in the presence of concept drift: a modelling framework, Neural Computing and Applications 34, 2022, 1–18.

23.

Zheng

and Yu

, Semi-supervised classification on data streams with recurring concept drift and concept evolution, Knowledge-Based Systems 215(1) (2021), 106749.

24.

Korycki

and Krawczyk

, Concept drift detection from multi-class imbalanced data streams, in: Proceedings of the 37th IEEE International Conference on Data Engineering Chania, Greece, 2021, pp. 1068–1079.

25.

Walker

D.M.

Zaitouny

and Corrêa

D.C.

, On using the modularity of recurrence network communities to detect change-point behaviour, Expert Systems with Applications 176 (2021), 114837.

26.

Liu

Zhang

Ding

Liu

and Zhu

, A comprehensive active learning method for multiclass imbalanced data streams with concept drift, Knowledge-Based Systems 215 (2021), 106778.

27.

Cai

Wen

and Yang

, A coarse-to-fine user preferences prediction method for point-of-interest recommendation, Neurocomputing 422, (2021), 1–11.

28.

Chen

Yan

and Yang

, Modeling dynamic user preference via dictionary learning for sequential recommendation, IEEE Transactions on Knowledge and Data Engineering 34(11) (2021), 1–13.

29.

Cao

and Caverlee

, What are you known for: Learning user topical profiles with implicit and explicit footprints, in: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, Shinjuku, Tokyo, Japan, 2017, pp. 743–752.

30.

Sagl

Mburu

and Fan

, A contextualized and personalized model to predict user interest using location-based social networks, Computers Environment and Urban Systems 58 (2016), 97–106.

31.

Zheng

Song

and Bao

, A temporal-topic model for friend recommendations in chinese microblogging systems, IEEE Transactions on Systems, Man, and Cybernetics: Systems 45(9) (2015), 1245–1253.

32.

Kang

and Lee

, Modeling user interest in social media using news media and wikipedia, Information Systems 65 (2017), 52–64.

33.

Ruano-Ordǎs

Fdez-Riverola

and Méndez

R.J.

, Concept drift in e-mail datasets: An empirical study with practical implications, Information Sciences 428 (2018), 120–135.

34.

Piao

and Breslin

, User modeling on twitter with wordnet synsets and dbpedia concepts for personalized recommendations, in: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, Indianapolis, Indiana, USA, 2016, pp. 2057–2060.

35.

Escovedo

Koshiyama

Abs da Cruz

and Vellasco

, DetectA: Abrupt concept drift detection in non-stationary environments, Applied Soft Computing 62(2017), 119–133.

36.

Demsar

and Bosnic

, Detecting concept drift in data streams using model explanation, Expert Systems with Applications 92 (2017), 546–559.

37.

Zhang

and Lu

, Fuzzy user-interest drift detection based recommender systems, in: Proceedings of the 2016 IEEE International Conference on Fuzzy Systems, Vancouver, BC, Canada, 2016, pp. 1274–1281.

38.

Sang

Tai

Cheng

Shang

J.S.

Chu

and Zhang

, Online meta-learning for poi recommendation, GeoInformatica 27 (2023), 61–76.

39.

Niu

Xie

Liu

and Sun

, Improved word representation learning with sememes, in: Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, Vancouver, Canada, 2017, pp. 2049–2058.

40.

Harper

and Konstan

, The movielens datasets, ACM Transactions on Interactive Intelligent Systems 5 (2015), 1–19.

Multi-granularity user interest modeling and interest drift detection

Abstract

Keywords

1. Introduction

2. Related works

2.1 Concept drift detection

2.2 Preference drift detection

3. Definitions

3.1 Definition of user preference

.

.

.

4.1 Hierarchical classification tree

.

4.2 Computation the preference weight

4.2.1 Explicit preference weights

.

.

.

.

.

.

5.1 Mining primary preferences

5.2 Predicting preference weight

6.1 Experimental environment and datasets

Table 2 Distribution characteristics of the data sets

6.2.1 Experiment parameters

Table 4 Description of the parameter values

6.2.5 Performance evaluation on α

6.2.6 Accuracy on explicit and implicit preference drift detection

Table 5 The accuracy on explicit and implicit preference drift detection

Footnotes

Acknowledgments

References

Table 2
Distribution characteristics of the data sets

Table 4
Description of the parameter values

6.2.5 Performance evaluation on $\alpha$

Table 5
The accuracy on explicit and implicit preference drift detection