=Paper=
{{Paper
|id=Vol-2578/BMDA6
|storemode=property
|title=A novel spatio-temporal clustering technique to study the bike sharing system in Lyon
|pdfUrl=https://ceur-ws.org/Vol-2578/BMDA6.pdf
|volume=Vol-2578
|authors=Marta Galvani,Agostino Torti,Alessandra Menafoglio,Simone Vantini
|dblpUrl=https://dblp.org/rec/conf/edbt/GalvaniTMV20
}}
==A novel spatio-temporal clustering technique to study the bike sharing system in Lyon==
https://ceur-ws.org/Vol-2578/BMDA6.pdf
A novel spatio-temporal clustering technique to study the bike
sharing system in Lyon
Marta Galvani∗ Agostino Torti†
University of Pavia Politecnico di Milano
Pavia, Italy Milan, Italy
marta.galvani@unipv.it agostino.torti@polimi.it
Alessandra Menafoglio‡ Simone Vantini§
Politecnico di Milano Politecnico di Milano
Milan, Italy Milan, Italy
alessandra.menafoglio@polimi.it simone.vantini@polimi.it
ABSTRACT the bike sharing program has been widely adopted by major
In the last decades cities have been changing at an incredible regions like Europe, North America and Asia-Pacific.
rate growing the needs of efficient urban transportation to avoid Bike sharing systems (BSSs) have become a common feature
traffic jams and high environmental pollution. In this context, of all metropolitan areas and according to a 2019 Global Market
bike sharing systems (BSSs) have been widely adopted by major Insights, Inc. report, it has been predicted that the fleet size of
regions like Europe, North America and Asia-Pacific becoming a bike sharing market will gain over 8% from 2019 to 2025, leading
common feature of all metropolitan areas. Its fast growing has the worldwide industry revenue to surpass a valuation of USD
increased the need of new monitoring and forecasting tools to 10 billion.
take fast decisions and provide an efficient mobility management. This fast growth has urged scientists in developing suitable moni-
In this context we focus on the BSS of Lyon in France, called toring and forecasting tools to handle with mobility management
Vélo’v. In particular we analyse a dataset containing the loading and make feasible and efficient future plans [5]. Many studies
profiles of 345 bike stations over one week, treating the data as have demonstrated that an efficient analysis of the data collected
continuous functional observations over a period of one day. The by BSSs can provide good insights for the service design, i.e. for
aim of this work is to identify spatio-temporal patterns on the the reallocation strategies optimization, to underly the causes
usage of bike sharing stations, identifying groups of stations and of network imbalance and for the adjustment of pricing policies
days with similar behaviour, with the purpose of providing useful ([10], [14], [1]).
information to the fleet managers. To this scope, we develop a Most BSSs provide open access to their data regarding the real-
novel bi-clustering algorithm able to deal with functional data, time status on their bike stations. In this context we focus on
extending a nonparametric algorithm developed for multivariate the BSS of Lyon, called Vélo’v. Launched in 2005, Vélo’v is the
data. This new algorithm is able to find simultaneously subsets first bicycle-sharing system in France, with a network of more
of rows and columns with similar behaviour when the elements than 3000 bikes spread over 345 stations in Lyon and neighboring
of the dataset are functional objects. Villeurbanne. The service has been developed by street furniture
Obtained results show that through this analysis it is possible company JCDecaux for Lyon Metropole and it counts now more
to identify different usage patterns according to the area of the than 68.500 subscribers.
city and the day of the week. In this work we analyse a dataset containing the loading pro-
files of 345 bike stations over one week during the period from
Monday 10th March until Sunday 16th March in 2014. The real
1 INTRODUCTION time data are available at https://developer.jcdecaux.com/ trough
Due to urbanization and globalization in the last decades, cities an api key and they were first used in [3]. Specifically, for each
have been changing at an incredible rate. In particular a growing station the number of available bikes divided by the total number
need of urban transportation has increased the number of vehicle of bike docks at each hour is recorded.
usage on roads and ultimately led to heavy traffic jams and high The aim of our work is to understand the spatio-temporal pat-
environmental pollution. To alleviate the above growing issues, terns of the bike stations usage, providing useful information
for the correct management of the service. We are interested in
∗ Department of Mathematics understanding how bike sharing stations are used according to
† MOX Laboratory for Modeling and Scientific Computing - Department of Mathe- their spatial position looking at the variability within and be-
matics. tween days.
Center for Analysis Decisions and Society, Human Technopole.
‡ MOX Laboratory for Modeling and Scientific Computing - Department of Due to the continuous dependence on time of our data, we decide
Mathematics. to model them making use of tools from Functional Data Analysis
§ MOX Laboratory for Modeling and Scientific Computing - Department of
(FDA), the branch of statistics dealing with curves, surfaces or
Mathematics. anything else varying over a continuum (e.g., [13]). In this way
it is possible to consider the within-day variability.
© 2020 Copyright held by its author(s). Published in the Workshop Proceedings From a statistical point of view, we are facing with a problem of
of the EDBT/ICDT 2020 Joint Conference, (March 30-April 2, 2020, Copenhagen,
Denmark) on CEUR-WS.org: clustering both the bike stations and the days of the week, which
Use permitted under Creative Commons License Attribution 4.0 International (CC is know in the literature as a bi-clustering problem. The main aim
BY 4.0)
Í |I | Í | J |
of bi-clustering (or co-clustering) algorithms is to simultaneously where f I J (t) = |I |1| J | i=1 j=1 fi j (t). For easiness of interpre-
group individuals and features into homogeneous sets, see [11] tation we define the bi-cluster template observing only the aver-
for a complete review of bi-clustering methodologies. age function in the bi-cluster.
As for each station and for each day we define the bike station Consequently, the extended H -score of a bi-cluster A′ (I, J ) is:
loading profile as a continuous functional datum, we have found ∫
ourselves with a problem of bi-clustering functional data. Differ- HI J = H I J (t)
T
ent methodologies, which extend some well known algorithm
Í |I | Í | J | 2
with H I J (t) = |I |1| J | i=1 j=1 fi j (t) − [f I J (t)] .
for clustering multivariate data, have been proposed in the liter-
ature with the aim of clustering functional data [9]. In the same The pseudo-code of the Algorithm to find a bi-cluster works as
way, bi-clustering methods can be generalized to functional data expressed in algorithm 1. The algorithm starts considering the
by defining new algorithms able to detect functional bi-clusters. whole dataset and try to find the biggest bi-cluster with a H -score
Although the concept of bi-clustering was first introduced by value lower then a given threshold δ . The rows/columns addition
[7] in the 1970s, [4] are recognized as the first ones to propose and deletion procedures are a natural extension of the ones in-
a bi-clustering algorithm. Subsequently different model based troduced in [4]. The procedure follows the main structure of the
approaches have been proposed, among them [6] relies on the original Cheng and Church algorithm, except for the masking
latent block model. Starting from it, [2] introduce a parametric procedure. Indeed, instead of this step, after finding a new bi-
model able to deal with functional data. Although, as based on cluster, a set of all the biggest submatrices containing elements
Latent block model, this approach is able to detect exhaustive not already assigned is found through the Bimax algorithm ([12]).
bi-clustering maintaining a checkerboard structure that does not Then, in the next iteration, the new bi-cluster is searched inside
always fit with the real situations. the biggest submatrix found. Each time a new bi-cluster is found
In this work we introduce a novel methodology based on the the set of the submatrices of not assigned elements is updated;
extension of the Cheng and Church algorithm with the aim of otherwise a new bi-cluster is searched in the following biggest
detecting functional non exclusive bi-clusters. We propose an it- submatrix in the set.
erative procedure based on a non parametric approach obtaining
a deterministic strategy that does not have to rely on strong mod- Algorithm 1: Functional Cheng and Church algorithm
elling assumptions of the data, which are generally not consistent
in the FDA framework, and allows for flexible non exclusive bi- Input: (n, m) matrix A whose elements are functions
clusters. fi j (t)
The rest of this paper is organized as follows: in Section 2 we de- δ >0 the maximum acceptable H -score
scribe the functional Cheng and Church bi-clustering, discussing maxIter the maximum number of allowed
how the extension of the algorithm is implemented. In Section 3 iterations
the introduced methodology is applied on the Vélo’v BSS and the Result: A set of Bi-clusters with H -score< δ
main results are reported. In Section 4 conclusions are presented Set M=A
and discussed, underlying the spatio-temporal patterns found in while iter < maxIter and submatrices to search in for
the data employing the novel algorithm proposed in this work. bi-clusters are present do
Given a submatrix M:
2 METHODOLOGY: THE FUNCTIONAL while H -score> δ and deletion/addition is still possible
do
CHENG AND CHURCH ALGORITHM
(1) Multiple Node Deletion:
Given a dataset arranged in a matrix A composed by n rows remove groups of rows/cols
and m columns, the aim of a bi-clustering technique is to find (2) Single Node Deletion:
a submatrix A′ ∈ A, corresponding to a subset of rows I and a remove the row/col that reduce H -score
subset of columns J , with a high similarity score. In particular, in the most
the Cheng and Church algorithm ([4]), an ideal bi-cluster is a set (3) Node Addition:
of rows I and a set of columns J such that each element ai j in the add rows/cols that do not make H -score
bi-cluster can be expressed as ai j = a I J + α i + β j ∀i ∈ I and ∀j ∈ greater than δ
J , where a I J is the average value in the bi-cluster and α i and
end
β j are respectively the residue of rows and columns average
if A new bi-cluster is found then
value and the total average value a I J . A particular measure of
Apply Bimax to search for all the biggest
goodness is evaluated for a bi-cluster A′ (I, J ) considering a score
submatrices of not assigned elements and select
H which is the Mean Squared Residue between all the real values
the biggest one as M
ai j ∈ A′ (I, J ) and their representative values in the bi-cluster
else
a I J + αi + β j . Select as M the following biggest submatrix
Extending these concepts to FDA, each element of the dataset end
matrix A is a function fi j (t) defined on a continues domain T . In end
such framework we define an ideal bi-cluster A′ as a subset of
rows I and columns J such that each function belonging to the
bi-cluster A′ (I, J ) can be defined as follows:
As in the classical Cheng and Church, the results are sensitive
to the choice of the input parameter δ . Indeed, a too high value
of δ would imply a unique big bi-cluster, while a too low value
fi j (t) = f I J (t) ∀i ∈ I and ∀j ∈ J
would imply a really large number of bi-clusters or even the
Figure 1: Functions belonging on each bi-cluster with their templates
impossibility to find a bi-cluster. To tune the parameter δ , we of the weekends (e.g. bi-clusters 4, 5, 6), while some other con-
perform a sensitivity analysis on the number of obtained clus- sidered stations that have the same pattern during working and
ters, the number of not assigned observations and the sum of weekend days (e.g. bi-clusters 1, 15, 18).
the H scores over all the found bi-clusters. Then, following the Turning our attention on the found bi-clusters, Figure 1, it is
same approach used for many other clustering techniques as the possible to interpret results as a way of segment the city in differ-
classical k-means, we choose the value of δ where an elbow or a ent activity areas according to the day of the week and the hour
peak are found. of the day. Observing the usage profiles of the bi-clusters, three
main groups can be identified: the constant profile, the residential
profile and the working profile.
3 DATA ANALYSIS AND RESULTS The constant profile bi-clusters show flat functions of usage dur-
The first step of our analyses is to treat the available raw data as ing the whole day implying a no usage or a continuous replace-
continuous functions. Specifically, for each station and for each ment of bikes in these stations. Among these, the always Full
day we define, through a kernel density estimation smoothing (e.g. bi-clusters 3, 6 and 9) and Empty stations (e.g. bi-clusters 13,
method [8], the bike station loading profile as a continuous func- 16 and 20), which necessarily imply user dissatisfaction as they
tional datum representing the number of available bikes divided respectively cannot drop-off or pick-up a bike, are of particular
by the total number of bike docks at each timestamp. In this way interest.
we obtain 2415 curves, i.e. 345 stations per 7 days, representing The working profile (e.g. bi-clusters 4, 10 and 14) and the residen-
all the elements fi j (t) (with t ∈ [0, 24]) of a dataset matrix A tial profile (e.g. bi-clusters 2 and 37) instead, are characterised by
with the same dimensions (345x7). Functional Cheng and Church a huge activity during rush hours in the morning, around 8a.m.,
algorithm, presented in the previous section, can be applied on and in the evening, around 7p.m.. However, the two groups show
this dataset. an opposite behaviour since while the first one fills up in the
To find the set of the best bi-clusters, a threshold δ must be pro- morning and empties out in the evening, instead, the second one
vided to the algorithm. After performing a sensitivity analysis to empties out in the morning and fills up in the evening. More-
choose the threshold parameter δ we fix δ equal to 0.025. over, looking at the days inside the working profile and residential
Results are shown in Figure 1. There are in total 94 bi-clusters profile groups, it appears that these bi-clusters are composed by
while the not assigned observations are artificially assigned to working days. The peculiarity of these two groups reveal a clear
bi-cluster 0. For each bi-cluster all the functions contained in that commuting behaviour of the bike sharing users which move dur-
bi-cluster are shown together in colors; the template function, de- ing working days in the morning and evening rush hours.
fined as the average curve of the bi-cluster, is displayed in black. To better explore these two behaviours, we focus, as explanatory
Looking at the bi-cluster dimensions (i.e. the number of curves in example, on bi-clusters 2 and 4. In Figure 2 and 3 results on these
the bi-cluster), the obtained results are able to explain the 75% of two bi-clusters are reported; in particular all the functions be-
the data, while the 25% of the functions are not assigned to any longing to the bi-cluster with the bi-cluster template (in black),
bi-clusters. Note that the found bi-clusters have been ordered the corresponding days and bike stations location are shown.
from the biggest one to the smallest one, considering the num- Observing Figure 2 it is possible to say that Bi-cluster 2 is a block
ber of included rows and columns. Evaluating the percentage of composed from 34 stations and 5 days (from Monday to Friday),
working and weekend days for each bi-cluster, we notice that covering almost the 7% of all the data. It is characterised from full
some bi-clusters cover specific patterns of the working days or stations before 8a.m. and after 8p.m. and empty stations during
Figure 2: Functions in bi-cluster 2 with calendar and bike Figure 3: Functions in bi-cluster 4 with calendar and bike
stations position on the map of Lyon stations position on the map of Lyon
4 CONCLUSION
The aim of our work is to study the spatio-temporal patterns
the rest of the day. This peculiar behaviour is justified by the of the Vélo’v BSS usage profile during a one week period in
fact that these stations are mostly located in residential areas Lyon providing useful information to the fleet managers. To this
in the East of the city. An opposite behaviour is instead present end, we model the usage profiles of the different bike stations
in all the stations belonging to bi-cluster 4 (Figure 3) which are around the city day by day as continuous functions with the
full between 8a.m.-8p.m. and empty in the rest of the day. This aim of discovering subgroups of stations and days with similar
behaviour is easily explainable by the fact that these stations are behaviour, which is know in the literature as a bi-clustering
located in parts of the city with many companies where people problem.
are used to commute during the day. This bi-cluster is composed To build our analyses, we introduce a novel non parametric bi-
by 17 stations and again the 5 working days from Monday to clustering algorithm extending the Cheng and Church algorithm
Friday, covering the 3.5% of the total observations in the data. in the FDA framework. From a methodological point of view
Another small group of bi-clusters, almost covering weekend the concept of ideal bi-cluster is extended for functional data
days, can be described as weekend profile (e.g. bi-clusters 6, 7 and a new score evaluation for found bi-clusters is introduced.
and 73). For instance, bi-cluster 73 (Figure 4) contains the daily In addition the new introduced algorithm overcomes the main
usage profiles of 3 stations for the entire weekend. The peculiar- weaknesses of the original Cheng and Church, avoiding the usage
ity of this bi-cluster is that the concerned bike stations are in of the masking procedure and introducing a greedy search in the
the city center, very closed to River Sâone banks, where there not already assigned elements. The developed algorithm allows
are many shops and bars especially active during the weekends. to find non exclusive bi-clusters with a H -score lower than a
It is possible to see, observing Figure 4, that these stations are given value δ , through a non parametric procedure. This has the
filled up during evening until they become almost totally full advantage of avoiding to rely on strong modelling. A sensitivity
before midnight and then they slowly empty out during the night. analysis for the δ parameter tuning is also presented.
This behaviour can be explained considering that people go out From a practical point of view, the developed approach is
clubbing during evening and then they return back home late in applied to study the daily usage profiles of all the 345 stations of
the night. the Vélo’v BSS in Lyon for one week in March 2014. Results show
REFERENCES
[1] Pierre Borgnat, Celine Robardet, Jean-Baptiste Rouquier, Patrice Abry, Patrick
Flandrin, and Eric Fleury. 2011. Shared Bicycles in a City: A Signal Processing
and Data Analysis Perspective. Advances in Complex Systems 14 (06 2011).
https://doi.org/10.1142/S0219525911002950
[2] Charles Bouveyron, Laurent Bozzi, Julien Jacques, and François-Xavier Jollois.
2018. The functional latent block model for the co-clustering of electricity
consumption curves. Journal of the Royal Statistical Society: Series C (Applied
Statistics) 67, 4 (2018), 897–915.
[3] Charles Bouveyron, Etienne Côme, Julien Jacques, et al. 2015. The discrimi-
native functional mixture model for a comparative analysis of bike sharing
systems. The Annals of Applied Statistics 9, 4 (2015), 1726–1760.
[4] Yizong Cheng and George M Church. 2000. Biclustering of expression data..
In Ismb, Vol. 8. 93–103.
[5] Elliot Fishman. 2016. Bikeshare: A Review of Recent Literature. Transport
Reviews 36, 1 (2016), 92–113. https://doi.org/10.1080/01441647.2015.1033036
[6] Gérard Govaert and Mohamed Nadif. 2013. Co-clustering: models, algorithms
and applications. John Wiley & Sons.
[7] John A Hartigan. 1972. Direct clustering of a data matrix. Journal of the
american statistical association 67, 337 (1972), 123–129.
[8] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2001. The Elements of
Statistical Learning. Springer New York Inc., New York, NY, USA.
[9] Julien Jacques and Cristian Preda. 2014. Functional data clustering: a survey.
Advances in Data Analysis and Classification 8, 3 (2014), 231–255.
[10] Neal Lathia, Saniul Ahmed, and Licia Capra. 2012. Measuring the impact of
opening the London shared bicycle scheme to casual users. Transportation
Research Part C: Emerging Technologies 22 (2012), 88 – 102. https://doi.org/10.
1016/j.trc.2011.12.004
[11] Beatriz Pontes, Raúl Giráldez, and Jesús S Aguilar-Ruiz. 2015. Biclustering
on expression data: A review. Journal of biomedical informatics 57 (2015),
163–180.
[12] Amela Prelić, Stefan Bleuler, Philip Zimmermann, Anja Wille, Peter Bühlmann,
Wilhelm Gruissem, Lars Hennig, Lothar Thiele, and Eckart Zitzler. 2006. A
systematic comparison and evaluation of biclustering methods for gene ex-
pression data. Bioinformatics 22, 9 (2006), 1122–1129.
[13] J. O. Ramsay and B. W. Silverman. 2005. Functional data analysis. Springer,
New York.
[14] Patrick Vogel, Torsten Greiser, and Dirk Christian Mattfeld. 2011. Understand-
ing Bike-Sharing Systems using Data Mining: Exploring Activity Patterns.
Procedia - Social and Behavioral Sciences 20 (2011), 514 – 523.
Figure 4: Functions in bi-cluster 73 with calendar and bike
stations position on the map of Lyon
clear patterns of usage allowing to segment the city in different
activity areas according to the day of the week and the hour of the
day. For instance, a commuting behaviour is observed revealing
that stations next to residential areas and working areas have an
opposite behaviour during working days. It is interesting to notice
that despite no apriori information about the spatial distribution
of the stations are taken into account by the model, it appears
that stations belonging to the same bi-cluster are actually located
in neighborhoods with the same socio-economic characteristics.
Moreover, groups of stations always full or always empty are
highlighted, revealing some criticalities of the service.
In conclusion, our work contributed to implement the study of a
bike sharing system in two ways: from a methodological point of
view, we defined a novel non parametric bi-clustering technique
for functional data; from an applied point of view, we analysed
the bike sharing system in the city of Lyon providing useful
information for the correct management of the service.