Determine spatiotemporal causal interactions in data

• US 9,536,146 B2
• Filed: 12/31/2014
• Issued: 01/03/2017
• 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
• Primary Examiner(s): Tabatabai, Abolfazl
• Application Number:
  US14/587,270
• Publication Number:
  US 20150117713A1
• Time in Patent Office: 734 Days
• Field of Search: 382/103, 382/104, 382/236, 348/143, 348/169, 701/117, 701/417, 701/472, 707/724, 340/990
• US Class Current: 1/1
• 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. A method implemented at least partially by a processor, the method comprising:

accessing, from a database associated with a content service provider, logs of global positioning system (GPS) points collected by geolocation sensors associated with service vehicles;

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

generating a graph of regions associated with the area based at least in part on the logs associated with the area in a plurality of time frames;

detecting outliers in the GPS points based at least in part on the graph; and

providing, via a user interface that is presented via a display of a device, recommendations for travelling in the area based at least in part on the outliers.

2. The method of claim 1, further comprising:

dividing the area into the two or more regions based at least in part on major roads; and

generating links for connecting pairs of regions of the two or more regions.

3. The method of claim 1, 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.

4. The method of claim 3, 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.

5. The method of claim 1, 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.

6. The method of claim 5, 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.

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

separating the GPS points into weekdays and at least one of weekends or holidays of a year; and

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

8. The method of claim 1, further comprising:

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

a total number of service vehicles on a link between an origin region and a destination region of the regions associated with the area;

a proportion of the service vehicles among the total number of the service vehicles moving out of the origin region during a particular time frame; and

a proportion of the service vehicles among the total number of the service vehicles moving into the destination region in the particular time frame and identifying extreme points farthest away from a center data cluster as at least some of the outliers in the particular time frame.

9. The method of claim 1, further comprising:

constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from a first 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.

10. The method of claim 1, 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 a first 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.

11. The method of claim 10, further comprising providing the 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.

12. The computer storage media of claim 1, 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.

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

accessing, from a database associated with a content service provider, logs of global positioning system (GPS) points collected by geolocation sensors associated with 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.

14. The computer storage media of claim 13, 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.

15. The computer storage media of claim 13, 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.

16. The computer storage media of claim 13, 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.

17. 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 perform one or more operations comprising;

accessing, from a database associated with a content service provider, logs of global positioning system (GPS) points collected by geolocation sensors associated with service vehicles;

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

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

generating links between pairs of regions of the plurality of regions 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

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

18. The device of claim 17, operations further comprising:

constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from a first 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, the first outlier and the second outlier being spatially correlated;

determining that the first outlier detected 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.

19. The device of claim 17, operations further comprising:

constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from a first 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.

20. The device of claim 19, operations further comprising providing, via a user interface associated with the device, 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.