{'fraction_non_alphanumeric': 0.029365354877394514, 'fraction_numerical': 0.007558304667529271, 'mean_word_length': 4.7987922042272855, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Potential destination prediction for low predictability individuals based on knowledge graph

Individuals with low predictability are common due to observation limitation, which shows random movement patterns and makes it difficult to perform mobility prediction (e.g., destination prediction). In this paper, we develop a new knowledge graph-based framework (PDPFKG) for destination prediction of low predictability travelers, especially those potential destinations a traveler never visits in history, by considering trip association relationships between them. We first construct a trip knowledge graph (TKG) to model the trip scenario by entities (e.g., travelers, destinations and time information) and their relationships, in which we introduce the concept of private relationship for complexity reduction. Then a modified knowledge graph embedding algorithm is implemented to optimize the overall graph representation. Based on the trip knowledge graph embedding model (TKGEM), the possible ranking of individuals’ unobserved destinations to be chosen in the future can be obtained by calculating triples’ distance. Empirically. PDPFKG is tested using an anonymous vehicular dataset from 138 intersections equipped with video-based vehicle detection systems in Xuancheng city, China. The results show that (i) the proposed method significantly outperforms baseline methods, and (ii) the results show strong consistency with human behavioural pattern of choosing potential destinations. Finally, we provide a comprehensive discussion and respond to the innovative points of the methodology.


Introduction
Destination prediction has always been the focus of research in the transportation field. As the increasingly rapid development of surveillance technologies in recent years, massive mobility data at individual level can be passively collected from both invasive and non-invasive detection systems. Such rich data after long-term observation enables traffic engineers to explore and propose many destination prediction approaches for different applications. However, things will be more difficult if only a short period data is available or at the early stage of observation. According to Gonzalez et al. (2008), the assumption that human mobility follows certain dynamic patterns is feasible only when long-term observation is available. In other words, under limited observation conditions, travelers tend to show random or accidental travel behaviors, which makes their destination less predictable statistically. Imagine a traveler with only several trips (like 3) and different destinations. The destination prediction of its next trip seems tough since there are too few records to mine the traveler's mobility patterns. Besides, potential destination prediction could be another problem. Potential destination refers to the location that a traveler has never visited before but could be observed in the near future. Potential destinations are widely existing among travelers, even regular ones, especially when the observation period is limited (see data analysis in Section 5.1). Potential destination prediction of low predictability travelers is of great importance as it benefits a large number of urban computing applications, like short-term hot spot prediction, personalized location recommendation, and dynamic OD estimation. Furthermore, it helps to determine the limits of predictability for low predictable human mobility, while the upper limit of predictability of high predictability individuals was discussed by Song et al. (2010); Kulkarni et al. (2019).
Potential destination prediction of low predictability travelers aims to predict the potential destinations of an individual based on limited historical records from the whole travelers with low predictability. Although many researchers have extensively studied in the field of destination prediction, few existing studies have considered travelers with low predictability, or travelers' potential destination under short-term observation period. Most of previous research pay little attention to potential destinations (Zhao et al. (2018), Ebel et al. (2020), Manasseh & Sengupta (2013)), or even ignores them totally (Gambs et al. (2012), Lu et al. (2013)). In Hariharan & Toyama (2004), trip destinations were just defined as the places travelers have visited. Krumm & Horvitz (2006) is the first work that introduces a concept of new destination with a similar meaning of potential destination, in order to improve overall prediction performance. However, no validation is performed on them. Since then, many related works have taken potential destination or other similar concepts into consideration, but they all failed to directly make prediction for low predictable individuals. One way is that most previous studies focus on implementing prediction by mobility pattern extraction or regularity analysis based on highly predictable individuals, where low predictable individuals as a minority receive less attention (Zhao et al. (2018); Rossi et al. (2019); Manasseh & Sengupta (2013)). In Zhao et al. (2021), although it aimed at predicting accidental destinations, in fact destination distribution for its individuals presented strong regularity, and all historical trips were taken into consideration in the research scenario. Additionally, in some research, travelers with relatively few trips are treated as abnormal individuals to adapt the proposed prediction methods better. For instance, Imai et al. (2018) filtered out individuals whose number of trips is less than 5. Under such settings, the majority of travelers to be predicted are highly predictable, and possible destinations were almost completely observed. As a result, there was no need to predict potential destinations anymore.
As our goal here is to predict potential destinations for individuals with low predictability, in this paper, we propose a generic framework that can be adapted to all kinds of mobility data under such conditions. To achieve this, the first problem facing us is how to enhance the predictability of a traveler when mobility pattern extraction is almost impossible for data sparsity. According to Gonzalez et al. (2008), human travel patterns shared inherent similarity despite of the diversity among their travel history. This motivates us to leverage useful information from other travelers, instead of a single individual. In this way, an unpredictable individual will become a predictable one as part of the whole. Then we need to deal with other remaining 3 challenges.
(1) How to organize all individuals' mobility data into one structure so that they can easily learn effective information from each other. (2) How to develop a proper optimization algorithm that can implement an overall optimization solution.
(3) how to design meaningful metrics to validate the prediction results. To deal with these problems, we propose a Potential Destination Prediction Framework based on Knowledge Graph (PDPFKG). Firstly, we present a trip knowledge graph (TKG) schema to organize the individual-level mobility data into a well-defined structure, in which the fundamental objects (e.g., travelers, destinations and time information) in the transportation field are modeled as entities with relevant relationships among them. Then, we adopt TransH, a popular knowledge graph embedding model proposed by Wang et al. (2014), on TKG with modifying the training strategy and objective function. Afterward, the entities and relationships in the TKG are all projected into a vector space and their positions are optimized based on the associations among them. In this way, the possibility ranking of vehicular (traveler's) potential destinations can be estimated by their core triples' distances. Furthermore, the results are improved by integrating the statistical information from the original data. Finally, we design three metrics by considering the prediction ranking as a discrete distribution to evaluate the correctness and effectiveness of the proposed framework, including ranking confusion degree, smoothing degree, and concentration degree.
To validate the framework we propose, we apply it to an anonymous dataset from 138 intersections in Xuancheng city, collected from a video-based detection system based on automatic vehicle identification (AVI) technology provided by the Chinese local transport bureau. We evaluate the ranking of potential destinations that the travelers have never been to in the training data through designed metrics. Experiment results demonstrate that the final ranking result is highly consistent with the desired choice pattern of potential destinations.
In summary, this paper mainly makes the following contributions.
• We develop a generic framework based on knowledge graph for potential destination prediction of individuals with low predictability (called PDPFKG in this paper).
• We customize PDPFKG to tackle a set of challenges, including a trip knowledge graph schema for mobility objects' association organization, an introduction of private relationships for complexity reduction, an adapted embedding model for learning relationships information and a statistic-integrated scheme to improve the prediction results.
• We design three metrics to evaluate the correctness and effectiveness of the proposed framework, and we conduct extensive experiments based on a city-scale AVI dataset.

Literature review
During the last two decades, a great deal of work has been devoted to forecasting trip destination and human mobility. This section aims at reviewing recent studies exploring destination prediction problem from two aspects: data condition and method. In Table 1, the summary of reviewed studies is presented, where the middle three columns (scenario, data type, and data size) show the data condition of studies and the last column illustrates the used method. Specifically, the scenario column indicates the specific scene of the study; the data type column shows whether the study used OD-only data (e.g., smart card data) or trajectory records (e.g., location-based GPS data and bluetooth data); and the data size column shows time span or average number of records for each individual. Most of previous studies mainly focus on prediction of highly predictable travelers. In general, a longer observation period means higher predictability of individuals (Gonzalez et al. (2008)). As shown in Table 1, the majority of existing studies were based on long-term observation, which results in adequate records and guarantees the majority of individuals have high predictability. Besides, some studies carried out data processing to make prediction individuals sufficiently predictable, which have certain mobility patterns that can be mined. For example, Manasseh & Sengupta (2013); Neto et al. (2018) limited prediction objects to specific highly regular individuals. Zhao et al. (2018) selected users with at least 60 active days of transit usage, which excluded occasional users and short-term visitors. Zhao et al. (2021) excluded individuals whose active days were less than 2. Imai et al. (2018) filtered out individuals whose trip number was less than 5. Wang et al. (2020) excluded trip records with relatively shorter travel time. Liang & Zhao (2021) excluded trips of individuals whose routing patterns are different from target individuals. Alvarez-Garcia et al. (2010) and Chen et al. (2019) suggested the trip regularity of individuals existed under their observation period.
Recently, some studies tried to make predictions for individuals with sparse data caused by limited observation. For instance, Wang et al. (2017a) predicted the moving destinations using sparse dataset. Xue et al. (2013) forecast destinations by solving data sparsity problem. Xue et al. (2015) handled the problem of data sparsity for destination prediction by sub-trajectory synthesis. Imai et al. (2018) predicted destinations at an early stage when the destinations had not been fully observed. Zhao et al. (2021) challenged destination prediction for occasional trips of individuals, including ones with few trips. Individuals with sparse data are considered more challenging to predict because of lower predictability, and lower prediction accuracy can be tolerated.
Existing studies based on sparse data mainly used trajectory data (Wang et al. (2017a); Xue et al. (2013Xue et al. ( , 2015; Imai et al. (2018)), whose information is more abundant than OD-only data for the process of mobility is recorded. Thanks to this, the above researches deal with sparse data through trajectory synthesis and characteristics extraction. Zhao et al. (2021) used OD-only data, but there are a large number of regular travelers in its dataset, except for partial inactive individuals. Besides, it excluded individuals with few activity days, whose predictability is very low. According to the above analysis, existing studies tend to make predictions for highly predictable individuals whose possible destinations are almost totally observed, while low predictability individuals have not been well considered yet (especially for OD-only data type).
Previous studies paid little attention to potential destinations of individual's trips. This is partly because all possible destinations of individuals are almost entirely observed under long-term observation conditions, for which potential destinations prediction hardly affect the overall results. For instance, Lu et al. (2013) achieved high prediction accuracy ignoring potential destinations. On the other hand, it is due to the limitation of existing prediction methods.
As shown in Table 1, the methods for destination prediction have been dominated by data-driven models (e.g., neural network-based), which became popular with a great quantity of data becoming available. Most of these models adopt supervised learning, and more training data is better, for which sufficient data is required. Considering the principle of these models, they learn the pattern of data and tend to reproduce data that have been trained. These make them poor predictors for sparse data and data without patterns, while they are unable to or hardly predict untrained data. Thus these models are neither good at dealing with individuals with low predictability (data not regular and sparse), nor good at predicting potential destination (unobserved). For the above reasons, some studies ignored potential destinations when predicting. For example, Lu et al. (2013); Gambs et al. (2012), which based on Markov Chain model, can not predict locations that users have never visited before.
There were some researches considered potential destinations, but their major attention was still put on observed ones, and no mechanism was specially developed for potential destinations.  Zhao et al. (2021)), without establishing and modeling relationships among individuals. Since none of these studies have validated the prediction results of unobserved destinations, their performance in potential destination prediction is still confusing. In summary, there is no research yet to reveal the pattern of individuals choosing potential destinations.

Concepts and notations
Following the previous study (Ji et al. (2021)), we use G to represent a knowledge graph, and it can be expressed as G = {E, R, F } where E, R and F are sets of entities, relationships and facts. A fact is denoted as a triple (h, r, t) ∈ F , where h and t are elements of the entity set E and r is the element of R. For the triple (h, r, t), r generally has a direction from h to t. The triple with a directional relationship shown in Fig. 1(a) can be represented as (h : Entity) − [r : Relationship] → (t : Entity), in which entities represented by h and t are called head entity and tail entity, respectively. Triple is the unit structure in knowledge graph and the information expressed by it is called fact. A specific triple expresses a specific fact.
The direct association of entities can be expressed by triples, while the indirect association information of them can be expressed by association path (or meta-path by Sun & Han (2012)) in knowledge graph. Entities that are not directly related but can be associated with one or more other entities are considered to be indirectly associated. The path that makes these entities associated is called the association path. It can be considered as a chain of multiple connected triples, or a sequence of alternating entities and relationships as shown in Fig. 1(b). The formation of an association path depends on different triples containing the same entity, and they should be the head entity and tail entity, respectively.
The relationships of a knowledge graph can be divided into four types of complexity: 1 − 1, 1 − N , N − 1, and N − N (N > 1). The former represents the number of head entities connected to the relationship, while the latter represents the number of its tail entities. For example, the relationship of 1 − N type means that there is only one head entity and its tail entity is multiple, as shown in Fig. 1(c). The relationship of 1 − 1 type that has only one head and one tail entity is called simple relationship. Relatively, 1 − N , N − 1 and N − N are called complex relationship, of which N − N is the most complex type, as shown in Fig. 1(d). For a complex relationship, its complexity depends on the quantity of its head and tail entities, i.e., the value of N . The more the quantity, the more complex it is.

Problem description
As shown in Fig. 2(a), based on a certain observation period, we define the possible destinations of an individual, which is unobserved during observation as a potential destination for the individual. On this basis, the problem of this study can be described by Fig. 2(b), and its formal description is as follows. Note the set of all locations as Z. For an individual v, based on a short-term observation, note the set of locations chosen as the destination by v during observation as Z o . For each location in Z − Z o that v have not visited, the method will give its ranking of possibility that v will visit it in the future.

Trip knowledge graph construction
The trip data we obtained is displayed in tabular form, where each record describes the information (e.g., vehicles, origins, departure time and destinations) of one trip made by a user. Though it benefits trip information retrieval and storage, the data is separate. As mentioned in Section 2, the similarities of travel patterns among different travelers can be leveraged to improve the prediction performance. To effectively learn the association information with each other, we propose to apply knowledge graph to organize all the data into one structure where the mobility-related objects are properly connected by designing a trip knowledge graph schema. Specifically, it includes two steps: entity extracting and relationship building.

Entity extracting
At this step, we have to decide which types of entities should be included in trip knowledge graph. As our goal is to infer potential destinations on a domain-specific knowledge graph, the extracted entities should serve the interests of the prediction task. Further, to make our graph model more general with all kinds of mobility data, we only consider the most common and available elements.
First, a type of entity representing the traveler's (vehicles) identity is required for prediction at the individual level, and we denoted it as V eh_id. Then each entity of V eh_id corresponds to a specific individual. Similarly, the element of spatial geography is also needed to represent the destination and origin of trips. Next, we considered the information relevant to the choice of trip destinations. Yuan et al. (2013) pointed out the significance of the time factor in the points of interest (POI) recommendation task. In addition, Zong et al. (2019) boosted the effectiveness of its model on the next location prediction task by adding weekday versus holiday information. Therefore, both the factor of POI and trip time are extracted as entities.
In summary, we determine the entity types whose meanings are shown in Table 2, where the entity of Zone is a spatial concept used to represent the destination and origin of the trip (see Section 5.1 for detail). When extracting entities, we need to ensure that they are consistent with the real world. In other words, different entities must uniquely represent one actual object of the real world. For example, a zone only responds to one entity of Zone, although it was visited by different individuals and appeared in multiple records.

. Relationship building
Relationship building is to describe the relationship of different types of entities. According to Section 3, entities and the relationship between them form a triple, which describes a fact. Hence, relationship building is essentially constructing various triples for describing facts. Therefore, what facts should be expressed is the issue in this step. According to entities extracted in Table 2, the facts that need to be described in trip knowledge graph can be divided into two categories: 1) Individual historical trips, including historical trip destinations, etc.; 2) Traffic zone contains POI. These require building relationships between V eh_id and T ime_span, Day_nat, and Zone respectively, as well as Zone and P OI.
In Section 3, we have introduced that the relationships have different degrees of complexity. It has no impact on humans' understanding but for knowledge graph embedding. To handle complex relationships, embedding models will also be more complex. In addition, the more complex a relationship is, the higher the dimension required to describe it. On the other hand, the embedding dimension of relationships with different types is usually the same. Therefore, the principles are as follows when building relationships. 1) Balance the complexity of different type relationships; 2) Avoid excessive complexity of relationships; 3) Make the complexity of relationships independent of the data scale. These three principles will ensure: 1) The optimal dimension of each type of relationship is consistent; 2) The relationship can be expressed in finite dimensions; 3) The model is migratory across datasets.
For the relationship between entities Zone and P OI, a common way is to build the relationship Has_P OI between them. Then Has_P OI is a complex relationship of type N − N since a traffic zone may contain multiple POIs, while one kind of POI may be distributed in different traffic zones. But its complexity will not reach an unacceptable level for the number of both its head and tail entity is small. In addition, the complexity is stable for the fact described by it is relatively constant.
For building relationships between V eh_id and the other three types of entity, we take V eh_id and Zone as an example. Following the way of defining Has_P OI, the relationship Choose_D will be built between V eh_id and Zone. Human beings can interpret this, but it violates all of the principles of relationship building. First, although both of Has_P OI and Choose_D are of type N − N , Choose_D is much more complex than Has_P OI for its number of head and tail entities is not at the same level with Has_P OI. Second, its complexity varies with the scale of the trip data. For example, as more individuals are considered, the number of its head entities increases accordingly, leading to increased complexity. Lastly, when the number of individuals considered is huge, the dimension required to express it will become unacceptable. To address the issue, we propose the concept of private relationship. We define the Choose_D_id as a group of relationships. Each relationship corresponds to a specific individual, i.e., the head entity of each relationship is only one entity of V eh_id. In other words, each individual has a private relationship of Choose_D_id. The complexity type of Choose_D_id is reduced to 1 − N versus Choose_D, and it's not excessive in complexity for the number of tail entities (Zone) is small. More importantly, it is independent of data scales. For instance, when the quantities of individuals change, the number of relationships of Choose_D_id changes accordingly, while the complexity is hardly affected. In addition, Choose_D_id is closer to Has_P OI in complexity compared to Choose_D. The same problem exists in building relationships between V eh_id and other types of entities like T ime_span, and we also adopt private relationships to handle them.
So far, we have completed the construction of the trip knowledge graph (TKG). The structure of TKG is shown in Fig. 3 and all types of triple and facts described by them see Table 3. The triple marked with * is called core triple, which is the triple that performs the prediction. In TKG, all types of entities have an association path, and the microscopic association between different types of entities is shown in Fig. 4.

Trip knowledge graph embedding
In TKG, information about all individuals' trips has been associated. But it is described by natural language that it cannot be computed and does not have the ability to predict. This section will use a modified knowledge graph embedding algorithm to map TKG to a continuous space and obtain parametric expressions of its entities and relationships.

Graph embedding models
The purpose of knowledge graph embedding is to map the entities and relationships in a continuous space. After embedding, entities and relationships of knowledge graph will have a parametric representation and then the knowledge graph is calculable. The translation model is a classical category of models for implementing knowledge graph embedding, including many specific models. All these models consider the tail entity of the triple as a translation of the head entity through relationships. Their differences are mainly in the complexity of the models, and it is reflected in the different number of parameters, which affects the ability of the models to handle complex relationships. In general, the more complex the model the better it is able to handle complex relationships, while the simplest TransE model can only handle simple relationships. Next, we will introduce the generic models of TransE and TransH. The former can most directly represent the principle of the translation model. And the latter deals with complex relationships in a relatively easy way that matches the structure of TKG well. For a more comprehensive understanding of graph embedding algorithms and translation models, the Wang et al. (2017b) can be consulted.
TransE model is the first and the classic algorithm of translation models for knowledge graph embedding. It regards the relationship in the knowledge graph as a translation vector between entities. For each triple like (h, r, t), TransE regards l r , the vector representation of relationship r, as the translation between the head entities' vector l h and tail entities' vector l t . Based on this idea, we can also regard l t as the translation of l h through relationship l r . As shown in Fig. 5, for a triple (h, r, t) which is short for (head) − [relationship] → (tail), the goal of TransE is to iteratively update the parameters of vector l h , l r , l t as much as possible so that the formula l h + l r ≈ l t holds. The loss function of the TransE model is defined in Eq. (1). In the geometric sense, |l h + l r − l t | L1/L2 is the distance from the head entity of the triple (h, r, t) to the tail entity through the translation of the relationship r. So, the result of Eq. (1) is also considered as the distance of the triple. TransE is the most concise form of the translation models, in which there is only one continuous space and where entity and relationship have a unique representation. However, it is difficult to handle complex relationships. To solve the problem, TransH was proposed. It is the first proposed translation model that can handle complex relationship types and its generic model was proposed by Wang et al. (2014). There is only one type of parameter that hyperplane was added in TransH compared to TransE and it is the most concise of the translation models that can handle complex relationships. TransH enables the same entity to have different representations in triples composed of different relationships by introducing hyperplanes. As shown in Fig. 5(b), for the relationship r, TransH model uses the translation vector l r and the normal vector w r of the hyper-plane to express it at the same time. As for a triple (h, r, t), TransH model projects the head entity vector l h and the tail entity vector l t along the normal to the hyper-plane corresponding to the relationship r, by which l hr and l ht will be obtained and their calculation equation is shown in Eq. (2, 3). On this basis, the loss function(also the calculation of the triple distance) of TransH model is changed to Eq. (4).
The negative sampling strategy is commonly adopted when training models to improve the efficiency of training and enhance distinguishing ability, such as Wang et al. (2020), especially for translation models. The triples constructed in the knowledge graph based on observed data are considered the correct triples or positive samples. Other triples are generally called false triples or negative samples. Unlike positive samples derived from historical data, negative samples need to be constructed artificially. The general method of generating the set of negative samples is to randomly replace one of the head entities, relationship and tail entity of positive samples with other entities or relationships. Denote the negative samples generated by this method as S − . Then it can be described by Eq. (5).
Most translation-based models typically adopt the negative sample strategy with their optimization objective function shown in Eq. (6) where S is the set of positive samples, S − is the set of negative samples and γ is the acceptable distance between the positive and negative samples.
4.2.2. Analysis and optimization of knowledge graph embedding for trip knowledge graph According to Eq. (4), (6), the optimization objective of translation-based embedding model is for a single triple or a pair of triples (a positive sample and a negative sample). Nevertheless, overall optimization can be achieved when implement it on TKG. Overall optimization means that the optimization process proceeds in the direction of considering the decreasing distances of all triples, and eventually converges to the overall optimum, not a single triple. The following will explain the reason.
Through Section 5.1 we know that the association path is formed by multiple triples. Then we consider the following association path: which is formed by triple f m : (h m , r m , e c ) and f n : (e c , r n , t n ). If the vector representation of entities and relationship of f n have been adjusted during training, triple f m will be affected simultaneously because the tail entity e c of f m serves as the head entity of f n . Likewise, the adjustment of the f m triple affects the triples that form associated path with it. That is, The training of a triple will affect all triples of the associated paths it forms. Through the introduction of Section 4.1 and Fig. 4, almost all entities in TKG have association paths among them. Thus, the update of one triple will affect the parameterized representation of the others. So, although the optimization objective is for a single triple, benefiting from the structure of TKG, the training will converge towards the overall optimal. The interplay of expressions of different entities and relationships realizes information transfer, enabling training to learn associative information.
Overall optimization can be achieved no matter which translation-based model is chosen. In this paper, we adopt TransH since it can handle the complex relationships in TKG, and it is concise with fewer parameters. In addition, TransH adopts the semantics of trips well. For example, a traffic zone generally contains multiple POIs, making individuals use them in different ways. It implies the meaning of traffic zones to individuals varies. So traffic zones should be represented differently in triples formed by different individuals, which can be handled by hyperplane of the relationship.
General embedding models were proposed for generic knowledge graph, and we find it doesn't match well with TKG (a domain-specific knowledge graph) and our task. Denote the triple of (Zone) − [Has_P OI] → (P OI) type as F poi and others in Table. 3 as F trip . F trip is constructed based on trip data, which is usually of a larger quantity. Whereas only relatively small number of triples contained by F poi . So the scale of F poi and F trip is imbalanced. The triple that (V eh_id) − [Choose_D] → (Zone) of F trip and F poi have a public type of entity Zone. If no adjustment is made to the training strategy, the representation of Zone entities will be mainly dominated by the (V eh_id) − [Choose_D] → (Zone), leading to the related information between traffic zones and POI being harder to learn. This will reduce training efficiency significantly. To solve this problem, we can do a pre-train for F poi , which can make a better initialization of Zone. On the other hand, it is also feasible to augment F poi so that it has a scale comparable to other type triples before training.
Second, we find negative sampling strategy does not apply to TKG for the potential destination prediction task. According to Eq. (6), the distance between negative samples is enlarged while it is reduced for positive samples during training. It means the negative sample is considered the opposite of the positive sample, or else it would be misleading for training. This requires the fact described by negative samples should be truly false. In other words, most facts should be observed and contained in the knowledge graph, i.e., the knowledge graph is almost complete. However, in TKG, triples describing individual historical trips are constructed by trip data collected under short-term observation. It means there are a large number of triples absent from TKG because they have not been observed, not for it is false. Thus the TKG is far from complete, and no information help telling whether triples that are not in TKG are really negative samples. Potential destination prediction is essentially predict unobserved facts. If the true triples describing the unobserved fact is regarded as negative samples during training, it will greatly affect the model's performance. For example, (V eh_id : v i ) − [Choose_D_i] → (Zone : z b ) may be considered and generated as a negative sample if v i has not chosen z b as the destination in history. However, z b may be a potential destination of v i , so it would be a disaster if the triple was trained as a negative sample. To adopt to our data and task, we eliminate negative sampling strategy and modify the optimization objective to Eq. (7). The idea of modified optimization objective is describing only the observed facts and considering that when the distance of a positive sample is less than γ that setting for preventing overfitting, then the fact is considered to be well expressed by the model without adjustment.

Potential destination prediction
Trip knowledge graph embedding model (TKGEM) will be obtained through implement the modified knowledge graph embedding algorithm (see Section 4.2.2) on TKG. This section will introduce the potential destination prediction based on TKGEM.
According to Section 4.2.1, the training is actually a process of decreasing the distance of positive samples. That is, TKGEM portrays the possibility that the fact is established by the distance of the triple that describes it. When the model converges, drawing on the knowledge graph completion task, we argue that the possibility of a fact is negatively correlated with its triple distance. Then the prediction flow is shown in Fig. 6. First, the set of potential destinations candidate Z p of each individual needs to be identified. According to the definition of potential destinations, each location (traffic zone) that has not been chosen as the destination of the individual is possible to be its potential destination. Denote the set of all traffic zones as Z. For each individual, denote the set of observed traffic zones chosen as the destination as to Z o , which can be obtained from its historical trip data. Then the Z p of the individual can be calculated by Eq. (8).
Among the triple types shown in Table 3, the core triple that (V eh_id)−[Choose_D_id] → (Zone) describes the fact that an individual chooses a traffic zone as its destination. Therefore, its distance can measure the possibility of the fact that the individual (represented by the head entity) chooses the traffic zone (represented by the tail entity) as a destination. If the traffic zone of the triple belongs to its Z p , the distance of the triple portrays the possibility that the individual will choose the traffic zone as a destination in the future, which is the foundation for potential destinations prediction. Hence, for an individual to be predicted, the distance of its core triples formed by zones of its Z p should be calculated. Specifically, take the individual's entity (V eh_id type) and the traffic zone (Zone type) as the head entity and tail entity respectively. Take the individual's private relationship of [Choose_D_id] type as the relationship. Then a core triple of the individual is formed, and its distance can be calculated. (see Algorithm 1).
There is no quantitative correlation between the distance of the triple and the probability that the fact it describes holds. Nevertheless, we can give the ranking of the possibility based on the qualitative relationship between them. That is the smaller the distance, the higher the probability. For example, for individual v n , denote distances of two cores triples c ni = (V eh_id : v n ) − [Choose_D_n] → (Zone : z i ) and c nj = (V eh_id : v n ) − [Choose_D_n] → (Zone : z j ) as d i and d j respectively. It is hardly to give quantitatively the probability that the fact described by c ni or c nj according to the distance, but what can be determined is the fact described by c nj is more likely to be established if d i > d j . In other words, v n is possible to choose traffic zone z j as its destination in the future. Based on this idea, the ranking of each unobserved traffic zone can be obtained based on the distance of their corresponding core triples.
The overall flow of the above individual potential destination prediction can be summarized as Algorithm 1. It describes the process of predicting the possible ranking of a traffic zone for an individual based on TKGEM.
Algorithm 1: Algorithm of potential destination prediction of an individual.
Input: Individual identity: v n ; TKGEM: M e ; Zone to be ranked: z j ∈ Z p Output: The possible ranking of z j for v n given by M e : k e j Get Z p of v n ; h n ← Entity (V eh_id : n); if d < d j then k e j ← k e j + 1; Return k e j TKGEM is supposed to predict based on overall association information. It cannot be obtained by statistics on the data or statistical models. In other words, the information learned by TKGEM is of a different dimension from statistical information. To confirm this, while utilizing statistical information to enhance the predictive effect of TKGEM, we introduce two other ranking ways of traffic zones: hotness ranking and combined ranking. The former is obtained by counting the frequency of different traffic zones chosen as destinations by all individuals based on the observed data and ranking them. The ranking of the traffic zone with the highest frequency is 1. For combined ranking, it combines the ranking given by TKGEM and hotness ranking. The algorithm flow to get combined ranking is shown in Algorithm 2.
So far, we have introduced three ranking ways: (1) Ranking given by TKGEM, which we call PDPFKG embedding ranking (PDPFKG-ER); (2) Hotness ranking (HR) given by statistical information; (3) Combined ranking (PDPFKG-CR) obtained by Algorithm 2. All of their prediction performances will be demonstrated and discussed in the experimental section.
Algorithm 2: Algorithm of calculating the combined ranking.
Input: Zone to be ranked: z j ∈ Z p Output: The combined ranking of z j : k c j L n ← ∅; for z j in Z p do k e j ← Algorithm 1; Get the hotness ranking of z j , denote as k h j ;

Dataset description
In this section, we performed the proposed method with a real-world dataset from Xuancheng, China.

Data preparation
The original trip data was collated by the automatic vehicle identification systems deployed in the city road network. It can record the vehicle's activity passively on the road network and its identity. The road network and the AVI systems distribution in Xuancheng are shown in Fig. 7. The fields of the original data are shown in Table 4. The traffic zone proposed in Wang et al. (2021) is used to describe the origin and destination of trips with the total number of 191. There are multiple points of interest (POIs) inside of the traffic zones, and this information is publicly available on the Internet.

Field
Description Vehicle_id The id of vehicle, which is the identification of the vehicle. Date The date of the trip. Ftime The departure time of the trip. Fzone The origin of the trip. Tzone The destination of the trip.
We first extract the first one week data from original data to simulate a short-term observation condition. To further ensure our scenario is consisted by low predictability individuals totally, those with strong regularities under such conditions are excluded. As a result, 95, 509 individuals are selected and formed the target group for prediction, which accounts for 81.56% of the total.

Data analysis
This section mainly shows the sparseness and randomness of trip data of the target individuals. First, the trip frequency distribution of these individuals is shown in Fig. 8. Meanwhile, we count the percentage of accidental destinations and potential destinations of target individuals. The accidental destination refers to the locations that a traveler has visited while lacking observation in the near future.
Denote the percentage of accidental destinations and potential destinations of an individual as P o and P f respectively. They are related to the observation period T o and the period in the future T f considered. The value of T o can be determined as the observation period in our data scene is one week. Hence, we show P o and  Table 5. Besides, we demonstrate the distribution of the P o and P f of target individuals with T f = 14 days by Fig. 9.

Percentage of accidental destination Percentage of potential destination
According to Fig. 8, the majority of individuals had less than 10 trips observed. For more than 20% of individuals, no more than two trips were observed. It means the amount of individual data is extremely limited. For a few individuals with more observed trips, the observation is also not enough for the randomness of their trip is strong, and many of their possible destinations are still not observed. On the other hand, Table 5 and Fig. 9 illustrate that individuals have a large proportion of both accidental destination and potential destination, indicating the destination choosing behaviour of individuals seems to be very random. Besides, a high percentage of potential destinations shows that potential destination prediction is worth researching under limited observation and confirms individuals' observation is insufficient in our data scene.

Experimental setting 5.2.1. Training and validation data splitting
The individuals we studied are the target individuals screened in Section 5.1.1. Five weeks data from 05/08/2019 to 08/09/2019 are used, of which only the first week of data is used for constructing the trip knowledge graph and training (embedding), containing 1, 047, 061 trip records. The remaining data was used for validation, of which two weeks are used for the evaluation (Section 5.5.2) and the last two weeks are used in the discussion (Section 6.1.1).
The trip knowledge graph has 95, 728 unique entities and 381, 513 relationships. The types of entities are shown in Table 2. When extracting trip time entities, Ftime in Table 4 were mapped as time spans, with a total of seven such as the morning peak. The structure of TKG is shown in Fig. 3, and its triples see Table 3.

Experiment setup
We implemented the modified TransH model to TKG based on Pytorch framework. The crucial parameters are as follows.

Prediction refinement
Destinations retrieved from an individual's validation data (after the first week) that do not appear in its training data (the first week) are potential destinations of the individual. For each potential destination of an individual, there are rankings (e.g., embedding ranking) corresponding to it predicted by PDPFKG (Algorithm 1-2). However, it is not reasonable to use the predicted results of a specific potential destination or individual for evaluation for their predicted performances vary, and we can't judge which one should prevail. So we aggregate  (2014)) the prediction results of all individuals (potential destinations). Denote the set of an individual's potential destinations as Z c , then Z c ⊂ Z p . Algorithm 3 describes the process of aggregating the predicted results, whose output is used for evaluation in Section 5.5. Count(K) means counting the proportion of elements of the set K. It will output a hash table whose key is the element, and its value is the number proportions of this key.
Get the ranking of z k for v n based on M , denoted as r k n ; K ← r k n ; R ← Count(K); Return R

Evaluation metrics
The prediction output R can be considered a discrete distribution about the predicted ranking r i and the proportion of potential destinations P (r i ) caught by r i , which is the basis for evaluating prediction performances. The ideal distribution should have the following characteristics. First, the lower the ranking, the lower its corresponding proportion, which reflects the correctness of the prediction. If it cannot be strictly monotonous, then the evolution of its corresponding proportion should be smooth as the ranking varies. Lastly, most of the proportion should be concentrated in top rankings, which reflects the capability of the prediction. On this basis, we give the following three evaluation metrics.
Ranking confusion degree. This metric is designed for evaluating the correctness of prediction. First we extract the values of R to get the sequence A = [P (r 1 ), P (r 2 ), P (r 3 ), · · · ] and next sort it in descending order. The ranking of the P (r i ) in the sequence A can be obtained and denoted as r r i . Then we can use the result of Eq. (11) to quantify the Degree of ranking confusion.
Smoothing degree. This metric is introduced to evaluate the smoothness of proportion (of potential destinations) evolution as ranking vary. It can measure whether a distribution follows a pattern. The equation is shown in Eq. (12) in which P (r i ) represents the proportion of ranking r i in ranking hash table R.
Concentration degree. This metric is introduced to evaluate the effectiveness of prediction as well as the capability of method. It measures the concentration by calculating the cumulative proportion of the Top-N rankings, and it can be calculated by Eq. (13).
Among the three metrics mentioned above, both D f and D s are the smaller the better, while for metric D c , the larger of it the better the model performance for the same N .

Baselines
We have chosen the following three categories of methods for comparison and all of them can achieve potential destination prediction personality.
• Random choice (RC): This method simulates predicting in the absence of any context information. The method randomly gives the possible ranking of the zones in the potential destination candidate set for each individual.
• Matrix decomposition (MD): It is a typical class of methods for data imputation. We use the individual and the traffic zone as the two dimensions of the matrix. And the entry of it is the number of trips that the individual chooses the traffic zone as the destination. By performing matrix decomposition, the 0 values in the matrix are filled. For each individual's vector, the traffic zone corresponding to the original 0 value constitutes its candidate set of potential destinations, and the ranking can be given by comparing the values after repair. We have implemented three common matrix decomposition methods, which are UV decomposition (MD-UV), QR decomposition (MD-QR) and SVD decomposition (MD-SVD).
• Collaborative filtering (CF): It is a classic method for recommendation system. For our task, we consider individual and traffic zone as user and item respectively. The frequency of individuals choosing a traffic zone as the destination is regarded as the user's score for the item. On this basis, we implemented two methods, collaborative filtering user-based (CF-U) and collaborative filtering item-based (CF-I). The former is based on the similarity of users, while the latter is based on the similarity of items.

Overall performance visualization
Visualization of prediction output (ranking hash table R) can intuitively show the overall effectiveness of the prediction. First, we visualize the output of three ranking ways mentioned in Section 4.3, see Fig. 10. Each of its bars represents the proportion of potential destinations caught by the ranking corresponding to its horizontal axis. Hotness ranking has a good performance in concentration as shown in Fig. 10(a), reflecting the city's hotspots are overall steady. But it is highly confusing and not smooth intuitively. PDPFKG's embedding ranking shows well performance in ranking confusion and smoothness. Nevertheless, its concentration is not very high. The performance of PDPFKG's combined ranking shown in 10(c) incorporates the advantages of the other two ranking ways. It monotonically decrease and smooth with a high degree of concentration. This variation proves that TKGEM learned is differs from statistical information. On the other hand, it also shows that combining the ranking is an effective way to integrate statistical and association information, which has a better performance.
The visualization of the baseline methods' results is shown in Fig. 11. We can see that the method of random choice almost obtains a uniform distribution, which means it is invalid. The performance of UV decomposition is close to random choice, except for a significant decline in the tail. Both QR decomposition and SVD decomposition perform well in the head. However, they all suffer from predicting a large number of potential destinations as ranking in the tail. This phenomenon is most notable for collaborative filtering item-based (CF-I). The ranking it gives is almost the exact opposite of the actual individual choice behaviour. For the method of collaborative filtering-user based, its figure drops rapidly in the middle. This indicates it can roughly distinguish the possibility of potential destinations being chosen, i.e., it is reasonable to consider that destinations with very low ranks have a very low probability of being chosen. However, it can't provide valid information when the ranking is in a specific interval like 1 − 75.

Experimental evaluation
In this section, we will show the evaluation of our and baseline methods using the metrics introduced in Section5.3. The ranking confusion degree of the different methods is visualized as shown in Fig. 12. Its horizontal axis indicates the ranking of prediction output (r i ), which is same as Fig. 10-11. Its vertical axis represents different methods. The potential destinations' proportion ranking (r r i ) of r i predicted by methods is noted with gradient color. The prediction results is totally correct if it satisfy: ∀r i < r j ⇒ r r i < r r j . Its visualization is shown as a benchmark in Fig. 12 and noted as correct. Therefore, the method with visualization similar to correct indicates better performance on this metric, i.e., the more correct the prediction. On the other hand, the chaos of the colors also visually demonstrates the degree of confusion in the rankings. It can be seen that our method is very close to correct, and other methods have a large gap with ours. The smoothing degree of the different methods is visualized as shown in Fig. 13 by adopting the polar coordinate system. Let (r, θ) represent the point in the polar coordinated system. The blue fill is formed by all points that (r i , P (r i+1 ) − P (r i )), and all points satisfying θ = 0 form the red curve, we call it the base circle. The degree of fit of the blue fill to the base circle visualizes the degree of smoothness. P (r i+1 ) > P (r i ) is more unacceptable and it is expressed as blue fill outside the base circle. Fig. 13 illustrates that random choice and our method perform remarkably better than other methods in smoothing degree. The performance of hotness ranking (HR) is extremely poor, indicating its prediction results do not form a stable pattern. Together with its inability to make personalized predictions, we exclude it from the subsequent evaluation.

3UHGLFWHGUDQNLQJ
To evaluate quantitatively, the ranking confusion degree D f and smoothing degree D s of different methods are calculated and shown in Table 7. It is consistent with the visualization, showing that our method significantly outperforms the other methods integrating D f and D s .  To summarize, PDPFKG proposed in this paper performs excellently in all three metrics, outperforming baseline methods, especially in the metric evaluating prediction correctness, and has reached an excellent level in prediction correctness. It means the traffic zones with a higher ranking are more likely to be chosen by the individual statistically. Thus, PDPFKG reveals the potential destination choice pattern of individuals. Further, the performance is improved in the concentration degree by integrating the statistical information of traffic zone hotness while maintaining the advantages of the other two metrics.
6. Discussion 6.1. Trip knowledge graph embedding model TKGEM is the kernel of PDPFKG. Both the particular design of the TKG structure and the customization of the embedding model serve it. This section will thoroughly discuss TKGEM and respond to crucial points mentioned in the methodology.

Different prediction periods
In Section 5, we use one week (7 days) of data for training and evaluate with the following two weeks (14 days) of data. What if we predict the potential destination of the individual over a more extensive period? Fig. 15 shows the results, which are almost consistent with the predicted two weeks. The reason is that potential destinations have been exposed for the vast majority of the two weeks according to Table 5. Hence two weeks as the predicted period length is sufficient to evaluate the effect of the model.

Impact of embedding dimension
The dimension is a critical parameter of knowledge graph embedding algorithm. In general, there is an optimal dimension that makes the model perform best for a given data and task. If the dimension selection of the model is correlated with the effect, then it will significantly reduce the work of parameter adjusting. To explore it with TKGEM, we selected different dimensions for a series of experiments. The results are shown in Fig. 16, illustrating that embedding dimension has a remarkable correlation with performance. In combination with the migration of the optimal dimensions mentioned in Section 4.1, we can migrate to other datasets by calibrating the optimal dimensions on one dataset. 6.1.3. Impact of non-core triples TKGEM can be trained without other type triples as long as the core triple is available. Non-core triples work by influencing the core triple's expression during the training process. We think their information is valid, for which they are introduced to TKG. Is this information beneficial? Does TKGEM make effective use of this information? To answer these questions, we designed a model containing only the core triple and trained it with the same parameters. The effect compared with the model containing non-core triples is shown in Fig. 17. It can be seen that the improvement of the model effect by introducing non-core triples is noticeable, which proves that the additional information we introduced is valid and can be learned by TKGEM.

Impact of the introduction of private relationships
In Section 4.1, we propose the concept of private relationship. It is scientific and satisfies the principles of relationship building, while public relationship (Choose_D) is not. Here we would like to discuss further through experiments. We have adopted public relationship to construct the core triple and trained it. Finally we get Fig. 18(b), whose performance is similar to Fig. 17(b), which adopts private relationship. But its dimension reaches 600. When setting dimension as 148, the performance is shown in Fig. 18(a). It proves that the more complex the relationship is, the larger the optimal dimension is. On this basis, it is conceivable that the optimal dimension of Choose_D and Has_P OI will differ greatly due to the difference in complexity, which is bad for determining the dimension of training. In addition, the variation of public relationship complexity with the data scale also leads to the optimal dimension being tied to the scale of the dataset. Thus, public relationship is not scientific for TKGEM.

Impact of the negative sampling strategy
In Section 4.2 we have referred to that negative sampling strategy is not adapted to TKGEM and our task. To explore the impact of introducing it, we train two models that adopt the negative sampling strategy. We used two ways to generate negative samples. The one is random replacement mentioned in Section 4.2.1. The other one is called controlled replacement that we designed, which guarantees that the replaced entity or relationship is different from the original one. Their performance is shown in Fig. 19. The concentration of Fig. 19(a) at the head becomes significantly worse. This is because many true core triples unobserved are trained as negative samples. Theoretically, controlled replacement does not produce possibly true triples. Nevertheless, it performs even worse and seems that it spoils the training.

Advantages of knowledge graph for prediction with low predictability individuals
For the prevailing prediction methods that are regularity-based, as we mentioned in Section 2, their principle is conflicting to prediction for low predictability individuals. In addition, there are the following specific problems when implementing them on our task. 1) Some methods can not give prediction results in ranked form; 2) It is difficult for supervised learning methods to determine the truth value; 3) For models that require training inputs consistent with test inputs like the neural network, only individual identities can be used for training since the prediction only requires the individual's identity. In summary, the advantages of these methods cannot be exploited on individuals with low predictability.
Knowledge graph is very powerful at expressing associated information, which fits with our idea of solving the prediction issue for low predictability individuals. Besides, it also specializes in organizing heterogeneous data, by which it is capable of utilizing multiple sources of heterogeneous data. Matrix decomposition and collaborative filtering predict based on information from all or similar individuals, but they are not modeling and learning individuals' association information. On the other hand, they can hardly take advantage of data such as POI limited by the ability to organize heterogeneous data. These are reasons why there is a gap between their performance and our method. We think another factor contributing to their poor performance is that they all default to the entity having only a single meaning. This has no problem for commodity recommendations since commodity usage is relatively singular, but not in our scene. For example, collaborative filtering will consider two individuals that have similar destination choices are similarity. However, they may go to the same traffic zone for different purposes. We have mentioned that TransH can deal with this case in Section 4.2.2, while matrix decomposition and collaborative filtering will be misleading. We think this is the main reason why other methods do not perform well in the tail, especially collaborative filtering-item based.

Conclusion and future works
In this paper, we proposed a knowledge graph-based potential destination prediction framework PDPFKG for low predictability individuals. To associate data of individuals, we first construct a trip knowledge graph (TKG) by organizing original data adopting knowledge graph. In TKG, partial data related to the individual destination choice are extracted as entities. When building relationships between them, we introduce the private relationship. It reduces and balances the complexity of the relationships and makes its complexity independent of the data scale, while ensuring the consistency of the optimal dimension of relationships and the migration of the model. Next, we apply a specialized embedding model to TKG and get trip knowledge graph embedding model (TKGEM). In TKGEM, entities and relationships are parameterized and computable. The specialization of the generic model mainly includes training strategies and optimization objectives, which are adapted to TKG and our task. Benefitting from the structure of TKG, the training of TKGEM can achieve overall optimization. Next, we give a potential destination prediction method based on TKGEM. It obtains the ranking of unobserved traffic zones chosen by the individual in the future. Future, we integrate statistical information with TKGEM when predicting and improving its performance, proving TKGEM does not simply learn statistical information. Lastly, we implement PDPFKG on low predictability individuals in a city scale real-world dataset. Experiments demonstrate the result of PDPFKG is highly consistent with potential destinations choices pattern of individuals. Finally, we have a thorough discussion of TKGEM and respond to its modifications.
Our future work will focus on the following two topics. 1) Explore how to improve the performance of model predictions. Section 6.1.3 has shown additional information can improve the performance. Next, we will consider introducing more data types, such as the adjacency between traffic zones. 2) Explore the correlation between group sizes and predictability of low-predictability individuals. PDPFKG has proved that individuals with low predictability are not completely unpredictable when put in a group. It can be determined that there is a correlation between the size of the group and predictability. It would be a meaningful effort to reveal the relationship between them.