Determine Spatiotemporal Causal Interactions in Data

• US 20150117713A1
• Filed: 12/31/2014
• Published: 04/30/2015
• Est. Priority Date: 12/21/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zheng, Yu, Xie, Xing
• Granted Patent: US 9,536,146 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0133 for classifying traffic situation

Abstract

Techniques for detecting outliers in data and determining spatiotemporal causal interactions in the data are discussed. A process collects global positioning system (GPS) points in logs and identifies geographical locations to represent the area where the service vehicles travelled with a passenger. The process models traffic patterns by: partitioning the area into regions, segmenting the GPS points from the logs into time bins, and identifying the GPS points associated with transporting the passenger. The process projects the identified GPS points onto the regions to construct links connecting GPS points located in two or more regions. Furthermore, the process builds a three-dimensional unit cube to represent features of each link. The points farthest away from a center of data cluster are detected as outliers, which represent abnormal traffic patterns. The process constructs outlier trees to evaluate relationships of the outliers and determines the spatiotemporal causal interactions in the data.

Claims

1-20. -20. (canceled)

21. A method implemented at least partially by a processor, the method comprising:

collecting sequences of global positioning system (GPS) points from logs of service vehicles;

identifying geographical locations from the GPS points to represent an area where the service vehicles travelled as recorded in the logs;

generating links based at least in part on travel by the service vehicles between two or more regions of the area in a plurality of time frames; and

detecting outliers in the GPS points in the geographical locations based at least in part on the links.

22. The method of claim 21, further comprising dividing the area into the two or more regions based at least in part on major roads.

23. The method of claim 21, wherein generating the links is further based at least in part on a number of transitions pertaining to the links for the travel between the two or more regions.

24. The method of claim 23, wherein the number of transitions is associated with a departure time from at least a region of origin and an arrival time in at least a region of destination, the region of origin and the region of destination comprising at least two of the two or more regions of the area.

25. The method of claim 21, further comprising:

calculating scores of minimum distort of features for each of the links in a particular time frame of the plurality of time frames; and

identifying extreme values among the scores of minimum distort as at least some of the outliers.

26. The method of claim 25, wherein the calculating the scores of minimum distort includes computing an Euclidean distance to calculate a difference between each feature of two time frames of the plurality of time frames, wherein the two time frames pertain to a same link.

27. The method of claim 21, wherein a time frame of the plurality of time frames is determined based at least in part on:

separating the GPS points into (a) weekdays and (b) weekends and/or holidays of a year; and

assigning the GPS points to time bins representative of thirty minute increments of a day.

28. The method of claim 21, further comprising:

creating a three-dimensional unit cube for each time frame of the plurality of time frames, the three-dimensional unit cube including a feature vector comprising;

a total number of objects on the link;

a proportion of the objects among all of the objects moving out of an origin region of the two or more regions during a particular time frame; and

a proportion of the objects among all of the objects moving into a destination region of the two or more regions in the particular time frame, wherein each point represents a link; and

identifying extreme points farthest away from a center data cluster as at least some of the outliers in the particular time frame.

29. The method of claim 21, further comprising:

constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from an early time frame of the plurality of time frames through a last time frame of the plurality of time frames;

determining that a first outlier of the outliers occurred at a time before a second outlier of the outliers;

determining that the first outlier and the second outlier are spatially correlated;

determining that the first outlier is a parent of the second outlier; and

adding the parent and a child that is dependent on the parent in the outlier trees being constructed.

30. The method of claim 21, further comprising determining spatiotemporal causal relationships from outlier trees by:

constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from an early time frame of the plurality of time frames through a last time frame of the plurality of time frames; and

discovering frequent subtrees from the constructed outlier trees that correspond to a causality and a relationship among the frequent subtrees to represent abnormal traffic patterns in the GPS points.

31. The method of claim 30, further comprising providing recommendations based at least in part on the frequent subtrees including abnormal traffic patterns, the recommendations including diverting traffic to less travelled roads, building additional roads, suggesting a bus route, or suggesting a subway line.

36. The computer storage media of claim 21, wherein the calculating the scores of minimum distort includes computing an Euclidean distance to calculate a difference between each feature of two time frames pertaining to a same link.

32. One or more computer storage media encoded with instructions that, when executed by a processor, perform acts comprising:

collecting sequences of global positioning system (GPS) points from logs of service vehicles;

identifying geographical locations from the GPS points to represent an area where the service vehicles travelled as recorded in the logs;

generating links to connect two or more regions of the area based at least in part on a number of transitions pertaining to the links for travel of the service vehicles between the two or more regions; and

detecting outliers in the GPS points in the geographical locations based at least in part on the links.

33. The computer storage media of claim 32, wherein:

at least some of the GPS points correspond to similar time spans in a year; and

the outliers are detected based at least in part on GPS points that correspond to the similar time spans in the year.

34. The computer storage media of claim 32, wherein the number of transitions is associated with a departure time from at least a region of origin and an arrival time in at least a region of destination, the region of origin and the region of destination comprising at least two of the two or more regions.

35. The computer storage media of claim 32, wherein the acts further comprise:

calculating scores of minimum distort of features for each of the links in a time frame; and

identifying extreme values among the scores of minimum distort as at least some of the outliers.

37. A device comprising.

one or more processors;

computer storage media; and

one or more modules maintained in the computer storage media and executable on the one or more processors to;

collect sequences of global positioning system (GPS) points from logs of service vehicles;

identify geographical locations from the GPS points to represent an area where the service vehicles travelled as recorded in the logs;

divide the area into a plurality of regions based at least in part on major roads;

generate links based at least in part on travel by the service vehicles between the plurality of regions of the area in a plurality of time frames; and

detect outliers in the GPS points in the geographical locations based at least in part on the links.

38. The device of claim 37, wherein the one or more modules are executable on the one or more processors to further:

construct outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from an early time frame of the plurality of time frames through a last time frame of the plurality of time frames;

determine that a first outlier of the outliers occurred at a time before a second outlier of the outliers, the first outlier and the second outlier being spatially correlated;

determine that the first outlier detected is a parent of the second outlier; and

add the parent and a child that is dependent on the parent in the outlier trees being constructed.

39. The device of claim 37, wherein the one or more modules are executable on the one or more processors to further:

construct outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from an early time frame of the plurality of time frames through a last time frame of the plurality of time frames; and

discover frequent subtrees from the constructed outlier trees that correspond to a causality and a relationship among the frequent subtrees to represent abnormal traffic patterns in the GPS points.

40. The device of claim 37, wherein the one or more modules are executable on the one or more processors to further provide recommendations based at least in part on the frequent subtrees including abnormal traffic patterns, the recommendations including diverting traffic to less travelled roads, building additional roads, suggesting a bus route, or suggesting a subway line.