101
1 INTRODUCTION
Identification of areas of collision risk in restricted
watersisnotonlyimportanttomeasuremarinetraffic
safety,butalsohelpfulformarinetrafficguidingand
controlling.
Many methods have been put forward for
measuringthe collisionrisk betweenvessels, suchas
fuzzytheory[1],ANN[2],ship’sDCPAandTCPA[3],
t
raditional clustering algorithm [4], etc. Generally,
these methodsaresuitablefor the high seas or open
waters because they do not consider ships’
dimension, which is a quite important factor for
evaluating the collision risk between vessels in
restrictedwaters.
AIStechnology makesitpractical tocollectships’
dimension informat
ion. Ship’s domain, which is
closely related to the ship’s dimension, is applied to
measure and identify the collision risk between
vessels in restricted waters, and then an improved
clustering algorithm based on DBSCAN [5], is put
forward for gathering the ships of collision risk and
areas of collision risk will be developed, finally, the
borderoftheareasissmoothed.
2 ANIMPROVEDDBSCANALGORITHMFOR
INDENTIFINGAREASOFCOLLISIONRISK
For mea
suring collision risk between vessels in
restricted waters, this paper images ships in the
restrictedwatersaseachindependentpolygonobject.
theseobjectsareclusteredtoidentifyareaofcollision
risk.Theso‐calledclusteringisthemethodgrouping
data object int
o several classes or cluster, the objects
insame classhas highsimilarity,otherwisehas high
difference. Clustering algorithmis an important part
inDataMining,commonlyusedclusteringalgorithm
are DBSCAN algorithm, OPTICS algorithm,
DENCLUE algorit
hms, CLIQUE algorithm, K‐
MEANSalgorithm,etc[4].
In the above algorithms, DBSCAN is typical
clustering algorithms which based on density
clustering method, its high dimensional data
A Clustering Analysis for Identifying Areas of
Collision Risk in Restricted Waters
Z.Xiang,Q.Hu&C.Shi
M
erchantMarineCollege,ShanghaiMaritimeUniversity,China
ABSTRACT:Thei
dentificationofareasofcollisionriskinrestrictedwaterscouldplayanimportantroleinVTS
services. Based on the concept of ship domain, this paper introduces a model for identifying collision risk
between vessels in restricted waters, then puts forward an improved DBSCAN clustering algorithm for
identifying areas of high collision risk, finally, the v
isualization algorithm is presented. The experimental
results in this paper show the algorithm is capable of identifying and rendering areas of collision risk in
restrictedwaters.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 7
Number 1
March 2013
DOI:10.12716/1001.07.01.13
102
handling and noise object eliminating effect is better
than the other clustering algorithm, so after
improvingitissuitabletoclusteringgeometryobjects.
In this paper the trafficflowinrestricted waters has
thesamecharacteristic(geometrytype),sowechoose
DBSCAN algorithm for prototype clustering
algorithm.
In DBSCAN algorithm,
the data object to be
clustering is seen as a particle, obviously it does not
fit the situation in the restricted waters. Taking this
problem into account, this paper introduces the
conceptoftheshipdomain[6,7,8,9,10].
Ship domain is the area that every ship hopes to
maintain an independent
region from otherness
around itself in order to avoid collisions. Factors
affectingtheshipdomaininclude:Ship’ssize,speed,
state of motion, manipulation and movement of the
shipʹsperformance,encounterposture,manipulator’s
psychological factors, traffic density in water, traffic
environment,andthenhydro‐meteorological,etc.
This paper combines ship domain
concept and
DBSCANclusteringalgorithm,proposedaimproved
DBSCAN algorithm.It selects the model of ship
domainasfollow:
1 Ship domain is oval.(it is simplified as octagon
whencalculateincomputer).
2 Ship domain can modify according to ship’s
size,speed,etc.
3 Shipitselflocates in rearward position of its ship
domain.
4 Onlywhentwo ships enterintoeach other’s ship
domain,thereisacollisionrisk.
Figure 2.1 show the ship domain model used in
thispaper.
Figure2.1.Shipdomaindomain
After selected model of ship domain, this paper
describedtheimprovedDBSCANalgorithmasbelow.
Definition 1 Objects:in this paper, the objects
meansships.
Definition2
neighborhood: the region(polygon)
of objects’ ship domains can be called objectʹs
neighborhood.
Definition 3 density: the density of a object p is
that the numberofobjectsbe contained in object p’s
neighborhood.
Definition 4 Core object: if an object’s
neighborhood at least contains the minimum
number(MinPts)objects,itnamedcoreobject.
Definition5Directlydensity‐reachable:inagiven
setofobjectsmarkedD,foragiven
neighborhood,
if the object p and the object q both in each other’s
neighborhood ,and q is a core object, then we call
the object p is directly density‐reachable from the
objectq.
Definition 6 density‐reachable: for exist objects
chain
1, 2, , 1 ,
p
ppp=qp=p
nn
,and
,
p
D(1 i n)
i
,if
every
1
p
i
is directly density‐reachable from p
i
in
the condition of given
neighborhood and MinPts
.we call the object p is density‐reachable from the
objectq.(transmission).
Definition 7 density‐connected: in a given set of
objects D ,
and MinPts, object p and object q are
both density‐reachable from the object O, then the
objectpandobjectqisdensity‐connected.
Definition 8 class with noise: in given
and
MinPts,aclassCisnon‐emptysubsetofgivensetof
objectsDsatisfiesthefollowingthreeconditions:
1 For any p, q ∈ D, if q ∈ C, and P is density‐
reachablefromq,thenp∈C;
2 Foranyp,q∈C,p
andqaredensity‐connected;
3 Donotbelongtoanyclassofobjectsisconsidered
noise.
Improved DBSCAN algorithm through
and
MinPts asinputparameterstocontrolthedensityof
theclass,onlyclassthedensitymorethanMinPtscan
be retain . The clustering process is based on the
followingprocedures:
(1)Givenparameters
andMinPts,ifexistscore
object P , every objects density‐reachable from P
satisfies
andMinPtsclustersaclassandPbelongs
tothisclass;
(2) Assuming that class C is satisfies
and
MinPts,PisacoreobjectofclassC,thentheclassCis
equivalent to the set contains objects density‐
reachablefromP.
Algorithm’s idea is that we trace and find
points(ships) to cluster through checking database
(AIS database).Firstly, we take different time data
synchronous to the same
time, this step involving
deadreckoning.If
neighborhood of point P (ship
P) contains more than MinPts number points, then
createanewclass(collisionriskarea)whichcoreisP.
Next,repeatedlylookinguptosomeobjectswhichis
density‐reachablefromthecoreP,inthisprocessmay
involve someclasscombined.Whenthereis
no new
point can be added to any class, it is the end of the
clustering process. Figure 2.2 and figure 2.3
respectivelyshowstheDBSCAN’sschematicdiagram
and the improved DBSCAN algorithm’s schematic
diagram.
Shipdomain
Shipitself
103
Figure2.2.DBSCAN’sschematicdiagram
Figure2.4. Im
proved DBSCAN algorithm’s schematic
diagram
It seems that improved DBSCAN algorithm has
the best recognition effect among three algorithm
above,specificallyintherestrictedwaters.
3 ALGORITHMFORCOMBININGAREASOF
COLLISIONRISK
Clusteringresultsinthe shape of the high‐risk areas
of the ship presented overlapping geometric and
disorganized, in order to let the drawing area to
contain the entire polygon outer envelope for
ident
ifying collision risk areas, we need to design a
polygonmergealgorithm.
This paper used the method of traversing
coordinates of spatial point to combine collision risk
areas,andallowedthepointsarrangeinclockwiseor
counterclockwise. Its purpose is formed through set
ofpointsformverticesofmult
iplepolygon(namedG)
))}(,()......,,(),,({
222111
NiyxpyxpyxpG
iii
acquired the queue of points in connection
dia
gram(namedT)
111 2 2 2
{ ( , ), ( , )......, ( , )}( )
jjj
Tpxypxy pxy jN
andmakethequeueTcanincludeallpointsofG.
Thealgorithmsdescribedareasfollows:
The set of points in the Cartesian coordinate
systemis
))}(,()......,,(),,({
222111
NiyxpyxpyxpG
iii
(1)Calculatedmaximumandminimumtwopointsin
Gsortingx,named
max
p
and
min
p
.
max max max max 1 2 max
( , ), max( , ......, ),
i
pxyx xxxpG
(3.1)
min min min min 1 2 min
( , ), min( , ......, ),
i
pxyx xxxpG
(3.2)
Point
max
p
asthefirstpointofTqueue.
(2)Makealinelinking
max
p
and
min
p
,itsequationis:
max min max min min min
(( ) / ( ))( )
k
y
yy xxxx y
(3.3)
ItcandivideGintoupperpartandlowerpart:
111 2 2 2
{ ( , ), ( , )......, ( , )}
up k k k
Gpxypxy pxy
max min max min min min
( , (( ) / ( ))( ) )
kk
kNy y y x x x x y
(3.4)
111 2 2 2
{ ( , ), ( , )......, ( , )}
down t t t
Gpxypxypxy
max min max min min min
( , (( ) / ( ))( ) )
tt
tNy y y x x xx y
(3.5)
(3) Let set
up
G
sorted in x descending order,
sequentially transferred the points in
up
G
to the
queue T until
up
G
is empty, and then added point
min
p
into T for the end point as an upper part
boundary;
(4) Let set
down
G sorted in x ascending order,
sequentially transferred the points in
down
G
to the
queueTuntil
down
G isempty,andthenaddedpoint
max
p
into T for the end point as an lower part
boundaryandalsoendpointofthewholequeueT.
Algorithmschematicdiagramasfollows:
Figure3.1.Algorithmofcombiningcollisionriskareas
ClassA
P1
P5
P2
P4
P8
P3
P7
P6
104
In figure 3.1, the dotted line around the two
quadrilateral vertex,they are
},,,{
43211
ppppG
and
},,,{
87652
ppppG .
Thesetofpointsformverticesof
1
G polygonand
2
G polygonnamed
},,,,,,,,{
187654321
pppppppppG
canaccordancewiththeabovealgorithmtoacquirea
queueofpointsinconnectiondiagram
},,,,,,,,{
673841256
pppppppppT
InFigure 3.1,the solidlineinthedirection ofthe
directionoftheenvelope.
4
P and
6
P are
min
p
and
max
p
,queueT’ssequenceiscounterclockwise.
4 ALGORITHMFORSMOOTHINGTHEBORDER
OFAREAOFCOLLISIONRISK
The combined polygon’s boundary is always rough
and exists pits, this paper introduced a algorithm to
smooth polygons, this method through calculating
polygon’s area to remove surplus pits and make
polygonmellowandlooks
good.
The algorithm’s purpose is that through the
connectiondiagram(namedT)
111 2 2 2
{ ( , ), ( , )......, ( , )}( )
jjj
Tpxypxy pxy jN
to find another connection diagram R, and cause R
includingallpointsofTandhavemaximumarea.
Therecursivealgorithmisdescribedasfollows:
(1) input connection diagram T, and calculate its
spatialareacalled
area
T .
(2)Sequentiallyremovedapoint
),(
kkk
yxp
in
))}(,()......,,(),,({
222111
NjyxpyxpyxpT
jjj
,
makeit
),,()...,,(),,({
111222111
kkktemp
yxpyxpyxpT
),)}(,()..,,(
111
Njkyxpyxp
jjjkkk
(4.1)
calculatethearea of
temp
T
,named
temparea
T
, if
jk
thentheprocessiscompleted.
(3) compare
area
T
and
temparea
T
, if
area
T less than
temparea
T
,thenreplaced
T
into
temp
T
asinputofstep
(1)andreturntoperformthestep(1),step(2);ifnot
gotostep(2).
Algorithmschematicdiagramasfollows:
Figure4.1.Bordersmoothingalgorithm
Obviously,removingtheremovedpointsinfigure
4.1cansurplusT’sarea.
5 EXPERIMENTALRESULTSAND
CONCLUSIONS
Experiment used AIS data collected from
Wusongkou (Shanghai), Waigaoqiao (shanghai)
which raw AIS data show as figure 5.1, successfully
identified areas of collision risk as figure 5.2
shows.(Ships’informationinfigure5.2correspondto
rawAISdatainfigure5.1)
Figure5.1.AISdata
Figure5.2.Experimentresult
y
remove
x
remove
105
Theresultsshowthatthealgorithmputforwardin
this paper is able to identify and render areas of
collisionriskinrestrictedwaters.
REFERENCES
[1]Xuwu Su,Guangyou Yang, Guozhu Zhou. Comparison
of fuzzy mathematics in pattern recognition
applications.JournalofHubeiUniversity,2005
[2]Xide Cheng, Zhuyuan Liu. Using improved BP neural
network caculate open water ship collision risk [C].
Naval Architecture and Ocean Engineering Research
Album.2001,143:91‐93.
[3]Xiaolin Zhu, Hanzhen Xu. A
ship collision risk model
based on neural network [J]. Journal of Huazhong
ScienceUniversity,2005,28(10).
[4]Lin He, Linda Wu, Yizhao Cai. Summary of clustering
algorithmsindatamining.ApplicationandResearchof
Computers,2007(10).
[5]Jian Li, Wei Yu, Baoping Yan. Memory effect in
DBSCAN algorithm. 2009 4th
International Conference
on Computer Science and Education(ICCSE 2009),
2009(31‐36).
[6]E.M.Goodwin, A statistical study of ship domain, The
JournalofNavigation,1975,vol.28,no.3:328‐344
[7]E.M.Goodwin, Determination of ship Domain Size．
Proceedings of International Conference on
Mathematical Aspect of Marine Traffic ． London ：
AcademicPress，1977：103‐127
[8]E.M.Goodwin,J.f.Kemp,Asurveyofmarinetrafficinthe
southern north sea, The Journal of Navigation, 1977,
vol.30,no.4:378
[9]P.A.Davis, M.J.Dove, C.T.Stockel, A computer
simulation of marine traffic using domains and areas,
TheJournalofNavigation,1980,vol.33,no.2:215‐222
[10]Tao Liu, QinyouHu, Chun
Yang. cluster analysis and
recognition in heavy water traffic area [J]. China
Navigation.2010.33(04)
