Sage Journals: Discover world-class research

Abstract

Finding the potential spatiotemporal co-occurrence behavior patterns of large groups of ships while sailing is a challenging problem of great importance in many real-world applications. Through spatiotemporal data mining of ship trajectory data, route rules, navigation behavior, and potential anomalies can be mined, providing important support for maritime management, navigation safety, and emergency response. With the analysis and mining of ship trajectory data in some hotspot sea areas, this paper introduced a ship spatiotemporal co-occurrence pattern mining algorithm based on association rules. Based on the research of data model and the judgment criterion of spatio-temporal co-occurrence law, such concepts as candidate set, frequency set, and instance set are introduced together with the key procedure of algorithm, including pruning and pasting of candidate sets, screening of instance sets, definition of association reasoning, and association rule mining. Subsequently, the process of implementing the spatiotemporal co-occurrence pattern mining algorithm is devised. In the end, the algorithm is verified by taking the automatic identification system data of ships in hotspot sea areas as the source data. The proposed algorithm can find several ship combinations with spatiotemporal co-occurrence regularity in these hotspot sea areas, and the association rules on the co-occurrence of several ships. The performance of the proposed algorithms is illustrated on a real-world ship trajectory database and made a detailed comparative analysis. The results are very promising in terms of computational time. The experimental results show that our algorithm can effectively identify the motion patterns and behavior characteristics of ships, which provides an important reference and support for Marine traffic management, ship safety and Marine environment protection. The research results of this paper are of great significance for improving the efficiency and safety of maritime traffic, and also provide new ideas and methods for further research in related fields.

Keywords

Ship trajectory data mining spatiotemporal co-occurrence patterns association rule mining

Introduction

In the modern world history, great powers must be strong in ocean around the world. Presently, ocean has gradually become the fundamental and restriction for the sustainable development of China. China’s national maritime rights and interests depend on ocean security. With the implementation of “the Belt and Road” national development initiative, “Smart Ocean” has been gradually brought up on the agenda as a program mainly aiming to combine modern intelligent techniques and big data technology with marine equipment and activities of China. Supported by an independent, secure, and reliable marine cloud environment, all kinds of marine information resources are integrated to achieve the all-directional three-dimensional perception, extensive interconnection, mass data sharing, knowledge analysis and decision, and in-depth smart service related to ocean. In this way, an integrated solution can be developed to enhance the maritime military, marine management and control, and ocean development capabilities.¹

In recent years, people have been constantly improving the capability of gathering the situation information of ships at sea with the rapid development and wide application of global positioning, sensor networking, and wireless communication technologies. According to statistics, more than 50,000 ships travel at sea every day.² These large objects moving in a complicated marine environment generate mass data under the support of the improving sensor technology. Marine location big data (LBD) refers to the data of marine geographical and human sociological information with spatial and temporal identifiers, including basic electronic charts and electronic navigation charts, real-time navigation information related to ship location, and real-time information of ship-borne equipment during navigation. Automatic identification system (AIS) has been extensively spread, so that the mass data of ship navigation in unified format is taken as an important information source for marine situation analysis and mining system. On a daily basis, around 4 GB of AIS data are collected by satellites and shore-based stations worldwide, generating up to 1.4 terabytes of AIS data in a year.³ The information is lastingly recorded to accumulate the mass data of historical and spatiotemporal ship trajectories in various fields. The trajectory data has not only contained a record of activities for each single moving object, but also embodied the hidden knowledge regarding activity regularities, kinematic features, behavioral patterns, and regional hotspots of population.⁴ Analyzing the mass data of ship trajectory and mining the hidden knowledge therein are of great significance to improving the construction of marine transportation facilities, enhancing maritime regulation capability, and defending national ocean security.

It is one of the hot research fields to analyze the ship trajectory data and to mine the ship motion pattern. Ship trajectory data refers to the data that records the ship’s moving path in the ocean or inland waters, which contains the ship’s position, speed, heading, and other key information. These data are not only of great significance to maritime management, safety monitoring, and navigation planning, but also provide rich information resources for Marine scientific research, resource development, and environmental protection. With the continuous growth of global maritime traffic and the development of ship automation technology, the scale and complexity of ship trajectory data are also increasing rapidly.

Spatiotemporal data mining is a technique for pattern recognition, correlation analysis and prediction using spatiotemporal information, which plays a vital role in ship trajectory data analysis. Through spatiotemporal data mining of ship trajectory data, route rules, navigation behavior, and potential anomalies can be mined, providing important support for maritime management, navigation safety, and emergency response.⁵ This paper will discuss the spatiotemporal data mining technology of ship trajectory data, including key technologies such as data preprocessing, trajectory pattern recognition, and anomaly detection, in order to deeply understand the characteristics and rules of ship trajectory data and mine the useful information contained therein, so as to provide scientific basis for decision-making and management in the maritime field.

With the wide application of Automatic Identification System (AIS) and other technologies, the generation of large amounts of ship trajectory data provides a valuable opportunity to study the movement behavior of single ships and the collective movement patterns at sea. These data not only contain the spatio-temporal information of ships, but also cover multi-dimensional information such as ship type, speed, and width, which makes it possible to conduct in-depth analysis of ship behavior. However, how to mine valuable co-occurrence patterns from these massive spatio-temporal data is still an urgent problem to be solved.

This paper aims to develop an efficient algorithm for mining the spatio-temporal co-occurrence patterns of ships in order to discover the co-occurrence patterns of ships in space, time, and other dimensions from AIS data. Through this pattern mining, the frequent encounter situation of different ship types in a specific area can be revealed, so as to provide a scientific basis for maritime traffic safety supervision. In addition, the algorithm will also be combined with the Hadoop platform to realize parallel processing to improve the computational efficiency and ensure that it can process large-scale spatio-temporal data sets. Finally, through the in-depth analysis of ship trajectory data, this study hopes to provide more accurate maritime traffic situation assessment and decision support for the shipping industry. This paper first introduces the background and significance of the research. In the third section, the theoretical model of spatio-temporal co-occurrence is established. In the fourth section, the spatio-temporal co-occurrence mining algorithm of ship trajectory is designed. In the fifth section, the algorithm is verified by a large number of AIS data in the hot sea area, and by adjusting the parameter Settings, the results of the algorithm are analyzed in detail. Finally, the conclusion of the paper is given.

Related work

In recent years, with the increasing of Marine traffic and the increasing importance of Marine environmental protection, the research on ship spatio-temporal co-occurrence pattern mining algorithms has attracted much attention. At present, many scholars have carried out in-depth research in this field. Among them, some researches focus on the application of data mining and machine learning techniques, such as clustering analysis based on trajectory data, pattern recognition, and anomaly detection. Other studies focus on algorithm optimization and improvement to improve the accuracy and efficiency of mining algorithms. At the same time, some researches are devoted to combining the ship spatio-temporal co-occurrence pattern mining algorithm with other related fields, such as intelligent transportation systems and Marine resources development, so as to expand the application range and depth of the algorithm.

Spatiotemporal co-occurrence pattern mining is an important research focus of motion pattern mining for moving objects. Co-occurrence refers to the state of motion in which two or more objects or instances exist in a neighborhood both spatially and temporally.⁶

The spatiotemporal co-occurrence pattern mining technology based on ship trajectory data is of great significance in the maritime field. This technique can reveal the spatiotemporal association patterns in ship trajectory data, that is, the co-occurrence trends or correlations between different ships in time and space, so as to help analysts better understand maritime traffic rules, navigation behaviors and potential risks. Through the mining of spatiotemporal co-occurrence patterns, the possible relationships, agglomeration phenomena or frequent trajectory patterns between ships can be found, which provides important support for ship control, route planning, and emergency response.⁷

Compared with the clustering based mining methods, the spatiotemporal co-occurrence pattern mining technology based on ship trajectory data pays more attention to mining the spatiotemporal correlation between different ships, rather than simply dividing ships into the same category or cluster. The spatiotemporal co-occurrence pattern mining method can take into account the interaction between ships and the spatiotemporal evolution law, help analysts to deeply understand the complex relationship behind the ship trajectory data, so as to better grasp the dynamic changes and potential risks of maritime traffic. Therefore, the application of spatiotemporal co-occurrence pattern mining technology based on ship trajectory data in the maritime field is of great significance, which can provide more in-depth and comprehensive information support for navigation safety management, route planning optimization, and maritime supervision.

The spatiotemporal co-occurrence mining with the mass data of ship trajectory is a typical problem in the motion pattern mining of ships, and greatly valuable in practice. For instance, smuggling ships normally navigate in a co-occurrence behavioral pattern for a period, and pirates may follow a target ship closely for a long time before taking any illegal action. In the antiterrorist and military fields, maritime military operations often involve ships in formation during navigation. Different formations reflect different operations. Frequently, a great number of ships from different countries and organizations may be disguised in different identities but jointly engage in a specific mission at sea. Facing such special maritime operations, spatiotemporal co-occurrence pattern mining can be adopted to perform the association analysis of AIS trajectory data from many ships, so as to provide the technical support for the operations planning and tactical activities in the military field.⁸ Liu et al.^9,10 introduced an AIS data-driven trajectory prediction framework, whose main component is a long short term memory (LSTM) network, to predict the spatiotemporal vessel trajectories. The main benefit of the proposed framework is that it takes full advantages of DBSCAN-based outliers detection and BLSTM-based trajectory reconstruction. To analyze the problem of taxi fraud, Belhadi et al.¹¹ proposed a two-phase trajectory anomaly detection model. The first phase determines the individual trajectory outliers by computing the distance of each point in each trajectory, whereas the second identifies the group trajectory outliers by exploring the individual trajectory outliers using both feature selection and sliding windows strategies. Veena et al.¹² proposed a generic model of fuzzy frequent spatial pattern that may exist in a quantitative spatiotemporal database. An neighbor-hood pruning has been introduced to effectively reduce the search space and the computational cost of finding the desired itemsets. Bommisetty et al.¹³ introduced an efficient algorithm to find spatial high utility itemsets in a high-dimensional spatiotemporal database, which contain two novel concepts “spatially closed utilities of an itemset” and “spatially non-closed utilities of an itemset.”

Researchers have proposed a variety of methods and models for mining spatiotemporal co-occurrence patterns of ships. For example, the analysis of AIS trajectories using co-clustering algorithms can discover co-occurrence patterns of ships in space, time, and other dimensions.¹⁴ In addition, based on the technologies of satellite navigation, spatio-temporal entity, Web-GIS, and spatial database, the key information of ships, such as basic attributes, real-time location, historical trajectory, association relationship, and running state, can be extracted and entity reorganized, so as to construct ship entity resources and establish a ship trajectory visual analysis system.¹⁵ In order to improve the mining efficiency and accuracy, researchers have proposed a GRU (gated recurrent unit) ship trajectory prediction method based on spatio-temporal attention mechanism, which significantly improves the accuracy of trajectory prediction by enhancing the ability of spatio-temporal information data.¹⁶

In addition, significant progress has been made in ship behavior feature mining and prediction based on AIS data. The research shows that through big data mining and AI analysis, the ship portrait can be formed, the ship operation behavior can be deeply analyzed, and the ship trajectory can be analyzed in detail.¹⁷ These studies not only help to improve the ability of water traffic safety supervision, but also provide support for the modeling and trend prediction of shipping network dynamics.⁸

In general, the research on ship spatio-temporal co-occurrence pattern mining algorithms has made some progress, but there are still some challenges and problems to be solved, such as data quality, algorithm efficiency, and real-time performance, which need further discussion and improvement. Future research is needed to further optimize the algorithm and improve the mining efficiency and accuracy to better serve the development of maritime traffic safety and intelligent navigation systems.

In this paper, a novel method is proposed to detect the potential spatiotemporal co-occurrence behavior patterns of large groups of ships while sailing. The ship’s spatiotemporal co-occurrence model is different from the vehicle’s or person’s spatiotemporal co-occurrence model. It can detect more subtle patterns of ship behavior, and can support the discovery of more ships with co-occurrence patterns.¹⁸ The main contributions of this work are summarized as:

1) According to the characteristics of ship trajectory, the data model of ship co-occurrence unit sea area is put forward, and the judgment criterion of spatio-temporal co-occurrence law is studied.

2) Based on the above data model and judgment criterion, such concepts as candidate set, frequency set, and instance set are introduced together with the key procedure of algorithm, including pruning and pasting of candidate sets, screening of instance sets, definition of association reasoning, and association rule mining. Subsequently, the process of implementing the spatiotemporal co-occurrence pattern mining algorithm is devised.

3) In the end, the algorithm is implemented by taking the automatic identification system data of ships in hotspot sea areas as the source data. We obtain several ship combinations with spatiotemporal co-occurrence regularity in these hotspot sea areas, and the association rules on the co-occurrence of several ships.

4) The performance of the proposed algorithms is illustrated on a real-world ship trajectory database and made a detailed comparative analysis. The results are very promising in terms of computational time. The results gathered in this paper can be linked to future enhancements using a variable time window function for future work.

Model preparations

Before describing the spatio-temporal co-occurrence algorithm of ship trajectories, a suitable theoretical model should be established as a basis. In this section, the co-occurrence unit sea area model of hot spot sea area is established, and then the concepts of spatio-temporal co-occurrence phenomenon judgment criterion and spatio-temporal co-occurrence regularity judgment criterion are elaborated in detail, which are the execution basis of the spatio-temporal co-occurrence algorithm of ship trajectory. Then, the conceptual models of candidate set, frequent set, and instance set are defined, which are the mathematical basic concepts of the ship trajectory spatio-temporal co-occurrence algorithm. The subsequent research algorithm is a large number of complex operations of these models.

Co-occurrence unit sea area

It is assumed that a hotspot sea area $k$ is identified, and its longitude and latitude spans are denoted by $Δ λ_{k}, Δ φ_{k}$ . The longitude span $Δ λ_{k}$ of the sea area $k$ is equally divided into $n_{k}$ , while its latitude span $Δ φ_{k}$ is equally divided into $m_{k}$ . All parameters are made to satisfy

\frac{Δ λ_{k}}{n_{k}} = Δ λ_{ρ}, \frac{Δ λ_{k}}{n_{k}} = Δ λ_{ρ}

(1)

where $Δ λ_{ρ}$ is the threshold of longitude span; and $Δ φ_{ρ}$ is the threshold of latitude span. If a ship $a$ and a ship $b$ pass a sea area with the longitude and latitude spans $Δ λ_{ρ}, Δ φ_{ρ}$ within a time period $Δ t$ , it is believed that there is a short distance between two ships when $Δ λ_{ρ}, Δ φ_{ρ}$ are small enough, so that they are more possible to spatially associate with each other. Hence, a sea area with the longitude and latitude spans $Δ λ_{ρ}, Δ φ_{ρ}$ is defined as a co-occurrence unit sea area.¹⁹

If the time period $Δ t$ is short enough, it is believed that both ships are temporally associated as well. At this time, the time period $Δ t$ is regarded as a time slot.

Spatiotemporal co-occurrence phenomenon judgment criterion

It is assumed that a ship $a$ and a ship $b$ pass a co-occurrence unit sea area within a time period $Δ t$ . If the time period $Δ t$ is short enough, and the longitude and latitude spans $Δ λ_{ρ}, Δ φ_{ρ}$ of the co-occurrence unit sea area are small enough, it is believed that both ships are temporally and spatially associated.²⁰ This is regarded as a spatiotemporal co-occurrence phenomenon of the ship $a$ and the ship $b$ within the time slot $Δ t$ .

Spatiotemporal co-occurrence regularity judgment criterion

If two ships $a$ and $b$ experience a spatiotemporal co-occurrence phenomenon in very rare cases, it is impossible to judge a highly potential association between them. In other words, it is not believed that there is spatiotemporal co-occurrence regularity between them. The spatiotemporal co-occurrence regularity exists between two ships $a$ and $b$ only if the number and probability of spatiotemporal co-occurrences are high within a surveyed time period $t_{s} ~ t_{e}$ .²¹

$k$ -element candidate set

In the AIS data, each ship has its unique identification (ID) number. If it is necessary to find out the spatiotemporal co-occurrence regularity between $k$ ships, the set of identifications for these ships is defined as a $k$ -element candidate set, that is, ${X}^{k} = {X_{1}, X_{2}, \dots, X_{m}}^{k}$ , where $X_{j}$ is a ship ID number in the candidate set; and $m = 1, 2, \dots, k$ . It is assumed that the $j$ th candidate set among all $k$ -element candidate sets is ${X}_{j}^{k}$ , and the total number of $k$ -element candidate sets is $| X^{k} |$ .

Hence, a $k$ -element candidate set means that there is possibly spatiotemporal co-occurrence regularity between $k$ ships in a candidate set.²⁰

$k$ -element frequency set

If the survey finds the spatiotemporal co-occurrence relationship between the ships with ID number in a $k$ -element candidate set, the $k$ -element candidate set ${X}^{k}$ is defined as a $k$ -element frequency set ${Z}^{k}$ :

{Z}^{k} = {Z_{1}, Z_{2}, \dots, Z_{l}}^{k}

(2)

where $Z_{l}$ is a ship ID number in the candidate set, and $l = 1, 2, \dots, k$ .

Hence, a $k$ -element frequency set means that there is actually spatiotemporal co-occurrence regularity between $k$ ships in a candidate set.

$k$ -element instance set

In order to confirm a $k$ -element candidate set ${X}^{k}$ , it is assumed that all $k$ -element candidate sets ${X}^{k}$ form a union ${B}^{k}$ , that is, an aggregate set of ship ID numbers in all $k$ -element candidate sets,

{B}^{k} = \cup_{j = 1}^{| X^{k} |} {X}_{j}^{k}

(3)

A hotspot sea area is equally divided into several co-occurrence unit sea areas with the same time slot $Δ t$ , longitude and latitude spans. For each co-occurrence unit sea area, a set of ship ID numbers in each time slot is denoted by ${Y}^{0}$ , which is called as 0-element instance set. Among these sets, the $i$ th 0-element instance set is denoted by ${Y}_{i}^{0}$ . The $k + 1$ -element instance set is obtained from the $k$ -element instance set in the following rule:

After traversing all ${Y}_{i}^{k}$ , if ${Y}_{i}^{k} \cap {B}^{k} = \emptyset$ , there is ${Y}_{i}^{k} \cap {X}_{j}^{k} = \emptyset$ to any $k + 1$ -element candidate set ${X}_{j}^{k}$ , so that the set ${Y}_{i}^{k}$ is deleted; if ${Y}_{i}^{k} \cap {B}^{k} \neq \emptyset$ , the set ${Y}_{i}^{k}$ is retained. After traversal, the retained ${Y}_{i}^{k}$ are renumbered and sequenced to obtain a new set of ${Y}_{i}^{k + 1}$ , which is a $k + 1$ -element instance set ${Y}^{k + 1}$ .

The $k$ -element instance set means a union of all instance sets having intersection with a $k$ -element candidate set. These instance sets are valuable to the research of spatiotemporal mining. On the contrary, the instance sets having no such intersection obviously make no contribution to the mining of spatiotemporal co-occurrence regularity.²² For this reason, the redundant data must be removed in each iterative cycle, so as to reduce computation.

Algorithm design

A recursive structure is adopted for the spatiotemporal co-occurrence pattern mining algorithm based on association rules. It mainly involves five steps such as pruning candidate sets, pasting frequency sets, screening instance sets, defining association reasoning, and mining association rules. The algorithm is implemented in the following procedure: a $k$ -element candidate set is pruned to generate a $k$ -element frequency set, and find out the $k$ -element ship combinations with spatiotemporal co-occurrence regularity; the $k$ -element frequency set is pasted to generate a $k + 1$ -element candidate set, and complete the preparation for iterative cycle; screening is carried out to delete every instance set having no association with all $k$ -element candidate sets from the $k$ -element instance set, in order to simplify computation; the possible association reasoning between $k$ -element ship combinations in the $k$ -element frequency set is found according to the definition of association reasoning; association rule mining is performed to verify the sufficient confidence in $k$ -element association reasoning, and a reasoning is regarded as a reliable association rule if it is sufficiently confident.

Pruning of candidate sets

Pruning of candidate sets means to calculate how frequently an element in a $k$ -element candidate set occurs in a $k$ -element instance set, and compare it with a given threshold or any threshold determined by a method, so as to judge the spatiotemporal co-occurrence regularity between ships in a $k$ -element candidate set. If the frequency does not meet the judgment rule, the candidate set is deleted. If it satisfies the rule, the candidate sett is retained as a $k$ -element frequency set.^23,24 This utilizes the recursive method to quickly find out the ships with co-occurrence regularity, and helps prepare for generating a $k + 1$ -element candidate set from a $k$ -element frequency set.

It is assumed that, in all $k$ -element instance sets ${Y}^{k}$ and $k$ -element candidate sets ${X}^{k}$ , the $i$ ^th $k$ -element instance set is ${Y}_{i}^{k}$ , and the number of such sets ${Y}_{i}^{k}$ is $| Y^{k} |$ ; the $j$ th $k$ -element candidate set is ${X}_{j}^{k}$ , and the number of such sets ${X}_{j}^{k}$ is $| X^{k} |$ .

Definition: the number of $k$ -element instance sets ${Y}_{i}^{k}$ that satisfy ${Y}_{i}^{k} \cap {X}_{j}^{k} = {X}_{j}^{k}$ is the value of frequency, that is, $a_{j}^{k}$ . Thus the frequency of the $k$ -element candidate set ${X}_{j}^{k}$ is regarded as

α_{j}^{k} = \frac{a_{j}^{k}}{| Y^{k} |}

(4)

The frequency $α_{j}^{k}$ is used to measure the possibility of spatiotemporal co-occurrence regularity between ships in the $j$ th $k$ -element candidate set ${X}_{j}^{k}$ . It is evident that, if the $k$ -element candidate set ${X}_{j}^{k}$ occurs more frequently in a $k$ -element instance set ${Y}_{i}^{k}$ , the ships in the $k$ -element candidate set ${X}_{j}^{k}$ have spatiotemporal co-occurrence phenomenon more frequently. In other words, the ships in the $k$ -element candidate set ${X}_{j}^{k}$ are more possible to demonstrate spatiotemporal co-occurrence regularity.

Definition of frequency judgment criterion: The frequency threshold is set to $θ_{s}$ . If the frequency of ${X}_{j}^{k}$ , that is, $α_{j}^{k}$ , satisfies

α_{j}^{k} \geq θ_{s}

(5)

The set ${X}_{j}^{k}$ is regarded as a $k$ -element frequency set, and the $l th k$ -element frequency set is recorded as ${Z}_{l}^{k}$ . Evidently, there is spatiotemporal co-occurrence regularity between two ships in the $k$ -element frequency set ${Z}_{l}^{k}$ . Otherwise, it is believed that the set ${X}_{j}^{k}$ is not a $k$ -element frequency set.

This aims to find out a $k$ -element frequency set with a certain frequency in the $k$ -element candidate set, and the ships in the $k$ -element frequency set have spatiotemporal co-occurrence regularity in pairs.

Pasting of frequency sets

Pasting of frequency sets means to generate a $k + 1$ -element candidate set by pasting from $k$ -element frequency sets. In the pasting process, it is required that the first $k - 1$ -element of two $k$ -element frequency sets involved are identical. If this requirement is satisfied, a union is taken from such two $k$ -element frequency sets to generate a $k + 1$ -element candidate set. Otherwise, the sets are not combined.^25,26

If there are at most $k - 2$ identical elements in the first $k - 1$ elements of two $k$ -element frequency sets, the $k + 1$ -element candidate set obtained by virtue of union contains at least two ships having no spatiotemporal co-occurrence regularity. In this case, the $k + 1$ -element candidate set will not be used to further generate a $k + 1$ -element frequency set.

It is assumed that the $k$ -element frequency set obtained by pruning candidate sets is ${Z}^{k}$ , the number of such sets is $| Z^{k} |$ , and the $l$ th $k$ -element frequency set is denoted by ${Z}_{l}^{k}$ . The following operations are conducted to all $k$ -element frequency sets ${Z}_{l}^{k}$ :

If $| {Z}_{l_{1}}^{k} \cap_{l_{2}}^{k} | = k - 1$ ( $l_{1} \neq l_{2}$ , and $l_{1}, l_{2} = 1, 2, \dots | Z^{k} |$ ), the number of the elements having intersection in two sets is $k - 1$ , the union ${Z}_{l_{1}}^{k} \cap_{l_{2}}^{k}$ is listed as a $k + 1$ -element candidate set. Otherwise, pasting is not implemented.

After traversal, all retained $k + 1$ -element candidate sets are renumbered and sequenced. The $j$ th $k + 1$ -element candidate set is ${X}_{j}^{k + 1}$ , and the total number of $k + 1$ -element candidate sets is $| X^{k + 1} |$ . This will be used in the next iterative cycle.

Screening of instance sets

Screening of instance sets means to delete all the instance sets that are not associated with the ships in $k$ -element candidate set from a $k - 1$ -element instance set in a process. If there is a $k - 1$ -element instance set, and the ships in such an instance set have no intersection with any $k$ -element candidate set, such an instance set makes no contribution to the frequency of spatiotemporal co-occurrence. Therefore, this instance set should not be taken as an indicator in the evaluation, and can be directly screened in iterative computation, so as to simplify search and computation.²⁷

It is assumed that there is a $k - 1$ -element instance set ${Y}_{i}^{k - 1}$ , and all $k$ -element candidate sets ${X}_{j}^{k}$ have ${Y}_{i}^{k - 1} \cap {X}_{j}^{k} = \emptyset$ . In other words, the $k - 1$ -element instance set ${Y}_{i}^{k - 1}$ does not contain any element belonging to any $k$ -element candidate set. It is therefore believed that this instance set does not make any contribution to the frequency of co-occurrence between ships in the surveyed $k$ -element candidate set ${X}_{j}^{k}$ . For the purpose of simpler computation, the set ${Y}_{i}^{k - 1}$ is then deleted. If ${Y}_{i}^{k - 1} \cap {X}_{j}^{k} \neq \emptyset$ , it is believed that the $k - 1$ -element instance set ${Y}_{i}^{k - 1}$ has potential value to co-occurrence pattern mining, and the set ${Y}_{i}^{k - 1}$ is then retained.

After traversal, all retained sets ${Y}_{i}^{k - 1}$ are renumbered and sequenced to obtain their new sets, that is, $k$ -element instance sets ${Y}^{k}$ . Among them, the $i$ th $k$ -element instance set is denoted by ${Y}_{i}^{k}$ , and will be used for co-occurrence pattern mining in the next iterative cycle.

Association reasoning

Association reasoning is to enumerate all possible association rules for all ships belonging to a k-element frequency set, that is, to put forward the hypothesis: “The co-occurrence of several ships in the k-element frequency set can infer that other ships in the set are also spatiotemporal associated.” On the one hand, this ensures that there is spatiotemporal co-occurrence regularity among all ships involved in the inference. On the other hand, all possible conclusion sets and phenomenon sets in k-element frequency sets are enumerated, which ensures that the association rules of ship co-occurrence can be obtained without missing.

For any k-element frequency set, select $i$ sets of ship numbers as the phenomenon set ${C}^{i}$ , and the other k- $i$ sets of ship numbers as the conclusion set ${R}^{i}$ . Denote the $p$ phenomenon set as ${C}_{p}^{i}$ , $p = 1, 2, \dots, C_{k}^{i}$ , and its corresponding conclusion set as ${R}_{p}^{i}$ .

Definition: ${C}_{p}^{i} \to {R}_{p}^{i}$ is an inference. It means “if there is a co-occurrence of ships in ${C}^{i}$ , then it follows that there is a co-occurrence of ships in ${R}_{p}^{i}$ .” Inference for k-element frequency set generation is collectively referred to as k-element associative inference.

Association rule mining refers to mining the association rules between the co-occurrence of ships by obtaining the confidence of the co-occurrence of any few ships in a frequency set to the co-occurrence of other ships, that is, filtering out all the “co-occurrence of a few ships in the k-element frequency set, it can be inferred that the co-occurrence of other ships in the set also occurs.” The inference by which this assumption holds, is the association rule.

Suppose that for some k-element frequency set ${Z}_{l}^{k}$ there exists an inference ${C}_{p}^{i} \to {R}_{p}^{i}$ of terms. Denote the number of k-element instance sets ${Y}_{i}^{k}$ satisfying ${C}_{p}^{i} \cap_{i}^{k} = {C}_{p}^{i}$ as $conf (C)$ , this is the number of instance sets containing the ship number in the phenomenon set ${C}^{i}$ . Denote the number of k-element instance sets ${Y}_{i}^{k}$ satisfying ${Z}_{l}^{k} \cap_{i}^{k} = {Z}_{l}^{k}$ as $conf (C, R)$ , this is the number of instance sets containing ship numbers in this frequency set ${Z}_{l}^{k}$ .

Let the confidence of an inference ${C}_{p}^{i} \to {R}_{p}^{i}$ be $β$ , which is expressed as follows:

β = \frac{conf (C, R)}{conf (C)}

(6)

It means the ratio of the number of instance sets containing the ship number in the phenomenon set ${C}^{i}$ to the number of instance sets containing the ship number in the frequency set ${Z}_{l}^{k}$ . It measures the support degree of the instance set for the reasoning ${C}_{p}^{i} \to {R}_{p}^{i}$ . Obviously, the higher the probability that a ship in the phenomenon set ${C}_{p}^{i}$ will also appear in the frequent set ${Z}_{l}^{k}$ . Therefore, the conclusion of the association rule “if the ships in ${C}_{p}^{i}$ co-occur, it can be inferred that the ships in ${R}_{p}^{i}$ co-occur” will be more credible.

Define the judgment criteria of association rules: set the confidence threshold as $θ_{C}$ . If the relationship between the confidence $β$ of inference ${C}_{p}^{i} \to {R}_{p}^{i}$ and the confidence threshold $θ_{C}$ satisfies:

β \geq θ_{C}

(7)

Then ${C}_{p}^{i} \to {R}_{p}^{i}$ is called an association rule: that is, the inference “if ships in ${C}_{p}^{i}$ co-occur, then we can deduce that ships in ${R}_{p}^{i}$ co-occur” holds.

Process of implementing spatiotemporal co-occurrence mining algorithm

Spatiotemporal co-occurrence pattern mining algorithm is used to find a set of all ships with spatiotemporal co-occurrence regularity. The process of implementing the algorithm is as presented in Figure 1.

Figure 1.

Process flow of spatiotemporal co-occurrence pattern mining algorithm.

The specific steps of implementing the algorithm are as follows:

Step 1: Initialization of parameters.

We set $k = 1$ , frequency threshold $θ_{s}$ , confidence threshold $θ_{c}$ , time slot $Δ t$ , 0-element co-occurrence instance set ${Y}^{0}$ , and number of instance sets $| Y^{0} |$ . Among these sets, the $i$ th instance set is recorded as ${Y}_{i}^{0}$ , $i = 1, 2, \dots | Y^{0} |$ ;

A set of all ship ID numbers is denoted by ${B}^{0}$ . The number of elements in the set is $| B^{0} |$ . All $k$ -element combinations in ${B}^{0}$ are taken to form $k$ -element candidate sets ${X}^{k}$ . Among these sets, the $j$ th candidate set is ${X}_{j}^{k}$ , and the total number of $k$ -element candidate sets ${X}^{k}$ is $| X^{k} |$ .

Step 2: Description of candidate sets

1) Each element in a $k$ -element candidate set is a combination of $k$ -element ship ID numbers;

2) The total number of $k$ -element candidate sets ${X}^{k}$ is $| X^{k} |$ , and the $j$ th candidate set is ${X}_{j}^{k}$ ;

3) The frequency of the $j$ th candidate set ${X}_{j}^{k}$ is counted as $a_{j}^{k} = 0$ .

Step 3: Screening of instance sets

1) All $k$ -element candidate sets ${X}_{j}^{k}$ are traversed for each $k - 1$ -element instance set ${Y}_{i}^{k - 1}$ :

If ${Y}_{i}^{k - 1} \cap {X}_{j}^{k} = \emptyset$ , the set ${Y}_{i}^{k - 1}$ is deleted;

If ${Y}_{i}^{k - 1} \cap {X}_{j}^{k} \neq \emptyset$ , the set ${Y}_{i}^{k - 1}$ is retained.

2) After traversal, all retained sets ${Y}_{i}^{k - 1}$ are renumbered and sequenced to obtain new sets ${Y}^{k}$ . Among them, the $i$ th $k$ -element instance set is denoted by ${Y}_{i}^{k}$ .

Step 4: Processing of candidate sets

1) All $k$ -element instance sets are traversed for each $k$ -element candidate set ${X}_{j}^{k}$ :

If ${Y}_{i}^{k} \cap {X}_{j}^{k} = {X}_{j}^{k}$ , there is $a_{j}^{k} = a_{j}^{k} + 1$ ;

If ${Y}_{i}^{k} \cap {X}_{j}^{k} \neq {X}_{j}^{k}$ , $a_{j}^{k}$ remains unchanged.

2) The frequency of each $k$ -element candidate set ${X}_{j}^{k}$ is calculated to be $α_{j}^{k} = a_{j}^{k} / | Y^{k} |$ .

Step 5: Pruning of candidate sets

1) All $k$ -element candidate sets ${X}_{j}^{k}$ are traversed:

If $α_{j}^{k} \geq θ_{s}$ , the $k$ -element candidate set ${X}_{j}^{k}$ is retained, and recorded as a $k$ -element frequency set;

If $α_{j}^{k} < θ_{s}$ , the $k$ -element candidate set ${X}_{j}^{k}$ is deleted.

2) After traversal, all retained $k$ -element frequency sets are renumbered and sequenced. The $l th k$ -element frequency set is recorded as ${Z}_{l}^{k}$ . The total number of $k$ -element frequency sets is denoted by $| Z^{k} |$ .

3) If $| Z^{k} | > 0$ , Step 6 is implemented;

4) If $| Z^{k} | = 0$ , the implementation of the algorithm ends.

Step 6: Pasting of candidate sets

1) As for each $k$ -element frequency set, all the other $k$ -element frequency sets ${Z}_{l}^{k}$ are traversed:

If $| {Z}_{l_{1}}^{k} \cap {Z}_{l_{2}}^{k} | = k - 1$ ( $l_{1} \neq l_{2}$ and $l_{1}, l_{2} = 1, 2, \dots | Z^{k} |$ ), we let ${Z}_{l_{1}}^{k} \cap {Z}_{l_{2}}^{k}$ be a $k + 1$ -element candidate set;

If $| {Z}_{l_{1}}^{k} \cap {Z}_{l_{2}}^{k} | \neq k - 1$ ( $l_{1} \neq l_{2}$ and $l_{1}, l_{2} = 1, 2, \dots | Z^{k} |$ ), no operation is conducted.

2) After reversal, all retained $k + 1$ -element candidate sets are renumbered and sequenced. The $j$ th $k + 1$ -element candidate set is recorded as ${X}_{j}^{k + 1}$ , and the total number of $k + 1$ -element candidate set is recorded as $| X^{k + 1} |$ .

3) We let $k = k + 1$ , and return to Step 2.

Experiment and analysis

In this section, all the parameters needed in the algorithm were studied and evaluated. The procedure of spatiotemporal co-occurrence pattern mining algorithm was then implemented to obtain all $k$ -element frequency sets, that is, spatiotemporal co-occurrence relationship between $k$ ships.^28,29 The hardware and software environment of the experiment in this paper is: Inter Core i7 4.0 GHz CPU, 16 GB memory, 1024 GB SSD drive, 1080Ti graphics card, and Windows 10-64 bit operating system. The algorithm is implemented by Python 3.5 programming language. The test data used in the experiment is a hot water located in Qiongzhou Strait, and the AIS data of 7071893 ships are collected within 30 days, with 1386 ships.

Setting of parameters

Considering the actual situation, relevant references^30,31 were consulted to eventually select such parameters as given in Table 1:

Table 1.

Parameters of the algorithm.

Symbol	Meaning	Value
$Δ λ_{ρ}$	Longitude span of co-occurrence unit sea area	$0.0026$
$Δ φ_{ρ}$	Latitude span of co-occurrence unit sea area	$0.0034$
$n_{k}$	Number of longitude segments after equal division of hotspot sea area	$100$
$m_{k}$	Number of latitude segments after equal division of hotspot sea area	$100$
$Δ t$	Length of time slot	$60 \min$
$t_{s}$	Start time	21:28:36, September 25, 2012
$t_{e}$	End time	21:04:00, October 26, 2012

The data of ships in a hotspot sea area divided by time slot and into co-occurrence unit sea areas is summed up in Figure 2:

Figure 2.

Data of ships in a hotspot sea area.

In the above figure, all the sea areas in a hotspot sea area were divided into 744 layers in terms of time slot. Each layer represented the distribution of ships in the hotspot sea area within 60 min. Each layer had a different color to indicate different ships in different time slots.

Selection of frequency threshold

Frequency threshold $θ_{s}$ was a key parameter in solving the algorithm. It was determined in the following way:

The procedure was implemented to obtain the frequency of all one-element candidate sets $α_{j}^{k}$ . These sets were sequenced based on $α_{j}^{k}$ from high to low, so that the variation curve of $α_{j}^{k}$ was drafted as given in Figure 3.

Figure 3.

Frequency support of one-member candidate sets.

It was assumed that the mean value of the frequencies $α_{j}^{1}$ for all one-member candidate sets was ${\bar{α}}^{1}$ . In the above figure, the broken red lines represent the straight lines $α_{j}^{1} = {\bar{α}}^{1}$ and $α_{j}^{1} = 2 {\bar{α}}^{1}$ , respectively, from bottom to top.

It was found that the variation curve of the frequency $α_{j}^{1}$ changed dramatically at twice of its mean value. At this time, the curve bent abruptly, and descended at a noticeably slowing rate. It was evident that $α_{j}^{1}$ changed dramatically when it was around $α_{j}^{1} = 2 {\bar{α}}^{1}$ . In all one-member candidate sets, there were clearly few sets with the frequency $α_{j}^{1}$ greater than $2 {\bar{α}}^{1}$ . These sets had a frequency much higher than the general frequency of candidate sets. As a result, $2 {\bar{α}}^{1}$ was selected as the frequency threshold $θ_{s}$ for one-member candidate sets:

θ_{s} = 2 {\bar{α}}^{1}

(8)

The calculation gave ${\bar{α}}^{1} = 7.215 \times 10^{- 4}$ , so that $θ_{s} = 1.443 \times 10^{- 3}$ . In all the subsequent cycles, we took the frequency threshold $θ_{s} = 2 {\bar{α}}^{1} = 1.443 \times 10^{- 3}$ .

Selection of confidence threshold

Confidence threshold $θ_{c}^{k}$ was also a key parameter for the algorithm. It was selected in the way similar to the selection of frequency threshold. The procedure was implemented to first obtain all eight-element association reasoning confidences $β_{j}^{8}$ (which started after completing the spatiotemporal co-occurrence pattern mining, and calculating the maximum value of $k$ for $k$ -element frequency sets, i.e. 8). The variation curve of $β_{j}^{8}$ was drafted as shown in Figure 4 after sequencing the confidences $β_{j}^{8}$ from high to low.³²

Figure 4.

Eight-element reasoning confidence curve.

It was assumed that the mean value of all eight-member association reasoning confidences $β_{j}^{8}$ was ${\bar{β}}^{8}$ . In the above figure, the broken red line represents $β_{j}^{8} = {\bar{β}}^{8}$ .

It was found that the variation curve of $β_{j}^{8}$ descended at a noticeably slowing rate when the confidence $β_{j}^{8}$ was equal to its mean value. Among all eight-element association reasoning sets, there were clearly few sets with the confidence greater than ${\bar{β}}^{8}$ . These sets had a confidence greater than the general confidence of candidate sets. Therefore, ${\bar{β}}^{8}$ was selected as the confidence threshold $θ_{c}^{8}$ for eight-element association reasoning sets:

θ_{c}^{8} = {\bar{β}}^{8}

(9)

The calculation gave ${\bar{β}}^{8} = 0.0014430$ , so that $θ_{c}^{8} = 0.0014430$ . In all subsequent cycles, we took the confidence threshold $θ_{c} = 0.0014430$ .

Results of spatiotemporal co-occurrence pattern mining

(1) Candidate sets

The variation curve of the frequency $α_{j}^{k}$ for candidate sets in each cycle of the algorithm is presented in Figure 5.

Figure 5.

Frequency support curves: (a) frequency support of two-element candidate sets, (b) frequency support of three-element candidate sets, (c) frequency support of four-element candidate sets, (d) frequency support of five-element candidate sets, (e) frequency support of six-element candidate sets, (f) frequency support of seven-element candidate sets, and (g) frequency support of eight-element candidate sets.

In the figure, the red broken line represents the frequency threshold of $k$ elements, that is, straight line $α_{j}^{k} = θ_{s} = 1.443 \times 10^{- 3}, k = 2, 3, \dots 8$ .

In the above figure, it is found that:

1) When $k = 1, 2$ , a large proportion of $k$ -element candidate sets are screened. When $k \geq 3$ , $k$ -element candidate sets are rarely screened, and most of them become $k$ -element frequency sets;

This may be highly attributed to the unchanged threshold in the traditional Apriori algorithm. While generating two-element candidate sets, the frequency support of candidates is still very low. Thus the algorithm can still screen a large proportion of candidate sets. When the third cycle starts, lots of instance sets are removed. In this case, the frequency support of candidate sets goes up noticeably, but the threshold remains low as before. For this reason, most $k$ -element candidate sets have a frequency support greater than the frequency threshold. Therefore, the effect of screening begins to diminish, and most $k$ -element candidate sets will become $k$ -element frequency sets.

2) When $k = 4$ , the number of $k$ -element candidate sets increases abruptly. In other cases, the number of $k$ -element candidate sets decreases with the increasing $k$ value.

This may be caused by the fact that a large proportion of $k$ -element candidate sets can be effectively screened in the first two cycles, and a low number of frequency sets are generated. For this reason, the number of $k + 1$ -element candidate sets generated in the first two cycles drops significantly. When $k = 3$ , the threshold of the traditional Apriori algorithm remains unchanged. The frequency support of candidate sets begins to remarkably ascend, but is still low. Hence, a very low number of candidate sets are screened in each cycle. The number of three-element frequency sets is therefore large, which causes more four-element candidate sets.

Thereafter, $k$ -element candidate sets are generated on the premise that the first $k - 2$ items in two $k - 1$ -element frequency sets are identical. This premise becomes stricter and stricter with the increasing $k$ value, causing a decreasing number of $k$ -element candidate sets.

(2) Frequency sets

The number of $k$ -element frequency sets obtained in each cycle of the algorithm varies as shown in Figure 6.

Figure 6.

Variation of $k$ -element frequency set count by the Apriori algorithm.

The above figure reveals that:

1) When $k \leq 3$ , the number of $k$ -element frequency sets increases with the increasing $k$ value.

This happens since candidate sets are screened by frequency at a lower rate than the generation of frequency sets from candidate sets when $k \leq 2$ . Very few candidate sets are screened by frequency threshold when $k = 3$ , but there are still many candidate sets, causing an abrupt increase in the number of three-element candidate sets.

2) When $k > 3$ , the number of $k$ -element frequency sets decreases gradually with the increasing $k$ value.

When $k > 3$ , the number of $k$ -element candidate sets constantly decreases with the increasing $k$ value. When frequency sets are generated in each cycle, the frequency threshold is relatively low, and cannot screen $k$ -element candidate sets. The number of frequency sets decreases consequently.

(3) Ship spatiotemporal co-occurrence results

In the end, a frequency set contained at most eight elements. In other words, there was spatiotemporal co-occurrence regularity between at most eight ships. Two frequency sets with the highest frequency support among $k$ -element frequency sets $(k = 2, 3, \dots 8)$ were taken as an example to obtain some ships with spatiotemporal co-occurrence regularity as listed in Table 2:

Table 2.

Results of spatiotemporal co-occurrence pattern mining.

Number of elements in a frequency set	Ship numbering in the procedure	Frequency support
$2$	534,535	0.0060
$3$	428,531,546	0.0076
$4$	531,532,542,548	0.0069
$5$	531,532,541,544,545	0.0172
$6$	531,532,541,544,545,546	0.0343
$7$	532,542,544,545,546,548,549	0.1538
$8$	531,532,544,545,546,547,548,549	0.5

Taking the ships in a frequency set in Table 2 as an example, their trajectories were drafted as given in Figure 7.

Figure 7.

Ship co-occurrence diagrams: (a) ship trajectories in two-element candidate sets, (b) ship trajectories in three-element candidate sets, (c) ship trajectories in four-element candidate sets, (d) ship trajectories in five-element candidate sets, (e) ship trajectories in six-element candidate sets, (f) ship trajectories in seven-element candidate sets, and (g) ship trajectories in eight-element candidate sets.

The above figure is analyzed to find that

1) The actual trajectories of the ships in the eight-element frequency sets calculated by the association rule mining algorithm are very highly similar in terms of shape. These trajectories are also very close to each other. This may be attributed to the navigation of these ships along the preset channel for navigational safety, which results in massive overlapping of their trajectories. Evidently, there is certainly spatiotemporal co-occurrence regularity between these ships. Meanwhile, this proves the effectiveness and correctness of the proposed algorithm.²⁹

2) When $k = 2, 3$ for $k$ -element frequency sets ( $k = 2, 3, \dots 8$ ), the trajectories extensively coincide with each other. After the $k$ value keeps increasing, the trajectories start to “ramify.” The reasons must be as follows: when $k$ is small, it is easier to find pairs of ships navigating on the same channel and nearly at the same time; when $k$ becomes large, the probability of ships navigating on the same channel and nearly at the same time decreases gradually, so that their trajectories begin to “ramify.” At this time, spatiotemporal co-occurrence of ships is mainly attributed to the coincidence channels along the coast of Hainan Island.

3) When the $k$ value increases for $k$ -element frequency sets ( $k = 2, 3, \dots 8$ ), the maximum frequency support goes up as well. This may be attributed to the decreasing denominator in the confidence expression of $k$ -element association reasoning since the number of instance sets decreases with the increasing $k$ value. Moreover, the increasing $k$ value causes stricter and stricter screening of instance sets. When the $k$ value is large enough, fewer, and fewer instance sets satisfy the screening requirements. Among the retained instance sets, more and more sets can support the spatiotemporal co-occurrence assumption, which further raises the maximum frequency support of $k$ -element frequency sets.

4) The trajectories “ramify” only at the top, but coincide perfectly at the bottom. This must be caused since the left channel is for shipping between Xinlei Port and Haikou Bay, while the right channel goes between Haian Port and Haikou Bay. The two channels start and terminate at the same port in Hainan Island, but at different ports in Leizhou Peninsula. Two channels coincide in the middle of the straits, resulting in this situation.

5) The ships in two sets with the highest frequency support among all $k$ -element frequency sets are heading south-north, but not east-west. This may be attributed to the south-north channel linking the mainland to Hainan Island. With short journey, fixed heading, periodic and regular navigation, these ships may have the same destination and sail for the same reason, for example, massive ferry service and regular cargo shipping. Hence, it is highly possible for these ships to co-occur more frequently in space and time. The east-west channel links South China Sea to Beibu Gulf, and passes by Qiongzhou Straits. The ships along the channel may have different purposes or motives of shipping, and do not show clear regularity. Moreover, these ships are less likely to co-occur spatially and temporally.

(4) Association rule analysis results

On the basis of the above experiments, we further carry out the analysis and mining of ship association rules. By studying the confidence $β_{j}^{k}$ of $k$ -element correlation reasoning, we can find that:

1) When $k \geq 6$ , as the $k$ value of $k$ -element association inference decreases, the number of $k$ -element association rules extracted increases. This is probably because when $k \geq 6$ , the criteria for screening instance sets are also high, so the matching degree between the screened instance sets and frequent sets is also high, and the support degree of generated inference is also high.

2) When $k \leq 5$ , as the $k$ value of $k$ -element association inference increases, the number of $k$ -element association rules extracted decreases. This is probably because when $k \leq 5$ , the number of instance sets begins to increase significantly, so as the $k$ value of $k$ -element association reasoning decreases, the probability of cause sets and result sets in the instance sets will also decrease, so the number of $k$ -element association rules extracted will be smaller.

Take the group of $k$ -element association rules with the highest confidence as an example. Table 3 lists some of the obtained association rules.

Table 3.

Results of association rule analysis.

Number of elements in a frequency set	Association rule	Confidence degree
$2$	${534} \to {535}$	$17.32 %$
$3$	${532, 546} \to {545}$	$42.37 %$
$4$	${544, 547, 548} \to {545}$	77.45%
$5$	${532, 549, 1048, 1134} \to {548}$	$100 %$
$6$	${532, 542, 544, 545, 546} \to {548}$	$100 %$
$7$	${532, 542, 544, 545, 546, 549} \to {548}$	$100 %$
$8$	${531, 532, 544, 545, 547, 548, 549} \to {546}$	$100 %$
$8$	${531, 532, 544, 547, 548, 549} \to {545, 546}$	$100 %$

Observing the above table, we can find that:

1) With the increase of K value, the highest confidence value in the K-element association rule increases. This is because with the increase of K value, the instance set becomes less and less, which makes the denominator in the confidence expression of K-element correlation inference smaller and smaller. With the increase of K value, the screening of instance sets becomes more and more stringent. When K value is large enough, the instance sets that meet the screening conditions become less and less, which further increases the confidence of K-element association reasoning.

2) The larger the K value, the more associative reasoning with a confidence of 100%. This is because with the increase of K value, the filtering of instance set becomes more and more stringent, and when K value is large enough, the instance set that meets the filtering condition becomes more and more rare. In fact, when $k \geq 6$ , frequent sets are already very rare, and the elements in each frequent set are highly similar, which also results in the highest confidence instance set with only a few fixed ships. This also reflects that they do have very strong association rules.^33,34

Conclusions

In this paper, the automatic identification system data of ships in a hotspot sea area is taken as the source data to study a ship spatiotemporal co-occurrence pattern mining algorithm based on association rules. Based on the research of data model and the judgment criterion of spatio-temporal co-occurrence law, such concepts as candidate set, frequency set, and instance set are introduced together with the key procedure of algorithm, including pruning and pasting of candidate sets, screening of instance sets, definition of association reasoning, and association rule mining. Subsequently, the key steps of implementing the ship spatiotemporal data mining algorithm based on association rules are illustrated, and the process of spatiotemporal co-occurrence pattern mining algorithm is designed. In the end, an experiment is presented to obtain several ship combinations with spatiotemporal co-occurrence regularity in the hotspot sea area. The results of implementing the algorithm are analyzed by adjusting the setting of parameters. The proposed algorithm can find several ship combinations with spatiotemporal co-occurrence regularity in these hotspot sea areas, and the association rules on the co-occurrence of several ships. The performance of the proposed algorithms is illustrated on a real-world ship trajectory database and made a detailed comparative analysis. After implementing the procedure for 30 days, the spatiotemporal co-occurrence patterns and association rules for 1386 ships are eventually mined from 7071893 pieces of AIS data. The conclusion reveals that spatiotemporal co-occurrence relationship exists between at most eight ships in the hotspot sea area. Moreover, the maximum confidence of association rules is higher when the number of elements in a frequency set is larger.

This research algorithm is based on an application attempt of APRIORI algorithm in ship trajectory big data, and some meaningful results are obtained, which can reveal the aggregation trend of ships in specific time and space, which is of great significance for maritime traffic management, ship path planning and maritime supervision. In addition, this method reduces the computation time of the algorithm and improves the efficiency of pattern mining through the mined instances and the spatio-temporal relationships between instances. Through the use of advanced algorithms and technologies, the performance of spatio-temporal co-occurrence pattern mining can be effectively improved, which can provide some reference for the subsequent research in the field of ship spatio-temporal co-occurrence mining.

However, there is still room for further improvement in the ship spatio-temporal co-occurrence pattern mining algorithm based on association rules. For example, the setting of the time window may affect the performance of the algorithm. In theory, different types of vessels have different time and space characteristics in application. In the next step, we can consider setting a variable time window function to adjust the range of the time window according to the different identity of the ship, so as to obtain a more real algorithm result of ship spatio-temporal co-occurrence mode.

Footnotes

Acknowledgements

Not applicable.

Handling Editor: Sharmili Pandian

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was funded by National Science Foundation for Outstanding Young Scholars (grant number 42122025), Natural Science Foundation for Distinguished Young Scholars of Hubei Province of China (grant number 2019CFA086), and Natural Science Foundation of Hubei Province of China (grant number 2017CFB377).

Data availability

Not applicable.

ORCID iD

Chengxu Feng

References

Zheng

Trajectory data mining: an overview. ACM Trans Intell Syst Technol 2015; 6: 1–41.

Feng

Zhu

A survey on trajectory data mining: techniques and applications. IEEE Access 2017; 4: 2056–2067.

Mazimpaka

Timpf

Trajectory data mining: a review of methods and applications. J Spatial Inf Sci 2016; 13: 61–99.

Mirge

Verma

Gupta

Dense traffic flow patterns mining in bi-directional road networks using density based trajectory clustering. Adv Data Anal Classif 2017; 11: 547–561.

Jiang

Liu

Ding

, et al. Behavior pattern mining based on spatiotemporal trajectory multidimensional information fusion. Chin J Aeronaut 2023; 36: 387–399.

Weng

Deng

, et al. Towards better detection and analysis of massive spatiotemporal co-occurrence patterns. IEEE Trans Intell Transp Syst 2021; 22: 3387–3402.

Kong

Chen

Hou

, et al. Mobility trajectory generation: a survey. Artif Intell Rev 2023; 56: S3057–S3098.

Zhen

Shao

Pan

Advance in character mining and prediction of ship behavior based on AIS data. J Geo-Inf Sci 2021; 23: 2111–2127.

Liu

Liang

Yang

, et al. Deep learning-powered vessel trajectory prediction for improving smart traffic services in maritime internet of things. IEEE Trans Network Sci Eng 2022; 22: 2327–4697.

10.

Liu

Nie

Garg

, et al. Data-driven trajectory quality improvement for promoting intelligent vessel traffic services in 6G-enabled maritime IoT systems. IEEE Internet Things J 2021; 8: 5374–5385.

11.

Belhadi

Djenouri

Srivastava

, et al. A two-phase anomaly detection model for secure intelligent transportation ride-hailing trajectories. IEEE Trans Intell Transp Syst 2021; 22: 4496–4506.

12.

Veena

Sai Chithra

Uday Kiran

, et al. Discovering fuzzy frequent spatial patterns in large quantitative spatiotemporal databases. In: Proceedings of the 2021 IEEE international conference on fuzzy systems, Luxembourg, Luxembourg, 2021.

13.

Bommisetty

Ravikumar

Uday

, et al. Discovering spatial high utility itemsets in high-dimensional spatiotemporal databases. Advances and trends in artificial intelligence, In Proceedings of the 34th international conference on industrial, engineering and other applications of applied intelligent systems, IEA/AIE 2021, Part I, Kuala Lumpur, Malaysia., pp.53–65.

14.

Wang

Zhu

Zhou

, et al. Vessel spatio-temporal knowledge discovery with AIS trajectories using co-clustering. J Navig 2017; 70: 1383–1400.

15.

Ship trajectory analysis system based on satellite navigation and spatio-temporal entity. GNSS World China 2024; 49: 101–106.

16.

Huang

Yang

, et al. Ship trajectory prediction method of gated recurrent unit based on spatial-temporal attention mechanism. J Transport Inf Saf 2023; 41: 82–89.

17.

Yang

Bian

, et al. A spatial-temporal data mining method for the extraction of vessel traffic patterns using AIS data. Ocean Eng 2024; 293: 116454.

18.

Weng

Deng

, et al. Towards better detection and analysis of massive spatiotemporal co-occurrence patterns. IEEE Trans Intell Transp Syst 2021; 22: 3387–3402.

19.

Zheng

Urban computing: enabling urban intelligence with big data. Front Comput Sci 2017; 11: 1–3.

20.

Fawzy

Moussa

Badr

The spatiotemporal data fusion (STDF) approach: IoT-based data fusion using data analysis. Sensors 2021; 21: 7035.

21.

Leonardi

Marketos

Frentzos

, et al. T-warehouse: visual OLAP analysis on trajectory data. In: Proceedings of the IEEE international conference on data engineering, Long Beach, CA, 1–6 March 2010, pp.1141–1144.

22.

Zhao

Yan

Zhou

, et al. A ship trajectory prediction method based on GAT and LSTM. Ocean Eng 2023; 289: 116159.

23.

Zhang

Qiang

Yang

Mobility transportation mode detection based on trajectory segment. J Comput Inf Syst 2013; 9: 3279–3286.

24.

Zhang

Yang

Huang

, et al. Wide-bandwidth signal-based multireceiver SAS imagery using extended chirp scaling algorithm. IET Radar Sonar Navig 2022; 16: 531–541.

25.

AL-Dohuki

Kamw

Zhao

, et al. An open source trajanalytics software for modeling, transformation and visualization of urban trajectory data. In: Proceedings of the 2019 IEEE intelligent transportation systems conference (ITSC), Auckland, New Zealand, 27–30 October 2019, pp.150–155.

26.

Shang

Bao

DITA: distributed in-memory trajectory analytics. In: Proceedings of the 2018 international conference on management of data, Houston, TX, 10–15 June 2018, pp.725–740.

27.

de Almeida

Souza

Baptista

de Andrade

, et al. A survey on big data for trajectory analytics. ISPRS Int J Geo-Inf 2020; 9: 88.

28.

Chen

Yuan

Wang

, et al. Interactive visual discovering of movement patterns from sparsely sampled geo-tagged social media data. IEEE Trans Visual Comput Graphics 2016; 22: 270–279.

29.

Chen

Zhang

, et al. COPE: interactive exploration of co-occurrence patterns in spatial time series. IEEE Trans Visual Comput Graphics 2019; 25: 2554–2567.

30.

Luo

Wei

A fast method for detection of the important co-occurrence cases from spatio-temporal dataset. E-Sci Technol Appl 2013; 4: 23–31.

31.

Feng

Luo

, et al. The design and development of a ship trajectory data management and analysis system based on AIS. Sensors 2022; 22: 310.

32.

Zeng

, et al., TelCoVis: visual exploration of co-occurrence in urban human mobility based on telco data. IEEE Trans Visual Comput Graphics 2016; 22: 935–944.

33.

Liu

Huang

Trampier

. Spatiotemporal topic association detection on tweets. In: Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS), San Francisco Bay Area, California, USA, 2016, p.28.

34.

Sharmiladevi

Siva Sathya

Ramesh

A survey on spatiotemporal co-occurrence pattern mining techniques. Appl Artif Intell Eng 2021; 11: 225–238.

A spatiotemporal co-occurrence pattern mining algorithm based on ship trajectory data

Abstract

Keywords

Introduction

Related work

Model preparations

Co-occurrence unit sea area

Spatiotemporal co-occurrence phenomenon judgment criterion

Spatiotemporal co-occurrence regularity judgment criterion

k -element candidate set

k -element frequency set

k -element instance set

Algorithm design

Pruning of candidate sets

Pasting of frequency sets

Screening of instance sets

Association reasoning

Process of implementing spatiotemporal co-occurrence mining algorithm

Experiment and analysis

Setting of parameters

Selection of frequency threshold

Selection of confidence threshold

Results of spatiotemporal co-occurrence pattern mining

(1) Candidate sets

(2) Frequency sets

(3) Ship spatiotemporal co-occurrence results

(4) Association rule analysis results

Conclusions

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

Data availability

ORCID iD

References

$k$ -element candidate set

$k$ -element frequency set

$k$ -element instance set