CN109918573A - A kind of personalized circuit recommendation system and method based on position social networks - Google Patents
A kind of personalized circuit recommendation system and method based on position social networks Download PDFInfo
- Publication number
- CN109918573A CN109918573A CN201910245028.4A CN201910245028A CN109918573A CN 109918573 A CN109918573 A CN 109918573A CN 201910245028 A CN201910245028 A CN 201910245028A CN 109918573 A CN109918573 A CN 109918573A
- Authority
- CN
- China
- Prior art keywords
- interest
- point
- user
- information
- time
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
A kind of personalized circuit recommendation system and method based on position social networks, belong to information technology field.In order to there is trip low efficiency up for the route for further being promoted and being recommended in the wish degree matching degree for solving the problem of that the servers off-line of current circuit recommendation method excavates the information such as point of interest and residence time, cost and user.System of the invention includes data acquisition interest point information of being registered according to user's history, and the offline point of interest planning module clustered according to interest point information；The point of interest evaluation module for constructing point of interest Rating Model based on user and time response according to the interest point information of acquisition, scoring；The planning request module for inputting information for obtaining user, generating layout of roads request；With the layout of roads module according to the interest point information and family information module of user, starting point information and departure time information planning route.The present invention is suitable for personalized circuit recommendation.
Description
Technical field
The invention belongs to information technology fields, and in particular to a kind of information recommendation system and method.
Background technique
With the rise and development of location-based social networks (such as Yelp and FourSquare), user can pass through intelligence
Restaurant, cinema, the park etc. that energy terminal accessed them register and score.Other users can be according to these scorings
Interested place is selected with comment information.This large-scale social media information includes metadata information abundant, such as
Point of interest feature tag, temporal information and geographical labels information etc..These context datas are although coarse and many and diverse, but for more
Media application is particularly useful, can be used for tag definition, search, advertisement pushing and recommendation etc..In numerous applications, circuit recommendation
Because it is received significant attention with being closely connected for daily life with importance.In general, typically travelling recommender system is by two
A aspect composition: general recommendations and personalized recommendation.For general recommendations, it contains user and provides when carrying out travelling planning
Destination travel advisory information, answer as " I want to go to Beijing travelling, which the tourist attractions that must be gone have? " it is such generally to ask
Topic.On the other hand, personalized recommendation considers the personal preference of user, matches and recommend itinerary information preferably.Individual character
Change the personal preference that user is excavated in circuit recommendation, consider constraint condition of the user on time and cost, plans one for user
It is suitable for and meets the personal high satisfaction itinerary constrained.
Existing circuit recommendation mainly faces following several challenges:
(1) is personalized.Different users has different personal preferences, such as the classification of point of interest, distance and suitable trip
The selection of user can all be influenced by looking at time etc..We can be registered record and its friend and similar users by the history of user
To speculate fancy grade of the target user to the point of interest having not visited.
(2) formulation of route.Traditional point of interest promotion expo is the single point of interest that user recommends high scoring, and these
The point of interest of height scoring may not be able to form one and meet user time and spend the itinerary of expense limitation.Layout of roads
The quantity of the interested point of interest of user need to be maximized, while to meet constraint of the user on time and cost as far as possible.
(3) limited time and cost expense.User reaches a new region, wants to access several interested positions
But insufficient hourage, and want to reduce to the greatest extent expense, personalized circuit recommendation seek to be under these restrictive conditions
User finds the walking route of a high satisfaction.
(4) flood tide calculates.The interested interest point set of user can form the route of a plurality of different order, if it wants
A route being made of 5 points of interest is found in 150 points of interest, feasible fruiting quantities can reach 1,000,000,000 ranks, but
It wherein many routes and does not meet user preference or is not able to satisfy restrictive condition, so we need a kind of Pruning strategy to reduce
Calculation amount, with the operational efficiency of boosting algorithm.
So layout of roads problem not only needs to filter out the interest point set for meeting user's limitation, it will also be according to certain
Built-up sequence reach optimal user satisfaction.
Ravi et al. (Ravi L, Vairavasundaram S.A Collaborative Location Based
Travel Recommendation System through Enhanced Rating Prediction for the Group
Of Users [J] .Comput Intell Neurosci, 2016,2016 (2): 1291358.) analyzing the feature of tourism packet,
Consider that the personal preference, regionality and favorable season of user carry out personalized traveling bag and recommend.Wang et al. (Wang X,
Leckie C,Chan J,et al.Improving Personalized Trip Recommendation by Avoiding
Crowds [J], 2016:25-34.) a kind of Bayesian learning models are devised, pass through the trip of extraction from the photo with geography information
Row line carries out personalized circuit recommendation.Above-mentioned research work carries out pushing away for traveling bag or route using probabilistic model
It recommends, they do not account for the satisfaction and others individual subscriber restrictive condition of user.Of user is considered in some systems
People's preference is to provide personalized suggestion for user.Travel agency uses PersonalTour recommender system (Lorenzi F, Loh
S,Abel M.PersonalTour:A Recommender System for Travel Packages[C].Ieee/wic/
acm International Conference on Web Intelligence and Intelligent Agent
Technology, 2011:333-336.), suitable travel package is found according to the preference of user, then to suggest the shape of inventory
Formula is sent to user.Subsequent user can evaluate in enjoying various service items.Koceski et al. (Koceski S,
Petrevska B.Empirical Evidence of Contribution to E-Tourism by Application of
Personalized Tourism Recommendation System[J].Annals of the Alexandru Ioan
Cuza University-Economics, 2012,59 (1): 363-374.) propose MyTravelPal user select travel
Behind region, tourist attractions are listed according to the preference of user and personalized recommendations service is provided.
Vansteenwegen et al. (Xu Z, Chen L, Chen G.Topic based context-aware travel
recommendation method exploiting geotagged photos[J].Neurocomputing,2015,155
(C): 99-107. the website City Trip Planner) is devised, it is laggard in acquisition individual subscriber preference and restrictive condition
Line circuit planning.Lu et al. (Marlow N A.A normal limit theorem for power sums of
independent random variables[J].Bell Labs Technical Journal,2013,46(9):2081-
2089.) the personalized travelling proposed recommends (Personalized Trip Recommendation, PTR) by user's
The behavior of registering is excavated, while considering to carry out personalized recommendation under the personal travelling restrictive condition of user.Yoon et al.
(Sun Y,Fan H,Bakillah M,et al.Road-based travel recommendation using geo-
Tagged images [J] .Computers Environment&Urban Systems, 2015,53:110-122.) it utilizes and works as
The GPS track of ground resident and travelling intelligent carry out the excavation of itinerary.
Although having had already appeared a variety of recommended methods at present, the servers off-line of current circuit recommendation method is excavated emerging
Interest point and residence time, type, spend etc. information and user wish degree matching degree be not it is especially high, up for further
It is promoted, but also there is a problem of that time overhead is bigger.
Summary of the invention
The present invention excavates point of interest and residence time, cost etc. to solve the servers off-line of current circuit recommendation method
There is line efficiency in the problem of information and the wish degree matching degree of user are up for further being promoted, and the route recommended
Low problem.
A kind of personalized circuit recommendation system based on position social networks, including offline point of interest planning unit and online
Circuit recommendation unit；
The off-line data planning unit includes:
Offline point of interest planning module, registers data acquisition interest point information according to user's history, and interest point information includes:
1. the cost of point of interest, type and residence time；The record 2. history of user is registered；3. between the user obtained in LBSN
Social network relationships；And clustered according to interest point information, plan residence time, tourism expense and the type letter of point of interest
Breath；
Point of interest evaluation module is scored according to the building of the interest point information of acquisition based on the point of interest of user and time response
Model scores to all candidate points of interest；
The online circuit recommendation unit includes:
Plan request module, for obtaining the time-constrain of user's input, spending budget, personal preference information, and according to
Information generates layout of roads request；
Trip information obtains module, for obtaining origin information, endpoint information and departure time information；
Layout of roads module, according to the interest point information of user and family information module, starting point information and departure time
Information planning route simultaneously recommends user.
Personalized circuit recommendation method based on position social networks, comprising the following steps:
The process of user's transmitting line planning request；
It obtains social network relationships and carries out the process of offline point of interest planning；
Construct the process of point of interest Rating Model；
Layout of roads is carried out, the process for the optimum line for recommending to meet the requirements to user.
Beneficial implementation result of the invention are as follows:
Servers off-line of the invention is excavated the information such as point of interest and residence time, cost and is matched with the wish degree of user
Degree is higher, and personalized circuit recommendation method can more match the wish of user, can guarantee search out with the inventive method
The route of highest satisfaction.The route that the present invention recommends simultaneously greatly reduces the invalid distance of travel route, thus greatly
Improve the efficiency of trip.So corresponding SE method of the invention is optimal on recommending quality and operational efficiency.
Detailed description of the invention
Fig. 1 is that user-point of interest is registered model schematic；Wherein user indicates that user, POI indicate that point of interest, map indicate
Map, check-in activity expression are registered；
Fig. 2 (a) is that Phoenix (PX) corresponding user satisfaction compares figure, and Fig. 2 (b) is full for New York (NY) corresponding user
Meaning degree compares figure, and Fig. 2 (c) is that Los Angeles (LA) corresponding user satisfaction compares figure；
Fig. 3 (a) is that the average operating time of Phoenix (PX) corresponding each user compares figure, and Fig. 3 (b) is New York (NY)
The average operating time of corresponding each user compares figure, and Fig. 3 (c) is the average operation of Los Angeles (LA) corresponding each user
Time compares figure；
Fig. 4 (a) is the corresponding route recommendation figure of SE, and Fig. 4 (b) is the corresponding route recommendation figure of Greedy.
Specific embodiment
Specific embodiment 1:
A kind of personalized circuit recommendation system based on position social networks, including offline point of interest planning unit and online
Circuit recommendation unit；
The off-line data planning unit includes:
Offline point of interest planning module, registers data acquisition interest point information according to user's history, and interest point information includes:
1. the cost of point of interest, type and residence time etc.；The record 2. history of user is registered；3. from LBSN
Social networks between the user obtained in (Location-based Social Network, location-based community network) closes
System；And clustered according to interest point information, plan residence time, the tourism information such as expense and type of point of interest；
Point of interest evaluation module is scored according to the building of the interest point information of acquisition based on the point of interest of user and time response
Model scores to all candidate points of interest；
The online circuit recommendation unit includes:
Request module is planned, for obtaining the time-constrain of user's input, spending the information such as budget, personal preference, and root
It is believed that breath generates layout of roads request；
Trip information obtains module, for obtaining origin information (starting point information), endpoint information and departure time information,
It can be and obtained automatically by the intelligent terminal carried, be also possible to the acquisition of information inputted according to user；
Layout of roads module, according to the interest point information of user and family information module, starting point information and departure time
Information planning route simultaneously recommends user.For the time overhead for reducing route search process, the present invention devises two kinds of beta pruning plans
The operational efficiency for slightly promoting Route Planning Algorithm, finally by the circuit recommendation of highest satisfaction to user.
Specific embodiment 2:
Personalized circuit recommendation method based on position social networks, comprising the following steps:
The process that user is requested by browser to the planning of server transmitting line；
Server obtains social network relationships and carries out the process of offline point of interest planning；
The process of server construction point of interest Rating Model；
Server carries out layout of roads, the process for the optimum line for recommending to meet the requirements to user.
Specific embodiment 3:
The process that user described in present embodiment is requested by browser to the planning of server transmitting line, including following step
It is rapid:
User spends budget by the time-constrain of mobile phone browser input travelling, personal type of preferences (such as park,
Shopping center, museum, food and drink, hotel, library etc.) etc. information；The time-constrain of planning request module acquisition user's input,
The information such as budget, personal preference are spent, layout of roads is formed and requests Q, and be sent to layout of roads module.The layout of roads
The information contained in request Q includes (ID, time, cost, start, end, type), and wherein ID is the ID of layout of roads request,
Time is time-constrain, and cost is to spend budget, and start is origin information, and end is endpoint information, and type is personal preference class
Type.
Other steps are identical with embodiment two.
Specific embodiment 4:
The interest point information of user is that history is registered data, that is, has just been corresponding with phase when the generation Social behaviors of user
The data answered stored data.In some embodiments, it can be after layout of roads module receives layout of roads request Q,
Restart offline point of interest planning module to obtain social network relationships and carry out offline point of interest planning.In some embodiments,
It is also possible to just start offline point of interest planning module acquisition social networks when user stores corresponding data when carrying out social
Relationship simultaneously carries out offline point of interest planning, and with the generation of user social contact behavior, offline point of interest planning module is periodically planned simultaneously
It updates, after layout of roads module receives layout of roads request Q, calls directly offline point of interest planning module and obtain social network
Network relationship and carry out offline point of interest planning as a result, this mode can not issue layout of roads request (quite using user
In free time) when planned, when user issue layout of roads request after, call directly and submitted as a result, user can be saved
Obtain the feedback time of program results after request, reduce the waiting time, improve result feedback efficiency, thus improve user experience and
Satisfaction.
Acquisition social network relationships described in present embodiment and the process for carrying out offline point of interest planning, including following step
It is rapid:
Offline point of interest planning module is registered data acquisition interest point information according to user's history, and interest point information includes:
1. the cost of point of interest, type and residence time etc.；The record 2. history of user is registered；3. between the user obtained in LBSN
Social network relationships；It include two class node of user and point of interest in LBSN, as shown in Figure 1, u1~u4Represent user, l1~l7
Represent point of interest；The directed edge that user is directed toward point of interest represents the behavior of registering of user in the position；Mainly include in LBSN: using
The relationship of registering of friendly neighbour's relationship between family, user and point of interest, the geographical location relationship between point of interest；
Point of interest in LBSN is recommended it is intended that user recommends some new interested positions, for user provide it is credible can
By the travel information with high satisfaction；Data prediction is carried out to register information and historical track of user with offline mode, is used
Density-based algorithms DBSCAN algorithm clusters the number of registering in track, and it is fewer to filter out number of registering
Place, by geographical location it is neighbouring place cluster be a point of interest, while according in track arrival time and time departure
The residence time of equal information plannings point of interest, the information such as expense and interest vertex type of travelling, for point of interest recommendation and circuit recommendation
Data are provided to support.
Other steps are identical as specific embodiment two or three.
Specific embodiment 5:
In recommended method of the invention in terms of point of interest scoring includes two:
(1) point of interest based on user scores (US:User-based score): measure user is inclined to target point of interest
Good degree；
(2) point of interest based on time response scores (TS:Temporal-based score): assessment current interest point exists
The suitable access degree of particular point in time；
Both are scored the point of interest score-system that permeates.
The process of point of interest Rating Model is constructed described in present embodiment, comprising the following steps:
Point of interest evaluation module constructs point of interest Rating Model and time based on user according to the interest point information of acquisition
The point of interest Rating Model of characteristic；
The point of interest Rating Model based on user:
Use the personal preference of Ranking-By-Preference (RBP) Policy evaluation user；Use the association based on friend
Speculate with filtering and based on the collaborative filtering of similar users target user to the preference of current interest point；
Ranking-By-Preference strategy: classification CAT (a) belonging to point of interest a, the preference and point of interest of user
Classification have larger connection；For example, can be liked if being frequently visited by the user the point of interest of national park classification with the reasonable expectation user
It is joyous to participate in outdoor sports, Central Park and Liberty State Park can be recommended to be suitble to outdoor sports in this way to user
Point of interest；For user u, count each point of interest category c (a kind of point of interest category referred to) user registered it is emerging
Interest point number, calculates user to the preference of the point of interest category, is denoted as the preference ps (u, c) of RBP point of interest category:
Point of interest category can be with reference to " classification of geography information point of interest and coding ", such as the point of interest class of tourist attractions class
Not set C={ natural landscape, the places of cultural interest, park plaza, theme park }.The present invention registers data progress in advance to user's history
Processing obtains the classification of point of interest, therefore history label of registering according to the longitude and latitude in place of registering and point of interest sorting code number specification
Format to data set D is [user UID, point of interest PID, register time Time, classification C].It is registered data according to user's history,
The number that counting user u registers in the point of interest that classification is c, is denoted as countu,c；Point of interest category is clustered, is counted
The most point of interest category of number of registering and number of registering, are denoted as max-check-in；Therefore count can be usedu,cWith max-
The ratio of check-in measures user to the preference ps (u, c) of certain classification point of interest；
We are user to all point of interest category c1~c|C|Preference value indicated with following vector:
PV (u)=< ps (u, c1),ps(u,c2),...,ps(u,c|C|) >
Point of interest score in predicting based on user considers two aspects: the preference of user and the preference of user friend.User
The scoring of preference be denoted as USRBP(u, a), scoring is using above-mentioned user to the preference of the point of interest generic, i.e. USRBP
(u, a)=ps (u, a.cat), wherein u represents user, and a represents certain point of interest, and a.cat indicates the classification of point of interest a；Consider society
Friendship relationship, user are influenced the hobby of certain point of interest by friend, therefore the present invention uses the collaborative filtering based on friends
(FCF:Friend-based CF) method is filtered, and basic thought is scoring US of the user u to point of interest aFCF(u a) is it
The mean value that all friend v score to point of interest a, specific calculation are as follows:
FU indicates friend's set of user a, | FU | indicate friend's quantity.
Collaborative filtering is the most ancient method of recommender system, and the collaborative filtering based on user uses arest neighbors technology, is utilized
The historical information of user calculates the similarity between user, then the scoring using the nearest neighbor of target user to point of interest
It predicts scoring of the target user to particular point of interest, finally target user is recommended according to this scoring.The present invention is by base
US is denoted as in the methods of marking of user's similitudeSCF；According to the preference vector of user, between cosine similarity method calculating user
Similitude:
Above formula calculates the similarity of the corresponding point of interest category preference vector of user u and v, and molecule is two preference vectors
Dot product, denominator are the length of two preference vectors.
To reduce computing cost, it is that select the preceding k user most like with it be reference to user u, is denoted as similar users collection
Close SU；Collaborative filtering scoring US based on user's similitudeSCFIt is as follows:
Two kinds of scorings that the point of interest scoring based on user that the present invention considers includes, the scoring based on friends
USFCFWith the scoring US based on user's similitudeSCFWeighted Fusion at a scoring US (u, a):
US (u, a)=w*USSCF(u,a)+(1-w)*USFCF(u,a)
Wherein, w is fusion weight；
Two kinds of methods of marking are fused into a score value, indicate the influence of user preference and friends to scoring.
The point of interest Rating Model based on time response:
From actual traveled it is found that different points of interest has different suitable access times；For example, New York Times are wide
Field is more suitable for making a visit at night；In this way, present embodiment defined in one day 24 time-based points of interest scorings (TS:
Temporal-based score), it is denoted as TS (a, t), considers the following two kinds scoring:
1. what time period access point of interest preferably；For particular point of interest, registering in each period is counted
Number, to determine the period scoring TS of the point of interestNBT(a, t), the strategy are denoted as Normalize-By-Time；
Wherein, a indicates that certain point of interest, t indicate certain period, counta,tIndicate the people in time period t Access Interest point a
Number；Denominator is meant that the number of registering of point of interest a in more each period, and selection is registered periods pair of the most numbers of a
Time period t ' number of registering be normalized, obtain point of interest a in the scoring of time period t；
2. which point of interest of current slot is most popular；For current slot, with number and this of Access Interest point a
The ratio of the maximum access times of other points of interest determines the access scoring TS of point of interest a in periodNBA(a, t), the strategy claim
For Normalized-By-Attraction (NBA)
Finally by TSNBT(a, t) and TSNBA(a, t) permeates the scoring of the point of interest based on time response TS (a, t):
Scoring fusion:
After calculating the point of interest scoring based on user and the point of interest scoring based on time response, the two is fused to
One final point of interest scores AS (u, a, t), is not only able to satisfy user preference to select, but also the point of interest that the time is suitable,
AS (u, a, t)=α * TS (a, t)+(1- α) * US (u, a)
α is equalizing weight, for balancing the point of interest scoring based on user and the point of interest scoring based on time response.
Point of interest scoring AS (u, a, t) is the point of interest scoring of point of interest Rating Model based on user and time response
Model, the occurrence determined using AS (u, a, t) are to score candidate point of interest.
Other steps are identical as one of specific embodiment two to four.
Specific embodiment 6:
The process of layout of roads is carried out described in present embodiment, comprising the following steps:
The basic thought of layout of roads is exactly to add suitable point of interest one by one in current line, has ultimately formed one both
It is able to satisfy user time and spends limitation, and route with the greatest satisfiction by user；Route based on conditional extensions of the invention is dug
Algorithm is dug, making rational planning for for route is carried out；
Point of interest distribution map: with the distribution of digraph G=(V, E) description point of interest, V={ 1,2 ..., n } is interest point set
It closes；Each point of interest i ∈ V has following attribute: mean residence time m of the user in the point of interesti；It is put down needed for the point of interest
Spend ci；User u indicates conveniently to be denoted as r to the scoring AS (u, a, t) of the point of interest in order to subsequentu,i；Each edge ei,j∈E
Represent from current interest point i to the path of next point of interest j, user from i to j needed for time ti,jWith ei,jLength have
It closes；
Itinerary: assuming that the starting point of user is x, terminal y, departure time T0, then walking route can be described
For x →... i ... → y, and initializing set mx=my=0, i.e. x and y only mark beginning and end, residence time 0；Except x, y with
Outer point is the point of interest of access；For specific user u, overall score F (P, u)=∑ of route Pi∈Pru,i；
The personal restrictive condition of user:
Time and cost limitation: user will be in BtTime expert covers whole route, BtIt is embodied not only in the stop of point of interest
Time, further include from a point of interest into another point of interest road the time it takes, and always take no more than Bc；
Conditional extensions:
Best itinerary is found using a kind of joint line mining algorithm based on conditional extensions；This method produces every step
Raw route regards a state as, it is assumed that the point of interest that current state finally accesses is i, then current route is x →... i → y；Often
One state is collectively labeled as s=(sK,sT,sC,sH,sρ,i)；sKIndicate the interest point set accessed；sTIt is to start to access i
Time, i.e. πi；sCIt is total cost of current line；sHIt is the overall score of the point of interest accessed, i.e. F (K, u)；sρIt is current
Route x →...→ i, i are the last one points of interest under current state；It is only stateful under original stateThat is route x → y；
The basic thought of layout of roads is to add point of interest into route one by one to extend current route；Assuming that working as front
I is the last one point of interest in the P of road, and current line P meets the time of user and spends limitation, πiIt is when starting to access i
Between；A new point of interest j is added into current line in next step, so that route becomes P=x →... i, j → y, and accessed
Point of interest quantity becomes k from k-1, and state becomes s ' from s, then each state parameter variation is as follows:
Design function Sat (i, j, π of the present inventioni,Ci) come examine route expand point of interest j after, whether new line still meets
User's constraint condition；Parameter i in function indicates the last one point of interest in current line, and j expression will be added in route
Point of interest, πiIt is the time for starting Access Interest point i, CiIndicate the cost of Access Interest point i；The specific method of inspection is: according to
The time of user and cost limitation, if gone sight-seeing since the last one point of interest i of current line, are transferred to interest after stop
Point j is then transferred to terminal y, the time of whole process and the limitation for taking no more than user after going sight-seeing j, then function returns to true,
Judge whether following inequality is true: if πi+mi+ti,j+mj+tj,y≤T0+BtAnd Ci+cj≤Bc, function Sat (i, j, πi,
Ci) return to true；
Similar route compares:
May have a kind of situation during conditional extensions: the s of several different conditions possesses identical sK, that is, accessed
Interest point set it is identical, and the last Access Interest point of each state is i, and these types of route is known as similar circuitry, phase
Liny road does not need whole reservations, because some states therein can not be extended to an optimum line；
If meeting following condition, state s is claimed to be better than s ':
(si=si′)∧(sK=sK′)∧(sT≤sT′)∧(sc≤sc′)∧(sH≥s'H)
∧ be conjunction operation, indicate and；
The comparison of above-mentioned state is designed to function Check (s, s '), compares the superiority-inferiority of two states, if Check
(s, s ') returns to true, indicates that state s is better than state s ', i.e. state s more early than s ' can reach home, and spends less.
Conditional extensions pseudo-code of the algorithm is as follows:
Under original state, S={ s0, the institute that algorithm is extended by the new point of interest of addition in S is stateful, in algorithm
Institute in two for cyclic extensions S is stateful, and the state for only meeting restrictive condition can be retained.At the same time, 9-10 row generation
Code carries out superiority and inferiority stateful in same step and compares, and only preferably state is retained.12-13 line code can save high full
The optimum line of meaning degree.The time complexity of conditional extensions algorithm is O (n22n), it is index rank, but still than simplest violence
O (the n of searching method！) fast.
The time complexity of conditional extensions algorithm is index rank.For the operational efficiency of boosting algorithm, by condition sK=
sK' replace with | sK|=| sK' |, i.e., the point of interest number accessed under two states is identical, then two states superiority-inferiority is more public
Formula becomes:
(si=si′)∧(|sK|=| sK′|)∧(sT≤sT′)∧(sc≤sc′)∧(sH≥sH′)
State s and s ' arrives at point of interest i, but the time spent in state s and spends less, and user satisfaction is higher.
And after changing, the number of states in conditional extensions algorithm set S can be substantially reduced, and Algorithms T-cbmplexity is by O (n22n) become
O(cn2), effectively improve the operational efficiency of algorithm.
Other steps are identical as one of specific embodiment two to five.
Embodiment:
Below by embodiment and attached drawing, elaborate to the present invention.
The real data set of embodiment selection Yelp and Foursquare.The data set of Yelp includes 45981 users,
The score information and 11537 points of interest that 229906 1 to 5 stars do not wait.Foursquare data set has 20784 users,
153477 score informations and 7711 points of interest.
Be performance to assess TripPlanner recommendation of the invention, when initialization set the overall travel time of user as
440 minutes, total spend was 60 dollars.Departure place is a random position, and the departure time is 8 points of morning, and user is from one
The driving mode of the Google Maps of time needed for point of interest to next point of interest is come simulated determination.Implementation environment is one
2.5GHz CPU and 8G memory runs the computer of Windows system.
Test the operational efficiency of different layout of roads methods and the difference of recommended line user satisfaction.Main test three
City, Phoenix (PX) in Yelp data set, in the New York (NY), Foursquare data set in Foursquare data set
Los Angeles (LA).By Central City, the Central Park and Hollyood in three cities as starting point and terminal.It is right
In each city, randomly choose 100 users and test, to each user, select they respectively score highest 150 it is emerging
Interest point carries out circuit recommendation as candidate interest point set.It selects in spite of above-mentioned limitation, but in 150 points of interest by 5
The route of point of interest composition, feasible solution quantity can still reach 1,000,000,000 ranks, it is clear that the mode for not being available force search carries out
Layout of roads.The runing time of the more following 4 kinds of methods of the present invention and the user satisfaction F (P, u) of recommendation results.
Greedy algorithm (is denoted as Greedy): route is added in the highest candidate point of interest of greedy algorithm selection scoring.
Dynamic Programming (is denoted as DP): a kind of dynamic line planning algorithm.
Conditional extensions algorithm (State Expansion, be denoted as SE): the conditional extensions algorithm in the present invention.
SE-SR indicates the conditional extensions algorithm of stateful extension (state-relaxing).SE algorithm guarantees to search out
The recommended line of one highest satisfaction, and SE-SR not can guarantee.
Fig. 2 (a) to Fig. 2 (c) is that user satisfaction compares figure, and Fig. 2 (a) is Phoenix (PX) corresponding user satisfaction ratio
Compared with figure, Fig. 2 (b) is that New York (NY) corresponding user satisfaction compares figure, and Fig. 2 (c) is that Los Angeles (LA) corresponding user is satisfied
Degree compares figure；Y-axis indicates the average satisfaction of all test users in figure, and x-axis indicates time restriction Bt.Interest in recommended line
Point total number is with BtChange and change, minimum is 3, up to 7.It can be seen from the figure that with BtIncrease, Yong Human
Meaning degree is gradually increasing, because of BtIncrease, user's having time goes to access more points of interest.The performance of SE algorithm is best, because its
It can guarantee the recommended line for searching out highest satisfaction.SE-SR algorithm only has small difference away from optimum.Greedy algorithm because
Its search strategy is simple, and overall performance is straight and narrow.And DP algorithm is performed poor in all tests.
Fig. 3 (a) to Fig. 3 (c) is that the average operating time of each user compares figure, and Fig. 3 (a) is that Phoenix (PX) is corresponding
The average operating time of each user compares figure, and Fig. 3 (b) is that the average operating time of New York (NY) corresponding each user compares
Figure, Fig. 3 (c) are that the average operating time of Los Angeles (LA) corresponding each user compares figure；Y-axis is runing time in figure
(second), x-axis are time restriction Bt(hour).It can be seen from the figure that greedy algorithm operation is most fast, and substantially not with BtVariation and
Variation.
A user is randomly selected, the user BtIt is 8 hours, carries out route in Los Angeles using SE and Greedy respectively and push away
It recommends.Fig. 4 really recommends Case comparison figure, and Fig. 4 (a) is the corresponding route recommendation figure of SE, and Fig. 4 (b) is the corresponding route of Greedy
Recommend figure.Point of interest 1 both as starting point or was used as terminal, then the linewise recommended is 1 → 2 →...→ 1.Due to SE and
Greedy considers the personal preference of user, thus have in its candidate interest point set more identical point of interest (such as 2,3,6,
7).As can be seen that the route that Greedy recommends is 1 → 2 → 3 → 6 → 1, but 1,3 and 2 from Fig. 4 (b), 6 distance farther out, is used
Family can spend the more time in road.However, SE algorithm avoids this problem well, the route recommended is circle
Shape reduces the time it takes in road, compares the route of Greedy, and user has accessed a point of interest more.
Implementation result: corresponding SE method of the invention can guarantee that the route for searching out highest satisfaction, SE-SR have higher
Operational efficiency, but user satisfaction also slightly lose.So corresponding SE method of the invention is recommending quality and operation effect
It is optimal in rate.
Claims (6)
1. a kind of personalized circuit recommendation system based on position social networks, which is characterized in that planned including offline point of interest
Unit and online circuit recommendation unit；
The off-line data planning unit includes:
Offline point of interest planning module is registered data acquisition interest point information according to user's history, and interest point information includes: 1. emerging
Cost, type and the residence time of interest point；The record 2. history of user is registered；3. the social activity between the user obtained in LBSN
Cyberrelationship；And clustered according to interest point information, plan residence time, tourism expense and the type information of point of interest；
Point of interest evaluation module, according to the building of the interest point information of acquisition based on the point of interest of user and time response scoring mould
Type scores to all candidate points of interest；
The online circuit recommendation unit includes:
Request module is planned, for obtaining the time-constrain of user's input, spending budget, personal preference information, and according to information
Generate layout of roads request；
Trip information obtains module, for obtaining origin information, endpoint information and departure time information；
Layout of roads module, according to the interest point information of user and family information module, starting point information and departure time information
Planning route simultaneously recommends user.
2. the personalized circuit recommendation method based on position social networks, which comprises the following steps:
The process of user's transmitting line planning request；
It obtains social network relationships and carries out the process of offline point of interest planning；
Construct the process of point of interest Rating Model；
Layout of roads is carried out, the process for the optimum line for recommending to meet the requirements to user.
3. the personalized circuit recommendation method according to claim 2 based on position social networks, which is characterized in that described
The process of user's transmitting line planning request, comprising the following steps:
User inputs the time-constrain of travelling, spends budget, personal type of preferences information；Plan that request module obtains user's input
Time-constrain, spend budget, personal preference information, form layout of roads and request Q, and be sent to layout of roads module.
4. the personalized circuit recommendation method according to claim 2 or 3 based on position social networks, which is characterized in that
The process for obtaining social network relationships and carrying out offline point of interest planning, comprising the following steps:
Offline point of interest planning module is registered data acquisition interest point information according to user's history, and interest point information includes:
1. the cost of point of interest, type and residence time；
The record 2. history of user is registered；
3. the social network relationships between the user obtained in LBSN；It include two class node of user and point of interest in LBSN；User
The directed edge for being directed toward point of interest represents the behavior of registering of user in the position；
Data prediction is carried out to register information and historical track of user with offline mode, using density-based algorithms
DBSCAN algorithm clusters the number of registering in track, is a point of interest by the neighbouring place cluster in geographical location, together
When according to residence time of arrival time and time departure information planning point of interest in track, expense of travelling and interest vertex type
Information.
5. the personalized circuit recommendation method according to claim 4 based on position social networks, which is characterized in that described
Construct the process of point of interest Rating Model, comprising the following steps:
Point of interest evaluation module constructs point of interest Rating Model and time response based on user according to the interest point information of acquisition
Point of interest Rating Model；
The point of interest Rating Model based on user:
Use the personal preference of Ranking-By-Preference Policy evaluation user；Using based on friend collaborative filtering and
Speculate target user to the preference of current interest point based on the collaborative filtering of similar users；
Ranking-By-Preference strategy: classification CAT (a) belonging to point of interest a；For user u, it is emerging to count each
The point of interest number that interest point classification c user registered, calculates user to the preference of the point of interest category, is denoted as RBP interest
The preference ps (u, c) of point classification:
It is registered data according to user's history, the number that counting user u registers in the point of interest that classification is c is denoted as countu,c；It is right
Point of interest category is clustered, and is counted the most point of interest category of number of registering and number of registering, is denoted as max-check-in；
Use countu,cUser is measured to the preference ps (u, c) of certain classification point of interest with the ratio of max-check-in；
User to all point of interest category c1~c|C|Preference value indicated with following vector:
PV (u)=< ps (u, c1),ps(u,c2),...,ps(u,c|C|) >
The scoring of the preference of user is denoted as USRBP(u, a), USRBP(u, a)=ps (u, a.cat), wherein u represents user, and a is represented
Certain point of interest, a.cat indicate the classification of point of interest a；
It is filtered using the collaborative filtering method based on friends, scoring US of the user u to point of interest aFCF(u a) is it
The mean value that all friend v score to point of interest a, specific calculation are as follows:
FU indicates friend's set of user a, | FU | indicate friend's quantity；
Methods of marking based on user's similitude is denoted as USSCF；According to the preference vector of user, with cosine similarity method meter
Calculate the similitude between user:
Selecting the preceding k user most like with it for user u is reference, is denoted as similar users set SU；Based on user's similitude
Collaborative filtering score USSCFIt is as follows:
USSCFWeighted Fusion at a scoring US (u, a):
US (u, a)=w*USSCF(u,a)+(1-w)*USFCF(u,a)
Wherein, w is fusion weight；
The point of interest Rating Model based on time response:
For particular point of interest, the number of registering in each period is counted, to determine the period scoring TS of the point of interestNBT
(a, t):
Wherein, a indicates that certain point of interest, t indicate certain period, counta,tIndicate the number in time period t Access Interest point a；Point
Mother is meant that the number of registering of point of interest a in more each period, selection register the most numbers of a period to the period
The number of registering of t' is normalized, and obtains point of interest a in the scoring of time period t；
Determine the access scoring TS of point of interest aNBA(a, t), the strategy are known as Normalized-By-Attraction；
Finally by TSNBT(a, t) and TSNBA(a, t) permeates the scoring of the point of interest based on time response TS (a, t):
After calculating the point of interest scoring based on user and the point of interest scoring based on time response, the two is permeated a
Final point of interest scores AS (u, a, t):
AS (u, a, t)=α * TS (a, t)+(1- α) * US (u, a)
α is equalizing weight；
Point of interest scoring AS (u, a, t) is the point of interest scoring mould of point of interest Rating Model based on user and time response
Type.
6. the personalized circuit recommendation method according to claim 5 based on position social networks, which is characterized in that described
Carry out the process of layout of roads, comprising the following steps:
Point of interest distribution map: with the distribution of digraph G=(V, E) description point of interest, V={ 1,2 ..., n } is interest point set；
Each point of interest i ∈ V has following attribute: mean residence time m of the user in the point of interesti；It is averaged needed for the point of interest
Spend ci；User u indicates conveniently to be denoted as r to the scoring AS (u, a, t) of the point of interest in order to subsequentu,i；Each edge ei,j∈ E generation
Table from current interest point i to the path of next point of interest j, user from i to j needed for time ti,jWith ei,jLength it is related；
Itinerary: assuming that the starting point of user is x, terminal y, departure time T0, by walking route be described as x →... i ... →
Y, and initializing set mx=my=0, i.e. x and y only mark beginning and end, residence time 0；Point in addition to x, y is access
Point of interest；For specific user u, overall score F (P, u)=∑ of route Pi∈Pru,i；
Regard the route that every step generates as a state, it is assumed that the point of interest that current state finally accesses is i, then current route is
x→…i→y；Each state is collectively labeled as s=(sK,sT,sC,sH,sρ,i)；sKIndicate the interest point set accessed；sT
It is the time for starting to access i, i.e. πi；sCIt is total cost of current line；sHIt is the overall score of the point of interest accessed, i.e. F (K,
u)；sρIt is current route x →...→ i, i is the last one point of interest under current state；It is only stateful under original stateThat is route x → y；
Point of interest is added into route one by one to extend current route；Assuming that i is the last one point of interest in current line P,
And current line P meets the time of user and spends limitation, πiIt is the time for starting to access i；Add in next step into current line
Add a new point of interest j, so that route becomes P=x →... i, j → y, and the point of interest quantity accessed becomes k, shape from k-1
State becomes s ' from s, then each state parameter variation is as follows:
Design function Sat (i, j, πi,Ci) come examine route expand point of interest j after, new line whether still meet user constrain item
Part；Parameter i in function indicates that the last one point of interest in current line, j indicate the point of interest that will be added in route, πi
It is the time for starting Access Interest point i, CiIndicate the cost of Access Interest point i；The specific method of inspection is: according to the time of user
It is limited with spending, if gone sight-seeing since the last one point of interest i of current line, point of interest j is transferred to after stop, goes sight-seeing j
After be then transferred to terminal y, the time of whole process and the limitation for taking no more than user, then function return true, that is, judge under
Whether face inequality is true: if πi+mi+ti,j+mj+tj,y≤T0+BtAnd Ci+cj≤Bc, function Sat (i, j, πi,Ci) return
true；
If meeting following condition, state s is claimed to be better than s ':
(si=si′)∧(sK=sK′)∧(sT≤sT′)∧(sc≤sc′)∧(sH≥s'H)
∧ be conjunction operation, indicate and.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910245028.4A CN109918573A (en) | 2019-03-28 | 2019-03-28 | A kind of personalized circuit recommendation system and method based on position social networks |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910245028.4A CN109918573A (en) | 2019-03-28 | 2019-03-28 | A kind of personalized circuit recommendation system and method based on position social networks |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN109918573A true CN109918573A (en) | 2019-06-21 |
Family
ID=66967409
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910245028.4A Pending CN109918573A (en) | 2019-03-28 | 2019-03-28 | A kind of personalized circuit recommendation system and method based on position social networks |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109918573A (en) |
Cited By (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110647693A (en) * | 2019-09-23 | 2020-01-03 | 京东城市(北京)数字科技有限公司 | Path recommendation method and device |
| CN110888951A (en) * | 2019-11-09 | 2020-03-17 | 华东师范大学 | Semantic track-based method for mining and locating interest point demands in region and ranking and analyzing system |
| CN111898043A (en) * | 2020-07-02 | 2020-11-06 | 北京大学 | Method for planning urban travel route |
| CN112560910A (en) * | 2020-12-02 | 2021-03-26 | 中国联合网络通信集团有限公司 | User classification method and device |
| CN112632379A (en) * | 2020-12-24 | 2021-04-09 | 北京百度网讯科技有限公司 | Route recommendation method and device, electronic equipment and storage medium |
| CN112781604A (en) * | 2019-11-08 | 2021-05-11 | 逸驾智能科技有限公司 | Method, apparatus, device and computer-readable storage medium for navigation |
| CN112902964A (en) * | 2021-01-22 | 2021-06-04 | 南京邮电大学 | Path recommendation method and device based on interest points |
| CN113505306A (en) * | 2021-06-21 | 2021-10-15 | 广东交通职业技术学院 | Interest point recommendation method, system and medium based on heterogeneous graph neural network |
| CN113723655A (en) * | 2020-12-31 | 2021-11-30 | 京东城市(北京)数字科技有限公司 | Path acquisition method and device, electronic equipment and storage medium |
| CN116579906A (en) * | 2023-07-13 | 2023-08-11 | 天禹文化集团有限公司 | Intelligent museum management method and system based on Internet of things |
| CN116821515A (en) * | 2023-08-30 | 2023-09-29 | 环球数科集团有限公司 | Personalized travel customization system based on associated data and user body |
| CN117953702A (en) * | 2023-12-26 | 2024-04-30 | 上海索西客智能科技有限公司 | Data processing system based on information service |
| CN118708788A (en) * | 2024-08-30 | 2024-09-27 | 沈阳美行科技股份有限公司 | Road book generation method, device, computer equipment and storage medium |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104965883A (en) * | 2015-06-15 | 2015-10-07 | 海南大学 | Individualized travel information screening method matching user characteristics |
| CN105069717A (en) * | 2015-07-29 | 2015-11-18 | 陕西师范大学 | Personalized travel route recommendation method based on tourist trust |
| CN106096785A (en) * | 2016-06-13 | 2016-11-09 | 北京游谱科技发展有限公司 | A kind of circuit method for customizing based on stroke planning, system |
| CN107436950A (en) * | 2017-08-07 | 2017-12-05 | 苏州大学 | A kind of itinerary recommends method and system |
-
2019
- 2019-03-28 CN CN201910245028.4A patent/CN109918573A/en active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104965883A (en) * | 2015-06-15 | 2015-10-07 | 海南大学 | Individualized travel information screening method matching user characteristics |
| CN105069717A (en) * | 2015-07-29 | 2015-11-18 | 陕西师范大学 | Personalized travel route recommendation method based on tourist trust |
| CN106096785A (en) * | 2016-06-13 | 2016-11-09 | 北京游谱科技发展有限公司 | A kind of circuit method for customizing based on stroke planning, system |
| CN107436950A (en) * | 2017-08-07 | 2017-12-05 | 苏州大学 | A kind of itinerary recommends method and system |
Non-Patent Citations (1)
| Title |
|---|
| 明骞: "面向LBSN的兴趣点和路线推荐系统", 《中国优秀硕士学位论文全文数据库 信息科技辑》 * |
Cited By (20)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110647693A (en) * | 2019-09-23 | 2020-01-03 | 京东城市(北京)数字科技有限公司 | Path recommendation method and device |
| CN112781604B (en) * | 2019-11-08 | 2024-02-09 | 逸驾智能科技有限公司 | Method, apparatus, device and computer readable storage medium for navigation |
| CN112781604A (en) * | 2019-11-08 | 2021-05-11 | 逸驾智能科技有限公司 | Method, apparatus, device and computer-readable storage medium for navigation |
| CN110888951B (en) * | 2019-11-09 | 2023-06-09 | 华东师范大学 | Method for mining and selecting interest point demands in region based on semantic track and ranking and analyzing system |
| CN110888951A (en) * | 2019-11-09 | 2020-03-17 | 华东师范大学 | Semantic track-based method for mining and locating interest point demands in region and ranking and analyzing system |
| CN111898043B (en) * | 2020-07-02 | 2023-11-24 | 北京大学 | Urban travel route planning method |
| CN111898043A (en) * | 2020-07-02 | 2020-11-06 | 北京大学 | Method for planning urban travel route |
| CN112560910B (en) * | 2020-12-02 | 2024-03-01 | 中国联合网络通信集团有限公司 | User classification method and device |
| CN112560910A (en) * | 2020-12-02 | 2021-03-26 | 中国联合网络通信集团有限公司 | User classification method and device |
| CN112632379A (en) * | 2020-12-24 | 2021-04-09 | 北京百度网讯科技有限公司 | Route recommendation method and device, electronic equipment and storage medium |
| CN113723655A (en) * | 2020-12-31 | 2021-11-30 | 京东城市(北京)数字科技有限公司 | Path acquisition method and device, electronic equipment and storage medium |
| CN112902964A (en) * | 2021-01-22 | 2021-06-04 | 南京邮电大学 | Path recommendation method and device based on interest points |
| CN112902964B (en) * | 2021-01-22 | 2024-02-23 | 南京邮电大学 | Path recommendation method and device based on interest points |
| CN113505306A (en) * | 2021-06-21 | 2021-10-15 | 广东交通职业技术学院 | Interest point recommendation method, system and medium based on heterogeneous graph neural network |
| CN113505306B (en) * | 2021-06-21 | 2022-04-22 | 广东交通职业技术学院 | Interest point recommendation method, system and medium based on heterogeneous graph neural network |
| CN116579906A (en) * | 2023-07-13 | 2023-08-11 | 天禹文化集团有限公司 | Intelligent museum management method and system based on Internet of things |
| CN116821515B (en) * | 2023-08-30 | 2023-11-03 | 环球数科集团有限公司 | Personalized travel customization system based on associated data and user body |
| CN116821515A (en) * | 2023-08-30 | 2023-09-29 | 环球数科集团有限公司 | Personalized travel customization system based on associated data and user body |
| CN117953702A (en) * | 2023-12-26 | 2024-04-30 | 上海索西客智能科技有限公司 | Data processing system based on information service |
| CN118708788A (en) * | 2024-08-30 | 2024-09-27 | 沈阳美行科技股份有限公司 | Road book generation method, device, computer equipment and storage medium |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109918573A (en) | A kind of personalized circuit recommendation system and method based on position social networks | |
| Kotiloglu et al. | Personalized multi-period tour recommendations | |
| Lim et al. | Personalized trip recommendation for tourists based on user interests, points of interest visit durations and visit recency | |
| Zheng et al. | Learning travel recommendations from user-generated GPS traces | |
| Xie et al. | Learning graph-based poi embedding for location-based recommendation | |
| Bao et al. | Recommendations in location-based social networks: a survey | |
| Zheng et al. | Recommending friends and locations based on individual location history | |
| JP5771534B2 (en) | System and method for delivering sponsored landmarks and location labels | |
| Khalid et al. | OmniSuggest: A ubiquitous cloud-based context-aware recommendation system for mobile social networks | |
| Li et al. | Mining user similarity based on location history | |
| Bao et al. | A survey on recommendations in location-based social networks | |
| Zhao et al. | Personalized recommendations of locally interesting venues to tourists via cross-region community matching | |
| CN109726336B (en) | POI recommendation method combining travel interest and social preference | |
| US8412667B2 (en) | Comparing and identifying similar tracks | |
| Bin et al. | A travel route recommendation system based on smart phones and IoT environment | |
| CN105532030A (en) | Apparatus, systems, and methods for analyzing movements of target entities | |
| Yochum et al. | An adaptive genetic algorithm for personalized itinerary planning | |
| Zhang et al. | Point-of-interest recommendations in location-based social networks | |
| Zheng et al. | Location-based social networks: Locations | |
| Gasparetti | Personalization and context-awareness in social local search: State-of-the-art and future research challenges | |
| Gu et al. | Enhancing personalized trip recommendation with attractive routes | |
| Padia et al. | Sentiment-aware and personalized tour recommendation | |
| JP2020537252A (en) | Systems and methods for predicting similar mobile devices | |
| Lathia | The anatomy of mobile location-based recommender systems | |
| Zhang et al. | A context-awareness personalized tourist attraction recommendation algorithm |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20190621 |
|
| WD01 | Invention patent application deemed withdrawn after publication |