Determine Spatiotemporal Causal Interactions In Data

• US 20130166188A1
• Filed: 12/21/2011
• Published: 06/27/2013
• Est. Priority Date: 12/21/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zheng, Yu, Xie, Xing
• Application Number:
  US13/333,535
• Publication Number:
  US 20130166188A1
• Time in Patent Office: Days
• US Class Current: 701/117
• 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:

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; and

detecting outliers in the GPS points in the geographical locations by;

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

generating links to connect two or more regions based on a number of transitions pertaining to the links for travel between the regions;

calculating a score of minimum distort of features for each link in a time frame;

identifying extreme values among the score of minimum distort as temporal outliers.

2. The method of claim 1, wherein the GPS points are analyzed from similar time spans in the year.

3. The method of claim 1, wherein the time frame comprises:

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

dividing a time of a day into time bins of thirty minute increments.

4. The method of claim 1, wherein the number of transitions of the GPS points is associated with a departure time from at least a region of origin and an arrival time in at least a region of destination.

5. The method of claim 1, wherein the calculating the score of minimum distort includes computing an Euclidean distance to calculate a difference between each feature of two time frames pertaining to a same link.

6. The method of claim 1, further comprising:

creating a three-dimensional cube unit for each time, the three-dimensional cube unit includes a feature vector of (a) a total number of objects on the link, (b) a proportion of the objects among all of the objects moving out of an origin region during a time period, and (c) a proportion of the objects among all of the objects moving into a destination region in the time period, wherein each point represents a link; and

identifying extreme points farthest away from a center data cluster as spatiotemporal outliers in the time frame.

7. The method of claim 1, further comprising:

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

determining a first outlier detected is a parent of a second outlier, if the first outlier occurred before the second outlier in time, and the first outlier and the second outlier are spatially correlated; and

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

8. 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 spatiotemporal outliers being detected by determining dependencies of outliers from an early time frame through a last time frame; and

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

9. The method of claim 8, further comprising providing recommendations based on at least on the frequent subtrees being detected of abnormal traffic patterns, the recommendations include diverting traffic to less travelled roads, building additional roads, suggesting a bus route, or suggesting a subway line.

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

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

creating a model that simulates a relationship of traffic of the service vehicles travelling through regions in an area;

generating a matrix of the regions from the model to;

detect the outliers from a graph of the regions;

construct outlier trees based on temporal and spatial properties of the detected outliers; and

determine spatiotemporal causal relationships from the constructed outlier trees to correspond to abnormal traffic patterns.

11. The computer-readable storage media of claim 10, further comprising:

formulating a number of transitions of travel between two or more regions;

generating links to connect the two or more regions based on the number of transitions;

associating a link to a feature vector to create a three dimensional matrix of (a) a total number of objects on the link, (b) a proportion of the objects among all of the objects moving out of an origin region during a time period, and (c) a proportion of the objects among all of the objects moving into a destination region in the time period; and

identifying abnormal links as the outliers in the graph of the regions.

12. The computer-readable storage media of claim 10, further comprising:

calculating a score of distort for a link that connects two or more regions by searching for a minimum difference between each feature of a given time period and another time period pertaining to a same link;

using an Euclidian distance to calculate the minimum difference between each feature of the given time period and the another time period pertaining to the same link; and

computing each link against precedent time periods and future time periods to identify a minimum distort.

13. The computer-readable storage media of claim 10, further comprising creating the model by:

partitioning the area into the regions based at least in part on major roads;

segmenting the GPS points from the logs into time bins and identifying the GPS points associated with a passenger in the service vehicles; and

projecting the GPS points associated with the passenger onto the regions to create links connecting regions travelled with passenger.

14. The computer-readable storage media of claim 10, further comprising presenting a user interface to visually provide one or more recommendations for converting streets to one way streets, adding more lanes to streets, adding more roads, adding another subway line, adding a bus stop, or adding a train stop based at least in part on information generated from the spatiotemporal causal relationships.

15. The computer-readable storage media of claim 10, further comprising:

presenting a user interface to receive a user query for an area;

searching the model for the area that is represented by a map of the area partitioned by roads and streets; and

providing one or more recommendations for adding a subway line, or widening roads.

16. A system comprising:

a memory;

a processor coupled to the memory to perform acts comprising;

receiving geographical locations from logs of service vehicles, the geographical locations represent an area where the service vehicles travelled with a passenger;

accessing a model of traffic patterns in the area by partitioning regions in the area and projecting global positioning system (GPS) points from the logs onto the regions to construct transitions of the GPS points from a first region to a second region;

generating links to connect two or more regions based on a number of transitions pertaining to the links for travel with the passenger between the regions; and

calculating a score of minimum distort of features for each link in a time frame to detect spatiotemporal outliers.

17. The system of claim 16, wherein the time frame includes a fixed number of time increments of approximately 30 minutes.

18. The system of claim 16, wherein a spatiotemporal outlier is a link with non-spatial and non-temporal attribute values that are very different from values of neighbors.

19. The system of claim 16, further comprising:

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

determining a first outlier detected is a parent of a second outlier, if the first outlier occurred before the second outlier in time, and the first outlier and the second outlier are spatially correlated.

20. The system of claim 16, further comprising:

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

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