Event identification in sensor analytics

• US 8,620,624 B2
• Filed: 09/30/2008
• Issued: 12/31/2013
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Verve Group, Inc. (Samarion SE)
• Original Assignee: Sense Networks, Inc. (Samarion SE)
• Inventors: Skibiski, Greg, Pentland, Alex (Sandy), Jebara, Tony, Lemke, Christine, Loecher, Markus, Rao, Girish, Uechi, Jason, Shaw, Blake, Mattiello, Joseph, Rosenberg, David
• Primary Examiner(s): SUGLO, JANET L
• Application Number:
  US12/241,266
• Publication Number:
  US 20100082301A1
• Time in Patent Office: 1,918 Days
• Field of Search: 702/188
• US Class Current: 702/188
• CPC Class Codes: H04L 41/0618 based on the physical or logical position
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A method of detecting an event anomaly includes receiving one or more data points, in which each data point represents a spatial or temporal event; associating a unique identifier with each of the one or more data points to obtain one or more individualized data points; distributing the one or more individualized data points across a grid, in which the grid includes one or more cells; determining an event likelihood ratio for one or more of the grid cells; identifying one or more event clusters, in which each event cluster includes one or more of the grid cells; and storing in a data repository an event cluster having a significance level above a threshold significance level.

Claims

1. A method of detecting an event anomaly comprising:

receiving, by a data processing apparatus, one or more individualized data points, wherein each individualized data point represents a spatial or temporal event and has a unique identifier associated with it;

distributing, by the data processing apparatus, the one or more individualized data points across a grid, wherein the grid includes one or more cells;

determining, by the data processing apparatus, an event likelihood ratio for each of one or more of the grid cells, wherein determining the event likelihood ratio for a respective grid cell comprises determining an expected number of individualized data points in the respective grid cell;

identifying, by the data processing apparatus, one or more event clusters, based on the event likelihood ratio, wherein each event cluster includes one or more of the grid cells, thus defining a region on the grid;

generating, by the data processing apparatus, multiple replicas of the region;

performing, by the data processing apparatus, simulations on the multiple replicas to obtain a significance value for each of the one or more event clusters; and

storing, by the data processing apparatus, the one or more event clusters in a data repository, based on a comparison of the significance value to a threshold.

2. The method according to claim 1, wherein the multiple replicas are generated based in part on a null hypothesis, and wherein the null hypothesis represents a baseline value determined from a historical dataset.

3. The method according to claim 1, wherein the multiple replicas are populated with random values obtained from a Poisson distribution or a negative binomial distribution with a mean and a variance from a historical data set.

4. The method according to claim 1, wherein the simulations performed on the multiple replicas are to enhance confidence that the one or more event clusters are anomalous.

5. The method according to claim 1, wherein the significance value corresponds to a ratio of the number of simulations that result in a maximum significance score that is greater than the event likelihood ratio relative to a total number of simulations performed by data processing apparatus.

6. The method according to claim 1, wherein the one or more data points are received according to a predetermined schedule.

7. The method according to claim 1, wherein the unique identifier comprises a location identifier.

8. The method according to claim 1, wherein the unique identifier comprises a time identifier.

9. The method according to claim 1, wherein the unique identifier comprises an event type identifier.

10. The method according to claim 1, wherein the unique identifier is associated with an individual user.

11. The method according to claim 1, wherein the unique identifier comprises a demographic attribute.

12. The method according to claim 11, wherein the demographic attribute is selected from the group consisting of Census Bureau data, financial demographics, social demographics, historical demographic information, derived demographic information, gender, race, educational level, historical geographic information and user entered information.

13. The method according to claim 1, wherein the grid is a spatial grid.

14. The method according to claim 13, further comprising partitioning the spatial grid based on a density of the individualized data points over a specified area.

15. The method according to claim 13, further comprising partitioning the spatial grid according to a predefined geographic layout.

16. The method according to claim 1, wherein the grid is a space-time grid.

17. The method according to claim 16, further comprising partitioning the space-time grid based on a frequency of occurrence of the individualized data points over a specified time interval.

18. The method according to claim 16, further comprising partitioning the space-time grid based on a density of individualized data points over a specified area.

19. The method according to claim 1, wherein the expected number of individualized data points is based on a time duration of historical events in the respective cell.

20. The method according to claim 1, wherein determining the expected number of individualized data points is based on an historical dataset in the respective cell.

21. The method according to claim 20, wherein determining the expected number of individualized data points comprises adjusting an historical dataset for the respective cell based on one or more covariate parameters.

22. The method according to claim 21, wherein the one or more covariate parameters comprises a weather event.

23. The method according to claim 21, wherein the one or more covariate parameters is selected from the group consisting of a holiday event, a time of the day, a time of the week, a time of the month, and a time of the year.

24. The method according to claim 1, wherein identifying one or more event clusters comprises calculating a total event likelihood ratio for one or more grid cells.

25. The method according to claim 1, wherein identifying one or more event clusters comprises scanning the grid for a group of one or more cells having a maximum event likelihood ratio.

26. The method according to claim 25, wherein the scanning is across a spatial region of the grid.

27. The method according to claim 25, wherein the scanning occurs over an interval in time.

28. The method according to claim 25, wherein the scanning occurs over an interval in space-time.

29. The method according to claim 1, further comprising exporting one or more identified event clusters to a display.

30. The method according to claim 29, wherein the one or more exported event clusters are non-overlapping.

31. The method according to claim 29, wherein an identified event cluster having a center in a previously exported event cluster is excluded from the display.

32. The method according to claim 29, wherein an identified event cluster having a center located in the center of a previously exported event cluster is excluded from the display.

33. The method according to claim 29, wherein an event cluster corresponding to each cell of the grid is exported to the display.

34. The method according to claim 1, further comprising refining a grid partition based on a size of one or more event clusters.

35. The method according to claim 1, further comprising annotating the event clusters with demographic information.

36. The method according to claim 1, wherein the threshold is user-defined.

37. The method according to claim 1, wherein the threshold is based on a size of the one or more event clusters.

38. The method according to claim 1, wherein the threshold is time dependent.

39. The method according to claim 1, further comprising determining a center of at least one of the one or more clusters having a relative risk greater than the specified threshold.

40. The method according to claim 1, further comprising identifying a flow cluster, wherein the flow cluster comprises a second order event cluster and a previously identified event cluster.

41. The method according to claim 40, wherein the second order event cluster is related to the previously identified event cluster based on individualized data points contained in the second order cluster and the previously identified cluster.

42. The method according to claim 41, wherein the individualized data points of the second order event cluster and a portion of the individualized data points of the previously identified cluster have the same unique identifier.

43. The method according to claim 1, further comprising tracking the one or more event clusters across a temporal and/or spatial region.

44. The method according to claim 1, further comprising detecting a deviation in the one or more event clusters.

45. A non-transitory computer readable medium having stored thereon a computer program that, when executed, causes a computer to perform the steps of:

receiving one or more individualized data points, wherein each individualized data point represents a spatial or temporal event and has a unique identifier associated with it;

distributing the one or more individualized data points across a grid, wherein the grid includes one or more cells;

determining an event likelihood ratio for each of one or more of the grid cells, wherein determining the event likelihood ratio for a respective grid cell comprises determining an expected number of individualized data points in the respective grid cell;

identifying one or more event clusters, based on the event likelihood ratio, wherein each event cluster includes one or more of the grid cells, thus defining a region on the grid;

generating multiple replicas of the region;

performing simulations on the multiple replicas to obtain a significance value for each of the one or more event clusters; and

storing the one or more event clusters in a data repository, based on a comparison of the significance value to a threshold.

46. A system for detecting an event anomaly comprising:

a network;

one or more user devices in communication with the network; and

a processor in communication with the network, wherein the processor is for;

i) receiving one or more individualized data points representing data originating from the one or more user devices, wherein each individualized data point represents a spatial or temporal event and has a unique identifier associated with it;

ii) distributing the one or more individualized data points across a grid, wherein the grid includes one or more cells;

iii) determining an event likelihood ratio for each of one or more of the grid cells, wherein determining the event likelihood ratio for a respective grid cell comprises determining an expected number of individualized data points in the respective grid cell;

iv) identifying one or more event clusters, based on the event likelihood ratio, wherein each event cluster includes one or more of the grid cells, thus defining a region on the grid;

v) generating multiple replicas of the region;

vi) performing simulations on the multiple replicas to obtain a significance value for each of the one or more event clusters; and

vii) storing the one or more event clusters in a data repository, based on a comparison of the significance value to a specified threshold value.

47. A system comprising:

means for distributing one or more individualized data points across a grid, wherein the grid includes one or more cells;

means for detecting an event likelihood ratio for each of the one or more cells of the grid, wherein detecting the event likelihood ratio for a respective grid cell comprises determining an expected number of individualized data points in the one or more cells;

means for identifying one or more event cluster based on the event likelihood ratio, wherein each event cluster includes one or more of the grid cells, thus defining a region on the grid;

means for generating multiple replicas of the region;

means for performing simulations on the multiple replicas to obtain a significance value for each of the one or more event cluster; and

means for storing the one or more event clusters in a data repository, based on a comparison of the significance value to a threshold.

48. A system comprising:

means for distributing one or more individualized data points across a grid, wherein the grid includes one or more cells;

means for detecting an event likelihood ratio for each of the one or more cells of the grid, wherein detecting the event likelihood ratio for a respective grid cell comprises determining an expected number of individualized data points in the one or more cells;

means for identifying one or more event cluster based on the event likelihood ratio, wherein each event cluster includes one or more of the grid cells, thus defining a region on the grid;

means for generating multiple replicas of the region;

means for performing simulations on the multiple replicas to obtain a significance value for each of the one or more event cluster, wherein the significance value corresponds to a ratio of the number of simulations that result in a maximum significance score that is greater than the event likelihood ratio relative to a total number of simulations performed; and

means for storing the one or more event clusters in a data repository when the significance value is determined to be less than a threshold risk level.