CN115599875B - Track abnormality detection method, system and product - Google Patents

Abstract

The invention relates to a track abnormality detection method, a track abnormality detection system and a track abnormality detection product. The method comprises the steps of obtaining starting point coordinates and end point coordinates, determining a group of tracks according to the starting point coordinates and the end point coordinates, enabling the group of tracks to comprise a plurality of tracks, enabling one track to consist of a series of coordinate points according to time sequence, converting longitude and latitude coordinates of the coordinate points in each track into polar coordinates based on a midpoint polar coordinate system, converting all the tracks into list-type features with equal length according to the polar coordinates, and enabling an abnormality detector suitable for the list-type features to conduct abnormality detection on the list-type features to determine abnormal tracks. The invention improves the abnormality detection precision and reduces the time complexity and the space complexity.

Description

Track abnormality detection method, system and product

Technical Field

The present invention relates to the field of abnormal track detection, and in particular, to a method, a system, and a product for detecting a track abnormality.

Background

The trajectory data, also called spatiotemporal data, is generated by a positioning device such as a global positioning system (Global Positioning System, GPS), wi-Fi, video surveillance or wireless sensor network, and records the geographic information of the moving object. The moving object can be a human or an animal, or can be a vehicle such as a vehicle or an airplane, or even a natural disaster such as hurricane. Track-based data mining techniques are largely divided into four categories, prediction, clustering, classification, and anomaly detection.

There is currently no uniform mathematical definition of "outlier data". Hodgkin gives the most general definition that outliers are observations that are very different from other observations, resulting in suspicions that they are generated by different mechanisms. The anomalous data may be noise that is detrimental to the data analysis and should therefore be removed prior to the data analysis. The technology for identifying the abnormal data is an abnormal detection technology, and can be applied to the fields of financial fraud detection, fault detection, network intrusion detection, industrial system monitoring and the like. The anomaly track detection technology, which is a subclass of anomaly detection technology, has been used for various application scenarios such as city services, path exploration, destination prediction, public safety, athletic performance analysis, group performance analysis, athletic performance analysis, social services, ecological monitoring, environmental assessment, energy assessment, and the like.

Anomaly detection was first applied to trace data in 2000. Anomaly techniques that have been popular with other types of data are then directly applied to trace data anomaly detection, such as hidden Markov models and clustering algorithms. Preprocessing, such as sampling or dimension reduction, of the vast amount of data is often required before these algorithms are applied. However, these techniques introduced from other fields are not optimized for the abnormal trajectory detection task, and thus the accuracy is not high.

By 11 months 2004, high-pass companies announced that the mobile phone assisted GPS test was successful, and a number of related technologies began to emerge, including abnormal track detection technologies. A typical anomaly trajectory detection process is to pre-process the input data first, score the data using a correlation algorithm to quantify the anomaly of the data, optimize the anomaly score of the data using post-processing techniques and integration techniques, and determine whether the data is normal or anomalous based on a score threshold. Among them, the preprocessing section is particularly important for the abnormal trajectory detection technique. Thus, the abnormal trajectory detection techniques can be categorized into four categories, mapping-based, sampling-based, segmentation-based, and other methods, depending on the preprocessing method used.

The map-based preprocessing method can be further subdivided into a grid-map-based method and a map-based method. The grid mapping-based method grids the region where the track is located and represents the track data as a series of grid points on the grid, typical techniques based on this type are iBAT, iBOAT, deepTEA, ATDC, etc. Such an approach has the advantage that the influence of different track recording device sampling frequencies and object movement speeds on track points can be avoided, but has the disadvantage that it is sensitive to the grid size, possibly resulting in two very close tracks being represented by two completely different sets of grid cells. The track data is mapped onto the actual road traffic map based on map mapping, thus requiring additional map information, typical techniques based on this category are RPat, DB-TOD, RNPAT, loTAD, etc. The advantage of this method is that the effect of noise is reduced after mapping the track to the real route, the disadvantage is that the mapping process is very time consuming and cannot reflect the situation of new roads in cities, temporarily blocked roads and traffic jams.

The sampling-based method obtains a shorter or fixed-length track by sampling the original track data, and can also process the track in the process in a sliding window interception mode to obtain a fragment with a fixed length. Typical techniques based on this type are PICIARELLI, RAPIDLOF, PN-Opt, STN-Outlier, etc. A disadvantage of such a method is that due to the influence of the sampling frequency of the track recording device and the speed of movement of the object, the distribution of points on the track is not necessarily uniform, which will result in a great difference in the results of the two identical tracks possibly after sampling, thus affecting the accuracy of the anomaly detection.

The segment-based method divides the whole track into a plurality of segments of sub-tracks and distinguishes the sub-tracks in which the abnormality occurs. The track containing the abnormal sub-track is also a global abnormal track. Typical techniques based on this type are TRAOD, TODCSS, STC, TPBA, etc. The common segmentation methods include abrupt point segmentation, which has the disadvantage of being sensitive to noise and drift trajectory points, and manual regular segmentation, which has the disadvantage of requiring manual experience to select parameters, thus limiting practical use.

Therefore, the existing abnormal track detection technology has some defects, mainly in the preprocessing stage, can directly lead to the accuracy of final abnormal detection, and has higher time complexity and space complexity.

Disclosure of Invention

The invention aims to provide a track abnormality detection method, a track abnormality detection system and a track abnormality detection product, which are used for solving the problems of low abnormality detection precision and high time complexity and space complexity.

In order to achieve the above object, the present invention provides the following solutions:

A track anomaly detection method, comprising:

Acquiring a start point coordinate and an end point coordinate, and determining a group of tracks according to the start point coordinate and the end point coordinate, wherein the group of tracks comprises a plurality of tracks, and the track consists of a series of coordinate points according to time sequence;

Converting longitude and latitude coordinates of coordinate points in each track into polar coordinates based on a midpoint polar coordinate system;

Converting all the tracks into list-type features with equal lengths according to the polar coordinates;

And (3) adopting an abnormality detector suitable for the list phenotype characteristics to perform abnormality detection on the list phenotype characteristics, and determining an abnormal track.

Optionally, the acquiring the start point coordinate and the end point coordinate, and determining a set of tracks according to the start point coordinate and the end point coordinate specifically includes:

querying all tracks similar to the starting point coordinates and the end point coordinates from the historical track database to determine a group of tracks, wherein the similar tracks are Is the starting point coordinate of the similar track, S is the starting point coordinate, I.I.I is Euclidean distance, lambda is a distance threshold,The end point coordinates of the similar tracks are obtained, and D is the end point coordinates.

Optionally, the converting, based on the midpoint polar coordinate system, longitude and latitude coordinates of the coordinate point in each track to polar coordinates specifically includes:

determining a first connecting midpoint of the starting point coordinate and the ending point coordinate;

Establishing a first polar coordinate system by taking the midpoint of the first connecting line as a pole and taking the direction from the midpoint of the first connecting line to the starting point coordinate as a polar axis;

and converting longitude and latitude coordinates of the coordinate points in each track into polar coordinates based on the first polar coordinate system.

Optionally, the converting, based on the midpoint polar coordinate system, longitude and latitude coordinates of the coordinate point in each track to polar coordinates specifically includes:

determining a second connecting line midpoint of a starting point coordinate and an ending point coordinate in any track aiming at each track;

Establishing a plurality of second polar coordinate systems by taking the midpoint of the second connecting line as a pole and taking the direction from the midpoint of the second connecting line to the starting point coordinate in the track as a polar axis;

And converting longitude and latitude coordinates of any coordinate point in the track corresponding to the second polar coordinate system into polar coordinates based on any one of the second polar coordinate systems until the longitude and latitude coordinates of the coordinate point in each track are converted into polar coordinates.

Optionally, the converting, based on the midpoint polar coordinate system, longitude and latitude coordinates of the coordinate point in each track to polar coordinates specifically includes:

determining a first connecting midpoint of the starting point coordinate and the ending point coordinate;

Randomly selecting a track point from a group of tracks, taking the midpoint of the first connecting line as a pole, and taking the direction from the midpoint of the first connecting line to the track point as a polar axis to establish a third polar coordinate system;

and converting longitude and latitude coordinates of the coordinate points in each track into polar coordinates based on the polar coordinate system.

Optionally, the converting all the tracks into list-type features with equal lengths according to the polar coordinates specifically includes:

uniformly dividing the circumferential angle 2 pi into k parts, wherein each part comprises an radian range of 2 pi/k;

The method comprises the steps of distributing the angular coordinates of each coordinate point on one track to any one of k parts, and calculating the average value of the radial coordinates of all coordinate points distributed to any one part, wherein the average value of the radial coordinates is a distance-based characteristic;

calculating the number of coordinate points allocated to any part, wherein the number of the coordinate points is based on the characteristics of the points;

And splicing the distance-based features and the point-based features to determine list-type features until all the tracks are converted into list-type features with equal lengths.

Optionally, the converting all the tracks into list-type features with equal lengths according to the polar coordinates specifically includes:

uniformly dividing a half circumference angle pi into k parts, wherein each part comprises a pi/k radian range;

The method comprises the steps of distributing the angular coordinates of each coordinate point on one track to any one of k parts, and calculating the average value of the radial coordinates of all coordinate points distributed to any one part, wherein the average value of the radial coordinates is a distance-based characteristic;

counting the number of coordinate points with the angular coordinates of [0, pi) and the number of coordinate points with the angular coordinates of [ pi, 2 pi), wherein the number of coordinate points with the angular coordinates of [0, pi) and the number of coordinate points with the angular coordinates of [ pi, 2 pi) are based on the characteristics of points;

And splicing the distance-based features and the point-based features to determine list-type features until all the tracks are converted into list-type features with equal lengths.

A trajectory anomaly detection system, comprising:

the system comprises a track determining module, a track processing module and a track processing module, wherein the track determining module is used for acquiring a starting point coordinate and an end point coordinate, and determining a group of tracks according to the starting point coordinate and the end point coordinate;

The polar coordinate conversion module is used for converting longitude and latitude coordinates of coordinate points in each track into polar coordinates based on a midpoint polar coordinate system;

the list type feature conversion module is used for converting all the tracks into list type features with equal lengths according to the polar coordinates;

and the abnormality detection module is used for detecting the abnormality of the list-type characteristics by adopting an abnormality detector suitable for the list-type characteristics and determining an abnormal track.

An electronic device comprising a memory for storing a computer program and a processor that runs the computer program to cause the electronic device to perform the trajectory anomaly detection method described above.

A computer readable storage medium storing a computer program which when executed by a processor implements the track abnormality detection method described above.

According to the specific embodiment of the invention, the invention discloses the following technical effects that the track anomaly detection method, the track anomaly detection system and the track anomaly detection product are provided, longitude and latitude coordinates of coordinate points in a group of tracks are converted into polar coordinates based on a midpoint polar coordinate system, all the tracks are converted into list-type features with equal length according to the polar coordinates, anomaly detection is carried out on the list-type features by adopting an anomaly detector suitable for the list-type features, the anomaly tracks are determined, the conditions of various track data are robust, the problem of low anomaly detection precision caused by a preprocessing stage is avoided, and all the tracks are converted into the list-type features with equal length, so that the time complexity and the space complexity are low, and the method is more convenient for large-scale industrial application.

Drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings that are needed in the embodiments will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments of the present invention, and other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.

FIG. 1 is a flowchart of a method for detecting trace anomalies provided by the present invention;

FIG. 2 is a schematic diagram of a process for extracting trace data features based on a midpoint polar coordinate system according to the present invention;

FIG. 3 is a schematic diagram of three types of exceptions provided by the present invention, FIG. 3 (a) is a schematic diagram of a bypass Detour, FIG. 3 (b) is a schematic diagram of a disturbance Perturbation, and FIG. 3 (c) is a schematic diagram of a switch Route-switching;

FIG. 4 is a schematic illustration of three pairs of start-stop routes provided by the present invention.

Detailed Description

The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

The invention aims to provide a track abnormality detection method, a track abnormality detection system and a track abnormality detection product, which improve abnormality detection precision and reduce time complexity and space complexity.

In order that the above-recited objects, features and advantages of the present invention will become more readily apparent, a more particular description of the invention will be rendered by reference to the appended drawings and appended detailed description.

Example 1

Fig. 1 is a flowchart of a track abnormality detection method provided by the present invention, as shown in fig. 1, a track abnormality detection method includes:

Step 101, acquiring a starting point coordinate and an ending point coordinate, and determining a group of tracks according to the starting point coordinate and the ending point coordinate, wherein the group of tracks comprises a plurality of tracks, and one track consists of a series of coordinate points according to time sequence. The track can be a GPS track or a Beidou satellite navigation system track and the like.

In practical application, the step 101 specifically includes querying all tracks similar to the start point coordinates and the end point coordinates from the historical track database to determine a set of tracks, where the similar tracks are Is the starting point coordinate of the similar track, S is the starting point coordinate, I.I.I is Euclidean distance, lambda is a distance threshold,The end point coordinates of the similar tracks are obtained, and D is the end point coordinates.

A track consisting of a series of time-sequential coordinate points, i.e.Wherein T _j is the j-th track,I is the time point at which the time point,Coordinates of the ith point in time for the jth track,AndThe latitude and longitude coordinates respectively,The coordinates of the mth time point of the jth track.

Given a start point coordinate s= { x _s,y_s } and an end point coordinate d= { x _d,y_d }, all start and end points and their close trajectories are first found from the historical trajectory database, where close is defined as In the above formula, |·| represents the euclidean distance, and λ is the distance threshold. Finally, a group of tracks G _S,D,λ＝{T₁,T₂,…,T_j,…T_n};T_n meeting the requirements is obtained as an nth track.

The object of the present invention is to find an anomaly track in the set of tracks, wherein anomaly is defined as a relatively small number of track routes or a large difference from other routes.

And 102, converting longitude and latitude coordinates of coordinate points in each track into polar coordinates based on a midpoint polar coordinate system.

In practical application, longitude and latitude coordinates of a coordinate point in a track are expressed as polar coordinates, and the invention provides three methods.

A1 The step 102 specifically includes determining a first connection midpoint between the start point coordinate and the end point coordinate, establishing a first polar coordinate system by taking the first connection midpoint as a pole and a direction from the first connection midpoint to the start point coordinate as a polar axis, and converting longitude and latitude coordinates of coordinate points in each track into polar coordinates based on the first polar coordinate system.

Finding the midpoint M of the connection between the starting point S and the end point D, taking the midpoint M as a pole,A polar coordinate system is established for the polar axis. Any coordinate point on any track in G _S,D,λ Can be expressed as polar coordinatesWherein the angular positionRadius coordinates

A2 The step 102 specifically includes determining a second connection midpoint of a start point coordinate and an end point coordinate in any track for each track, establishing a plurality of second polar coordinate systems with a direction from the second connection midpoint to the start point coordinate in the track as a polar axis by taking the second connection midpoint as a pole, wherein one second polar coordinate system corresponds to one track, and converting longitude and latitude coordinates of any coordinate point in the track corresponding to the second polar coordinate system into polar coordinates based on any one second polar coordinate system until longitude and latitude coordinates of coordinate points in each track are converted into polar coordinates.

For one track in G _S,D,λ Find its own starting pointAnd endpointIs shown as a mid-point M ^j of the line, with this as the pole of the pole,A polar coordinate system is established for the polar axis. Any one coordinate point on the trackCan be expressed as polar coordinatesWherein the angular position Radius coordinates

A3 The step 102 specifically includes determining a first connection midpoint between the start point coordinate and the end point coordinate, randomly selecting a track point from a group of tracks, taking the first connection midpoint as a pole, taking a direction from the first connection midpoint to the track point as a polar axis, establishing a third polar coordinate system, and converting longitude and latitude coordinates of coordinate points in each track into polar coordinates based on the polar coordinate system.

The midpoint M of the line connecting the start point S and the end point D is found and taken as a pole. Randomly selecting a track point Q from G _S,D,λ andA polar coordinate system is established for the polar axis. Any coordinate point on any track in G _S,D,λ Can be expressed as polar coordinatesWherein the method comprises the steps of

And step 103, converting all the tracks into list-type features with equal lengths according to the polar coordinates.

In practical application, the invention provides two methods for extracting the list-type features with equal length from the track data with unequal length:

B1 The step 103 specifically includes uniformly dividing a circumference angle 2pi into k parts, each part including an radian range of 2pi/k, distributing the angular coordinates of each coordinate point on one track to any one of the k parts, calculating an average value of radius coordinates distributed to all coordinate points in any one part, wherein the average value of the radius coordinates is a distance-based feature, calculating the number of coordinate points distributed to any one part, wherein the number of coordinate points is a point-based feature, and splicing the distance-based feature and the point-based feature to determine a list feature until all tracks are converted into list features with equal lengths.

After all coordinate points of a track are expressed in the form of polar coordinates, the invention uniformly divides the circumference angle 2pi into k parts, namely each part comprises the radian range of 2pi/k, which is expressed asThen, each coordinate point on a track is allocated to one of the k parts according to its angular coordinates, i.e

After all coordinate points are distributed, for distributionCalculating the average value of their radius coordinates d and representing them asI.e.Thus can getThis is referred to herein as a distance-based feature.

Recalculating allocation intoThe number of coordinate points in (a) is expressed asThe number of elements in the computation set is represented by I.I. and is then availableThe present invention refers to this as a point-based feature.

Finally, the two features are spliced together to obtain the final feature, i.e

B2 Step 103 specifically includes uniformly dividing a half circumference angle pi into k parts, each part including an arc range of pi/k, assigning an angular coordinate (an angular coordinate exceeding pi is changed to 2 pi minus the angular coordinate) of each coordinate point on one track to any one of the k parts, and calculating an average value of radial coordinates assigned to all coordinate points in any one part, the average value of radial coordinates being a distance-based feature, counting the number of coordinate points between the angular coordinates [0, pi ] and the number of coordinate points between the angular coordinates [ pi, 2 pi ], the number of coordinate points between the angular coordinates [0, pi ] and the number of coordinate points between the angular coordinates [ pi, 2 pi ] being a distance-based feature, and stitching the distance-based feature and the distance-based feature until all tracks are converted into a list-type feature having equal length.

The half-circumference angle pi is uniformly divided into k parts, i.e., each part contains pi/k radian range, expressed asThen, each coordinate point on a track is allocated to one of the k parts according to its angular coordinates, i.e

After all coordinate points are distributed, for distributionCalculating the average value of their radius coordinates d and representing them asI.e.Thus can getThis is referred to herein as a distance-based feature.

Then, the number of coordinate points with the angular coordinates between [0, pi ] is counted and recorded asCounting the number of coordinate points with angular coordinates between [ pi, 2 pi), and recording asThus can getThe present invention refers to this as a point-based feature.

Finally, the two features are spliced together to obtain the final feature, i.e

Finally, all the tracks G _S,D,λ＝{T₁,T₂,…,T_j,…T_n are converted into a feature list f= [ F ₁,F₂,…,F_j,…F_n ].

And 104, adopting an anomaly detector suitable for the list phenotype characteristics to perform anomaly detection on the list phenotype characteristics, and determining an anomaly track.

In practical application, any anomaly detector suitable for the column phenotype features is applied to the converted features, such as a local anomaly factor method (LOF) or a K nearest neighbor method (KNN), so as to complete the detection of the anomaly track.

In the present invention, LOF is used as the anomaly detector.

For steps 102-103, the present invention refers to the combination of method a1+method B1 as GMiPo, the combination of method a1+method B2 as MiPo, the combination of method a1+using only distance-based features in method B2 as MiPoD, the combination of method a1+using only point-based features in method B2 as MiPoP, and the combination of method a2+method B2 as PMiPo.

First, the present invention provides a simple example of MiPo. As shown in FIG. 2, miPo extracts two sets of features, distance-based features, from the trajectory data(Top box B1 of FIG. 2) and point-based features(Bottom block B2 of fig. 2) to convert the trajectory data { T ₁,T₂,T₃,T₄ } (bottom left block a of fig. 2) into table data [ F ₁,F₂,F₃,F₄ ] (bottom right block C of fig. 2). To extract distance-based features MiPo represents each point in the trajectory data using midpoint polar coordinates, vectorsAs a reference vector, where M is the midpoint of the line connecting the start point S and the destination point D. The points in each trace may then be divided into three, as shown on the left side of block B1 of fig. 2. For example, the distribution of points in the track T ₁ isThe average of the distances between the points in each lot and M was then calculated, resulting in 3.4,3.0 and 2.4. Thus T ₁ is characterized by the distanceSince all six points in T ₁ are located on one side of the connection SD, i.e. their angles are all between 0 and pi, the point-based feature of T ₁ isFinally, the invention concatenates these two features as the final feature of T ₁, i.e., F ₁ = [3.4,3.0,2.4,6,0].

Secondly, the invention designs a series of perfect experiments based on a real GPS driving track data set so as to compare the invention with other abnormal track detection technologies. The data set comprises 1710670 tracks of 442 taxis between 1 month and 7 days in the grape dental Bohr diagram 2013 and 1 month and 30 days in 2014, and the GPS sampling frequency is 1/15Hz. According to the invention, 3 pairs of starting points and ending points are selected from the data set, and 12 test sets are constructed in a mode of combining manual selection of tracks, manual labeling of anomalies and manual addition of anomalies. The manually added exception types are three, namely detour (Detour), disturbance (Perturbation) and Route-switching (Route-switching). Detour represents that the driver detours a large section of far road in the normal route, disturbance represents that the driver frequently makes a small-scale detour in the normal route driving process, and route switching represents that the driver switches from one route to another normal route halfway. Fig. 3 is a schematic diagram of three anomalies provided by the present invention, as shown in fig. 3. Table 1 is a table of twelve test set information, and specific test set information is shown in table 1.

TABLE 1

In table 1, aiSq-prefix data sets represent routes based on a first pair of start-stop points, stSt-prefix data sets represent routes based on a second pair of start-stop points, and UnCh-prefix data sets represent routes based on a third pair of start-stop points. Fig. 4 is a schematic view of three pairs of start-stop points provided by the present invention, as shown in fig. 4.

Over these 12 test sets, the GMiPo, miPo, miPoD, miPoP, PMiPo embodiments proposed in the present invention, and the IBAT, IBOAT, rapidLOF, LSTM, ATDC, TPBA, ELSTMAE and RNPAT eight typical anomaly trajectory detection techniques were tested and compared, and the area under the receiver operating characteristic curve (Area Under Receiver Operating Characteristic Curve, AUC-ROC) commonly used in the anomaly detection field was used as an evaluation index. The value of the index is between 0,1, and a larger index represents a better technical performance. Table 2 is a table of the results of the 5 inventive regimens and 8 comparative techniques on twelve test sets, with the experimental results shown in Table 2.

TABLE 2

In table 2 AVG, STD, media represents the mean, standard deviation and median, respectively, of the results of a method over all test sets. As can be seen from table 2, miPo performed optimally in all the presented scenarios, with an average AUC of 0.99. In contrast, GMiPo had a mean AUC of 0.96 and a slightly lower performance, indicating that method B2 was superior to method B1. While MiPoP and MiPoD each perform less than MiPo, indicating that the distance-based feature domain is more advantageous when combined with point-based features. PMiPo and MiPo are very similar in performance, indicating that there is no significant difference between method A1 and method A2.

In the comparative other abnormal track detection technique RNPAT, since the urban road map is required as additional information to match the track with the real road, it is not suitable for the test set to which the abnormal route is manually added, so it has no results of the first 8 datasets. The comparison results show that MiPo is superior to all other anomaly track detection techniques over all test sets, i.e., regardless of which pair of start-stop routes, which anomaly track type, and anomaly ratio. At the same time MiPo results have a minimum standard deviation of 0.01, which means that it is robust and stable.

TABLE 3 Table 3

Finally, the present invention tests the operational time consumption of all techniques. Table 3 shows a table of MiPo scheme correlations and 8 comparative techniques for operating time, the results of which are shown in Table 3, where the units of time are seconds, n represents the number of tracks tested, and m represents the length of each track. Mipo represents the time consuming step 102+step 103, mipo-represents the time consuming step 103, miPo +lof represents the time consuming step 102+step 103+step 104. The results show that feature extraction for 10000 tracks of length 90 takes only about 0.78 seconds, i.e. on average only 1 microsecond per track, with the midpoint polar coordinates of the tracks converted. If the time of the midpoint polar transformation is calculated, only 2.7 milliseconds are required for extracting the characteristics of each track on average. This indicates that MiPo runs very fast and can be further accelerated by converting the midpoint polar coordinates of the track in advance and storing in a database.

In lateral comparison, miPo +lof is almost 10 times faster than IBAT compared to a performance competitive technique IBAT. If only MiPo-and LOF are considered, even 100 times faster than IBAT. The fastest of the remaining technologies is RapidLOF, but the performance varies much as can be seen from the RLOF column of table 2. Compared with the methods LSTM and ELSTMAE based on deep learning, miPo +LOF is more than 40 times faster. RNPAT is most time consuming due to the need for preprocessing to map the trajectory onto the road map.

Example two

In order to perform a corresponding method of the above embodiment to achieve the corresponding functions and technical effects, a track abnormality detection system is provided below.

A trajectory anomaly detection system, comprising:

the system comprises a track determining module, a track processing module and a track processing module, wherein the track determining module is used for acquiring starting point coordinates and end point coordinates and determining a group of tracks according to the starting point coordinates and the end point coordinates, the group of tracks comprises a plurality of tracks, and the track consists of a series of coordinate points according to time sequence.

And the polar coordinate conversion module is used for converting longitude and latitude coordinates of the coordinate points in each track into polar coordinates based on a midpoint polar coordinate system.

And the list type feature conversion module is used for converting all the tracks into list type features with equal lengths according to the polar coordinates.

And the abnormality detection module is used for detecting the abnormality of the list-type characteristics by adopting an abnormality detector suitable for the list-type characteristics and determining an abnormal track.

Example III

An embodiment of the present invention provides an electronic device including a memory and a processor, where the memory is configured to store a computer program, and the processor runs the computer program to enable the electronic device to execute the trace abnormality detection method of the first embodiment.

In practical applications, the electronic device may be a server.

In practice, the electronic device includes at least one processor (processor), memory (memory), bus, and communication interface (Communications Interface).

The processor, the communication interface and the memory complete communication with each other through the communication bus.

And the communication interface is used for communicating with other devices.

And a processor, configured to execute a program, and specifically may execute the method described in the foregoing embodiment.

In particular, the program may include program code including computer-operating instructions.

The processor may be a central processing unit, CPU, or an Application specific integrated Circuit, ASIC (Application SPECIFIC INTEGRATED circuits), or one or more integrated circuits configured to implement embodiments of the present invention. The one or more processors included in the electronic device may be the same type of processor, such as one or more CPUs, or different types of processors, such as one or more CPUs and one or more ASICs.

And the memory is used for storing programs. The memory may comprise high-speed RAM memory or may further comprise non-volatile memory, such as at least one disk memory.

Based on the description of the above embodiments, an embodiment of the present application provides a storage medium having stored thereon computer program instructions executable by a processor to implement the method of any embodiment

The track abnormality detection system provided by the embodiment of the application exists in various forms, including but not limited to:

(1) Mobile communication devices, which are characterized by mobile communication functionality and are aimed at providing voice, data communication. Such terminals include smart phones (e.g., iPhone), multimedia phones, functional phones, and low-end phones, among others.

(2) Ultra mobile personal computer equipment, which belongs to the category of personal computers, has the functions of calculation and processing and generally has the mobile internet surfing performance. Such terminals include PDA, MID and UMPC devices, etc., such as iPad.

(3) Portable entertainment devices such devices can display and play multimedia content. Such devices include audio, video players (e.g., iPod), palm game consoles, electronic books, and smart toys and portable car navigation devices.

(4) Other electronic devices with data interaction functions.

Thus, particular embodiments of the present subject matter have been described. Other embodiments are within the scope of the following claims. In some cases, the actions recited in the claims can be performed in a different order and still achieve desirable results. In addition, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some embodiments, multitasking and parallel processing may be advantageous.

The system, apparatus, module or unit set forth in the above embodiments may be implemented in particular by a computer chip or entity, or by a product having a certain function. One typical implementation is a computer. In particular, the computer may be, for example, a personal computer, a laptop computer, a cellular telephone, a camera phone, a smart phone, a personal digital assistant, a media player, a navigation device, an email device, a game console, a tablet computer, a wearable device, or a combination of any of these devices.

For convenience of description, the above devices are described as being functionally divided into various units, respectively. Of course, the functions of each element may be implemented in the same piece or pieces of software and/or hardware when implementing the present application. It will be appreciated by those skilled in the art that embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.

The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the application. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

In one typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.

The memory may include volatile memory in a computer-readable medium, random Access Memory (RAM) and/or nonvolatile memory, such as Read Only Memory (ROM) or flash memory (flash RAM). Memory is an example of computer-readable media.

Computer readable media, including both non-transitory and non-transitory, removable and non-removable media, may implement information storage by any method or technology. The information may be computer readable instructions, data structures, modules of a program, or other data. Examples of a storage medium for a computer include, but are not limited to, a phase change memory (PRAM), a Static Random Access Memory (SRAM), a Dynamic Random Access Memory (DRAM), other types of Random Access Memory (RAM), a Read Only Memory (ROM), an Electrically Erasable Programmable Read Only Memory (EEPROM), a flash memory or other memory technology, a compact disc read only memory (CD-ROM), a compact disc Read Only Memory (ROM),

Digital Versatile Discs (DVDs) or other optical storage, magnetic cassettes, magnetic tape magnetic disk storage or other magnetic storage devices

Or any other non-transmission medium, may be used to store information that may be accessed by a computing device. Computer-readable media, as defined herein, does not include transitory computer-readable media (transitorymedia), such as modulated data signals and carrier waves.

It should also be noted that the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising one does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises an element.

It will be appreciated by those skilled in the art that embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.

The application may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular transactions or implement particular abstract data types. The application may also be practiced in distributed computing environments where transactions are performed by remote processing devices that are connected through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

In the present specification, each embodiment is described in a progressive manner, and each embodiment is mainly described in a different point from other embodiments, and identical and similar parts between the embodiments are all enough to refer to each other. For the system disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and the relevant points refer to the description of the method section.

The principles and embodiments of the present invention have been described herein with reference to specific examples, which are intended to facilitate an understanding of the principles and concepts of the invention and are to be varied in scope and detail by persons of ordinary skill in the art based on the teachings herein. In view of the foregoing, this description should not be construed as limiting the invention.

Claims (8)

1. A track abnormality detection method, characterized by comprising:

Acquiring a start point coordinate and an end point coordinate, and determining a group of tracks according to the start point coordinate and the end point coordinate, wherein the group of tracks comprises a plurality of tracks, and the track consists of a series of coordinate points according to time sequence;

Converting longitude and latitude coordinates of coordinate points in each track into polar coordinates based on a midpoint polar coordinate system;

Converting all the tracks into list-type features with equal lengths according to the polar coordinates;

Adopting an anomaly detector suitable for the list phenotype characteristics to perform anomaly detection on the list phenotype characteristics, and determining an anomaly track;

the step of converting all the tracks into list-type features with equal lengths according to the polar coordinates specifically comprises the following steps:

Uniformly dividing the circumference angle 2 pi into k parts, wherein each part comprises an radian range of 2 pi/k, distributing the angular coordinate of each coordinate point on one track to any one part of k parts, calculating the average value of the radial coordinates distributed to all coordinate points in any one part, wherein the average value of the radial coordinates is a distance-based characteristic, calculating the number of coordinate points distributed to any one part, wherein the number of coordinate points is a point-based characteristic, and splicing the distance-based characteristic and the point-based characteristic to determine a list-type characteristic until all the tracks are converted into the list-type characteristic with equal length;

or uniformly dividing a semi-circumference angle pi into k parts, wherein each part comprises a pi/k radian range, distributing the angular coordinate of each coordinate point on one track to any one part of k parts, calculating the average value of the radial coordinates distributed to all coordinate points in any one part, wherein the average value of the radial coordinates is a distance-based feature, counting the number of coordinate points with the angular coordinates of [0, pi ] and the number of coordinate points with the angular coordinates of [ pi, 2 pi), wherein the number of coordinate points with the angular coordinates of [0, pi) and the number of coordinate points with the angular coordinates of [ pi, 2 pi) are point-based features, and splicing the distance-based features and the point-based features until all tracks are converted into the list-type features with equal lengths.

2. The method for detecting a trace abnormality according to claim 1, wherein the acquiring the start point coordinates and the end point coordinates and determining a set of traces based on the start point coordinates and the end point coordinates, specifically comprises:

querying all tracks similar to the starting point coordinates and the end point coordinates from a historical track database to determine a group of tracks, wherein the similar tracks are ,Is the starting point coordinate of the similar track, S is the starting point coordinate,For euclidean distance, lambda is the distance threshold,The end point coordinates of the similar tracks are obtained, and D is the end point coordinates.

3. The track anomaly detection method according to claim 2, wherein the converting the longitude and latitude coordinates of the coordinate point in each track into polar coordinates based on the midpoint polar coordinate system specifically comprises:

determining a first connecting midpoint of the starting point coordinate and the ending point coordinate;

Establishing a first polar coordinate system by taking the midpoint of the first connecting line as a pole and taking the direction from the midpoint of the first connecting line to the starting point coordinate as a polar axis;

and converting longitude and latitude coordinates of the coordinate points in each track into polar coordinates based on the first polar coordinate system.

4. The track anomaly detection method according to claim 2, wherein the converting the longitude and latitude coordinates of the coordinate point in each track into polar coordinates based on the midpoint polar coordinate system specifically comprises:

determining a second connecting line midpoint of a starting point coordinate and an ending point coordinate in any track aiming at each track;

Establishing a plurality of second polar coordinate systems by taking the midpoint of the second connecting line as a pole and taking the direction from the midpoint of the second connecting line to the starting point coordinate in the track as a polar axis;

And converting longitude and latitude coordinates of any coordinate point in the track corresponding to the second polar coordinate system into polar coordinates based on any one of the second polar coordinate systems until the longitude and latitude coordinates of the coordinate point in each track are converted into polar coordinates.

5. The track anomaly detection method according to claim 2, wherein the converting the longitude and latitude coordinates of the coordinate point in each track into polar coordinates based on the midpoint polar coordinate system specifically comprises:

determining a first connecting midpoint of the starting point coordinate and the ending point coordinate;

Randomly selecting a track point from a group of tracks, taking the midpoint of the first connecting line as a pole, and taking the direction from the midpoint of the first connecting line to the track point as a polar axis to establish a third polar coordinate system;

and converting longitude and latitude coordinates of the coordinate points in each track into polar coordinates based on the polar coordinate system.

6. A trajectory anomaly detection system, comprising:

the system comprises a track determining module, a track processing module and a track processing module, wherein the track determining module is used for acquiring a starting point coordinate and an end point coordinate, and determining a group of tracks according to the starting point coordinate and the end point coordinate;

The polar coordinate conversion module is used for converting longitude and latitude coordinates of coordinate points in each track into polar coordinates based on a midpoint polar coordinate system;

The list-type feature conversion module is used for converting all tracks into list-type features with equal length according to the polar coordinates, and specifically comprises the steps of uniformly dividing a circumferential angle 2 pi into k parts, wherein each part comprises a radian range of 2 pi/k, distributing the angular coordinate of each coordinate point on one track to any part in the k parts, calculating the average value of the radial coordinate of each coordinate point distributed to any part, wherein the average value of the radial coordinate is a feature based on distance, calculating the number of coordinate points distributed to any part, the number of the coordinate points is a feature based on points, splicing the feature based on distance and the feature based on points, determining list-type features until all the tracks are converted into list-type features with equal length, or uniformly dividing half of the circumferential angle pi into k parts, wherein each part comprises a radian range of pi/k, distributing the angular coordinate of each coordinate point on one track to any part in the k parts, calculating the average value of the radial coordinate points distributed to all coordinate points in any part, calculating the radial coordinate points in any part, wherein the average value of the radial coordinate points is a feature based on distance, calculating the number of coordinate points distributed to any part, the coordinate points is a feature based on point number of points, splicing the feature based on point number [ 0] and the feature based on the number of the point [0, the feature based on pi and the feature between the point and the feature based on equal number [ 0] and the feature between the point [ feature and the feature based on the number [0, and the feature based on the feature is equal;

and the abnormality detection module is used for detecting the abnormality of the list-type characteristics by adopting an abnormality detector suitable for the list-type characteristics and determining an abnormal track.

7. An electronic device comprising a memory for storing a computer program and a processor that runs the computer program to cause the electronic device to perform the trajectory anomaly detection method of any one of claims 1-5.

8. A computer-readable storage medium, characterized in that it stores a computer program which, when executed by a processor, implements the trajectory anomaly detection method according to any one of claims 1 to 5.