S a ion Segmen a ion o Lisbon bicycle sha ing
sys em based on use s demand and supply
Ma isa Ma inho Fe nandes
P ojec wo k p esen ed as he pa ial equi emen o
ob aining a Mas e 's deg ee in In o ma ion Managemen
NOVA In o ma ion Managemen School
Ins i u o Supe io de Es a ís ica e Ges ão de In o mação
Uni e sidade No a de Lisboa
STATION SEGMENTATION OF LISBON BICYCLE SHARING SYSTEM
BASED ON USERS DEMAND AND SUPPLY
Ma isa Ma inho Fe nandes
P ojec Wo k p esen ed as he pa ial equi emen o ob aining a Mas e 's deg ee in In o ma ion
Managemen , Specializa ion in Knowledge Managemen and Business In elligence
Ad iso : Mau o Cas elli
Janua y 2021
iii
ACKNOWLEDGEMENTS
I would like o hank e e yone ha c ossed my pa h du ing my academic li e and con ibu ed o
en ich my li e and o my pe sonal and academic g ow h.
A wa m hank you o my amily, in special o my pa en s ha suppo ed me in his jou ney and
wo ked ha d all hei li es o make su e ha I had he oppo uni y o educa e mysel and pu sui o a
be e and p ospe ous u u e o me.
A huge hank you o Mau o Cas elli ha i elessly suppo ed me h oughou my mas e hesis,
wi hou him o achie ing his ma k on my li e would ha e been much mo e di icul .
All my iends ha kep on o e ing me all he suppo ha I need and kep on eminding me ha I
was almos he e, a big hank you ollowed by a big hug, wi hou you his jou ney would ha e been
lonelie .
A las , bu no leas , an eno mous hank you o mysel o keeping on his p ojec while wo king,
o no s opping belie ing ha i was possible hough di icul , o no accep ing he emp ing hough
o “I can lea e i o he nex yea ”, o keeping de e minedly ai h ul o my ambi ion.
i
E e yone hinks o changing he wo ld, bu no one hinks o changing himsel .
Leo Tols oy
ABSTRACT
Bike-sha ing sys ems a e well known in he sus ainable mobili y ield and ha e se e al aspec s ha
need op imiza ion and imp o emen . One o he mos ele an aspec s is s a ion segmen a ion based
on use demand and supply, and i is he ocus o he hesis. The segmen a ion wo k has an eno mous
po en ial o educe complexi y in p edic ing he bicycle demand and supply, hus imp o ing he o e all
quali y o se ice.
Se e al machine lea ning algo i hms we e used o in es iga e he a o emen ioned segmen a ion
ask. This wo k conside s wo popula and well-known clus e ing algo i hms o ex ac and analyze
in e es ing pa e ns, like he di e ence be ween a i als and depa u es h oughou ime and s a ions:
he DBSCAN (Densi y-Based Spa ial Clus e ing o Applica ions wi h Noise) and he hie a chical
clus e ing.
The algo i hms a e applied o he speci ic case o GIRA, he bicycle sha ing sys em (BSS) o he ci y
o Lisbon. The ob ained esul s sugges ha conside ing he a iables unde analysis, he op imal
numbe o clus e s o be used in a second phase o he BSS op imiza ion (demand and supply o ecas )
is he same as he numbe o s a ions in he Lisbon BSS. The esul s a e e y insigh ul and allow u u e
wo k o ocus ei he on he demand o ecas o he en ichmen o he a iables unde s udy.
KEYWORDS
Machine lea ning; Timese ies segmen a ion; Bike-sha ing sys ems; Sus ainable mobili y

i
Index
1. In oduc ion .................................................................................................................. 1
2. Rela ed wo k ................................................................................................................. 3
3. Da a unde s anding ...................................................................................................... 6
4. P e-p ocessing .............................................................................................................. 8
4.1. Da a cleaning ......................................................................................................... 8
4.2. Da a in eg a ion................................................................................................... 10
4.3. Da a Reduc ion .................................................................................................... 11
4.4. Da a T ans o ma ion ........................................................................................... 12
5. Bike S a ions dimensionali y educ ion ...................................................................... 13
5.1. Unsupe ised lea ning s Supe ised lea ning .................................................... 13
5.1.1. Unsupe ised lea ning .................................................................................. 13
5.1.2. Supe ised lea ning ...................................................................................... 13
5.2. Unsupe ised lea ning applied o ime se ies ..................................................... 13
5.3. Dis ance measu e ................................................................................................ 14
5.4. Algo i hms o unsupe ised lea ning ................................................................. 15
5.4.1. Hie a chical Clus e ing ................................................................................. 15
5.4.2. Densi y-based spa ial clus e ing o applica ions wi h noise (DBSCAN) ....... 16
5.5. Measu ing clus e quali y .................................................................................... 17
5.5.1. In insic e alua ion me hods ........................................................................ 18
6. Resul s, conclusion and u u e wo k .......................................................................... 19
7. Bibliog aphy ................................................................................................................ 22
ii
LIST OF TABLES
Table 1 - Bicycle s a ion ile - in o ma ion ................................................................................. 6
Table 2 - Bicycle ips ile - in o ma ion ..................................................................................... 6
Table 3 - Incohe ence example 1 ............................................................................................... 9
Table 4 - Incohe ence example 2 ............................................................................................... 9
Table 5 - Incohe ence example 3 ............................................................................................. 10
Table 6 - Incohe ence example 4 ............................................................................................. 10
Table 7 - New ea u es in o ma ion ......................................................................................... 11
Table 8 - Di e ences be ween unsupe ised and supe ised lea ning (Jones, Johns on, &
K uge , 2019) .................................................................................................................... 13
Table 9 - Calcula ions o he DTW dis ance be ween ime se ies a and b (Izakian, Ped ycz, &
Jamal, 2015) ..................................................................................................................... 15
Table 10 - DBSCAN algo i hm (Chauhan, 2020) ....................................................................... 17
Table 11 - Time se ies clus e ing esul s .................................................................................. 20
iii
LIST OF ABBREVIATIONS AND ACRONYMS
PCA P incipal Componen Analysis
IST Ins i u o Supe io Técnico
DTW Dynamic Time Wa ping
BSS Bicycle Sha ing Sys ems
FFBSS F ee-Floa ing Bicycle Sha ing Sys em
SBRP S a ic Bicycle Reposi ioning Sys em
DBRP Dynamic Bicycle Reposi ioning Sys em
ANN A i icial Neu al Ne wo k
DBSCAN Densi y-based spa ial clus e ing o applica ions wi h noise
1
1. INTRODUCTION
A bicycle sha ing sys em (BSS) can be de ined as a ne wo k o bicycles sp ead in a ci y, a ailable o
use s. A use can ake a bicycle a he s a ing poin , d i e i un il he des ina ion poin and lea e he
bicycle whe e he ip inished, momen in which he bicycle will become a ailable o o he use s.
Bicycle sha ing sys ems gained popula i y in ecen yea s and became a popula se ice in majo
ci ies. The i s BSS wo ld-wide was in oduced in Ams e dam in 1965 (Shaheen, 2012) and he bicycles
we e unlocked and placed a ound he ci y. The nex BSSs wen h ough some changes and challenges:
some o hem we e paid, and some ha e su e ed om he o e en andalism. Th oughou he yea s,
BSSs became mo e popula a ound he wo ld and by he beginning o Ap il o 2020 he e we e 2102
ci ies wi h BSS, wi h app oxima ely 17866900 sel -se ice public use bicycles and elec ic assis ed
bicycles. (DeMaio & DesJa dins, s.d.).
Ci ies a e cha ac e ized by an agi a ed li e, a ic conges ion, long wai ing imes be ween public
anspo s connec ions, and bad ai quali y. BSSs can be seen as a way o coun e ac ing o minimizing
some o hese issues. In Albiński and coau ho s (Albiński, Fon aine, & Minne , 2018) wo k, a BSS is
p esen ed as a good al e na i e anspo mode wi h espec o he exis en ones ( ain, am, me o
and bus). In ac , i he ci y has a well-s uc u ed bicycle in as uc u e, iding a bicycle can be he
as es way o go om one place o ano he and, as a consequence, a ime-sa ing al e na i e. Besides
ha , i has a posi i e impac on use ’s heal h due o he exe cise done by iding a bike. Mo eo e , he
educ ion o g eenhouse gas emissions is also a ac o ha con ibu es o he BSS adop ion and i s
inc easing popula i y. Fo ma and coau ho s (Fo ma, Ra i , & Tzu , 2015) and Shui and coau ho s (Shui
& Sze o, 2018) poin ed ou ha BSS is an en i onmen ally iendly op ion and i can complemen he
public anspo a ion.
This s udy uses machine lea ning echniques o clus e docking s a ions wi h simila demand and
o e beha io s, aking in o accoun he BSS o Lisbon. The ci y made a ailable a BSS in 2017 wi h he
p ojec GIRA, and by Sep embe o 2019 i coun ed wi h 81 s a ions and a ound 600 (bo h casual and
elec ic) sha ed bicycles. The e a e wo ypes o BSS: he so-called adi ional BSS, which is
cha ac e ized by ha ing he bicycles associa ed o a docking s a ion and he ee- loa ing BSS (FFBSS)
in which he e is no a ixed place o each bicycle and he bicycles ee- loa a ound he ci y (Liu, Sze o,
& Ho, 2018). The BSS o Lisbon is a adi ional BSS.
In he con ex o a adi ional BSS, each jou ney ypically s a s om a speci ic docking-s a ion,
inishes in ano he , and he use does no need o e u n o he ini ial s a ion. This ype o beha io
con ibu es o emp y and ull s a ions. I is impo an o no e he BSSs a e e icien when s a ions a e
balanced (no emp y o ull). The e o e, unbalanced s a ions lead o ine iciency in BSS which also leads
o unsa is ied use s and, consequen ly, o a po en ial loss o use s. (Dell'Amico, Io i, No ellani, &
Sub amanian, 2018) The unbalanced s a ion is also a p oblem in he con ex o he GIRA p ojec ha
will be add essed in his wo k.
The e a e wo common app oaches o minimize he p oblem o unbalanced BSS, being he i s
use -based and he second uck-based. The use -based app oach is usually less cos ly han he la e ,
bu i a ely sol es he p oblem by i sel . In pa icula , he use -based app oach gi es a
ewa d/incen i e o use s ha s a a ip in s a ions wi h an excess o bicycles and o he use s ha
end a ip in s a ions wi h a de ici o bicycles. The uck-based app oach add esses he p oblem by
8
4. PRE-PROCESSING
This chap e will explo e one o he mos ime consuming and also one o he mos impo an asks
o he success o he algo i hm’s esul s. (Kambe , Han, & Pei, 2011)
The app oach aken in his chap e was guided by (Wi en, Pal, Hall, & F ank, 2016). The au ho s
o he book spli p e-p ocessing s ep in o 4 majo ca ego ies:
1. Da a cleaning ou ines a e applied o ha e clean he da a. Those ou ines a e pu in p ac ice
h ough: illing missing alues; smoo hing noisy da a; emo ing ou lie s and iden i ying and
esol ing inconsis encies o incohe ences.
2. Da a In eg a ion is used when he e is he need o he possibili y o ge mo e da a om
ano he da a sou ce. Ge ing mo e da a, will e y likely en ich he explanabili y o he
phenomena unde analysis. Da a in eg a ion is no all oses, i is common ha wi h i ,
edundancies, noise and inconsis encies will ise. The e o e, i ’s impo an ha his s ep is
explo ed along side wi h da a cleaning.
3. Da a Reduc ion goal is o ha e a da ase wi h less a iables bu wi h he same o almos he
same explanabili y o he phenomena. The e a e some echniques ha can be used and all
unde da a educ ion s ep, such as: dimensionali y educ ion echniques (e.g., PCA, ac o
analysis, o wa d ea u e selec ion, e c.), ea u e subse selec ion (e.g., i ele an o edundan
ea u es) o ea u e c ea ion (e.g., c ea ion o new ea u es ha summa ize o he s such as
c ea ing he a iable du a ion ins ead o ha ing da e s a and da a end).
4. Da a T ans o ma ion s ep is esponsible o ans o ming da a (i needed) in o a s a e ha will
make he modeling p ocess mode e icien . This p ocess includes se e al possible echniques,
such as: ea u e cons uc ion (e.g., c ea ion o new ea u es om exis ing ones), agg ega ion
(e.g., agg ega e da a by da e ime e e y 10 minu es ins ead o ha ing da a o he second),
no maliza ion (e.g., scale ea u es o a smalle ange) o disc e iza ion (e.g., con e o
pa i ion con inuous alues in o in e als o in o new ea u es).
4.1. DATA CLEANING
This sub-chap e will go deepe in how he i s s ep o p e-p ocessing, he da a cleaning, was
applied in he con ex o his s udy. The s eps aken will be desc ibed alongside wi h some speci ic
example o a be e unde s anding o he wo k done:
Resol e incohe encies
1) As i was men ioned in Da a unde s anding chap e , he columns “id_expl”, “id_planeamen o”
and “desig_come cial” ( he numbe s in he beginning) e e ence he same alue, he s a ion
numbe . The e o e, hose we e checked agains each o he o make su e ha i s alues we e
co ec . In he majo i y o he cases, he alues we e cohe en , in he emaining cases whe e
he alues we e no cohe en , he da a was co ec ed ha ing he “desig_come cial” numbe
has a decision make . Fo example, as i can be seen in Table 3, he id_expl and

9
id_planeamen o a e he same bu he design_come cial isn’ . As he desig_come cial has
p e alence o e he o he s, he eco ds in ques ion we e co ec ed o 103.
Table 3 - Incohe ence example 1
Id_expl
Id_planeamen o
desig_come cial
1
1
103-Ja dim da Água
2) The second case o incohe encies e i ied is he e i ica ion o he “desig_come cial” alues.
The s a ions names we e analyzed, and some i egula i ies we e no iced unde he ollowing
cases ca ego iza ion:
a. The id was he same, bu he name was sligh ly di e en .
b. The name was he same, bu he id was di e en ( ypically sequen ial, e.g., 224 and
225).
c. The e was no name, only id.
In o de o esol e hese cases, he websi e (h ps://www.gi a-bicicle asdelisboa.p /descob e-
as-es acoes/ ) whe e esides he o icial map wi h all he s a ions in Gi a’s ne wo k was aken
unde conside a ion and obse a ion.
Rega ding case a), he s a ion names we e co ec ed o he o icial name ( he name p esen in
he o icial websi e). The cases obse ed can be seen in Table 4.
Table 4 - Incohe ence example 2
Desig_come cial-1
Desig_come cial-2
Desig_come cial-decision
488 - Rua Fe nando
Namo a N35 / Rua An ónio
Quad o
488 - Rua Fe nando Namo a
n35 / Rua An ónio Quad o
488 – Rua Fe nando Namo a
/ Rua An ónio Quad os
410 - Rua da Mesqui a /
Rua D . Júlio Dan as
410 - Rua da Mesqui a
/Uni e sidade No a de
Lisboa
410 - Rua da Mesqui a
/Uni e sidade No a de
Lisboa
Rega ding case b), he wo cases iden i ied we e co ec , meaning ha he e we e wo s a ions
wi h he same name. The cases obse ed can be seen in Table 5.
10
Table 5 - Incohe ence example 3
Desig_come cial-1
Desig_come cial-2
224 - Ma im Moniz
225 - Ma im Moniz
307 - Ma quês de Pombal
Rua D . Júlio Dan as
308 - Ma quês de Pombal
Rega ding case c), he decision made was simply assigning he o icial name o he ones ha
we e missing i . The example can be seen in Table 6E o ! Re e ence sou ce no ound.
Table 6 - Incohe ence example 4
Desig_come cial-1
Desig_come cial-2
Desig_come cial-decision
303
303 - A enida da Libe dade /
Rua das P e as
303 - A enida da Libe dade /
Rua das P e as
Remo e noisy da a
Rega ding emo ing o no conside ing ce ain da a, he columns “es ado” speci ies i he s a ion
is ac i e, in epai o in s ock. Only he eco ds associa ed wi h he “es ado” in s ock o in epai we e
emo ed om he da ase . Tha choice was made, based on he ac ha he phenomena unde
analysis only s udies he s a ions ha a e ac i e and by consequen ha e ips associa ed.
4.2. DATA INTEGRATION
Da a in eg a ion chap e will go h ough he aken s eps in o de o ge mo e ea u es ha can
explain he phenomena unde analysis. Th ough hose s eps, da a om 3 di e en ex e nal sou ces
we e used:
1) Po uguese holidays websi e: om his websi e, i was possible o ga he all he o icial
Po uguese holidays o he 2018 yea and u he con e hose in o a py hon dic iona y.
2) Ins i u o Supe io Técnico wea he s a ion API: IST has a ee API wi h wea he da a, based
on a wea he s a ion loca ed in Alameda. In his case, Alameda was conside ed ep esen a i e
o he ci y o Lisbon has a wea he p oxy. The da a collec ed om his API con ains hou ly da a.
3) Sun ise and sunse API: In o de o ha e he da a needed o u he unde s and when i was
dayligh o no , da a ega ding he sunse and sun ise ime in he ci y o Lisbon was collec ed.
The da a is a da e ime wi h de ail un il he second.
11
Table 7 - New ea u es in o ma ion
Va iable
Desc ip ion
Sou ce
Sunse ime
Con aining he
da e ime (un il
seconds) o sunse
and sun ise o each
day
h ps://sun ise-sunse .o g/api
Sun ise ime
Po uguese holidays
Con ains all o icial
holidays.
h ps://www.calenda .com/po ugal/calenda io-
2018/
To al p ecipi a ion
How many millime e s
o ain
h p://me eo2-ciis .is .u l.p :8080/api
A mosphe ic
p essu e
A mosphe ic p essu e
in miliba s
Sola adia ion
Sola adia ion in
wa s pe squa e
Rela i e humidi y
Pe cen age o
humidi y
Tempe a u e
Tempe a u e in
Celsius deg ees
Wind di ec ion
Deg ees o wind
di ec ion
Wind gus
How s ong is he
wind gus in me e s
pe second
Wind speed
The wind speed in
me e s pe second
4.3. DATA REDUCTION
This chap e will explain wha was done in e ms o da a educ ion. As i was explained in P e-
p ocessing, he e a e h ee majo se o ac ions ha usually a e pe o med, om which only wo we e
used:
1) Fea u e subse selec ion: Some ea u es we e no longe conside ed due o he ac ha ei he
hey didn’ add in o ma ion ha wasn’ al eady in o he a iables, o hey didn’ ha e
comple e in o ma ion in o de o be used. The cases we e:
a. “id_expl” and “id_planeamen o” since hei in o ma ion is al eady in
“desig_come cial”
b. “es ado” because he da ase will only ha e eco ds wi h “es ado” o ac i e, so i
wouldn’ add new in o ma ion.
12
c. “ ipo_se ico_ni eis” because in he ile ha has in o ma ion om s a ions, his
column has incomple e in o ma ion, o in o he wo ds, he da a in his column is no
su icien o conclusi e abou how many elec ical bicycles o no mal ones a e in he
s a ion a each ime. The e o e, o assu e quali y o he da a, i can’ be used.
d. “bike_ id”, “geom”, “num_ e ices” a e geog aphical a iables. Since in his s udy,
he geog aphical dimension won’ be conside ed, hese a iables won’ apply.
e. “id”, since i is only a unique numbe o each ip and won’ add ele an in o ma ion.
. “dis ance”, his ea u e is also incomple e, mo e han 49% o he da ase has null
alues. Since i ’s no a good app oach o in e pola e 49% o he da a, he ea u e was
emo ed om he analysis.
2) Fea u e c ea ion
a. A a iable called “du acao_min” was c ea ed, which is a p oduc o he di e ence
be ween he da e s a and he da e end. Ins ead o 2 ea u es we now ha e 1 wi h
he same in o ma ion.
4.4. DATA TRANSFORMATION
In his chap e all he ans o ma ions in he da a will be explained. The ans o ma ions we e
made in o h ee majo ypes:
a) Bina y ans o ma ion was used in he case o he holidays and dayligh a iables. In
he holidays case, now ha a iable has alue 1 i i was holiday in Po ugal and 0 i i
wasn’ . In he dayligh case, om he sunse and sun ise da e imes, now he a iable
has also bina y alues, 1 i i was dayligh and 0 i i wasn’ .
b) Agg ega ion was used o he ime dimension. The decision o agg ega ing he ime
dimension in o bins o 20 minu es was made because o 2 easons, i s he pe iodici y
o he da a was inconsis en (1 second, 2 minu es, 5 minu es, e c.), second in e ms o
he s udy scope, he bike sha ing ebalancing p oposal won’ be made e e y second,
so he decision o 20 minu es pe iodici y was made based on he al eady men ioned
pape . (Regue & Recke , 2014)
c) New ea u es c ea ed all in o wo ypes: ime ela ed and numbe o bikes ela ed.
The ime ela ed ones a e a iables elling ( ip wise) he hou , minu e and i i was a
weekday o no . The numbe o bikes ela ed ones, a e he numbe o bicycles p esen
in he s a ion 1, 24 and 168 hou s be o e (1 hou , 1 day and 1 week, espec i ely).
13
5. BIKE STATIONS DIMENSIONALITY REDUCTION
5.1. UNSUPERVISED LEARNING VS SUPERVISED LEARNING
Supe ised lea ning and unsupe ised lea ning a e wo machine lea ning asks ha a e commonly
employed o add essing di e en kinds o p oblems and ha e some main di e ences (Jones,
Johns on, & K uge , 2019)
Table 8 - Di e ences be ween unsupe ised and supe ised lea ning (Jones, Johns on, & K uge ,
2019)
Unsupe ised lea ning
Supe ised lea ning
No labels p o ided
Labels p o ided
Finds s uc u e in unlabeled da a
Finds pa e ns in exis ing s uc u e
Uses echniques such as clus e ing
o dimensionali y educ ion
Uses echniques such as eg ession o
classi ica ion
5.1.1. Unsupe ised lea ning
Unsupe ised lea ning is used when he a ge alue o each obse a ion is unknown and he
inpu da a is he only a ailable in o ma ion. This ype o lea ning ask is commonly used o iden i ying
g oups o simila obse a ions: his p ocess is pa icula ly help ul when ying o ind he meaning in
he da a, assign he obse a ions o simila g oups o educe dimensionali y.
5.1.2. Supe ised lea ning
Supe ised lea ning is used o sol e p oblems whe e he a ge alue o each obse a ion is
known, so his in o ma ion can be used o ei he classi y (e.g. p edic ing i a pe son will has endency
o be an alcoholic o no based on hei s b ain cells ac i i y) o i a eg ession (e.g. p edic ing he p ice
o a pe sonal compu e based on how much memo y and p ocessing capaci y i has).
5.2. UNSUPERVISED LEARNING APPLIED TO TIME SERIES
As ou lined in he wo k o Reddy and Agga wal, ime-se ies segmen a ion can ha e wo main
o mula ions, which s ongly depend on he p oblem aken in o accoun (Reddy & Agga wal, 2013). I
he p oblem consis s o inding se s o ime se ies wi h simila ends, we ha e a co ela ion-based
online clus e ing p oblem. On he o he hand, i he p oblem consis s o ime se ies wi h simila
shapes, we ha e a shape-based o -line clus e ing p oblem.
Co ela ion-based online clus e ing: This o mula ion is commonly used in cases o inancial ma ke s
domain o iden i ying g oups o s ocks ha ha e simila ends o co ela ed ends.
Shape-based o -line clus e ing: Con e sely o he p e ious explained o mula ion, in he shape-based
o mula ion, he ime se ies a e e alua ed and clus e ed o -line. This o mula ion is used in he cases
in which he objec i e is o ind ime se ies wi h simila shapes. The bigges challenge and mos

14
de e mina e aspec o g ouping based on shapes is he de ini ion o how o measu e simila i y in he
shapes. Depending on he p oblem being sol ed, he e a e se e al good simila i y unc ions, such as
Euclidean unc ion o dynamic ime w apping.
Ha ing bo h o mula ion ypes o ime-se ies segmen a ion and knowing ha he goal wi h he
segmen a ion wi h his wo k is o ind g oups o ime se ies (s a ions) ha ha e simila beha io s, he
mos sui able o mula ion is he shape-based o -line clus e ing.
5.3. DISTANCE MEASURE
As explained in he wo k o Reddy and Agga wal, when he clus e ing p oblem is a imese ies
p oblem he simila i y concep and how i is measu ed is e y impo an o ha e in conside a ion. In
his sec ion we will go h ough simila i y/dis ance me ics.
As i was men ioned in Sec ion 3.2 and as s a ed by Izakian and coau ho s, “Selec ing a dis ance
unc ion o e alua e simila i ies/dissimila i ies o ime se ies has a signi ican impac on he clus e ing
algo i hms and hei inal esul s p oduced by hem” (Izakian, Ped ycz, & Jamal, 2015).
Due o his signi ican impac , some well-known and commonly used dis ance unc ions will be
explained and conside ed:
• Euclidean dis ance: Conside ing ha he da apoin s ha e n dimensions, his me ic ha akes
he di e ence o he coo dina es be ween wo da a poin s p and q, squa es i and sums i . The
dis ance be ween he wo poin s is gi en by he squa e o ha sum.
𝑑(𝑝,𝑞)= √(𝑞1−𝑝1)2+(𝑞2−𝑝2 )2 +⋯+(𝑞𝑛−𝑝𝑛)2
• Manha han dis ance: Conside ing ha he da apoin s ha e n dimensions, his me ic e u ns
sum o he absolu e di e ence among he n coo dina es o he da a poin s p and q. The
Manha han dis ance be ween wo da a p and q is o malized as ollows:
𝑑(𝑝,𝑞)= ∑|𝑝𝑖−𝑞𝑖 |
𝑛
𝑖=1
Besides he dis ance me ics jus men ioned abo e, he e is an impo an aspec o his s udy ha
will a ec he choice o he me ic, he ac ha he ype o obse a ions ha compose ou da ase
a e ime se ies.
Wo king wi h ime se ies b ings some conce ns wi h espec o hei compa ison. Fo example, wo
ime se ies can be exac ly equal bu wi h a ime shi o 2 hou s, and i he Euclidean dis ance is used,
he wo ime-se ies will appea di e en o each o he , which is no in ac ue i we conside he ime
shi o 2 hou s.
To add ess ha impo an aspec and commonly aced p oblem, dynamic ime w apping is he bes
dis ance o deal wi h ha . This measu e “de e mines an op imal ma ch be ween wo ime se ies by
s e ching o comp essing some segmen s o he se ies. As a esul , pa e ns occu ing a di e en ime
ins ances o ime se ies a e conside ed as simila ”. (Izakian, Ped ycz, & Jamal, 2015)
15
DTW acul y o add ess his p oblem has a lo o do wi h he abili y o conside ime si s by compa ing
each poin belonging o ime se ies a wi h any poin om ime se ies b. (Izakian, Ped ycz, & Jamal,
2015) DTW algo i hm pseudo code can be consul ed in Table 9.
Table 9 - Calcula ions o he DTW dis ance be ween ime se ies a and b (Izakian, Ped ycz, & Jamal,
2015)
Calcula ions o he DTW dis ance be ween ime se ies a and b
Gi en:
a = 𝑎1,𝑎2,…𝑎𝑛, he i s ime se ies wi h leng h n
b = b1,𝑏2,…𝑏𝑚, he second ime se ies wi h leng h m
Ou pu :
cos : a ma ix o size 𝑛×𝑚 con aining he cos alues cos n,m is he DTW dis ance
be ween a and b
pa h: a ma ix o size 𝑛×𝑚 con aining a wa ping pa h
DTW(a, b):
Le δbe a dis ance be ween coo dina es o sequences
cos 1,1 = δ(a1; b1);
pa h1,1 = (0,0);
o i = 2,3,…, n do
cos i,1 = cos i-1,1 + δ(ai , b1)
end
o j = 2,3,…, m do
cos 1,j = cos 1,j-1 + δ(a1 , bj)
end
o I = 2,3,…, n do
o j = 2,3,…, m do
cos i,j = min (cos i-1,j , cos i,j-1 , cos i-1,j-1 ) + δ(ai ,bj )
pa hi,j = min _index(( i – 1, j),( i , j – 1),( i -1 , j – 1));
end
end
5.4. ALGORITHMS FOR UNSUPERVISED LEARNING
In his chap e , we explo e he echniques and some pa ame e s used o sol e he bicycle s a ions
clus e ing p oblem.
5.4.1. Hie a chical Clus e ing
Hie a chical clus e ing algo i hm has wo speci ica ions: The Agglome a i e and he di isi e. Bo h
ollow di e en app oaches o achie e he clus e s o ma ion. The usage o one o he o he depends
16
on he ollowed app oach. Ei he he clus e s a e eached by a bo om-up (me ging) o by a op-down
(spli ing) app oach.
The in e es ed eade is e e ed o he wo ks o Reddy and coau ho s (Reddy & Agga wal, 2013)
and Kambe and coau ho s (Kambe , Han, & Pei, 2011) o a comp ehensi e o e iew on hese
clus e ing echniques.
Agglome a i e hie a chical clus e ing app oach: This app oach uses a bo om-up s a egy, which
means ha he algo i hm s a s by conside ing as many clus e s as obse a ions and i e a i ely me ges
he close wo clus e s (based on a simila i y /dis ance measu e). This p ocess is i e a ed un il he
algo i hm eaches one clus e con aining all he obse a ions o un il some s opping c i e ia ( ypically
he numbe o clus e s ob ained) is me .
Di isi e hie a chical clus e ing app oach: This app oach uses a op-down s a egy, which s a s by
assigning all he obse a ions o one clus e and i e a i ely di ides he clus e s in o smalle ones. This
p ocess is i e a ed un il he algo i hm eaches a numbe o clus e s equal o he numbe o
obse a ions o un il some s opping c i e ia ( ypically he numbe o clus e s ob ained) is me .
How agglome a i e hie a chical clus e ing measu es he closes wo clus e s o me ge a e
explained below:
Single linkage: The single linkage dis ance be ween clus e a and b is he minimum o all dis ances
be ween poin s o clus e a and clus e b.
Comple e linkage: The comple e linkage dis ance be ween clus e a and b is he maximum o all
dis ances be ween poin s o clus e a and clus e b.
A e age linkage: The a e age linkage dis ance be ween clus e a and b is he a e age o all dis ances
be ween poin s o clus e a and clus e b.
5.4.2. Densi y-based spa ial clus e ing o applica ions wi h noise (DBSCAN)
DBSCAN is a clus e ing algo i hm ha ies o iden i y clus e s o obse a ions using he ac ha
he in e -clus e densi y is highe han he densi y among he obse a ions ha do no belong o he
same clus e (Kambe , Han, & Pei, 2011).
DBSCAN ecei es wo pa ame e s:
1) Eps: This pa ame e speci ies he maximum dis ance be ween i sel (poin A) and i s
neighbo hood. I he dis ance be ween i sel and a poin B is smalle han eps, poin B is
conside ed o be a neighbo o poin A.
2) minP s: The minimum numbe o poin s ha cons i u e a clus e . Fo example, i minP s is wo,
means ha o a clus e o be o med needs o ha e a leas wo poin s.
DBSCAN ca ego izes obse a ions in o 3 di e en classes:
1) Co e poin s: a e he poin s ha ha e in hei neighbo hood (eps) a leas he minimum numbe
o poin s a clus e needs o ha e (minP s), i sel included.
2) No co e poin s/bo de poin s: a e he poin s ha do no comply wi h he ules o he co e
poin s. Howe e , hey include inside hei neighbo hood a leas 1 co e poin .
17
3) Noise/Ou lie : hese a e he poin s ha do no comply wi h ei he ule. In o he wo ds, hey
a e a away om any o he co e poin . The e o e, hey a e conside ed ou lie s o noise.
In he ollowing sequence o s eps is explained how he algo i hm pe o ms in o de o iden i y he
clus e s:
1. The pa ame e s a e de e mined (eps and minP s)
2. A andom poin A is selec ed
a. The neighbo hood o poin A is calcula ed using eps.
b. I he e a e a leas minP s numbe o poin s in i s neighbo hood, poin A is ca ego ized
as a co e poin and a clus e is o med wi h poin A and i s neighbo s. I no , poin A is
ca ego ized as noise.
Table 10 - DBSCAN algo i hm (Chauhan, 2020)
DBSCAN (D, Eps, MinP s)
//All objec s in D a e un isi ed
Begin
Fo all objec s in D, selec A:
I A is un isi ed:
Neigh = Calcula e A’s neighbo hood
N = numbe o poin s in Neigh
I N +1 >= eps:
Classi y A as co e poin
Conside all o his poin s o be pa o he same clus e
Else:
Classi y A as noise
END
5.5. MEASURING CLUSTER QUALITY
The e comes a poin in which se e al models mus be compa ed so ha he bes model o he
p oblem unde exam is selec ed. To selec he bes pe o me among he exis ing models, i is
necessa y o measu e hei quali y and, subsequen ly, o compa e hem.
The e a e se e al me hods o assess clus e ing quali y, ha all in wo ca ego ies:
1) Ex insic me hods: To use his me hod, he ac ual label o each obse a ion mus be
a ailable. The ex insic me hods compa e he labels a ibu ed by he clus e ing model
wi h he ac ual labels and measu e how accu a e he classi ica ion was.
2) In insic me hods: The e is no he need o ha e he ac ual label o each obse a ion o
use in insic me hods. This ca ego y o me hods measu es how well he clus e s a e
sepa a ed.
In he p oblem conside ed in his wo k, he ac ual label o each obse a ion is no known. Thus,
only he in insic me hods we e used o add ess his p oblem.
24