Quantifying anomalous behavior by identifying anomalies at subtrajectories

• US 9,995,588 B2
• Filed: 06/23/2015
• Issued: 06/12/2018
• Est. Priority Date: 06/23/2015
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Banerjee, Prithu, Srivastava, Biplav, Tamilselvam, Srikanth Govindaraj
• Primary Examiner(s): ALHARBI, ADAM MOHAMED
• Application Number:
  US14/747,883
• Publication Number:
  US 20160377441A1
• Time in Patent Office: 1,085 Days
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

Methods and arrangements for identifying at least one anomaly in a path taken by a plurality of objects. A plurality of trajectories are input, wherein each trajectory comprises a data set indicative of a path taken by a plurality of objects from a starting point to an ending point, wherein the starting point and ending point are substantially similar for each trajectory. A plurality of sub-trajectories within the input trajectories are identified. There are identified, within the plurality of sub-trajectories, a set of sub-trajectories that are anomalous when compared to other sub-trajectories within the plurality of sub-trajectories, wherein the anomalous sub-trajectories deviate from a predetermined standard. A maximal anomalous sub-trajectory is identified from among the identified set of anomalous sub-trajectories. Other variants and embodiments are broadly contemplated herein.

Claims

1. A method of identifying at least one anomaly in a path taken by a plurality of objects, said method comprising:

controlling at least one processor to execute computer code that performs the steps of;

inputting a plurality of trajectories, wherein each trajectory comprises a data set indicative of a path taken by a plurality of vehicles from a starting point to an ending point, wherein the starting point and ending point are substantially similar for each trajectory and wherein each of the plurality of trajectories is manned to a road network;

identifying a plurality of sub-trajectories within the input trajectories, wherein each of the plurality of sub-trajectories comprise a portion of the path taken by the plurality of vehicles;

identifying a set of sub-trajectories, within the plurality of sub-trajectories, that are anomalous when compared to other sub-trajectories within the plurality of subtrajectories, wherein the anomalous sub-trajectories deviate from a predetermined standard, wherein the identifying comprises identifying an average travel time with respect to the each of the plurality of sub-trajectories using a historical distribution of travel times and wherein the anomalous sub-trajectories are identified based upon the sub-trajectory exceeding the average travel time by a predetermined deviation amount;

and

obtaining a maximal anomalous sub-trajectory from among the identified set of anomalous sub-trajectories by sorting the anomalous sub-trajectories within the set of sub-trajectories and identifying the anomalous sub-trajectory from the sorted set, wherein the maximal anomalous sub-trajectory comprises a sub-trajectory associated with one of the plurality of vehicles that identifies the one of the plurality of vehicles as engaging in an undesired driving pattern.

2. The method according to claim 1, wherein the set of anomalous sub-trajectories comprises one-length sub-trajectories.

3. The method according to claim 1, wherein said identifying of a maximal anomalous sub-trajectory comprises adding an edge to each of the anomalous sub-trajectories.

4. The method according to claim 3, wherein said adding of an edge comprises adding one of:

a left edge or a right edge.

5. The method according to claim 4, wherein said identifying of a maximal anomalous sub-trajectory comprises subsequently adding the other of:

a left edge or a right edge.

6. The method according to claim 1, wherein said identifying of a maximal anomalous sub-trajectory comprises:

adding at least one edge to each of the anomalous one-length sub-trajectories;

finding the longest list of sub-trajectories that remain anomalous subsequent to said adding of at least one edge; and

iterating said steps of adding and finding until a maximal anomalous sub-trajectory is determined.

7. The method according to claim 1, comprising determining anomalous behavior via comparing the maximal anomalous sub-trajectory to a corresponding input trajectory.

8. The method according to claim 7, wherein said determining of anomalous behavior comprises determining a proportion of the corresponding input trajectory accounted for by the maximal anomalous sub-trajectory, and comparing the proportion to a predetermined threshold.

9. The method according to claim 1, wherein said identifying of a set of sub-trajectories comprises deriving the anomalous sub-trajectories from the data sets of the input trajectory.

10. The method according to claim 9, wherein said learning comprises computing at least one Mahalanobis Distance.

11. The method according to claim 1, wherein the input trajectories comprise speed distributions relative to vehicle travel over a road network.

12. An apparatus for identifying at least one anomaly in a path taken by a plurality of objects, said apparatus comprising:

at least one processor; and

a computer readable storage medium having computer readable program code embodied therewith and executable by the at least one processor, the computer readable program code comprising;

computer readable program code configured to input a plurality of trajectories, wherein each trajectory comprises a data set indicative of a path taken by a plurality of vehicles from a starting point to an ending point, wherein the starting point and ending point are substantially similar for each trajectory and wherein each of the plurality of trajectories is mapped to a road network;

computer readable program code configured to identify a plurality of subtrajectories within the input trajectories, wherein each of the plurality of sub-trajectories comprise a portion of the path taken by the plurality of vehicles;

computer readable program code configured to identify a set of sub-trajectories, within the plurality of sub-trajectories, that are anomalous when compared to other subtrajectories within the plurality of sub-trajectories, wherein the anomalous sub-trajectories deviate from a predetermined standard, wherein the identifying comprises identifying an average travel time with respect to the each of the plurality of sub-trajectories using a historical distribution of travel times and wherein the anomalous sub-trajectories are identified based upon the sub-trajectory exceeding the average travel time by a predetermined deviation amount; and

computer readable program code configured to obtain a maximal anomalous sub-trajectory from among the identified set of anomalous sub-trajectories by sorting the anomalous sub-trajectories within the set of sub-trajectories and identifying the anomalous sub-trajectory from the sorted set, wherein the maximal anomalous sub-trajectory comprises a sub-trajectory associated with one of the plurality of vehicles that identifies the one of the plurality of vehicles as engaging in an undesired driving pattern.

13. A computer program product for identifying at least one anomaly in a path taken by a plurality of objects, said computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to input a plurality of trajectories, wherein each trajectory comprises a data set indicative of a path taken by a plurality of vehicles from a starting point to an ending point, wherein the starting point and ending point are substantially similar for each trajectory and wherein each of the plurality of trajectories is mapped to a road network;

computer readable program code configured to identify a plurality of subtrajectories within the input trajectories, wherein each of the plurality of sub-trajectories comprise a portion of the path taken by the plurality of vehicles;

computer readable program code configured to identify a set of sub-trajectories, within the plurality of sub-trajectories, that are anomalous when compared to other subtrajectories within the plurality of sub-trajectories, wherein the anomalous sub-trajectories deviate from a predetermined standard, wherein the identifying comprises identifying an average travel time with respect to the each of the plurality of sub-trajectories using a historical distribution of travel times and wherein the anomalous sub-trajectories are identified based upon the sub-trajectory exceeding the average travel time by a predetermined deviation amount; and

computer readable program code configured to obtain a maximal anomalous sub-trajectory from among the identified set of anomalous sub-trajectories by sorting the anomalous sub-trajectories within the set of sub-trajectories and identifying the anomalous sub-trajectory from the sorted set, wherein the maximal anomalous sub-trajectory comprises a sub-trajectory associated with one of the plurality of vehicles that identifies the one of the plurality of vehicles as engaging in an undesired driving pattern.

14. The computer program product according to claim 13, wherein the set of anomalous sub-trajectories comprises one-length sub-trajectories.

15. The computer program product according to claim 13, wherein the identifying of a maximal anomalous sub-trajectory comprises adding an edge to each of the anomalous sub-trajectories.

16. The computer program product according to claim 15, wherein the adding of an edge comprises adding one of:

a left edge or a right edge.

17. The computer program product according to claim 16, wherein the identifying of a maximal anomalous sub-trajectory comprises subsequently adding the other of:

a left edge or a right edge.

18. The computer program product according to claim 13, wherein the identifying of a maximal anomalous sub-trajectory comprises:

adding at least one edge to each of the anomalous one-length sub-trajectories;

finding the longest list of sub-trajectories that remain anomalous subsequent to said adding of at least one edge; and

iterating said steps of adding and finding until a maximal anomalous sub-trajectory is determined.

19. The computer program product according to claim 13, comprising computer readable program code configured to determine anomalous behavior via comparing the maximal anomalous sub-trajectory to a corresponding input trajectory.