毕业设计外文资料翻译-基于轨迹数据挖掘的个人语义化场所识别

1、毕业设计外文资料翻译学 院： 专业班级： 学生姓名： 学 号： 指导教师： 外文出处：(外文) HYPERLINK /s?wd=journaluri:(738b17840f6f93f4)%20%E3%80%8ANeurocomputing%E3%80%8B&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&sc_f_para=sc_hilight=publish&sort=sc_cited t /_blank o Neurocomputing Neurocomputing,2015 P1-4 附 件：1.外文资料翻译译文； 2.外文原文 指导教师评语：外文翻译符合要求。签

2、名： 2015年10月14日 .外文原文The discovery of personally semantic places based on trajectory data miningIntroductionWith the prevalence of mobile devices with positioning ability, there have been an increasing number of location-aware applications. These applications provide users a rich set of location-base

3、d services, e.g., directory services (finding the location of the nearest gas station), navigation services (providing the routes to the destination location), geo-coding services (mapping a postal address to a location), social networking services (detecting the locations of your friends), etc. The

4、 key element of these applications is “location”. However, instead of latitude and longitude coordinates, many emerging location-aware applications require a more semantic notion: “place”, which is a human-readable label of space, e.g., home, work, restaurant, etc. Harrison and Dourish HYPERLINK l p

5、age11 1 have highlighted the critical distinction between place and space, and pointed out that place, rather than space, is a fundamental concept in application design. Using the notion “place” can help to link geographic information to the users actual needs HYPERLINK l page11 2, and enable these

6、location-aware applications to act more intelligently and adaptively. For example, spatial query system can provide contextualized answers according to the places of the users HYPERLINK l page11 3, location-based reminder can associate a to-do list with specific places HYPERLINK l page11 4, location

7、-based recommender can recommend interesting places HYPERLINK l page11 5, route planner can navigate the pedestrian to the destination through a sequence of personalized places HYPERLINK l page11 6, location-based messaging system can allow messages to be delivered to spe-cific places HYPERLINK l pa

8、ge11 7, location prediction system can predict the users des-tination when beginning a trip HYPERLINK l page11 8, etc.According to HYPERLINK l page11 9, the sense of place refers to the fact of under-standing the properties of places, i.e., their spatial characteristics and social meanings. Thus, a

9、personally semantic place could be defined as a space that is frequently visited by an individual user and carries important semantic meanings to the user, and the discovery of a users personally semantic places can be divided into two sub-problems, i.e., obtaining the physical locations of the plac

10、es (i.e., physical place extraction) and assigning semantics to these places (i.e., semantic place recognition). For the former problem, many approaches have been exposed to extract significant locations of users from their his-torical trajectories HYPERLINK l page11 10 HYPERLINK l page11 14. Howeve

11、r, these significant locations are represented by a geographical point, a point plus radius or a geo-graphical region without semantic meanings. For the latter problem, methods like manual labeling HYPERLINK l page11 15, HYPERLINK l page11 16, reverse geo-coding HYPERLINK l page11 17, HYPERLINK l pa

12、ge11 18 and customized geographic database query HYPERLINK l page11 13, HYPERLINK l page11 19, HYPERLINK l page11 20 are adopted to give semantic meanings to locations. The shortcomings of these methods are as follows: for manual labeling, it lays extra interaction burden on users, and thus does not

13、 scale well when the number of locations becomes large. For reverse geo-coding, the obtained semantics is always represented as postal address (e.g., x Road, y City), which is often as challenging to interpret as raw locations. For customized geographic database query, the personal meaning (e.g., ho

14、me,workplace) of a place is almost impossible to be drawn. Besides, the same place may carry different personal meanings to different users. Since a place can be roughly classified based on the activity performed there HYPERLINK l page11 21, we prefer an approach which can automatically estimate the

15、 semantic meanings of personal places by categorizing them into several pre-defined types.Since GPS is often preferred over its alternatives (e.g., GSM/Wi-Fi based positioning systems) for the above mentioned applica-tions because it is known to be more accurate HYPERLINK l page11 22, this paper pro

16、poses an approach for automatically discovering a users per-sonally semantic places (including physical place extraction and semantic place recognition) from the users GPS trajectory. Our contributions in this paper are summarized as follows:For physical place extraction, a hierarchical clustering a

17、lgorithm which leverages the advantages of both time-based clustering (which is simple and can work in an incremental way on mobile devices) and distance-based clustering (which can accom-modate arbitrary shapes of places) is designed to effectively extract significant locations from GPS trajectory.

18、For semantic place recognition, a comprehensive recognition approach which lies upon the hierarchical clustering algorithm and exploits the temporal, spatial and sequential features of the extracted physical places is proposed to categorize them into pre-defined types.The remainder of this paper is

19、organized as follows: HYPERLINK l page11 Section 2 gives a survey of the related work. In HYPERLINK l page11 Section 3, we present the architecture of our approach. HYPERLINK l page11 Section 4 proposes the hierarchical clustering framework for physical place extraction. HYPERLINK l page11 Section 5

20、 details the techniques for semantic place recognition. The eva-luation of the approach and the experimental results are reported in HYPERLINK l page11 Section 6. Finally, we conclude our work and give some future work in HYPERLINK l page11 Section 7.2. Related work2.1. Physical place extractionPrev

21、ious works on physical place extraction can be generally divided into two groups, i.e., fingerprint-based approaches and geo-metry-based approaches. Fingerprint algorithms HYPERLINK l page11 23, HYPERLINK l page11 24 detect stable radio environment that indicates a stay at a place, and the fingerpri

22、nt of the place is collected during the stay as a vector of visible radio beacons (e.g., cell towers, WiFi APs, etc.). The collected fingerprint is then used to recognize when the user returns to the place. Finger-print-based algorithms could obtain room-level places because they use data from perva

23、sive radio beacons which have wider coverage in cities than that of GPS signals. However, the major drawback of fin-gerprint-based approaches is that the physical location cannot be obtained. Although some databases (e.g., PlaceLab HYPERLINK l page11 25) containing the physical location of radio bea

24、cons are created based on war driving techniques, the coverage is still limited in practice, especially in rural areas and in the developing countries. Thus, fingerprint-based approaches may not be suitable for many above mentioned applica-tions, where the physical locations of places must be known.

25、Geometry-based approaches represent places by points, circles or polygons based on physical locations (e.g., GPS coordinates). Most existing geometry approaches apply clustering algorithms to find places. These clustering algorithms can be roughly divided into two categories, i.e., point based clust

26、ering and trajectory based clustering. For example of point based clustering, Ashbrook and Starner HYPERLINK l page11 10 used a variant of K-Means clustering algorithm to cluster the locations (where the GPS signal lost and reappeared after a pre-defined interval) into places. Zhou et al. HYPERLINK

27、l page11 12 developed DJ-Cluster, a density-based clustering algorithm, to discover places of arbitrary shape. However, these algorithms do not take the temporal continuity of trajectories into account, and this short-coming may cause them fail to find some places (e.g., outdoor places where GPS sig

28、nal is not lost, indoor places with sparse GPS points, etc.). On the other hand, trajectory based clustering algo-rithms cluster locations by taking advantage of the temporal continuity of trajectories. For example, Kang et al. HYPERLINK l page11 11 designed a time-based clustering algorithm to incr

29、ementally extract places along the time axis of a trajectory. Palma et al. HYPERLINK l page11 13 proposed CB-SMoT, a speed-based clustering algorithm, to detect places which are parts of a trajectory where the speed is lower than in other parts of the same trajectory. However, these algorithms work

30、with single trajectories, and the problem of whether multiple places in different trajectories are the same is not well solved (by simply comparing their distance with a threshold HYPERLINK l page11 11 or judging whether they intersect with each other HYPERLINK l page11 13). Besides, the GPS signal

31、loss problem may disturb the continuity of locations in a trajectory, and thus produce false negative results.2.2. Semantic place recognitionTo assign semantic meanings to physical places, location-aware applications such as Reno HYPERLINK l page11 15 and Connecto HYPERLINK l page11 16 allow users t

32、o manually input meaningful labels by interacting with their inter-faces, and this information may be further contributed to a global place database for reuse. Apparently, manual labeling requires a great calibration effort, and thus does not scale well when the number of places increases. Some exis

33、ting works transform phy-sical locations to semantic labels by using reverse geo-coding techniques HYPERLINK l page11 17, HYPERLINK l page11 18. However, the return of reverse geo-coding services (e.g., Google Map) for a given location is its postal address, which is often difficult to interpret. To

34、 acquire colloquial place labels, customized POI (Point of Interest) databases which store the physical locations and semantic meanings of landmarks are used HYPERLINK l page11 13, HYPERLINK l page11 20. However, these databases only contain the infor-mation of public places without personal meaning

35、. For example, a users home or workplace cannot be identified by querying these databases. Besides, even the same place may have different per-sonal meanings to different users, e.g., a customer has dinner in a restaurant whereas a cook works there.To estimate personal meanings of places, Liao et al

36、. HYPERLINK l page11 26 used relational Markov networks (RMN) to recognize high-level human activities associated with significant locations. The RMN model is extended to incorporate a variety of features including temporal information, spatial information, and global constraints for loca-tion-based

37、 activity recognition. This approach estimates the semantic meanings of activities performed at each individual sig-nificant location. However, the semantic meaning of a place is more sophisticated than that of activity, and it often requires to be visited multiple times before its semantic meaning

38、can be accu-rately estimated. On the other hand, our approach firstly extracts physical places which may be visited multiple times, and then feeds the mining results (which capture the statistical temporal, spatial and sequential features of these places) into the semantic place recognition model. W

39、e have also exploited temporal and spatial information for estimating personal meanings of places in our previous work HYPERLINK l page11 31. Since people usually have certain sequential regularities to visit different types of places, we use sequential patterns as additional information to further

40、improve the estimation accuracy in this paper.In conclusion, we summarize the difference of our method and the existing work in HYPERLINK l page11 Table 1.A summary of the difference of our method and the existing work.3. System architecture HYPERLINK l page11 Fig. 1 gives an overview of the system

41、architecture of our approach, including two major steps, i.e., physical place extraction and semantic place recognition. Given the GPS trajectories of a specific user, our approach firstly uses a hierarchical clustering algorithm to extract the physical places (from GPS trajectories to visit points,

42、 and from visit points to physical places), whose par-ticular properties are calculated at the same time. Then, different techniques are employed to explore the place properties for esti-mating the personal semantics of the extracted physical places, i.e., classification technique for temporal featu

43、res, geographic database for spatial features, HMM (Hidden Markov Model) for sequential features. Physical place extractionThis paper proposes a hierarchical clustering algorithm to extract physical places where the users have visited based on a three layered model. As shown in HYPERLINK l page11 Fi

44、g. 2, the lowest level is the GPS trajectory which contains all the GPS points sorted by timestamp (see HYPERLINK l page11 Definition 1), the middle level contains all the visit points (see HYPERLINK l page11 Definition 2), and the highest level represents the physical places (see HYPERLINK l page11

45、 Definition 3). The hierarchical clustering algorithm takes the GPS trajectory as input and conducts a time-based clustering to identify visit points, and then extracts physical places from these visit points based on a distance-based clustering.(Definition 1. ) GPS point and GPS trajectory: a GPS p

46、oint is a pair p(lng, lat), representing the longitudelatitude location. A GPS trajectory is a sequence of pairs Traj o(p0, t0),(pn, tn)4, in which pk is a GPS point and tk (k0,n) is a timestamp (0rkon, tk otk 1).(Definition 2. Visit point: a visit point is a triple VP(p, tin, tout), where p is a GP

47、S point, tin and tout are timestamps, and the visit point stands for a location p around which the user stays for longer than a time threshold (i.e. tout tin 4time).(Definition 3. ) Physical place: a physical place is a collection of visit points PVP1,VPn, in which VP1.p, ,VPn.p are close to each ot

48、her.PlacesVisit PointsGPS TrajectoryFig. 2. A three-layered model for physical place extraction.4.1. Extracting visit pointsWe use a time-based clustering algorithm to incrementally form location clusters (i.e., a set of GPS points that are spatially close to each other) and identify visit points fr

49、om these clusters. The criterion of existing time-based clustering algorithm for considering a cluster to be a visit point is that the clusters time duration should be longer than a threshold time HYPERLINK l page11 11. However, this criterion may not work well for GPS trajectories with discontinuou

50、s points sampling due to the GPS signal loss problem. For example, if a user enters a large building from one side A and leaves from another side B (as shown in HYPERLINK l page11 Fig. 3(a), the GPS signal will be blocked and the GPS points recorded around A and those recorded around B will form two

51、 different clusters (i.e., clusters I and II) because the locations around A are not close enough to those around B. Apparently, neither I nor II can be identified as visit point even if the person stays a long time in the building, and thus produce false negative results. This problem may also exis

52、t even when the user enters and leaves the building from the same side, because GPS device often require a period of time to receive signal when the user may leave the building for a relatively long distance (as shown in HYPERLINK l page11 Fig. 3(b). We call this problem as the entrance and exit dev

53、iation problem.To counter this problem, we refine the existing time-based clustering algorithm to adapt to the discontinuous characteristics of GPS trajectories. The algorithm (as depicted in HYPERLINK l page11 Algorithm 1) works in an incremental way and processes the GPS points along the time axis

54、. In the algorithm, CC and PC are the current cluster and the previous cluster, respectively. For each GPS point in T, the algorithm compares the distance between it and the centroid of the current cluster with cluster_distance. If the distance is less than cluster_distance, this GPS point is added

55、to the current cluster (lines 24). Otherwise, the algorithm checks the time duration of the current cluster. If the time duration is longer than time, the cur-rent cluster is considered as a visit point (lines 68). If the time duration is not long enough, the algorithm does not simply ignore it, but

56、 checks the time interval (i.e., the interval between the exit time of the previous cluster and the enter time of the current cluster) and the distance (i.e., the distance between the centroids of the previous and the current clusters). If the time interval is longer than time and the distance is le

57、ss than tolerated_distance, the algorithm combines these two clusters and treats the result as a visit point (lines 1012).Algorithm 1. Visit Point ExtractionINPUT: GPS trajectory T, clustering distance threshold cluster_distance, time threshold time, and tolerated distancethreshold tolerated_distanc

58、eOUTPUT: A set of visit point VPcurrent cluster CC , previous cluster PC, VPfor each GPS point pi in T doif distance(CC, pi)ocluster_distance thenAppend pi to CCelseif duration(CC)4time thenAppend CC to VPCC , PC elseif interval(CC, PC)4time and distance(CC,PC)otolerated_distance thenCCcombine(CC, P

59、C), and Append CC to VPPCelsePCCCCCend forWhen using the algorithm in practice, the parametertolerated_distance should always be set larger than cluster_distance inorder to tolerate the entrance and exit deviation problem. By using tolerated_distance, the entrance and exit deviation problem can be g

60、reatly alleviated when the GPS sampling is interrupted for a long period of time between two areas which are not far from each other. As the example shown in HYPERLINK l page11 Fig. 3, cluster I (i.e., GPS points around the entrance) and cluster II (i.e., GPS points around the exit) can be combined