Entropy 2013, 15,2218-2245;doi:10.3390/e15062218 OPENACCESS entropy ISSN1099-4300 www.mdpi.com/journal/entropy Article VesselPatternKnowledgeDiscoveryfromAISData:A FrameworkforAnomalyDetectionandRoutePrediction GiulianaPallotta,MicheleVespeandKarnaBryan NATOScienceandTechnologyOrganization(STO),CentreforMaritimeResearchand Experimentation(CMRE),VialeSanBartolomeo400,19126,LaSpezia,Italy; E-Mails:[email protected](M.V.);[email protected](K.B.) Authortowhomcorrespondenceshouldbeaddressed;E-Mail:[email protected]; Tel.:+39-0187-527-349;Fax:+39-0187-527-354. Received:1March2013;inrevisedform:10May2013/Accepted:29May2013/ Published:4June2013 Abstract: UnderstandingmaritimetrafﬁcpatternsiskeytoMaritimeSituationalAwareness applications,inparticular,toclassifyandpredictactivities.Facilitatedbytherecent build-upofterrestrialnetworksandsatelliteconstellationsofAutomaticIdentiﬁcation System(AIS)receivers,shipmovementinformationisbecomingincreasinglyavailable, bothincoastalareasandopenwaters.Theresultingamountofinformationisincreasingly overwhelmingtohumanoperators,requiringtheaidofautomaticprocessingtosynthesize thebehaviorsofinterestinaclearandeffectiveway.AlthoughAISdataareonlylegally requiredforlargervessels,theiruseisgrowing,andtheycanbeeffectivelyusedto inferdifferentlevelsofcontextualinformation,fromthecharacterizationofportsand off-shoreplatformstospatialandtemporaldistributionsofroutes.Anunsupervisedand incrementallearningapproachtotheextractionofmaritimemovementpatternsispresented heretoconvertfromrawdatatoinformationsupportingdecisions.Thisisabasisfor automaticallydetectinganomaliesandprojectingcurrenttrajectoriesandpatternsintothe future.Theproposedmethodology,calledTREAD(TrafﬁcRouteExtractionandAnomaly Detection)wasdevelopedfordifferentlevelsofintermittency(i.e.,sensorcoverageand performance),persistence(i.e.,timelagbetweensubsequentobservations)anddatasources (i.e.,ground-basedandspace-basedreceivers). Keywords: maritimesituationalawareness;knowledgediscovery;maritimeroute extraction;routeprediction;anomalydetectionEntropy 2013, 15 2219 1.Introduction Maritimetransportationrepresentsapproximately90%ofglobaltradebyvolume,placingsafety andsecuritychallengesasahighpriorityfornationsacrosstheglobe.Maritimesurveillancedataare collectedatdifferentscalesandareincreasinglyusedtoachievehigherlevelsofsituationalawareness. AutomaticIdentiﬁcationSystem(AIS)technologyprovidesavastamountofnear-realtime information,callingforaneverincreasingdegreeofautomationintransformingdataintomeaningful informationtosupportoperationaldecisionmakers.Asanexample,theCentreforMaritimeResearch andExperimentation(CMRE)iscurrentlyreceivinganaveragerateof600MillionAISmessagesper monthfrommultiplesources,andtherateisincreasing[1].AISisaself-reportingmessagingsystem originallyconceivedforcollisionavoidance(AISismandatoryforshipsof300grosstonnageand upwardsininternationalvoyages,500andupwardsforcargoesnotininternationalwatersandpassenger vessels[2].Inaddition,ﬁshingvesselsgreaterthan15msailinginwaterunderthejurisdictionof theEuropeanUnionMemberStatesshallalsoberequiredtobeﬁttedwithAIS[3].)tobroadcast informationontheirlocation(positional,identiﬁcationandotherinformation)atavariablerefresh rate,whichdependsontheirmotion(vesselsatanchortransmittheirpositioneverytwominutesand increasethebroadcastrateuptotwosecondswhenmaneuveringorsailingathighspeed;everyﬁve minutes,vesselstransmitotherdata(staticandvoyagerelatedinformation)containingidentiﬁers,such asInternationalMaritimeOrganization(IMO)number,callsign,shipnameandMaritimeMobileService Identity(MMSI),usedasaprimarykeytolinkthemessagetopositioninformation.Staticinformation alsoincludessize,typeofvesselandcargo,whereasvoyagerelateddata,suchasEstimatedTimeof Arrival(ETA)anddestination,aremanuallysetandnotfullyreliable[4].)Overthelastseveralyears,the AISdatareceivedbyshipsandcoastalstationshavebeentransmittedtoregionalornationaldatacenters. Whenmultiplereceiversareconnectedintonetworks,certainchallengesarisewithdataintermittency, resolvingdataredundancyreceivedbymultiplereceivers,correctingerrorsintimestampsassignedby varyingreceiversandidentifyingtracksofvesselsthaterroneouslysharethemessageidentiﬁer.This levelofpre-processingisnecessarytoextractmaritimemotionpatterns,especiallyataglobalscale. ReceivingAISmessagesfromspace[5]isbecomingincreasinglycommonplace.Asopposedto terrestrialnetworksofAISreceivers,whoseperformanceischaracterizedbyhighpersistence,butlimited coverage,satellite-basedsystemscanpickupmessagesintheopensea,farawayfromthecoastline. Space-basedreceiverstendtobemountedonLowEarthOrbit(LEO)satellites,sotheAIScoverage isglobalattheexpenseofpersistence,duetotheorbitingplatformrevisittime.Itisclearthatwhen integratingsuchsystemswithdatareceivedbyterrestrialreceivers,thereareadditionalissuestoresolve withvariablefrequencyupdate,coverageandpersistence. Inthiswork,amethodologyispresentedthataimstoconvertthelargeamountofAISdatainto decisionsupportelements,independentlyofthenumberofreceivers,theirperformance,theplatform oforiginandthescaleoftheareaofinterest.Theknowledgeisextractedviaanincremental learningapproach,inordertodynamicallyadapttoevolvingsituations(e.g.,maritimeseasonalpatterns, operationalconditionsorchangingroutingschemes).Thisallowsmaritimetrafﬁctobecharacterized followingafullyunsupervisedlearningstrategywithno apriori informationneeded(i.e.,usingonly rawAISdata).Entropy 2013, 15 2220 Theproposed trafﬁcrouteextraction methodologycanbeusedtoprovideup-to-datehighlevel contextualinformation(e.g.,Level2processingintheJointDirectorsofLaboratories(JDL)model[6]). Knowledgeoftrafﬁcroutesisausefulinputtosituationalawarenessandhelpsinunderstandingseasonal variationsintrafﬁcpatterns.Besidestrafﬁcdensities,theextractedroutesprovideusefulinformationon dailypatternsandtransitdurationdifferentiatedbyvesseltypes.Further,extractedroutesenablerealistic simulationsoftrafﬁc,whichareusefultotestandevaluatetargettrackingperformance,theeffectiveness ofsurveillancetechnologiesandotherdecisionsupportframeworks. Generatedcontextualmaritimeknowledgecanalsobeusedtoperformrule-basedandlow-likelihood anomalydetection.Rule-basedanomalydetectionapproachesrefertothegenerationofalertsbasedon asetofrules[7],suchasmaximumspeedallowedinaport,presenceinareasrestrictedtonavigationor inconsistenciesbetweenshipclaimedandactualactivity.Conversely,low-likelihoodanomalydetection aimsatdetectingdeviationsfrom“normality”ofvesseltrafﬁcpatternsderivedinthelearningphase(see, e.g.,[8]andreferencestherein)andisillustratedviaanexampleprovidedinthepresentwork.Behaviors thatdifferfrom“normality”donotnecessarilymeantheyare“anomalies”inanoperationalcontext,but theyarehighlightedas unusual forfurtheranalysis. Thevesseltrafﬁcandmotioninformation,onceextracted,canbealternativelyexploitedtoperform shiproutepredictionatagiventime.Thisistheprocessofpredictingshipmovementswellbeyond anyavailablepositioningdata,basedonbehaviorsofpastvesselsonthesameroute.Thisisuseful,for example,incounterpiracyapplicationstoidentifyriskareasassociatedwiththejointpredictedpresence ofwhiteshippingdensity(e.g.,commercialmerchanttrafﬁc)andPiratesActionGroups(PAG)[9]. Backwardandforwardtrackingofvesselscanalsobesigniﬁcantlyimprovedusingthelearnedmaritime trafﬁcpatterns,whichareparticularlyusefulwhenattemptingtofuseAISandspace-basedopticalor SyntheticApertureRadar(SAR)information(e.g.,[10]). Thedistributionandcharacterizationoftrafﬁccanalsobeusedforaugmentingremotesensing trackingandclassiﬁcationperformance,enablingknowledge-basedtrackingandclassiﬁcation (e.g.,[11]).Speciﬁcally,theknowledgeofvesselpatternscanbeusedfor(i)connectingtracksoriginated bythesametargetandbrokenbygapsincoverageorreducedobservabilityand/or(ii)providing apriori knowledgeaboutthevesseltypeforclassiﬁcationpurposes. InSection 2,wegiveabriefreviewofrelatedworkontrafﬁccharacterizationandrouteknowledge extraction.WediscussthetrafﬁcknowledgediscoverymethodologyinSection 3.Thisisfollowed bysomeexamplesofrouteknowledgeexploitationinSection 4:therouteclassiﬁcationisgivenin Section 4.1.Twospeciﬁcapplications(i.e.,routepredictionandanomalydetection)areprovidedin Sections 4.2 and 4.3,respectively,toillustratethepotentialofthederivedknowledge.Finally,concluding remarksaregiveninSection 5. 2.RelatedWork Theapplicationofstatisticalmethodologiestoderivemotionpatternsfromacollectionoftrajectories inanunsupervisedwayisachallengingtask.Severalmethodshavebeenproposedasappliedinvideo surveillanceandimageprocessing(e.g.,[12–16]).In[17],aprobabilisticmodeltotrackhumanbehavior overtimeispresented.Thepapers[18–21]speciﬁcallydealwithmaritimeapplications,althoughEntropy 2013, 15 2221 usingimageprocessingtechniques.Reference[12]presentedanextensivemodeltostatisticallylearn motionpatternswithoutanypriorknowledgeintrafﬁcsceneswherethetrafﬁcﬂowsareconstrained tostayinspeciﬁcareas.Theapplicationofsuchtechniquesinmaritimesituationalawarenesshas gainedanincreasingacceptanceduringrecentyears.Onepossibleapproachistosubdividethearea ofinterestintoaspatialgridwhosecellsarecharacterizedbythemotionpropertiesofthecrossing vessels(e.g.,[10,22,23]).Althougheffectiveforsmallareasurveillance,themainlimitationsofthe “grid”-basedapproachresidesintherequiredcomputationalburdenwhenincreasingthescale,aswell astheneedfor apriori selectionoftheoptimalcellsize.Inareascharacterizedbycomplextrafﬁc, likeintersectingsealanes,theresultingmulti-modalbehavioraldescriptionwouldleadtocomplex algorithmstoperformanomalydetection.Anewtrendintheﬁeldofmaritimeanomalydetectionis toadopta“vectorial”representationoftrafﬁc,wheretrajectoriesarethoughtofasasetofstraightpaths connectingwaypoints;thisallowsacompactrepresentationofvesselmotionsthatcanbeimplemented ataglobalscale.Intheworksreportedin[24,25],thewaypointsarenodesintheproximityofland masses,andGreatCircleroutesareformedtorepresentoceanjourneys.Inareascharacterizedby complexroutingsystems,itisnecessarytofurtherintroduceintermediatenodes(i.e.,turningpoints)to moreaccuratelydescriberoutes.For[26,27],turningpointsaredetectedinareaswherechangesinthe CourseOverGround(COG)ofvesselsareconsistentlyobserved.Oneofthelimitationsof“vectorial” approachesisthedetectionofturningpointsinunregulatedareas,wherethebehaviorofvesselsismuch morecomplexand,therefore,difﬁculttocategorize.Thepresentpaperaddressesthispracticalissue: therepresentationofmaritimetrafﬁcisstill“vectorial”,butincontrasttopreviousresearch,theroute objectsaredirectlyformedbytheﬂowvectorsofthevesselswhosepathsconnectthederivedwaypoints (i.e.,stationaryareas,aswellasentryandexitpoints).Speciﬁcally,theapproachintroducedhereisbased onapreliminaryclusteringofwaypoints.Trajectoriesare,then,identiﬁedbetweensuchwaypoints. Differentlyfromother“vectorial”representations,therouteobjectsincludedirectionalchangeswithout explicitlyderivingturningpoints.Aswillbeseen,itisstillpossibletoconsistentlycapturemaritime patternsinacompactandaccurateway.Itisalsofeasibletoextracttemporalinformation,likeroute traveltimedistributionsanddailypatterns,aswellastoassociatehistoricalroutepatternstovessels. Thesefeaturesenablethediscoveryofmaritimetrafﬁcknowledgethatcanbeusedtoimplementhigher levelanomalydetectiontools.Additionally,thedistance-basedapproach,adoptedin[26,27],wasnot alwayseffectiveindistinguishingwaypointsclosetoeachother.Inordertoovercomethisdifﬁculty,a density-basedalgorithm(i.e.,DBSCAN—Density-BasedSpatialClusteringofApplicationswithNoise) wasselectedandadaptedtothespeciﬁcmaritimeapplication. Dealingwithpotentialapplicationsofthederivedframework,anomalydetectionintrajectorydata isoneofthemostinteresting.Withinthisﬁeld,agreatnumberofpapersrecentlyappeared.Some ofthemclassifyatrajectoryasanomalousbasedonthedistancetotheclosestsetoftrajectories, groupedusingsimilaritymetrics.Whenthedistancebetweentrajectoriesisexpressedintermsofa likelihood,wespeakofprobabilisticanomalydetection[28].In[17,29–31],someprobabilisticmethods foranomalydetectionarepresented.Manymethodstendtoﬁrstpre-processthetrajectories,since commonlyusedsimilaritymeasures,suchastheEuclideandistance,requireequallyspacedandproperly alignedtrajectories.Toovercomethesedifﬁculties,somealternativemetricshavebeenproposed,suchas theDynamicTimeWarping(DTW)(see,e.g.,[14])whichﬁndstheminimumEuclideandistancewhenEntropy 2013, 15 2222 thedatapointsofthetwotrajectoriesareshiftedarbitrarilyintime).However,mostoftheavailable approachesarethoughttoworkwithcompletetrajectories, i.e.,theyneedthepointsofthewhole trajectorybeforeclassifyingthetrajectoryasanomalous.Thatisaprobleminareaswherepositional dataarereceivedonlyintermittentlyandcompletetrajectoriesarenotobserved.Moreover,whenapplied forsurveillancepurposes,thedetectionofanomaliesneedstobeperformedon-line.Inthiscontext,it iscrucialtoreducedelaysbetweenthestartoftheanomalousbehaviorandthealarmraisedbythe monitoringsystem.Sequentialprocesscontroltechniquesaimatshorteningtheaveragetimerequired tosignalachangeinthenormalprocess.Inthispaper,weapplypoint-basedincrementalalgorithms bothinmaritimeknowledgediscoveryandexploitation.Theprovidedexampleofanomalydetectionis performedbyusingaslidingtimewindow,similarlytovideosurveillancetechniques(see,e.g.,[15]).A similarapproachisproposedin[32],wheresequentialmotionanomalydetectionisperformed,assuming thatAIStrainingdataarealreadyextractedtoformclustersofcommonpaths.Inthepresentpaper,the pre-processing,transformationandvalidationofAISdataisintegratedintothefunctionalarchitecture, whichgeneratesthetrafﬁcpatternframework. 3.TrafﬁcModelandKnowledgeDiscovery Theproposedmethodology,calledTrafﬁcRouteExtractionandAnomalyDetection(TREAD), automaticallylearnsastatisticalmodelformaritimetrafﬁcfromAISdatainanunsupervisedway, i.e., withoutassuminganypriorknowledgeonthemonitoredscene.Buildingontheworkin[26,27,33],the trafﬁcknowledgeusedhereisshapedbyvesselobjects,createdandupdatedfromthesequenceofinput AISmessages.Aboundingboxisselectedandcorrespondstothespeciﬁcareaundersurveillance.The seriesofvesselstatevectorscanoriginateasdiscontinuousevents,suchasabreakinobservationupdates. Theclusteringofsuchevents,initiatedbydifferentvesselsobjects, Vs,enablesustoformwaypoint objects, WPs,whichidentifyeitherstationarypoints, POs,entrypoints, ENs,andexitpoints, EXs, withintheselectedboundingbox.Thelinkingofsuchwaypointsultimatelyleadstothedetection andstatisticalcharacterizationofrouteobjects, Rs.Anomaliescanthenbedetectedonthebasisof thediscoveredknowledgeanditsinteractionwithreal-timevesseltrafﬁc.Thegeneralassumptionof thestatisticalmodelisthatthefeaturevaluesofthedatapointscomefromastable(i.e.,stationary) distributionofnormaltrafﬁc,estimatedusingtrainingdata.Thefeaturedatapointsareconsideredas singletrajectorypoints.Intheliterature,suchanapproachisreferredtoasapoint-basedapproach (see,e.g.,[8]),incontrasttotrajectory-basedapproaches,wherethetrafﬁcrepresentationisbasedon completetrajectories(see,e.g.,[14]). Theapproachpresentedhereisapracticalcompromisetogetareliabletrafﬁcrepresentationwithout increasingthemodelcomplexity:(i)itusesapoint-basedtrafﬁcrepresentationand(ii)itintegratestime informationintotheknowledgeexploitationtoincludetherelationshipbetweensuccessivedatapoints. ApracticaladvantageisthattheTREADmethodologycaneasilyhandletrajectoriesofunequallengthor withgaps.Asamatteroffact,incompleteandsegmentedtrajectoriesarefrequentinmaritimetrafﬁc,due totherefreshrateofAISmessagesbeinghighlyvariableforanumberoflegitimatereasons(sinceitwas conceivedforcollisionavoidance,AISClassAunitschangethemessagestransmissionratedepending ontheneedtorefreshinformation,rangingfromthreeminutes(shipatanchor)uptotwoseconds(fastEntropy 2013, 15 2223 and/ormaneuveringvessel).Similarly,ClassBdevicesfornon-SOLAS(SafetyofLifeatSea)vessels reportatvariableintervals,althoughtransmittingatlowerratesthanClassAequipment[34].).This occurswhenAIStracksare“lost”,becauseof(i)terrestrialcoveragegapsinthenetworkofreceivers, (ii)intermittentAIS[35]or(iii)longtimeintervalsbetweensubsequentoverpassesorlowprobabilityof detectionofsatellite-basedreceivers[36].Avesseltranspondercouldalsobeswitchedoffintentionally, butthatisaseparateissue. TREADFunctionalArchitectureManager: thediscoveryandexploitationofmaritimetrafﬁc knowledge-basedonAISinformationfollowsthefunctionalarchitectureshowninFigure 1;thestream ofAISmessagesisprocessedtoincrementallylearnmaritimemotionpatternsthroughthe“Vessel ObjectsManager”activatedbyrelevanteventsbasedonthetemporalandspatialcharacterizationof vesselbehavior.Theclusteringofsucheventsleadstothediscoveryofwaypoints(stationaryobjects andentry/exitpoints).Theknowledgediscoveryprocessisfollowedbypotentialexploitation,suchas inrouteclassiﬁcation,predictionandanomalydetection. Figure1. Knowledgediscoveryfunctionalarchitecture:historicaldatabaseorreal-time datastreamofAutomaticIdentiﬁcationSystem(AIS)messagesissequentiallyprocessedto incrementallylearnmaritimemotionpatternsthroughprocesses(“managers”)activatedby relevantevents.Theknowledgediscoveryprocessisfollowedbyon-lineexploitation,such asrouteclassiﬁcation,predictionandanomalydetection. VesselObjectsManager: Assoonasanewvesselentersthemonitoredscene,adetectionoccurs, andthemanagementofvesselobjectsisinitialized(seeAlgorithm 1-UnsupervisedRouteExtraction, AnnexA).Thelistofvesselobjects, Vs,isupdatedaccordingtotheinformationcontentofeach decodedAISmessage(ordatabaserecordwhenperforminghistoricaldataanalysis).Everyvessel object, VsfMMSIg,isidentiﬁedbytheMMSInumberandcontainsbothstaticanddynamicproperties. Whiletheformerarelinkedtotheidentiﬁcationofthevessel(e.g.,type,callsign,name,International MaritimeOrganization(IMO)number,size),thelatterarerelatedtothestatevector(e.g.,position, CourseOverGround(COG),SpeedOverGround(SOG))andtohistoricalandcurrentroutepatterns). Thesepropertiesareprogressivelyupdatedwhennewdatabecomeavailable.Withreferenceto Algorithm 1—UnsupervisedRouteExtractioninAnnexA—the VsfMMSIg:track referstotheEntropy 2013, 15 2224 timestampedhistoryofobservedstatevectorinformation(i.e.,positionandvelocityparameters)for thevesselobject, VsfMMSIg. Algorithm1 UnsupervisedRouteExtraction Require: messages //AISmessagescontainingstaticanddynamicinfo,e.g., MMSI, COG, SOG, x, y, timestamp Require: //timeneededbeforelabelingthevesselasbeing‘lost’ Require: Vs;ENs;POs;EXs;Rs //listofvessel,waypointandrouteobjects Require: NENs;NPOs;NEXs;EpsENs;EpsPOs;EpsEXs //clusteringparameters(seeAlgorithm 2) 1: forall message 2 messages do 2: if not(VsfMMSIg) then 3: //thevesselobjectidentiﬁedby MMSI doesnotexist:itisaddedtothe Vs list,itsstatusinitializedas‘sailing’, anentryeventgeneratedtobeanalyzedfor ENs objectsclusteringandtherouteslist Rs updated 4: Vs add(VsfMMSIg) 5: VsfMMSIg:status (‘sailing’) 6: VsfMMSIg:track (x;y;COG;SOG;timestamp;::: ) 7: [Rs;ENs;VsfMMSIg] Online WPs Clustering(ENs;VsfMMSIg;EpsENs;NENs) //see Algorithm 2 8: [Rs;VsfMMSIg] Route Objects Manager(Rs;VsfMMSIg) //(seeAlgorithm 3) 9: else 10: //thevesselexists:itsparametersareupdatedandtested 11: VsfMMSIg:track(end +1) (x;y;COG;SOG;timestamp;::: ) 12: VsfMMSIg:avg speed =pos=t //observedaveragespeedshownbythevessel 13: if VsfMMSIg:avg speed and v:status =(‘lost’) then 30: //thelastrecordedpositionofthevesselisusedtomodifythe EXs list,toupdatethelistofvesselwaypoints andtocreate/updatetheroutes, Rs 31: v:status (‘lost’) 32: [Rs;EXs;v] Online WPs Clustering(EXs;v;EpsEXs;NEXs)) 33: [Rs;v] Route Objects Manager(Rs;v) 34: endif 35: endfor 36: endif 37: endfor 38: return Vs;EXs;ENs;POs;Rs FromtheAISdatastream,thestatusofvesselobjectsisderivedandupdated.Changesofthestatus ofvesselobjectsareeventsofinterest,suchas“lost”whennotobservedforatime ,whichisa multipleofthemaximumAISmessagerefreshrateintheareaofinterest.Additionalvesselstatusesare “stationary”/“sailing”,andtheirtransitionsidentifyothereventsofinterest,suchaswhenthevesselstopsEntropy 2013, 15 2225 orstartssailingagainfromastoppage.Sucheventscreateorupdatewaypointobjects,WPs,asshownin AnnexA,Algorithm 1—UnsupervisedRouteExtraction—andAlgorithm 2—On-LineWPsClustering. Algorithm2 On lineWPsClustering Require: Vs;v //listofallvessels, Vs,andvessel, v,thatgeneratedtheeventofinteresttobeclustered Require: WPs;Rs //listofwaypointstobeclustered, i.e.,either ENs, EXs or POs,androutestobemodiﬁed Require: Eps;N //minimumnumberofpoints, N,inthe Eps neighborhoodoftheeventlocatedin v:track(end) thatis requiredtogenerateacluster wpn 2 WPs 1: [WPs;op] Incremental DBSCAN(WPs;v:track(end);N;Eps) //seeIncrementalDBSCANin[37]. 2: if op =‘none’ then 3: //theeventisnotclusteredandisconsideredasnoise 4: v:wps(end +1) (‘UnclassiﬁedWaypoint’;v:track(end)) 5: else 6: //theoperationperformedintheWPsspaceiseitherthegenerationofanewwaypoint,theabsorptionintoanexisting oneorthemergeofmultiplewaypoints: 7: if op =‘newcluster’ then 8: //theeventhascreatedanewcluster, wpn,thevessellistofwaypointsisupdatedtogetherwiththetime, timestampwpn,ofinformation,asextractedfrom v:track(end) 9: WPs add(‘WPn’) 10: v:wps(end +1) (‘WPn’) 11: v:timestampwp(end +1) (v:track(end)) 12: //inforegardingthe MMSI ofthevesselanditslastpositionisrecordedinto wpn 13: [wpn:List MMSIs(end +1);wpn:tracks(end +1)] (v:MMSI;v:track(end)) 14: endif 15: if op =‘clusterexpanded’ then 16: //theeventisabsorbedintothecluster, wpn: 17: v:wps(end +1) (‘WPn’) 18: v:timestampwp(end +1) (v:track(end)) 19: [wpn:List MMSIs(end +1);wpn:tracks(end +1)] (v:MMSI;v:track(end)) 20: endif 21: if op =‘clustersmerged’ then 22: //theneweventcausesthemergingoftwoclusters, wpm and wpn,into wpn,theeventisclustered, wpn updated and,ﬁnally, wpm deleted. 23: v:wps(end +1) (‘WPn’) 24: v:timestampwp(end +1) (v:track(end)) 25: wpn (v:MMSI;v:track(end)) 26: wpn merge(wpn;wpm) 27: forall ^ v 2 VsfMMSI = wpm:List MMSIsg do 28: ^ v:wps(^ v:wps =‘WPm’) (‘WPn’) 29: endfor 30: //mergetheaffectedroutesandupdatetherelevantlist 31: forall ^ R 2 (Rs:wps(1)=‘WPm’jRs:wps(2)=‘WPm’) do 32: ~ R (Rs:wps( ^ R:wps = ‘WPm’) =‘WPn’) 33: ~ R merge( ~ R; ^ R) 34: delete( ^ R) 35: endfor 36: delete(‘WPm’) 37: endif 38: endif 39: return WPs;v;Rs StationaryObjectsManager: Aspecialclassofwaypointsisrepresentedbystationarypoints,such asportsandoffshoreplatforms, POs.Thisclassofobjectsconsistsofvesselshavingaspeedlower thanagiventhreshold.Inparticular,ascanbeseeninAnnexA,Algorithm 1—UnsupervisedRoute Extraction—stationaryeventsaredetectedbyspeedgatingbasedonthelastobservationsrelatedtoEntropy 2013, 15 2226 thevesselofinterest:theparameters, t and pos (i.e.,thelastobservedtimeintervalandthe resultingdisplacementinposition),arecomputedtoempiricallyderivetheaveragevesselspeed.Thisis implemented,sincetheﬁeld, SOG,intheAISmessagesisunreliabletobeusedindetectingstationary events.Portandoffshoreplatformsarelearnedbyclusteringthestationarybehaviorofvessels,andtheir areasareprogressivelyshapedbyvesselsfollowingthesamebehavior.Waypointsclusteringisbased onDBSCAN(i.e.,Density-BasedSpatialClusteringofApplicationswithNoise)methodology([38]). DBSCANformsclustersofelementsonthebasisofthedensityofpointsintheirneighborhood.Inother words,givenaspeciﬁcpoint, p,ifthecardinalityoftheneighborhoodofagivenradius, Eps,isgreater thanacertainthresholdoftheminimumnumberofpoints,thensuchpointsaredensity-reachablefrom p andbelongtothesamecluster.Moreover,twopoints, p and q,aredensity-connectedifthereisa thirdpoint, o,suchthat p and q aredensity-reachablefrom o.Pointsthataredensity-connectedtoeach otherbelongtothesamecluster,andpointsthataredensity-connectedtoanypointoftheclusterarealso partofthecluster.Inthisframework,thosepointsthatarenotdensity-connectedtootherpointsdonot belongtoanyclusterandareconsiderednoise. Algorithm3 RouteObjectsManager Require: v, WPs (i.e.;ENs;EXs;POs), Rs 1: //ifthevesselhaspassedthroughatleasttwowaypoints 2: if length(v:wps) > 1 then 3: [wpa;wpb] v:wps(end 1: end) 4: if not(Rsfwpa to wpbg) then 5: //theroutefrom wpa to wpb doesnotexist:itisaddedtothe Rs list 6: Rs add(Rsfwpa to wpbg) 7: endif 8: //updatetherelevantroutebyaddingthetrackportionbetween wpa and wpb 9: timestampwpa = v:timestampwp(v:wps = wpa) 10: timestampwpb = v:timestampwp(v:wps = wpb) 11: Rsfwpa to wpbg:params(end +1) (v:track(timestamp 2 [timestampwpa ;timestampwpb ])) 12: //updatethevessellistofroutes 13: v:routes add(‘Rsfwpa to wpbg’) 14: endif 15: return v;Rs Differentlyfromcentroid-basedclustering,DBSCANdoesnotrequirethenumberofclusters apriori, whilearbitrarilyshapedclusterscanbeeasilyfoundasoftenobservedwithinthemaritimetrafﬁccontext. Forinstance,centroid-basedmethodscanfailindiscriminatingdifferentportswhosecentroidsareclose toeachother,whentheyarelocatedalongthecoastline,asshowninFigure 2.Moreover,DBSCAN introducesawaytoclassifynoisepoints,whichcanbeusedtodetectandﬁlteroutliers,aswillbe shownhereafter. Theon-linelearningenablesanincrementaldensity-basedclusteringofwaypoints.Thewaypoints clustersareeithercreated,expandedandmerged,followingthetypicalprocedureofincremental DBSCAN,asintroducedin[37].InAlgorithm 2,theon-lineclusteringof WPs isillustrated,showing howthevesselobjectfeaturesareupdatedaccordingly.Theclusterparameters(i.e.,theradius, Eps,of theneighborhoodoftheeventofinterestandtheminimumnumber, N,ofpointstobedetectedinthe Eps-neighborhoodofthevessel)aretuned,basedonthespeciﬁcnatureofthe WPs (i.e.,whetherthey are POs or ENs/EXs objects)andonthespeciﬁcfeaturesofthemonitoredarea.Entropy 2013, 15 2227 Topographically,portandoffshoreplatformobjectsarerepresentedviaaspatialdistributiongivenby thecoordinatesofthevessels,whichcontributetocreateorupdatethem.Asaconsequence,suchobjects areautomaticallydescribedviaalistofvesselobjectsandavolumeoftrafﬁc.Inthisway,afrequency plotbasedonthetypeofvesselscanbeassociatedtoeachportandoffshoreplatformobjectinorderto helpcharacterizetheactivitiesinthestopzones. Figure2. Stationarypoints(greendots)incrementallydetectedduringatwo-weekperiod overtheStraitofGibraltar,anareacharacterizedbyintensetrafﬁc.Stationarypointsarethen clusteredusingincrementalDensity-BasedSpatialClusteringofApplicationswithNoise (DBSCAN)intoportandoffshoreplatformobjects,whoseconcavehulls(right)consistently captureareaswherevesselsanchoroutsideports. EntryandExitPointsManager: Anotherclassofwaypointsusefulfordescribingthemotionpatterns withinaselectedareaisrepresentedbyentry(ENs)andexit(EXs)points.Wheneveravesselobject enters(leaves)theareaunderanalysis,itgenerates“birth”/“death”events(correspondingtovesselstatus transition“transmitting”/“lost”and viceversa),andtherelevantentry/exitpointiscreatedorupdated. Asinimageprocessingandvisualsurveillance(see,e.g.,[16]),entryandexitpointsarerelatedtothe monitoredsceneandmaychangedependingontheboundingboxarea,whileportoroffshoreplatform objectsareﬁxedreferencepoints.Similarlytothestationarypoints,entryandexitpointsarelearned throughtheincrementalDBSCANmethodanddescribedwithalistoftransitingvesselobjectsand avolumeoftrafﬁc.Algorithm 2—On-LineWPsClustering inAnnexAsummarizesthemainsteps. Figure 3 showstheresultsoftheunsupervisedwaypointsdetectionandcharacterizationovertheNorth AdriaticSea,wheremanyroutingsystemsarepresent(suchastrafﬁcseparationschemes),becauseof theintensetrafﬁcandoildrillingactivities. RouteObjectsManager: Oncethewaypointsarelearned,routeobjects, Rs,canbebuiltbyclustering theextractedvesselﬂows,whichconnecttwoports(i.e.,localroutes),anentrypointtoaport,aportand anexitpointoranentrypointandanexitpoint(i.e.,transitroutes).Routeobjectsdonotmerelycount theregisteredtransitingvessels,butarealsostatisticallydescribedbythestaticandkinematicfeatures ofthevesselsthatcreatedorupdatedthem. Speciﬁcally,theRouteObjectsManager,whosemainstepsarereportedinAlgorithm 3—Route ObjectsManagerinAnnexA—dealswiththecreationofnewrouteobjectsandwiththedynamicEntropy 2013, 15 2228 managementoftheirfeaturesandlabels,asresultingfromtheincrementalclusteringoftherelevant WPs describedinAlgorithm 2—On-LineWPsClustering,AnnexA. Figure3. Waypointsdetectionandcharacterizationovera 200 160 kmareaintheNorth AdriaticSea(a)fromMarch1toMay15,2012.Theunsupervisedanalysisleadstothe detectionofentry(cyan),exit(magenta)andstationaryareas(green)(b),oneofthem beinganoffshoreregasiﬁcationgatewayasconﬁrmedbytheshiptypedistributionanalysis (c),followingthecategorizationin[39],performedontheMaritimeMobileServiceIdentity (MMSI)listofregisteredvessels. Onceavesselentersthescene,itsfeaturesarecomparedwiththeexistingsetofroutes.Ifaroute alreadyexists,whosepositionalfeaturesarecompatibletothevesselfeatures,boththevesselisadded totheroutelistofvesselsand,mutually,therouteisaddedtothelistofthe WPs transitedbythevessel. Otherwise,thevesselcontributestotheinitializationofanewroute,and,whenaminimumnumber ofdetections(i.e.,numberoftransitsalongtheroute)isreached,thenewrouteisactivated.Each routeobjecthasaspatio-temporalsequenceofstatevectors,facilitatingtheanalysisandclassiﬁcation ofactivities.Thedetectedroutescanbeorganizedinhistoricalatlases,whichsummarizethemaritime trafﬁcintheconsideredarea.Asanexample,wereporttheroutecodebooklearnedintheNorthAdriatic SeainFigure 4.SomeofthederivedroutesarenoteasytoexplainbyglancingattheAIStrafﬁcmessages reportedinFigure 3b.Themethodologyshowsasigniﬁcantagreementwiththetrafﬁcschemesinuse onnauticalcharts. InFigure 5,anexampleoftworoutesextractedbetweentwodetectedstationaryareasintheStrait ofGibraltarisillustrated.Themajoreastandwestboundtrafﬁcvolumessigniﬁcantlyexceedthetrafﬁc ﬂowbetweentheselectedports,makingtheroutes’visualisolationdifﬁcult. Thetworoutesadheretothemaritimerulesoftheroadwhencrossingthemaintrafﬁcﬂows:the maintrafﬁcinthesamedirectionﬂowiscrossedatashallowangle(i.e., 20 –30 ),whiletheopposing trafﬁcﬂowineachrouteiscutacrossatbroadangles(i.e., 90 ).Thesecondportionofeachrouteis, therefore,morediffuse,astheferriesmaneuvermorewhencrossingtheopposingsealanescompared toovertakingtrafﬁcinthesamedirection.Theextractedroutes,whosenumberisnotassumed apriori, butautomaticallylearned,arecharacterizedalsobytheinformationoftheenteringandexitingtime oftheregisteredvesselstogetherwiththeirshiptype.Differentfromlivevideoanalysisapplications,Entropy 2013, 15 2229 thisallowstheextractionofhigherlevelinformation,suchastheshiptype,distributionoftheroute,its averagetraveltimeandthedaily/weeklypatterns,asshowninFigure 6. Figure4. SetofhighlydenseroutesintowhichthetrafﬁcinFigure 3 wasdecomposed. Anomaliesinthetrafﬁcschedulecanthereforebemodeledonvesselsthatarefullycompliantwith theroutedirections,butusethematlow-likelihoodtimes.Detectedrouteobjectsoftenshowtrajectories thatsharethesameenteringandexitingwaypoints,buttheirpathconsiderablydeviatesfromotherEntropy 2013, 15 2230 vesselpathswithinthesameroute.Itisnecessarytodiscardthoseoutliers,sothatanomalydetection canbeperformedbasedonamorerepresentativepictureofthevesselnormaltrafﬁc,asiscommonly doneinstatisticalprocesscontrolandchangedetectionpractice.Thus,anomalydetectionisrelated to,butdiffersfrom,noiseremovalinthedata:noiseworksasanobstructiontodataanalysisandis notofprimaryinteresttotheanalyst.Undesiredoutliersmustberemovedbeforefurtherknowledge exploitationcanbeperformed.Thispre-processingphaseisimplementedbyusingtheDBSCAN method.Speciﬁcally,itincludestheclassiﬁcationofroutepointsascorepoints,borderpointsand noisepoints.Noisepointsarenotconsideredrepresentativeofhistoricalpatternsandareﬁlteredout.An exampleofapre-processedrouteisreportedinFigure 7b.Ashighlightedin[8],vesselstypicallyfollow trafﬁcsealanesthataresequencesofstraightlines.TheGaussianMixtureModels(GMM),verypopular inthepatternrecognitionliterature,canbeusedtoﬁtthedistributionofpositiondatapoints.Alongthe minoraxisperpendiculartothelane,theGaussianmodelscancapturethevesselpositionvariabilityand displacements.However,alongthemajoraxis,thevesseldistributionisassumedtobeapproximately uniform,andthus,theGaussiandistributionisasub-optimalspatialdensitymodel.So,anon-parametric approachcanbemoreappropriatetomodelthetwo-dimensionaltrafﬁcdensitydistributionandhas beenadoptedinthepresentwork.Amongthenon-parametricapproaches,KernelDensityEstimation (KDE)isacommontechniqueforestimatingtheunknownprobabilitydensityfunction(pdf)ofthe randomvariable“vesselposition”.ComparedtoGMM,KDEmakesnoassumptionabouttheparametric modeloftheunderlyingpdf,whoseformisestimatedusinghistoricaldatasamples.Moreover,KDE doesnotneedtospecifythenumberofcomponentsofthemixturemodel,whichisoneofthemain drawbacksofGMM.Forthesereasons,KDEhasshownasuperiorabilitytoaccuratelymodeltrafﬁc lanes.Figure 7creportstheKDErepresentationofareﬁnedroute,adoptingaGaussiankernelwithan optimizedbandwidthselectionbasedontheMinimizationofaCostfunction. Figure5. AIStrafﬁcdatainproximityoftheStraitofGibraltar(left)collectedovertwo months,and(right)extractedroutesbetweenthelearnedportofTarifaandtheoldportof Tangier,bothhighlightedinred.Entropy 2013, 15 2231 TREADwastestedindifferentareasandusingdatafromdifferentAISsources(i.e.,terrestrialand satelliteAIS).Figure 8 showsanexampleofthetrafﬁcknowledgelearnedusingsatelliteAISdatainthe IndianOcean.ItisnoteworthythatsomeoftheroutesdisplayedinFigure8barenoteasilyanticipatedby simplylookingattherawAIStrafﬁcdatainFigure 8a.Asanexample,theroutefromtheSuezCanalto theLaccadiveSea(Figure 8c)isﬁrstlyconstrainedbytheInternationallyRecommendedTransitCorridor (IRTC)andeasilyisolated.Then,itbecomesmoredisperseoutsidetheroutingsystemandmoredifﬁcult tobeidentiﬁed.ThespatialspreadofthesecondrouteinFigure 8eshowshowtheeffectsofpiracyhave modiﬁedthecommonroutesovertheIndianOceannearSomalia,duetohigh-riskareas. Figure6. Dailypatternsbetweennorthbound(left)andsouthbound(right)routescovered byfourferrieswhoseschedulecanbederivedbythemultiplepeaksofthetimehistograms onthebottom. Figure7. Color-codedroutes(a)extractedovertheareainFigure 3,showingpatterns notclearlyvisiblebyanalyzingtrafﬁcdensitydata(seeFigure 3b);oneofthem(b)is highlighted,showinginredthepotentialoutliersdetectedandisolatedusingdensity-based clusteringontheroutepoints.TheKernelDensityEstimation(KDE)distributionforthe speciﬁcrouteisﬁnallycomputed(c). Atlast,eachroutecanbedecomposedintotheelementarytrajectoriesfollowedbyallthevessels belongingtothatroute,thusfacilitatingthesearchfortracksthatdeviatefrom“normality”.WhenaEntropy 2013, 15 2232 vesselobjectisinstantiated,itsfeaturesarecomparedwithalltheroutesalreadypresentinthedatabase performingRouteClassiﬁcation(seeSection 4.1). Figure8. Three-monthsatelliteAISpositioningdataovertheIndianOcean(a); superpositionofdetectedroutes(b).Twoofthemarefurtheranalyzedintermsofspatial (c and e)andtraveltimesdistribution(d and f). 3.1.LearningPerformanceandTrafﬁcEntropy ThelearningperformanceofTREADmethodologywasanalyzedintermsoftheratiobetweenthe numberofAISmessagesmappedintotheextractedsystemofroutesandthenumberofprocessed positioningmessages.Figure 9 showsthelearningresultson50-daygroundbaseddataovertheStrait ofGibraltarandtheNorthAdriaticSeaandsatellite-baseddataovertheIndianOceanasintroducedby Figures 3b, 5aand 8,respectively.Afteracommonpreliminaryphasewhenthesystemconstructsthe entry/exitandstationarypointobjects,thelearningaccuracyperformancestabilizesatdifferentlevels, dependingontrafﬁcdensityandconstraints.Thus,themorethetrafﬁcisconstrainedorregulated,the moreaccuratetheunsupervisedlearningresults.Theextremelyhightrafﬁcdensityandrigidrouting systemallowedtheStraitofGibraltartobelearnedrelativelyquicklyandconsistently,capturingupto 95%oftheprocessedmessages.LoweraccuracyperformancecanbeseenintheNorthAdriaticSea, where,despitetherelativelyconstrainedtrafﬁc,thereareopportunitiesformanyroutestobefollowed withinthetimewindow.Asaresult,only70%ofthetrafﬁcislearned.Thisaspectisevenmore pronouncedintheIndianOcean,wheremerely40%ofthetrafﬁccanbeclustered,duetoalackoftrafﬁc constraintsoveralargeareacombinedwiththelowupdateratesofsatellite-basedAISdata.Entropy 2013, 15 2233 ThecurvesinFigure 9 representtheportionoftheinformationthatcontributestothehistoricaltrafﬁc patternmodel versus theamountofprocessedinformation.Theamountofinformationthatdoesnot contributetothetrafﬁcknowledgediscoveryisdiscarded.Thereisacertainpointofdiminishingreturns, oranupperthreshold,forthenumberofdatapoints,whichareincludedintothelearnedsystemofroutes, beyondwhichtheadditionaldatadonotprovidefurtherusefulinformationtothehistoricalroutesystem. Thetrafﬁcpatternknowledgediscoveryprocesscanthereforebelinkedtothenotionofentropy,which measuresthedegreeofdisorderinasystem.InformationTheoryentropyiswidelyemployedtopredict humanmobility,AsynchronousTransferMode(ATM)trafﬁcstreamsandcellularnetworktrafﬁc[40]. Entropyclearlyprovidesameasureoftheextenttowhichthetrafﬁccanbepredictedonthebasisofthe historicalpatternsoverthearea.Withinthisframework,entropycanbeusedtoquantifytheinformation gainthatthederivedtrafﬁcpatternswillprovideforprediction[41].Ingeographicalclusteringstudies, thenotionofentropyhasbeensuggestedin[42]andrecentlyappliedtodetectabnormalactivitiesin videosurveillancein[43].Asaconsequence,thedetectionofpotentialanomaliescanbelinkedtothe trafﬁcentropy:thecapabilitytosuccessfullyrecognizelow-likelihoodbehaviorsisenhancedinareas wherethetrafﬁcpatternsarehighlyregularand,therefore,theassociatedlevelofdisorderislow. Figure9. PortionofAISmessagescapturedbythelearnedsystemofroutesoverthereported areasofinterest. Thus,whilethelearningratedependsonthetrafﬁcdensity,theendstateknowledgediscovery performanceisaffectedbythedifferentlevelsoftrafﬁcentropyovertheareaofinterestandwillvary fromregiontoregion.Entropy 2013, 15 2234 4.RoutesKnowledgeExploitation Similarlyto[12,15],oncethepictureofthemaritimetrafﬁcisconstructed,thehistoricalknowledge canbeusedto(i)classifytheroutes,assigningtoeachofthemaprobabilitythatthevesselisactually followingit,(ii)predictthefutureroutealongwhichavesselisgoingtomove,inagreementwiththe partiallyobservedtrackandgiventhevesselstaticinformationand(iii)detectanomalousbehaviorsthat deviatefromthelearnedtrafﬁcnormality. 4.1.RouteClassiﬁcation Classifyingasetofvesselpositioningobservationsintospeciﬁcroutesiscrucialforaugmentingthe situationalawarenessoverthemaritimetrafﬁcarea.Routeclassiﬁcationassignsaprobabilitytoeach routecompatibletothevesselposition.Thisisexpressedastheposteriorprobabilitythatthevessel belongstothatspeciﬁcroute,havingobservedapartialvesseltrack.Generallyspeaking,avesseltrack, V,isatimeseriesof T observedstatevectors, vi: V = fv1; v2;:::; vT g (1) wherethestatevectorobservation, vt,isdirectlyisolatedfromthebroadcastAISinformation.Inthis study,itincludesbothpositionandvelocityinformationasextractedbythevesseltrackproperties, v:track (seeSection 3): vt =[xt;yt; _ xt; _ yt] | (2) where xt and yt arerelatedtothevesselcoordinatesandthevelocitycomponents, _ xt and _ yt,are derivedbycombiningSOGandCOGinformation,basedontheconditions:SOGt = p_ x2 t +_ y2 t and COGt = tan 1 _ yt _ xt Thevesseltrack, V,canbeassociatedtoatimeseriesofregions, S = fs1; s2;:::; sT g,spatially identiﬁedbycirclesofradius d centeredintheobservedpositions, [xt;yt],whichrepresentthetemporal sequenceofstatesandtakeintoaccountthetimelags, t,betweensubsequentobservations.Thespatial regionidentiﬁedbythe t th state, st,asfurtherdiscussedhereafter,canbeusedasamasktocapture therouteelementsintheneighborhoodoftheobservation, vt,subsequentlyusedtocharacterizethelocal routebehavior.Itisclearthattheselectionofthedistance, d,and,therefore,thesizeofthestateregions, affecttherouteclassiﬁcationeffectiveness:if d istoosmall,thecharacterizationofthelocalroute behaviorwouldbebasedonareducednumberofneighbors,leadingtopoorgeneralizationcapabilities. Similarly,if d istoolarge,thecharacterizationwouldbebiasedbythemixingofdifferentbehaviors (e.g.,asinthecaseofnon-rectilinearroutes).ThisisillustratedbyFigure 10. Ithasbeenfoundthatstateregionswitharadius d intheorderofafewnauticalmilesleadto acceptableclassiﬁcationresultsindependentlyoftheroutespatialanddirectionaldispersion.Entropy 2013, 15 2235 EachAISmessagecanbedecodedtoderivethevesseltype, c,accordingtothecategorization in[39].Theclassiﬁcationproblemliesinﬁndingtheroute, Rk c ,thatmaximizestheposteriorprobability, P(Rk c jV; S),overthe k =1;:::;K possiblecompatibleroutes Rk c 2 Rs (seeSection 3): Rk c =argmax k P(Rk c jV; S) (3) where,followingtheBayesrule, P(Rk c jV; S),canbedecomposedasfollows: P(Rk c jV; S) / P(V; SjRk c )P(Rk c ) (4) Figure10. Exampleofobservedvesseltrack, fvt 2; vt 1; vtg (red),associatedtemporalstate sequence, fst 2; st 1; stg (circles)andpoints(blue)ofacompatibleroute,asresultingfrom thetrafﬁcknowledgediscoveryprocess.Iftheselectedradiusistoolarge(e.g., d0 >d), distinctlocaldirectionaldistributionscanbeincludedintothesamestate,biasingthe motioncharacterizationoftherelevantobservationneighborhoodand,thus,theroute classiﬁcationprocess. Theprior P(Rk c ) canbeempiricallyevaluatedastheratioofthenumberofvesselsthattransited alongtheroute, Rk c ,overthetotalnumberofvesselsdetectedintheareaofinterest.Thelikelihood, P(V; SjRk c ),accountsforthejointprobabilityofthetimeseries, V,oftheobservationsandthesequence ofthestates, S,comparedtotheroute, Rk c . SimilarlytotheprobabilisticapproachintheHiddenMarkovModel(HMM)literature[44]andinthe spatio-temporaltrajectoryminingliterature(see,e.g.,[45,46]),thejointprobability, P(V; SjRk c ),ofthe vesseltrack, V,andstatessequence, S,giventheroute, Rk c ,canbewrittenasfollows: P(V; SjRk c )= P(Vj S;Rk c )P( SjRk c ) (5) thesequenceofstates, S,beingﬁxed,oncethetracksequence, V,hasbeenobserved.Similarinteresting examplescanbefoundinsignalprocessing[47],videotracking[15]andmaritimesurveillance applications[48]. Theprobability, P(Vj S;Rk c ),oftheobservationsequence, V,forthestatesequence, S,giventhe route, Rk c ,canbeexpressedasfollows: P(Vj S;Rk c )= T Y t=1 P(vtjst;Rk c ) (6)Entropy 2013, 15 2236 InEquation(6),theprobabilityofobservingafeaturevector, vt,inonestate, st,isassumedto beindependentofthefeaturevectorsinotherstates.Thisisanapproximation,sincethefeature vectorsofthetrack, V,arerelatedtothesamevesseland,hence,areinterdependent.Nevertheless, thisapproximationhasbeenadoptedelsewhere(see,e.g.,[47])withsatisfyingresults.Thegeneric P(vtjst;Rk c ) istheprobabilityofobservingthefeaturevector, vt,giventheelements, fRk c (`):[x;y; _ x; _ y]g, oftheroute, Rk c ,withinthestateregion, st,deﬁnedasfollows: fRk c (`):[x;y; _ x; _ y]g where kRk c (l):[x;y] [xt;yt]k d; 8l 2 ` (7) Theprobability, P(vtjst;Rk c ),iscalculatedas: P(vtjst;Rk c )= P(xt;yt; _ xt; _ ytjst;Rk c )= P(_ xt; _ ytjxt;yt; st;Rk c )P(xt;ytjst;Rk c ) (8) where P(_ xt; _ ytjxt;yt; st;Rk c ) istheprobabilityofobservingthevelocitycomponents, _ xt and _ yt,within thestate, st,asidentiﬁedbytheneighborsofthecurrentposition, [xt;yt],withinadistance, d.This conditionalprobabilitytakesintoaccountthevelocitydependencyontheareawherethevesselisactually observed.Inotherwords,thiscomponenttellsustheextenttowhichthevesselvelocityvectorisinline withthehistoricalspeedanddirectionlocalfrequencydistributions,giventheroute, Rk c .Giventhat thestate, st,isidentiﬁedbytheobservedposition, [xt;yt],theprobability, P(_ xt; _ ytjxt;yt; st;Rk c ),can besimpliﬁedas P(_ xt; _ ytjst;Rk c ).Both P(_ xt; _ ytjst;Rk c ) and P(xt;ytjst;Rk c ) canbeestimatedusing,e.g., non-parametricmethods,suchastheKernelDensityEstimator,asdiscussedinSection 3. TheotherterminEquation(5)istheprobability, P( SjRk c ),ofthestatesequence, S,giventheroute, Rk c ,andcanbedecomposedasfollows: P( SjRk c ) / P(s2js1;Rk c )P(s3js2;Rk c ) :::P(sT jsT 1;Rk c ) (9) wheretheproportionalityfollowsfromtheassumptionthattheinitialstateprobability, P(s1jRk c ),is equalforallthepossiblestatesequencesin Rk c .Inotherwords,thesequenceisequallyprobableto startatanypointoftheroute.TheEquation(9)accountsforthecompatibilityofthestatesequence, fst 1; stg,totheroute, Rk c ,andtakesintoaccountthehighvariabilityofAISrefreshrates,asdiscussed inSection 3.Thiscanbeestimatedasafunctionofthedistance, p,betweentheobservedposition, [xt;yt] (whichisthecenteroftheneighborhood st),andthepredictedposition, [^ xt; ^ yt],calculatedby propagating [xt 1;yt 1] tothecurrenttime, t,giventhevelocitydistributionalongtheroute, Rk c ,as describedinthetrackpredictorinAlgorithm 4—TrackPredictor(containedinAnnexA)—where de is theceilingfunctionand t isaroughtimeincrementbetweentwopositions.Thetimeincrementcanbe convenientlychosen,dependingonthecomplexityoftheroute(see[32]).Thedistance, p,canbeused toestimatethelikelihoodofobservingthestate, st,giventhepreviousstate, st 1,andtheroute, Rk c . p canberegardedasarandomvariabledescribingthepredictionerror, i.e.,thedisplacementofthecurrent observedposition,withrespecttotheexpectedone,givenatimelag, t,betweentheobservations andacompatibleroute, Rk c .Thus,thedistance, p,isultimatelycalculatedastheEuclideandistance, p = k[xt;yt] [^ xt; ^ yt]k,sincemostobserveddistancesaregenerallybeloweightnauticalmiles,witha reducedcurvatureeffect.Entropy 2013, 15 2237 Algorithm4 TrackPredictor Require: Rk c , [xt 1;yt 1], timestampt, timestampt 1, stept, Eps 1: t (timestampt timestampt 1) 2: (t)=d(t)=stepte 3: for = timestampt 1 to timestampt step do 4: ﬁnd ` s.t. 8l 2 ` : kRk c (l):[x;y] [x ;y ]k Eps 5: s fRk c (`):[x;y; _ x; _ y]g 6: [_ xs ; _ ys ] median (s :[_ x; _ y]) 7: [x+1;y+1] [x ;y ]+[_ xs ; _ ys ] 8: endfor 9: return [^ xt; ^ yt] Inordertoinvestigatethevariabilityof p,aparametricmodelhasbeenselectedfromthe literatureandanalyzed.Typically,survivaldistributionsareusedtoestimatetime-to-event.These functionsareappropriate,becausetheradialdistance-to-eventcanberegardedasanalogousto time-to-event.Exponential-likemodelsshowgoodnessofﬁtandalsoconformwithsomerelated literature(see,e.g.,[12,49,50]).Amongthem,theWeibullmodelhasbeenselected,sinceitshows goodcorrelationwiththeempiricaldistributionsoftheobserveddistancesonrealAISdatastreamsin differentareas.Asaresult,thetransitionprobability, P(stjst 1;Rk c ),can,then,beexpressedasfollows: P(stjst 1;Rk c )=exp " p k k # (10) Theshapeparameter, k,basicallydoesnotchangewithtime,whilethescaleparameter, k,is assumedtodependonthetimewindow, t,betweentwosubsequentobservationsasfollows: k = mkt (11) for t > 0.So,theexpectedvaluefortherandomvariable, p,is: E fpg = k 1+ 1 k (12) andthevarianceisequalto: Var fpg = 2 k 1+ 2 k (E fpg) 2 (13) where istheGammafunction.DuetoEquation(11),thevarianceincreaseswith 2 t ,accounting forthegrowthofuncertaintyrelatedtothepropagationmodelinlong-termprediction,astypicalof diffusionmodels. Theestimates, ^ k and ^ k,areobtainedusingthesampleddistancesbetweenthepredictedpoints, [^ xt; ^ yt],andtheactualobservedpoints, [xt;yt],inthespeciﬁedroute, Rk c ,foreachgiventimelag, t, usingMaximumLikelihoodmethods(see,e.g.,[51]). Fromthisstartingpoint,apracticalestimate, ^ mk,canbeobtainedstraightforwardlyviaalinear regressionforeachroute, Rk c .ThenEquation(10)becomes: P(stjst 1;Rk c )=exp " p ^ mk t ^ k # (14)Entropy 2013, 15 2238 for t > 0.Inthisway,aconsistenttransitionprobabilityfortheconsideredlikelihoodestimation problemisobtained.TwodesiredbehaviorsareincorporatedinEquation(14).Thus,givenatimelag, t, P(stjst 1;Rk c ) decaysasthepositioningdistance, p,increases.Conversely,givenadistance, p, P(stjst 1;Rk c ) increasesasthetimelag, t,increases.Figure 11 showsanexampleoftheanalysis startingfromtherealstreamofAISdataintheNorthAdriaticSeaarea(seeFigure 3). 4.2.RoutePrediction Whenobservingasequenceofstatevectorsforavesselofagiventype, c,therouteclassiﬁcation assignsaprobabilitytoeachcompatibleroute,basedontheposteriorprobability(4)thatthevessel belongstothatroute.Inotherwords,giventhelateststatevectorsequenceforavesselandatime window, t,thefuturepositionofthevessel,bothinasingleandmulti-stepmode,canbepredicted followingAlgorithm 4. Figure11. Estimationoftransitionprobabilities:Empirical(solidblueline)andﬁtted Weibull-like(dashedredline)distributionsofthedistances, p,innauticalmilesbetween thepredictedandactualpositionsofvesselsintheNorthAdriaticSeaAreaanalyzedin Figure 3.Thetimelag, t,rangesfromﬁveto60minutes,withanincrementofﬁveminutes. Theﬁgureshowshowtoderivethetransitionprobability, P(stjst 1;Rk c ),fromthedistance betweenthenewobservation, [xt;yt],andthepredictedposition, [^ xt; ^ yt],giventhe Rk c and thepreviousobservation, [xt 1;yt 1].Thisgivesameasureofmatchbetweentherouteand theobservedstatesequence. Assumingthatnoanomalieswillbeobservedforthevesselsofinterest,theroutepredictionis essentiallyapplyingcontext-basedtrackingalgorithms.Inotherwords,themeanvelocitydirection togetherwiththeseriesofroutepointsprovidedbypreviousvesselsrepresentasetofconstraints thatcanbeusedtoefﬁcientlypredictfuturevesselspositions,basedonstaticstoredinformation, suchasthevesseltype.Inthiscase,theinferenceisdrivenbythelearnedroutecodebookandby thetopmostprobableroutescomputedusingEquation(6).Figure 12 showsanexampleofrouteEntropy 2013, 15 2239 prediction.InFigure 12a,agivenvesselentersthesceneintheright-bottomcornerandismonitored inthreesubsequenttimeframes, T1, T2 and T3.Ineachtimeframe,atracksegmentoftheﬁve mostrecentstatevectorsisobserved.Basedontheseﬁveobservedvalues,themethodologyisable toprovideaprobabilisticpredictionofthevesselﬁnalpositionafteragivenamountoftime,using thehistoricalcontextualinformation.Fortheconsideredvessel,thereareinitiallyﬁvecompatible routes:thereportedpercentagesrepresenttheprobabilitythatthevesselisexpectedtomovealong eachroutebasedontherouteclassiﬁcationprocess.InFigure 12b,sevenhoursaheadfromthelatest observation,thepredictedpositions,obtainedfollowingAlgorithm 4,areshown,togetherwiththe associatedprobabilities,computedasinSection 4.1.InFigure 12c,weseethatinthenexttimeframe (threehoursafterward),theprobabilitiesareupdatedtoreﬂectthereducednumberofdestinationoptions. Figure12. Vesseldestinationpredictiongiventhesetofcompatibleroutes(a)atthree differenttime-frames(b, c and d).Theprobabilityofvessellocationiscomputedbased onEquation(6)andconditionedtothedistributionofvesseltypeswithineachroute.It canbeseenthattheextractedroutesprovideenoughinformationtoconsistentlypredictthe vesselpositionhoursahead,eveninrelativelycomplexroutingsystems.Entropy 2013, 15 2240 InFigure 12d,theprobabilitiesthatthevesselwouldturneitherWestorNorthhasbecomenegligible, andthemostprobableportturnsouttobetheactualdestinationofthevessel.Itisinterestingtonote thatthecomputationofthepredictionprobabilitieshasincludedthevesseltypecharacterization.Such contextualinformationresultedinenhancedpredictionperformance. 4.3.AnomalyDetection Thedetectionofananomaly, H1,attime, t,canbethoughtofasdeviationfromthenormality, H0, learnedusinghistoricaldataandcanbeapproachedbysettingaminimumthresholdinEquation(15), accordingtothedetectionandfalsealarmratesrequiredbythespeciﬁcsurveillanceapplication: argmax k P(V; SjRk c )P(Rk c ) H1 Q H0 Th (15) where V istheobservedtrackfortheVesselOfInterest(VOI)and S isthecorrespondingtemporal statesequence.Inordertoavoidproblemsderivingfromincompleteorintermittenttracks,theanomaly detectionisperformedon-line,usingaslidingtimewindow,whichcapturesonlythemostrecentpoints ofthepartiallyobservedtrack.Thus,theposteriorprobabilityofobserving V,giventhetrafﬁchistory inthearea,isincrementallycalculatedassoonasanewobservationisreceived. Figure13. Posteriorprobabilityoftheobservedtrackforthemonitoredvesselofinterest. ThevesselstartsfromPortofLivorno(greendots)andexitstheareaintheexitpoint (magenta),aftermakingananomalousdoubleU-turn.Entropy 2013, 15 2241 Figure 13 exempliﬁessuchasequentialanalysis.ThemonitoredsceneisinfrontofthePortof Livorno,intheLigurianSeaarea.Avesselshowsananomalousbehavior,whichiscorrectlydetectedby theproposedmethodology.Thevesselinitiallymoveswestward,inaccordancewiththemotionpattern ofthecompatibleroute,resultingfromtheclassiﬁcation.Thecompatiblehistoricalrouteisshownwith grayarrows.Whilethevesselsailsthearea,theprobabilityofitsstatevectorissequentiallyupdated basedonEquation(6).Thetrajectoryofthevesselisrepresentedwithasequenceofarrowswhosehead markercolordependsontheincrementalposteriorprobabilitycalculatedwithagiven-widthbackward timewindow.Thevesselinitiallymoveswithinthenormalroute,andbothitspositionandmotionare compatiblewiththehistoricalpatters.Itstrackedpositionsareshownbythebluedots.Then,thevessel startsheadingeastwardandmakesadoubleU-turn:thepositionalfeaturesarestillcompatible,sincethe vesselismovinginsidetheroutearea,buttheposteriorprobabilitydecaysdramatically,duetothevessel headingandvelocity,whichareincompatiblewiththehistoricalpatterns.Thetransitionprobabilities accountforthismotionincompatibility.Thereddotshighlighttheanomalousbehaviorandchange againintoblueafterthevesselre-entersthenormalmotionﬂowoftheroute. 5.Conclusions Thelargeamountofshipmovementdatacollectedbyterrestrialnetworksandsatelliteconstellations ofAISreceiversrequirestheaidofautomaticprocessingtechniquesifthedataaretobefullyutilized. TheTREADmethodologyderivesknowledgeofmaritimetrafﬁcinanunsupervisedway,inorderto detectlow-likelihoodbehaviorsandtopredictvesselsfuturepositions. Thelearningprocessisrobustwithrespecttodifferentnumberofsensors,theircoverageandrefresh rateandthescaleoftheareaofinterest.Thetrafﬁcrouteextractionprocessisbasedonincremental learningandcanbeappliedbothinreal-timeorbatchfashion. Inthisresearchwork,vesselsareanalyzedasacollectiveentitythatconstructsandshapesthetrafﬁc patternsovertheareaofinterest.Theresultinglow-likelihoodbehaviordetectioncanoftenbefully explainedthroughtheinteractionbetweenobjects.Forexample,asuddenchangeincourseorspeedcan beduetocollisionavoidancemaneuverwithrespecttoanothervesseloranintenttodelaythetransit toarriveatapre-arrangedtime.Thislevelofinteraction,iftakenintoaccount,canhelpimprovethe interpretationofvesselbehaviorandintent. Acknowledgments ThisworkrelatestoDepartmentoftheNavyGrantN62909-11-1-7040issuedbyOfﬁceofNaval ResearchGlobal.TheauthorswishtoexpressthankstoRonFunkandtoalltheMSAteamatCMRE forthehelpfuldiscussionsandinsights.Theauthorsalsowishtothankthereviewersforthevaluable commentsandsuggestions.Entropy 2013, 15 2242 References 1. Cimino,G.;Ancieri,G.;Horn,S.;Bryan,K. SensorDataManagementtoAchieveInformation SuperiorityinMaritimeSituationalAwareness;CMREFormalReport,NATOUnclassiﬁed; NATO:Brussels,Belgium,2013;inpress. 2. InternationalConventionfortheSafetyofLifeatSea(SOLAS),ChapterV:SafetyofNavigation, Regulation19,13December2002. 3. CommissionoftheEuropeanCommunities. CommonpositionadoptedbytheCouncilwitha viewtotheadoptionofaDirectiveoftheEuropeanParliamentandoftheCouncilamending Directive2002/59/ECestablishingaCommunityvesseltrafﬁcmonitoringandinformationsystem, DocumentCOM2008310ﬁnal–2005/0239COD;Brussels,Belgium,11June2008;Available online:http://eur-lex.europa.eu/LexUriServ/LexUriServ.do?uri=COM:2008:0310:FIN:EN:pdf (accessedon30May2013). 4. Baldauf,M.;Benedict,K.;Motz,F.Aspectsoftechnicalreliabilityofnavigationsystemsand humanelementincaseofcollisionavoidance.InProceedingsoftheNavigationConferenceand Exhibition,London,UK,28–30October2008;pp.1–11. 5. Høye,G.K.;Eriksen,T.;Meland,B.J.;Narheim,B.T.Space-basedAISforglobalmaritimetrafﬁc monitoring. ActaAstronaut. 2008, 62,240–245. 6. Hall,D.L.;Llinas,J.Anintroductiontomultisensordatafusion. Proc.IEEE 1997, 85,6–23. 7. Roy,J.AnomalyDetectionintheMaritimeDomain.InProceedingsofSPIE:OpticsandPhotonics inGlobalHomelandSecurityIV,Orlando,FL,USA,16March2008;Halvorson,C.S.,Lehrfeld, D.,Saito,T.,Eds.;Volume6945. 8. Laxhammar,R.AnomalyDetectioninTrajectoryDataforSurveillanceApplications.Ph.D.Thesis, ¨ OrebroUniversity, ¨ Orebro,Sweden.2011. 9. Hansen,J.;Jacobs,G.;Hsu,L.;Dykes,J.;Dastugue,J.;Allard,R.;Barron,C.;Lalejini,D.; Abramson,M.;Russell,S. etal.Informationdomination:DynamicallycouplingMETOCand INTELforimprovedguidanceforpiracyinterdiction. 2011NRLReview 2011,110–119. 10. Vespe,M.;Sciotti,M.;Burro,F.;Battistello,G.;Sorge,S.Maritimemulti-sensordataassociation basedongeographicandnavigationalknowledge.InProceedingsofIEEERadarConference RADAR08,Rome,Italy,26-30May2008;pp.1–6. 11. Gini,F.;Rangaswamy,M. KnowledgeBasedRadarDetection,TrackingandClassiﬁcation; Wiley:Hoboken,NJ,USA,2008. 12. Hu,W.;Xiao,X.;Fu,Z.;Xie,D.;Tan,T.;Maybank,S.Asystemforlearningstatisticalmotion patterns. IEEETrans.PatternAnal.Mach.Intell. 2006, 28,1450–1464. 13. Stauffer,C.;Grimson,W.E.L.Learningpatternsofactivityusingreal-timetracking. IEEETrans. PatternAnal.Mach.Intell. 2000, 22,747–757. 14. Morris,B.T.;Trivedi,M.M.Asurveyofvision-basedtrajectorylearningandanalysisfor surveillance. IEEETrans.CircuitsSyst.VideoTechnol. 2008, 18,1114–1127. 15. Morris,B.T.;Trivedi,M.M.Trajectorylearningforactivityunderstanding:Unsupervised, multilevel,andlong-termadaptiveapproach. IEEETrans.PatternAnal.Mach.Intell. 2011, 33,2287–2301.Entropy 2013, 15 2243 16. Makris,D.;Ellis,T.Learningsemanticscenemodelsfromobservingactivityinvisualsurveillance. IEEETrans.Syst.ManCybern.PartBCybern. 2005, 35,397–408. 17. Lane,R.O.;Copsey,K.D.Trackanomalydetectionwithrhythmoflifeandbulkactivitymodelling. InProceedingsof15thConferenceonInformationFusion,Singapore,Singapore,9–12July 2012; pp.24–31. 18. Seibert,M.;Rhodes,B.J.;Bomberger,N.A.;Beane,P.O.;Sroka,J.J.;Kogel,W.;Kreamer,W.; Stauffer,C.;Kirschner,L.;Chalom,E.; etal.SeeCoastportsurveillance.InProceedingsofSPIE: PhotonicsforPortandHarborSecurityII,Orlando,FL,USA,18–19April2006;Volume6204. 19. Willems,N.;Wetering,H.V.D.;Wijk,J.J.V.Visualizationofvesselmovements. Comput.Graph. Forum 2009,28,959–966. 20. Riveiro,M.VisualAnalyticsforMaritimeAnomalyDetection,Ph.D.Thesis, ¨ OrebroUniversity, ¨ Orebro,Sweden.2011. 21. Kraiman,J.B.;Arouh,S.L.;Webb,M.L.Automatedanomalydetectionprocessor.InProceedings ofSPIE:EnablingTechnologiesforSimulationScienceVI,Orlando,FL,USA,1April2001;Sisti, A.F.,Trevisani,D.A.,Eds.;pp.128–137. 22. Bomberger,N.A.;Rhodes,B.J.;Seibert,M.;Waxman,A.M.Associativelearningofvesselmotion patternsformaritimesituationawareness.InProceedingsof9thInternationalConferenceon InformationFusion,Florence,Italy,10–13July2006;pp.1–8. 23. George,J.;Crassidis,J.;Singh,T.;Fosbury,A.M.Anomalydetectionusingcontext-aidedtarget tracking. J.Adv.Inf.Fusion 2011,6,39–56. 24. Nevell,D.Anomalydetectioninwhiteshipping.InProceedingsof2ndIMAConferenceon MathematicsinDefence,Farnborough,UK,19November2009;pp.1–7. 25. Lane,R.O.;Nevell,D.A.;Hayward,S.D.;Beaney,T.W.Maritimeanomalydetectionandthreat assessment.InProceedingsof13thConferenceonInformationFusion,Edinburgh,UK,26–29 July2010;pp.1–8. 26. Vespe,M.;Bryan,K.;Braca,P.;Visentini,I.Unsupervisedlearningofmaritimetrafﬁcpatterns foranomalydetection.InProceedingsof9thIETDataFusionandTargetTrackingConference, London,UK,16–17May2012;pp.1–5. 27. Vespe,M.;Pallotta,G.;Visentini,I.;Bryan,K.;Braca,P.Maritimeanomalydetectionbasedon historicaltrajectorymining.InProceedingsoftheNATOPortandRegionalMaritimeSecurity Symposium,Lerici,Italy,21–23May2012;pp.1–11. 28. Laxhammar,R.;Falkman,G.;Sviestins,E.Anomalydetectioninseatrafﬁc:Acomparisonof Gaussianmixturemodelandkerneldensityestimator.InProceedingsof12thConferenceon InformationFusion,Seattle,WA,USA,6–9July2009;pp.756–763. 29. Will,J.;Claxton,C.;Peel,L.FastmaritimeanomalydetectionusingKD-treeGaussianprocesses. InProceedings2ndIMAConferenceonMathsinDefence,Shrivenham,UK,20October2011. 30. Kowalska,K.;Peel,L.MaritimeanomalydetectionusingGaussianprocessactivelearning. InProceedingsof15thConferenceonInformationFusion,Singapore,Singapore,9–12July2012; pp.1164–1171.Entropy 2013, 15 2244 31. Smith,M.;Reece,S.;Roberts,S.Rezek,I.OnlinemaritimeabnormalitydetectionusingGaussian processandextremevaluetheory.InProceedingsofIEEE12thInternationalConferenceonData Mining(ICDM).Brussels,Belgium10–13December2012;pp.645–654. 32. Ristic,B.;LaScala,B.;Morelande,M.;Gordon,N.StatisticalanalysisofmotionpatternsinAIS data:Anomalydetectionandmotionprediction.InProceedingsof11thConferenceonInformation Fusion,Cologne,Germany,June30–July32008;pp.40–46. 33. Pallotta,G.;Vespe,M.;Bryan,K. TrafﬁcRouteExtractionandAnomalyDetection(TREAD): VesselPatternKnowledgeDiscoveryandExploitationforMaritimeSituationalAwareness;NATO FormalReportCMRE-FR-2013-001,NATOUnclassiﬁed;NATO:Brussels,Belgium,2013. 34. TechnicalcharacteristicsforanautomaticidentiﬁcationsystemusingTDMAintheVHF maritimemobileband,RecommendationITU-RM.1371-4.2010.Availableonline: http://www.itu.int/rec/R-REC-M.1371/en(accessedonline30May2013). 35. Guerriero,M.;Coraluppi,S.;Carthel,C. AnalysisofAISIntermittencyandVesselCharacterization UsingaHiddenMarkovModel;NURC-FR-2010-002,NATOUnclassiﬁed;NATO:Brussels, Belgium,2010. 36. Performancetestprocedures,methodology,datasources,qualityofacquiredAISspacebornedata. EuropeanCommission-DGMARE,Pasta-MareProject,TechnicalNoteTN5.2010.Availabel online:https://webgate.ec.europa.eu/maritimeforum/system/ﬁles/6039r%20PASTA%20MARE LXS TN-005 Performance%20Test%20procedure Issue2 0.pdf(accessedonline30May2013). 37. Ester,M.;Kriegel,H.;Sander,J.;Wimmer,M.;Xu,X.Incrementalclusteringformininginadata warehousingenvironment.InProceedingsofthe24thInternationalConferenceonVeryLargeData Bases,NewYork,NY,USA,24–27August1998;pp.323–333. 38. Ester,M.;Kriegel,H.;Sander,J.;Xu,X.Adensity-basedalgorithmfordiscoveringclustersinlarge spatialdatabaseswithnoise.InProceedingsofSecondInternationalConferenceonKnowledge DiscoveryandDataMining,Portland,OR,USA,2–4August1996;pp.226–231. 39. Categorizationandlistingofnoxiousliquidsubstancesandothersubstances,International ConventionforthePreventionofPollutionFromShips,1973asmodiﬁedbytheProtocolof1978 (MARPOL73/78),AnnexII,Chapter2,Regulation6. 40. Riihijarvi,J.;Wellens,M.;Mahonen,P.Measuringcomplexityandpredictabilityinnetworkswith multi-scaleentropyanalysis.InProceedingofIEEEconferenceINFOCOM,RiodeJaneiro,Brazil, 19–25April2009;pp.1107–1115. 41. Zhou,X.;Zhao,Z.;Li,R.;Zhou,L.;Zhang,H.Thepredictabilityofcellularnetworkstrafﬁc. InProceedingsoftheInternationalSymposiumonCommunicationsandInformationTechnologies (ISCIT),GoldCoast,Queensland,Australia,2–5October2012;pp.973–978. 42. Batty,M.Spatialentropy. Geogr.Anal. 1974,6,1–31. 43. Sharif,H.;Djeraba,D.Anentropyapproachforabnormalactivitiesdetectioninvideostreams. PatternRecogn. 2012, 45,2543–2561. 44. Rabiner,L.R.AtutorialonhiddenMarkovmodelsandselectedapplicationsinspeechrecognition. Proc.IEEE 1989, 77,257–285.Entropy 2013, 15 2245 45. Giannotti,F.;Nanni,M.;Pinelli,F.;Pedreschi,D.;Axiak,M.Trajectorypatternmining. InProceedingsofthe13thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryand DataMining,SanJose,CA,US,12–15August2007;pp.330–339. 46. Emrich,T.;Kriegel,H.;Mamoulis,N.;Renz,M.;Zuﬂe,A.Queryinguncertainspatio-temporal data.InProceedingsofthe28thIEEEInternationalConferenceonDataEngineering,Washington, DC,US,1–5April2012;pp.354–365. 47. Runkle,P.R.;Bharadwaj,P.K.;Couchman,L.;Carin,L.HiddenMarkovmodelsformulti-aspect targetclassiﬁcation. IEEETrans.SignalProcess. 1999, 47,2035–2040. 48. Jakob,M.;Vanˇ ek,O.;Hrstka,O.;Pˇ echouˇ cek,M.Agents vs.pirates:Multi-agentsimulation andoptimizationtoﬁghtmaritimepiracy.InProceedingsofthe11thInternationalConferenceon AutonomousAgentsandMultiagentSystems,Valencia,Spain,4–8June2012;pp.37–44. 49. Erto,P.Genesis,propertiesandidentiﬁcationoftheinverseWeibullsurvivalmodel[inItalian]. StatisticaApplicata 1989,1,117–128. 50. Morgan,L.;Martinez,A.;Myers,L.;Bourgeois,B.Distributionﬁttingofaregularpointprocess. InProceedingsoftheAmericanStatisticalAssociation2001JointStatisticalMeeting,Atlanta,GA, US,5–9August2001. 51. Cohen,C.MaximumlikelihoodestimationintheWeibulldistributionbasedoncompleteandon censoredsamples. Technometrics 1965,7,579–588. c 2013bytheauthors;licenseeMDPI,Basel,Switzerland.Thisarticleisanopenaccessarticle distributedunderthetermsandconditionsoftheCreativeCommonsAttributionlicense (http://creativecommons.org/licenses/by/3.0/).