# An Improved Fuzzy Trajectory Clustering Method for Exploring Urban Travel Patterns

Authors: Fang Liu; Wei Bi; Wei Hao; Fan Gao; Jinjun Tang
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

Exploring urban travel patterns can analyze the mobility regularity of residents to provide guidance for urban traffic planning and emergency decision. Clustering methods have been widely applied to explore the hidden information from large-scale trajectory data on travel patterns exploring. How to implement soft constraints in the clustering method and evaluate the effectiveness quantitatively is still a challenge. In this study, we propose an improved trajectory clustering method based on fuzzy density-based spatial clustering of applications with noise (TC-FDBSCAN) to conduct classification on trajectory data. Firstly, we define the trajectory distance which considers the influence of different attributes and determines the corresponding weight coefficients to measure the similarity among trajectories. Secondly, membership degrees and membership functions are designed in the fuzzy clustering method as the extension of the classical DBSCAN method. Finally, trajectory data collected in Shenzhen city, China, are divided into two types (workdays and weekends) and then implemented in the experiment to explore different travel patterns. Moreover, three indices including Silhouette Coefficient, Davies–Bouldin index, and Calinski–Harabasz index are used to evaluate the effectiveness among the proposed method and other traditional clustering methods. The results also demonstrate the advantage of the proposed method.


---

## Body

## 1. Introduction

Travel patterns can be explored by analyzing the travel characteristics of moving objects (vehicles and humans), which reflects peoples’ travel regularity, traffic congestion regularity, and social activity pattern. Travel patterns have been applied in many areas, for instance, providing the decision information for urban planning and emergency [1–4], analyzing and optimizing the path to provide personalized travel recommendations for residents [5–8], vehicles dispatching [9, 10], and station optimization and selection [11]. These applications can prove insights for urban construction and development.Nowadays, more and more researchers and scholars explore urban travel patterns using large-scale trajectory data, which contain huge hidden information about travel feature and regularity. Several approaches have been used for this application. (1) Clustering methods: trajectory clustering has been gaining increasing interest in recent years, and it generally requires two components, similarity measurement and clustering algorithm [12–15]. (2) Spatial statistics: Ni et al. [16] employed a spatial econometric model for travel flow analysis to explore factors that influence travel demand; Zhang et al. [17] proposed a Bayesian hierarchical approach for modeling the destination choice behavior considering the unavailable factors and spatio-temporal correlations; Kamruzzaman et al. [18] estimated the effects of urban form and spatial biases on residential mobility. (3) Deep learning: especially nonparametric deep learning methods have proven to give more accurate predictions in urban traffic forecast [19, 20]. (4) Classical traffic theory models: some classical models have been used in travel patterns analysis. For instance, using combined Markov chain and multinomial logit model [21] to improve the accuracy of travel destination prediction and using traffic assignment models [22] for O-D matrix estimation.In the abovementioned methods, the clustering method is an unsupervised learning process that classifies datasets on the basis of similarity. By defining a reasonable similarity criterion, the clustering method can effectively excavate hidden information from massive trajectory data and thus reveal travel patterns. Some researchers adopt traditional clustering methods for travel patterns analysis, such asC-means [23], shared nearest neighbor clustering [24], DBSCAN [25, 26], hierarchical clustering method [27, 28], and optics algorithm [29, 30]. Besides, there are also some researchers who propose several modified clustering methods to obtain better clustering results: a modified bee colony optimization (MBCO) [31] is proposed which introduces the approach based on probability selection; a hybrid model-fused k-means and fuzzy c-means clustering with the modified cluster centroid (FKMFCM-MCC) [32]; Wang et al. [33] presented a modified find density peaks (MFDP) algorithm to transform the high-dimensional points into two-dimensional, and it expressed good potential for application.The literatures mentioned above have provided practical applications of travel patterns analysis, and several classical or modified clustering methods have been proved that they can achieve good clustering results to explore residents’ travel patterns. However, there are also some limitations need to be improved in trajectory clustering for travel patterns analysis. Firstly, as for similarity measurements, lots of literatures only consider the spatial attribute of trajectories, and fewer literatures consider the multiattributes (such as temporal, directional, and other characteristics) of trajectories, ignoring other attributes will cause inaccurate results and unreasonable travel patterns. Besides, many researchers who consider multiattributes do not assign weights to different attributes. The configuration and discussion of weights is necessary because different attributes have different influences on trajectory clustering. Secondly, trajectory data have the attribute of faint borders and overlapping borders; thus, the efficient algorithm which has soft constrains is required to handle such dataset, while lots of researchers consider the ideology of hard divided clustering. Finally, many works pay attention on improving clustering algorithm to reduce computational complexity and obtain better results, and there are lacks in using multiple indices to the quantitative evaluation of results.Fuzzy clustering methods have the ability to identify clusters with variable density distributions and partially overlapping borders [34]. In fuzzy clustering methods, the framework of the fuzzy set theory is defined with the aim to make up for the shortage of crisp clustering algorithms. Generally, the clustering methods realize soft constraints by introducing weight entropy, membership function, or fuzzy distance function. Currently, the fuzzy clustering methods have been applied in many areas, such as predictive models: Seresht et al. [35] proposed a fuzzy clustering algorithm and assign weights to the fuzzy inference systems to improve the accuracy of predictive models; virus research: Mahmoudi et al. [36] used fuzzy clustering technique to compare the spread of COVID-19 in many countries; image segmentation: Wu and Chen [37] proposed a novel fuzzy clustering method to improve the robustness of the exiting picture clustering. Moreover, some internal evaluation indices are adopted for trajectory data which are unlabeled in clustering results analysis: silhouette coefficient [38, 39]; Davies–Bouldin index [40]; Calinski–Harabasz index [41]; Q-Measure [42]; Dunn’s index [39, 43].The main contributions of this paper include the following several aspects. Firstly, an improved fuzzy clustering method based on DBSCAN is proposed to cluster taxi trajectory data, in which fuzzy theory is introduced to defining membership functions. It is different from traditional DBSCAN algorithm and can effectively deal with taxi trajectory data which have the attributes of faint borders and overlapping borders. The greatest advantage of the proposed method is introducing the theory of soft constrain, which can divide trajectories into reasonable clusters. While traditional DBSCAN uses hard constrain, when a trajectory may belong to either cluster 1 or cluster 2, the algorithm divides it into first cluster, and this is unreasonable. Secondly, we define the trajectory distance considering the combination of spatial, temporal, and directional attributes to measure the similarity between trajectories. Besides, the weights of different attributes are optimized in trajectory distance function to obtain better results. Finally, several internal evaluation indices are used in model comparison, and the results show the effectiveness and advantage of the proposed method comparing with other classical clustering methods.The remainder of this paper is organized as follows. Section2 introduces the framework and theory of the proposed method. In Section 3, data description and case results’ analysis of Shenzhen city are introduced. In Section 4, the evaluation among compared approaches is conducted, and the results are then discussed. In Section 5, we summarize the conclusion of this paper.


## 2. Methodology

### 2.1. Framework

The proposed method for taxi trajectory clustering in this paper is shown in Figure1 as a framework. The framework mainly contains three aspects: (1) after preprocessing the initial trajectory data, the trajectory distance can be calculated with the combination of spatial, temporal, and directional distance using the weight coefficients; (2) the TC-FDBSCAN is adopted to cluster trajectories, which need to determine the weight coefficients and other algorithm parameters; (3) three indices are used to evaluate the clustering results.Figure 1
Framework of the trajectory clustering method.


### 2.2. Multicharacteristics Similarity Measurement

A trajectory is denoted byTR in this paper. TR=p1,t1,p2,t2,…,pk,tk, where pk=pkx,pky denotes the location (abscissa pkx and ordinate pky, the longitude and latitude, are converted to plane coordinates) of track point k, and tk denotes the recording time of track point k. Next, we introduce measurements of multicharacteristics similarity between two trajectories TRA and TRB, where TRA=pA1,tA1,pA2,tA2,…,pAi,tAi and TRB=pB1,tB1,pB2,tB2,…,pBj,tBj.


#### 2.2.1. Spatial Distance between Trajectories

Determining a rule to calculate the spatial distance of track points between trajectories is the key to measure the spatial similarity of trajectories. Hausdorff distance is a common distance measurement method for two points and can be introduced into trajectory dataset. Figure2 shows the Hausdorff distance between two trajectories.Figure 2
Hausdorff distance between two trajectories.
(a)(b)Traditional Hausdorff distance calculates the Max-Min distance, which can only measure the dispersion of the distance between trajectories. And, it is susceptible to local shapes of trajectories. In order to improve its robustness to local effects, a modified Hausdorff distance is defined as follows:(1)hTRA,TRB=1ni∑pAi⊂TRAminpBj⊂TRBdistpAi,pBj,hTRB,TRA=1nj∑pBj⊂TRBminpAi⊂TRAdistpBj,pAi,HTRA,TRB=maxhTRA,TRB,hTRB,TRA,where ni denotes the number of track points in TRA, nj denotes the number of points in TRB, distpAi,pBj is the Euclidean distance between points pAi and pBj, and HTRA,TRB is an absolute Hausdorff distance, which denotes the spatial distance between two trajectories.


#### 2.2.2. Temporal Distance between Trajectories

The trajectory is represented as an interval, which is related to time of starting points and time of ending points. Considering the influence of trajectory duration, the temporal distance between two trajectories is defined as follows:(2)TemTRA,TRB=1,TA∩TB=∅,tA1−tB1+tAi−tBjtAi−tA1+tBj−tB1,TA∩TB≠∅,where TA=tA1,tA2,…,tAi and TB=tB1,tB2,…,tBj.Only if the starting time and ending time of two trajectories are the same (tA1=tB1tAi=tBj), the temporal distance is 0, which means two trajectories are completely similar in temporal characteristic. When two trajectories are separated in temporal characteristic, they are not completely similar and have a temporal distance TemTRA,TRB between 0 and 1.


#### 2.2.3. Directional Distance between Trajectories

Linear directional mean is commonly used to describe the trend or average direction of a set of lines. On the basis of linear directional mean, for trajectoryTRA, treating each trajectory segment (which consists of two consecutive points in TRA) as a line, its average direction is defined as follows:(3)γTRA=arctan∑k=1ni-1sinθAk′∑k=1ni-1cos⁡θAk′,γTRA′=γTRA,∑k=1ni-1cos⁡θAk′>0,∑k=1ni-1sinθAk′≥0,180°-γTRA,∑k=1ni-1cos⁡θAk′<0,∑k=1ni-1sinθAk′≥0,180°+γTRA,∑k=1ni-1cos⁡θAk′<0,∑k=1ni-1sinθAk′≤0,360°-γTRA,∑k=1ni-1cos⁡θAk′>0,∑k=1ni-1sinθAk′≤0,θAk=arctanpAk+1y-pAkypAk+1x-pAkx,θAk′=θAk,pAk+1x-pAkx>0,pAk+1y-pAky≥0,180°-θAk,pAk+1x-pAkx<0,pAk+1y-pAky≥0,180°+θAk,pAk+1x-pAkx<0,pAk+1y-pAky≤0,360°-θAk,pAk+1x-pAkx>0,pAk+1y-pAky≤0,where θAk′ is the real direction of trajectory segment pAk,tAk,pAk+1,tAk+1, which represents the angle rotated counterclockwise due east, θAk′⊂0°,360°.The angle of linear directional mean between two trajectories is defined as follows:(4)γTRA,TRB=γTRA′−γTRB′.


#### 2.2.4. Trajectory Distance

Firstly, the spatial and directional distance need to be Min-Max normalized and converted to the dimensionless value, while the temporal distance does not need to be normalized because its value is between 0 and 1; then, the corresponding distance can be defined as follows:(5)SDistTRA,TRB=HTRA,TRB−minHmaxH−minH,TDistTRA,TRB=TemTRA,TRB,DDistTRA,TRB=γTRA,TRB−minγmaxγ−minγ,where H and γ are the set of spatial and directional distance between all pairs of trajectories, respectively.In combination with spatial, temporal, and directional distance, the trajectory distance is defined considering the influence of weights:(6)TRDistTRA,TRB=α⋅SDistTRA,TRB+β⋅TDistTRA,TRB+ω⋅DDistTRA,TRB,α+β+ω=1,α≥0,β≥0,ω≥0,where α, β, and ω are weight coefficients.


### 2.3. Trajectory Clustering Method TC-FDBSCAN

In this section, based on the classical DBSCAN method, an improved TC-FDBSCAN (trajectory clustering method based on fuzzy density-based spatial clustering of applications with noise) method is proposed in trajectory data clustering. In this method, membership functions are introduced to achieve fuzziness and parametersMinTRs (minimum trajectories in neighborhood) and ε (radius of neighborhood) in classical DBSCAN are replaced by MinTRsmin (minimum value of minimum trajectories in neighborhood), MinTRsmax (maximum value of minimum trajectories in neighborhood), εmin (minimum radius), and εmax (maximum radius).Several extended definitions of the modified method are described in detail as follows.Definition 1.
Neighborhood: the region within a definite radius of a trajectory.Definition 2.
Core trajectory: the number of trajectories in the neighborhood of a trajectory is greater than a definite value.Definition 3.
The local density of a trajectory:(7)denTR=∑TRl∈neighborTR,εmaxμϵTR,TRl,where neighborTR,εmax=TRl,TRDistTR,TRl<εmax and denTR denotes the number of trajectories in neighborhood with membership degree μϵTR,TRl.Definition 4.
ε membership function:(8)μϵTR,TRl=1,TRDistTR,TRl≤εmin,εmax−TRDistTR,TRlεmax−εmin,εmin<TRDistTR,TRl<εmax,0,TRDistTR,TRl>εmax.
This membership function considers the fuzzies of neighborhood, which causes a trajectory having a specified membership degree in the fuzzy neighborhood of another trajectory.Definition 5.
MinTRs membership function:(9)μMinTRsdenTR=1,denTR≥MinTRsmax,denTR−MinTRsminMinTRsmax−MinTRsmin,MinTRsmin<denTR<MinTRsmax,0,denTR≤MinTRsmin.
This membership function considers the fuzzies of core trajectory, which causes the number of trajectories in the fuzzy neighborhood having a specified membership degree.Definition 6.
Core membership degree: ifμMinTRsdenTR>0, then trajectory TR is a fuzzy core trajectory, and it belongs to a cluster with core membership degree fuzzycoreTR=μMinTRsdenTR.Definition 7.
Border membership degree: ifμMinTRsdenTR=0, then trajectory TR should be a border or noise trajectory. Then, TR can be a fuzzy border trajectory which belongs to a cluster with border membership degree:(10)fuzzyborderTR=minTRl∈neighborcoreTRminμMinTRsdenTRl,μϵTR,TRl,where neighborcoreTR=TRl,μMinTRsdenTRl>0andμϵTR,TRl>0.
The trajectory will be a noise trajectory if it is not a fuzzy core trajectory or fuzzy border trajectory.Definition 8.
Directly density-reachable: if trajectoryTRj is in the fuzzy neighborhood of trajectory TRi and TRi is a fuzzy core trajectory, then TRj is directly density-reachable to TRi.Definition 9.
Density-reachable: if eachTRn is directly density-reachable to TRn−1 under the condition of TRn and TRn−1 are in the TRi,…,TRn−1,TRn,…,TRj, then TRj is density-reachable to TRi.Definition 10.
Density-connected: ifTRk is density-reachable to both TRi and TRj, then TRi and TRj are density-connected.
The aim of the TC-FDBSCAN is to divide the regions with high density into clusters, which are the largest sets of density-connected trajectories. The major difference from classical DBSCAN is that a trajectory is determined to be a core trajectory or border trajectory considering membership degree, which means the possibility of this trajectory to belong to clusters.
The process is demonstrated as follows which is similar with classical DBSCAN:(1)
Randomly select a trajectory to visit. If it is a fuzzy core trajectory, then add it into a new cluster with membership degree computed by equation (11) and add other trajectories in its fuzzy neighborhood into an alternate set.(2)
Visit other trajectories in the alternate set; if the trajectories satisfy the fuzzy core trajectory condition, then add them into the original cluster with membership degree computed by equation (11) and add the trajectories in their fuzzy neighborhood; if they do not satisfy the fuzzy core trajectory condition, then add them into original cluster as fuzzy border trajectories with membership degree computed by equation (12).(3)
Repeat step (2) until all trajectories in the alternate set have been visited.(4)
Repeat step (1) to step (3) until all trajectories in the dataset have been visited.
There is a simple approach to allow users to determine two percentages,permin and permax. And, then, use permin⋅maxTRDist and permax⋅maxTRDist to determine the values of εmin and εmax, where maxTRDist denotes the maximum distance between all pairs of trajectories. For MinTRsmin and MinTRsmax, a curve can be drawn, in which the x-coordinate is ε and y-coordinate is the number of trajectories in the set where the distance between each other is equal to ε. This curve is not monotonically decreasing; then, the corresponding y-coordinate values in the first two bends can be selected as MinTRsmin and MinTRsmax.


### 2.4. Cluster Evaluation Indices

In the relevant studies of cluster evaluation, as the experimental data is labeled and which cluster the sample belongs to is known in advance, so the method based on accuracy such as Purity, Rand Index, and Accuracy can be used. While the trajectory data is unlabeled, there is no external information that can be used to verify the authenticity of the clustering results. Then, several internal evaluation indices which consider the geometric structure of data are required to evaluate the effect of clustering results.Silhouette coefficient (SC) [36]:(11)SC=1nC∑i=1nCbi−aimaxai,bi,(12)bi=minh=1,2,…,nC,h≠i1nCh∑TRh∈ChTRDistTRi,TRCh,(13)ai=1nCi∑TRi∈CiTRDistTRi,TRCi,where nC is the number of clusters, Ci denotes the ith cluster, nCi denotes the number of trajectories in Ci, and TRCi denotes the center of Ci. The larger value of SC indicates better clustering results.Davies–Bouldin index (DB) [44]:(14)DB=1nC∑i=1nCmaxh=1,2,…,nC,i≠h1/nCi∑TRi∈CiTRDistTRi,TRCi+1/nCh∑TRh∈ChTRDistTRh,TRChTRDistTRCi,TRCh,where Ch denotes the hth cluster, nCh denotes the number of trajectories in Ch, and TRCh denotes the center of Ch. The smaller value of DB indicates better clustering results.Calinski–Harabasz index (CH) [45]:(15)CH=∑i=1nCnCiTRDist2TRC,TRCi/nC−1∑i=1nC∑TRi∈CiTRDist2TRi,TRCi/nTR−nC,where nTR denotes the number of all trajectories in dataset and TRC denotes the center of dataset. The larger value of CH indicates better clustering results.


## 2.1. Framework

The proposed method for taxi trajectory clustering in this paper is shown in Figure1 as a framework. The framework mainly contains three aspects: (1) after preprocessing the initial trajectory data, the trajectory distance can be calculated with the combination of spatial, temporal, and directional distance using the weight coefficients; (2) the TC-FDBSCAN is adopted to cluster trajectories, which need to determine the weight coefficients and other algorithm parameters; (3) three indices are used to evaluate the clustering results.Figure 1
Framework of the trajectory clustering method.


## 2.2. Multicharacteristics Similarity Measurement

A trajectory is denoted byTR in this paper. TR=p1,t1,p2,t2,…,pk,tk, where pk=pkx,pky denotes the location (abscissa pkx and ordinate pky, the longitude and latitude, are converted to plane coordinates) of track point k, and tk denotes the recording time of track point k. Next, we introduce measurements of multicharacteristics similarity between two trajectories TRA and TRB, where TRA=pA1,tA1,pA2,tA2,…,pAi,tAi and TRB=pB1,tB1,pB2,tB2,…,pBj,tBj.


### 2.2.1. Spatial Distance between Trajectories

Determining a rule to calculate the spatial distance of track points between trajectories is the key to measure the spatial similarity of trajectories. Hausdorff distance is a common distance measurement method for two points and can be introduced into trajectory dataset. Figure2 shows the Hausdorff distance between two trajectories.Figure 2
Hausdorff distance between two trajectories.
(a)(b)Traditional Hausdorff distance calculates the Max-Min distance, which can only measure the dispersion of the distance between trajectories. And, it is susceptible to local shapes of trajectories. In order to improve its robustness to local effects, a modified Hausdorff distance is defined as follows:(1)hTRA,TRB=1ni∑pAi⊂TRAminpBj⊂TRBdistpAi,pBj,hTRB,TRA=1nj∑pBj⊂TRBminpAi⊂TRAdistpBj,pAi,HTRA,TRB=maxhTRA,TRB,hTRB,TRA,where ni denotes the number of track points in TRA, nj denotes the number of points in TRB, distpAi,pBj is the Euclidean distance between points pAi and pBj, and HTRA,TRB is an absolute Hausdorff distance, which denotes the spatial distance between two trajectories.


### 2.2.2. Temporal Distance between Trajectories

The trajectory is represented as an interval, which is related to time of starting points and time of ending points. Considering the influence of trajectory duration, the temporal distance between two trajectories is defined as follows:(2)TemTRA,TRB=1,TA∩TB=∅,tA1−tB1+tAi−tBjtAi−tA1+tBj−tB1,TA∩TB≠∅,where TA=tA1,tA2,…,tAi and TB=tB1,tB2,…,tBj.Only if the starting time and ending time of two trajectories are the same (tA1=tB1tAi=tBj), the temporal distance is 0, which means two trajectories are completely similar in temporal characteristic. When two trajectories are separated in temporal characteristic, they are not completely similar and have a temporal distance TemTRA,TRB between 0 and 1.


### 2.2.3. Directional Distance between Trajectories

Linear directional mean is commonly used to describe the trend or average direction of a set of lines. On the basis of linear directional mean, for trajectoryTRA, treating each trajectory segment (which consists of two consecutive points in TRA) as a line, its average direction is defined as follows:(3)γTRA=arctan∑k=1ni-1sinθAk′∑k=1ni-1cos⁡θAk′,γTRA′=γTRA,∑k=1ni-1cos⁡θAk′>0,∑k=1ni-1sinθAk′≥0,180°-γTRA,∑k=1ni-1cos⁡θAk′<0,∑k=1ni-1sinθAk′≥0,180°+γTRA,∑k=1ni-1cos⁡θAk′<0,∑k=1ni-1sinθAk′≤0,360°-γTRA,∑k=1ni-1cos⁡θAk′>0,∑k=1ni-1sinθAk′≤0,θAk=arctanpAk+1y-pAkypAk+1x-pAkx,θAk′=θAk,pAk+1x-pAkx>0,pAk+1y-pAky≥0,180°-θAk,pAk+1x-pAkx<0,pAk+1y-pAky≥0,180°+θAk,pAk+1x-pAkx<0,pAk+1y-pAky≤0,360°-θAk,pAk+1x-pAkx>0,pAk+1y-pAky≤0,where θAk′ is the real direction of trajectory segment pAk,tAk,pAk+1,tAk+1, which represents the angle rotated counterclockwise due east, θAk′⊂0°,360°.The angle of linear directional mean between two trajectories is defined as follows:(4)γTRA,TRB=γTRA′−γTRB′.


### 2.2.4. Trajectory Distance

Firstly, the spatial and directional distance need to be Min-Max normalized and converted to the dimensionless value, while the temporal distance does not need to be normalized because its value is between 0 and 1; then, the corresponding distance can be defined as follows:(5)SDistTRA,TRB=HTRA,TRB−minHmaxH−minH,TDistTRA,TRB=TemTRA,TRB,DDistTRA,TRB=γTRA,TRB−minγmaxγ−minγ,where H and γ are the set of spatial and directional distance between all pairs of trajectories, respectively.In combination with spatial, temporal, and directional distance, the trajectory distance is defined considering the influence of weights:(6)TRDistTRA,TRB=α⋅SDistTRA,TRB+β⋅TDistTRA,TRB+ω⋅DDistTRA,TRB,α+β+ω=1,α≥0,β≥0,ω≥0,where α, β, and ω are weight coefficients.


## 2.2.1. Spatial Distance between Trajectories

Determining a rule to calculate the spatial distance of track points between trajectories is the key to measure the spatial similarity of trajectories. Hausdorff distance is a common distance measurement method for two points and can be introduced into trajectory dataset. Figure2 shows the Hausdorff distance between two trajectories.Figure 2
Hausdorff distance between two trajectories.
(a)(b)Traditional Hausdorff distance calculates the Max-Min distance, which can only measure the dispersion of the distance between trajectories. And, it is susceptible to local shapes of trajectories. In order to improve its robustness to local effects, a modified Hausdorff distance is defined as follows:(1)hTRA,TRB=1ni∑pAi⊂TRAminpBj⊂TRBdistpAi,pBj,hTRB,TRA=1nj∑pBj⊂TRBminpAi⊂TRAdistpBj,pAi,HTRA,TRB=maxhTRA,TRB,hTRB,TRA,where ni denotes the number of track points in TRA, nj denotes the number of points in TRB, distpAi,pBj is the Euclidean distance between points pAi and pBj, and HTRA,TRB is an absolute Hausdorff distance, which denotes the spatial distance between two trajectories.


## 2.2.2. Temporal Distance between Trajectories

The trajectory is represented as an interval, which is related to time of starting points and time of ending points. Considering the influence of trajectory duration, the temporal distance between two trajectories is defined as follows:(2)TemTRA,TRB=1,TA∩TB=∅,tA1−tB1+tAi−tBjtAi−tA1+tBj−tB1,TA∩TB≠∅,where TA=tA1,tA2,…,tAi and TB=tB1,tB2,…,tBj.Only if the starting time and ending time of two trajectories are the same (tA1=tB1tAi=tBj), the temporal distance is 0, which means two trajectories are completely similar in temporal characteristic. When two trajectories are separated in temporal characteristic, they are not completely similar and have a temporal distance TemTRA,TRB between 0 and 1.


## 2.2.3. Directional Distance between Trajectories

Linear directional mean is commonly used to describe the trend or average direction of a set of lines. On the basis of linear directional mean, for trajectoryTRA, treating each trajectory segment (which consists of two consecutive points in TRA) as a line, its average direction is defined as follows:(3)γTRA=arctan∑k=1ni-1sinθAk′∑k=1ni-1cos⁡θAk′,γTRA′=γTRA,∑k=1ni-1cos⁡θAk′>0,∑k=1ni-1sinθAk′≥0,180°-γTRA,∑k=1ni-1cos⁡θAk′<0,∑k=1ni-1sinθAk′≥0,180°+γTRA,∑k=1ni-1cos⁡θAk′<0,∑k=1ni-1sinθAk′≤0,360°-γTRA,∑k=1ni-1cos⁡θAk′>0,∑k=1ni-1sinθAk′≤0,θAk=arctanpAk+1y-pAkypAk+1x-pAkx,θAk′=θAk,pAk+1x-pAkx>0,pAk+1y-pAky≥0,180°-θAk,pAk+1x-pAkx<0,pAk+1y-pAky≥0,180°+θAk,pAk+1x-pAkx<0,pAk+1y-pAky≤0,360°-θAk,pAk+1x-pAkx>0,pAk+1y-pAky≤0,where θAk′ is the real direction of trajectory segment pAk,tAk,pAk+1,tAk+1, which represents the angle rotated counterclockwise due east, θAk′⊂0°,360°.The angle of linear directional mean between two trajectories is defined as follows:(4)γTRA,TRB=γTRA′−γTRB′.


## 2.2.4. Trajectory Distance

Firstly, the spatial and directional distance need to be Min-Max normalized and converted to the dimensionless value, while the temporal distance does not need to be normalized because its value is between 0 and 1; then, the corresponding distance can be defined as follows:(5)SDistTRA,TRB=HTRA,TRB−minHmaxH−minH,TDistTRA,TRB=TemTRA,TRB,DDistTRA,TRB=γTRA,TRB−minγmaxγ−minγ,where H and γ are the set of spatial and directional distance between all pairs of trajectories, respectively.In combination with spatial, temporal, and directional distance, the trajectory distance is defined considering the influence of weights:(6)TRDistTRA,TRB=α⋅SDistTRA,TRB+β⋅TDistTRA,TRB+ω⋅DDistTRA,TRB,α+β+ω=1,α≥0,β≥0,ω≥0,where α, β, and ω are weight coefficients.


## 2.3. Trajectory Clustering Method TC-FDBSCAN

In this section, based on the classical DBSCAN method, an improved TC-FDBSCAN (trajectory clustering method based on fuzzy density-based spatial clustering of applications with noise) method is proposed in trajectory data clustering. In this method, membership functions are introduced to achieve fuzziness and parametersMinTRs (minimum trajectories in neighborhood) and ε (radius of neighborhood) in classical DBSCAN are replaced by MinTRsmin (minimum value of minimum trajectories in neighborhood), MinTRsmax (maximum value of minimum trajectories in neighborhood), εmin (minimum radius), and εmax (maximum radius).Several extended definitions of the modified method are described in detail as follows.Definition 1.
Neighborhood: the region within a definite radius of a trajectory.Definition 2.
Core trajectory: the number of trajectories in the neighborhood of a trajectory is greater than a definite value.Definition 3.
The local density of a trajectory:(7)denTR=∑TRl∈neighborTR,εmaxμϵTR,TRl,where neighborTR,εmax=TRl,TRDistTR,TRl<εmax and denTR denotes the number of trajectories in neighborhood with membership degree μϵTR,TRl.Definition 4.
ε membership function:(8)μϵTR,TRl=1,TRDistTR,TRl≤εmin,εmax−TRDistTR,TRlεmax−εmin,εmin<TRDistTR,TRl<εmax,0,TRDistTR,TRl>εmax.
This membership function considers the fuzzies of neighborhood, which causes a trajectory having a specified membership degree in the fuzzy neighborhood of another trajectory.Definition 5.
MinTRs membership function:(9)μMinTRsdenTR=1,denTR≥MinTRsmax,denTR−MinTRsminMinTRsmax−MinTRsmin,MinTRsmin<denTR<MinTRsmax,0,denTR≤MinTRsmin.
This membership function considers the fuzzies of core trajectory, which causes the number of trajectories in the fuzzy neighborhood having a specified membership degree.Definition 6.
Core membership degree: ifμMinTRsdenTR>0, then trajectory TR is a fuzzy core trajectory, and it belongs to a cluster with core membership degree fuzzycoreTR=μMinTRsdenTR.Definition 7.
Border membership degree: ifμMinTRsdenTR=0, then trajectory TR should be a border or noise trajectory. Then, TR can be a fuzzy border trajectory which belongs to a cluster with border membership degree:(10)fuzzyborderTR=minTRl∈neighborcoreTRminμMinTRsdenTRl,μϵTR,TRl,where neighborcoreTR=TRl,μMinTRsdenTRl>0andμϵTR,TRl>0.
The trajectory will be a noise trajectory if it is not a fuzzy core trajectory or fuzzy border trajectory.Definition 8.
Directly density-reachable: if trajectoryTRj is in the fuzzy neighborhood of trajectory TRi and TRi is a fuzzy core trajectory, then TRj is directly density-reachable to TRi.Definition 9.
Density-reachable: if eachTRn is directly density-reachable to TRn−1 under the condition of TRn and TRn−1 are in the TRi,…,TRn−1,TRn,…,TRj, then TRj is density-reachable to TRi.Definition 10.
Density-connected: ifTRk is density-reachable to both TRi and TRj, then TRi and TRj are density-connected.
The aim of the TC-FDBSCAN is to divide the regions with high density into clusters, which are the largest sets of density-connected trajectories. The major difference from classical DBSCAN is that a trajectory is determined to be a core trajectory or border trajectory considering membership degree, which means the possibility of this trajectory to belong to clusters.
The process is demonstrated as follows which is similar with classical DBSCAN:(1)
Randomly select a trajectory to visit. If it is a fuzzy core trajectory, then add it into a new cluster with membership degree computed by equation (11) and add other trajectories in its fuzzy neighborhood into an alternate set.(2)
Visit other trajectories in the alternate set; if the trajectories satisfy the fuzzy core trajectory condition, then add them into the original cluster with membership degree computed by equation (11) and add the trajectories in their fuzzy neighborhood; if they do not satisfy the fuzzy core trajectory condition, then add them into original cluster as fuzzy border trajectories with membership degree computed by equation (12).(3)
Repeat step (2) until all trajectories in the alternate set have been visited.(4)
Repeat step (1) to step (3) until all trajectories in the dataset have been visited.
There is a simple approach to allow users to determine two percentages,permin and permax. And, then, use permin⋅maxTRDist and permax⋅maxTRDist to determine the values of εmin and εmax, where maxTRDist denotes the maximum distance between all pairs of trajectories. For MinTRsmin and MinTRsmax, a curve can be drawn, in which the x-coordinate is ε and y-coordinate is the number of trajectories in the set where the distance between each other is equal to ε. This curve is not monotonically decreasing; then, the corresponding y-coordinate values in the first two bends can be selected as MinTRsmin and MinTRsmax.


## 2.4. Cluster Evaluation Indices

In the relevant studies of cluster evaluation, as the experimental data is labeled and which cluster the sample belongs to is known in advance, so the method based on accuracy such as Purity, Rand Index, and Accuracy can be used. While the trajectory data is unlabeled, there is no external information that can be used to verify the authenticity of the clustering results. Then, several internal evaluation indices which consider the geometric structure of data are required to evaluate the effect of clustering results.Silhouette coefficient (SC) [36]:(11)SC=1nC∑i=1nCbi−aimaxai,bi,(12)bi=minh=1,2,…,nC,h≠i1nCh∑TRh∈ChTRDistTRi,TRCh,(13)ai=1nCi∑TRi∈CiTRDistTRi,TRCi,where nC is the number of clusters, Ci denotes the ith cluster, nCi denotes the number of trajectories in Ci, and TRCi denotes the center of Ci. The larger value of SC indicates better clustering results.Davies–Bouldin index (DB) [44]:(14)DB=1nC∑i=1nCmaxh=1,2,…,nC,i≠h1/nCi∑TRi∈CiTRDistTRi,TRCi+1/nCh∑TRh∈ChTRDistTRh,TRChTRDistTRCi,TRCh,where Ch denotes the hth cluster, nCh denotes the number of trajectories in Ch, and TRCh denotes the center of Ch. The smaller value of DB indicates better clustering results.Calinski–Harabasz index (CH) [45]:(15)CH=∑i=1nCnCiTRDist2TRC,TRCi/nC−1∑i=1nC∑TRi∈CiTRDist2TRi,TRCi/nTR−nC,where nTR denotes the number of all trajectories in dataset and TRC denotes the center of dataset. The larger value of CH indicates better clustering results.


## 3. Case Study

### 3.1. Data Description

The research area of the experiments is Shenzhen City, China. Shenzhen city consists of eight administrative districts (Futian, Luohu, Nanshan, Yantian, Baoan, Longgang, Longhua, Pingshan, and Guangming) and one functional district (Dapeng), which are located between 113°46′ E to 114°37′ E and 22°27′ N to 22°52′ N. In this study, taxi trajectory data is used in experiment, and it is composed of a series of sample points collected by vehicular GPS equipment.Each sample point includes the information of the license plate, location (latitude and longitude), recording time, and instantaneous speed and state (0 represents vacant and 1 represents occupied). We use the data collected by 1000 taxies during one week in May, 2019, and we divide them into two groups to conduct experiment separately, which are weekdays (from May 13th to May 17th) and weekends (from May 18th to May 19th). In order to reduce the influence of abnormal points on clustering results, the original data is preprocessed firstly, which mainly includes eliminating the outliers (latitude and longitude are 0 or out of right range and the state is neither 0 or 1) and interpolating the missing points (recording time interval discontinuity). Finally, 2,499,880 original points during the workdays generate 82,144 passenger-occupied trajectories (49,456 trajectories are valid), and 107,186 original points during the weekends generate 34,384 passenger-occupied trajectories (22,774 trajectories are valid).The travel time and travel distance of trajectories on workdays and weekends can be calculated, respectively, as shown in Figure3. The percentage represents the ratio of the number of trajectories in the interval to all trajectories. It can be concluded that both on workdays and weekends, most passengers prefer to take taxi in a short (0 to 5 km) or medium (5 to 15 km) travel distance and takes no more than 20 minutes. Few passengers take more than 1 hour by taxi.Figure 3
The statistical characteristics of trajectories on workdays and weekends: (a) the proportion of trajectories in different travel distance intervals and (b) the proportion of trajectories in different travel time intervals.
(a)(b)


### 3.2. Parameter Configuration

In the proposed method, the parameters includingα, β, ω, εmin, εmax, MinTRsmin, and MinTRsmax are needed to be determined to obtain reasonable clustering results. In parameter configuration and comparison, we adjust parameters and select the reasonable parameter combination according to the Silhouette Coefficient (SC) of the clustering results. Firstly, set up several combinations of weight coefficients to compare the clustering results, and the trajectory distance TRDist can be calculated meanwhile. Secondly, determine two percentages permin=40% and permax=60% according to the approach mentioned in Section 2.3; then, εmin and εmax can be determined according to the value of maxTRDist. In this part, maxTRDist is equal to 1 in these combinations, so we select εmin=0.4 and εmax=0.6. Thirdly, the statistical curve is drawn to select MinTRsmin and MinTRsmax as mentioned in Section 2.3. For workday data, MinTRsmin=1876 and MinTRsmax=2353, which are shown in Figure 4(b). While, for weekend data, MinTRsmin=782 and MinTRsmax=986, which are shown in Figure 5(b). Finally, the optimal parameter combination is determined in the condition that the value of SC is largest in all combinations.Figure 4
Parameter configuration for the data collected on workday: (a) the SC under different combinations of weight coefficients and (b) the curve used to determineMinTRsmin and MinTRsmax.
(a)(b)Figure 5
Parameter configuration for the data collected on weekend: (a) the SC under different combinations of weight coefficients and (b) the curve used to determineMinTRsmin and MinTRsmax.
(a)(b)Next, the process of parameter configuration for workday data and weekend data are demonstrated as follows, respectively. Totally, we compare twenty combinations of weight coefficients, and the detailed results including the SC, the number of clusters, and the number of noise trajectories of each clustering result are shown in Tables1 and 2. We can observe the points which have largest value of SC from Figures 4(a) and 5(a). These points reflect that the clustering results under the corresponding weight combination are the best result for the case study. And, the best results are highlighted in bold in Tables 1 and 2.Table 1
Comparison of different parameter combinations for workday data.
αβωSCThe number of clustersThe number of noise trajectories0.20.20.60.59664163510.20.30.50.59784159700.20.40.40.59825113690.20.50.30.59995121580.20.60.20.59885142230.20.70.10.59685101960.30.20.50.5971599450.30.30.40.60015124540.30.40.30.60185131120.30.50.20.60135108980.30.60.10.59704156680.40.20.40.61154160110.40.30.30.61295124470.40.40.20.62205120980.40.50.10.63006102560.50.20.30.6224699630.50.30.20.63826108910.50.40.10.63665110250.60.20.20.6102788610.60.30.10.6233510258Table 2
Comparison of different parameter combinations for weekend data.
αβωSCThe number of clustersThe number of noise trajectories0.20.20.60.5983659990.20.30.50.6004657660.20.40.40.6134659880.20.50.30.6011853650.20.60.20.6102755310.20.70.10.6006756880.30.20.50.6015560120.30.30.40.6226757640.30.40.30.6269758410.30.50.20.6255854990.30.60.10.6301855010.40.20.40.6298752230.40.30.30.6404949130.40.40.20.6418854230.40.50.10.6398948260.50.20.30.6313950120.50.30.20.63321047880.50.40.10.6397849780.60.20.20.6210848140.60.30.10.635675112Finally, for workday data, we selectα=0.5, β=0.3, ω=0.2, εmin=0.4, εmax=0.6, MinTRsmin=1876, and MinTRsmax=2353, while, for weekend data, we select α=0.4, β=0.4, ω=0.2, εmin=0.4, εmax=0.6, MinTRsmin=782, and MinTRsmax=986.


### 3.3. Clustering Results

Based on the selected parameters, we then adopt the proposed method to cluster taxi trajectory data in Shenzhen city. Figure6 shows travel patterns of taxi trajectory data collected on workday and weekend. Tables 3 and 4 show the detailed temporal and directional information of each cluster. The value of main direction represents the angle of rotation counterclockwise in terms of east.Figure 6
Clustering results: (a) workday and (b) weekend.
(a)(b)Table 3
Detailed information of each cluster on workday.
ClusterMain travel time periodsMain direction (angle)Cluster 17 : 00 to 9 : 00189.29°Cluster 216 : 30 to 19 : 0044.38°Cluster 3All day138.26°Cluster 4All day319.35°Cluster 5All day332.17°Cluster 67 : 00 to 9 : 00; 16 : 00 to 20 : 0094.32°Table 4
Detailed information of each cluster on weekend.
ClusterMain travel time periodsMain direction (angle)Cluster 1All day46.18°Cluster 2All day42.06°Cluster 39 : 00 to 11 : 0057.92°Cluster 422 : 00 to 0 : 30264.32°Cluster 520 : 00 to 22 : 30331.23°Cluster 616 : 00 to 19 : 00227.36°Cluster 7All day124.06°Cluster 8All day274.34°We can conclude some findings comparing the final results between workday and weekend data. Several common phenomena are observed as follows. (1) Most of the trajectories in final clusters are located in arterial roads of city and are concentrated in the downtown area. (2) Some main commuter roads are both detected in clusters (for example, Beijing-Hong Kong-Macau expressway and Binhe avenue are two main roads where most trajectories of clusters located in, which can be observed in Figure6(a) Cluster 5 and Figure 6(b) Cluster1). (3) Some clusters do not show obvious characteristics on temporal attribute, while they are prominent on spatial and directional attributes (for example, the main travel time periods of Cluster 4 and Cluster 5 in Figure 6(a) do not have a concentrate pattern, while Cluster 4 concentrates on Guangming district, the travel trend is the southeast, and Cluster 5 concentrates on Futian district, the travel trend is towards the east). (4) Clusters which have opposite direction are found in the workday and weekend results, respectively (for example, in Figure 6(a) and Table 3, Cluster 3 and Cluster 4 have opposite direction, since the main direction of Cluster 3 is 138.26° and the main direction of Cluster 4 is 319.35°). It shows that the proposed method can effectively cluster trajectories which have different trends of directions.There are also obvious differences between workday and weekend. Firstly, the clustering results of weekend data is better than workday data according to the value of SC (workday: 0.6382 and weekend: 0.6418). Secondly, on weekend, the range of clusters are more widespread, and residents tend to travel to the suburb (for example, in Figure6(b), Cluster 2 and Cluster 3 reflect the larger travel range, the trajectories travel on roads including Pingshan avenue and Pingkui road are added to the final cluster). Thirdly, in contrast to workday, the trajectories of clusters reflect travel in night on weekend (for example, in Figure 6(b) and Table 4, the trajectories in Cluster 4 concentrate on night periods, which during 22 : 00 to 0 : 30). Finally, the number of clusters on weekend is more than weekend and the direction of clusters are more various on weekend which are shown in Figures 6(a) and 6(b).


## 3.1. Data Description

The research area of the experiments is Shenzhen City, China. Shenzhen city consists of eight administrative districts (Futian, Luohu, Nanshan, Yantian, Baoan, Longgang, Longhua, Pingshan, and Guangming) and one functional district (Dapeng), which are located between 113°46′ E to 114°37′ E and 22°27′ N to 22°52′ N. In this study, taxi trajectory data is used in experiment, and it is composed of a series of sample points collected by vehicular GPS equipment.Each sample point includes the information of the license plate, location (latitude and longitude), recording time, and instantaneous speed and state (0 represents vacant and 1 represents occupied). We use the data collected by 1000 taxies during one week in May, 2019, and we divide them into two groups to conduct experiment separately, which are weekdays (from May 13th to May 17th) and weekends (from May 18th to May 19th). In order to reduce the influence of abnormal points on clustering results, the original data is preprocessed firstly, which mainly includes eliminating the outliers (latitude and longitude are 0 or out of right range and the state is neither 0 or 1) and interpolating the missing points (recording time interval discontinuity). Finally, 2,499,880 original points during the workdays generate 82,144 passenger-occupied trajectories (49,456 trajectories are valid), and 107,186 original points during the weekends generate 34,384 passenger-occupied trajectories (22,774 trajectories are valid).The travel time and travel distance of trajectories on workdays and weekends can be calculated, respectively, as shown in Figure3. The percentage represents the ratio of the number of trajectories in the interval to all trajectories. It can be concluded that both on workdays and weekends, most passengers prefer to take taxi in a short (0 to 5 km) or medium (5 to 15 km) travel distance and takes no more than 20 minutes. Few passengers take more than 1 hour by taxi.Figure 3
The statistical characteristics of trajectories on workdays and weekends: (a) the proportion of trajectories in different travel distance intervals and (b) the proportion of trajectories in different travel time intervals.
(a)(b)


## 3.2. Parameter Configuration

In the proposed method, the parameters includingα, β, ω, εmin, εmax, MinTRsmin, and MinTRsmax are needed to be determined to obtain reasonable clustering results. In parameter configuration and comparison, we adjust parameters and select the reasonable parameter combination according to the Silhouette Coefficient (SC) of the clustering results. Firstly, set up several combinations of weight coefficients to compare the clustering results, and the trajectory distance TRDist can be calculated meanwhile. Secondly, determine two percentages permin=40% and permax=60% according to the approach mentioned in Section 2.3; then, εmin and εmax can be determined according to the value of maxTRDist. In this part, maxTRDist is equal to 1 in these combinations, so we select εmin=0.4 and εmax=0.6. Thirdly, the statistical curve is drawn to select MinTRsmin and MinTRsmax as mentioned in Section 2.3. For workday data, MinTRsmin=1876 and MinTRsmax=2353, which are shown in Figure 4(b). While, for weekend data, MinTRsmin=782 and MinTRsmax=986, which are shown in Figure 5(b). Finally, the optimal parameter combination is determined in the condition that the value of SC is largest in all combinations.Figure 4
Parameter configuration for the data collected on workday: (a) the SC under different combinations of weight coefficients and (b) the curve used to determineMinTRsmin and MinTRsmax.
(a)(b)Figure 5
Parameter configuration for the data collected on weekend: (a) the SC under different combinations of weight coefficients and (b) the curve used to determineMinTRsmin and MinTRsmax.
(a)(b)Next, the process of parameter configuration for workday data and weekend data are demonstrated as follows, respectively. Totally, we compare twenty combinations of weight coefficients, and the detailed results including the SC, the number of clusters, and the number of noise trajectories of each clustering result are shown in Tables1 and 2. We can observe the points which have largest value of SC from Figures 4(a) and 5(a). These points reflect that the clustering results under the corresponding weight combination are the best result for the case study. And, the best results are highlighted in bold in Tables 1 and 2.Table 1
Comparison of different parameter combinations for workday data.
αβωSCThe number of clustersThe number of noise trajectories0.20.20.60.59664163510.20.30.50.59784159700.20.40.40.59825113690.20.50.30.59995121580.20.60.20.59885142230.20.70.10.59685101960.30.20.50.5971599450.30.30.40.60015124540.30.40.30.60185131120.30.50.20.60135108980.30.60.10.59704156680.40.20.40.61154160110.40.30.30.61295124470.40.40.20.62205120980.40.50.10.63006102560.50.20.30.6224699630.50.30.20.63826108910.50.40.10.63665110250.60.20.20.6102788610.60.30.10.6233510258Table 2
Comparison of different parameter combinations for weekend data.
αβωSCThe number of clustersThe number of noise trajectories0.20.20.60.5983659990.20.30.50.6004657660.20.40.40.6134659880.20.50.30.6011853650.20.60.20.6102755310.20.70.10.6006756880.30.20.50.6015560120.30.30.40.6226757640.30.40.30.6269758410.30.50.20.6255854990.30.60.10.6301855010.40.20.40.6298752230.40.30.30.6404949130.40.40.20.6418854230.40.50.10.6398948260.50.20.30.6313950120.50.30.20.63321047880.50.40.10.6397849780.60.20.20.6210848140.60.30.10.635675112Finally, for workday data, we selectα=0.5, β=0.3, ω=0.2, εmin=0.4, εmax=0.6, MinTRsmin=1876, and MinTRsmax=2353, while, for weekend data, we select α=0.4, β=0.4, ω=0.2, εmin=0.4, εmax=0.6, MinTRsmin=782, and MinTRsmax=986.


## 3.3. Clustering Results

Based on the selected parameters, we then adopt the proposed method to cluster taxi trajectory data in Shenzhen city. Figure6 shows travel patterns of taxi trajectory data collected on workday and weekend. Tables 3 and 4 show the detailed temporal and directional information of each cluster. The value of main direction represents the angle of rotation counterclockwise in terms of east.Figure 6
Clustering results: (a) workday and (b) weekend.
(a)(b)Table 3
Detailed information of each cluster on workday.
ClusterMain travel time periodsMain direction (angle)Cluster 17 : 00 to 9 : 00189.29°Cluster 216 : 30 to 19 : 0044.38°Cluster 3All day138.26°Cluster 4All day319.35°Cluster 5All day332.17°Cluster 67 : 00 to 9 : 00; 16 : 00 to 20 : 0094.32°Table 4
Detailed information of each cluster on weekend.
ClusterMain travel time periodsMain direction (angle)Cluster 1All day46.18°Cluster 2All day42.06°Cluster 39 : 00 to 11 : 0057.92°Cluster 422 : 00 to 0 : 30264.32°Cluster 520 : 00 to 22 : 30331.23°Cluster 616 : 00 to 19 : 00227.36°Cluster 7All day124.06°Cluster 8All day274.34°We can conclude some findings comparing the final results between workday and weekend data. Several common phenomena are observed as follows. (1) Most of the trajectories in final clusters are located in arterial roads of city and are concentrated in the downtown area. (2) Some main commuter roads are both detected in clusters (for example, Beijing-Hong Kong-Macau expressway and Binhe avenue are two main roads where most trajectories of clusters located in, which can be observed in Figure6(a) Cluster 5 and Figure 6(b) Cluster1). (3) Some clusters do not show obvious characteristics on temporal attribute, while they are prominent on spatial and directional attributes (for example, the main travel time periods of Cluster 4 and Cluster 5 in Figure 6(a) do not have a concentrate pattern, while Cluster 4 concentrates on Guangming district, the travel trend is the southeast, and Cluster 5 concentrates on Futian district, the travel trend is towards the east). (4) Clusters which have opposite direction are found in the workday and weekend results, respectively (for example, in Figure 6(a) and Table 3, Cluster 3 and Cluster 4 have opposite direction, since the main direction of Cluster 3 is 138.26° and the main direction of Cluster 4 is 319.35°). It shows that the proposed method can effectively cluster trajectories which have different trends of directions.There are also obvious differences between workday and weekend. Firstly, the clustering results of weekend data is better than workday data according to the value of SC (workday: 0.6382 and weekend: 0.6418). Secondly, on weekend, the range of clusters are more widespread, and residents tend to travel to the suburb (for example, in Figure6(b), Cluster 2 and Cluster 3 reflect the larger travel range, the trajectories travel on roads including Pingshan avenue and Pingkui road are added to the final cluster). Thirdly, in contrast to workday, the trajectories of clusters reflect travel in night on weekend (for example, in Figure 6(b) and Table 4, the trajectories in Cluster 4 concentrate on night periods, which during 22 : 00 to 0 : 30). Finally, the number of clusters on weekend is more than weekend and the direction of clusters are more various on weekend which are shown in Figures 6(a) and 6(b).


## 4. Discussion

In order to verify the effectiveness of the proposed method, we compare it with other commonly used clustering methods in this section. The case data is 10,000 trajectories randomly selected from the original data (from May 13th to May 19th). Three internal evaluation indices such as Silhouette Coefficient, Davies–Bouldin index, and Calinski–Harabasz index as mentioned in Section2.4 are adopted to evaluate the clustering results.


### 4.1. Comparative Approaches

#### 4.1.1. Hard C-Means (HCM)

HCM or K-means clustering algorithm is an iterative solution of the cluster analysis algorithm. In this method, the data is divided intoC groups, which are randomly selected from C objects as the initial clustering centers. Then, for each object, calculate the distance between every seed clustering center to each object from its nearest cluster center. The clustering centers and the objects assigned to them represent a cluster. Since each sample has been assigned, the clustering center of the cluster is recalculated according to the existing objects in the cluster. This process is repeated until a termination condition is met. The termination condition can be that no (or minimum number) objects are reassigned to different clusters, no (or minimum number) cluster centers change again, and the error sum of squares is locally minimum.


#### 4.1.2. Fuzzy C-Means (FCM)

Fuzzy C-means clustering is a kind of clustering algorithm which uses membership degree to determine the degree of each object belonging to a certain cluster. It is an improvement of the earlier HCM clustering method. FCM divides the original data intoC fuzzy groups and finds the clustering center of each group in order to minimize the value function of the nonsimilarity index. The main difference between FCM and HCM is FCM applying fuzzy division so that each given trajectory is determined by the membership degree between 0 and 1. In accordance with the introduction of fuzzy division, the membership matrix has normalization provisions so that the sum of membership degrees of a dataset is always equal to 1.


#### 4.1.3. Agglomerative Nesting Algorithm (AGNES)

Agglomerative nesting algorithm adopts a bottom-up strategy. Each object is initially treated as a cluster, and these clusters are then merged step by step according to some criteria. The distance between two clusters can be determined by the similarity of the closest data in the two different clusters. The merging process of clustering is repeated until all objects meet the number of clusters.


#### 4.1.4. DBSCAN

DBSCAN is a density-based clustering algorithm, which generally assumes that clusters can be determined by the density of the sample distribution. Samples of the same cluster are closely related to each other, and there must be other samples of the same cluster not far away from any sample of the cluster. A cluster is obtained by grouping closely related samples together. The final result of all clusters is obtained by dividing all groups of closely related samples into different clusters. The definitions of DBSCAN algorithm are similar to the descriptions in Section2.3 without membership constraint.


#### 4.1.5. Shared Nearest Neighbor Clustering (SNNC)

The shared nearest neighbor clustering algorithm was proposed by Jarvis and Patrick, where a link is created between a pair of pointsp and q, if and only if p and q have each other in their closest k-nearest neighbor [46]. This algorithm is an extension of the DBSCAN. The basic idea of SNNC is based on determining the core points around which clusters with various sizes and shapes are built, without worrying about determining their number [47]. Counting the number of points shared between two points p and q in their k-nearest neighbor list based on the distance metric allows us to determine the similarity between them. The greater the number of shared points, the higher the similarity between p and q.


### 4.2. Results’ Discussion

In order to apply these approaches to the case study in comparison analysis, the distance in HCM, FCM, AGNES, DBSCAN, and SNNC is calculated by the trajectory distance as mentioned in our method. The weight coefficients are determined, so the trajectory distance is described byTRDist=0.4×SDistTRA,TRB+0.3×TDistTRA,TRB+0.3×DDistTRA,TRB. The detailed results are shown in Table 5.Table 5
Comparison of different clustering approaches for case data.
Serial numberApproachMain parametersSC1HCMThe number of clusters: 80.5632FCMThe number of clusters: 80.591Fuzzy degree parameter: 23AGNESThe number of clusters: 80.545Linkage distance: 0.454DBSCANε: 0.45; MinTRs: 3500.6205SNNC\0.6336TC-FDBSCANMinTRsmin: 300; MinTRsmax: 500;0.652εmin: 0.36; εmax: 0.54Table5 and Figure 7 show the effectiveness evaluation of different clustering approaches, and we can observe their ability in analyzing unlabeled data samples. The values of SC show that the proposed TC-FDBSCAN model produces better clustering results than other methods, while AGNES produces worse clustering results than others. In Figure 7, the DB index and CH index describe the similar effect: (1) TC-FDBSCAN is obviously superior to other methods; (2) AGNES is obviously inferior to others; (3) HCM and FCM show the similar results, while FCM is better than HCM; (4) DBSCAN and SNNC show that their clustering performance are close, while SNNC is better than DBSCAN. Overall, the proposed method can find better clustering division and provide high clustering accuracy for large-scale trajectory data in travel pattern analysis.Figure 7
Boxplot diagram of the clustering evaluation for case data. (a) DB index. (b) CH index.
(a)(b)


## 4.1. Comparative Approaches

### 4.1.1. Hard C-Means (HCM)

HCM or K-means clustering algorithm is an iterative solution of the cluster analysis algorithm. In this method, the data is divided intoC groups, which are randomly selected from C objects as the initial clustering centers. Then, for each object, calculate the distance between every seed clustering center to each object from its nearest cluster center. The clustering centers and the objects assigned to them represent a cluster. Since each sample has been assigned, the clustering center of the cluster is recalculated according to the existing objects in the cluster. This process is repeated until a termination condition is met. The termination condition can be that no (or minimum number) objects are reassigned to different clusters, no (or minimum number) cluster centers change again, and the error sum of squares is locally minimum.


### 4.1.2. Fuzzy C-Means (FCM)

Fuzzy C-means clustering is a kind of clustering algorithm which uses membership degree to determine the degree of each object belonging to a certain cluster. It is an improvement of the earlier HCM clustering method. FCM divides the original data intoC fuzzy groups and finds the clustering center of each group in order to minimize the value function of the nonsimilarity index. The main difference between FCM and HCM is FCM applying fuzzy division so that each given trajectory is determined by the membership degree between 0 and 1. In accordance with the introduction of fuzzy division, the membership matrix has normalization provisions so that the sum of membership degrees of a dataset is always equal to 1.


### 4.1.3. Agglomerative Nesting Algorithm (AGNES)

Agglomerative nesting algorithm adopts a bottom-up strategy. Each object is initially treated as a cluster, and these clusters are then merged step by step according to some criteria. The distance between two clusters can be determined by the similarity of the closest data in the two different clusters. The merging process of clustering is repeated until all objects meet the number of clusters.


### 4.1.4. DBSCAN

DBSCAN is a density-based clustering algorithm, which generally assumes that clusters can be determined by the density of the sample distribution. Samples of the same cluster are closely related to each other, and there must be other samples of the same cluster not far away from any sample of the cluster. A cluster is obtained by grouping closely related samples together. The final result of all clusters is obtained by dividing all groups of closely related samples into different clusters. The definitions of DBSCAN algorithm are similar to the descriptions in Section2.3 without membership constraint.


### 4.1.5. Shared Nearest Neighbor Clustering (SNNC)

The shared nearest neighbor clustering algorithm was proposed by Jarvis and Patrick, where a link is created between a pair of pointsp and q, if and only if p and q have each other in their closest k-nearest neighbor [46]. This algorithm is an extension of the DBSCAN. The basic idea of SNNC is based on determining the core points around which clusters with various sizes and shapes are built, without worrying about determining their number [47]. Counting the number of points shared between two points p and q in their k-nearest neighbor list based on the distance metric allows us to determine the similarity between them. The greater the number of shared points, the higher the similarity between p and q.


## 4.1.1. Hard C-Means (HCM)

HCM or K-means clustering algorithm is an iterative solution of the cluster analysis algorithm. In this method, the data is divided intoC groups, which are randomly selected from C objects as the initial clustering centers. Then, for each object, calculate the distance between every seed clustering center to each object from its nearest cluster center. The clustering centers and the objects assigned to them represent a cluster. Since each sample has been assigned, the clustering center of the cluster is recalculated according to the existing objects in the cluster. This process is repeated until a termination condition is met. The termination condition can be that no (or minimum number) objects are reassigned to different clusters, no (or minimum number) cluster centers change again, and the error sum of squares is locally minimum.


## 4.1.2. Fuzzy C-Means (FCM)

Fuzzy C-means clustering is a kind of clustering algorithm which uses membership degree to determine the degree of each object belonging to a certain cluster. It is an improvement of the earlier HCM clustering method. FCM divides the original data intoC fuzzy groups and finds the clustering center of each group in order to minimize the value function of the nonsimilarity index. The main difference between FCM and HCM is FCM applying fuzzy division so that each given trajectory is determined by the membership degree between 0 and 1. In accordance with the introduction of fuzzy division, the membership matrix has normalization provisions so that the sum of membership degrees of a dataset is always equal to 1.


## 4.1.3. Agglomerative Nesting Algorithm (AGNES)

Agglomerative nesting algorithm adopts a bottom-up strategy. Each object is initially treated as a cluster, and these clusters are then merged step by step according to some criteria. The distance between two clusters can be determined by the similarity of the closest data in the two different clusters. The merging process of clustering is repeated until all objects meet the number of clusters.


## 4.1.4. DBSCAN

DBSCAN is a density-based clustering algorithm, which generally assumes that clusters can be determined by the density of the sample distribution. Samples of the same cluster are closely related to each other, and there must be other samples of the same cluster not far away from any sample of the cluster. A cluster is obtained by grouping closely related samples together. The final result of all clusters is obtained by dividing all groups of closely related samples into different clusters. The definitions of DBSCAN algorithm are similar to the descriptions in Section2.3 without membership constraint.


## 4.1.5. Shared Nearest Neighbor Clustering (SNNC)

The shared nearest neighbor clustering algorithm was proposed by Jarvis and Patrick, where a link is created between a pair of pointsp and q, if and only if p and q have each other in their closest k-nearest neighbor [46]. This algorithm is an extension of the DBSCAN. The basic idea of SNNC is based on determining the core points around which clusters with various sizes and shapes are built, without worrying about determining their number [47]. Counting the number of points shared between two points p and q in their k-nearest neighbor list based on the distance metric allows us to determine the similarity between them. The greater the number of shared points, the higher the similarity between p and q.


## 4.2. Results’ Discussion

In order to apply these approaches to the case study in comparison analysis, the distance in HCM, FCM, AGNES, DBSCAN, and SNNC is calculated by the trajectory distance as mentioned in our method. The weight coefficients are determined, so the trajectory distance is described byTRDist=0.4×SDistTRA,TRB+0.3×TDistTRA,TRB+0.3×DDistTRA,TRB. The detailed results are shown in Table 5.Table 5
Comparison of different clustering approaches for case data.
Serial numberApproachMain parametersSC1HCMThe number of clusters: 80.5632FCMThe number of clusters: 80.591Fuzzy degree parameter: 23AGNESThe number of clusters: 80.545Linkage distance: 0.454DBSCANε: 0.45; MinTRs: 3500.6205SNNC\0.6336TC-FDBSCANMinTRsmin: 300; MinTRsmax: 500;0.652εmin: 0.36; εmax: 0.54Table5 and Figure 7 show the effectiveness evaluation of different clustering approaches, and we can observe their ability in analyzing unlabeled data samples. The values of SC show that the proposed TC-FDBSCAN model produces better clustering results than other methods, while AGNES produces worse clustering results than others. In Figure 7, the DB index and CH index describe the similar effect: (1) TC-FDBSCAN is obviously superior to other methods; (2) AGNES is obviously inferior to others; (3) HCM and FCM show the similar results, while FCM is better than HCM; (4) DBSCAN and SNNC show that their clustering performance are close, while SNNC is better than DBSCAN. Overall, the proposed method can find better clustering division and provide high clustering accuracy for large-scale trajectory data in travel pattern analysis.Figure 7
Boxplot diagram of the clustering evaluation for case data. (a) DB index. (b) CH index.
(a)(b)


## 5. Conclusion

Clustering taxi trajectory based on similarity measurement is a widely applied way to explore urban travel patterns. This study proposes an improved TC-FDBSCAN to uncover urban travel patterns. The taxi trajectory data collected in Shenzhen city is used to evaluate clustering results in the case study. The dataset is divided into two parts, workdays and weekends, which are be used in clustering analysis and model comparison. Some main findings are concluded in following aspects. (1) Both on workdays and weekends, the trajectories in clusters are mainly distributed on the arterial roads. However, clustering results show that, on weekends, the range of residents’ travel is wider than that analyzed on workdays. (2) Introducing the fuzzy theory into traditional DBSCAN algorithm can improve clustering performance according to three evaluation indicators. (3) Different attributes of trajectories have different influences on clustering results according to the values of weight coefficients.There are still some limitations which need to be improved in future study. On the one hand, other fuzzy clustering methods need to be studied to reduce computational complexity of the algorithm. On the other hand, other fuzzy theory such as weight entropy should be combined in the trajectory clustering method. Moreover, the proposed method is also necessary to be applied in different cities to prove its universality.



---

*Source: 6651718-2021-02-04.xml*