Comparing Clustering Methods in Recognition of Temporal Travel Pattern of Public Transport

Les organismes de transport en commun doivent étudier les habitudes de déplacement afin d'élaborer des stratégies et des plans plus conformes aux habitudes d'utilisation de leur réseau. De nombreuses études ont été réalisées sur le comportement des passagers pour aider les autorités de transport à mieux comprendre leurs services. En facilitant la collecte des données, les systèmes de paiement par cartes à puce a rendu possible l'exploration de ces précieuses données sur les déplacements. Pour reconnaître les comportements de déplacement, des méthodes de clustering sont utilisées. En regroupant les passagers ayant le comportement le plus similaire dans un même cluster, nous pouvons alors adapter les stratégies de transport en fonction de ces groupes plutôt que les appliquer à tous les usagers . Les données des cartes à puce ayant des caractéristiques de séries temporelles, le développement de la méthode la plus appropriée pour traiter ces séquences permettra d'obtenir un processus de segmentation plus précis et pertinent. Le choix d'une mesure de distance appropriée, ainsi que de la méthode elle-même, est crucial dans les algorithmes de clustering de séries temporelles. Dans les études précédentes sur les données des cartes à puce, les distances euclidiennes et Manhattan sont le plus souvent utilisées avec les méthodes de clustering. Cependant, toutes deux ignorent les caractéristiques des séquences et les comparent dans leurs calculs comme des données statiques, sans tenir compte de leur ordre ou de leurs corrélations. Certains auteurs ont tenté de résoudre ce problème dans leurs recherches. En proposant une méthode de projection pour transférer les données de séries temporelles vers des espaces tridimensionnels et en appliquant ensuite des techniques de clustering (Ghaemi et al., 2017) ou en choisissant la distance de corrélation croisée (CCD) comme mesure de distance plus appropriée pour la comparaison de séries temporelles (He et al., 2018). Cependant, comme ils ont utilisé le clustering hiérarchique avec CCD, ils ont été obligés d'utiliser une stratégie d'échantillonnage en raison de la limitation du clustering hiérarchique avec de grands ensembles de données. La mesure de distance dynamic time warping (DTW) est une autre distance appropriée pour la comparaison de séries temporelles, mais elle souffre d'une complexité temporelle. L'objectif de cette étude est de combler cette lacune. Pour ce faire, un nouveau clustering k-shape avec une mesure de distance basée sur la forme (SBD) est testé et appliqué pour la première fois aux données des cartes à puce dans les transports publics. Cette méthode a été proposée par Paparrizos and Gravano (2017) pour le regroupement de séries temporelles. Elle est précise, efficace et rapide. Nous développons un cadre de comparaison entre les résultats de cette nouvelle méthode, le DTW et les mesures de Distances Euclidiennes (ED) sur le même ensemble de données afin d'explorer leurs avantages et leurs inconvénients. Ce faisant, nous utilisons le regroupement k-means ainsi que les distances DTW et ED pour avoir une comparaison significative entre les performances des mesures de distance. Nous appelons nos trois méthodes DTW, SBD et ED. Notre cadre de comparaison comporte trois critères, mais avant cela, nous avons utilisé le résultat de DTW comme vérité de base pour construire une comparaison plus structurée. Tout d'abord, DTW est comparé à SBD et ED sur la base de la distance moyenne entre les centroïdes des clusters. Celui dont la distance est la plus courte est donc considéré comme le plus compatible avec DTW. Deuxièmement, la comparaison est basée sur deux indices externes de validation des clusters : l'indice Rand ajusté (ARI) et l'indice de variation de l'information (VI). Plus l'ARI est élevé, plus les deux approches sont en accord. Un VI plus faible, en revanche, indique que les deux techniques sont plus identiques. Enfin, en plus des mesures statistiques, nous comparons les approches en fonction des modèles qu'elles ont identifiés et de la distribution de leurs clusters sur chaque jour, ainsi que de la distribution des produits tarifaires. En outre, comme le type de vecteurs, ainsi que la méthode, ont un impact significatif sur les résultats finaux, nous utilisons trois types de profils différents pour comparer les performances des méthodes. Les données d'entrée de nos trois approches sont des vecteurs carte-jour (utilisateur-jour), arrêt-jour et itinéraire-jour, et nous pouvons voir si la comparaison est restée la même lorsque les vecteurs ont changé. Ces vecteurs sont basés sur le temps d'embarquement, c'est-à-dire le moment où les passagers effectuent une transaction lorsqu'ils utilisent les transports publics au quotidien. Les données de cette étude proviennent du Réseau de transport de la Capitale (RTC), une agence de transport qui offre des services de transport en commun à Québec, et ont été recueillies sur le réseau d'autobus pendant un mois, en février 2019. Les résultats de cette recherche contribuent non seulement à la littérature croissante sur les données des cartes à puce, mais confirment également que la distance euclidienne, malgré sa popularité, ne fonctionne pas bien dans la reconnaissance de modèles bien définis lorsqu'il s'agit de données de séries temporelles. En outre, bien que le clustering k-means avec la distance DTW soit une approche appropriée pour la segmentation des séries temporelles, il souffre de sa complexité temporelle. Le clustering K-shape avec SBD est une méthode puissante de reconnaissance des formes, qui a été testée pour la première fois pour le clustering de données de cartes à puce. Cependant, elle ne prend pas en compte le décalage temporel, ce qui pourrait avoir pour conséquence de mettre des séries temporelles de même forme dans le même groupe alors qu'elles pourraient avoir un décalage temporel. Il a cependant produit des résultats compétitifs dans la création de clusters de routes lorsque le décalage temporel était moindre. Dans l'ensemble, cette constatation démontre qu'il n'existe pas de solution unique au problème du regroupement des séries chronologiques. Chaque méthode présente des avantages et des inconvénients qui doivent être examinés en fonction du type et du volume de données, du type de distorsions imposées aux données, de l'objectif de l'étude et de la durée d'application de la méthode. SBD est une nouvelle méthode de regroupement de séries temporelles qui a été introduite dans cette thèse et qui peut être utilisée pour une variété d'objectifs dans le domaine du transport, comme l'étude des fluctuations. Elle peut également être réglée pour être contrainte au décalage temporel ou même combinée avec d'autres méthodes.

Abstract

Transit agencies need to investigate travel patterns in order to develop strategies and plans that are more in line with usage patterns. There has been a lot of study done on passenger behaviour to help transportation authorities gain a better understanding of their services. By facilitating data collection, smart card system has made these studies more possible to explore valuable detailed travel data. For recognizing travel behaviour, clustering methods are used. By grouping passengers with the most similar behaviour in the same cluster, we can then adapt the transport strategies based on these groups rather than a large number of individuals. Since smart card data has the characteristics of time-series, developing the most suitable method to handle these sequences will results in more accurate segmentation process. Choosing a proper distance measure, as well as the method itself, is crucial in time-series clustering algorithms. In previous studies of smart card data, Euclidean and Manhattan distances are most often used with clustering methods. However, both of them ignore the characteristics of sequences and compare them in their calculations as static data without considering their order or correlations. Some authors have tried to address this problem in their research. By proposing a projection method to transfer time-series data to three dimensional spaces and then applying clustering techniques (Ghaemi et al., 2017) or by choosing Cross Correlation Distance (CCD) as a more suitable distance measure for time-series comparison (He et al., 2018). However, since they used hierarchical clustering with CCD, they were forced to plan a sampling strategy due to the limitation of hierarchical clustering with large dataset. DTW distance measure is another suitable distance for time-series comparison, but it suffers from time complexity. The purpose of this investigation is to address this gap. To do this, a novel k-shape clustering with Shape-Based Distance measure (SBD) is tested and applied to smart card data in public transit for the first time. This method has been proposed by Paparrizos et al. (2017) for time-series clustering, which is accurate, efficient, and very fast with large dataset. We develop a comparison framework among the results of this novel method, DTW, and Euclidean distance (ED) on the same dataset in order to explore their advantages and drawbacks. In doing so, since k-shape clustering is based on k-means principles, we used k-means clustering along with DTW as a suitable distance metric for time-series, and ED as a most used distance in the literature, to have a meaningful comparison between distance measures' performance. For simplicity, we call our three methods as DTW, SBD, and ED. Our comparison framework has three criteria, and in order to build a more structured comparison we used DTW result as the ground truth. First, DTW is compared with SBD and ED based on the average distance between cluster centroids. The one with the shortest distance was therefore considered the most compatible with DTW. Secondly, the comparison is based on two cluster validations external indices: Adjusted Rand Index (ARI) and Variation of Information (VI) index. The higher the ARI, the closer the two approaches agree. Less VI, on the other hand, indicates that two techniques are more identical. Finally, in addition to statistical measurements, we compared the three approaches based on the usage patterns of their resulted clusters. Furthermore, because the type of vectors, as well as the method, has a significant impact on the final outcomes, we employed three different types of profiles with different time-shifting patterns to compare the performance of the methods. The input data for our three approaches were card-day (user-day), stop-day, and route-day vectors, and we can see whether the comparison remained the same when the vectors changed. These vectors are based on the boarding time, which is when passengers make a transaction when using public transportation on a daily basis. The data for this study came from the Réseau de transport de la Capitale (RTC), a transportation agency that offers transit services in Québec City and was gathered from the bus network over one month in February 2019. Results of this research not only contribute to the growing literature on smart card data, but also confirm that ED in spite of its popularity does not work well in recognition of well-defined patterns when it comes to time-series data. Besides, although k-means clustering with DTW distance is a proper approach for time-series segmentation, it suffers from the time complexity. K-shape clustering with SBD is a powerful method in pattern recognition, which was tested for the first time for smart card data clustering, however, it does not take into account time shifting which could result in putting time-series of the same shape in the same group while they might have a time difference. It however, produced competitive results in the creation of route clusters when the shifting in time was less. On the other hand, the application time of this method was faster than DTW impressively.