# Abnormal Ship Behavior Detection Based on AIS Data
## 3 Materials and Methods
### Detection of Abnormal Ship Behavior Based on Spatial Attributes  
#### 3.2.1 Maritime Route Extraction Based on AIS Data  
The situation is also more complex for sea lanes, which are not constructed like roads on land and are, by contrast, subject to dynamic changes due to external factors such as climate, currents, and accidents. Detection of the maritime routes will help to provide the newest routes and traffic information for ships. In order to model the ship behavior pattern more precisely, we first extracted the structure of the maritime routes based on the AIS data. Although the AIS data have the advantages of fast updates and a very large geographical range, due to their puncture reception problem, they are also characterized by poor data quality and data density in different regions of great difference. These issues are also a great challenge for the renewal and normalization of sea lanes. Therefore, we used the extraction method for road networks for offshore road networks [32]. This method generates a road network from trajectory point data based on the principal graph structure learning and tree linking strategy. It does not depend on data pretreatment, and the noise, low sampling rate, and non-uniformity of the density of the data's distribution can be minimized, allowing the robust extraction of the feature structure of the maritime traffic routes. It was considered that most ships would travel close to the centerlines of the routes (i.e., the centerline of our final generated road map would be consistent with the peak point of the trajectory point), so we could express the geometric topology of the real-world maritime routes approximately in the form of an undirected graph \(G\). In this study, the structure of the maritime routes was abstracted into the following form:  
\[G_{0}=\left(V_{0},E_{0},W_{0}\right) \tag{1}\]  
where \(V_{0}\) represents the node of the graph, \(E_{0}\) represents the edge of the graph, and \(W_{0}\) represents the connection matrix of the graph in Equation (1). After inputting a set of trajectory points, we hoped to obtain the best map that could fit the set of trajectory points, namely \(G_{opt}=\left(V_{opt},E_{opt},W_{opt}\right)\). Considering that the maritime route is usually a smooth straight line or curve, the optimal main graph should meet the following two conditions: (1) the distance from all the points to the figure shall be as short as possible, and (2) the edges of the graph are straight or rounded, all the edges are as small as possible, and the main graph representing the basic maritime routes shall be as regular as possible. We found that the reversed graph-embedding technology could satisfy the above two conditions to obtain the best main graph. In order to better understand the reversed graph-embedding technology, we need to understand what the graph-embedding technology is. The graph-embedding technique is a  
Figure 4: Diagram before and after track data preprocessing. feature transformation operation that constructs the relationship of input spatial data from the perspective of a graph and then reflects the flow pattern structure of the data. Laplacian Eigenmaps is one of the common graph-embedding methods. The main idea of Laplacian Eigenmaps is that if two sets of data \(i\) and \(j\) are very close to each other, they should be as close as possible in the target subspace after dimension reduction. The structure of the maritime routes is a kind of \"graph\" structure, so our task was to use a \"graph\" to fit the structure of the maritime routes (i.e., to embed and then express the road network structure in the form of a graph). Suppose that \(\mathsf{X}=\{\mathsf{x}1,\mathsf{x}2,\ldots\mathsf{x}\mathsf{N}\}\) represents the input spatial trajectory point data. The point set of potential space \(\mathsf{Y}=\{\mathsf{y}1,\mathsf{y}2,\ldots\mathsf{y}\mathsf{N}\}\) denotes the node of \(G=(\mathsf{V},\mathsf{E},\mathsf{W})\) and can fully express the data distribution characteristics of \(\mathsf{X}\).