CN109977324B - A method and system for mining points of interest - Google Patents

Abstract

The invention discloses a method and system for mining interest points. Clustering interest points are constructed according to an original trajectory data set, a user-location bipartite graph is obtained according to the clustered interest points, and then converted into a corresponding association matrix. Adjust the privacy budget that characterizes the size of user privacy security

to set the noise

, the noise

Add each item in the correlation matrix, obtain the perturbation correlation matrix, use the perturbation correlation matrix as input, and use the HITS algorithm to generate a user recommendation list and a location recommendation list for query users to query points of interest; the present invention ensures user privacy and security. At the same time, the user's points of interest are mined, and a high-accuracy point of interest query service is provided for the user of the point of interest query.

Description

A method and system for mining points of interest

technical field

The invention relates to a point of interest mining method and system, belonging to the technical field of data mining.

Background technique

With the rapid growth of mobile positioning devices and the widespread use of high-speed wireless networks, location-based services (LBS), including location-based social networking, location-based advertising, and location-based information sharing, are widely used. The track is composed of a series of location information represented by <longitude, latitude, timestamp> triples, which contain information such as the user's moving destination, moving path, and moving mode. The service backend can provide users with accurate and useful point-of-interest recommendation services by collecting large-scale historical trajectory data of different mobile users, processing and mining, for example, where are the top 10 points of interest in a city, and which shopping The center is most popular in this area, and which users frequently visit this restaurant, etc.

However, the exposure of sensitive trajectory data may lead to the leakage of private information. Specifically, location information represented as two-dimensional coordinates is usually associated with semantic meaning, such as bars, shopping malls, or hospitals, etc. For example, if an attacker infers that the user is associated with a hospital, the user's health status can be known. Therefore, privacy-preserving trajectory mining is a challenging problem. However, the research on the restriction mechanism of privacy protection shows that there is a conflict of interests between data mining and privacy protection, and the privacy protection processing of data will inevitably reduce the effect of data mining. Therefore, how to balance the interests of the two, while protecting private information, and improving the effect of data mining as much as possible is a further problem to be solved urgently.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a method and system for mining points of interest, so as to solve the above-mentioned defects or one of the defects caused in the prior art.

To achieve the above object, the present invention adopts the following technical solutions to realize:

In a first aspect, the present invention provides a method for mining points of interest, the method comprising the following steps:

Step 1: construct a clustered interest point dataset according to the user trajectory dataset, construct a user-location bipartite graph according to the clustered interest point dataset, and convert the user-location bipartite graph into an association matrix;

获取扰动关联矩阵；其中Δf为全局敏感度，ε为隐私预算，所述隐私预算ε满足隐私阈值要求；Step 2: Add Laplace-distributed noise to each item in the correlation matrix

Obtain the perturbation correlation matrix; where Δf is the global sensitivity, ε is the privacy budget, and the privacy budget ε meets the privacy threshold requirement;

Step 3: According to the correlation matrix and the HITS algorithm, obtain the user recommendation list and location recommendation list without noise; according to the disturbance correlation matrix and the HITS algorithm, obtain the user recommendation list and location recommendation list with noise added;

Step 4: Calculate the matching degree according to the user recommendation list and location recommendation list without noise, and the user recommendation list and location recommendation list with noise added; if the matching degree satisfies the set matching degree threshold, go to step 5; if the matching degree If the set matching threshold is not met, go to step 2, and reset the noise by adjusting the global sensitivity Δf and privacy budget ε

Step 5: Save the noise-added user recommendation list and the location recommendation list whose matching degree satisfies the matching degree threshold to the database for query by the query user.

Further, the method further includes collecting trajectory data including user location information and time information corresponding to the location information, and constructing a user original trajectory data set.

Further, the method for calculating the matching degree MR(A) includes:

Among them, ori(A) represents the user recommendation list and location recommendation list without noise, noi(A) represents the user recommendation list and location recommendation list with noise added, and A represents the user group and location group in the user-location bipartite graph. union.

The method of constructing a clustered interest point dataset includes the following steps:

constructing a point of interest dataset according to the user's original trajectory dataset; the data in the point of interest dataset includes user information, user's location information, and time information corresponding to the location information;

The DBSCAN clustering algorithm is used to perform cluster analysis on the data set of interest points to form multiple clusters, each cluster is represented by the position information of the center point of the cluster, and the ID of the center point is used as the unique identifier of the cluster, and The frequency of each user accessing the cluster is counted, and a clustered interest point dataset is constructed.

The data structure of the user-location bipartite graph ULBG=(U, L, E), where U={u _i |1≤i≤m} represents the user node group, and L={l _j |1≤j≤n} represents the location node group, E={(u _i , l _j , w _ij )|1≤i≤m, 1≤j≤n} represents the access set of the edge; wherein, _ui represents the Id of user i, and l _j represents The Id of point of interest j, w _ij represents the frequency of user i visiting point of interest j.

The correlation matrix includes |U| rows and |L| columns, and the elements in the correlation matrix are the frequency w _ij of the user i visiting the interest point j.

In another aspect, the present invention provides a system for mining points of interest, the system comprising:

The first acquisition module is used to construct a clustered interest point data set according to the user trajectory data set, construct a user-location bipartite graph according to the clustered interest point data set, and convert the user-location bipartite graph into an association matrix;

获取扰动关联矩阵；其中Δf为全局敏感度，ε为隐私预算，所述隐私预算ε满足设定隐私阈值要求；The second acquisition module: used to add noise that obeys Laplace distribution to each item in the correlation matrix

Obtain the perturbation correlation matrix; where Δf is the global sensitivity, ε is the privacy budget, and the privacy budget ε meets the requirement of setting the privacy threshold;

The third obtaining module: used to obtain the user recommendation list and location recommendation list without noise according to the correlation matrix and the HITS algorithm; according to the disturbance correlation matrix and the HITS algorithm, obtain the user recommendation list and location recommendation list with noise added;

Data processing module: It is used to calculate the matching degree according to the user recommendation list and location recommendation list without noise, and the user recommendation list and location recommendation list with noise added; if the matching degree satisfies the set matching degree threshold, it is transferred to the storage module for processing ; If the matching degree does not meet the set matching degree threshold, transfer to the second acquisition module for processing, and reset the noise by adjusting the global sensitivity Δf and the privacy budget ε

Storage module: used to save the noise-added user recommendation list and location recommendation list satisfying the matching degree to the database for query by the query user.

Further, the system further includes a building module for collecting trajectory data including user location information and time information corresponding to the location, and constructing a user's original trajectory data set.

The first acquisition module also includes a first building module for constructing a clustered interest point dataset, and the building module includes:

The second building module: for constructing a point of interest data set according to the user's original trajectory data set; the data in the point of interest data set includes user information, user location information and time information corresponding to the location information;

The third building module is used to perform cluster analysis on the data set of interest points using the DBSCAN clustering algorithm to form multiple clusters, each cluster is represented by the position information of the center point of the cluster, and the Id of the center point is used as the The unique identification of the cluster, and the frequency of each user accessing the cluster is counted to construct a clustered interest point dataset.

The invention provides a method and system for mining interest points, which converts the user's original trajectory data set into a user-position bipartite graph, and then converts it into a corresponding correlation matrix, and adds Laplace noise to obtain a perturbation correlation matrix. Relevance matrix, using the HITS algorithm to generate user recommendation lists and location recommendation lists that meet the security and usability requirements for query users to query.

Description of drawings

Fig. 1 is a kind of trajectory data migration diagram provided according to the embodiment of the present invention;

2 is a flowchart of a method for mining points of interest provided according to an embodiment of the present invention;

3 is a structural diagram of a user-location bipartite graph provided according to an embodiment of the present invention;

FIG. 4 is a service architecture diagram of a point of interest mining provided according to an embodiment of the present invention.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings. The following examples are only used to illustrate the technical solutions of the present invention more clearly, and cannot be used to limit the protection scope of the present invention.

This embodiment provides a method for mining points of interest. Referring to FIG. 1 and FIG. 2 , the method includes the following steps:

Step 1: Data Acquisition:

Collect user trajectory data and construct the user's original trajectory data set. The original data set contains the trajectory data of multiple users; each user's trajectory data is composed of multiple <longitude, latitude, timestamp> triples, representing the user's location information and the time information corresponding to the location information; the user trajectory data is discretely captured by the GPS device.

Step 2: Build a user-location bipartite graph and convert the user-location bipartite graph into an association matrix:

Step 21: Build the POI Dataset

According to the user's original trajectory data set constructed in step 1, a data set of interest points is constructed; it should be clear that not all the captured position points of the user are points of interest, and the points of interest represent the time spent within a distance threshold D _t Spatial area greater than or equal to the time threshold T _t ; and some position points in the user's original trajectory data set are only captured when the user passes by, and do not belong to points of interest. Therefore, it is necessary to filter the trajectory data in the user's original trajectory data set to select interest The method for selecting interest points includes: when the kth trajectory data {(x _k , y _k , t _k )|a≤k≤b} satisfies

t _b -t _a ≥T _t (3)

, the k-th trajectory data (x _k , y _k , t _k ) is called point of interest data, where x _k represents the longitude coordinates of the user’s position k at time t _k , and y _k represents the user’s position k at time t _k latitude coordinates of the user's location at time t a; x _a represents the longitude coordinates of the user's location at time t _a , y _a represents the latitude coordinates of the user's location at time t _a ; x _b+1 represents the user's location at time t _b The longitude coordinates of the location at ₊₁ , y _b+1 represents the latitude coordinates of the user's location at time t _b+1 , t _a represents the time corresponding to the starting point a of the user's original trajectory data, and t _b represents the collection The time corresponding to the end position b of the user's original trajectory data;

Step 22: Build a clustered interest point dataset

The DBSCAN algorithm is used to perform cluster analysis on the set of interest points obtained according to step 21, each formed cluster is represented by the location information of the center point of the cluster, and the Id of the center point is used as the unique identifier of the cluster. The location of the cluster center point is associated with a corresponding geographic tag, including tourist attractions and shopping centers; the frequency of each user's visit to the cluster is counted, and the frequency of the user's visit to the cluster indicates the user's access to the point of interest corresponding to the cluster. Frequency, used to construct a clustered POI dataset, where the clustered POI includes user ID, POI ID, and frequency information of users visiting POI;

Steps 21 and 22 are the data pre-cleaning process to obtain the data set to be processed.

Step 23: Build a user-location bipartite graph;

According to the access relationship between the user and the location, a user-location bipartite graph is generated. Refer to Figure 3 for the structure of the user-location bipartite graph. The arrow pointing to the location by the user indicates that the user visits the location, and the weight on the arrow indicates that the user has multiple times. Visit the location, the higher the frequency of visits, the higher the user's recommendation for the location;

The data structure of the user-location bipartite graph ULBG=(U, L, E), where U={u _i |1≤i≤m} represents the user node group, and L={l _j |1≤j≤n} represents the location Node group, E={(u _i , l _j , w _ij )|1≤i≤m, 1≤j≤n} represents the access set of the edge, _ui represents the Id of user i, and l _j represents the point of interest j Id, w _ij represents the frequency of user i visiting point of interest j.

Step 24: Get the Correlation Matrix

Convert the user-location bipartite graph into an association matrix M[i][j]; the association matrix includes |U| rows and |L| columns, and each item in the matrix is the edge weight between user i and interest point j , the edge weight is equal to the frequency w _ij of user i visiting point of interest j, if user _ui has never visited location l _j , set w _ij to 0.

Step 3: Obtain the perturbation correlation matrix

条记录；It should be clear that differential privacy techniques can ensure that the published statistics do not depend on the existence of a record in the data, thus achieving the effect of protecting privacy. What needs to be protected in this solution is the user-location bipartite graph. According to the user-location bipartite graph data structure constructed in step 23, an edge (u _i , l _j , 1) in the graph is equivalent to a record, and the user-location bipartite graph CCP contains

Records;

获取扰动关联矩阵

This embodiment uses the Laplacian mechanism to ensure differential privacy, and the implementation method is to add noise that obeys the Laplacian distribution to each item in the correlation matrix obtained according to step 24

Get the perturbation correlation matrix

Among them, Δf is the global sensitivity, which is used to measure the maximum impact of a single record change in the clustered interest point dataset. The global sensitivity Δf satisfies the set global sensitivity threshold; ε is the privacy budget, and the privacy budget ε is used to measure the The security of user privacy protection, the privacy budget ε meets the privacy threshold requirements;

Step 4: Obtain the user recommendation list and location recommendation list with added noise

A good Hub page will point to many good Authority pages, and many good Hub pages will point to a good Authority page. By analogy, the user of the user-location bipartite graph constructed according to step 23 is regarded as the Hub page, and the position is regarded as the Hub page. For the Authority page, use the HITS algorithm to score each user and location. Users with higher scores indicate more experienced users who are more reliable in recommending points of interest, and locations with higher scores indicate more worth visiting points of interest;

In the solution provided in this embodiment, the user-location bipartite graph conversion obtained according to step 24 is used as input, and the HITS algorithm is used to obtain the user recommendation list and location recommendation list without noise; The perturbation correlation matrix is used as the input, and the HITS algorithm is used to obtain the user recommendation list and location recommendation list with added noise; the user recommendation list includes users in ascending order of their corresponding ratings, and the location recommendation list includes locations.

Step 5: Usability Assessment

In order to ensure the privacy protection of users and the accuracy of point of interest recommendation results, the usability evaluation of the produced recommendation list is carried out:

According to the above steps, the disturbance correlation matrix is obtained by adding noise to the correlation matrix, and the noise-added user recommendation list and location recommendation list are obtained according to the perturbation correlation matrix, so as to achieve the purpose of protecting the privacy of users who collect the original trajectory data, but it should be clear Yes, the higher the added noise, the lower the accuracy of the recommendation results and the lower the usability of point-of-interest mining. In order to balance security and accuracy, it is necessary to calculate the matching degree of the recommended user list and location list, and calculate the matching degree MR(A ) methods include:

Among them, ori(A) represents the user recommendation list and location recommendation list without noise, noi(A) represents the user recommendation list and location recommendation list with noise added, A=U _rec ∪L _rec , representing the user-location bipartite graph User group and location group take the union, where U _rec represents the user group and L _rec represents the location group:

U _rec ={u, score(u)|score(u _i )≥score(u _j ), 1≤i＜j≤|U|} (6)

L _rec ={l, score(l)|score(l _i )≥score(l _j ), 1≤i<j≤|L|} (7)

If the matching degree MR(A) satisfies the set matching degree threshold, go to step 6;

在调整Δf和隐私预算ε的过程中，要保证Δf满足设定的全局敏感度阈值，隐私预算ε满足隐私阈值要求；If the matching degree does not meet the set matching degree threshold, go to step 3, and reset the noise by adjusting the global sensitivity Δf and the privacy budget ε

In the process of adjusting Δf and privacy budget ε, it is necessary to ensure that Δf meets the set global sensitivity threshold, and the privacy budget ε meets the privacy threshold requirements;

The privacy budget ε is used to control the probability ratio of the algorithm to obtain the same output on adjacent data sets, reflecting the privacy protection level. The smaller the privacy budget ε, the higher the privacy protection level, and the higher the noise that needs to be added, resulting in a lower matching degree MR. . Δf represents the difference between statistical query results caused by changes in a single record in the dataset. The smaller Δf, the lower the noise that needs to be added, resulting in a higher matching degree MR.

Step 6: Save the noise-added user recommendation list and location list satisfying the matching degree to the database for query by the query user, and recommend the user recommendation list and location recommendation list matching the query information to the query user according to the query information of the query user.

The embodiment of the present invention also provides a system for mining points of interest, which is used to implement the above method for mining points of interest. The system includes:

A first acquisition module for constructing a user-location bipartite graph according to the user's original trajectory data set, and converting the user-location bipartite graph into an association matrix;

获取扰动关联矩阵；其中Δf为全局敏感度，ε为隐私预算，所述隐私预算ε满足设定隐私阈值要求的第二获取模块；Used to add Laplace-distributed noise to each entry in the correlation matrix

obtaining a perturbation correlation matrix; wherein Δf is the global sensitivity, ε is the privacy budget, and the privacy budget ε meets the second obtaining module for setting the privacy threshold requirement;

The third acquisition module is used to obtain the user recommendation list and location recommendation list without noise according to the correlation matrix and the HITS algorithm; according to the disturbance correlation matrix and the HITS algorithm, obtain the user recommendation list and the location recommendation list with noise added; the third acquisition module;

It is used to calculate the matching degree according to the user recommendation list and location recommendation list without noise, and the user recommendation list and location recommendation list with noise added; if the matching degree satisfies the set matching degree threshold, it is transferred to the storage module for processing; If the set matching degree threshold is not met, it will be transferred to the second acquisition module for processing, and the noise data processing module will be reset by adjusting the global sensitivity Δf and the privacy budget ε;

A storage module for storing the noise-added user recommendation list and location list satisfying the matching degree to the database for query by the querying user.

Further, the system further includes a building module for collecting trajectory data including user location information and time information corresponding to the location, and constructing a user's original trajectory data set.

The first acquisition module also includes a first building module for constructing a user-location bipartite graph, the building module includes:

The second building module: for constructing a point of interest dataset according to the user's original trajectory dataset; the point of interest dataset includes user information, location information and time information;

The third building module: used to perform cluster analysis on the data set of interest points using the DBSCAN clustering algorithm to form multiple clusters, and count the frequency of each user accessing the cluster to construct a clustered interest point data set;

The fourth building module is used to construct a user location bipartite graph according to the clustered interest point dataset.

获取扰动关联矩阵，根据扰动关联矩阵，使用HITS算法生成加入噪声的用户推荐列表和加入噪声的位置推荐列表供查询用户查询，通过调节噪声中全局敏感度Δf和隐私预算ε的大小，调节生成的加入噪声的用户推荐列表和加入噪声的位置推荐列表的准确性，在调节噪声的过程中，保证隐私预算ε符合设定隐私阈值，以保证对用户的隐私保护，本发明实施例提供了一种准确性高的兴趣点挖掘方法，并保证了用户的隐私安全，本发明提供的兴趣点挖掘方法及系统可用于向兴趣点查询用户推荐兴趣点。In a method and system for mining points of interest provided by the embodiments of the present invention, a user's original trajectory data set is converted into a user-location bipartite graph, and then converted into a corresponding association matrix, and noise is added.

Obtain the perturbation correlation matrix, and use the HITS algorithm to generate the recommended list of users with added noise and the recommended list of locations with added noise according to the perturbed correlation matrix. The accuracy of the noise-added user recommendation list and the noise-added location recommendation list. In the process of adjusting the noise, it is ensured that the privacy budget ε meets the set privacy threshold, so as to ensure the privacy protection of the user. The embodiment of the present invention provides a The high-accuracy POI mining method ensures the privacy and security of users, and the POI mining method and system provided by the present invention can be used to recommend POIs to users who query POIs.

The above are only the preferred embodiments of the present invention. It should be pointed out that for those skilled in the art, without departing from the technical principle of the present invention, several improvements and modifications can also be made. These improvements and modifications It should also be regarded as the protection scope of the present invention.

Claims (9)

1. A method for mining points of interest, the method comprising the steps of:

step 1: constructing a clustering interest point data set according to the user track data set, constructing a user-position bipartite graph according to the clustering interest point data set, and converting the user-position bipartite graph into an incidence matrix;

and 2, step: adding noise obeying Laplace distribution to each item in incidence matrix

Obtaining a disturbance incidence matrix; wherein Δ f is the global sensitivity, ε is the privacy budget, and ε meets the privacy threshold requirement;

and step 3: acquiring a user recommendation list and a position recommendation list which are not subjected to noise according to the incidence matrix and the HITS algorithm; acquiring a user recommendation list and a position recommendation list added with noise according to the disturbance incidence matrix and the HITS algorithm;

and 4, step 4: calculating the matching degree according to the user recommendation list and the position recommendation list which are not subjected to noise addition and the user recommendation list and the position recommendation list which are subjected to noise addition; if the matching degree meets the set matching degree threshold value, switching to

Step 5; if the matching degree does not meet the set matching degree threshold value, the step 2 is carried out, the global sensitivity delta f and the privacy budget epsilon are adjusted, and the noise is reset

And 5: and storing the user recommendation list and the position recommendation list with the matching degree meeting the threshold value of the matching degree, added with the noise, into a database for querying a query user.

2. The method of interest mining of claim 1, further comprising: and acquiring track data containing user position information and time information corresponding to the position information, and constructing an original track data set of the user.

3. The method of interest point mining according to claim 1, wherein the method of calculating the matching degree mr (a) comprises:

wherein ori (a) represents a non-noisy user recommendation list and a location recommendation list, noi (a) represents a noisy user recommendation list and a location recommendation list, and a represents a user group and location group union in a user-location bipartite graph.

4. The method of interest point mining of claim 1, wherein the method of constructing a clustered interest point data set comprises the steps of:

constructing an interest point data set according to an original track data set of a user; the data in the interest point data set comprises user information, position information of a user and time information corresponding to the position information;

and performing clustering analysis on the interest point data set by adopting a DBSCAN clustering algorithm to form a plurality of clusters, wherein each cluster is represented by the position information of the central point of the cluster, the Id of the central point is used as the unique identifier of the cluster, the frequency of accessing the cluster by each user is counted, and the clustered interest point data set is constructed.

5. The point-of-interest mining method of claim 1, wherein the user-location bipartite graph has a data structure, ULBG ═ (U, L, E), wherein U ═ U ═ E _i I 1 ≦ i ≦ m } representing the user node group, L ≦ L ≦ m _j I 1 ≦ j ≦ n } represents a position node group, E { (u) _i ，l _j ，w _ij ) I is more than or equal to 1 and less than or equal to m, and j is more than or equal to 1 and less than or equal to n represents an access set of the edge; wherein u is _i Id, l representing user i _j Id, w representing point of interest j _ij Representing the frequency with which user i visits point of interest j.

6. The method of claim 5, wherein the correlation matrix comprises | U | rows and | L | columns, and the elements in the correlation matrix are the frequency w of the user i accessing the point of interest j _ij 。

7. A point of interest mining system, the system comprising:

a first obtaining module: constructing a clustering interest point data set according to the user track data set, constructing a user-position bipartite graph according to the clustering interest point data set, and converting the user-position bipartite graph into an incidence matrix;

a second obtaining module: for adding noise obeying a Laplace distribution to each entry in the correlation matrix

Obtaining a disturbance incidence matrix; wherein Δ f is global sensitivity, ε is a privacy budget, and ε meets the requirement of a set privacy threshold;

a third obtaining module: the system comprises a correlation matrix, a HITS algorithm and a positioning recommendation list, wherein the correlation matrix is used for acquiring a user recommendation list and a position recommendation list which are not added with noise according to the correlation matrix and the HITS algorithm; acquiring a user recommendation list and a position recommendation list added with noise according to the disturbance incidence matrix and the HITS algorithm;

a data processing module: the matching degree is calculated according to the user recommendation list and the position recommendation list which are not subjected to noise addition and the user recommendation list and the position recommendation list which are subjected to noise addition; if the matching degree meets the set matching degree threshold value, switching to a storage module for processing; if the matching degree does not meet the set matching degree threshold value, the processing is switched to a second acquisition module, and the noise is reset by adjusting the global sensitivity delta f and the privacy budget epsilon

A storage module: and the noise-added user recommendation list and the position recommendation list with the matching degree meeting the threshold of the matching degree are stored in a database for querying the user.

8. The system of claim 7, further comprising a construction module for collecting trajectory data including user location information and time of day information corresponding to the location, and constructing a user raw trajectory data set.

9. The point-of-interest mining system of claim 7, wherein the first obtaining module further comprises a first constructing module for constructing a clustered point-of-interest data set, the constructing module comprising:

a second building block: the method comprises the steps of constructing an interest point data set according to an original track data set of a user; the data in the interest point data set comprises user information, position information of a user and time information corresponding to the position information;

a third building block: the method is used for performing clustering analysis on the interest point data set by adopting a DBSCAN clustering algorithm to form a plurality of clusters, each cluster is represented by the position information of the central point of the cluster, the Id of the central point is used as the unique identifier of the cluster, the frequency of each user accessing the cluster is counted, and the clustered interest point data set is constructed.

Images