PervasiveandMobileComputing19(2015)7185 [622622]

PervasiveandMobileComputing19(2015)71–85
Contents lists available at ScienceDirect
PervasiveandMobileComputing
journal homepage: www.elsevier.com/locate/pmc
DisorientationdetectionbyminingGPStrajectoriesfor
cognitively-impairedelders
QiangLina,∗,DaqingZhanga,b,KayConnellyc,HongboNia,ZhiwenYua,
XingsheZhoua
aShaanxiKeyLabofEmbeddedSystemTechnology,SchoolofComputerScience,NorthwesternPolytechnicalUniversity,China
bInstitutMines-Télécom/TélécomSudPais,France
cSchoolofInformaticsandComputing,IndianaUniversity,USA
a r t i c l e i n f o
Articlehistory:
Received7August2013
Receivedinrevisedform13November
2013
Accepted17January2014
Availableonline24January2014
Keywords:
Elderlycare
Dementia
Disorientationdetection
GPStrajectoriesa b s t r a c t
Theagingpopulationisamajorconcernofhumansocietyinthe21stcentury.Elderswho
sufferphysicalorcognitiveimpairmentsoftenhavedifficultiesinnavigationaltasksand
rememberinglandmarks.Assuch,disorientation(i.e.,gettinglost)becomescommonfor
peoplewithdementiainunfamiliaroreveninfamiliarenvironments.Inordertoprovide
appropriatereal-timeassistiveservicestotheseelders,suchasremindersandalerts,we
proposeadisorientationdetectionmethodthatdetectsoutliersinone’sGPStrajectories.
Inparticular,wefirstmodelanindividual’smovementtrajectoriesasagraphbasedonher
historicalGPStraces.Wethenidentifyoutlyingtrajectoriesthathaveadefinedwandering
ordeviatingpatternaspotentialinstancesofdisorientation.Wedevelopamethodcalled
iBDDthatisabletodetecttwocategoriesofoutlyingtrajectoriesinauniformframework
inreal-time.Usingtenindividuals’real-worldGPSdatasets,wedemonstratethatiBDDcan
achieve95%detectionrateofdisorientationwithlessthan3%offalsepositives,basedon
properlychosenparameters.
©2014ElsevierB.V.Allrightsreserved.
1. Introduction
Withtherapidlyagingpopulationinmostcountries,theproportionofelders(i.e.,peopleaged65andabove)inthe
worldwillsignificantlyincreaseinthenextfewdecades[1].Aspeoplegrowolder,aconsiderablenumberofelderswould
experiencephysicalandcognitiveimpairments.Dementiahasbeenidentifiedasaprogressive,disabling,andchronic
disease,affecting5%ofeldersagedabove65andaround40%ofeldersagedover90[2].Generally,anelderwithdementia
performsherdailyroutinespoorly,andoftencannotconductinstrumentalactivitiesofdailyliving[3],suchaspreparing
mealsordoinghousework.
Oneofthemostchallengingproblemsfacedbyelderswithdementiaisnavigatingorrememberinglandmarks,making
itaprimarydifficultywhendoingdailyoutdooractivities[4],suchasvisitingdoctorsandgoingshopping.Disorientation,
orgettinglost,occursfrequentlyinunfamiliarlocationsforpeoplewithmilddementia;forthosewithmoderatecognitive
impairment,itmayevenhappeninfamiliarenvironments[5].AsreportedbyMcShaneetal.[6]intheirlongitudinalstudyon
∗Correspondenceto:Room503A,BuildingSchoolofComputerScience,ChanganCampusofNorthwesternPolytechnicalUni.,Xi’anShaanxi710129,
PRChina.Tel.:+[anonimizat];fax:+862988431531.
E-mailaddresses: [anonimizat](Q.Lin),[anonimizat](D.Zhang),[anonimizat](K.Connelly),
[anonimizat](H.Ni),[anonimizat](Z.Yu),[anonimizat](X.Zhou).
1574-1192/$–seefrontmatter ©2014ElsevierB.V.Allrightsreserved.
http://dx.doi.org/10.1016/j.pmcj.2014.01.003

72 Q.Linetal./PervasiveandMobileComputing19(2015)71–85
104participantsover5years,‘‘gettinglost’’hasaprevalencerateof24%inthefirstyearoftheonsetofdementia.Asaresult,
safetyhasbecomethecriticalconcernforcognitivelyimpairedelders,particularlywhentheyconductroutineactivitiesin
outdoorenvironments.Frequentcasesofmissingeldershaveindicatedthatthetraditionalsolutionstothedisorientation
problem,suchaswearinganidentitycard[7],donotworkverywell.
Continuouslytrackingelders’activitiesanddeliveringpersonalizedservices(e.g.,promptingorcallingforhelpunder
anemergencycircumstance)usingpervasivetechnologiesprovidesapromisingsolutiontomanyelderlycareproblems.
Personalizedservicesareabletoimprovetheautonomyandindependenceofelders,whilereducingthepotentialrisksand
carers’workload.Someworkinthisareahasbeenreportedintheliterature,includingpreventingeldersfromwalkingout
ofa‘‘security’’areabypositioningRF-baseddetectorsonexits[8]orlettingelderscarryabody-attachedsensorsuchasGPS
(GlobalPositionSystem)equippedartifact[9].Anotherlineofresearchistoprovideoutdoornavigationsupportforelders
whendeviatingfrompre-definedroutesbyusingalocationsensingdevice(e.g.,GPSequippedcellphones)combinedwith
GIS(geographicinformationsystem)[10,11].
Whilelimitingthefreedomofmovementtopreventeldersfrombeinglostisimpracticalinreallifeforthosewithmild
dementiawhostillcareforthemselvesmostofthetime,thesolutionsin[10,11]canonlydetectpartofelders’disorientation
behaviors.Inthiswork,weproposeamethodthatisabletofindpotentialdisorientationbehaviorsbymonitoringan
individual’smovementtrajectory.Thisdetectionmethodensuresthatthedisorientationbehaviors(i.e.,gettinglost)can
bedetectedinrealtime,assumingthateldersareequippedwithGPSenabledmobilephones.Ourworkisbasedonthe
followingobservations.
•Despitedifferences,humansfollowsimplepatternsintheirdailyroutines[12].Thisisparticularlytrueforelderlypeople
withdementiabecausemostofthemmaintainasimplelifestyle.Thisfactmakesitpossibletoextracthiddenspatio-
temporalpatternsfromtherecordingsofdailyroutinesandmodelone’smobilitypattern.
•Thewidecoverageofinfrastructure(e.g.,GPSsatellites)andhighpenetrationofpersonalmobilecomputingplatforms
(e.g.,cellphonesorPDAs)makeitpossibletocollecthumanmovementinformationinrealtime.Thus,appropriateand
timelyalertingservicescanbeprovidedwheneldersaredisorientated.
Ashumanmobilityishighlyrandomanddifferentpeoplehavedifferenthabitswithrespecttotheplacestheyvisitand
theroutestheytake,itisaverychallengingtasktocharacterizepeople’smobilitybehaviorswithoneunifiedandrigorous
model.Thesecondchallengeistocharacterizethecommonfeaturesofdisorientation,examiningthehugedifferenceamong
individual’snormalanddisorientationbehaviors.Thethirdchallengeistodevelopasimplebuteffectivealgorithmwhich
isabletotellthedisorientedtrajectoryfromthenormalonesinreal-time,sothattimelyalertingservicescanbeprovided
toelders.
Toaddresstheabovechallenges,inthispaperweprojecteachelder’shistoricalmovementtrajectoriesontogridcells
inadigitalmap,andmodeleachelder’sregularmovementasagraphwhereverticesrepresentfrequentedplacesand
edgescorrespondtotheroutesbetweenplaces.Inthisway,eachindividual’smovementtrajectorycanberepresentedasa
sequenceoftraversedcellsymbolsanddisorientationdetectionbecomesaproblemofcomparingtheon-goingmovement
trajectoryagainsteachuser’sregularmovementgraph.Second,weanalyzevarioususerdisorientationbehaviorsand
discoverthatallelders’disorientationtrajectoriescontainoutlyingrouteseitherdeviatingfromthemodel,orlooping
insidethegraph,oracombinationofthetwo.Finally,weproposeaneffectivedisorientationdetectionmethodbasedon
theisolation-basedmechanism[13]torecognizetheon-goingoutlyingroutescorrespondingtodisorientationbehaviors.
Specifically,ourmethodevaluatesanon-goingtesttrajectorythroughminingandmonitoringitssupportdegreeinthe
existinghistoricaltrajectorydataset.Thosetrajectorieswithlowsupportdegreeareregardedasoutliers,i.e.,atrajectory
correspondingtoadisorientationbehavior.Insummary,themaincontributionsofthisworkinclude:
First,weproposetomodeltheregularmovementpatternofeachelderasagraphandcharacterizethefeaturesof
disorientationbehaviorsascontainingoutlyingrouteseitherdeviatingfromthemodel,orloopinginsidethegraph,ora
combinationofthetwo;
Second,weconvertthedisorientationdetectionproblemintocomparingtheon-goingmovementtrajectoryagainstthe
regularmovementgraph;
Third,weproposeanisolation-baseddetectionmethod,whichidentifiesdisorientationbyminingandmonitoringits
supportdegreeintheexistinghistoricaltrajectorydataset;and
Lastly,weusetenindividuals’real-worldGPSdatasettoevaluatetheproposedmethod.Theexperimentalresults
demonstratethatourmethodperformswellintermsofaccuracy(i.e.,thedetectionrateandfalsepositiverate),aswell
astimecomplexity.
Therestofthispaperisorganizedasfollows.InSection2,wepresentourmodeltocharacterizeindividual’smovement
behaviorsandourdefinitionofdisorientationbehavior,withwhichthedisorientationdetectionproblemisformalized.
Section3providesanoverviewofourproposeddetectionmethodanddescribeshowweconvertanoriginalGPStrajectory
intoasequenceofcellsymbols.Section4presentstheproposedisolation-baseddisorientationdetectionapproachindetail.
Section5reportstheevaluationresultsforourproposedmethod.Section6brieflysummarizestherelatedwork.Finally,
Section7concludesthisworkandpointsoutseveralpotentialresearchdirections.

Q.Linetal./PervasiveandMobileComputing19(2015)71–85 73
Fig. 1.Agraphmodelofindividualoutdoortrips. H:home,C:communitycenter, S:departmentstore, G:grocery,M:medicalclinic,and D:daughter’s
home.
2. Disorientation detection problem formulation
2.1. Modelinghumanmobilityasagraph
Asmentionedabove,theelderlyoftenpursueasimplelifestyleintheirdailylifebyvisitingrelativelyfixedplaceswhere
theyperformdailyactivities.Assuch,weareabletoconstructagraphtorepresentanindividual’smovementbehaviors
accordingtoEq.(1).
TG=(V,E)
V= {P1,P2, . . . ,Pn}
E= {(Pi;Pj),1≤i̸=j≤n}.(1)
InEq.(1),eachelder’shistoricaltrajectorygraph TGrepresentshis/hermovementmodel,wherethevertexset Vdenotes
physicalplacesfrequentedbytheelder,andtheedgeset Eindicatespathsbetweenvertices.Specifically,thephysicalplace
Pi∈V(1≤i≤n)referstoalocationanelderfrequentsinhis/herdailyroutine,includingplaceslikeher home,herfavorite
restaurant,etc.;theedge (Pi;Pj)∈Edenotesthetraversedpathfromoneoftheplacesin Vtoanother.Becausetheuser
movementmodel TGiscreatedbyextractingallthefrequentedplacesandtraversedpaths,theverticesandedgesincluded
inTGreflectthemovementtracesofone’shistoricaltrips.Eachelderhasadifferentmovementmodelands/hevisitsthe
placesandroutesatdifferentfrequency.Inordertodistinguishverticesfromotherplaces,wecallthosein Vsemanticplaces
inthispaper.
AssumeHistheelder’shome(asshowninFig.1),onaregularbasis,shevisitsthe communitycenter (C)forsocial
engagement,the grocerystore(G)forfood,thedepartmentstore (S)forshopping.Sometimes,shegoestothe medicalclinic
(M)forahealthcheck,and daughter’shome (D)foragathering.Inthiscase,weobtainaninstance {H,C,S,D,G,M}for
setVand{(H;C), (H;G), (H;S), (H;M) . . . , (S;D)}forsetE.Afulltripisthereforeanorderedsequenceofpathsin E,
formingaclosedloopthatstartsatandfinishesintheelder’sownhome H.Consequently,forexample,atripto Mcanbe
either {(H;M), (M;H)}or{(H;M), (M;G), (G;H)},itiscompletelydependentonthelifestyleasexhibitedbyone’smobility
history.Allthenormaltripsarethosewhichfollowfrequentlyoneofthehistoricaltrips.
Forelders’movementbehaviors,weneedtoexploreallpotentialoutliersthatmayrelatetodisorientationbehavior
directly.Firstly,atriptoanewplaceobviouslydidnotmatchthedefinedmodel,suchasthetrip t1(fromHtod1)inFig.1,
becaused1andpartoft1arenotcontainedinmodel TG.Therefore,tripslike t1areoutlying(i.e.,fewanddifferent)as
comparedtohistoricaltrips.Thishappensbecauseofeitherincorrectpathsortravelingtoanewlyvisitedplace.Theformer
islikelytocorrespondtoadisorientationbehavior,whilethelattershouldbeconsideredcloselybytheend-userapplication
sincecognitively-impairedeldersarepronetoexperienceadverseevents,especiallyinunfamiliarsettings.Forthisreason,
therareeventoftravelingtoanewplaceisflaggedasanoutlier.
Asecondpotentialoutlierisatripinwhichtheelderfrequentlyreversesdirectionwithincertainroutes,suchas t3
onpath (M;D)ort2aroundS.Thistypeofbehaviorcouldmeanthattheelderfeelsconfusedaboutwheretogo,soshe
changesdirectioninaroutefrequently.Itisreasonabletoclassifytripslike t2andt3intooutlyingclustersforanelderwith
dementiaifthesetripsneverappearinhermobilityhistory.However,sincedirectionchangealsooccursaftervisitinga
specificlocation,ouralgorithmexcludeschangesat semanticplaces.Additionally,sinceitiscommonforsomeonetochange
directionwhentheyrealizetheyhaveforgottensomething,wetestifthenumberofdirectionchangeislargerthanacertain
thresholdbeforeitisconsideredasanoutlier.Forexample,whilethefirsttwochangesintrip t3maycorrespondtothefact
thattheelderchangeshermindorforgetssomething,thethirdchangeislikelytomeanthattheelderhaslostherway.Ifthe
directionchangesoccurexactlyinthesameplaces,thefourthchangeratherthanthethirdchangeisconsideredasthesign
ofdisorientation.Itisnoteworthythatthephysicaldistancebetweentwochangesshouldbelargeenoughtodistinguish
disorientationfrompacingbehavior[14].

74 Q.Linetal./PervasiveandMobileComputing19(2015)71–85
Afinalpotentialoutlieristhesituationinwhichaneldertakesseveralpathsthatwouldbeconsiderednormal
ontheirown,butperformedinadifferentorderascomparedtohistoricaltrips.Forinstance,foratrip Icontaining
{(H;G), (G;D), (D;M), (M;G), (G;D), (D;M)},althoughanyseparatepathinthistripisnormalaccordingtothedefined
model,itisstillanoutlierduetotheincorrectorderinwhichtheyappeared.Thiscanhappenwhenanelderbecomes
confusedaboutwhattheyareouttoaccomplish,soshekeepsvisitingfamiliarplaces,butwithnocleargoals.Tripsfalling
intothiscategorycontainneithernewplacesnornewdirectionchangesasmentionedinthefirsttwocases.
Tosumup,anelder’sdisorientation-relatedtripsarecharacterizedbyspatialdeviation(e.g.,strangeplaces),repetitive
changesofmovingdirection(e.g.gettinglostbetweentwoplaces),aswellasincorrectorderofplacesvisited(e.g.forgetting
thepurposeoftheirouting).Thepathsinthesethreecategoriesareallcorrespondingtonewtravelingroutesascompared
tothehistoricaltrips.
2.2. Disorientationbehavior
Disorientationhasdifferentdefinitionsindifferentapplicationfields.Asanexample,theAmericanHeritageR⃝Medical
Dictionarydefinesdisorientationas‘‘ lossofone’ssenseofthedirection,position,orrelationshipwithone’ssurroundings ’’.In
thiswork,weareinterestedindetectingdisorientationinelders’dailytrips.Beforegivingaformaldefinitionforelder’s
disorientationbehavior,weclassifytheusermovementbehaviorsintothefollowingthreecategories:
•Regular:Movingfromonesemanticplacetoanotherfollowingoneofthefrequenthistoricaltracesorpaths.
•Deviating:Movingtoplacealongaroutethathasneverbeenvisitedbeforeascomparedtohistoricaltraces.
•Wandering:Travelingtosemanticplacesoralongoldrouteswithadifferentsequenceinsidehistoricaltraces.
Intheabovethreepatterns,theregularpatternreferstothenormalmovementbehavior,whiletheremainingtwo
patternsareviewedasdisorientationbehaviorinthispaper.Specifically,atripwithadeviatingpatterncorrespondsto
eitherexploringanewplacepurposelyormovingtoanincorrectplacewithunfamiliarroutes.Forthewanderingbehavior,
itincludesthreedifferentmovementpatterns:(1)Atripcontainsdirectionchangesinsideapathbetweentwosemantic
places(seet3inFig.1),wherethedirectionchangeneverhappensinthehistoricaltraces;(2)Atripcontainsdirection
changesaroundasemanticplace(see t2inFig.1),wherethedirectionchangeneverhappensinthehistoricaltraces;and
(3)Atripcontainsatleastoneoldpathandtwosemanticplacesbutthetripneveroccursinthehistoricaltraces(suchas
I= {(H;G), (G;D), (D;M), (M;G), (G;D), (D;M)}inFig.1).
Basedonthesetwotypesofdisorientationpatterns(i.e.,deviatingandwandering),wenowformalizethedefinitionof
disorientationforcognitively-impairedeldersasfollows:
Definition 1(Disorientation).Referstotheoutlyingmovementbehaviorsforelderswithdementiainoutdoorenvironments,
whichfolloweitherthewanderingpattern,thedeviatingpattern,orboth,asdefinedabove.
Assuch,tript1,t2,andt3inFig.1arethereforedisorientationtripswith t1followingadeviatingpattern, t2,t3andI
followingawanderingpattern.
2.3. Problemstatement
Inthispaper,theproblemofdisorientationdetectionisdefinedasfollows:
Problem.Supposewehaveanelder’shistoricalmovementtrajectoryset T= {t1,t2, . . . ,tn},wherenisthetotalnumber
oftrajectoriesstoredinthetrajectoryset.Givenoneelder’son-goingtriptrajectory t,theobjectiveistoinforminreal-time
whethertisadisorientationtrajectorythatfollowsthedeviatingorwanderingpatternasdefinedabove.
3. iBDD: isolation-based disorientation detection method
Inthissection,firstwepresentanoverviewofourproposeddisorientationdetectionmethod,wethenprovidesome
definitionswhichallowustodescribethetransformationprocessfromanoriginalGPStrajectoryintoasymbolizedsequence
oftraversedsymbols.
3.1. Overview
AsshowninFig.2,theproposediBDD(Isolation-BasedDisorientationDetection)methoddetectingadisorientation
trajectorycomprisesoftwomainsteps.Inthefirststep,wesplitthecitymapofinterestintogrid-cellsofequalsizeto
formacellmatrixnamed CellMatrix.WeusetheobtainedcellmatrixtotransformallGPStrajectorieswithinagivenset
ofhistoricaltrajectories, T,intosequencesoftraversedcellsviaa symbolizationprocess.Finally,weinstantiatethegraph
modelTGwithtransformedtrajectoriesin Ttogenerateanewvalidtrajectoryset TG.Inthesecondstep,wepresentour
iBDDdetectionmethodtoexaminewhetheranon-goingtrajectory tisadisorientationtrajectory.Specifically,weexploit

Q.Linetal./PervasiveandMobileComputing19(2015)71–85 75
Fig. 2.OverviewoftheproposediBDDmethod.
the‘‘fewanddifferent’’propertiesofdisorientationtrajectories,andapplytheisolationmechanismtodetectdisorientation
trajectories.
Algorithm 1:theiBDDmethod
Inputs:t= ⟨p1,p2, . . . ,pn⟩—aGPStrajectory
CellMatrix—acitymapmatrix
TG—asetofsymbolizedtrajectories
Outputs:label=1fordisorientation,0fornormal(default)
Process:
1:initializeTwithTG//Tisaworkingset
2:fori=1tondo
3: (new,c)←symbolization (pi,CellMatrix )
4: ifnew==1then
5: (l,os,T′)←detection (c,T)
6:T←T′
7: end if
8:end for
9:label←l
Algorithm1summarizestheprocessoftheiBDDmethodindetectingifanon-goingtrajectory tshouldbeclassifiedas
disorientation.TheGPSpoints(e.g., pi)ofthetesttrajectory tareinputtedonebyone,andeachofthemisfirsttransformed
intoacellsymbolbycallingthe symbolizationprocedure(whichwillbeintroducedinthenextsubsection),thenfora
validcell,thedetectionprocedure(whichwillbeintroducedinSection4)determinesiftheon-goingsub-trajectory tis
adisorientationtrajectorysofar.Ifitisadisorientationtrajectory,thealgorithmoutputsavalueof label=1.
3.2. GPStrajectorypreprocessing
Asmentionedabove,weuseGPStrajectoriestorepresentanelder’soutdoortrips,andthedetectionprocedureworks
onsymbolizedtrajectories.Here,therefore,wefirstdefineaGPStrajectoryandasymbolizedtrajectorybeforedescribinga
detailedtransformationprocess.

76 Q.Linetal./PervasiveandMobileComputing19(2015)71–85
Definition 2(Elders’MobilityGPSTrajectory ).AGPStrajectory, t,isasequenceofpoints ⟨p1,p2, . . . ,pn⟩,wherepi=(xi,yi)
istheithphysicalpositionintheformof(longitude,latitude).Foragiven1 ≤i<j≤n,ti:j= ⟨pi, . . . ,pj⟩iscalleda
sub-trajectoryof t.
AsGPSpointsarecollectedatahighsamplingrate,manypointsoftenfallintoarelativelysmallphysicalarea,causing
highcomputationcostanddifficultywhencomparingtwotrajectories.Asymbolizedtrajectoryisdesirabletorepresent
differentinstancesofthesamerouteconsistently.
Definition 3(SymbolizedMobilityTrajectory ).Asymbolizedtrajectory, t,isasequenceofsymbols ⟨c1,c2, . . . ,cm⟩obtained
fromt,whereck(1≤k≤m≪n)denotesthek-thphysicalareathat ttraversed.
Thephysicalarea ckisgeneratedbydecomposingacitymapofinterestintoaseriesofequal-sizedcellsaccordingtoa
givensize(e.g.,150m ×150m).Givenatrajectorydatasetofanelder,weareabletodetermineavalidrangeoftherelevant
citymapaccordingtothemaximum(minimum)longitudeandlatitudevalue,andthendecomposethisareaintoaseriesof
cellsofthesamesize( d×d).Finally,wenameeachcellandrecorditintoamatrixof CellMatrixasfollows:
CellMatrix =
c11· · ·c1n
………
cm1· · ·cmn
.
Fig.3showstworealGPStrajectoriesandthesymbolizedsequences(graycells),wheretheGPSpointsfallingintothe
samecellsarereplacedbythetraversedcellfromthe CellMatrix.AsdepictedinFig.3,twotrajectoriestraversingthesame
pathmaylookverydifferentifnotrajectorypre-processingisdone.Thereasonsforthisarethreefold.First,GPStrajectories
usuallyhaveahighsamplingrate(e.g.,about1–5sor5–10mperpointinourdatasets).Thehighsamplingrateresultsin
morethanoneGPSpointbeingrecordedwhenapersontraversesacell.Anelderwalkingthesamepathatdifferentspeeds
willthusproduceadifferentsymbolizedsequenceofcells.Secondly,GPSsignalsaresusceptibletosurroundingconditions,
suchasbadweatherandtallbuildings,whichcancreatenoisydatasuchasapointthatwillregisterasoriginatingfrom
aneighboringcell.Finally,itisnotunusualtohaveapaththattraversestheborderbetweentwocells,asshownbythe
‘‘criticalpoints’’inFig.3.Thiscancausetwotrajectoriestoberepresentedastraversingdifferentsequencesofcells.
Wehandletheseissuesbyadoptingthefollowingtrajectorysymbolizationprocess,which,inreal-time,transformsan
originalsequenceofGPSpointsintoasequenceoftraversedcells,takingintoaccounttheabovethreefactors.
GPStrajectorysymbolization :SymbolizingatrajectorymeansfirstmappingeachGPSpointintothematchingcellby
searchingtheCellMatrix,thenfilteringrepetitiveandinvalidcells.Thiswillresultinasymbolizedsequenceoftraversedcells
fortheoriginalGPSpointsequence.Thealgorithmspecificallylooksfor(andremoves)invalidcells—thosecorresponding
tonoisyGPSdataandcriticalpoints.
InordertotransformtheGPStrajectoryinreal-time,wetakeapre-examinationandpost-evaluationcombinedapproach,
integratingdistanceanddistributiondensityintothealgorithm(seeAlgorithm2).
Algorithm 2:symbolization(p′,CellMatrix′)
Process:
1:t←t∨p′//t= ⟨p1,p2, . . . ,pi⟩
2:si←Map(pi)//accordingtoEq.(2)
3:s←s∨si//s= ⟨s1,s2, . . . ,si⟩
4:ifsiissamewithsi−1then
5:n←n+1//countingsamecell
6:nP←nP∨pi
7:else
8:c←c∨sj//cisusedtorecordvalidcells
9: ifdist(nP)≤d/3&n≤d/5rordist (pi,pi−1)≥2rthen
10:new′←0
11: ifc(end)==c(end–2 )then
12: c←c(1:end–1 )
13: end if
14:nP← { }
15: else
16:new′←1
17: end if
18: end if
19: return(new′,c(end–1 ))

Q.Linetal./PervasiveandMobileComputing19(2015)71–85 77
Fig. 3.AnillustrationofGPStrajectoriesandthesymbolizedsequences.
Fig. 4.AnillustrationofGPStrajectorysymbolizationprocess.
ThealgorithmstartsbycomparingthecurrentGPSpointtothepreviouspoint.IfthecurrentGPSpointliesinthesame
cellaspreviousone,thenarepetitivecellsituationisidentifiedandthecellisignored(line4–6inAlgorithm2).Whenthe
on-goingtrajectoryentersanewcell,thedistancebetweenthecurrentpointandthepreviouspointisexaminedtoestimate
whetheritisa‘‘noisy’’point.ThisisbecauseGPSnoisesignalsoftenleadtosignificantdistancedeviation.Ifapointistoo
farfromthepreviouspoint,itcanbeconsiderednoiseanddiscarded.Second,aftertheon-goingtrajectoryleavesacell,
thetraverseddistanceandthenumberofpointswithinthatcellareusedtorecognize‘‘ criticalpoints’’(i.e.thosethatoccur
becausethepathisalongtheborderoftwocells).Suchcriticalpointsusuallyhaveashorttraverseddistanceandasmall
numberofpoints.Thus,asaresult,thepointfallinginto c4′isrecognizedasanoisypointwhiletheonesin c6′arecritical
points(asshowninFig.4).
Thesuitabledistanceandproperdensitythatanormalcellhasaredeterminedempiricallyaccordingtothesizeofthe
cellandthesamplingrateofGPSdata.Supposethatthesizeofacellis d,thesamplingrateis r,adistancebetweentwo
adjacentpointsofmorethan rstronglysuggeststhatthelatterisanoisypoint.Atthesametime,averyshortdistance
traversedbyasmallnumberofpointsmayimplyacriticalcategoryforthesepoints.Again,inFig.4,thedistancebetween
thepointinc4′anditspredecessorissignificantlylarge,andthepointstraversedwithin c6′areverysmallwithonly
twopointsinit.Welabelcellsresultingfromnoisyandcriticalpointsinvalidandremovethemfromthesymbolized
trajectory.
Map(p)=
cklif|x−xkl| ≤d/2and |y−ykl| ≤d/2
ckl=(xkl,ykl)∈CellMatrix
. (2)
Algorithm2summarizesthedetailedsymbolizationprocessforanincomingGPSpoint p′(assumeitisthe ithpointpi).
Firstly,thealgorithmconcatenatesthepredecessorswith pitoformanewon-goingtrajectory t= ⟨p1,p2, . . . ,pi⟩,and
mapspiintothematchingcell sibyusingamappingfunctionasdefinedinEq.(2).Ifitliesinthesamecellasitspredecessor,
thealgorithmcountsandrecords piintonP(line5and6).Otherwise,themappedcell siisconcatenatedwith c(recording
non-repetitivecells),andthealgorithmexamineswhethertheprecedingcellisaninvalidcell(line9).Aninvalidcellusually
leadstocellrepetitionatitsleftandrightneighborsasmentionedabove,soitneedsfurtherprocessing(line11–13).Fora
normalcell,variable new′willbesetas1(thedefaultvalueis0).Finally,thealgorithmreturns new′andc(end–1 )tothe
iBDDalgorithm,with new′=1denotingavalidcellof c(end–1 )(line4inAlgorithm1).Specifically,dist (nP)meansthe
traverseddistancebyallthepointsin nP,whichrecordsallpointsfallingintoacell;dist (pi,pi−1)isthedistancebetween
pointpiandpi−1.
NotethatthesymbolizationalgorithmdescribedinAlgorithm2actsasasub-procedurecalledbytheiBDDalgorithmfor
onlinedetectionofdisorientationtrajectories.Forachievingasymbolizedhistoricaltrajectoryset, T,weonlyneedtorecord
thesequenceofcells(symbols)in cforeveryGPStrajectorybysimplyadjustingtheoutputofAlgorithm2.
Thelaststageindatapre-processingistoinstantiatethedefinedgraphmodel TGwiththesymbolizedtrajectoriesin
Ttoobtainanewset TG.Wefirstlabelallsemanticcellsthatrelatetotheidentifiedsemanticplaces.Thenweindexall

78 Q.Linetal./PervasiveandMobileComputing19(2015)71–85
trajectoriesinTbycountingnotonlythetrajectoriesthatcontainexactlythehomecellastheirsourceanddestination,but
alsotheonesthattraverseanyothertwosemanticcells.Thisisbecauseinarealsituation,noteveryGPStrajectory(hence
thetransformedone)exactlystartsatandendsinthehomecell.
4. Disorientation trajectory detection algorithm
Thissectionintroducesthedisorientationdetectionprocessindetail.Inordertotestifanon-goingsub-trajectory
isdisorientation,weexploititssupportdegreeinhistoricaltrajectoriescombinedwiththedefinedoutlyingpatterns.
Therefore,thissectionbeginswithsomerelateddefinitions,andthenpresentsthedetectionalgorithm.
4.1. Preliminariesanddefinitions
Definition 4(Support,SupportSet,andSupportDegree ).Fortwogiventrajectories ti̸=tj∈T,wesaytisupportstj(ortjis
supportedbyti)ifandonlyiftjisasub-trajectoryof ti.Thesetconsistingofallsymbolizedtrajectoriesinset Tthatsupport
tjiscalledsupportsetof tj:
Ttj
supp= {ti|ti∈T∧tisupportstj} (3)
andtheproportionof Ttj
suppinTiscalledsupportdegreeof tj:
supp(tj,T)= |Ttj
supp| ×1
|T|. (4)
Forexample,assume T= {t1,t2,t3}isasetconsistingofthreetrajectories t1= ⟨c1,c2,c3,c4⟩,t2= ⟨c1,c2,c3,c4,c5⟩,
andt3= ⟨c2,c3,c4,c5⟩.Giventwotesttrajectories t′= ⟨c1,c2,c3⟩andt′′= ⟨c2,c3,c4⟩.AccordingtoDefinition4, t′has
asupportsetof {t1,t2}andsupportdegreeof2 /3(≈66.67%),becausetherearetwotrajectories t1andt2inTthatsupport
t′(i.e.,t′isasub-trajectoryofboth t1andt2).Similarly,thesupportsetandsupportdegreefor t′′are{t1,t2,t3}and3/3
(100%),respectively.
Asdemonstratedbytheaboveexample,foragiventrajectoryset T,differenttesttrajectoriesoftenobtaindifferent
supportsets,hencehavedifferentsupportdegrees.Inpractice,itisveryraretoobtainasupportdegreeof100%forany
giventrajectory.Becauseinreallife,theset Tconsistsoftripstodifferentsemanticplaces,hencedifferenttraversedpaths
fromoneplacetoanother.Consequently,weneedtodefinea θ-supporttrajectoryasfollows.
Definition 5(θ-Support).Foragivenconstant0 ≤θ≤1,atrajectorytjiscalled θ-supportwithrespectto Tifitssupport
degreesupp (tj,T)≥θ.
Aθ-supporttrajectoryisregardedasanormaltrajectorywithrespecttothegivenconstantthreshold θ.Again,if θisset
as0.5,t′andt′′areallnormaltrajectoriesintermsof Tasshownintheaboveexample.However,only t′′isnormalifwe
assign0.8to θ.Ifatrajectorytjhassupportdegreesupp (tj,T)≥θ,thenthereareatleast θ%trajectoriesin Tthatsupport
tj;otherwise,tjisconsideredas‘‘ fewanddifferent’’.
Itisobviousthatthreshold θiscrucialindeterminingwhetheratrajectoryisnormalornot.Ahighervaluefor θimplies
ahighernumberofsimilartrajectoriesinaset.Inreallife,however,anelder’shistoricaltrajectoryset Tisactuallydivided
intodifferentclusters,witheachclustercomprisingoftrajectoriestodifferentsemanticplaces.Inmostcases,wecaneven
furtherpartitionaspecificclusterintoseveraldifferentsub-clustersaccordingtothetraversedpaths.Consequently,each
(sub-)clusterhasadifferentdistributiondensityoftrajectories,whichwillvaryalotfordifferentsemanticplaces.For
instance,foraspecificelder,thenumberoftrajectoriesto grocerystoremaybegreaterthanto daughter’shome.Thus,
θshouldbedetermineddependingontheelders’mobilityhistory(i.e.,recordingsofhistoricaltrips)andshouldnotbe
toolarge.
Definition 6(OutlyingPointandOutlierScore ).Anoutlyingpointisanon- θ-supportcell,wherethetrajectoryeitherdeviates
fromnormaltrajectoriesorchangesdirectionrepeatedly.Thenumberofthefoundoutlyingpointsischosentobetheoutlier
score(OS)foradisorientationtrajectory.
AccordingtoDefinition1,adisorientationtrajectorycontainsatleastthreecontinuousdeviatingorloopingpoints.
However,ifatrajectorycontainsoutlyingpoint(s),nomatterhowbigthenumberis,itisnolonger θ-supportaccording
toDefinitions4and5.Sinceitispossibleforaneldertorecoverandgetbackontrack,anappropriatestrategyisneededto
breakofftheon-goingtrajectorytoensurethatthesubsequentsub-trajectoriescanbeconsidered θ-support.Thisisdone
dependingonthetypesofoutlyingpoints:(1) deviatingpoint:breakintoasub-trajectoryaftertheoutlyingpoint;(2) looping
point:breakintoasub-trajectorybeforethepreviouspointoftheoutlyingpoint.

Q.Linetal./PervasiveandMobileComputing19(2015)71–85 79
4.2. Disorientationdetectionalgorithm
Algorithm 3:detection(c′,Tws)
Process:
1:t←t∨c′//t= ⟨c1,c2, . . . ,ci⟩
2: searchTwswithttoobtainasupportset Tt
supp
3: computesupp (t,Tws)accordingtoEq.(4)
4:ifsupp(t,Tws) < θ then//θisathresholdconstant
5: ift(end)==t(end–2 )then
6:t← ⟨t(end–1 ),t(end)⟩//breakingattheplacebefore t(end–1 )
7:Rl←Rl+1//countingloopingoutlyingpoint
8: else
9:t← ⟨ ⟩//emptyingt
10:Rd←Rd+1//countingdeviatingoutlyingpoint
11: end if
12: reset Twswiththeoriginalset TG
13: else
14:Tws←Tt
supp
15: end if
16: ifRdorRl≥3then
17:l′←1//withinitialvalueof0
18:os′←os′+1//withinitialvalueof0
19: end if
20: return (l′,os′,Tws)
Algorithm3summarizesthedetaileddetectionprocessforanongoingtrajectory t= ⟨p1,p2, . . . ,pk⟩,wherewesuppose
pkisthenewlyarrivedGPSpoint,anditismappedintoavalidcell ci.Additionally,weassumethat tisconsidereda
normaltrajectorybeforethearrivalof pk,i.e.,wehaveasymbolizedon-goingsub-trajectory t= ⟨c1,c2, . . . ,ci−1⟩,where
cl(1≤l≤i≪k)aretraversedcellsbyGPStrajectory t.
Withthenewlyarrivedcell ci,thealgorithmfirstconcatenates ⟨c1,c2, . . . ,ci−1⟩withcitoobtainanewsequence
t= ⟨c1,c2, . . . ,ci−1,ci⟩,andthencreatesasupportsetfor tbyminingalltrajectoriesinworkingset Tws.Aftercomputing
supportdegree, ciwillberecognizedasanoutlyingpointif tisnotsupportedintermsofthegiventhresholdconstant θ
(inline4–12).If ciisaloopingoutlyingpoint, twillbebrokenat ci−1(i.e.,t= ⟨t(end–1 ),t(end)⟩ = ⟨ci−1,ci⟩).Ifciisa
deviatingoutlyingpoint, twillbeemptied(i.e., t= ⟨ ⟩).RlandRdaretwovariablesusedtocountfoundoutlyingpointsof
loopinganddeviatingpatterns,respectively.Inboththesecases,workingset Twswillberesetwiththeoriginalset TGfora
non-θ-support(sub-)trajectory(like tatthepresentmoment).
However,ifciisdetectedasanormalpoint,thereisonlyanupdateoperationfor Tws:itwillberesetwiththesupport
setoft(line14).Theuseoftheworkingset Twsaimstoimprovethedetectionefficiencybylimitingthesearchonlywithin
theθ-supporttrajectoriesinthepreviousstep.So,anupdated TwsisreturnedbyAlgorithm3(line20),correspondingtothe
oneinline5(6)inAlgorithm1.
Ifthreeoutlyingpointshavebeenfound, twillberecognizedasatripwithdisorientationbehavior(line17inAlgorithm
3,andline9inAlgorithm1),andallremainingcellscontributeoutlierscore1percellaccordingtoDefinition6.
Fromtheabovedetectionprocesswecanseethatitisofteninsufficienttodetectadisorientedtrajectorybyonlymining
supportdegreeofanindividualpoint;inotherwords,weneedtoexaminethesupportdegreeoftheon-goingtrajectory
t= ⟨c1,c2, . . . ,ci−1,ci⟩insteadofthatof ci.Thisisbecausealoopingoutlyingpointitselfisstilla θ-supportcelloccurring
inthenormalpaththatistraversedbytheprecedingcells;itisanoutlierbecausethetripreversesdirectionfromtheprior
cell(i.e.,ci−1).However,toobtainasupportsetforalong(sub-)trajectorybyminingalltrajectoriesin Twsisobviouslytime-
consuming,causinglowerperformanceforthedetectionsystem.Wehandlethisissuebyusingaworkingtrajectory tws,
whichonlyrecordsthelastthreecellsofalong(sub-)trajectory.Therationalforthisisbasedonthefollowingobservation.
Observation 1.Anongoingtrajectory t= ⟨c1,c2, . . . ,ci−1,ci⟩isθ-support,ifandonlyifsub-trajectory ⟨ci−2,ci−1,ci⟩is
θ-support.Onthecontrary, ⟨ci−2,ci−1,ci⟩istheshortestnon- θ-supportsub-trajectory.
ThenecessityforObservation1isobvious,becauseanysub-trajectoryofa θ-supporttrajectoryis θ-support.So,a θ-
supporttrajectory t= ⟨c1,c2, . . . ,ci−1,ci⟩necessarilyimplies θ-support ⟨ci−2,ci−1,ci⟩.Forsufficiency,wefirstassume
thatt= ⟨c1,c2, . . . ,ci−1,ci⟩isnot θ-support.Atthistime,foranyorderedsub-trajectoryextractedfrom t,itisnot θ-
supportifandonlyifitcontains ci.Thisisbecause ⟨c1,c2, . . . ,ci−1,ci⟩isθ-support,orelseithasbeenbrokensomewhere.
Thus,thecandidatesare: ⟨ci⟩,⟨ci−1,ci⟩,⟨ci−2,ci−1,ci⟩,andsoon.Asmentionedpreviously,however,both ⟨ci⟩and⟨ci−1,ci⟩

80 Q.Linetal./PervasiveandMobileComputing19(2015)71–85
Table 1
Datasetutilizedinourexperiment.
T−1T−2T−3T−4T−5T−6T−7T−8T−9T−10
Trajectories 310 333 281 237 420 196 237 273 232 510
Outlyingtrajectories 28 30 20 21 35 17 22 22 18 29
Ratio(%) 9.03 9.00 7.18 8.86 8.33 8.67 9.28 8.06 7.76 5.69
Semanticplaces 4 3 4 4 5 2 2 2 3 3
maystillbe θ-supportiftisdetectedasaloopingtrajectory.Therefore, ⟨ci−2,ci−1,ci⟩istheonlyshortestnon- θ-support
sub-trajectory.
Consequently,foralong(sub-)trajectory,weonlyusethelastthreeelementstosearchtrajectoryset Twstoobtainits
supportset,whichisabletofurtherimprovedetectionefficiency.Assuch,theline2inAlgorithm3isthereforemodifiedas
follows:
2:iflen(t)≥3then
searchTwswith⟨t(end-2 ),t(end-1 ),t(end)⟩toobtainasupportset
else
Finally,webrieflyexplainwhyatripcontainsoneortwooutlyingpointsisstillcategorizedasanormaltrajectory:
•Foraloopingpattern,anoutlyingpointdenotesachangeofmovingdirection.Onechangemaybecausedbythefactthat
theelderchangeshermind,whiletwochangesmaycorrespondtothecasethatanelderforgotsomething(firstchange)
sosheheadedback,shecontinuedthetrip(secondchange)afterpicking-upthething.Botharequitecommoninhuman
dailylife,sotheyareconsideredasnormaltrajectories.
•Foradeviatingpattern,anoutlyingpointisonethatisnotonanormaltrajectory.Whileoneortwosuchpointsmay
simplybeasmallintendeddeviation,thelargerthenumberofoutlyingpoints,thelargerthedeviationfromnormality.
Sinceanassistivedisorientationdetectionsystemshouldberobusttonoise,smalldeviationsshouldbetolerated.Inour
symbolizedrepresentationofcellsequences,acellhasasizeof150m ×150m,allowingadeviationofupto300m
beforebeingflaggedasapossibledisorientationevent.
5. Experimental evaluation
Inthissection,weprovideanempiricalevaluationofourproposedapproachusingareal-worldGPSdatasetofindividuals.
5.1. Experimentalsetup
Intheevaluation,weuseanopendatasetwithmorethan160individuals’GPStracesreleasedbyMicrosoftResearch
Asia[15,16].Wechose10individuals’GPStracesasourtestdatasets.Sincethedatasetisnotofolderadultswithmild
dementia,itdoesnotcontainwanderingpatterns(thoughitdoescontaindeviatingtrajectories).Thus,inordertotest
theperformanceoftheiBDDmethodindetectingwanderingpatternsintrajectories,weaddedseveraltrajectorieswith
wanderingpatternsperdatasetmanually,whichhavebeensymbolizedbeforeadding.Table1givesthestatisticsofeach
individual’sGPSdataset,includingthenumberoftotaltrajectories,outlyingtrajectories(alsooutlierrate),andthesemantic
locationsineachdataset.Ineachdataset,GPStrajectorydataarecollectedatarateof2–5sor5–10mperpoint.Additionally,
intheexperiment,weassigndifferentvaluesforsizeofcellin CellMatrixwhendiscretizetheareaofinterestinto
squarecells.
Toquantitativelyevaluatetheproposedmethod,weaskedthreevolunteerstomanuallylabelallthetrajectoriesin
eachdataset.Ifthemajorityofthevolunteers(i.e.,atleasttwoofthem)thinkthatatrajectoryisoutlying(i.e.,probably
adisorientationevent),itislabeledasanoutlyingone.Thevolunteerscompriseof:onemaleelder(ages67),onefemale
teacher(ages56),andonemasterstudent(ages23)inourteam.Thevolunteersindependentlylabeledeachtrajectory
afterbeingtrainedtoidentifythetwodifferentpatternsofdisorientationbehavior.Thesemanuallylabeledoutlying
trajectoriesserveasgroundtruthintheexperiments.TheevaluationmetricweuseisAUC(AreaUnderROCCurve).In
practice,aclassifiedtrajectoryfallsintooneofthefourcategories: TruePositive(TP),whichcorrectlyidentifiesanoutlying
trajectoryasanoutlier; FalsePositive(FP),whichincorrectlyidentifiesanormaltrajectoryasanoutlier, FalseNegative(FN),
whichincorrectlyidentifiesanoutlyingtrajectoryasnormal,and TrueNegative(TN),whichcorrectlyidentifiesanormal
trajectoryasnormal.Accordingly,wedefinethedetectionrate drandthefalsepositiverate flrasdr=TP/(TP+FN)and
flr=FP/(FP+TN),respectively.
Itisdesirablethatadetectionmethodshouldhavebothahighdetectionrateandalowfalsepositiveratesimultaneously.
TheROCcurveshowsthedetectionrate( y-axis)againstthefalsealertrate( x-axis),andtheAUCvalueisdefinedasthearea
undertheROCcurve.Asastatisticalexplanation,theAUCvalueisequaltotheprobabilitythatarandomlychosenoutlying
trajectoryisrankedhigherthanarandomlychosennormalone.Thus,thecloserto1theAUCvalueis,thehigherperformance
theoutlierdetectionmethodachieves.
TheexperimentsareruninMatlabonanIntelCoreE8400PCwith2GBRAMrunningWindowsXP.

Q.Linetal./PervasiveandMobileComputing19(2015)71–85 81
Fig. 5.Anillustrationofdisorientationdetection. Hdenotescenterlocationand Pi’saresemanticplaces.(a)Alltrajectories.(b)Manuallylabeledoutlying
trajectories.(c)iBDDdetectedoutlyingtrajectory.
Fig. 6.Anexampleofthedeviatingpatterntrajectory.
5.2. Experimentalresults
TotesttheiBDDmethodinrealtime,eachtimewetakeatrajectoryfromthecurrentdataset Tasouron-goingtest
trajectoryt,thecellsoftareinputtedintothedetectionalgorithm(i.e.,Algorithm1)oneatatime.So,thesupportof tis
computedaccordingtosupp (t,T− {t}).
(1)Visualization
Withavalueof150mfor dandavalueof0.10for θ(whichmeansthatanon-goingtrajectoryorsub-trajectoryisnormal
ifitissupportedby10%ofthetrajectoriesin T− {t}),avisualizationofthedetectionresultsofthedataset T−1hasbeen
providedinFig.5,wheremanuallylabeledoutlyingtrajectoriesandtheoutlyingtrajectoriesdetectedbyiBDDaredepicted.
TheoutlyingtrajectoriesplottedinFig.5(c)arethosedetectedbytheiBDDmethodwiththehighestscore.Thenumberof
thesetrajectoriesisequaltothatofmanuallylabeledtrajectoriesinFig.5(b),buttheIDsarenotnecessarilyidentical.From
thevisualizationinFig.5,wecanseethatthedetectedresultsareverysimilartothoseofmanuallylabeledtrajectories.This
indicatesthatiBDDiseffectiveindetectingdisorientationtrips.Likewise,theiBDDmethodachievessimilarresultsusing
otherindividuals’GPSdatasets.
Inreallife,differentsemanticplaceshavedifferentdistributionsoftrajectorieswithvariousdensities.Inotherwords,
theclusterbetween HandP1hasmanymoretrajectoriesthantheonebetween HandP3(alsoP4)inFig.5.Thisis
becauseP1denotesanoftenvisitedplace,suchasagrocerystoreoracommunitycenter,whereas P3andP4arevisited
lessfrequently.Inaddition,trajectoriesusingdifferentmodesoftransportationhavesignificantlydifferentfeatures.The
trajectoriesbetween HandP1arefromwalkingwhiletheonesbetween HandP2aregeneratedbytakingabusorother
vehicle.Generallyspeaking,thewalkingtrajectoriesarenotasneatasthosefromvehicles.Inrealsituations,however,each
individualtrajectoryhasonlyasmallnumberofnoisypoints.Weclassifythesetracesintotwocategories: slightlydeviated
pointsanddeviatedpointswithdiscontinuedcells .
Fortheslightlydeviatedpoints,thedatapreprocessinghasensuredthatthecellsmappedfromthesepointswillnot
appearinthetransformedsequenceofcells,sotheyhavenoeffectsonthedetectionresults.Forthedeviatedpointswith
discontinuedcells,theprocessingmechanismfordeviatingpatternsthatiBDDtakesensuresthatthosedisconnectedcells
shouldnotbecountedtoreducethefalsepositiverate.WefurtherexplainthisinFig.6usingdataset T−3withtwooutlying
points(depictedas c2′andc3′).Afterthearrivalof c2′,thepartialtrajectory t= ⟨c1,c2,c2′⟩isnolonger θ-supportforthefirst
time.c2′isrecognizedasanoutlyingpointinthedeviatingpattern.Thus,theon-goingtrajectory tisresetto ⟨ ⟩.However,
afterthefollowingcellof c2,thet= ⟨c2⟩becomes θ-supportagain,sothecountofoutlierscorefor c2′issetto0.Inother
words,cellc2′isnotregardedasarealoutlyingpoint,similarlyfor c3′.Asaresult,thetrajectory tobtainstheoutlierscore
of0.
Fig.7showsthedetectionresultsfortwoclassesofoutlyingtrajectories(bothwanderinganddeviatingpatterns),where
theredcurvesdenotetheoutlyingpartsofallthreedepictedtrajectories.Particularly, op1,op2andop3denotethestarting
pointsoftheoutlyingtrajectoriesrespectively,sincethesearethepointswherethetrajectoriesstarttobedetectedas

82 Q.Linetal./PervasiveandMobileComputing19(2015)71–85
Fig. 7.AnillustrationofoutlyingtrajectoriesdetectedbyiBDD. op1,op2,andop3arethefirstoutlyingpointineachdisorientationtrajectory.(For
interpretationofthereferencestocolourinthisfigurelegend,thereaderisreferredtothewebversionofthisarticle.)
Table 2
TheAUCvaluesofiBDDwithdifferentvaluesofcellsize dwhen θ=0.10.
d(m)T−1T−2T−3T−4T−5T−6T−7T−8T−9T−10
80 0.8872 0.8753 0.8990 0.8999 0.8824 0.9001 0.9104 0.9200 0.9006 0.8942
120 0.9903 0.9911 0.9921 0.9933 0.9875 0.9941 0.9940 0.9954 0.9960 0.9959
150 0.9972 0.9995 0.9962 0.9968 0.9967 0.9997 0.9977 0.9974 0.9994 0.9992
180 0.9912 0.9931 0.9929 0.9927 0.9915 0.9939 0.9953 0.9955 0.9959 0.9969
220 0.9012 0.8994 0.8999 0.9100 0.8971 0.9033 0.9320 0.9297 0.9119 0.9022
disorientedtrips.Recallthatatrajectoryisnotrecognizedasanoutlierimmediatelyafteranoutlyingcellisfound.Rather,
adecisionismadeaftertwooutlyingcells(inadeviatingpattern)orthreechangesofdirection(inawanderingpattern)
havebeendetected.Thethickpartofthewanderingtrajectory(depictedwiththelightblueline)aretheloops,depictinga
changeofmovingdirectionatleastthreetimes.
(2)Quantitativeevaluationresults
WequantitativelyevaluatetheproposediBDDmethodbycalculatingitsAUCvaluesforeachchosendataset.Specifically,
weprovideseveraldifferentresultsintermsofdifferentvaluesfor d(i.e.,sizeofcell)fordecomposinganindividualcity
mapintoacellmatrix.
AscanbeseenfromtheAUCvaluesinTable2( θissetwith0.1),avaluebetween120and180mfor dobtainsalmost
thesameAUCvaluesforallchosendatasets,withadetectionrateover95%andafalsepositiverateoflessthan3%forall
datasets.However,if dissetwithavalueoflessthan100mormorethan200m,onlyarelativelysmallAUCvaluecan
beobtainedforeverychosendataset.Thereasonforthisphenomenonisthatavaluefor dthatistoosmallleadstothe
continuousGPSpointsofanormaltrajectory(e.g.,awalkingtrajectory)beingmappedintodifferentcells,hencethehigh
falsepositiverate.Atthesametime,avaluefor dthatistoolargemayresultinloop-likemovementsinacellnotbeing
detected,hencethelowdetectionrate.
AsthetargetaudienceoftheproposediBDDmethodiselderswithimpairedcognition,adisorientationtrajectory
followingadeviatingpatternneedstobedetectedinatimelymannerbeforetheelderdeviatesfortoolongfromoneof
thenormalpaths.Thus,avalueof150mfor disnotonlyalgorithmicallyfeasible,butisalsoacceptableintherealworld.In
thiscase,anelderwilltravelabout300m(i.e.,twocells)beforehis/herdisorientationbehaviorisdetected.Basedonthis
computedvaluefor d,Fig.8depictstheROCcurvesofiBDDonalldatasets.ItcanbeseenthatiBDDisabletoachieveahigh
detectionratewhilekeepingalowfalsepositiverate.Inaddition,apropervaluefor drangingfrom120to180mhasno
obviousdifferencebetweendifferentdatasets.
AnotherimportantparameteroftheiBDDmethodisthethresholdconstant θ,whichshouldbedeterminedaccording
tothedistributionoftrajectories.Generally,anevendistributionoftrajectoriesinagivendatasetcorrespondstoalarge
valuefor θ.Inreallife,trajectorydistributionisdirectlyrelatedtothetypeandnumberofindividual’ssemanticplaces.
Forexample,formanyelders,therewillbesignificantlymoretrajectoriesto communitycenter thantorelativehome.A
comparisonofAUCvaluesfor θ=0.05,0.10,and0.20hasbeenprovidedinTable3,whichsuggeststhat θ=0.10is
suitableforevaluatingourproposedmethodwiththechosendatasets.Additionally,dataset T−6,T−7andT−8obtained
obvioushigherAUCvaluesthanotherswhen θissetwith0.20becausethereareonlytwosemanticplacesinthemand
trajectoriesinthesedatasetsarerelativelyneat.
(3)Timecomplexity
Theoretically,iBDDhasthetime-complexityof O(mn),wheremisthenumberoftrajectoriesinaset,and nisthenumber
ofcellsofatesttrajectory.ThislineartimecomplexityshowsthatourproposediBDDmethodisefficientindetecting
disorientationtrajectory.
Inaddition,wealsoexaminetheCPUtimeconsumptionindetectingaGPStrajectorywithadifferentnumberofhistorical
trajectoriescontainedintheset T.AsdepictedinFig.9,theelapsedaverageCPUtimefordetectingatesttrajectoryis

Q.Linetal./PervasiveandMobileComputing19(2015)71–85 83
Fig. 8.TheROCcurvesofiBDDforalldatasets.Therangesoffalsepositiverateanddetectionratearesetto[0,0.2]and[0.3,1].
Table 3
TheAUCvaluesofiBDDwithdifferentvaluesof θwhend=150m.
θT−1T−2T−3T−4T−5T−6T−7T−8T−9T−10
0.05 0.9979 0.9991 0.9967 0.9971 0.9971 0.9998 0.9981 0.9978 0.9995 0.9997
0.10 0.9972 0.9995 0.9962 0.9968 0.9967 0.9997 0.9977 0.9974 0.9994 0.9992
0.20 0.7731 0.7912 0.8005 0.7889 0.7544 0.9210 0.9074 0.9309 0.8127 0.7999
Fig. 9.TheelapsedaverageCPUtimeofiBDDindetectingatrajectoryatdifferentscaleoftrajectoriesindataset.
relativelylowandthereisanobviouslinearrelationshipbetweentimecomplexityandthenumberoftrajectories.Therefore,
ourproposediBDDmethodisefficientindetectingdisorientationbehaviorofelderswithimpairedcognition.
6. Related work
Thissectionreviewsrelatedworkinthreerelevantsub-areas:outdoormonitoring,routefindingandanomalousGPS
trajectorydetection.Theresearchinthefirstcategorywasaimedmainlyatmonitoringsafetyofelderswithseveredementia
inoutdoorenvironments;whereasworkinthesecondcategoryisintendedtoprovidenavigationsupportforpeoplewith
mildcognitivedecline.Thefinalcategoryfocusesonresearchindetectinganomaloustrajectories.
6.1. Outdoormonitoring
Therehasbeenmuchworktopreventpeoplewithseveredementiafromgettinglostbyconstrainingthemtoaprotected
area.Generally,alocationsensingdevice(custom-builtoroff-the-shelf)isneededtocollectauser’slocationinformation.
Shimizuetal.[17]developedalocationsystembyutilizingalocationsensingdeviceandGIS.Thepatientcarriesa
responderconsistingofacellphoneandGPSunit.Carerscanfindthepatient’scurrentpositiononamapdisplayedon
theirPCbyinvokingtheresponderthroughthecellphonenetwork.Thissystemwasdevelopedmainlytoalleviatecarers’
workloadwhencaringforpatientswithseveredementia.Ogawaetal.[9]investigatedasafetysupportsystembylocating

84 Q.Linetal./PervasiveandMobileComputing19(2015)71–85
awanderingperson’spositionviaamobilephoneterminal(havingnotelephonecallfunctionality).Theterminalobtainsa
cellstationIDandsendsittothephonecompany,allowingthePCtodownloadthelatitudeandlongitudedataoftheuser’s
location(i.e.,stationlocation)fromthemobilephonecompanyviatheInternet.Whenthewanderingelderlypersonisaway
fromhome,thesystemautomaticallyinformsthecaregiverandalsosendstheelder’slocationbye-mailtothecarers.For
furtherdeterminingtheuser’ssurroundings,intheirrecentwork,theyaddedasmallmicrophonetocollectenvironmental
sound[18].Inthesesystems,theauthorsreportthatthewanderingperson’slocationcanbeidentifiedwithin100mfrom
themobilephonecompany’santennaID.
Therearealsosystemsthatattempttoassistolderadultsdirectly.Forexample,theTakeMeHome-Serviceinthe
COGKNOWproject[19]aimstohelpdisorienteduserstofindtheirwaybackhomebyutilizingaGPS-equippedPDA.
Similarly,researchershaveinvestigatedamobilesocialnetwork[20]thatprovidesmonitoringforeldersusingaGPS-
enabledmobilephone.Inthissystem,whenanelderisbeyondthepre-definedsecurityperimeteraroundtheirhome,
theirmobilewillringandvibrate,displayingamaponthemobileonhowtogethome.
Theabovesolutionsweredevelopedprimarilyforpeoplewithseveredementia,eithersettingtightconstraintsonwhere
apatientmaybe,orprovidingawayofsharingtheircurrentlocationwithacarer.
6.2. Routefinding
Findingawaytypicallyrequiresapersonknowingwheresheis,knowingherdestination,followingthebestroutetothe
destination,recognizingthedestinationuponarrival,andfindingherwayback[21].Allofthesearechallengingtasksfor
thecognitively-impairedeldersduetodeclinesintheirmemory,thought,andreasoningfunctions.
TheOpportunityKnocksystemproposedbyPattersonetal.[10]isoneoftheearliestworksinthisfield.Inthissystem,
cognitivelyimpairedpeoplearetrackedinrealtimewithaGPSdevice.Locationdataissenttoaremoteserverviaacell
phone.Theinferenceenginerunningontheserverdetectspotentiallyerroneousbehavior,suchastakinganincorrectbus,
basedonuser’shistoricaltrajectories.Ifananomalyisdetected,thesystemplaysasoundlikeaknockonadoortogetthe
user’sattention,andthenrecommendsawaytogetbackontracktotheuser.Theuser’slikelytransportationmodeislearned
fromtheirhistoricaltrendsandahierarchicalDynamicBayesianNetworkmodel[22].Similarly,Chang[11]investigated
detectingdeviationfromtravelingtrajectoriesforcognitivelyimpairedworkers.BycomparingeveryincomingGPSpoint
withanormalpath,atrajectorywithdeviationcanbedetectedinrealtimeandremindersareprovidedtotheuserifneeded.
However,thepaperdidnotspecifyhowtoidentifynormalpaths.Basedonthiswork,amobilelocation-basednetworking
systemwasintroducedbyChangandWang[23]tofurtherimproveservicesforcognitivelyimpairedworkersbyincluding
formalcaregiversinthesystem.Requestforhelpcanbeautomatic(i.e.,whenthesystemdetectsapotentialdeviation)or
manual(i.e.,whenapersonfeelslost).
Withboththemodel-based[10]anddistance-based[11]approaches,thereisahighfalsepositiverateduetothe
abundantnoiseofGPSdataandtherandomnessofhumanmobility.Inaddition,model-basedmethodsareusuallynot
optimalindetectinganomalies[13],whiledistance-basedmethodssufferfromahightimecomplexityduetothefrequent
calculationofdistances.Furthermore,bothapproachesareincapableofdetectingaloopingpatternthatoccursoftenwhen
peoplearedisoriented.
6.3. Outliertrajectorydetection
Theworkinthisareafocusesondetectinganomaloustrajectories.Currently,therearealargenumberofsolutions,each
addressingdifferentaspectsofabnormalitybytargetingspecificproblems.
Forinstance,Leeetal.[24]proposedthepartition-and-detectframeworktodetectoutlyingsub-trajectories.Intheir
framework,boththedistanceanddensitymeasuresareusedforanomalydetection.LikeLeeetal.,Geetal.[25]discover
evolvingtrajectoryoutliersbasedonanoutlyingscorebycombiningtheevolvingdirectionanddensityoftrajectories.Using
aclusterjoinmechanism,Buetal.[26]presentedanoutlierdetectionframeworkformonitoringanomaliesovercontinuous
trajectorystreams.Alternatively,Lietal.[27]developedatemporaloutlierdetectionapproachforvehicletrafficdata,which
aimstodiscoveranomaloustrafficchangesinroadnetworks.Inaddition,anumberofdifferentmachinelearning-based
approaches[28–30]havebeendeveloped,withthelimitationofhighcostsinlabeling.Focusingontaxiapplications,Zhang
etal.[31,32]proposedasignificantlydifferentapproachtodetectinganomaloustrajectoriesbyexploitinganisolation-based
mechanism[13].Aftermodelingatrajectoryasasequenceoftraversedcells,anomalydetectionisconvertedtoaproblemof
findingthosetrajectoriesthatare‘‘fewanddifferent’’fromnormaltrajectoryclusters.Similarly,inanotherGPS-basedtaxi
application,Yuanetal.[33]developedasmartdrivingdirectionsystemthatcanhelptaxidriverschoosedrivingdirections
byprovidingafastestroutetoagivendestinationatagivendeparturetimebasedonGPStracesandtheintelligenceof
experienceddrivers.Anextendeddiscussionaboutsemantictrajectoriesmoldingandanalysishasrecentlybeendoneby
Parentetal.[34].
OurworkisdirectlyinspiredbyZhangetal.’sapproaches[31,32],butwithadifferentresearchobjectiveandmodel.Our
workmodelsone’smovementtrajectoriesasagraphandtheobjectiveistodiscoverdisorientationbehaviorsforcognitively-
impairedelders,resultingindifferentsituations(e.g.,twotypesofoutlierswithcertainduration)thatshouldbetakeninto
account.

Q.Linetal./PervasiveandMobileComputing19(2015)71–85 85
7. Conclusion
In this paper, we have proposed to model people’s movement trajectory as a graph and formulated the elder’s
disorientationdetectionproblemasanabnormaltrajectoryidentificationissue.Wefurtherpresentanewmethodcalled
iBDDthatcandetectdisorientationbehaviorsforcognitively-impairedeldersinreal-time.Insteadofusingdistanceor
densitymeasures,theiBDDmethoddetectsoutlyingtrajectoriesbyutilizingthedisorientationtrajectory’sintrinsicproperty
ofbeing‘‘fewanddifferent’’fromthemajority.
Theproposedapproachhasbeenvalidatedontenindividuals’historicalGPStrajectories.Evaluationresultsshowthat
theiBDDmethodachievesexcellentperformancewithAUC >0.99,a95%detectionrateandafalsepositiverateofless
than3%,basedonavalueof150mforcellsize dandavalueof0.10forthresholdconstant θ.Basedonthedisorientation
behaviorsdetected,eitherareminderoralertingservicecanbedeliveredtoeldersandcarers.
Inthefuture,weplantoextendthisworkintwodirections.First,weintendtocollectGPStracesofelderlypeoplein
realworldsettingsandfine-tunetheiBDDmethodsothatitworksinrealeldercaresystems.Second,weattempttoexploit
otherinformationcontainedinGPStraces,suchastimestamps,sothatdisorientationbehaviorcanbeidentifiedinamore
preciseandfine-grainedmanner.
Acknowledgment
TheauthorswouldliketothankDr.XingXieofMicrosoftResearchinAsiaforprovidingtheGPSdatasetusedinthe
evaluationofthiswork.ThisworkwaspartiallysupportedbytheNationalNaturalScienceFoundationofChina(No.
61332013).
References
[1] UNFPA,StateofWorldPopulation2011.[Online]Available:http://foweb.unfpa.org/SWP2011/reports/EN-SWOP2011-FINAL.pdf.
[2] C.Kawas,R.Katzman,EpidemiologyofdementiaandAlzheimer’sdisease,AlzheimerDis.(1999)95–116.
[3] K.Du,D.Zhang,X.Zhou,M.Hariz,Handlingconflictsofcontext-awareremindingsysteminsensorisedhome,ClusterComput.14(1)(2011)81–89.
[4] T.Giovannetti,D.J.Libon,L.J.Buxbaum,M.F.Schwartz,Naturalisticactionimpairmentsindementia,Neuropsychologia40(8)(2002)1220–1232.
[5] B.Reisberg,S.Ferris,M.Leon,T.Crook,Theglobaldeteriorationscaleforassessmentofprimarydegenerativedementia,Am.J.Psychiatry139(1982)
1136–1139.
[6] R.McShane,K.Gedling,J.Keene,etal.,Gettinglostindementia:alongitudinalstudyofabehaviouralsymptom,Int.Psychogeriatr.10(1998)253–260.
[7] [Online]Available:http://www.nedap-securitymanagement.com/.
[8] L.Robinson,D.Hutchings,L.Corner,F.Beyer,etal.,Asystematicliteraturereviewoftheeffectivenessofnon-pharmacologicalinterventionstoprevent
wanderingindementiaandevaluationoftheethicalimplicationsandacceptabilityoftheiruse,HealthTechnol.Assess.10(26)(2006)1–124.
[9] H.Ogawa,Y.Yonezawa,H.Maki,etal.Amobilephone-basedsafetysupportsystemforwanderingelderlypersons,in:Proc.ofEngineeringinMedicine
andBiologySociety,EMBS,2004,pp.3316–3317.
[10] D.Patterson,L.Liao,K.Gajos,etal.,Opportunityknocks:asystemtoprovidecognitiveassistancewithtransportationservices,in:Proc.ofUbiComp,
2004,in:LNCS,vol.3205,2004,pp.433–450.
[11] Y.Chang,Anomalydetectionfortravellingindividualswithcognitiveimpairments,Newsl.ACMSIGACCESSAccess.Comput.97(2010)25–32.
[12] M.C.González,C.A.Hidalgo,A.L.Barabási,Understandingindividualhumanmobilitypatterns,Nature453(2008)779–782.
[13] F.T.Liu,K.M.Ting,Z.-H.Zhou,Isolationforest,in:8thIEEEInternationalConferenceonDataMining,ICDM,pp.413–422.
[14] D. Martino-Saltzman, B.B. Blasch, R.D. Morris, et al., Travel behavior of nursing home residents perceived as wanderers and nonwanderers,
Gerontologist31(5)(1991)666–672.
[15] Y.Zheng,Q.Li,Y.Chen,etal.UnderstandingmobilitybasedonGPSdata,in:Proc.ofUbiComp,2008,pp.312–321.
[16] Y.Zheng,X.Xie,W.Ma,GeoLife:acollaborativesocialnetworkingserviceamonguser,locationandtrajectory,IEEEDataEng.Bull.33(2)(2010)
32–40.
[17] K.Shimizu,K.Kawamura,K.Yamamoto,Locationsystemfordementiawandering,in:Proc.ofEMBS,2000,pp.1556–1559.
[18] S.Matsuoka,H.Ogawa,H.Maki,etal.Anewsafetysupportsystemforwanderingelderlypersons,in:Proc.ofEMBS,2011,pp.5232–5235.
[19] M.Mulvenna,S.Sävenstedt,F.Meiland,etal.Designing&evaluatingacognitiveprostheticforpeoplewithmilddementia,in:Proc.ofECCE,2010,
pp.11–18.
[20] C.Palomino,P.Heras-Quiros,etal.Outdoorsmonitoringofelderlypeopleassistedbycompass,GPSandmobilesocialnetwork,in:Proc.ofIWANN,
2009,pp.808–811.
[21] J.Brush,M.Calkins,Cognitiveimpairment,wayfinding,andthelong-termcareenvironment,Pers.Gerontol.13(2)(2008)65–73.
[22] L.Liao,D.Fox,H.Kautz,Learningandinferringtransportationroutines,in:Proc.ofAAAI,2004,pp.348–353.
[23] Y.Chang,T.Wang,Mobilelocation-basedsocialnetworkinginsupportedemploymentforpeoplewithcognitiveimpairments,Cybern.Syst.41(3)
(2010)245–261.
[24] J.-G.Lee,J.Han,X.Li,Trajectoryoutlierdetection:apartition-and-detectframework,in:Proc.ofICDE,2008,pp.140–149.
[25] Y.Ge,H.Xiong,Z.-H.Zhou,etal.Top-eye:top- kevolvingtrajectoryoutlierdetection,in:Proc.ofCIKM,2010,pp.1733–1736.
[26] Y.Bu,L.Chen,A.W.-C.Fu,D.Liu,Efficientanomalymonitoringovermovingobjecttrajectorystreams,in:Proc.ofKDD,2009,pp.159–168.
[27] X.Li,Z.Li,J.Han,J.-G.Lee,Temporaloutlierdetectioninvehicletrafficdata,in:Proc.ofICDE,2009,pp.1319–1322.
[28] X.Li,J.Han,S.Kim,H.Gonzalez,ROAM:rule-andmotif-basedanomalydetectioninmassivemovingobjectdatasets,in:Proc.ofSDM,2007,
pp.273–284.
[29] R.R.Sillito,R.B.Fisher,Semi-supervisedlearningforanomaloustrajectorydetection,in:Proc.ofBMVC,2008,pp.1035–1044.
[30] Z.Liao,Y.Yu,B.Chen,AnomalydetectioninGPSdatabasedonvisualanalytics,in:Proc.ofVAST,2010,pp.51–58.
[31] D.Zhang,N.Li,Z.Zhou,C.Chen,etal.iBAT:detectinganomaloustaxitrajectoriesfromGPStraces,in:Proc.ofUbiComp,2011,pp.99–108.
[32] C.Chen,D.Zhang,P.S.Castro,etal.Real-timedetectionofanomaloustaxitrajectoriesfromGPStraces,in:Proc.ofMobiQuitous,2011,pp.1–12.
[33] J.Yuan,Y.Zheng,X.Xie,G.Sun, T-drive:enhancingdrivingdirectionswithtaxidrivers’intelligence,IEEETrans.Knowl.DataEng.25(1)(2013)
220–232.
[34] C.Parent,S.Spaccapietra,C.Renso,etal.,Semantictrajectoriesmodelingandanalysis,ACMComput.Surv.45(4)(2013)42–64.