CN-116226684-B - ETC abnormal data rapid detection method based on improved DTW algorithm

CN116226684BCN 116226684 BCN116226684 BCN 116226684BCN-116226684-B

Abstract

The invention discloses an ETC abnormal data rapid detection method based on an improved DTW algorithm, which comprises the steps of converting ETC transaction data into a vehicle track sequence ETra according to the spatiotemporal semantic characteristics of the ETC transaction data of a highway, inquiring and obtaining a portal track sequence ODLJ of the highway based on the vehicle track sequence ETra, starting from two ends of the vehicle track sequence ETra respectively, calculating matching similarity with the portal track sequence ODLJ, constructing a dynamic matching window according to the identified split matching points as boundaries, planning a dynamic path, and rapidly identifying abnormal track points within a limited range. The invention avoids a large amount of time-consuming matrix computation.

Inventors

ZOU FUMIN
WANG HAOLIN
LIN ZIYANG
ZHOU ZHAOYI
XING YUE
GUO FENG
CAI QIQIN
REN QIANG
LI NAN
LUO XU
WU SONGYANG
HUANG SHIBIN

Assignees

福建工程学院

Dates

Publication Date: 20260508
Application Date: 20230313

Claims (8)

1. The ETC abnormal data rapid detection method based on the improved DTW algorithm is characterized by comprising the following steps of: step 1, converting ETC transaction data into a vehicle track sequence ETra according to the spatiotemporal semantic characteristics of the ETC transaction data of the expressway; Step 2, inquiring and acquiring a portal track sequence ODLJ of the expressway based on the vehicle track sequence ETra; Step 3, respectively starting from two ends of the vehicle track sequence ETra and calculating the matching similarity with the portal track sequence ODLJ, wherein the specific steps of the step 3 are as follows: Step 3-1, using the initial feature point of the vehicle track sequence ETra as the semantic information matching of the current feature point to start the positive sequence; step 3-2, judging whether the current feature point of the vehicle track sequence ETra is the same as the semantic information of the corresponding feature point in the portal track sequence ODLJ, if so, adding the matched feature mark value of the portal track sequence ODLJ and the vehicle track sequence ETra together to execute step 3-6, otherwise, executing step 3-3; Step 3-3, setting or obtaining a dynamic search step length R for limiting quick search matching; step 3-4, judging that the current feature point of the vehicle track sequence ETra is in the dynamic retrieval step length If the characteristic points of the portal track sequence ODLJ are searched in the portal track sequence, executing the step 3-5, otherwise, executing the step 3-6; Step 3-5, judging whether the current characteristic point of the vehicle track sequence ETra is the same as the semantic information of the corresponding characteristic point in the portal track sequence ODLJ, if so, adding one to the matched characteristic mark value of the portal track sequence ODLJ and the vehicle track sequence ETra, and carrying out auxiliary mark value on the characteristic point in the retrieved vehicle track sequence track to output a result, otherwise, executing the step 3-6; Step 3-6, judging whether the characteristic points of the vehicle track sequence ETra are not matched, if yes, selecting the next characteristic point of the current sequence of the vehicle track sequence ETra as the current characteristic point and executing step 3-2, otherwise, executing step 3-7; step 3-7, judging whether the current matching is positive-order semantic information matching, if so, starting reverse-order semantic information matching by taking the end point characteristic points of the vehicle track sequence ETra as the current characteristic points and executing step 3-2, otherwise, executing step 3-8; Step 3-8, detecting each group of characteristic points corresponding to the matched characteristic mark value one by one, and adding a plurality of groups of characteristic points with auxiliary mark values into an abnormal range set, wherein the specific steps of the step 3-8 are as follows: Step 3-8-1, constructing a W window according to the identified segmentation matching points serving as boundaries: ODLJ is a path sequence and ETraj vehicle track sequence, And Track points ETraj and ODLJ respectively, which form a regular matrix D, n and m are the size of the matrix, i, j are the ith data of the query sequence and the jth data of the subsequence respectively, (2) Wherein the window has a size of , , ; Is the lateral dynamic search step size, The step length is dynamically searched for the longitudinal track point; step 3-8-2, each constructed window W uses an abnormal feature recognition algorithm AFC to carry out path planning detection on abnormal data in the window so as to recognize missed transactions or misdelivery easy data; Step 3-8-3, adding the identified data features into an abnormal range set; and 4, constructing a dynamic matching window according to the identified segmentation matching points as boundaries, performing dynamic path planning, and rapidly identifying abnormal track points in a limited range.
2. The rapid ETC anomaly data detection method based on the improved DTW algorithm of claim 1, wherein in step 3-3, the absolute value length of the start points of the vehicle track sequence ETra and the portal track sequence ODLJ plus the difference between the two tracks is used as the dynamic search step length for comparison , The expression of (2) is: (1) Wherein, the Representing the path length of the vehicle track sequence ETra, Representing the path length of the gantry track sequence ODLJ.
3. The ETC abnormal data rapid detection method based on the improved DTW algorithm of claim 1, wherein the step of the abnormal feature identification algorithm AFC is as follows: Step 3-8-2-1, combining standard road network topology according to n vehicle transaction portal frames to obtain a topology storage matrix of a corresponding standard subtree set ; Step 3-8-2-2, generating a storage matrix of a corresponding real-time dynamic running track subtree set of the vehicle according to the passing portal node of the on-road vehicle ETC transaction data updating storage matrix uploaded in real time through iterative analysis ; Step 3-8-2-3, marking a vehicle track set with an abnormal label according to a detection result to obtain an abnormal identification matrix by detecting the abnormality in the subtree set 。
4. The ETC abnormal data rapid detection method based on the improved DTW algorithm according to claim 3, wherein the specific steps of the step 3-8-2-1 are as follows: (1-1) generating a dynamic vehicle track based on vehicle transaction data, using a portal of a vehicle generated transaction as a root node of a subtree; (1-2) associating root nodes of a subtree with a standard topology Matching to obtain corresponding standard subtree set , Representing the ith standard subtree S; (1-3) based on the path selection algorithm, calculating the weight of each branch of the standard subtree set, wherein each standard subtree corresponds to a group for storing the weight of the branch.
5. The rapid ETC anomaly data detection method based on the improved DTW algorithm of claim 4, wherein (1-1) the dynamic track of the vehicle transaction data is extracted at fixed time intervals.
6. The ETC abnormal data rapid detection method based on the improved DTW algorithm according to claim 3, wherein the specific steps of the step 3-8-2-2 are as follows: (2-1) taking a portal node of the vehicle for completing the transaction at the moment T as a current node, namely, the current node enters a queue by a subtree root; (2-2) outputting the current node G1, and simultaneously enabling the first-level sub-nodes (G2 and G3) of the current node G1 to respectively calculate the time domain of the vehicle reaching each first-level sub-node according to the respective weights; (2-3) waiting for the system to confirm that both primary child nodes (G2, G3) have reached the departure time; (2-4) judging whether the vehicle generates transaction data with any one-level sub-node (G2, G3) portal frame in the corresponding time domain, if so, marking the one-level sub-node generating the transaction data as 0, pruning the subtree of the other sub-node of the same level and executing the step (2-5), otherwise, marking the corresponding one-level sub-node as1 and executing the step (2-5); (2-5) judging whether secondary sub-nodes (namely sub-nodes G4, G5, G6 and G7 of the primary sub-nodes) exist, if yes, executing (2-6), otherwise, ending the dynamic track matching to obtain a storage matrix of a real-time vehicle dynamic running track sub-set ; (2-6) Judging whether the first-level child nodes are all marked as '1', if yes, executing the step (2-7), otherwise, taking the first-level child nodes marked as '0' as current nodes and executing the step (2-2); And (2-7) judging whether the current node has unmatched peer nodes, if so, taking the node with the heavy weight in the unmatched peer nodes corresponding to the current node as the current node and executing the step (2-2), otherwise, taking the primary node corresponding to the secondary child node with the largest weight as the current node and executing the step (2-2), namely, a process of circularly executing from (2-2) to (2-7), and selecting one node with the largest weight each time until the topological subtree has no child node.
7. The rapid ETC abnormal data detection method based on the improved DTW algorithm of claim 3, wherein the method comprises the following steps of 3-8-2-3 And (3) with Dynamic matching is carried out to obtain an abnormal identification matrix of a vehicle passing through a portal frame , (3) = (4) (5) Wherein, the And (3) with A successful match is marked as 0, a non-match is marked as 1, i.e. the portal is abnormal, matrix The row represents the situation where one vehicle is transacted with a plurality of portals, and the column represents the situation where a plurality of vehicles are transacted with a single portal.
8. The ETC abnormal data rapid detection method based on the improved DTW algorithm of claim 3, further comprising the steps of: step 3-8-2-4, counting abnormal identification matrix The abnormal frequency of each portal is as follows: ,k=1,2...,n (6) Wherein, the Representing the frequency of gantry anomalies for each, For up to n portals contained in the matrix, Is an anomaly identification matrix The number of vehicles involved in supervision; Step 3-8-2-5, calculating a portal anomaly rate based on the portal anomaly frequency, wherein the portal anomaly rate calculation formula is as follows: (7) Wherein, the Representing the average value of the ETC portal anomaly rate during the period T, Indicating the abnormal frequency of the vehicle passing through the ETC portal during the t period, The number of vehicles passing through the ETC portal in the t time period is represented, and N represents the number of all vehicles of the ETC portal.

Description

ETC abnormal data rapid detection method based on improved DTW algorithm Technical Field The invention relates to the technical field of expressway management, in particular to an ETC abnormal data rapid detection method based on an improved DTW algorithm. Background At present, the largest-scale expressway electronic toll collection (Electronic Toll Collection, ETC) system is built in China, more than 2 ten thousand portal devices are deployed On the expressway of more than 16 ten thousand kilometers in China, more than 2 hundred million On Board Unit (OBU) devices of ETC are deployed, and daily ETC transaction data are nearly 10 hundred million [1]. ETC transaction data almost records traffic conditions of vehicles on the expressway, can be used for expressway traffic flow prediction [2-3], traffic time estimation [4-5], traffic demand visualization [6] and the like, and is expected to provide important auxiliary decision information service for expressway intelligent driving. However, due to equipment failure, car shielding, wireless crosstalk, etc., the highway ETC system inevitably has missed transactions and misdelivery easy events. Obviously, the ETC system is used for providing auxiliary decision information service for intelligent driving of the expressway, the error rate and the deletion rate of ETC data are required to be strictly controlled, and the error and the deletion condition of the ETC data are required to be accurately detected by depending on the context of the track semantic structure. The key problem of track abnormal point detection as time sequence data processing is one of domestic and foreign research hotspots, wherein DTW (Dynamic Time Warping) algorithm is used as a main stream method for track similarity measurement, and is widely researched and applied, such as user similarity analysis [8-9], travel mode analysis, travel path recommendation and the like. However, because the ETC transaction data volume is too huge and the data feature modeling of the system is lacked, partial provincial level platforms try to apply mainstream algorithms such as DTW and the like to measure the error rate and the missing rate of the ETC transaction data of the whole provincial expressway in one day, and the problems of long time, low efficiency and the like are encountered, so that the quality of the ETC transaction data of the expressway in various places in the whole country is basically unknown, the use efficiency of the expressway ETC system is seriously influenced, and the realization of the application value of the ETC big data is restricted. How to more effectively utilize the mass information provided by the ETC portal system and provide support for the operation management and the service of the expressway is one of the difficulties of the current expressway. Disclosure of Invention The invention aims to provide an ETC abnormal data rapid detection method based on an improved DTW algorithm. The technical scheme adopted by the invention is as follows: the ETC abnormal data rapid detection method based on the improved DTW algorithm comprises the following steps: step 1, converting ETC transaction data into a vehicle track sequence ETra according to the spatiotemporal semantic characteristics of the ETC transaction data of the expressway; Step 2, inquiring and acquiring a portal track sequence ODLJ of the expressway based on the vehicle track sequence ETra; Step 3, starting from two ends of the vehicle track sequence ETra respectively, and calculating the matching similarity with the portal track sequence ODLJ; step 4, constructing a dynamic matching window according to the identified segmentation matching points as boundaries, performing dynamic path planning and rapidly identifying abnormal track points in a limited range; Further, the specific steps of step 3 are as follows: Step 3-1, using the initial feature point of the vehicle track sequence ETra as the semantic information matching of the current feature point to start the positive sequence; step 3-2, judging whether the current feature point of the vehicle track sequence ETra is the same as the semantic information of the corresponding feature point in the portal track sequence ODLJ, if so, adding the matched feature mark value of the portal track sequence ODLJ and the vehicle track sequence ETra together to execute step 3-6, otherwise, executing step 3-3; Step 3-3, setting or obtaining a dynamic search step length R for limiting quick search matching; step 3-4, judging whether the current characteristic point of the vehicle track sequence ETra is searched for the characteristic point of the portal track sequence ODLJ in the dynamic search step length R, if so, executing step 3-5, otherwise, executing step 3-6; Step 3-5, judging whether the current characteristic point of the vehicle track sequence ETra is the same as the semantic information of the corresponding characteristic point in the portal track sequence ODLJ, if so, addin