Study on complexity of marine traffic based on traffic intrinsic features and data mining

Abstract

The large scale, high speed and increasing number of vessels along with busy sea routes increase the complexity of marine traffic. It is important for traffic controllers or mariners to understand the traffic situation and pay more attention to high-complexity area. In previous studies, density-based clustering algorithm was often used to discover high-density vessel clusters, so as to evaluate collision risk in waters. However, it can be argued that ship’s encounter situation was ignored with those algorithms. This paper focuses on complexity modeling of the two encountering ships and clustering using data mining technology. A complexity model is proposed by employing intrinsic features to reflect pair-wise interactions between ships. A clustering method of ship to ship encountering risk is presented on the basis of complexity by proposing a new distance definition, to quickly calculate the complexity of a large number of ships in an area.

Keywords

Automatic identification system density-based clustering ship encounter collision risk OPTICS algorithm

1. Introduction

The automatic identification system (AIS), which is to be compulsorily installed on vessels of 500 gross tonnages and above, has brought a large amount of ship dynamic data. However, the massive traffic data do not always help traffic controllers or mariners to understand the traffic situation. On the contrary, too many irrelative data may decrease the cognition of other important information [1]. Therefore, how to draw useful massage from the massive data has attracted considerable attention in terms of both academic research and practical applications.

Currently, there are primarily two methods to demonstrate traffic situation. First focuses on the statistics and analysis of traffic characteristics from a macroscopic perspective by mining historical AIS data. The research waters are divided into grids, and the number of AIS objects on each cell is counted to obtain the ship density distribution [2]. The routes and mooring areas are estimated using the AIS trajectory clustering method [3]. Second studies on ship behaviors at the micro level using ship domain, traffic conflict and probability theories. Encounter situation and near-miss are detected to evaluate the ship collision risk on the basis of AIS data [4, 5, 6]. Ship behaviors such as fishing, barging, smuggling and other activities, can also be determined by analyzing AIS data [7].

Nevertheless, there are few researches that have applied both of the two methods simultaneously. In previous AIS-based studies, for instance, density-based clustering algorithm was often used to discover high-density vessel clusters, so as to evaluate collision risk in waters [8, 9]. It can be argued that the encounter situation was ignored with those algorithms. Apparently, there is no higher risk for well-organized high-density ships in traffic separation schemes. Therefore, the various encounter situations such as approaching or receding, head-on or crossing should be significant factors in clustering.

Actually, there are three approaches to rank encounter risk in general. The first approach uses the progress of the distance at closest point of approach (DCPA) and time to closest point of approach (TCPA) during encounters. Second estimates the normally maintained ship domains, and determines whether these domains are entered [10]. Third proposes a frame to rank the conflict severity or complexity [11, 12, 13]. However, due to the enormous complexity in accounting for the spatio-temporal relations of multiple interacting traffic users, all methods mentioned above mainly focus on pair-wise encounters between vessels.

Recently, traffic complexity has received more and more attention in academic research. It was developed to estimate air traffic controllers’ workload at the beginning. Along with the development of relative research, the traffic complexity was gradually applied to describing traffic situation. Some researchers believe that traffic situation are only related to traffic intrinsic features (like: location and motion) [14]. A marine traffic complexity model was built on the basis of intrinsic features, to describe the traffic situation [1]. Nonetheless, the proposed model has just assumed the standard length overall (LOA) and its utility in data mining has not yet been discussed.

Accordingly, this paper primarily focuses on complexity modeling of the two encountering ships and clustering using data mining technology. Compared with previous academic work, its main contributions are involved in three fields. Firstly, the research is divided into two steps, complexity modeling and density-based clustering, combining the microscopic analysis of ship encounter behavior with the macroscopic statistics of ship density distribution. Secondly, the complexity model is proposed by employing intrinsic features, different LOA and a novel analysis of crossing angle factor. Eventually, a clustering method of ship-ship encountering risk is presented on the basis of complexity and risk factors analysis by proposing a new distance definition.

2. Complexity model

2.1 Basic concept

Two encountering vessels at close range, $i$ and $j$ , constitute the basic marine traffic relationship unit, denoted by vessel couple $(VC_{ij})$ . The states of vessels $i$ and $j$ are defined as $i({{\rm t}_{i},{\rm m}_{i},x_{i},y_{i},v_{i},{\rm\alpha}_{i},l_{i}})$ and $j({{\rm t}_{j},{\rm m}_{j},x_{{\rm j}},y_{{\rm j}},v_{{\rm j}},{\rm\alpha}_{{% \rm j}},l_{j}})$ . Specifically, ${\rm t}_{i},{\rm t}_{j}$ represent AIS reporting time, ${\rm m}_{i},{\rm m}_{j}$ are regarded as maritime mobile service identity (MMSI), $(x_{i},y_{j})$ , $(x_{i},y_{j})$ as longitude and latitude, $v_{i},v_{{\rm j}}$ as speed over ground (SOG), ${\rm\alpha}_{i},{\rm\alpha}_{{\rm j}}$ as course over ground (COG), and $l_{i},l_{j}$ as LOA. $\overrightarrow{D_{ij}}$ refers to the distance from $i$ to $j$ . Note that $|{\overrightarrow{D_{ij}}}|$ is the geographical distance between $i$ and $j$ , instead of Euclidian distance. $\overrightarrow{v_{ij}}$ indicates the relative speed from $i$ to $j$ . Besides, the crossing angle of two vessels is shown as $\varphi$ , $\varphi=|{{\rm\alpha}_{i}-{\rm\alpha}_{{\rm j}}-\pi}|\in[{0,\pi}]$ .

There is a distance boundary ( $l_{\textit{upper}}$ ) within $VC_{ij}$ . Only when the distance is less than $l_{\textit{upper}}$ , two vessels are in encounter situation. The complexity value is set to be the minimum when their distance is larger than $l_{\textit{upper}}$ . The ship domain is an area that rejects other ships. When the ownship domain (relative distance less than $l_{\textit{lower}}$ ) is invaded, the complexity value is maximized. The distance boundary which both ships take action to avoid a collision is expressed as $l_{\textit{middle}}$ [1].

2.2 Complexity analysis

Relative distance, movement trend and crossing angle are selected as influence factors on the complexity of vessel couple [13].

Definition 1 (Complexity of vessel couple). The complexity of $VC_{ij}$ refers to the influence degree of vessel $j$ to vessel $i$ by the factors of relative distance, movement trend and crossing angle, denoted by $\textit{complexity}_{ij}$ .

It follows the hypothesis that the complexity of vessel couple has continuity, that is to say, the complexity values change continuously with the changes of the factors [1].

Figure 1.

Diagram of movement trend analysis.

2.2.1 Relative distance factor

Definition 2 (Complexity of relative distance factor). It is caused by vessel $j$ with a relative distance $|{\overrightarrow{D_{ij}}}|$ from $i$ , denoted by $\textit{distance}_{ij}$ , expressed as [15]

$\displaystyle\textit{distance}_{ij}=\begin{cases}{\lambda e^{-\alpha\frac{|{% \overrightarrow{D_{ij}}}|}{R}},|{\overrightarrow{D_{ij}}}|\geqslant R}\\ {\lambda e^{-\alpha},|{\overrightarrow{D_{ij}}}|<R}\\ \end{cases}$

$\lambda,\alpha$ are correction parameters, $\lambda>0,\alpha>0.$ $R$ refers to the minimum safety distance between vessels $j$ and $i$ , $R=l_{\textit{lower}}$ .

If both movement trend and crossing angle are invariant, the complexity with closer relative distance becomes greater. When $|{\overrightarrow{D_{ij}}}|\geqslant R$ , $\textit{distance}_{ij}$ increases nonlinearly with decrease of relative distance. When $|{\overrightarrow{D_{ij}}}|<R$ , the complexity reaches its maximum, indicating that another vessel is already within its ship domain.

2.2.2 Movement trend factor

In the case of the same distance and crossing angle, there are two opposite kinds of movement tendency, approaching or receding, depending on the relative position and orientation of the vessels. In most cases, there is no risk involved in the receding vessels [12]. The complexity of receding vessel couple can be defined as zero.

Definition 3 (Complexity of movement trend factor). It is caused by vessels’ relative movement tendency, denoted by $\textit{trend}_{ij}$ . If a vessel couple is receding, $\textit{trend}_{ij}=0$ . Otherwise, $\textit{trend}_{ij}$ is positively related to the relative speed.

The relative motion of two vessels can be determined as [16]

$\displaystyle\frac{{\rm d}|{\overrightarrow{D_{ij}}}|}{{\rm dt}}=\frac{% \overrightarrow{D_{ij}}\cdot\overrightarrow{v_{{ij}}}}{|{\overrightarrow{D_{ij% }}}|}=|{\overrightarrow{v_{{ij}}}}|\cdot\cos({\overrightarrow{v_{{ij}}},% \overrightarrow{D_{ij}}})$

It can be deduced from Fig. 1,

$\displaystyle\cos({\overrightarrow{v_{{ij}}},\overrightarrow{D_{ij}}})=\frac{(% {x_{j}-x_{i}})(|{\overrightarrow{v_{j}}}|\sin\alpha_{j}-|{\overrightarrow{v_{i% }}}|\sin\alpha_{i})+({y_{j}-y_{i}})(|{\overrightarrow{v_{j}}|{\cos\alpha_{j}-}% |\overrightarrow{v_{i}}}|\cos\alpha_{i})}{|{\overrightarrow{v_{{ij}}}|\cdot|% \overrightarrow{D_{ij}}}|}$ (1)

Set $\theta$ as the angle between $\overrightarrow{v_{{\rm ij}}}\text{ and }\overrightarrow{D_{ij}}$ . If $\frac{{\rm d}|{\overrightarrow{D_{ij}}}|}{{\rm dt}}>0$ , then $\theta\in[{0,\frac{{\rm\pi}}{2}}]$ , indicating that vessel couple is receding. If $\frac{{\rm d}|{\overrightarrow{D_{ij}}}|}{{\rm dt}}<0$ , then $\theta\in({\frac{{\rm\pi}}{2},{\rm\pi}}]$ , the vessel couple is approaching to each other, so

$\displaystyle\textit{trend}_{ij}=l_{R^{-}}\left\{{\frac{{\rm d}|{% \overrightarrow{D_{ij}}}|}{{\rm dt}}}\right\}=\begin{cases}\left|{{% \displaystyle\frac{{\rm d}|{\overrightarrow{D_{ij}}}|}{{\rm dt}}}}\right|,&{% \displaystyle\frac{{\rm d}|{\overrightarrow{D_{ij}}}|}{{\rm dt}}}<0\\ 0,&{\displaystyle\frac{{\rm d}|{\overrightarrow{D_{ij}}}|}{{\rm dt}}}>0\\ \end{cases}$

$l_{R^{-}}$ is an indicator function to output its absolute value when the variable is negative, otherwise 0.

2.2.3 Crossing angle factor

Definition 4 (Complexity of crossing angle factor). It is caused by crossing angle $\varphi$ , denoted by ${\textit{angle}}_{ij}$ .

Figure 2.

The diagram of ship encounter situation.

Two-ship encountering is shown in Fig. 2 [17], with reference to “convention on the international regulations for preventing collisions at sea, 1972” (COLREGS). With ${\rm\varphi}\in\left[{0,3^{\circ}}\right]$ , when two power-driven vessels are meeting on the reciprocal or nearly reciprocal courses, each shall alter its course to starboard so as to avoid the risk of collision. ${\rm\varphi}\in\left({3^{\circ},112.5^{\circ}}\right)$ , the give-way ship shall alter her course to starboard. ${\rm\varphi}\in\left({90^{\circ},112.5^{\circ}}\right)$ , the give-way ship shall alter her course to portside. ${\rm\varphi}\in\left({112.5^{\circ},180^{\circ}}\right]$ , any vessel that overtakes others shall keep out of the way of the overtaken one. With ${\rm\varphi}=90^{\circ}\text{ or }112.5^{\circ}$ , it’s complicated to identify the encounter situation.

Merely, when numerous ships approach at the same time, they shall search for an optimal set of safe trajectories of all ships involved in an encounter [18]. A power-driven vessel which takes action in a crossing situation in accordance with sub-paragraph 17.3 of the COLREGS to avoid collision with another power-driven vessel shall, if the circumstances of the case admit, not alter course to port for a vessel on her own port side. Whereas, the common practice of seafarers in multi-ship encounter situation is to obey the regulations on specific situation of encounter. For instance, it tends to turn to starboard when avoiding a ship coming in front [19], which is contradictory to the give-way ship’s anti-collision behavior with ${\rm\varphi}\in\left({90^{\circ},112.5^{\circ}}\right)$ in two-ship encounter situation.

Therefore, we suppose that the complexity is maximized when ${\varphi}\in\left[{90^{\circ},112.5^{\circ}}\right]$ , and draw the complexity line caused by $\varphi$ , as shown in Fig. 3.

The complexity increases nonlinearly with decreasing $|{\overrightarrow{D_{ij}}}|$ . The complexity is set to minimum if $|{\overrightarrow{D_{ij}}}|$ exceeds $l_{\textit{upper}}$ and reaches a peak when $|{\overrightarrow{D_{ij}}}|$ is less than $l_{\textit{lower}}$ . Thus, $|{\overrightarrow{D_{ij}}}|=l_{\textit{middle}}$ defines the condition of the median complexity that has fluctuated nonlinearly as a function of $\varphi$ [1]. According to Fig. 3, the median complexity is revealed as:

$\displaystyle f\left(\varphi\right)=\begin{cases}\sin\left({\displaystyle\frac% {\varphi}{2}}+{\displaystyle\frac{\pi}{4}}\right),&\varphi\in\left[{0,{% \displaystyle\frac{\pi}{2}}}\right)\\ 1,&\varphi\in\left[{{\displaystyle\frac{\pi}{2}},{\displaystyle\frac{5\pi}{8}}% }\right]\\ \sin\left({\varphi-{\displaystyle\frac{\pi}{8}}}\right),&\varphi\in\left({{% \displaystyle\frac{5\pi}{8}},\pi}\right]\\ \end{cases}$ (2)

$f(\varphi)$ has an increasing function for $\varphi\in\left[{0,\frac{\pi}{2}}\right)$ and a decreasing function for $\varphi\in\left({\frac{5\pi}{8},\pi}\right]$ , while reaching the summit for ${\rm\varphi}\in\left[{\frac{\pi}{2},\frac{5\pi}{8}}\right]$ .

Figure 3.

Angle complexity as a function of $\varphi$ .

Besides, to ensure the assumption that the complexity is continuous, the following functions are constructed [20]:

$\displaystyle\text{When }|{\overrightarrow{D_{ij}}}|\in({l_{\textit{lower}},l_% {\textit{middle}}}],g_{1}({|{\overrightarrow{D_{ij}}}|})=\frac{|{% \overrightarrow{D_{ij}}}|-l_{\textit{lower}}}{l_{\textit{middle}}-l_{\textit{% lower}}},\textit{ angle}_{ij}=f(\varphi)\cdot g_{1}({|{\overrightarrow{D_{ij}}% }|})$ $\displaystyle\text{When }|{\overrightarrow{D_{ij}}}|\in({l_{\textit{middle}},l% _{\textit{upper}}}],g_{2}({|{\overrightarrow{D_{ij}}}|})=\frac{l_{\textit{% upper}}-|{\overrightarrow{D_{ij}}}|}{l_{\textit{upper}}-l_{\textit{middle}}},% \textit{ angle}_{ij}=f(\varphi)\cdot g_{2}({|{\overrightarrow{D_{ij}}}|})$

2.3 Complexity of vessel couple

As mentioned above, the encounter situation should be an influential factor in the density-based AIS data clustering. Supposing that complexity of vessel couple is sum of the complexity generated by encounter situation and the complexity due to spatial distance, it can be expressed as follows:

$\textit{complexity}_{ij}=\textit{distance}_{ij}+{\textit{angle}}_{ij}\cdot{% \textit{trend}}_{ij}$

$\displaystyle=\begin{cases}\lambda{e^{-\alpha}},&|{\overrightarrow{{D_{ij}}}}|% \in({0,{l_{\textit{lower}}}}]\\ \lambda{e^{-\alpha\frac{{|{\overrightarrow{{D_{ij}}}}|}}{R}}}+{l_{{R^{-}}}}% \left\{{{\displaystyle\frac{{{\rm{d}}|{\overrightarrow{{D_{ij}}}}|}}{{{\rm{d}}% t}}}}\right\}f(\varphi){g_{1}}({|{\overrightarrow{{D_{ij}}}}|}),&|{% \overrightarrow{{D_{ij}}}}|\in({{l_{\textit{lower}}},{l_{\textit{middle}}}}]\\ \lambda{e^{-\alpha\frac{{|{\overrightarrow{{D_{ij}}}}|}}{R}}}+{l_{{R^{-}}}}% \left\{{{\displaystyle\frac{{{\rm{d}}|{\overrightarrow{{D_{ij}}}}|}}{{{\rm{d}}% t}}}}\right\}f(\varphi){g_{2}}({|{\overrightarrow{{D_{ij}}}}|}),&|{% \overrightarrow{{D_{ij}}}}|\in({{l_{\textit{middle}}},{l_{\textit{upper}}}}]\\ \lambda{e^{-\alpha\frac{{|{\overrightarrow{{D_{ij}}}}|}}{R}}},&|{% \overrightarrow{{D_{ij}}}}|\in({{l_{\textit{upper}}},+\infty})\end{cases}$ (3)

On account of LOA’s difference, the ship domains have distinguishing radiuses, $\textit{distance}_{ij}$ is asymmetric, so $\textit{complexity}_{ij}$ has the same attribute, $\textit{complexity}_{ij}\neq\textit{complexity}_{ji}$ . Nonetheless, the probability of marine traffic accident mainly depends on the larger-size party. Therefore, the complexity of vessel couple takes the maximum [12], that is,

$\displaystyle\textit{complexity}({i,j})=\max\{\textit{complexity}_{ij},\textit% {complexity}_{ji}\}$ (4)

3. Clustering method

Typically, the more complexity, the more dangerous the vessel couples are. This paper proposes a new distance definition of order distance, that is, the narrower the order distance is, the more hazardous the vessel couples are.

Definition 5 (Order distance). The order distance is nonlinearly overlaid of the ship’s encounter situation to their spatial distance. Its value is equal to the reciprocal complexity of vessel couple.

$\displaystyle\textit{orderDist}({i,j})=\frac{1}{\textit{complexity}({i,j})}$ (5)

3.1 AIS data reduction

Scholars usually study how to compress ship trajectory big data to minimize data storage capacity while ensuring data quality, for instance, using Douglas-Peucker algorithm [21], and focus on algorithms for detecting and pre-processing errors of AIS tracks including physical integrity, spatial logical integrity and time accuracy [22]. This paper highlights the issue of ship AIS data on the same time slices on account that encounter is a simultaneous appearance of vessels in a certain limited area.

In order to calculate the complexity of vessel couples, the AIS data points should be obtained from the same time slice ${\rm t}_{i}$ and move to next time slice ${\rm t}_{i+1}$ afterwards. The time slice interval ( ${\rm t}_{i+1}-{\rm t}_{i}$ ) should be over 30 seconds, otherwise, there may not be a point within 30 seconds for Class B AIS devices [23]. One minute is regarded as an appropriate interval because it will be pretty long for some navigational maneuvers if more than 60 seconds.

For an area, a large number of AIS data points are to be extracted from vessel traffic service (VTS) system over a period of time. Specifically, each point has seven attributes that are time, MMSI, longitude, latitude, SOG, COG and LOA, denoted by $i\left({{\rm t}_{i},{\rm m}_{i},x_{i},y_{i},v_{i},{\rm\alpha}_{i},l_{i}}\right)$ separately.

AIS data are reduced by the following steps:

Step 1: Step 1:
Remove the AIS data in which MMSI is substandard.
Step 2:
Remove the AIS data with speed less than or equal to 2.0 knots. When SOG is larger than 2.0 knots, AIS data transmission internal is less than 30 seconds regardless of being Class A or Class B AIS equipment [23], so that there are sample points in a minute all the time.
Step 3:
Remove AIS data except the first one in a minute. For example, if a vessel $i$ broadcasts several AIS data at 12:31:06, 12:31:20, 12:31:43 from 12:31:00 o’clock, then only 12:31:06 (point 1 in Fig. 4) is retained.
Step 4:
Calculate the vessels’ location at exactly minute respectively. Assume that the speed and course of vessel $i$ remain stable within small interval, thus, the location of vessel $i$ can be projected at $t_{i}^{k}$ based on points at $t_{i}^{k+1}$ by exploiting linear functions. For example, the location of vessel $i$ at 12:31:00 (point 0 in Fig. 4) can be projected from the location at 12:31:06.

Figure 4.
Diagram of AIS data reduction.

3.2 OPTICS algorithm improvement

Ordering points to identify the clustering structure (OPTICS) is an algorithm for finding density-based clusters in spatial data [24], which is originally stemmed from the spatial distance and its fundamental approach cannot deal with spatio-temporal data. In order to get complete complexity of each time slice in a period of time, the OPTICS definition and procedure are improved in this paper.

3.2.1 Algorithm redefinition

Actually, improved OPTICS algorithm still requires two parameters: $\varepsilon$ , which describes the maximum order distance to be considered, and MinPts, indicating the number of AIS points that are required to form a cluster.

Definition 6 ( $\varepsilon$ -neighborhood). Given a database DB of AIS points in a specific area, the $\varepsilon$ -neighborhood of an AIS point $i,$ denoted by $N_{\varepsilon}(i),$ is defined as

$\displaystyle N_{\varepsilon}(i)=\{j\in DB|{t}_{i}={t}_{j}\text{ and }\textit{% orderDist}({i,j})\leqslant\varepsilon\}$ (6)

AIS points of $i$ ’ $s$ $\varepsilon$ -neighborhood are all at the same time slice as $i$ . An AIS point $i$ is a core point if at least MinPts AIS points are found within its $\varepsilon$ -neighborhood.

Definition 7 (Core distance). The core distance describes the order distance to the MinPts-th closest AIS point.

$\displaystyle\textit{coreDist}(i)=\begin{cases}\textit{UNDIFINED},&\text{if }N% _{\varepsilon}(i).\text{size}<\textit{MinPts}\\ \textit{MinPts}_{\rm th}\text{ smallest order distance in }N_{\varepsilon}(i),% &\text{else}\\ \end{cases}$ (7)

Definition 8 (Reachability distance). The reachability distance of another AIS point $j$ from an AIS point $i$ is either the order distance between $j$ and $i$ , or the core distance of $i$ , whichever is bigger:

$\displaystyle\textit{reachDist}({i,j})=\begin{cases}\textit{UNDIFINED},&\text{% if }N_{\varepsilon}(i).\text{size}<\textit{MinPts}\\ \max\{{\textit{coreDist}(i),\textit{orderDist}({i,j})}\},&\text{else}\\ \end{cases}$ (8)

Figure 5.

Procedure of improved OPTICS (DB, $\varepsilon$ , MinPts).

3.2.2 Procedure description

As illustrated in Fig. 5, the main procedure is OPTICS (DB, $\varepsilon$ , MinPts). For each point $p$ of DB, its reachability distance (reach-dist) is set as undefined. For each unprocessed point $p$ of DB, get its $\varepsilon$ -neighborhood (N), mark $p$ as processed and output $p$ to the ordered list. If $p$ ’ $s$ core distance is undefined, create an empty priority queue (Seeds), which always keeps its nodes with priority order (reach-dist), and updates Seeds. Afterwards, for each $q$ in Seeds, get its $\varepsilon$ -neighborhood (N’), mark $q$ as processed and then output $q$ to the ordered list. Eventually, if $q$ ’ $s$ core distance is defined, update Seeds.

Update (N, $p$ , Seeds) is a crucial sub-procedure. It get $p$ ’ $s$ core distance (core-dist). For each $o$ in N, if $o$ is not processed, getting maximum of the core-dist and the order distance between $p$ and $o$ , which is denoted by new-reach-dist. If $o$ is not in Seeds, set $o$ ’ $s$ reach-dist as new-reach-dist and insert $o$ into Seeds by priority. Otherwise, if new-reach-dist is less than $o$ ’ $s$ reach-dist, set the latter one as the former one, insert $o$ into Seeds and adjust it by priority.

Apparently, through the algorithm, AIS data points are linearly ordered so that the points which are the closest on order distance become well-aligned neighbors. The diagram of reachability distance can distinctly reveal the low-concave area, indicating the greater risk among vessels, which is more accident-prone.

3.3 Complexity of marine traffic

At a time slice, there are numerous vessels in an area and every two of them may make up a pair of vessel couple.

Definition 9 (Complexity of marine traffic). The improved OPTICS algorithm is run on AIS data at a time slice $t$ in an area, and there are a total of $m$ reachability distances in result, $d_{1},d_{2}$ , …, $d_{m}$ . The complexity of marine traffic at the time slice $t$ is expressed as $C_{t}$ , then

$\displaystyle C_{t}=\frac{1}{d_{1}}+\frac{1}{d_{2}}+\ldots+\frac{1}{d_{m}}$ (9)

When the algorithm outputs some vessel objects whose reachability distances are defined, there will be complexity of marine traffic among the vessel objects. MinPts $\geqslant$ 3 indicates that at least three AIS points are required to form a cluster where reachability distances are defined, resulting in multi-ship encounter situation.

Figure 6.

Procedure of update (N, $p$ , Seeds).

Figure 7.

Diagram of research waters.

Usually, the complexity of marine traffic may be efficient to rank risk level at a time slice, so as to reveal traffic situation minute by minute in real time. It is crucial for VTS operators to grasp the complexity variation over time and lay more emphasis on the high-complexity area timely.

Definition 10 (Average complexity of marine traffic). The average complexity of marine traffic in an area is the average value of $C_{t}$ at exactly every minute in a given period, expressed as AC,

$\displaystyle AC=\frac{C_{t1}+C_{t2}+\ldots+C_{tn}}{n}$ (10)

The above-mentioned period can be divided into $n$ minutes.

Admittedly, the average complexity of marine traffic can not only discover long-term traffic pattern and knowledge, but also assess current traffic status of VTS area and the workload of VTS operator. Through traffic organizations, VTS operator makes the reduction of multi-ship encounter at close range possible, so that his performance can be measured by average complexity of marine traffic with his work hours.

4. Case study

4.1 AIS data collection and reduction

For case study, respectively, four points (ABCD) of the water area in Zhoushan North Sea of China are selected, where the East Route, West Route, Majishan Fairway and Yangshan Fairway converge, as shown in Fig. 7. The marine traffic flow here is relatively complicated.

A total of 2,525,478 AIS data points for a month (1 July to 31 July 2017) are extracted from VTS system. After the AIS data reduction caused by the method explained in Section 3.1, 447,632 data records are kept in total, demonstrated in Table 1.

4.2 Parameter settings

Experts are invited to set parameters. Given the rather extensive scope of the elicitation, it was preferred to select only a limited number of experts who were able to contribute their expertise over a longer time. The experts include one captain (10 years of experience), two first officers (10 and 5 years of experience) and two VTS operators (8 and 6 years of experience).

Table 1
AIS data list after reduction (part)

Time	MMSI	Longitude/ ${}^{\circ}$	Latitude/ ${}^{\circ}$	SOG/kn	COG/ ${}^{\circ}$	LOA/m
20170705 00:07:00	538003776	122.2046	29.8447	12.2	150.0	274
20170705 00:07:00	538004648	121.8890	30.2849	2.9	112.9	184
20170705 00:26:00	412424132	122.3645	29.8624	10.1	346.7	85
20170705 00:07:00	636015047	121.9364	30.4047	11.9	55.2	120
20170708 09:12:00	636016247	121.8820	29.9655	10.8	242.8	228
20170708 10:08:00	412040050	122.1845	30.6144	7.6	207.7	40
20170708 10:08:00	412081790	122.3276	30.7189	7.0	173.4	112

$l_{\textit{upper}}$ is the upper distance boundary for two ships, which is various on account that different mariners have distinct sense of danger. It also depends on the environment ship sailing. Mariners or traffic controllers can set $l_{\textit{upper}}$ ’s value by their experience [1]. Nowadays, motor vessels’ LOA are between 20 meters and 400 meters, $L\in({20\text{ m},400\text{ m}})$ . In case study, experts estimate that other ships a mile away can be ignored by the ship whose LOA is 20 meters, and that other ships three miles away can be ignored by the ship whose LOA is 400 meters. It can be described linearly as, $\frac{l_{\textit{upper}}-1}{L-20}=\frac{3-1}{400-20}$ , that is, $l_{\textit{upper}}=\frac{L}{190}+\frac{17}{19}$ .

$l_{\textit{middle}}$ is the distance boundary that both ships should take action to avoid a collision. It is closely related to the mariners’ maneuvering habits and the performance of ship. Mariners or traffic controllers can confirm $l_{\textit{middle}}$ ’s value according to the ship performance. In this paper, experts suppose $l_{\textit{middle}}=0.5\ast l_{\textit{upper}}=\frac{L}{380}+\frac{17}{38}.$

$l_{\textit{lower}}$ is the radius of the ship domain. Empirical research shows actual ship domains are more elliptical [25]. To simplify the model, it is supposed that the ship domain is rounded and its safety distance is shown as $l_{\textit{lower}}$ , which is three times the size of LOA [26], $l_{\textit{lower}}=\frac{3L}{1852}$ . For example, if in a vessel’s LOA, $L=$ 185 m, then $l_{\textit{lower}}=$ 0.3 n miles, $l_{\textit{middle}}=$ 0.93 n miles and $l_{\textit{upper}}=$ 1.87 n miles.

Besides, more information needs to be provided by mariners and traffic controllers in order to obtain the value of $\alpha$ and $\lambda$ , which have no physical meaning, for instance, the comparison of complexity in different situation. With the minimum influence of movement trend and crossing-angle, the complexity of vessel couple when $|{\overrightarrow{D_{ij}}}|=6L$ is five times as that when $|{\overrightarrow{D_{ij}}}|=12L$ . In the case of $|{\overrightarrow{D_{ij}}}|=9L$ , maximizing the impact of movement trend and crossing angle, the total complexity of movement trend factor and crossing angle factor is twice the complexity of the relative distance factor, that is

$\displaystyle\lambda e^{-2\alpha}=5\ast\lambda e^{-4\alpha}$ $\displaystyle 2\ast\lambda e^{-\alpha\frac{|{\overrightarrow{D_{ij}}}|}{R}}=l_% {R^{-}}\left\{{\frac{{\rm d}|{\overrightarrow{D_{ij}}}|}{{\rm d}t}}\right\}% \cdot f(\theta)\cdot g_{1}({|{\overrightarrow{D_{ij}}}|})$

It can be calculated as ${\rm\lambda}=110.2,\alpha=0.8$ , and the maximum complexity $\lambda e^{-\alpha}=50$ .

Figure 8.

Illustration of OPTICS clustering (part).

4.3 Clustering analysis and discussion

Programming the optimized OPTICS algorithm on the platform of waikato environment for knowledge analysis (WEKA) based on JAVA language, the clustering can be interpreted as follows.

Table 2
The clustering result of improved OPTICS algorithm (part)

Key	Time	MMSI	Longitude / ${}^{\circ}$	Latitude / ${}^{\circ}$	SOG /kn	COG / ${}^{\circ}$	Core distance	Reachability distance
100950	3:22	413483000	122.4452	30.5541	8.7	140	0.215	UNDEFINED
125012	3:22	413702090	122.4650	30.5513	7.9	323.7	0.131	0.215
144111	3:22	482458290	122.4692	30.5336	8.2	320.4	0.059	0.131
12674	3:22	373134000	122.4604	30.5164	19	282.8	0.059	0.059
147704	3:22	566047000	122.4657	30.5236	10.2	286	0.043	0.059
74804	3:22	413370750	122.4419	30.4992	7.8	6	UNDEFINED	0.087
36204	3:22	412436360	122.4530	30.5551	11.3	140.9	0.061	0.130
101488	3:22	413489830	122.4913	30.5256	7.4	325.1	0.193	0.148
15113	3:22	412148000	122.5148	30.5380	10.3	267.1	0.221	0.221
112578	3:22	413556320	122.5034	30.5423	11.2	152.5	0.270	0.221
100951	3:23	413483000	122.4477	30.5516	8.5	139.3	0.043	UNDEFINED
36205	3:23	412436360	122.4551	30.5527	11.5	140.7	0.043	0.043
43695	3:23	412501270	122.4510	30.5552	10.3	134.2	0.038	0.043
144112	3:23	482458290	122.4668	30.5361	8.3	319.4	0.075	0.061
12675	3:23	373134000	122.4545	30.5177	19	283.6	0.119	0.075
140366	3:23	477333900	122.4960	30.5077	18.9	103.3	0.165	0.358
112579	3:23	413556320	122.5051	30.5394	11.4	152.3	0.165	0.165
15114	3:23	412148000	122.5115	30.5378	10.3	265.9	0.134	0.165
55134	3:23	413176779	122.5276	30.4866	6.7	143.6	0.196	0.196
35389	3:23	412434120	122.5330	30.4877	11	142.4	0.260	0.196
151311	3:23	636017577	122.5885	30.4854	7.5	317.4	0.085	0.260
18468	3:23	412320440	122.6224	30.4828	8	176.7	0.057	0.085
22208	3:23	412355490	122.6254	30.4897	7.9	4.9	0.046	0.057
53087	3:23	412762270	122.6269	30.4898	7.7	180.3	0.057	0.046
23260	3:23	412356750	122.6152	30.5046	8.7	0.8	0.419	0.085
26223	3:23	412379640	122.5541	30.4630	8.9	140	0.130	0.130
82879	3:23	413424050	122.5455	30.4692	7.9	139.1	0.145	0.130
26013	3:23	412379380	122.5610	30.5165	9	314	UNDEFINED	0.166
77090	3:23	413376840	122.6335	30.4555	11.1	186	UNDEFINED	0.350
7042	3:23	312282000	122.6460	30.4776	10	5.3	0.514	0.381
120236	3:23	413696320	122.5544	30.4430	11.7	157.5	0.626	0.425
100952	3:24	413483000	122.4489	30.5503	8.7	139.9	0.208	UNDEFINED

4.3.1 Clustering of vessel couple by order distance

Setting $\varepsilon=$ 1 and MinPts $=$ 3, indicate that at least three vessels are density-connected within a radius of one by order distance. Partial results are shown in Table 2 and Fig. 8.

The AIS data object (MMSI: 41348300) at 03:22 o’clock on 2 July 2017 is denoted by column A (key: 100950), whose core distance is 0.21542 and reachability distance is undefined. It is density-connected with nine adjacent AIS data objects (in output order, their MMSI are 413702090, 482458290, 373134000, 566047000, 413370750, 412436360, 413489830, 412148000, 413556320, according to Table 2) on the right side of Fig. 8 that constitute a cluster. Whereas, the same object (MMSI: 41348300) at 03:23 o’clock is denoted by column B (key: 100951), whose core distance is 0.04267 and reachability distance is also undefined. It is density-connected with twenty adjacent AIS data objects (in output order, their MMSI are 412436360, 412501270, 482458290, …, 413696320, according to Table 2) on the right part of Fig. 8, forming another cluster. The different clusters are separated by columns whose value is undefined.

Afterwards, the data object (MMSI: 412762270) at 03:23 o’clock is denoted by column C (key: 53087), whose core distance is 0.05716 and reachability distance is 0.0457. Column C is in the trough of the diagram, representing smaller order distance and bigger complexity with the surrounding objects. It can be considered as the more dangerous situation by VTS operator.

4.3.2 Complexity of marine traffic

It can be calculated by the Eq. (9) and data from Table 2,

$\displaystyle{\rm C}_{03:22}=\frac{1}{0.215}+\frac{1}{0.131}+\ldots+\frac{1}{0% .221}=81.176$ $\displaystyle{\rm C}_{03:23}=\frac{1}{0.043}+\frac{1}{0.043}+\ldots+\frac{1}{0% .425}=197.259$

The complexity of marine traffic at 03:23 o’clock is larger than that at 03:22 o’clock, indicating a process of complexity evolution. The complexity of marine traffic in specific area at exactly every minute (time slice) are calculated by Eq. (9). The statistics are illustrated as Table 3.

Table 3
Statistics of time slices with complexity of marine traffic

Range of the complexity of marine traffic	[0, 1)	[1, 25)	[25, 50)	[50, 100)	[100, 300)	[300, $+\infty$ )
Slice count	20448	15556	4393	2856	1262	125
Ratio	45.8%	34.8%	9.9%	6.4%	2.8%	0.3%

Totally, there are 44,640 minutes or time slices (31 days multiply 24 hours and multiply 60 minutes) and 20448 minutes or time slices at which the complexity of marine traffic is greater than or equal to 0 and less than 1. Therefore, the ratio is 45.8%. It can be calculated by the same way that, 80.6% (45.8% plus 34.8%) is between 0 and 25, 16.3% (9.9% plus 6.4%) is between 25 and 100, and 3.1% (2.8% plus 0.3%) is greater than 100.

The notion of “safety pyramid” was discussed as early as 1931 by Heinrich and was further developed by Bird based on his 1969 study of industrial accidents [27]. The bottom region of the pyramid was expanded to include events with no adverse effects, such as observation of a condition that has the potential of causing an incident, and the lower portion of the pyramid was identified as the “near-miss” region, which in down-up order are: “positive illusions, unsafe condition and unawareness, ignorance, complacency”, “foreshadowing events and observations”, “minor-loss events” [28]. In this paper, the “near-miss” region is divided into three parts, “low complexity”, “medium complexity” and “high complexity”. Furthermore, it is assumed that low complexity accounts for about 80%, medium complexity for about 16%, and high complexity for 4% or so at sea in the long term. Accordingly, we can measure the complexity of marine traffic in the research area that the value between 0 and 25 is relatively low (accounting for 80.6%), the value between 25 and 100 is medium (occupying 16.3%), and the value larger than 100 is in high level (taking the proportion of 3.1%). Thus, if the value (115) is computed according to given formula, it is highly risky, requiring VTS operator to pay extra attention.

In accordance with crew’s on-duty schedule, a day is divided into 6 equal periods. The average complexity of marine traffic in a period of time can be calculated by the Eqs (9) and (10). Its statistics are illustrated by Table 4.

Table 4

Statistics of the average complexity of marine traffic within periods of time

Periods of time	[00, 04)	[04, 08)	[08, 12)	[12, 16)	[16, 20)	[20, 24)
Average complexity of marine traffic	12.392	15.624	11.247	27.491	16.138	11.615

The average complexity of marine traffic reaches the summit between 1200 and 1600 while falling to the bottom between 0800 and 1200 in the waters, indicating that it is usually of high risk at afternoon and VTS operator should be cautious.

5. Conclusions

This research primarily focuses on the complexity modeling of vessel couple and clustering using data mining technology. A complexity model is proposed by employing intrinsic features so as to reflect pair-wise interactions between ships. The clustering method of ship to ship encountering risk is presented on the basis of complexity and risk factors analysis through proposing a new distance definition, in order to efficiently calculate the complexity of numerous ships in an area ultimately.

Actual AIS data within a month from Zhoushan North Sea of China are employed to demonstrate the model and the algorithm. The statistical results illustrate that the low complexity is between 0 and 25, the medium is between 25 and 100, and the high is larger than 100 in the area. Moreover, it can also be concluded that the average complexity of marine traffic peaks between 1200 and 1600 and tumbles to the lowest point between 0800 and 1200, indicating the most risky moment is in the afternoon while the least risky one is at morning in the waters.

Based on the complexity modeling of vessel couple and clustering using data mining technology, the research methodology may be beneficial to all marine traffic waters for safe marine operations.

References

Wen

Huang

Zhou

Yang

Xiao

and Wu

, Modelling of marine traffic flow complexity, Ocean Engineering 104 (2015), 500–510.

Meng

Weng

and Li

, Analysis of AIS-based vessel traffic characteristics in the Singapore Strait, 93rd Annual Meeting of Transportation Research Board (2014).

Pallotta

Vespe

and Bryan

, Vessel pattern knowledge discovery from AIS data: A framework for anomaly detection and route prediction, Entropy 15(6) (2013), 2218–2245.

Weng

and Xue

, Ship collision frequency estimation in port fairways: A case study, Journal of Navigation 68(3) (2015), 602–618.

Zhang

Goerlandt

Kujala

and Wang

, An advanced method for detecting possible near miss ship collisions from AIS data, Ocean Engineering 124 (2016), 141–156.

Westrenen

and Ellerbroek

, The effect of traffic complexity on the development of near misses on the North Sea, IEEE Transactions on Systems, Man, and Cybernetics: Systems 47(3) (2017), 432–440.

Zhang

Rachmawati

Rajabally

and Huang

, Exploiting AIS data for intelligent maritime navigation: A comprehensive survey, arXiv (2016). [Internet] available from: https://arxiv.org/abs/1606.00981.

Liu

Matwin

and Sydow

, Knowledge-based clustering of ship trajectories using density-based approach, IEEE International Conference on Big Data, 2014.

Yan

Wen

Zhang

and Yang

, Vessel movement analysis and pattern discovery using density-based clustering approach, IEEE International Conference on Big Data, 2016.

10.

Van Iperen

, Detection of hazardous encounters at the North Sea from AISdata, Proceedings of International Workshop of Next Generation NauticalTraffic Models, Shanghai, 2012, pp. 1–12.

11.

Chin

H.C.

and Debnath

A.K.

, Modeling perceived collision risk in port water navigation, Safety Science 47(10) (2009), 1410–1416.

12.

Goerlandt

Montewka

Kuzmin

and P Kujala, A risk-informed ship collision alert system: Framework and application, Safety Science 77 (2015), 182–204.

13.

Zhang

Goerlandt

Montewka

and Kujala

, A method for detecting possible near miss ship collisions from AIS data, Ocean Engineering 107 (2015), 60–69.

14.

Lee

Feron

and Pritchett

, Describing airspace complexity: Airspace response to disturbances, Journal of Guidance, Control, and Dynamics 32(1) (2009), 210–222.

15.

Geng

Huang

Wen

and Zhou

, Modelling of the Marine Traffic Situation Complexity, MATEC Web of Conferences 68 (2016), 1–5.

16.

Delahaye

and Puechmorel

, Air traffic complexity: Towards intrinsic metrics, 3rd USA/Europe Air Traffic Management R&D Seminar, Napoli, 2000.

17.

Tam

and Bucknall

, Collision risk assessment for ships, Journal of Marine Science and Technology 15 (2010), 257–270.

18.

Szłapczyński

, Evolutionary sets of safe ship trajectories with speed reduction manoeuvres within traffic separation schemes, Polish Maritime Research 1(81) (2014), 20–27.

19.

and Zhao

, Ship Collision Prevention and Watch Keeping (4rd), Dalian Maritime University Press, China, 2014, 166–167.

20.

and Hu

, Traffic structure-based air traffic complexity modeling, Journal of Transportation Systems Engineering and Information Technology 12 (2012), 166–173.

21.

Zhang

Liu

Zhang

Shi

and Cai

, A method for AIS track data compression based on Douglas-Peucker algorithm, Journal of Harbin Engineering University 36(5) (2015), 595–599.

22.

Zhao

Shi

and Yang

, Ship trajectories pre-processing based on AIS data, Journal of Navigation 71(5) (2018), 1210–1230.

23.

IEC, Maritime navigation and radiocommunication equipment and systems, Automatic Identification Systems (AIS) (2012).

24.

Ankerst

Breunig

M.M.

Kriegel

H.-P.

and Sander

, OPTICS: Ordering points to identify the clustering structure, ACM SIGMOD International Conference on Management of Data, 1999.

25.

Hansen

M.G.

Jensen

T.K.

Lehn-Schioler

Melchild

Rasmussen

F.M.

and Ennemark

, Empirical ship domain based on AIS data, Journal of Navigation 66 (2013), 931–940.

26.

Mehta

A.L.

Zaloom

V.A.

and Craig

B.N.

, Analysis of waterway transportation in Southeast Texas waterway based on AIS data, Ocean Engineering 121 (2016), 196–209.

27.

Bird

F.E.

and Germain

G.L.

, Practical loss control leadership (revised), Loganville, GA: Det Norske Veritas (1996).

28.

Oktem

U.G.

Wong

and Oktem

, Risk & regulation [Special issue on Close Calls, Near-Misses and Early Warnings], LSE Publication, 2010, pp. 12–13.

Study on complexity of marine traffic based on traffic intrinsic features and data mining

Abstract

Keywords

1. Introduction

2. Complexity model

2.1 Basic concept

2.2 Complexity analysis

2.2.2 Movement trend factor

3.2.1 Algorithm redefinition

3.3 Complexity of marine traffic

4.1 AIS data collection and reduction

4.2 Parameter settings

Table 1 AIS data list after reduction (part)

Table 2 The clustering result of improved OPTICS algorithm (part)

4.3.2 Complexity of marine traffic

Table 3 Statistics of time slices with complexity of marine traffic

References

Table 1
AIS data list after reduction (part)

Table 2
The clustering result of improved OPTICS algorithm (part)

Table 3
Statistics of time slices with complexity of marine traffic