[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN111159247A - A method for mining the propagation trajectory of regional traffic congestion - Google Patents

A method for mining the propagation trajectory of regional traffic congestion Download PDF

Info

Publication number
CN111159247A
CN111159247A CN201911138270.8A CN201911138270A CN111159247A CN 111159247 A CN111159247 A CN 111159247A CN 201911138270 A CN201911138270 A CN 201911138270A CN 111159247 A CN111159247 A CN 111159247A
Authority
CN
China
Prior art keywords
time
average speed
grid
grid area
congestion
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201911138270.8A
Other languages
Chinese (zh)
Other versions
CN111159247B (en
Inventor
王美红
谢东繁
赵小梅
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Beijing Jiaotong University
Original Assignee
Beijing Jiaotong University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Beijing Jiaotong University filed Critical Beijing Jiaotong University
Priority to CN201911138270.8A priority Critical patent/CN111159247B/en
Publication of CN111159247A publication Critical patent/CN111159247A/en
Application granted granted Critical
Publication of CN111159247B publication Critical patent/CN111159247B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24Querying
    • G06F16/245Query processing
    • G06F16/2458Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
    • G06F16/2465Query processing support for facilitating data mining operations in structured databases
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/29Geographical information databases
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00Pattern recognition
    • G06F18/20Analysing
    • G06F18/23Clustering techniques
    • G06F18/232Non-hierarchical techniques
    • G06F18/2321Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions
    • G06F18/23213Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions with fixed number of clusters, e.g. K-means clustering
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00Pattern recognition
    • G06F18/20Analysing
    • G06F18/24Classification techniques
    • GPHYSICS
    • G08SIGNALLING
    • G08GTRAFFIC CONTROL SYSTEMS
    • G08G1/00Traffic control systems for road vehicles
    • G08G1/01Detecting movement of traffic to be counted or controlled
    • G08G1/0104Measuring and analyzing of parameters relative to traffic conditions
    • G08G1/0125Traffic data processing
    • YGENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02ATECHNOLOGIES FOR ADAPTATION TO CLIMATE CHANGE
    • Y02A30/00Adapting or protecting infrastructure or their operation
    • Y02A30/60Planning or developing urban green infrastructure

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • General Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Evolutionary Computation (AREA)
  • Probability & Statistics with Applications (AREA)
  • Evolutionary Biology (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Artificial Intelligence (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Remote Sensing (AREA)
  • Fuzzy Systems (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Computational Linguistics (AREA)
  • Chemical & Material Sciences (AREA)
  • Analytical Chemistry (AREA)
  • Traffic Control Systems (AREA)

Abstract

本发明涉及一种区域交通拥堵传播轨迹挖掘方法,包括:1、将研究区域的城市道路区域按1km*1km的方格进行网格区域划分;2、计算网格区域的平均速度和流量数据;3、将各网格区域的平均速度、流量数据信息标准化;4、将标准化后的各网格区域的平均速度、流量数据进行聚类,得到各网格区域的交通状态分类;5、用“0‑1”标记网格区域是否发生拥堵事件,并提取道路发生拥堵的时间段,发生拥堵的位置信息;6、按时间基准点分类构造滑动窗口事务集,并对其应用跨事务时空关联规则,挖掘区域交通拥堵传播轨迹。本发明使用的数据易于收集,并通过大数据挖掘的方法,快速便捷地获得拥堵规律,具有良好的实际应用价值。

Figure 201911138270

The invention relates to a method for mining the propagation trajectory of regional traffic congestion, comprising: 1. dividing the urban road area of the research area into grid areas according to a grid of 1km*1km; 2. calculating the average speed and flow data of the grid area; 3. Standardize the average speed and flow data information of each grid area; 4. Cluster the normalized average speed and flow data of each grid area to obtain the traffic status classification of each grid area; 5. Use "" 0‑1” marks whether there is a congestion event in the grid area, and extracts the time period when the road is congested, and the location information of the congestion; 6. Classify the sliding window transaction set according to the time reference point, and apply the cross-transaction space-time association rule to it , and excavate the propagation trajectory of regional traffic congestion. The data used in the invention is easy to collect, and the congestion rule can be obtained quickly and conveniently through the method of big data mining, which has good practical application value.

Figure 201911138270

Description

Regional traffic jam propagation track mining method
Technical Field
The invention relates to the technical field of intelligent traffic systems, in particular to a regional traffic jam propagation track mining method based on cross-transaction space-time association rules.
Background
With the rapid development of economic society, the travel demand of urban residents is increased, the retention amount of automobiles in cities is always on an increasing trend, and the problem of traffic jam is increasingly serious due to the fact that the contradiction between traffic supply and demand is increasingly prominent under the restriction of the inherent road supply capacity of the cities. For this reason, many large and medium-sized cities have issued various types of traffic control measures, such as the private car restriction policy issued by Beijing. However, in the rush hour, some areas still have serious traffic jam, which affects the normal traveling of residents and reduces the traveling experience. In order to solve the problems of traffic jam in the existing large and medium-sized cities, environmental pollution and the like caused by the traffic jam, the mechanism of traffic jam generation, evolution and dissipation needs to be scientifically and deeply excavated, so that the traffic jam is effectively inhibited and prevented, citizens are guided to travel, a traffic jam area is avoided, and the travel efficiency is improved.
The normal social life of people depends on the normal operation of an urban traffic system, and the traffic in the city is also a frequent region of traffic jam, so that a jam evolution track is obtained by excavating the space-time correlation among jam regions, a source region of the jam generation and a space-time range of the jam evolution are found, a jam relieving measure can be taken in advance, and the influence caused by the jam is reduced. However, in the current research on mining the spatio-temporal correlation between congestion areas by using the correlation rule, the core idea is to divide and conquer time and space, or on the basis of time segmentation, apply the spatial correlation rule, and then complete mining of the spatio-temporal correlation rule based on time interval expansion in the temporal correlation rule; or attribute change caused by congestion evolution is ignored, and the process from no congestion to congestion of the road section due to the influence of traffic congestion of surrounding areas is not reflected.
Therefore, the invention designs a cross-transaction spatio-temporal association rule algorithm suitable for excavating the congestion spatio-temporal association based on a big data association rule excavating technology, excavates the spatio-temporal association of a congestion area, discovers the evolution track of the congestion on time and space, and provides the traffic management personnel with the prior knowledge of the traffic congestion. Through data verification, the method can effectively calculate the space-time relevance of the congestion area, excavate the evolution track of the traffic congestion of the area, and has better universality and feasibility.
Disclosure of Invention
The technical problems to be solved by the invention are as follows:
urban traffic jam frequently occurs, so that the time cost of resident trip is increased, and the experience of trip is reduced. At present, the research aiming at the space-time correlation of traffic jam still has the advantages of dividing and treating time and space, and the function of excavating jam evolution is not realized. The invention provides a regional traffic jam propagation track mining method based on a cross-transaction space-time association rule, which can be used for mining a source region of a jam and a range and a direction of jam propagation, so that a jam evacuation scheme can be prepared in advance, traffic flows in the jam region can be shunted in time, and traffic conditions of other regions are prevented from being influenced by the jam propagation.
In order to achieve the above object, the present invention provides a method for mining a propagation trajectory of regional traffic congestion,
step 1: dividing an urban road area of a research area into grid areas according to 1km by 1km grids;
step 2: calculating average speed and flow data of the grid area;
and step 3: standardizing the average speed and flow data information of each grid area;
and 4, step 4: the normalized average speed and flow data of each grid area are clustered to obtain the traffic state classification of each grid area, and the traffic parameter data set of each grid area is divided by using a clustering algorithm fusing 'kmeans + +' and FCM to generate 4 classifications, namely unblocked, basically unblocked, slightly blocked and blocked. The traffic parameter data set comprises average speed and flow data for a grid area;
and 5: marking whether the grid area is congested or not by using '0-1', if the grid area is congested in a certain period, marking as 1, otherwise, marking as 0; extracting the time slot when the road is congested and the position information of the congestion, wherein the position information is the number information of the grid area;
step 6: and constructing a sliding window transaction set according to the time reference point in a classified manner, applying a cross-transaction space-time association rule to the sliding window transaction set, and excavating a regional traffic jam propagation track.
The traffic data is collected by a bayonet device arranged near an intersection, and two adjacent bayonet devices in the same direction form 1 road section; firstly, counting the number of road sections and bayonet codes in each grid area; secondly, counting the average speed and the traffic flow of vehicles passing through each road section in a certain time period to obtain the average speed of the road section in the time period; and finally, averaging the average speeds of all road sections in the grid area to obtain the average speed of the grid area, and summing the flow data of all road sections in the grid to obtain the flow data of the grid area.
The time granularity of counting the average speed and traffic flow of vehicles passing through each road section is 15 minutes, and each day is divided into 96 time periods.
The average speed of the vehicles in each road section is calculated as follows:
first, an average speed calculation formula when the ith vehicle passes through the section R is calculated as follows:
Figure BDA0002280149260000041
wherein,
Figure BDA0002280149260000042
the average speed of the ith vehicle passing through the road section R; lRIs the length of the road segment R;
Figure BDA0002280149260000043
time when the ith vehicle passes through the road section R;
secondly, the average speed of the vehicles on the road section is calculated according to the following formula:
Figure BDA0002280149260000044
wherein, Vt,RIs the average speed of the road section R over the time period t; t is a time interval number, and t is 0,1,2, … …, 95; the number of vehicles passing through the road section R in the t period is nvol;
the calculation formula of the average velocity of each mesh region is as follows:
Figure BDA0002280149260000045
wherein, Vgrid,tThe average speed of grid area grid in a time period t; v. oft,RThe average speed of the R road section in the t period is obtained; t is a time interval number, and t is 0,1,2, … …, 95; num is the number of segments within the grid area grid.
The formula for calculating the traffic flow passing through the bayonet m by the time period t is as follows:
Figure BDA0002280149260000046
wherein, vehiclem,t0Is at t0A vehicle passing through the gate m in time; t is ti、tjRepresenting the start and end times of a period t; q. q.st,mThe flow rate passing through the bayonet m is a time period t; t is a time interval number, and t is 0,1,2, … …, 95;
the calculation formula of the flow data of the grid area is as follows:
Figure BDA0002280149260000051
wherein Q isgrid,tRepresenting the average flow of grid in a t period; num represents the number of checkpoints within the grid region grid.
The step6 specifically comprises the following steps:
step1, inputting a multi-element time sequence merging set, a minimum support degree, a minimum confidence degree, a time granularity size lambda and the length omega of a sliding time window;
step2, constructing a sliding time window transaction set according to the time reference point in a classified manner, and applying a cross-transaction space-time association rule to the sliding time window transaction set;
aiming at a certain time reference point, the steps of Step3-Step5 are carried out:
step3, counting the support degree of each item set in the sliding window transaction set, and screening according to the minimum support degree to obtain a frequent 1-item set of the time reference point;
step4, recursion is carried out on the frequent 1-item set by using a connecting Step and a pruning Step to form a frequent 2-item set, and then a frequent k-item set is calculated in sequence;
step5, calculating the confidence coefficient of the frequent k-item set, and screening according to the minimum confidence coefficient to generate a strong association rule;
step6, merging strong association rules obtained by mining omega time reference points, merging if a certain rule back piece of a previous time reference point is the same as a certain rule front piece of a next time reference point, and mining a plurality of strong association rules so as to mine the regional traffic jam propagation track.
In Step3, the support factor calculation formula is as follows:
Figure BDA0002280149260000061
frq (I (o ', t)) is a support degree count of the congestion item set I with a time period t and a position o'; n [ t ] is the number of transactions occurring in time period t; and o' is the location information of the congested area.
Step4, connecting Step: remembering frequent k-item set as Lk,LkFrom a set of candidate k-items CkFurther screening results in a candidate k-term set CkFrom Lk-1Self-ligation to generate, Lk-1When all subsets are connected with each other, space constraint, time constraint and attribute constraint are required to be met, the constraints are met, self-connection is carried out, and a candidate k-item set C is formedk
Step4, pruning Step: ckIs a frequent k-term set LkSuperset of (C)kMay not be all frequent, deleting items that are not likely to be a frequent k-item set first; if one waitsK-1 item set of the selected k-item set is not in Lk-1In this case, the candidate k-item set is unlikely to become a frequent item set, and is selected from CkThe middle deletion is a pruning process.
In Step5, the confidence calculation formula is as follows:
Figure BDA0002280149260000062
wherein,
Figure BDA0002280149260000063
o' and o "represent two different location information.
The invention has the beneficial effects that:
the method and the system utilize the historical traffic data set for clustering, determine the congestion state and mark the congestion state for the traffic data. After the time and the place of the congestion are comprehensively considered, the congestion space-time data is used for constructing a sliding window transaction set, a cross-transaction space-time association rule is applied to the transaction set, and the propagation track of the congestion between the regions is mined. According to the invention, the propagation track of congestion in a certain area can be predicted through the historical traffic state of a road section, the specific probability is displayed, and the transmission of the congestion in time and space is explored from different dimensions by crossing transaction space-time association rules, so that the evolution rule of the congestion is obtained. The analysis result can provide a travel scheme for travelers and a traffic control direction for traffic managers, and congestion is prevented from spreading to adjacent areas. The data used by the method is easy to collect, and the congestion rule is quickly and conveniently acquired by a big data mining method, so that the method has good practical application value.
Drawings
The invention has the following drawings:
fig. 1 is a general flowchart of a regional traffic congestion propagation track mining method according to the present invention.
FIG. 2 is a schematic diagram of the urban road grid area division of the present invention.
Fig. 3 shows the spatial relationship between the road meshes of the present invention.
FIG. 4 is a sliding time window transaction set of the present invention with epoch i as the temporal reference point.
Detailed Description
The invention is described in further detail below with reference to figures 1-4.
The basic concepts involved in the algorithm are first introduced:
definition 1: congestion time series aggregation: let S be { S ═ S1,s2,...sn}。TiIs a set of congestion zones, which is a set of observation values, T, for S in a time period ii={s1(i),s2(i),...sn(i) And (4) defining a multi-element time sequence merging set D as: d ═ T1,T2,...Tm}. D Each set of observations TiAs a transaction set, each is assigned an identification number TID.
And based on the congestion time sequence collection in the definition 1, recombining the congestion time sequence collection according to the time sequence to form a data base of the cross-transaction space-time association rule in the definition 2.
Definition 2: cross-transaction spatiotemporal association rules: is provided with
∑={e1(0),e1(1),...e1(ω-1),e2(0),e2(1),...e2(ω-1)...eu(0),...eu(ω -1) } is a set of congestion entries that are each sequence observations in the multi-element time-series merged set D, ω being the length of the sliding time window of D. Let time s (s is more than or equal to 1 and less than or equal to n-omega +1) be a reference time reference point of D, and if time s + gamma (gamma is more than or equal to 0 and less than or equal to omega-1) congestion item eiIf it occurs, mark ei(γ) belongs to Ts. Each congestion item ei(γ) assigning an identification number TID. Then the cross-transaction spatiotemporal association rule is an implication in the form of X → Y, and at the same time the following conditions are satisfied:
1)X∈∑,Y∈∑;
2)
Figure BDA0002280149260000081
3)
Figure BDA0002280149260000082
4)
Figure BDA0002280149260000083
5)
Figure BDA0002280149260000084
6)X=[ti,oi,v1],Y=[tj,oj,v1]x and Y satisfy the constraint defined in definition 5, v1Indicates congestion, oi、ojTwo distinct regions.
Definition 3:
item and item set: let F ═ F1,F2,......Fp) For a collection of all items, called item sets (items), each FbThe term (b) ═ 1, 2.... p) refers to an item, and the number of items contained in F (l) ═ k refers to a k-item set, for example, the set { westbill congestion, college road congestion, beijing south station congestion } is a 3-item set.
Definition 4:
sliding time window transaction set: and arranging the transaction sets according to the time sequence, wherein the sliding time window transaction set is formed by item sets corresponding to the continuous omega time points. The time period t ═ 7:00-7:15,7:15-7:30, … …,21:45-22:00 studied]The time series set S has n time series, each time series including a time period t. Constructing Σ from definitions 1 and 2, generates a sliding time window transaction set with different time reference points. If the set sliding time window is too large, the calculation efficiency of the algorithm is influenced; however, if the sliding time window is small, the influence of the duration of the time on the study content cannot be mined. So the appropriate ω is selected from the study purpose and transaction data set size. As shown in FIG. 4, wherein TiSet of congested areas for time period I, Ii,1And the congestion area set of the first time series in the period i is shown, n is the total number of the time series, omega is the length of a sliding time window, and TID is the number of the transaction set.
Definition 5: and (3) time constraint:
Figure BDA0002280149260000091
wherein, △ t is the time interval of the difference between two research periods, | △ t | ═ time-step, tα dα th period on day dβ kβ th time period of the z-th day, and the lambda is the time particle size and the continuity of the reaction time.
And (3) space constraint:
after the congestion event occurs, the congestion event spreads to the surrounding areas, namely, the congestion event is spatially adjacent to the surrounding areas, and the spatial relationship is shown in fig. 3.
And (4) attribute constraint:
Figure BDA0002280149260000092
wherein o isα(i is 1,2, … …, n) indicates a certain spatial position, 0 and 1 indicate whether the traffic is congested, and 0 indicates that the traffic is uncongested in a certain area in an adjacent time slot.
Definition 6:
the support degree is as follows: and (3) deforming based on the support degree of the classical association rule, and calculating the probability of the occurrence of an item set containing time, space and attribute constraints in the transaction set, so that the final rule can reflect the evolution rule of congestion in space and time. And when the support degree of the calculated k-item set is greater than the set minimum support degree, namely the k-item set is a frequent k-item set, and the k-item set is called a candidate k-item set before being compared with the minimum support degree. The support calculation formula is as follows:
Figure BDA0002280149260000101
frq (I (o ', t)) is a support degree count of the congestion item set I with a time period t and a position o'; n [ t ] is the number of transactions occurring in time period t; and o' is the location information of the congested area.
Definition 7:
confidence coefficient: based on the support obtained by definition 6, calculating the confidence of the cross-transaction spatio-temporal association rule, wherein the calculation formula is as follows:
Figure BDA0002280149260000102
wherein
Figure BDA0002280149260000103
o' and o "represent two different location information.
As shown in fig. 1 to 4, the method for mining an area traffic jam propagation track according to the present invention includes the following steps:
step 1: dividing an urban road area of a research area into grid areas according to 1km by 1km grids;
step 2: calculating average speed and flow data of the grid area;
the traffic data is collected by the gate equipment arranged near the intersection, and two adjacent gate equipment in the same direction form 1 road section; firstly, counting the number of road sections and bayonet codes in each grid area; secondly, counting the average speed and the traffic flow of vehicles passing through each road section in a certain time period to obtain the average speed of the road section in the time period; finally, averaging the average speeds of all road sections in the grid area to obtain the average speed of the grid area, and summing the flow data of all road sections in the grid to obtain the flow data of the grid area; counting the time granularity of the average speed and the traffic flow of vehicles passing through each road section to be 15 minutes, dividing each day into 96 time periods, and obtaining the speed and the flow data of each time period of each grid area according to the method;
the average speed of the vehicles in each road section is calculated as follows:
first, an average speed calculation formula when the ith vehicle passes through the section R is calculated as follows:
Figure BDA0002280149260000111
wherein,
Figure BDA0002280149260000112
is the ith vehicleAverage speed of the vehicle as it passes through section R; lRInputting longitude and latitude information of upstream and downstream checkpoints of the road section in a mode of calling a Baidu map API (application program interface) for the length of the road section R, so as to obtain the distance between the upstream and downstream checkpoints of the road section;
Figure BDA0002280149260000113
is the time when the ith vehicle passes through the section R.
Secondly, the average speed of the vehicles on the road section is calculated according to the following formula:
Figure BDA0002280149260000114
wherein, Vt,RIs the average speed of the road section R over the time period t; t is a time interval number, where t is 0,1,2, … …,95, that is, the time interval is divided by taking 15min as an interval, one day is divided into 96 time intervals, and the time span for acquiring data is d days; the number of vehicles passing through the road section R in the t period is nvol;
the calculation formula of the average velocity of each mesh region is as follows:
Figure BDA0002280149260000121
wherein, Vgrid,tThe average speed of grid area grid in a time period t; v. oft,RThe average speed of the R road section in the t period is obtained; t is a time interval number, and t is 0,1,2, … …, 95; num is the number of segments within the grid area grid.
The formula for calculating the traffic flow passing through the bayonet m by the time period t is as follows:
Figure BDA0002280149260000122
wherein, vehiclem,t0Is at t0A vehicle passing through the gate m in time; t is ti、tjRepresenting the start and end times of a period t; q. q.st,mThe flow rate passing through the bayonet m is a time period t; t is the slot number, and t is 0,1,2, … …, 95.
The calculation formula of the flow data of the grid area is as follows:
Figure BDA0002280149260000123
wherein Q isgrid,tRepresenting the average flow of grid in a t period; num represents the number of checkpoints within the grid region grid.
And step 3: and standardizing the average speed and flow data information of each grid area.
And 4, step 4: the normalized average speed and flow data of each grid area are clustered to obtain the traffic state classification of each grid area, and the traffic parameter data set of each grid area is divided by using a clustering algorithm fusing 'kmeans + +' and FCM to generate 4 classifications, namely unblocked, basically unblocked, slightly blocked and blocked. The traffic parameter data set includes average speed and flow data for a grid area.
And 5: marking whether the grid area is congested or not by using '0-1', if the grid area is congested in a certain period, marking as 1, otherwise, marking as 0; and extracting the time slot when the road is jammed and the position information of the jam, wherein the position information is the number information of the grid area.
Step 6: and (4) constructing a sliding window transaction set according to definition 4 in a classification mode according to the time reference points, applying a cross-transaction space-time association rule to the sliding window transaction set, and excavating a regional traffic jam propagation track. The method specifically comprises the following steps:
step 1: inputting a multi-element time sequence merging set, a minimum support degree, a minimum confidence degree, a time granularity size lambda and the length omega of a sliding time window.
Step 2: a sliding time window transaction set is constructed according to definition 4, sorted by temporal reference point, as shown in figure 4. A cross-transaction spatiotemporal association rule is applied to a sliding time window transaction set.
Taking a certain time reference point as an example:
step 3: the support count is counted for each set of items in the sliding window transaction set. And obtaining the frequent 1-item set of the time reference point according to the minimum support degree screening. The support calculation formula is shown as follows:
Figure BDA0002280149260000131
frq (I (o ', t)) is a support degree count of the congestion item set I with a time period t and a position o'; n [ t ] is the number of transactions occurring in time period t; and o' is the location information of the congested area.
Step 4: and recursion is carried out on the frequent 1-item set by using a connecting step and a pruning step to form a frequent 2-item set, then the frequent k-item sets are sequentially calculated, and the interaction of congestion on a time line is explored. Setting omega to be 2, therefore, defining time-step to be 15min in 5, namely mining the current time period tαAnd t isα+1Frequent 2-item sets between periods.
Wherein the connection step is as follows: remembering frequent k-item set as Lk,LkFrom a set of candidate k-items CkFurther screening results in a candidate k-term set CkFrom Lk-1Self-ligation to generate, Lk-1When all subsets are connected with each other, whether the spatial property of the connection item satisfies the spatial constraint needs to be considered, as shown in fig. 3; and whether the time constraint is satisfied, as in equation 8. The congestion propagation characteristics are considered while the attribute constraints need to be satisfied, as in equation 9. Can self-connect to form a candidate k-item set C only when the above factors are satisfiedk
Pruning: ckIs a frequent k-term set LkA superset of (i), i.e. CkMay not be all frequent, so deleting items that are not likely to be a frequent k-item set first is beneficial to reducing computational costs. If the k-1 item set of a candidate k-item set is not in Lk-1Then the candidate k-term set is unlikely to become a frequent term set, and is thus driven from CkThe middle deletion is a pruning process.
Step 5: and calculating the confidence coefficient of the frequent k-item set, and screening according to the minimum confidence coefficient to generate a strong association rule.
Step 6: and (3) merging the strong association rules obtained by mining omega time reference points, namely merging if the back part of a certain rule of the former time reference point is the same as the front part of a certain rule of the latter time reference point, mining a plurality of strong association rules, and mining the regional traffic jam propagation track as shown in definition 2.
The confidence calculation formula is as follows:
Figure BDA0002280149260000141
wherein,
Figure BDA0002280149260000142
o' and o "represent two different location information.
Those not described in detail in this specification are within the skill of the art.

Claims (10)

1.一种区域交通拥堵传播轨迹挖掘方法,其特征在于,包括如下步骤:1. a regional traffic jam propagation trajectory mining method, is characterized in that, comprises the steps: 步骤1:将研究区域的城市道路区域按1km*1km的方格进行网格区域划分;Step 1: Divide the urban road area of the study area into a grid area of 1km*1km; 步骤2:计算网格区域的平均速度和流量数据;Step 2: Calculate the average speed and flow data of the grid area; 步骤3:将各网格区域的平均速度、流量数据信息标准化;Step 3: Standardize the average speed and flow data information of each grid area; 步骤4:将标准化后的各网格区域的平均速度、流量数据进行聚类,得到各网格区域的交通状态分类,通过使用融合“kmeans++”与FCM的聚类算法对网格区域的交通参数数据集进行划分,产生4种分类,分别为畅通、基本畅通、轻微拥堵、拥堵;所述交通参数数据集包括网格区域的平均速度和流量数据;Step 4: Cluster the normalized average speed and flow data of each grid area to obtain the traffic status classification of each grid area, and use the clustering algorithm integrating "kmeans++" and FCM to analyze the traffic parameters of the grid area. The data set is divided into 4 categories, namely unblocked, basically unblocked, slightly congested, and congested; the traffic parameter dataset includes the average speed and flow data of the grid area; 步骤5:用“0-1”标记网格区域是否发生拥堵事件,若在某一时段网格区域发生拥堵,则标记为1,否则,标记为0;并提取道路发生拥堵的时间段,发生拥堵的位置信息,位置信息为网格区域的编号信息;Step 5: Mark the grid area with "0-1" whether there is a congestion event. If the grid area is congested during a certain period of time, mark it as 1, otherwise, mark it as 0; and extract the time period when the road is congested. The location information of the congestion, the location information is the number information of the grid area; 步骤6:按时间基准点分类构造滑动窗口事务集,对滑动窗口事务集应用跨事务时空关联规则,挖掘区域交通拥堵传播轨迹。Step 6: Classify the sliding window transaction set according to the time reference point, apply the cross-transaction spatiotemporal association rule to the sliding window transaction set, and mine the regional traffic congestion propagation trajectory. 2.如权利要求1所述的区域交通拥堵传播轨迹挖掘方法,其特征在于:所述交通数据由安置在交叉口附近的卡口设备采集,同方向相邻两个卡口设备构成1个路段;首先,统计各网格区域内的路段数量及卡口编码;其次,统计一定时段内通过各路段车辆的平均速度和车流量,获得该时段路段的平均速度;最后,将网格区域内所有路段的平均速度进行平均获得网格区域的平均速度,网格内所有路段的流量数据求和获得网格区域的流量数据。2. The method for mining the propagation trajectory of regional traffic congestion according to claim 1, wherein the traffic data is collected by a bayonet device placed near the intersection, and two adjacent bayonet devices in the same direction form a road section ; First, count the number of road sections and bayonet codes in each grid area; second, count the average speed and traffic flow of vehicles passing through each road section within a certain period of time to obtain the average speed of the road section in that period; The average speed of the road sections is averaged to obtain the average speed of the grid area, and the flow data of all road sections in the grid are summed to obtain the flow data of the grid area. 3.如权利要求2所述的区域交通拥堵传播轨迹挖掘方法,其特征在于:统计通过各路段车辆的平均速度和车流量的时间粒度为15分钟,将每天划分为96个时段。3. The method for mining the propagation trajectory of regional traffic congestion as claimed in claim 2, wherein the time granularity of counting the average speed and traffic flow of vehicles passing through each road section is 15 minutes, and each day is divided into 96 time periods. 4.如权利要求3所述的区域交通拥堵传播轨迹挖掘方法,其特征在于,各路段车辆的平均速度计算过程如下:4. The regional traffic congestion propagation trajectory mining method as claimed in claim 3, wherein the average speed calculation process of each road section vehicle is as follows: 首先,计算第i辆车通过路段R时的平均速度计算公式如下:First, the calculation formula for the average speed of the i-th vehicle passing through the road section R is as follows:
Figure FDA0002280149250000021
Figure FDA0002280149250000021
其中,
Figure FDA0002280149250000022
为第i辆车通过路段R时的平均速度;lR为路段R的长度;
Figure FDA0002280149250000023
为第i辆车通过路段R的时间;
in,
Figure FDA0002280149250000022
is the average speed of the i-th vehicle passing through the road segment R; l R is the length of the road segment R;
Figure FDA0002280149250000023
is the time for the i-th vehicle to pass the road segment R;
其次,所述路段车辆的平均速度计算公式如下:Secondly, the formula for calculating the average speed of vehicles in the road section is as follows:
Figure FDA0002280149250000024
Figure FDA0002280149250000024
其中,Vt,R为路段R在时段t的平均速度;t为时段编号,t=0,1,2,……,95;nvol为路段R在t时段内通过车辆数;Among them, V t,R is the average speed of the road section R in the time period t; t is the time period number, t=0,1,2,...,95; nvol is the number of vehicles passing through the road section R in the time period t; 各网格区域的平均速度的计算公式如下:The formula for calculating the average velocity of each grid area is as follows:
Figure FDA0002280149250000025
Figure FDA0002280149250000025
其中,Vgrid,t为网格区域grid在时段t的平均速度;vt,R为R路段在t时段的平均速度;t为时段编号,t=0,1,2,……,95;Num为网格区域grid内的路段数。Among them, V grid,t is the average speed of grid area grid in time period t; v t,R is the average speed of R road section in time period t; t is the time period number, t=0,1,2,...,95; Num is the number of road segments in the grid area grid.
5.如权利要求3所述的区域交通拥堵传播轨迹挖掘方法,其特征在于:通过所述时段t通过卡口m的车流量的计算公式如下:5. The method for excavating the propagation trajectory of regional traffic congestion as claimed in claim 3, wherein the calculation formula of the traffic flow through the bayonet m through the time period t is as follows:
Figure FDA0002280149250000031
Figure FDA0002280149250000031
其中,vehiclem,t0为在t0时间通过卡口m的车辆;ti、tj表示时段t的开始和结束时刻;qt,m为时段t通过卡口m的流量;t为时段编号,t=0,1,2,……,95;Among them, vehicle m, t0 is the vehicle passing through the bayonet m at time t 0 ; t i and t j represent the start and end time of the time period t; q t,m is the flow through the bayonet m in the time period t; t is the time period number , t=0,1,2,...,95; 所述网格区域的流量数据的计算公式如下:The calculation formula of the flow data of the grid area is as follows:
Figure FDA0002280149250000032
Figure FDA0002280149250000032
其中,Qgrid,t表示网格grid在t时段的平均流量;num表示网格区域grid内的卡口数。Among them, Q grid, t represents the average flow of the grid in the t period; num represents the number of bayonets in the grid area.
6.如权利要求1所述的区域交通拥堵传播轨迹挖掘方法,其特征在于,所述步骤6具体包括以下步骤:6. The method for mining the propagation trajectory of regional traffic congestion as claimed in claim 1, wherein the step 6 specifically comprises the following steps: Step1、输入多元时间序列合并集合、最小支持度、最小置信度、时间粒度大小λ以及滑动时间窗口的长度ω;Step1. Enter the multivariate time series merged set, the minimum support, the minimum confidence, the time granularity λ, and the length of the sliding time window ω; Step2、按时间基准点分类构造滑动时间窗口事务集,对滑动时间窗口事务集应用跨事务时空关联规则;Step 2. Construct a sliding time window transaction set according to the time reference point classification, and apply cross-transaction spatiotemporal association rules to the sliding time window transaction set; 针对某一时间基准点,进行Step3-Step5的步骤:For a certain time reference point, perform the steps of Step3-Step5: Step3、对滑动窗口事务集中的每个项集统计支持度计数,依据最小支持度筛选,获得该时间基准点的频繁1-项集;Step3. Count the support degree of each item set in the sliding window transaction set, and filter according to the minimum support degree to obtain the frequent 1-item set at the time reference point; Step4、在频繁1-项集上使用连接步、剪枝步递推形成频繁2-项集,然后依次计算频繁k-项集;Step4. Use connection step and pruning step to recursively form frequent 2-itemsets on frequent 1-itemsets, and then calculate frequent k-itemsets in turn; Step5、计算频繁k-项集的置信度,依据最小置信度进行筛选,生成强关联规则;Step5. Calculate the confidence of frequent k-itemsets, filter according to the minimum confidence, and generate strong association rules; Step6、对相距ω个时间基准点挖掘得到的强关联规则进行合并,若前一时间基准点的某一规则后件与后一时间基准点的某一规则前件相同,则进行合并,挖掘出多项强关联规则,从而挖掘区域交通拥堵传播轨迹。Step6. Merge the strong association rules excavated from ω time reference points. If the consequent of a rule at the previous time reference point is the same as the antecedent of a rule at the next time reference point, then merge and mine out A number of strong association rules are used to mine the propagation trajectory of regional traffic congestion. 7.如权利要求6所述的区域交通拥堵传播轨迹挖掘方法,其特征在于:Step3中,支持度计算公式如下所示:7. The regional traffic congestion propagation trajectory mining method as claimed in claim 6, wherein: in Step3, the support calculation formula is as follows:
Figure FDA0002280149250000041
Figure FDA0002280149250000041
其中,frq(I(o',t))为时段t、位置为o'的拥堵项集I的支持度计数;N[t]为时段t发生的事务数;o'为拥堵区域的位置信息。Among them, frq(I(o', t)) is the support count of the congestion item set I in the time period t and the location o'; N[t] is the number of transactions occurred in the time period t; o' is the location information of the congested area .
8.如权利要求6所述的区域交通拥堵传播轨迹挖掘方法,其特征在于:Step4中连接步:记频繁k-项集为Lk,Lk由候选k-项集Ck进一步筛选产生,候选k-项集Ck由Lk-1自连接产生,Lk-1所有子集相互连接时需要满足空间约束、时间约束和属性约束,满足以上约束进行自连接,形成候选k-项集Ck8. The method for mining the propagation trajectory of regional traffic congestion as claimed in claim 6, characterized in that: in Step4, a connection step: denote frequent k -itemsets as Lk, and Lk is generated by further screening of candidate k -itemsets Ck , The candidate k-item set C k is generated by the self-connection of L k -1 . When all subsets of L k-1 are connected to each other, they need to satisfy the space constraints, time constraints and attribute constraints, and self-connection is carried out to form a candidate k-item set when the above constraints are satisfied. C k . 9.如权利要求6所述的区域交通拥堵传播轨迹挖掘方法,其特征在于:Step4中剪枝步:Ck是频繁k-项集Lk的超集,Ck的成员可能不全是频繁的,先删除不可能为频繁k-项集的项;如果一个候选k-项集的k-1项集不在Lk-1中,则该候选k-项集也不可能成为频繁项集,将其从Ck中删除,为剪枝过程。9. The regional traffic congestion propagation trajectory mining method as claimed in claim 6, characterized in that: pruning step in Step4: C k is the superset of frequent k-itemsets L k , and the members of C k may not be all frequent , first delete the items that are unlikely to be frequent k-itemsets; if the k-1 itemsets of a candidate k-itemset are not in L k-1 , the candidate k-itemsets cannot become frequent itemsets either. It is deleted from C k as a pruning process. 10.如权利要求6所述的区域交通拥堵传播轨迹挖掘方法,其特征在于:Step5中,置信度计算公式如下所示:10. The method for mining the propagation trajectory of regional traffic congestion as claimed in claim 6, wherein: in Step5, the confidence calculation formula is as follows:
Figure FDA0002280149250000051
Figure FDA0002280149250000051
其中,
Figure FDA0002280149250000052
o'和o”表示两个不同的位置信息。
in,
Figure FDA0002280149250000052
o' and o" represent two different location information.
CN201911138270.8A 2019-11-20 2019-11-20 Regional traffic jam propagation track mining method Active CN111159247B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201911138270.8A CN111159247B (en) 2019-11-20 2019-11-20 Regional traffic jam propagation track mining method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201911138270.8A CN111159247B (en) 2019-11-20 2019-11-20 Regional traffic jam propagation track mining method

Publications (2)

Publication Number Publication Date
CN111159247A true CN111159247A (en) 2020-05-15
CN111159247B CN111159247B (en) 2024-01-12

Family

ID=70556028

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201911138270.8A Active CN111159247B (en) 2019-11-20 2019-11-20 Regional traffic jam propagation track mining method

Country Status (1)

Country Link
CN (1) CN111159247B (en)

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111640304A (en) * 2020-06-04 2020-09-08 扬州大学 Automatic quantitative extraction method for traffic jam propagation characteristics of continuous flow traffic facility
CN111914768A (en) * 2020-08-06 2020-11-10 南京航空航天大学 A grid-based method for judging the crowded state of terminal passenger flow
CN112035873A (en) * 2020-08-18 2020-12-04 合肥市大数据资产运营有限公司 Time-space trajectory data desensitization method
CN114170796A (en) * 2021-11-20 2022-03-11 无锡数据湖信息技术有限公司 Algorithm improved congestion propagation analysis method
CN114333359A (en) * 2021-12-30 2022-04-12 浪潮卓数大数据产业发展有限公司 Artificial intelligence-based self-adaptive traffic signal lamp control method and system
CN114821514A (en) * 2022-06-30 2022-07-29 交通运输部公路科学研究所 A remove detecting system for detecting tunnel road surface wet and slippery state
CN116842018A (en) * 2023-07-06 2023-10-03 江西桔贝科技有限公司 Big data screening method and system
CN117037465A (en) * 2023-05-24 2023-11-10 东北师范大学 Traffic jam propagation mode sensing and visual analysis method
CN118506579A (en) * 2024-07-09 2024-08-16 云南公路联网收费管理有限公司 Intelligent induction method and system based on high-speed flow monitoring

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106257301A (en) * 2016-05-12 2016-12-28 内蒙古工业大学 Distributed space time correlation model trace tracking method based on statistical inference
CN107844602A (en) * 2017-11-24 2018-03-27 重庆邮电大学 A kind of Forecasting Methodology based on time-space attribute correlation rule
US20190266902A1 (en) * 2018-02-26 2019-08-29 Honeywell International Inc. Method and system for generating a grid map that shows air traffic intensity

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106257301A (en) * 2016-05-12 2016-12-28 内蒙古工业大学 Distributed space time correlation model trace tracking method based on statistical inference
CN107844602A (en) * 2017-11-24 2018-03-27 重庆邮电大学 A kind of Forecasting Methodology based on time-space attribute correlation rule
US20190266902A1 (en) * 2018-02-26 2019-08-29 Honeywell International Inc. Method and system for generating a grid map that shows air traffic intensity

Cited By (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111640304B (en) * 2020-06-04 2021-01-08 扬州大学 Automatic quantitative extraction method of traffic congestion propagation features for continuous flow traffic facilities
CN111640304A (en) * 2020-06-04 2020-09-08 扬州大学 Automatic quantitative extraction method for traffic jam propagation characteristics of continuous flow traffic facility
CN111914768B (en) * 2020-08-06 2024-10-22 南京航空航天大学 Method for judging traffic congestion state of terminal building based on grid
CN111914768A (en) * 2020-08-06 2020-11-10 南京航空航天大学 A grid-based method for judging the crowded state of terminal passenger flow
CN112035873A (en) * 2020-08-18 2020-12-04 合肥市大数据资产运营有限公司 Time-space trajectory data desensitization method
CN114170796A (en) * 2021-11-20 2022-03-11 无锡数据湖信息技术有限公司 Algorithm improved congestion propagation analysis method
CN114170796B (en) * 2021-11-20 2023-01-10 无锡数据湖信息技术有限公司 Algorithm improved congestion propagation analysis method
CN114333359A (en) * 2021-12-30 2022-04-12 浪潮卓数大数据产业发展有限公司 Artificial intelligence-based self-adaptive traffic signal lamp control method and system
CN114821514A (en) * 2022-06-30 2022-07-29 交通运输部公路科学研究所 A remove detecting system for detecting tunnel road surface wet and slippery state
CN117037465A (en) * 2023-05-24 2023-11-10 东北师范大学 Traffic jam propagation mode sensing and visual analysis method
CN116842018B (en) * 2023-07-06 2024-02-23 上海比滋特信息技术有限公司 Big data screening method and system
CN116842018A (en) * 2023-07-06 2023-10-03 江西桔贝科技有限公司 Big data screening method and system
CN118506579A (en) * 2024-07-09 2024-08-16 云南公路联网收费管理有限公司 Intelligent induction method and system based on high-speed flow monitoring

Also Published As

Publication number Publication date
CN111159247B (en) 2024-01-12

Similar Documents

Publication Publication Date Title
CN111159247A (en) A method for mining the propagation trajectory of regional traffic congestion
Almatar Traffic congestion patterns in the urban road network:(Dammam metropolitan area)
An et al. Mining urban recurrent congestion evolution patterns from GPS-equipped vehicle mobility data
Ambühl et al. Empirical macroscopic fundamental diagrams: New insights from loop detector and floating car data
CN111008223B (en) A method for calculating regional traffic congestion correlation based on spatiotemporal association rules
Li et al. Identifying important variables for predicting travel time of freeway with non-recurrent congestion with neural networks
Loulizi et al. Steady‐State Car‐Following Time Gaps: An Empirical Study Using Naturalistic Driving Data
Necula Analyzing traffic patterns on street segments based on GPS data using R
EP2590151A1 (en) A framework for the systematic study of vehicular mobility and the analysis of city dynamics using public web cameras
Liu et al. Intersection delay estimation from floating car data via principal curves: a case study on Beijing’s road network
CN115311854B (en) Vehicle space-time track reconstruction method based on data fusion
Chen et al. Data analytics approach for travel time reliability pattern analysis and prediction
Chepuri et al. Examining travel time reliability-based performance indicators for bus routes using GPS-based bus trajectory data in India
Li et al. Real-time congestion prediction for urban arterials using adaptive data-driven methods
Oskarbski et al. Estimating the average speed of public transport vehicles based on traffic control system data
Wang et al. Digital roadway interactive visualization and evaluation network applications to WSDOT operational data usage.
CN106355882A (en) Traffic state estimation method based on in-road detector
CN110021161B (en) Traffic flow direction prediction method and system
He et al. Link dynamic vehicle count estimation based on travel time distribution using license plate recognition data
Heshami et al. A stochastic microscopic based freeway traffic state and spatial-temporal pattern prediction in a connected vehicle environment
Wu Measuring reliability in dynamic and stochastic transportation networks
Pallela et al. Examining the lane-wise time headway and speed characteristics at curb-side bus stop on four-lane divided urban arterials
Wang et al. Congestion prediction for urban areas by spatiotemporal data mining
Liu et al. Vehicle trajectory reconstruction with sparse automatic license plate recognition data for urban road networks
KR102242554B1 (en) Inspection target selection apparatus and method for evaluating the performance of vehicle detectors

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant