Title Author Keyword ::: Volume ::: Vol. 19Vol. 18Vol. 17Vol. 16Vol. 15Vol. 14Vol. 13Vol. 12Vol. 11Vol. 10Vol. 9Vol. 8Vol. 7Vol. 6Vol. 5Vol. 4Vol. 3Vol. 2Vol. 1 ::: Issue ::: No. 4No. 3No. 2No. 1

Pattern Recognition of Ship Navigational Data Using Support Vector Machine

Joo-Sung Kim, and Jung Sik Jeong

Department of Maritime Transportation System, Mokpo National Maritime University, Mokpo, Korea
Correspondence to: Jung Sik Jeong, (jsjeong@mmu.ac.kr)
Received November 18, 2015; Revised December 24, 2015; Accepted December 25, 2015.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

A ship’s sailing route or plan is determined by the master as the decision maker of the vessel, and depends on the characteristics of the navigational environment and the conditions of the ship. The trajectory, which appears as a result of the ship’s navigation, is monitored and stored by a Vessel Traffic Service center, and is used for an analysis of the ship’s navigational pattern and risk assessment within a particular area. However, such an analysis is performed in the same manner, despite the different navigational environments between coastal areas and the harbor limits. The navigational environment within the harbor limits changes rapidly owing to construction of the port facilities, dredging operations, and so on. In this study, a support vector machine was used for processing and modeling the trajectory data. A K-fold cross-validation and a grid search were used for selecting the optimal parameters. A complicated traffic route similar to the circumstances of the harbor limits was constructed for a validation of the model. A group of vessels was composed, each vessel of which was given various speed and course changes along a specified route. As a result of the machine learning, the optimal route and voyage data model were obtained. Finally, the model was presented to Vessel Traffic Service operators to detect any anomalous vessel behaviors. Using the proposed data modeling method, we intend to support the decision-making of Vessel Traffic Service operators in terms of navigational patterns and their characteristics.

Keywords : Vessel Traffic Service, Traffic pattern, Route extraction, Decision-making support system, Support vector machine
1. Introduction

Based on Article 36 of the Maritime Safety Act (20), Article 28 of the Open Ports Rules and Regulations, and the IMO RESOLUTION A.857(20) [1], a Vessel Traffic Service (VTS) can be established and operated by relevant or authorized governments as a way to prevent accidents and protect marine environments. The goals of a VTS are ship safety and efficiency at sea. However, the risk of marine accidents is increasing owing to larger and faster ships and increased volumes of marine traffic. VTS operators (VTSOs) monitor the traffic situations and provid proper information 24 hours a day to prevent potential accidents. Although such tasks are extremely important aspects of VTS operations, they are made entirely based on the specific capabilities of the VTSO [2, 3]. The decision-making of a VTSO is a matter of how they collect and utilize significant amounts of information. Kim et al. [4, 5] tried to apply a ship’s dead reckoning position (DRP) on its traffic route; however, an advanced DRP requires an accurate traffic route model. Ship trajectories and navigational data are collected, stored, and used for traffic and accident analyses by VTS centers.

However, current traffic analyses have been conducted for simple reasons such as passage usage or frequency. In addition, traffic analyses within harbor limits have also been performed in similar ways in coastal areas [6?8]. In particular, the traffic patterns and navigational environments within harbor limits differ in different coastal areas owing to frequent changes in course and speed, a large density of vessels, the geographical conditions, construction of the port facilities, dredging operations, and so on. Depending on the ship destinations, different traffic patterns among the vessels that navigate the same passage exist, and there are few datasets classifying each specific leg [9?11]. Owing to these characteristics, it is necessary to develop methods applicable to particular harbor limits.

In this study, we present a data modeling method for vessels that are the last have called, the results of which can be calculated using a small dataset. A support vector machine-regression (SVM-R) was used to develop the optimal-route and navigational-pattern model. A K-fold cross-validation and grid search were used for selecting the appropriate parameters. A simulation was conducted using a virtual channel and ships to validate the proposed modeling method. The channel complexity used is similar to the circumstances found in actual harbor limits. A group of vessels was composed within the channel, where each vessel was given various changes in speed and course. As a result of machine learning, the optimal route and voyage data model were obtained. Finally, the proposed model was presented to VTSOs to detect anomalous vessel behaviors.

2. Support Vector Machine-Regression

An SVM is a tool used for classifying data consisting of a hyperplane, and generates the maximum margin among the data using a supervised learning method [12?14]. An SVM was originally developed for solving classification problems, but has recently been extended to address problems associated with regression and probability density estimations [15?17].

An SVM assumes that the training dataset, (x1, y1), . . . , (xN, yN) ∈ RM × R, are given. When learning datasets (N) are given in input space RM, a linear function f(x) that has spaces ? from output vector y against input vector x is

$f(x)=+b?with?w∈RM,?b∈R.$

As shown in Figure 1, when training datasets are given outside of space ?, a solution to the following optimization problem using slack variables ξi, $ξi*$ is required [12, 15]:

$min12?w?2+C∑i=1N(ξi+ξi*)subject?to?yi--b≤?+ξi+b-yi≤?+ξiξi,?ξi*≥0.$

Meanwhile, it is necessary to solve the separation of a nonlinear dataset. In general, a linearly separable condition may occur if the dataset transfers to a higher-level space using a nonlinear transfer function. Figure 2 shows a case of linear data that cannot be classified [12]. Non-detachable data are transferred to a non-linear case using a non-linear transfer function (mapping) $zk=(xk,xk2)$.

For two-dimensional data, it is possible to obtain a linearly separable plane when mapping as a three-dimensional space. The kernel function is defined as follows:

$K?(x,x′)=φ(x)Tφ(x′).$

As shown in Figure 3, function f(x) is composed in a nonlinear form but can be transformed into a linear form using a kernel function [12, 15]:

$y=∑i=1Nαi+αi*)·<φ(xi),φ(x)>+b=∑i=1N(αi+αi*)·K(xi,x)>+b.$

The types of kernel functions include splines, polynomials, hyperbolic tangents, sigmoid functions, and radial basis functions (RBFs) [18]. In this study, we used an RBF, which is generally known to have an excellent performance capability:

$K?(xi,xj)=exp?(-?xi-xj?2σ2).$
3. Data Extraction

Data extraction is a three-step process:

1. Data collection

2. Data classification

3. Data modeling

In this section, we present the proposed data modeling method. The collected trajectory data are categorized as regional separations and the separated data are classified as particular routes based on the gate line at each passage [19, 20]. The divided datasets need to be converted into a type of column vector to match the SVM-R algorithm before the modeling process is conducted. The modeling process can be described through the following steps [18]:

1. 1) Dataset transformation

2. 2) Data scaling

3. 3) Kernel function selection

4. 4) Parameter selection

1. 4?1) K-fold cross-validation

2. 4?2) Grid search

3. 5) Selected model training

4. 6) Model validation

For the above modeling process, it is necessary to separate the datasets into sub-datasets and transform them into sets of column vectors such as time T(n) = [t1, t2, ···, tn]T, longitude Lon(tn) = [x(t1), x(t2), ···, x(tn)]T, latitude Lat(tn) = [y(t1), y(t2), ···, y(tn)]T, course Co(tn) = [c(t1), ···, c(tn)]T, and speed Spd(tn) = [s(t1), s(t2), ···, s(tn)]T.

According to Hsu et al. [18], scaling prior to applying an SVM is very important. The main advantage of scaling is to avoid attributes within greater numeric ranges dominating those within smaller numeric ranges. Another advantage is to avoid numerical difficulties during the calculation.

The vector T(n) = [t1, t2, ···, tn]T can be transformed into

$Tscaling=[(t1-t1)/(tk-t1),(t2-t1)/(tk-t1),?,(tk-t1)/(tk-t1)]T$

after scaling from zero to 1. The other vectors (i.e., Lon(tn), Lat(tn), Co(tn), and Spd(tn)) can also be transformed into

$Tscaling=T-Min[T]Max[T]-Min[T].$

For the optimal parameter search, the training sets need to be divided into ‘k’ sub-sets of equal size. One sub-set is tested using the algorithm and trained on the remaining ‘k-1’ subsets. The cross-validation procedure can prevent an over-fitting problem.

Figure 4 shows a k-fold cross-validation, which can be explained as below:

$Minvalidation?error=Min?(q1+q2+q3+?+qkk).$

As a result of each instance, a validation errors (q1, ···, qk), and the minimum validation error can be found.

4. Simulation

We reproduced a curved virtual channel and ship trajectories with various characteristics. The circumstances are similar with the actual harbor limits. As shown in Figure 5, the channel is in the form of a letter ‘R’ and the ship tracks are within the channel. Before conducting the simulation, the whole datasets were separated into sub-datasets and transformed into sets of column vectors. The simulation conditions are as follows.

1. Sharp curves

2. Narrow areas

3. Various directions

4. High density

5. Different course changes

6. Different speeds

7. Navigating within the channel only

8. Same starting and end points

9. No detours or short-cuts through the channel

The separated datasets are divided into sub-datasets again, which consist of a validation dataset and four learning datasets. A 5-fold cross-validation and grid search were conducted to select the optimal parameters, and an RBF was used as a kernel function. The results of the calculations are listed in

As shown in Figures 6(left) and 7(left), each sub-dataset has a certain pattern, but the datasets are necessary to be adjusted because the ships are sailing within the same location but at different speeds.

After scaling the data, machine learning was conducted for whole datasets. As a result of the learning, red curves were obtained, as shown in Figures 6(right) and 7(right).

As shown in Figure 8, the optimal route is obtained after modeling. The entire datasets were learned to build the model by applying the selected parameters. The data conversion and SVM-R were performed for all sub-datasets.

The final model can be adjusted based on the number of training datasets or samplings. It is also possible to reduce the calculation time of the modeling process by downsizing the number of support vectors used.

As shown in Figure 9, the course-change model was obtained through machine learning. The extracted navigational model can be compared to data values for changes in course and speed at a certain position through a combination with the coordinates. It can also be used for preventing accidents by identifying the anomalous movements of ships and predicting changes in navigation before they occur. If any deviation in a ship’s position or navigational data, such as course and speed, occurs it means that the uncertainty about the ship’s future position is increasing. Therefore, the proposed model can be used for the prediction of future navigation.

5. Conclusion

It is important to understand a ship’s navigational intention and its location in order to predict traffic situations and organize traffic plans and determine dangerous traffic situations. In particular, the identification of a ship’s anomalous navigational behaviors within VTS areas is available only through the constant monitoring of traffic states by VTSOs. In addition, the workload and stress levels of VTSOs are increasing in VTS areas owing to a high density of traffic and narrow maritime waters. This study was conducted to prevent accidents to marine traffic by reducing errors of VTSOs caused by individual differences in ability. The proposed method can be used for identifying a ship’s deviation and irregular changes in speed and course. It may also be used for supporting the decision-making of a VTSO under complex situations by improving a ship’s dead reckoning position. Moreover, it is expected to assist a proper Traffic Organization Service (TOS) or Information Service (INS) when multilateral relationships are encountered in a VTS area. As a future study, we plan to develop additional methods that can be applied to a large number of ships with different types and navigational environments. Additionally, an application needs to be developed for investigating marine accident in VTS areas.

Acknowledgements

This work was supported by ETRI through Maritime Safety & Maritime Traffic Management R&D Program of the Ministry of Public Safety and Security/Korea Institute of Marine Science & Technology Promotion (No. 2009403, Development of next generation VTS for maritime safety).

Figures
Fig. 1.

?-Insensitive loss function.

Fig. 2.

Non-detachable data mapping to two-dimensional space.

Fig. 3.

Kernel functions for transforming data into higher dimensional feature space.

Fig. 4.

K-fold cross-validation.

Fig. 5.

Virtual curved channel and ship tracks.

Fig. 6.

Plotted latitude components (left), and results of machine learning after scaling (right). SVM, support vector machine.

Fig. 7.

Plotted longitude components (left), and results of machine learning after scaling (right). SVM, support vector machine.

Fig. 8.

Extracted traffic route.

Fig. 9.

Course changes of extracted route (upper), course data of all ships (middle), and extracted course model (lower).

TABLES

### Table 1

Parameter selection results

ge012345
64.46624.27304.26204.76945.23016.2994
74.55014.23474.21484.69515.22976.4380
84.61374.24764.19774.62565.64868.1237
94.66534.28054.21114.81376.22009.2866
104.86534.44744.44715.09906.682410.0518

References
1. International Maritime Organization (1997). Guidelines for Vessel Traffic Services [IMO Resolution A857(20)]. London: International Maritime Organization
2. Kim, JS, Jeong, JS, and Park, GK (2013). Prediction table for marine traffic for vessel traffic service based on cognitive work analysis. International Journal of Fuzzy Logic and Intelligent Systems. 13, 315-323.
3. Kim, JS, Jeong, JS, and Park, GK (2014). Utilization of planned routes and dead reckoning positions to improve situation awareness at sea. International Journal of Fuzzy Logic and Intelligent Systems. 14, 288-294.
4. Kim, JS, Jeong, JS, and Park, GK 2014. Application of planned routes and dead reckoning positions for supporting decision-making of vessel traffic services., Proceeding of the International Symposium on Advanced Intelligent Maritime Safety and Technology, Mokpo, Korea, pp.121-124.
5. Kim, JS, Jeong, JS, Park, GK, Jung, JY, Lee, JH, Oh, T, and Han, H 2015. Extraction of ship’s tracking model for improving situation awareness at vessel traffic service areas., Proceeding of the Korean Institute of Intelligent Systems (KIIS) Spring Conference, Ansan, Korea, pp.51-52.
6. Hong, T (2014). Development of a system for transmitting a navigator’s intention for safe navigation. International Journal of Fuzzy Logic and Intelligent Systems. 14, 130-135.
7. Kim, EK, Jeong, JS, Park, GK, and Im, NK (2012). Characteristics of ship movements in a fairway. International Journal of Fuzzy Logic and Intelligent Systems. 12, 285-289.
8. Jeong, JS, Kim, KI, and Park, GK (2012). A quantitative collision probability analysis in port waterway. Journal of Korean Institute of Intelligent Systems. 22, 373-378.
9. Moon, BT, Ryu, YH, and Joe, GJ (2012). Study on software architecture for intelligent vessel navigation analysis. Journal of Korean Institute of Intelligent Systems. 22, 583-589.
10. Kim, KI, Jeong, JS, and Park, GK (2013). Assessment of external force acting on ship using big data in maritime traffic. Journal of Korean Institute of Intelligent Systems. 23, 379-384.
11. Kim, DY, Park, GK, and Kim, HY (2014). A study on the ship information fusion with AIS and ARPA Radar using by blackboard system. Journal of Korean Institute of Intelligent Systems. 24, 16-21.
12. Gunn, SR (1998). Support vector machines for classification and regression. UK: School of Electronics and Computer Science, University of Southampton
13. Kim, GH, Kim, YW, Lee, SJ, and Jeon, GJ (2010). A hierarchical clustering method based on SVM for real-time gas mixture classification. Journal of Korean Institute of Intelligent Systems. 20, 716-721.
14. Choi, HH, Lee, GH, Kim, JG, Joo, YB, Choi, BJ, Park, KH, and Yun, BJ (2009). A defect inspection method in TFT-LCD panel using LS-SVM, ””. Journal of Korean Institute of Intelligent Systems. 19, 852-859.
15. Vapnik, VN (1998). Statistical Learning Theory. New York, NY: Wiley
16. Jo, TH (2008). Modified version of SVM for text categorization. International Journal of Fuzzy Logic and Intelligent Systems. 8, 52-60.
17. Kim, MS, and Lee, SY (2004). Pattern classification for biomedical signal using BP algorithm and SVM. Journal of Korean Institute of Intelligent Systems. 14, 82-87.
18. Hsu, CW, Chang, CC, and Lin, CJ (2003). A practical guide to support vector classification. Taipei, Taiwan: Department of Computer Science, National Taiwan University
19. Kim, JS, and Jeong, JS 2015. Vessel trajectory and route detection in vessel traffic service areas using machine learning theories., Proceedings of International Symposium on Advanced Intelligent Maritime Safety and Technology, Daejeon, Korea, pp.142-145.
20. Kim, JS, Jeong, JS, and Jung, JY 2014. Recreating ship’s reference routes to predict traffic situations in vessel traffic service areas., Proceeding of the Korean Society of Marine Environment and Safety (KOSOMES) Fall Conference, Busan, Korea, pp.295-297.
Biographies

Joo-Sung Kim is a Ph.D. candidate in International Maritime Transportation Sciences at Mokpo National Maritime University in Korea, and a VTSO at Kyeong-in VTS Center in Korea. His research interests include maritime traffic engineering, ship collision avoidance, maritime information and communication network. He received his B.S. degree in Nautical Science from Mokpo National Maritime University in Korea in 2004 and his M.S. degree in International Maritime Transportation Sciences from Mokpo National Maritime University in Korea in 2014. His research areas include intelligent system, fuzzy system, human factors engineering, work analysis, vessel traffic services, maritime transportation system, etc.

E-mail: jskim81@korea.kr

Jung Sik Jeong is a professor in the Department of International Maritime Transportation Sciences at Mokpo National Maritime University in Korea. His research interests include intelligent system, fuzzy system, intelligent navigation control system and maritime information. He received his B.S. degree in Nautical Science from Korea Maritime University in 1987, his M.S. degree in Communication and Electronic Engineering from Korea Maritime University in 1993, and his Ph.D. degree in Electrical and Electronic Engineering from Tokyo Institute of Technology in 2001. He worked at Korea Telecom at 1996. His research areas include maritime traffic engineering, ship collision avoidance, maritime information and communication network, etc.

E-mail: jsjeong@mmu.ac.kr

March 2019, 19 (1)
Full Text(PDF) Free

Services

Funding Information