CN114925294B - Position prediction system and method based on graph enhancement time-space model - Google Patents

Abstract

A point of interest recommendation system and method based on graph-enhanced time-space model. For the next point of interest recommendation task, the geographical information of the points of interest and the user-point of interest interaction information are used to capture the complex geographical relationship between the points of interest. At the same time, the user's historical interaction sequence is used to capture the user's specific time dependency. After obtaining the time and space dependency, the attention mechanism is used to aggregate and model the user's interest in the points of interest. Finally, the complete recommendation model predicts the user's probability of visiting the point of interest at the next moment based on the user's interest score for the point of interest obtained by modeling, and generates a recommendation result for the user.

Description

Position prediction system and method based on graph-enhanced time-space model

Technical Field

The present invention relates to a technology in the field of neural network applications, specifically a future point of interest recommendation system based on a graph enhanced time-space model.

Background Art

Existing next POI recommendation systems often only use the geographical distance between adjacent POIs as the input of the model and are unable to model the complex geographical influences between POIs.

After searching the prior art, it was found that the Chinese patent document number CN114021011A was published on 20220208, disclosing a next point of interest recommendation method based on the self-attention mechanism. First, the sequence information, spatiotemporal information and context-related dynamic social relations are integrated and modeled; secondly, two parallel channels (long/short-term channels) are designed to model the long/short-term preferences of users and their friends, and the self-attention mechanism is used to capture the long-distance dependency between any two historical check-ins of the user; finally, the user's preference score for the point of interest at the next moment is predicted. However, it is difficult for the prior art to reasonably capture the time dependency of the user's visit history. Specifically, when modeling long-term and short-term preferences, the prior art only uses the vanilla attention mechanism to model the mutual influence between the representations of the points of interest in the user sequence, and there is no design for modeling the time information of the access sequence, and the influence of the time dependency in the sequence on the user's interest is not considered. The technology lacks the modeling of the important geographical influence of the transfer relationship of the point of interest. As a physical location that exists in fact, the point of interest has a strong contextual relationship. The technology lacks this part of the design. The modeling method of the distance relationship of the technology needs to be optimized. The L2L graph constructed by this technology directly uses geographic distance as the edge weight, without reasonable regularization and numerical normalization. In the specific implementation, the problem of large numerical differences causing the model to be difficult to converge may occur; this technology lacks reasonable integration of temporal information and spatial information. This technology directly uses geographic information as the original input for sequence modeling. Since the distribution of geographic information and temporal information is generally different, this structure serializes two different types of information together and it is difficult to capture them reasonably.

Summary of the invention

In view of the above-mentioned deficiencies in the prior art, the present invention proposes a point of interest recommendation system based on a graph-enhanced time-space model, which extracts information from the semantic graph of point of interest by utilizing graph embedding technology to obtain high-order spatial dependencies between points of interest, and adaptively integrates the user's temporal dependency and the spatial dependency between points of interest by utilizing LSTM and attention mechanism.

The present invention is achieved through the following technical solutions:

The present invention relates to a method for recommending points of interest based on a graph-enhanced time-space model, comprising:

Step 1) Data preprocessing: Unify the format of access records and perform simple cleaning on the records. Generate a historical access sequence for each user in chronological order.

Step 2) Constructing a semantic graph of interest points: According to the coordinate information of all interest points and all user-interest point interaction records, a semantic graph based on geographic distance and a semantic graph based on transfer relationship are constructed to respectively save the distance relationship and transfer relationship between interest points.

Step 3) construct and train a graph-enhanced time-space model, which includes: a spatial dependency module, a time dependency module and a space-time dependency aggregation module, wherein: the spatial dependency module first uses an embedding operation to obtain an embedding vector of the distance relationship and the transfer relationship of the interest point, and then performs a graph embedding operation on the two interest point semantic graphs constructed in step 2) to obtain the spatial dependency representation of the corresponding interest point; the time dependency module first uses an embedding operation to obtain the embedding representation of the interest point itself, and then uses LSTM to model the user's historical access sequence, and uses the last output of the sequence as the user's time dependency information; the space-time dependency aggregation module aggregates the above-obtained interest point spatial dependency information and the user's time dependency information according to the attention mechanism, first uses the time dependency information as the query of the attention mechanism, and aggregates the spatial dependency representation of the interest point in the sequence as the key and value of the attention mechanism, and adds the result obtained after the aggregation with the spatial dependency of the interest point to obtain the user-specific spatial dependency, and then adds the time dependency and the user-specific spatial dependency to obtain the user's preference score for the interest point.

The spatial dependency module uses a Gaussian kernel function to model distance: Where: dist( _li , _lj ) represents the spatial distance between two points of interest, represents the Gaussian kernel function, and the transfer relationship refers to the direct transfer relationship between interest points, that is, the number of times the interest point _lj is visited after l _i in all user sequences.

The threshold Δd of the Gaussian kernel function is preferably 1 km.

The embedding operation is: e _l =Ev _l , where e _l is the learned embedding representation, E is the learnable embedding matrix, and v _l is the one-hot representation of the interest point.

The time-dependent module is calculated through the LSTM process: T _1t =σ(W _x1 x _t +σ(Δt _t W _t1 )+b ₁ ), T _2t =σ(W _x2 x _t +σ(Δt _t W _t2 )+b ₂ ), i _t =tanh(W _i x _t +W _i h _t-1 +b _i ), o _t =tanh(W _o x _t +W _o h _t-1 +b _o ), Among them: W _cx , W _x1 , W _x2 , _Wi , W _o are trainable parameter matrices, and b _c , b ₁ , b ₂ , _bi , b _o are trainable bias items. is the dot product, tanh is the tanh function, and _xt is the vector representation of the point of interest at the previous moment.

The attention mechanism is specifically: Where W ₁ , W ₂ , W ₃ are parameter matrices, Q, K, V are queries, keys and values in the mechanism, and d is the dimension size of the vector.

Step 4) Generate recommendation results: In the recommendation stage, the user's dynamic preferences at the next time point generated by the model are used to calculate the user's visit probability to the point of interest. Points of interest with high visit probability are selected and recommended to the user.

The probability is calculated as: Wherein, exp represents an exponential function with base e, and _ru,i represents the preference score of user u for point of interest i in step 3).

Technical Effects

The present invention takes the time difference between adjacent access records as the input of LSTM, constructs a semantic graph based on the transfer relationship and explicitly models the time dependency of the access history. On two evaluation datasets, the spatial dependency captured by the semantic graph of the point of interest and the space-time dependency aggregation module both improve the recommendation results of the model to a certain extent.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 is a flowchart of a recommendation system based on a graph-enhanced time-space model;

Figure 2 is a semantic graph of interest points based on distance relations;

Figure 3 is a semantic graph of interest points based on transfer relations;

FIG4 is a schematic diagram of the graph enhanced time-space model structure.

DETAILED DESCRIPTION

As shown in FIG1 , this embodiment relates to a method for recommending points of interest based on a graph-enhanced time-space model, including:

Step 1) Data preprocessing: The user's visit to the point of interest will generate corresponding records, that is, <u, l, time>, where u∈U represents the user and l∈L represents the point of interest. Each point of interest has its specific geographic information <l, lon, lat>, which means that the longitude and latitude coordinates of the point of interest l are lon and lat respectively. First, these interaction records need to be cleaned to remove some possible noise, such as deleting points of interest that have been visited less than 5 times in the entire data set, and deleting users with less than 5 visit records. For the records generated by each user, sorting according to the timestamp can form the access sequence H ^u ={<l ₁ , t ₁ >, <l ₂ , t ₂ >..., <l _n , t _n >} of user u.

Step 2) Constructing a semantic graph of interest points, including:

2.1) Constructing the distance graph: As shown in Figure 2, the distance graph is a weighted undirected graph G _D = (V, _ED , _AD ), which is used to capture the distance relationship between interest points. In the figure, V is the set of all interest points, _ED ∈ V x V is the set of edges in the graph, and when the distance between two interest points _li and _lj is less than the set threshold Δd, there is an edge between the two nodes, that is, e _ij ∈ _ED . _AD ∈ R ^NxN is a weight matrix that stores the weight of each edge. Where: dist( _li , _lj ) represents the spatial distance between two interest points. represents the Gaussian kernel function. In this embodiment, the threshold Δd is set to 1 km.

2.2) Constructing the transition graph: As shown in Figure 3, the transition graph is a weighted directed graph _GT = (V, _ET , _AT ), which is used to capture the transition relationship between interest points, where: V is the set of all interest points, _ET∈VxV is the set of edges in the graph, and for the same user's access sequence, if the interest point _lj appears directly after _li , then there is a transition relationship between the two nodes, that is, there is an edge between the corresponding nodes. _AT∈R ^NxN is a weight matrix that stores the weight freq( _li , _lj ) of each edge, that is, the number of times the interest point _lj is visited after _li in all user sequences.

Step 3) Build and train the graph-enhanced time-space recommendation model, including:

3.1) Spatial dependency modeling, that is, modeling the spatial dependency between interest points from a global perspective: Based on the two interest point semantic graphs constructed in the previous step, two spatial dependencies are captured: distance-based spatial dependency and transfer-based spatial dependency. First, an embedding operation is used to obtain the embedding vector of each interest point l _i , that is, the distance-based embedding vector Vector based on propagation capability Vector based on receptive capacity in: is a trainable embedding matrix, k is the dimension of the embedding vector, _{and vi} is the one-hot encoding of _li . Then, the three embedding vectors are optimized through graph embedding technology to represent the spatial dependencies of interest points.

The graph embedding technology mentioned above refers to:

① The conditional probability that there is an edge (i.e., direct connection) between any two interest points l _i and l _j in the distance graph G _D Where: exp(·) represents an exponential function with base e. The empirical probability that there is an edge (i.e., direct connection) between two interest points l _i and l _{j is} in represents the (i, j)-bit element of the weight matrix _AD ; the optimization function of embedding d _i is obtained according to the conditional probability and the empirical probability. In order to reduce the computational complexity, this embodiment omits some constant terms and adopts a negative sampling strategy to obtain the optimization function Wherein: σ is the sigmoid function, NEG(i) is the negative sampling set for l _i , and the number of negative sampling is set to 5 in this embodiment.

② For the transfer graph _GT , the propagation capability and the acceptance capability are calculated for each interest point, where the propagation capability represents the ability of the interest point to transfer users to other interest points, and the acceptance capability represents the ability of the interest point to accept users to transfer in. Similarly, this embodiment calculates the conditional probability that there is an edge between any two interest points _li and _lj in the transfer graph _GT . And the empirical probability in: Represents the (i, j)th element in the weight matrix; optimization function of transmission capacity and reception capacity By optimizing the above two functions, three optimized embedding representations d, g, and h are obtained to represent the spatial dependency relationship between interest points.

3.2) Temporal dependency modeling, i.e., modeling the temporal dependency of user access sequences: First, an embedding operation is used to obtain the low-dimensional vector representation _xi of each point of interest, and the points of interest in the user's historical access sequence are converted into corresponding embedding representations. Among them: _xi represents the embedded representation of the interest point itself, represents the embedding matrix, _vi represents the unique hot representation of the interest point; LSTM is used to model the time dependency, and LSTM satisfies: T _1t =σ(W _x1 x _t +σ(Δt _t W _t1 )+b ₁ ), T _2t =σ(W _x2 x _t +σ(Δt _t W _t2 )+b ₂ ), i _t =tanh(W _i x _t +W _i h _t-1 +b _i ), o _t =tanh(W _o x _t +W _o h _t-1 +b _o ), Among them: W _cx , W _x1 , W _x2 , _Wi , W _o are trainable parameter matrices, and b _c , b ₁ , b ₂ , _bi , b _o are trainable bias items. is the dot product, tanh is the tanh function, and _xt is the vector representation of the interest point at the previous moment. The present invention takes the last output of LSTM as the time dependency, that is, _hn = LSTM ( _x1 , ..., _xn ).

3.3) Time-space dependency aggregation: For each point of interest in the user's historical sequence, the attention mechanism is used to aggregate their spatial dependencies as follows: Where: _Wd1 , _Wg1 , _Wd2 , _Wg2 , _Wd3 , _Wg3 are trainable parameter matrices, softmax represents the softmax function, and the geographical impact _Id , It of the user visiting the point of interest _lj is obtained by _adding the geographical dependence of _lj on all points of interest in the historical visit sequence, specifically: Among them: _gi , _gi , _gi are the distance-based, propagation-based, and receptive-capability-based vector representations corresponding to the interest points, and | ^Hu | represents the sequence length.

Step 4) Generate recommendation results: Based on the temporal dependency and aggregated spatial dependency obtained above, this embodiment can calculate the preference of user u for point of interest l _j The larger the preference score r _u , _{j is} , the greater the probability that the user will visit l _j at the next time point. That is, l _j should be recommended to the user.

This embodiment verifies the system recommendation effect on the Gowalla and Foursquare datasets. Both datasets are collected from the real world and are widely used in experimental verification related to the next point of interest recommendation.

The parameters in the experiment were set as follows: the embedding vector dimension of the item was set to 64, the length of the user's access sequence was set to 20, and when the length was less than 20, the left end of the sequence was padded with 0 until the sequence length became 20. The mini-batch gradient descent optimization method was used and the batch size was set to 128. During training, the Adam optimizer was used and the learning rate was set to 0.001.

Evaluation method: In order to evaluate the performance of the recommendation system disclosed by this method, it is compared with a variety of existing next point of interest recommendation technologies in experimental verification. When evaluating the recommendation effect, the recall ratio (abbreviated as Recall) and the normalized discounted cumulative gain (abbreviated as NDCG) are used as evaluation indicators. This embodiment specifically compares the performance of the disclosed system with the existing technology in Recall@5, Recall@10, NDCG@5, and NDCG@10. On the Foursquare dataset, the Recall@5, Recall@10, NDCG@5, and NDCG@10 values of the disclosed system are 0.2713, 0.3416, 0.2019, and 0.2246. On the Gowalla dataset, the Recall@5, Recall@10, NDCG@5, and NDCG@10 values of the disclosed system are 0.2146, 0.2791, 0.1541, and 0.1749.

Compared with other existing technologies, the performance indicators of this system are improved in the following aspects: for the Recall@5 indicator, it is improved by 9.21% and 13.96% on the two tasks; for the HR@10 indicator, it is improved by 5.72% and 11.73% on the two tasks; for the NDCG@5 indicator, it is improved by 10.2% and 13.22% on the two tasks. For the NDCG@10 indicator, it is improved by 8.29% and 6.51% on the two tasks.

The present invention also uses ablation experiments to verify the technical effects of the spatial dependency captured by the semantic graph and the spatial-temporal dependency aggregation module. The present invention first removes the spatial dependency captured by the semantic graph on the basis of the complete model. For the Recall@10 indicator, the ablated model decreases by 18.38% and 19.27% on the two tasks. Secondly, the present invention removes the spatial-temporal dependency aggregation module on the basis of the complete model. For the Recall@10 indicator, the ablated model decreases by 1.14% and 1.12% on the two tasks.

In summary, the present invention utilizes high-order complex geographical influences between points of interest to provide additional effective basis for the next point of interest recommendation. The present invention uses the geographical distance information and transfer information of the points of interest to respectively construct two semantic graphs of points of interest: the semantic graph based on geographical distance contains the distance information between points of interest. Generally speaking, users are more inclined to visit points of interest that are close to the current location. The semantic graph based on transfer information contains the transfer relationship between points of interest. For example, after visiting a bar, users are less likely to go to their workplace. The present invention utilizes a spatial dependency modeling module to extract relevant high-order geographical influences, and combines the user's time dependency to generate recommendation results. The present invention is an end-to-end architecture that does not require manual definition or extraction of a particularly large number of features; the architecture also has good scalability.

The above-mentioned specific implementation can be partially adjusted in different ways by those skilled in the art without departing from the principle and purpose of the present invention. The protection scope of the present invention shall be based on the claims and shall not be limited by the above-mentioned specific implementation. Each implementation scheme within its scope shall be subject to the constraints of the present invention.

Claims (6)

1. A method for recommending points of interest based on a graph-enhanced time-space model, comprising: Step 1) Data preprocessing: unify the format of access records and perform simple cleaning on the records; generate a historical access sequence for each user in chronological order; Step 2) Constructing a semantic graph of interest points: constructing a semantic graph based on geographic distance and a semantic graph based on transfer relationship based on the coordinate information of all interest points and all user-interest point interaction records, respectively used to save the distance relationship and transfer relationship between interest points, including: 2.1) Constructing distance graph: The capped distance graph is a weighted undirected graph G _D = (V, _ED , _AD ), which is used to capture the distance relationship between interest points. In the graph, V is the set of all interest points, _ED ∈ VxV is the set of edges in the graph, and when the distance between two interest points _li and _lj is less than the set threshold Δd, there is an edge between the two nodes, that is, e _ij ∈ _ED ; _AD ∈ R ^NxN is a weight matrix that stores the weight of each edge. Where: dist(l _i ,l _j ) represents the spatial distance between two points of interest; represents the Gaussian kernel function; 2.2) Constructing the transition graph: The transition graph is a weighted directed graph _GT = (V, _ET , _AT ), which is used to capture the transition relationship between interest points, where: V is the set of all interest points, _ET∈VxV is the set of edges in the graph, and for the same user’s access sequence, if the interest point _lj appears directly after _li , then there is a transition relationship between the two nodes, that is, there is an edge between the corresponding nodes; _AT∈R ^NxN is a weight matrix that stores the weight freq( _li , _lj ) of each edge, that is, the number of times the interest point _lj is visited after _li in all user sequences; Step 3) construct and train a graph-enhanced time-space model, which includes: a spatial dependency module, a time dependency module and a space-time dependency aggregation module, wherein: the spatial dependency module first uses an embedding operation to obtain an embedding vector of the distance relationship and the transfer relationship of the interest point, and then performs a graph embedding operation on the two interest point semantic graphs constructed in step 2) to obtain the spatial dependency representation of the corresponding interest point; the time dependency module first uses an embedding operation to obtain the embedding representation of the interest point itself, and then uses LSTM to model the user's historical access sequence, and uses the last output of the sequence as the user's time dependency information; the space-time dependency aggregation module aggregates the above-obtained interest point spatial dependency information and the user's time dependency information according to the attention mechanism, first uses the time dependency information as the query of the attention mechanism, and aggregates the spatial dependency representation of the interest point in the sequence as the key and value of the attention mechanism, and adds the result obtained after the aggregation with the spatial dependency of the interest point to obtain the user-specific spatial dependency, and then adds the time dependency and the user-specific spatial dependency to obtain the user's preference score for the interest point, specifically including: 3.1) Spatial dependency modeling, that is, modeling the spatial dependency between interest points from a global perspective: Based on the two interest point semantic graphs constructed in the previous step, two spatial dependencies are captured: distance-based spatial dependency and transfer-based spatial dependency. First, an embedding operation is used to obtain the embedding vector of each interest point l _i , that is, the distance-based embedding vector Vector based on propagation capability Vector based on receptive capacity in: is a trainable embedding matrix, k is the dimension of the embedding vector, _{and vi} is the one-hot encoding of _li . Then, the three embedding vectors are optimized by graph embedding technology to represent the spatial dependency of interest points. 3.2) Temporal dependency modeling, i.e., modeling the temporal dependency of user access sequences: first, an embedding operation is used to obtain a low-dimensional vector representation x _i of each point of interest, and the points of interest in the user's historical access sequence are converted into corresponding embedding representations; Among them: _xi represents the embedded representation of the interest point itself, represents the embedding matrix, _vi represents the unique hot representation of the interest point; LSTM is used to model the time dependency, and LSTM satisfies: T _1t =σ(W _x1 x _t +σ(Δt _t W _t1 )+b ₁ ), T _2t =σ(W _x2 x _t +σ(Δt _t W _t2 )+b ₂ ), i _t =tanh(W _i x _t +W _i h _t-1 +b _i ), o _t =tanh(W _o x _t +W _o h _t-1 +b _o ), Where: W _cx , W _x1 , W _x2 , _Wi , W _o are trainable parameter matrices, b _c , b ₁ , b ₂ , _bi , b _o are trainable bias terms; ⊙ is the dot product, tanh is the tanh function, x _t is the vector representation of the point of interest at the previous moment; the last output of LSTM is taken as the time dependency, that is, h _n =LSTM(x ₁ ,…,x _n ); 3.3) Time-space dependency aggregation: For each point of interest in the user's historical sequence, the attention mechanism is used to aggregate their spatial dependencies as follows: Where: _Wd1 , _Wg1 , _Wd2 , _Wg2 , _Wd3 , _Wg3 are trainable parameter matrices, softmax represents the softmax function, and the geographical impact _Id , It of the user visiting the point of interest _lj is obtained by _adding the geographical dependence of _lj on all points of interest in the historical visit sequence, specifically: Where: d _i , g _i , h _i are the distance-based, propagation-based, and receptive-capability-based vector representations of the interest points, and |H ^u | represents the sequence length; Step 4) Generate recommendation results: In the recommendation stage, the user's dynamic preferences at the next time point generated by the model are used to calculate the user's visit probability to the point of interest; and points of interest with high visit probability are selected and recommended to the user. 2. According to the method for recommending points of interest based on graph-enhanced time-space model in claim 1, it is characterized in that the threshold Δd of the Gaussian kernel function is 1 km. 3. According to the method for recommending points of interest based on graph-enhanced time-space model in claim 1, it is characterized in that the embedding operation is: e _l =Ev _l , wherein e _l is the learned embedding representation, E is the learnable embedding matrix, and v _l is the one-hot representation of the point of interest. 4. The method for recommending points of interest based on a graph-enhanced time-space model according to claim 1, wherein the attention mechanism is specifically: Where W ₁ , W ₂ , W ₃ are parameter matrices, Q, K, V are queries, keys and values in the mechanism, and d is the dimension size of the vector. 5. The method for recommending points of interest based on graph-enhanced time-space model according to claim 1, wherein the probability is calculated as follows: Wherein, exp represents an exponential function with base e, and _ru,i represents the preference score of user u for point of interest i in step 3). 6. The method for recommending points of interest based on a graph-enhanced time-space model according to claim 1, wherein the graph embedding technology refers to: ① In the distance graph _GD , there is an edge between any two interest points l _i and l _j , that is, the conditional probability of direct connection Where: exp(·) represents an exponential function with base e; there is an edge between two interest points l _i and l _j , that is, the empirical probability of direct connection in Represents the (i, j)-bit element of the weight matrix _AD ; the optimization function of embedding d _i is obtained according to the conditional probability and empirical probability. To reduce the computational complexity, the optimization function Where: σ is the sigmoid function, NEG(i) is the negative sampling set for l _i ; ② For the transfer graph _GT , calculate the propagation capacity and acceptance capacity for each interest point, where the propagation capacity represents the ability of the interest point to transfer users to other interest points, and the acceptance capacity represents the ability of the interest point to accept users to transfer in; calculate the conditional probability that there is an edge between any two interest points _li and _lj in the transfer graph _GT And the empirical probability in: Represents the (i, j)th element in the weight matrix; optimization function of transmission capacity and reception capacity By optimizing the above two functions, three optimized embedding representations d, g, and h are obtained to represent the spatial dependency relationship between interest points.