Predicting traffic patterns

Patent metadata

Field	Value
Publication number	US-9424745-B1
Application number	US-201314077063-A
Country	US
Kind code	B1
Filing date	Nov 11, 2013
Priority date	Nov 11, 2013
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for predicting traffic patterns. One of the methods includes receiving a velocity distribution for a road segment, wherein the velocity distribution includes, for each velocity interval, a count of how many velocity observations have a velocity measurement within the velocity interval, wherein each velocity observation has one or more features describing conditions under which the velocity observation was made. A mixture model having K component distributions is generated for the velocity distribution. A decision tree is generated from the K component distributions and a rule is generated from a particular leaf of the decision tree, wherein the rule maps one or more features for the road segment to one of the K component distributions according to a path from the root of the decision tree to the particular leaf.

First claim

What is claimed is:

1. A computer implemented method comprising:
receiving a velocity distribution for a road segment, wherein the velocity distribution includes a plurality of velocity intervals, and, for each velocity interval, a count of how many velocity observations have a velocity measurement within the velocity interval, wherein each velocity observation has one or more features describing conditions under which the velocity observation was made;
generating a mixture model having K component distributions, including generating a respective component distribution for each of one or more segments of the velocity distribution, wherein each velocity observation in the velocity distribution is assigned to one of the K component distributions;
generating a decision tree, wherein the decision tree has a plurality of leaves, each leaf corresponding to one of the K component distributions, wherein a path from a root of the decision tree to each leaf represents a particular set of one or more features for the road segment;
generating a rule from a particular leaf of the decision tree, wherein the rule maps one or more features for the road segment to one of the K component distributions according to a path from the root of the decision tree to the particular leaf, wherein the path corresponds to the one or more features for the road segment; and
using, by a traffic data server implementing a predictive model that is configured to predict traffic behavior for a given road segment based on one or more features of the given road segment, the rule to predict traffic behavior for the road segment given one or more features for the road segment.

2. The method of claim 1 , further comprising:
receiving a first velocity observation having one or more first features;
obtaining a particular rule generated from at least one leaf of the plurality of leaves of the decision tree, wherein the particular rule maps the one or more first features of the first velocity observation to a first component distribution; and
designating the first velocity observation as belonging to the first component distribution based on the particular rule.

3. The method of claim 1 , further comprising:
determining that a first component of the K component distributions is assigned multiple, non-consecutive segments of the velocity distribution; and
assigning a first segment of the multiple, non-consecutive segments to a second component distribution of the K component distributions.

4. The method of claim 3 , wherein assigning a first segment of the multiple, non-consecutive segments to a second component distribution of the K component distributions comprises:
determining that a particular segment assigned to the first component is an out-of-order segment in an ordering of the K component distributions by mean; and
reassigning the out-of-order segment.

5. The method of claim 4 , wherein the out-of-order segment is a beginning segment or an end segment, and wherein reassigning the out-of-order segment comprises reassigning the out-of-order segment to a component distribution of an adjacent segment.

6. The method of claim 4 , wherein the out-of-order segment is between two adjacent segments assigned to respective adjacent component distributions, and wherein reassigning the out-of-order segment comprises reassigning the out-of-order segment to a particular component distribution of the adjacent component distributions having a lower mean.

7. The method of claim 1 , further comprising:
computing a difference between a first mean or median of a first component distribution of the K component distributions and a second mean or median of a second component distribution of the K component distributions;
determining that the difference satisfies a threshold; and
in response to determining that the difference satisfies the threshold, assigning a first segment of the velocity distribution assigned to the first component distribution and a second segment of the velocity distribution assigned to the second component distribution to a third component distribution.

8. The method of claim 1 , wherein a feature of the one or more features is a time of day, a vehicle type, a road segment type, information about existing weather conditions, a number of traffic lights on the road segment, a ratio of green light time to red light time on the road segment, or a direction of travel.

9. The method of claim 1 , wherein generating a mixture model having K component distributions further comprises:
calculating a Bayesian information criterion for a plurality of mixture models, wherein each mixture model has a different number of component distributions; and
determining that the mixture model from the plurality of mixture models has a least negative Bayesian information criterion.

10. The method of claim 9 , wherein calculating the Bayesian information criterion comprises applying a penalty factor that penalizes models having a higher number of component distributions.

11. A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
receiving a velocity distribution for a road segment, wherein the velocity distribution includes a plurality of velocity intervals, and, for each velocity interval, a count of how many velocity observations have a velocity measurement within the velocity interval, wherein each velocity observation has one or more features describing conditions under which the velocity observation was made;
generating a mixture model having K component distributions, including generating a respective component distribution for each of one or more segments of the velocity distribution, wherein each velocity observation in the velocity distribution is assigned to one of the K component distributions;
generating a decision tree, wherein the decision tree has a plurality of leaves, each leaf corresponding to one of the K component distributions, wherein a path from a root of the decision tree to each leaf represents a particular set of one or more features for the road segment;
generating a rule from a particular leaf of the decision tree, wherein the rule maps one or more features for the road segment to one of the K component distributions according to a path from the root of the decision tree to the particular leaf, wherein the path corresponds to the one or more features for the road segment; and
using, by a traffic data server implementing a predictive model that is configured to predict traffic behavior for a given road segment based on one or more features of the given road segment, the rule to predict traffic behavior for the road segment given one or more features for the road segment.

12. The system of claim 11 , wherein the operations further comprise:
receiving a first velocity observation having one or more first features;
obtaining a particular rule generated from at least one leaf of the plurality of leaves of the decision tree, wherein the particular rule maps the one or more first features of the first velocity observation to a first component distribution; and
designating the first velocity observation as belonging to the first component distribution based on the particular rule.

13. The system of claim 11 , wherein the operations further comprise:
determining that a first component of the K component distributions is assigned multiple, non-consecutive segments of the velocity distribution; and
assigning a first segment of the multiple, non-consecutive segments to a second component distribution of the

Assignees

• Kagoshima Alexander Masaru
• Sio Noelle Lindsay
• Das Kaushik Kunal
• Emc Corp

Inventors

• Kagoshima Alexander Masaru
• Sio Noelle Lindsay
• Das Kaushik Kunal

Classifications

• G08G1/052 Primary

  with provision for determining speed or overspeed {(speed measuring in general G01P)} · CPC title

• G08G1/0129

  for creating historical data or processing based on historical data · CPC title

• G08G1/0125 Primary

  Traffic data processing · CPC title