CN108364467B - A Road Condition Information Prediction Method Based on Improved Decision Tree Algorithm - Google Patents

Abstract

The invention discloses a road condition information prediction method based on an improved decision tree algorithm, comprising: determining and analyzing attributes of road connectivity based on the influence factor of road connectivity; collecting road data, data preprocessing, calculating information entropy, and calculating each attribute Calculate the attribute entropy of each attribute based on the association function, calculate the weight value of each attribute based on the association function value of each attribute; calculate the information gain of each attribute based on the information entropy, the attribute entropy of each attribute and the weight value of each attribute , build a decision tree according to the size of the information gain of each attribute, and predict the road conditions according to the decision tree. The present invention constructs a decision tree by calculating the correlation function value of the attribute and expanding the attribute weight value obtained by the information entropy operation, which can overcome the problem that the traditional ID3 algorithm tends to select elements with more possible values as high-weight attributes. Use the constructed decision tree to predict the degree of road congestion improvement in the next period.

Description

A Road Condition Information Prediction Method Based on Improved Decision Tree Algorithm

technical field

The invention relates to the technical field of decision tree algorithm and road traffic flow model, in particular to a road condition information prediction method based on an improved decision tree algorithm.

Background technique

With the advancement of global urbanization, the number of motor vehicles in cities increases year by year. By the end of June 2016, the number of motor vehicles in Beijing had reached 5.44 million, ranking first in the country. For megacities such as Beijing, Tokyo, and New York, this figure will continue to rise over time. The huge number of motor vehicles will not only cause traffic congestion, but also cause air pollution, energy waste and other problems, hinder urban development and reduce people's living standards. Among the world's 200 large cities (population greater than 800,000), Beijing ranks 15th in terms of traffic congestion. Congested traffic conditions not only bring extra time consumption to people's travel, but also increase fuel consumption, which greatly increases the operating costs of transportation, logistics and other industries. In 2011, logistics companies lost $13.7 billion in delays caused by traffic jams in Australia's six largest cities. In China, transportation fuel costs account for 46 percent of a logistics company's total operating costs. To sum up, alleviating road congestion and improving road traffic conditions can not only reduce people's travel costs, but also help reduce economic losses caused by road congestion and reduce exhaust emissions. The reasons for traffic congestion are diverse. Under the existing traffic conditions, maximizing the use of road resources can effectively alleviate congestion. The study of road information is helpful to intuitively and efficiently evaluate the traffic flow and wayfinding on the road. the effectiveness of the algorithm.

1. Decision tree algorithm and improvement

Decision tree is a commonly used classification and regression method, which infers the classification rules of decision tree representation from a set of disordered and irregular cases. The decision tree classification algorithm adopts a top-down recursive method, compares the attribute values among the internal nodes of the decision tree, judges the branches from the node downward according to different attribute values, and obtains the classification result when the leaf node is judged. The nodes in the decision tree represent an attribute, the test results are output in the branches of leaf nodes, and the results corresponding to different conditions are further verified in the nodes of the next layer. Therefore, each path from the root of the decision tree to the leaf node corresponds to a selection method. The attribute weight value of the node closer to the root is higher, and the entire decision tree corresponds to a set of expression rules.

Decision tree classification algorithm consists of two steps of decision tree generation and pruning. The generative algorithm constructs a binary or multi-fork decision tree by inputting a set of sample parameters with class labels. For a binary tree, the internal node is generally represented as a logical judgment; the edge of the tree can be regarded as the branch result of the logical judgment. For a multi-fork tree, the internal nodes are the attributes of the sample set, the edges are all the values of the attribute, the number of attribute values determines the number of edges in the decision tree, and the leaf nodes of the tree are the category labels. The method used in the decision tree construction process is a top-down recursive method. The specific algorithm is as follows:

AlgorithmGenerate_decision_tree

Input: training sample samples, represented by discrete-valued attributes; attribute_list, a collection of candidate attributes.

Output: A decision tree generated from the given sample.

(1), create node N;

(2) If the samples are all in the same class C, return N as a leaf node, mark class C, and the program ends;

(3) If attribute_list is empty, return N as a leaf node, marked as the most common class in samples, and the program ends;

(4), select the attribute h_attribute with the highest information gain in the attribute_list;

(5), mark the node N as h_attribute;

(6), for each known value Si in h_attribute, grow a branch with the condition h_attribute=Si from node N;

(7), let Si be the set of samples with h_attribute=Si in samples, if Si is empty, add a leaf, marked as the most common class in samples, otherwise add one and return by Generate_decision_tree(Si, attribute_list, h_attribute) node.

The key to the process of decision tree generation lies in how to choose a good logical judgment or attribute. Choosing appropriate attributes to construct a decision tree is an NP-hard problem, so only heuristic strategies can be used for attribute selection. Attribute selection relies on impurity measures for various sample subsets, including information gain, information gain ratio, evidence weight, minimum description length, etc.

Since the data in the real world is generally imperfect, the corresponding measurement method should be selected according to the characteristics of the problem and attribute fields. In addition, for the lack of values in some attributes, inaccurate data, noise or errors, etc., the decision tree can reduce noise through pre-pruning and post-pruning to ensure the integrity and accuracy of the data. The basic decision tree construction method does not consider noise, so the generated decision tree completely fits the training samples. In the case of noise, complete fitting will lead to overfitting, that is, the complete fitting of the classification model to the training data will make the training data fit. The classification model's ability to predict the classification of the displayed data decreases. Therefore, denoising by pruning the data is another part of the decision tree construction process, which will simplify the tree and make it easier to understand.

Under the guidance of the decision tree idea, Quinlan proposed the ID3 algorithm to construct a decision tree based on entropy and information gain. The algorithm uses information entropy as heuristic knowledge for the sample set to select appropriate classification attributes to realize the operation of dividing the sample set into several subsets. The nodes of the decision tree are constructed layer by layer by selecting the attribute with the highest information entropy as the preferential classification condition for the sample set. In this way, the information required for the training sample subset obtained after classification will be the smallest, and using the attribute with the highest information entropy to divide the sample set contained in the current node will make the attributes of all generated sample subsets mixed. reduced to a minimum. In order to find the best way to classify samples, the number of questions to be asked when building a decision tree should be as much as possible, that is, to reduce the depth of the tree, and the information gain function is one of the ways to provide this balanced division.

Suppose S is a training set sample, which contains n categories of samples, denoted by C ₁ , C ₂ , ..., C _n respectively, and the entropy value of S is

where pi represents the probability of class Ci. If the n types of training samples in S are regarded as n different messages, then the entropy of S represents the average number of bits required to encode each message, and |S|×entropy(S) represents the required number of bits to encode S. number of bits. |S| denotes the number of samples in S.

Suppose that attribute A divides S into m parts, and its own entropy or expected information divided according to A can be expressed as the following formula:

Among them, S _i represents the ith subset of the sample set divided according to the attribute A, and |S| and |S _i | represent the number of samples in S and S _i , respectively. Information gain is used to measure the expected reduction of entropy, so the information gain obtained by dividing S by attribute A is

Gain(S,A)=Entropy(S)-Entropy(S,A)

Gain(S,A) refers to the expected compression of entropy due to knowing the value of attribute A. According to the definition of information gain, the greater the information gain, the greater the reduction of entropy, and the more blunt the node is; therefore, the greater the Gain(S, X), the more information the selection of the test attribute X provides for the classification. Correspondingly, according to the information gain value of each attribute, the larger one is selected as the branch attribute of the decision tree.

Based on the existing decision tree algorithm, the ID3 algorithm takes information entropy as the primary reference index and applies it to the selection of decision tree node attributes, which improves the relevance of sample classification. The ID3 algorithm is as follows:

Algorithm ID3

Input: training samples, sample attributes with discrete values, set of candidate inductive attributes

Output: a decision tree

(1) Initialize the decision tree T and create a node N. If the sample set planting contains a class of attributes Q, return N as the root node of the tree, and Q is the overall attribute set.

(2) If (all leaf nodes (X', Q') in T satisfy that X belongs to a class or Q' is empty) then the algorithm stops; (3) Else{Any one that does not have the state in (2) The leaf nodes of (X', Q')};

(4) Attribute A in For each Q'

Do calculate the information gain gain(A, X');

(5) Select the attribute B with the highest information gain as the test attribute of the node (X', Q');

(6) The value b _i of For each B

Do{Branch from the depth of the node (X', Q'), representing the test output B=bi; obtain the subset X _i whose B value is equal to _bi in X, and generate the corresponding leaf nodes _{(X i '} , Q'-{B});}

(7) Jump to step (2);

The ID3 algorithm is a greedy algorithm that uses a top-down, divide-and-conquer recursive method to build a decision tree. The termination condition of this recursion is that all samples within a node belong to the same class. If there is no attribute that can be used to divide the current sample set, then use the voting principle to make it a mandatory leaf node and mark it as the sample type with the most categories.

It can be seen that the advantage of the ID3 algorithm is that the method is simple and the processing ability of the sample set is strong, but it depends on the features with a large number of features, and the attribute with the most attribute value is not necessarily the best. In other words, for the problem that more factors need to be considered in the actual situation, the traditional ID3 algorithm has certain shortcomings in the priority determination of attributes, which is often due to the higher information entropy value of attributes with more options.

Therefore, it is necessary to avoid only considering information entropy when creating a decision tree. In this regard, Zhang et al. adopted an improved ID3 algorithm to avoid this part of the problem, such as analyzing and calculating the sensitivity of attributes to give more reasonable attribute weights, using The joint density function based on information entropy performs secondary evaluation and integration of decision tree nodes. In these two algorithms, the sensitivity calculation will derive the corresponding neural network according to the input attribute value and train it, which will greatly increase the complexity of the algorithm, and the algorithm efficiency is not high; the analysis using the joint density function is only suitable for discrete types. data, not necessarily compatible with the data of the present invention.

SUMMARY OF THE INVENTION

In view of the deficiencies in the above problems, the present invention provides a road condition information prediction method based on an improved decision tree algorithm.

To achieve the above object, the present invention provides a method for predicting road condition information based on an improved decision tree algorithm, including:

Step 1. Determine the influencing factors of road connectivity, the influencing factors include lane length R _l , number of lanes R _s , lane width R _d , number of traffic lights R _x , average length of continuous driving R _l *, number of road intersections L _n , The number of connected road segments L _r , whether the road segment contains bus stops B _s and the lane change index _Le ;

Step 2. Determine and analyze the attributes of the road connectivity force based on the influencing factors in step 1. The attributes include road capacity R _m , lane width R _d , expected waiting time T _s , average number of turns L _g on the road, and average length of continuous driving R _l *. Whether the road section contains bus stop B _s and lane change index _Le ;

Step 3. Collect road data;

Step 4. Data preprocessing: Eliminate unsatisfactory data and repair data;

Step 5: Calculate the information entropy E(S) based on the collected road data;

In the formula: S is the training set sample of road data, which contains n categories of samples, which are represented by C ₁ , C ₂ , ..., C _n respectively; pi _{represents the probability of class C i ;}

Step 6: Calculate the attribute entropy E(S, A) of each attribute based on the collected road data;

Among them, S _i represents the ith subset of training set samples divided according to attribute A, and |S| and |S _i | represent the number of samples in S and S _i , respectively;

Step 7, calculate the correlation function value CF(A) of each attribute based on the correlation function;

In the formula: X _im-1 and X _im are the specific values of the parameter X _ij , the subscript j represents each condition of attribute A, i represents each value condition of the data, and n is the total amount of data;

Step 8. Calculate the weight value Wg(A) of each attribute based on the associated function value CF(A) of each attribute;

In the formula: m is the number of attributes, CF(1), CF(2)...CF(m) are the correlation function values of each attribute respectively;

Step 9. Calculate the information gain Gain'(S,A) of each attribute based on the information entropy E(S), the attribute entropy E(S,A) of each attribute, and the weight value Wg(A) of each attribute;

Gain'(S,A)=(E(S)-E(S,A))*Wg(A)

Step 10: Sort and construct a decision tree according to the size of each attribute information gain, and predict road conditions according to the decision tree.

As a further improvement of the present invention, in step 2, the road capacity R _m is:

where α _l is the lane attenuation coefficient.

As a further improvement of the present invention, in step 2, the expected waiting time T _s is:

In the formula, T _p is the ratio of the time of each traffic direction to the total cycle time.

As a further improvement of the present invention, in step 2, the average turning number L _g of the road section is:

As a further improvement of the present invention, in step 4, excluding unsatisfactory data includes:

Exclude data with traffic flow greater than the maximum limit value;

Exclude the data whose road speed is greater than the maximum limit value;

Exclude data with negative or empty traffic flow and road speed;

Exclude data where the road speed is zero, but the traffic flow is not zero;

Data with zero traffic flow but non-zero road speed is excluded.

As a further improvement of the present invention, in step 4, the data repairing includes: using data of an adjacent road or an adjacent time to repair.

As a further improvement of the present invention, between step 4 and step 5, it also includes:

Data classification: Construct a road connectivity decision tree for congestion and smooth conditions based on the average traffic density at the inflow end.

As a further improvement of the present invention, in step 10, the attribute with the largest information gain is used as the root node of the decision tree, the attribute with the second largest information gain is used as the second layer node of the decision tree, and so on to construct a decision tree.

Compared with the prior art, the beneficial effects of the present invention are:

The present invention uses the method of the correlation function to give a more reasonable evaluation to the attribute value weight. The decision tree is constructed by calculating the value of the association function of the attribute and expanding the attribute weight value obtained by the information entropy operation, which can not only overcome the problem that the traditional ID3 algorithm tends to select elements with more possible values as high-weight attributes, At the same time, the correlation between attributes is taken into account in the algorithm, which more comprehensively reflects the weight of attributes.

Description of drawings

1 is a flowchart of a method for predicting road condition information based on an improved decision tree algorithm disclosed in an embodiment of the present invention;

2 is a schematic diagram of a decision tree in an off-peak period disclosed by an embodiment of the present invention;

3 is a schematic diagram of a decision tree during peak hours disclosed by an embodiment of the present invention;

FIG. 4 is a schematic diagram of the correct rate of influence of a single factor on the connectivity force during off-peak hours disclosed by an embodiment of the present invention;

FIG. 5 is a schematic diagram of the accuracy of judging connectivity by two algorithms during off-peak hours disclosed in an embodiment of the present invention;

6 is a schematic diagram of road prediction accuracy under different road conditions during off-peak hours disclosed by an embodiment of the present invention;

FIG. 7 is a schematic diagram of the correct rate of influence of a single factor on the connectivity force during peak hours disclosed by an embodiment of the present invention;

FIG. 8 is a schematic diagram showing the accuracy of the judgment of connectivity between two algorithms during peak hours disclosed in an embodiment of the present invention;

FIG. 9 is a schematic diagram showing the accuracy of road prediction under different road conditions during peak hours according to an embodiment of the present invention.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative work fall within the protection scope of the present invention.

Below in conjunction with accompanying drawing, the present invention is described in further detail:

The invention provides a road condition information prediction method based on an improved decision tree algorithm, and predicts the road conditions by using the improved decision tree ID3 algorithm. The present invention uses the method of the correlation function to give a more reasonable evaluation to the attribute value weight. The decision tree is constructed by calculating the value of the association function of the attribute and expanding the attribute weight value obtained by the information entropy operation, which can not only overcome the problem that the traditional ID3 algorithm tends to select elements with more possible values as high-weight attributes, At the same time, the correlation between attributes is taken into account in the algorithm, which more comprehensively reflects the weight of attributes. The definition formula of information gain is appropriately adjusted according to the value of the correlation function of the attribute.

First, when analyzing an attribute using a correlation function, the value of the attribute's correlation function is calculated first. Let A be an attribute value of data set P, and B be a category attribute in data set P. The relationship between attribute A and its category attribute B is as follows:

有以下关联函数定义式：right

There are the following associated function definitions:

In this formula, X _im-1 and X _im can be regarded as the specific value of the general parameter X _ij , which refers to the specific quantity value of a certain data, the subscript j represents each possible situation of the attribute A, and i represents the data For each possible value, the total amount of data is represented by n.

Next, normalize the value of the association function for each attribute. Assuming that there are m attributes, the correlation function value of each attribute is CF(1), CF(2)...CF(m), and the corresponding attribute weight value can be expressed as:

Among them, 0<A≤m; then, the weighted information gain of attribute A can be expressed as the following form:

Gain'(S,A)=(Entropy(S)-Entropy(S,A))*Wg(A)

In the process of constructing decision tree, Gain'(S,A) can effectively replace Gain(S,A) as a new standard for attribute classification. This can effectively avoid preferentially selecting attributes with more values when selecting nodes, and at the same time, the weight values of attribute values are processed with fidelity, which reduces the difference between the information gain and the actual situation, and ensures that the In the process, the more influential attributes are preferentially selected.

specific:

As shown in Figure 1, the present invention provides a method for predicting road condition information based on an improved decision tree algorithm, including:

Step 1. Determine the influencing factors of road connectivity:

If you want to use the decision tree algorithm to quantitatively analyze the road connectivity, you must first clarify the corresponding influencing factors and environmental variables. There are many factors that affect road connectivity, from the initial design intention and construction standards of the road to the specific geographical location and social environment, real-time weather, general traffic flow direction and driver habits, whether pedestrians abide by traffic rules, whether there are sudden traffic accidents and other factors. In the present invention, the emphasis will be placed on road information, and the analysis from the road information not only conforms to the scientific research standard that the data is objective without additional factors, but also facilitates the collection of data, ensuring the objectivity and validity of the experimental results. The influencing factors include lane length R _l , number of lanes R _s , lane width R _d , number of traffic lights R _x , duration of traffic lights R _t , average length of continuous driving R _l *, number of road intersections L _n , number of connected road segments L _r , whether the road segment is Including bus stop B _s and lane change index _Le . in:

1), Lane length R _l

Lane length defines the road bearing capacity and is also one of the basic properties of road connectivity. The longer the lane length, the higher the maximum number of vehicles waiting to pass during the congestion period. Considering the speed and distance at the time of starting, the more vehicles waiting, the smaller the proportion of the traffic passing through the intersection to the total waiting vehicles when releasing, which translates into a relatively weak ability to alleviate road congestion. It can be seen that the influence of lane length on road connectivity is very significant.

2), the number of lanes R _s

The effect of the number of lanes on the connectivity force is similar to that of the lane length. As the basic attributes of the road segment, these two determine the capacity of the road and indirectly affect the strength of the connectivity.

3), lane width R _d

Due to the inconsistency between urban road planning and road connectivity objectives, even the lane widths of different road sections in adjacent blocks are not completely consistent. This factor results in significant differences in the traffic speeds of different road sections in local areas. The speed difference in this aspect directly affects the driving environment such as vehicle starting, normal driving, and passing through intersections. According to the "Code for Design of Urban Roads", the ideal continuous traffic flow road lane width should be 3.6 meters or more. When the lane width is less than this value, the average speed of traffic flow on the road section during peak hours will drop significantly.

4), the number of traffic lights R _x

Urban roads are not only areas for motor vehicles to pass through, but also important places for pedestrians to travel. Correspondingly, there are not only traffic lights at intersections to control traffic flow, but also traffic lights in non-intersection sections to govern the people crossing the traffic flow, which leads to the phenomenon of delaying local traffic flow. Therefore, the number of traffic lights has an impact on road connectivity. also in this study. It is worth noting that the traffic lights at the intersection reflect the various choices of road connectivity, and can also be used as a reference for the start and end points of the lane. The pedestrian traffic lights in the road section are used to block the connectivity to a certain extent. The value recorded here is only the value within the road segment, and does not include the lights at the intersections at both ends.

5), traffic light duration R _t

The alternating sequence of traffic lights is not the same as the passing time of each direction, which determines the passing time of a single traffic flow. Frequent switching of traffic status lights will make the starting stage of driving occupy more crossing time, which will affect the traffic. The unwinding speed of the flow. It is difficult to see the relationship between this attribute and road connectivity by simply considering the duration of traffic lights. Therefore, in the algorithm implementation stage, the present invention combines the number and duration of traffic lights to calculate the expected non-waiting duration of a single road as an influencing factor for these two attributes.

6), the average length of continuous driving R _l *

When a motor vehicle is driving, it will inevitably slow down or stop temporarily when it encounters an intersection, which brings a blocking effect to the traffic flow. Therefore, when considering the aspect of continuous driving, this paper chooses the average value of continuous driving length as one of the influencing factors of road connectivity.

7), the number of road intersections L _n

In the block road environment, due to the small traffic flow, traffic will not be blocked during off-peak hours, and there are no traffic lights at the intersections of some roads. As a result, the number of intersections in some road sections is more than the number of traffic lights. Under this condition, only considering the number of traffic lights is not enough to indicate the inflow and outflow conditions of road traffic, so the number of intersections in the road section is introduced as one of the factors that constitute the connectivity conditions of the road section. .

8), the number of connecting road segments L _r

The number of junctions in the introduced road segment is not only to distinguish it from the number of traffic lights, but also to be one of the parameters to describe the degree of connection between the current road and other road segments. To further refine this degree of connection, this study introduces the attribute of the number of connected road segments. The intersections at home and abroad are generally cross or T-shaped, and the number of corresponding connecting sections is 3 or 2 in turn. If there is construction work or temporary restrictions on traffic in a certain direction, the value will be reduced accordingly. The larger the value of this attribute, the more choices of traffic flow at the outflow end of the current road segment, and the stronger the corresponding road connectivity.

9) Whether the road section contains bus stop B _s

Apart from private cars and taxis, buses are also a factor that cannot be ignored in the urban road traffic environment. Due to the large size of the bus itself and the need to stop at the stop, it is prone to frequent changes in the speed of the bus during road travel, and short-term area congestion caused by stop and stop. These conditions will cause other vehicles on the road to merge, accelerate and decelerate more frequently, and then affect the speed of the traffic flow.

10), lane change index _Le

车道为直行道路，左侧

车道为左转道路，若R_s为偶数，右侧

车道为直行道路，左侧为左转道路。在实际调研中，两者的实际差数的绝对值为该路段的行车变道指数。In the process of driving on the road, for various purposes, the driver will inevitably encounter the situation of changing lanes, for example, to turn at the next intersection; the current lane driving direction specified by the road marking is different from the intended destination; overtaking changes change lanes or avoid traffic accidents, etc. From the scientific research point of view, the present invention cannot effectively count the driver's subjective lane change willingness and sudden road failures. Therefore, from the perspective of objective road design, the present invention conducts statistical analysis on the driving change behavior caused by the traffic guide signs, that is, judges Whether the preset steering of the lane after entering the road segment is consistent with the steering sign given by the landmark at the end of the road segment. For the road segment with the number of lanes greater than or equal to 2, if the number of lanes R _s is odd, the default right side of the road segment

Lane is straight road, left

The lane is a left turn road, if R _s is an even number, the right

The lane is a straight road and the left is a left turn road. In the actual investigation, the absolute value of the actual difference between the two is the lane change index of the road section.

Obviously, evaluating and quantifying road connectivity is not an easy task, as there are many influencing factors and the possibility of mutual influence. Therefore, after the above-mentioned impact factors are proposed, it is very necessary to summarize and organize them, and give the attribute set that can be realized by the improved ID3 algorithm.

Step 2. Determine and analyze the attributes of the road connectivity force based on the influencing factors in step 1. The attributes include road capacity R _m , lane width R _d , expected waiting time T _s , average road turning number L _g , average continuous driving length R _l *, Whether the road section contains bus stop B _s and lane change index _Le . in:

From the perspective of the road itself, the lane width can be independent of the lane length and the number of lanes as a separate detection standard, but considering the length of the lane or the number of lanes alone is too thin, so this study combines the two and incorporates the lane attenuation coefficient α _l , After synthesizing the three, the attribute road capacity _Rm is formed as the attribute of comprehensive analysis of road connectivity. The definition of road capacity _Rm is as follows:

因此只需要对所有值进行求和即可得到该路段的期望等候时间T_s，定义式如下：Next, the relevant information of the traffic signal lights is processed: considering that the traffic directions and traffic durations of different lights are different, it is difficult to achieve a balance within the data set if a unified timing method or traffic sequence evaluation method is adopted. In order to affect the validity of the analysis results, it is advisable to use the attribute of expected waiting time to comprehensively reflect the impact of the duration and number of traffic lights on road connectivity from the perspective of road driving. The expected waiting time is the expected value of the time when the vehicle stops and waits due to the traffic light caused by the traffic light on the target road section. For each traffic light on the road section, the time of each traffic direction accounts for a fixed value T _p in the total cycle time, and T _p is determined by the traffic light duration R _t , then the expectation of waiting time is

Therefore, it is only necessary to sum all the values to obtain the expected waiting time T _s of the road section, which is defined as follows:

Similarly, considering the number of road intersections and the number of connected road segments alone is too simple, the difference between the two, the average number of turns at the intersection, can well reflect whether the outflow end of the current road has a variety of choices. The average number of turns L _g of the road segment is defined as follows:

In summary, this study analyzes the factors that affect road connectivity by taking the characteristics of the road itself, the distribution and waiting time of traffic lights, the attributes of adjacent intersections, and driving conditions as the four main characteristics. In subsequent experiments, this paper will divide and integrate all attributes into these attributes: road characteristic attributes include road capacity R _m , lane width R _d ; traffic signal characteristic attributes include expected waiting time T _s ; adjacent intersection characteristic attributes include road average turning The number L _g ; the characteristic attributes of driving conditions include the average length of continuous driving R _l *, whether the road section contains a bus stop B _s , and the driving lane change index L _e .

Step 3. Collect road data;

After clarifying the influencing factors of road connectivity, the present invention collects road data, and selects data that meets the experimental conditions for subsequent experiments. For static information such as road length, number of lanes, etc., it is collected through on-the-spot investigation, literature review, and map surveying and mapping. In order to investigate the road connectivity force, this study collects and compares the road speed data in a specified unit time. According to the change value of the road speed, combined with the vehicle speed-flow model, the road flow change is calculated to qualitatively deduce the strength of the connectivity force.

In recent years, the digitization of Beijing's road traffic information has developed rapidly. After the establishment of the Beijing Traffic Information External Release System, the functions of intersection monitoring and road traffic data collection have been applied to daily life respectively, and are used by commonly used map tools to display real-time road information. In this paper, the road traffic speed in the southeastern part of Beijing in the afternoon time period (14:00-15:30) and the evening time period (17:00-18:30) is collected every 15 minutes as the original data. The example data is shown in Table 1. Show:

Table 1

Step 4. Data preprocessing:

Considering the difference in traffic flow in different sections of the section per unit time, an effective screening mechanism should be established in the data preprocessing stage. There are a lot of researches on the preprocessing of traffic data at home and abroad. On this basis, this paper summarizes some common problems that affect the experimental results for the collected road traffic data, and proposes a method for road connectivity data preprocessing, which mainly includes data validity. Sexuality analysis and data supplementation.

1), remove the data that does not meet the requirements:

In the process of collecting road condition information, it is inevitable to encounter sudden road accidents and large-scale traffic congestion caused by traffic flow and vehicle speed exceeding a reasonable threshold. The density-flow model contradicts. For data under such extreme conditions, it is difficult to find effective information for summarizing universal laws. Therefore, the present invention proposes the following data elimination rules to eliminate erroneous data, so as to improve the effectiveness of data mining in temporal and spatial associations.

Exclude data with traffic flow greater than the maximum limit value;

Exclude the data whose road speed is greater than the maximum limit value;

Exclude data with negative or empty traffic flow and road speed;

Exclude data where the road speed is zero, but the traffic flow is not zero;

Data with zero traffic flow but non-zero road speed is excluded.

2), data repair:

For the data that has been eliminated and some road condition information that cannot be accurately collected, it is necessary to supplement and adjust the missing data at sporadic moments. In this study, the data after the initial screening were repaired by the data near the road or the near time. For the missing data in a certain period of time, the average value of the road information at the outflow end or inflow end at the adjacent time is used to supplement the simulation and then perform data smoothing processing. In this case, only when the adjacent road has a strong correlation with the data-missing road can be used under the circumstances.

The data processed by the above two processes and the attribute parameters generated by some operations can be used to generate a decision tree. Some data samples are shown in Table 2:

Table 2

In Table 2, when the attribute B _s is 1, it means that there is a bus stop in this section, and 0 means that it is not established. A road condition improvement value of 0 indicates that the traffic flow density on the current road section has not changed. The absolute value of the specific value of this value indicates the span area where the road condition changes. A positive value indicates an improvement toward the gain, and a negative value indicates a change in the debuff. Due to the large time span of statistics, the road changes in different road sections are complicated, so when judging the improvement value of road flow density, the situation with more distribution is taken as the result of the current road section to obtain the content.

In order to simplify this part of the attribute information, for the more specific attributes, the attribute range is divided according to the numerical distribution to meet the needs of the decision tree algorithm. According to a total of 3090 training sample sets for all 103 roads in 3 days and 10 time periods, including 2394 valid samples, the road capacity R _m , the expected waiting time T _s , the average turning number L _g of the road section, and the average continuous driving length R _l *The four attributes are divided as shown in Table 3:

table 3

Step 5. Data classification: Construct the road connectivity decision tree for congestion and smooth conditions according to the average traffic density at the inflow end.

The improved information gain is obtained by calculating the information entropy and attribute weight value of the sorted attributes that affect the road connectivity. Then, a decision tree is constructed according to the obtained data to determine the influence of attributes. However, for the collected data in the evening period (17:00-18:30) and the afternoon period (14:00-15:30), the evening period is the peak period, and the afternoon period is the off-peak period; there are significant differences in the obtained results. Therefore, according to the road information under different traffic flow pressures in different periods, two decision trees for road connectivity in peak hours and non-peak hours are constructed respectively.

Step 6: Calculate the information entropy E(S) based on the collected road data;

In the formula: S is the training set sample of road data, which contains n categories of samples, which are represented by C ₁ , C ₂ , ..., C _n respectively; pi _{represents the probability of class C i ;} where:

By classifying and dividing a total of 2394 valid sample sets, they are divided into two groups of data in the afternoon and evening to calculate the information entropy of attributes respectively. The division of these two sets of data is not only based on simple time division, but also based on the average driving speed of all samples, which can also be understood as different congestion levels. The level is less than 30%, and the traffic density in the evening period has increased significantly, and the average vehicle speed has also decreased compared with the afternoon period. Among all valid samples, there are 1347 groups of valid data in the afternoon period, and 1047 groups of valid data in the evening peak period.

First, the information entropy is calculated for the average turning number attribute of the road segment in the afternoon period. For the 1347 training samples, there are 727 sets of data with improved road traffic density and 620 sets of samples without improvement. According to the formula, the information entropy can be obtained:

Step 7: Calculate the attribute entropy E(S, A) of each attribute based on the collected road data;

Among them, S _i represents the ith subset of training set samples divided according to attribute A, and |S| and |S _i | represent the number of samples in S and S _i , respectively;

Take the road capacity R _m as an example:

Attribute entropy is calculated for the road capacity _Rm attribute of the road connectivity force. For the sample set S, R _m divides S into three parts, R _m ≤ 1812, 1812<R _m ≤ 2834, and R _m >2834, that is, the capacity is small, medium, and large. In the present invention, S _v is used to represent the sample set with the attribute value v, |S _small |=234, |S _medium |=687, |S _large |=426, in |S _small |, there are two values of class R _m The number of samples are 101 and 133 respectively, and the entropy of | _Ssmall | is:

In the same way, it can be calculated that _the entropy _in S and S are 0.752 and 0.821, respectively, so the expected information for dividing S by attribute R _m is:

Similarly, the information gain for the remaining attributes can be derived in the same way.

Step 8, calculate the correlation function value CF(A) of each attribute based on the correlation function;

In the formula: X _im-1 and X _im are the specific values of the parameter X _ij , the subscript j represents each case of attribute A, i represents each value case of the data, and n is the total amount of data; where:

In order to avoid the influence of attribute distribution on the analysis results, the weight value is obtained by calculating the weight function of each attribute and the corresponding information entropy weight value. Taking the attribute R _m as an example, the composition of its data is shown in Table 4:

Table 4 Single factor results of road capacity in sample data

Similarly, the present invention can calculate the correlation function values of the remaining six attributes, as shown in Table 5:

Table 5 Other attribute information entropy weight values

Step 9. Calculate the weight value Wg(A) of each attribute based on the association function value CF(A) of each attribute;

In the formula: m is the number of attributes, CF(1), CF(2)...CF(m) are the correlation function values of each attribute respectively;

Step 10: Calculate the information gain Gain'(S,A) of each attribute based on the information entropy E(S), the attribute entropy E(S,A) of each attribute, and the weight value Wg(A) of each attribute;

Gain'(S,A)=(E(S)-E(S,A))*Wg(A)

Step 11: Sort and construct a decision tree according to the size of the information gain of each attribute, and predict road conditions according to the decision tree; the method of constructing the decision tree is:

The attribute with the largest information gain is used as the root node of the decision tree, and the attribute with the second largest information gain is used as the second-level node of the decision tree, and so on, to construct a decision tree.

For off-peak hours, according to the ID3 decision tree algorithm based on attribute weight and the above-mentioned related information entropy operation, the decision tree shown in Figure 2 is given. From this decision tree, the present invention can see that, in the afternoon time period, the attribute with the largest gain of information entropy based on weight is the average number of turns of the road section, so it is used as the root node of the whole tree, and the classification of different samples is carried out according to different sample classification conditions. Select the expected waiting time attribute with the second largest information entropy gain as the second layer node, and so on until all samples are classified.

Different from the afternoon period, the decision tree obtained for the collected peak period data is shown in Figure 3.

Based on the above results, road conditions are predicted for roads under different road conditions, and the prediction results are shown in Figure 4-9.

The above are only preferred embodiments of the present invention, and are not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (8)

1. a road condition information prediction method based on improved decision tree algorithm, is characterized in that, comprises: Step 1. Determine the influencing factors of road connectivity, the influencing factors include lane length R _l , number of lanes R _s , lane width R _d , number of traffic lights R _x , average length of continuous driving R _l *, number of road intersections L _n , The number of connected road segments L _r , whether the road segment contains bus stops B _s and the lane change index _Le ; Step 2. Determine and analyze the attributes of the road connectivity force based on the influencing factors in step 1. The attributes include road capacity R _m , lane width R _d , expected waiting time T _s , average number of turns L _g on the road, and average length of continuous driving R _l *. Whether the road section contains bus stop B _s and lane change index L _e ; Step 3. Collect road data; Step 4. Data preprocessing: Eliminate unsatisfactory data and repair data; Step 5: Calculate the information entropy E(S) based on the collected road data;

In the formula: S is the training set sample of road data, which contains n categories of samples, which are represented by C ₁ , C ₂ , ..., C _n respectively; pi _{represents the probability of class C i ;} Step 6: Calculate the attribute entropy E(S, A) of each attribute based on the collected road data;

Among them, S _i represents the ith subset of the training set samples divided according to the attribute A, |S| and |S _i | represent the number of samples in S and S _i respectively, m is the number of subsets divided by the training set samples; Among them, attribute A is the attribute of determining and analyzing road connectivity force based on the influence factor of step 1; Step 7, calculate the correlation function value CF(A) of each attribute based on the correlation function;

In the formula: X _{i m-1} and X _im are the specific values of the parameter X _ij , the subscript j represents each case of the attribute A, i represents each value of the data, n is the total amount of data, and m represents the attribute For the specific attributes selected in A, X _ij represents the value of each attribute; Step 8: Calculate the weight value of each attribute based on the associated function value CF(A) of each attribute;

In the formula: m is the number of attributes, CF(1), CF(2)...CF(m) are the correlation function values of each attribute respectively; Step 9. Calculate the information gain Gain'(S, A) of each attribute based on the information entropy E(S), the attribute entropy E(S, A) of each attribute, and the weight value Wg(A) of each attribute; Gain'(S,A)=(E(S)-E(S,A))*Wg(A) Step 10: Sort and construct a decision tree according to the size of each attribute information gain, and predict road conditions according to the decision tree. 2. the road condition information prediction method based on improved decision tree algorithm as claimed in claim 1 is characterized in that, in step 2, road capacity R _m is:

where α _l is the lane attenuation coefficient,

is the lane length of the i-th lane. 3. the road condition information prediction method based on improved decision tree algorithm as claimed in claim 1 is characterized in that, in step 2, expected waiting time T _s is:

In the formula, T _p is the ratio of the time of each traffic direction to the total cycle time. 4. the road condition information prediction method based on improved decision tree algorithm as claimed in claim 1, is characterized in that, in step 2, road section average turning number L _g is:

5. the road condition information prediction method based on improved decision tree algorithm as claimed in claim 1, is characterized in that, in step 4, excluding unqualified data comprises: Exclude data with traffic flow greater than the maximum limit value; Exclude the data whose road speed is greater than the maximum limit value; Exclude data with negative or empty traffic flow and road speed; Exclude data where the road speed is zero, but the traffic flow is not zero; Data with zero traffic flow but non-zero road speed is excluded. 6 . The method for predicting road condition information based on an improved decision tree algorithm according to claim 1 , wherein in step 4, the data repairing comprises: using data of an adjacent road or an adjacent time for repairing. 7 . 7. The road condition information prediction method based on improved decision tree algorithm as claimed in claim 1, is characterized in that, between step 4 and step 5, also comprises: Data classification: Construct a road connectivity decision tree for congestion and smooth conditions based on the average traffic density at the inflow end. 8. The road condition information prediction method based on improved decision tree algorithm as claimed in claim 1, is characterized in that, in step 10, the attribute with the largest information gain is used as the root node of the decision tree, and the attribute with the second largest information gain is used as the decision tree. The second-level nodes of the tree, and so on, construct a decision tree.

Images