Scalable spatiotemporal clustering of heterogeneous events

• US 9,230,216 B2
• Filed: 05/08/2013
• Issued: 01/05/2016
• Est. Priority Date: 05/08/2013
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Bart, Evgeniy, Price, Robert R.
• Primary Examiner(s): CHANG, LI WU
• Application Number:
  US13/890,139
• Publication Number:
  US 20140337264A1
• Time in Patent Office: 972 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

One embodiment of the present invention provides a system for clustering heterogeneous events. During operation, the system finds a partition of events into clusters such that each cluster includes a set of events. In addition, the system estimates probability distributions for various properties of events associated with each cluster. The system obtains heterogeneous event data, and analyzes the heterogeneous event data to determine the distribution of event properties associated with clusters and to assign events to clusters.

Claims

1. A computer-executable method, comprising:

determining a prior distribution of a cluster index variable for event assignments, wherein the prior distribution includes a hyperparameter that describes the mean and variance for the cluster index variable;

determining a property-specific prior distribution for a respective event property, wherein the property-specific prior distribution includes a property-specific hyperparameter that describes the mean and variance for the respective event property;

obtaining heterogeneous event data that corresponds to two or more heterogeneous event types;

generating, based on the property-specific prior distribution for the respective event property and the property-specific hyperparameter, event property clusters for a respective event property of a plurality of event properties, wherein the respective event property is probabilistically dependent on the cluster index variable;

generating two or more different event type clusters for the heterogeneous event types, wherein a respective event type cluster is associated with a plurality of event property clusters, a respective event has an event type, an event type is an event property, and the respective event is represented by one or more event properties; and

assigning events from the heterogeneous event data to the two or more different event type clusters and the event property clusters.

2. The method of claim 1, wherein a respective event property is one of:

event time, event location, event type, event description, event location properties, or event time properties.

3. The method of claim 2, wherein the event location properties indicate whether the location is urban, rural, or near or far from a road.

4. The method of claim 2, wherein the event time properties indicate whether the event time is day, night, weekend, or weekday.

5. The method of claim 1, further comprising:

analyzing the heterogeneous event data to determine the distribution of event properties associated with clusters using a joint probability distribution that factorizes as follows;

6. The method of claim 1, further comprising applying a Gibbs sampling or variational inference algorithm to determine the distribution of event properties associated with clusters and to assign events to clusters.

7. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

determining a prior distribution of a cluster index variable for event assignments, wherein the prior distribution includes a hyperparameter that describes the mean and variance for the cluster index variable;

determining a property-specific prior distribution for a respective event property, wherein the property-specific prior distribution includes a property-specific hyperparameter that describes the mean and variance for the respective event property;

obtaining heterogeneous event data that corresponds to two or more heterogeneous event types;

generating, based on the property-specific prior distribution for the respective event property and the property-specific hyperparameter, event property clusters for a respective event property of a plurality of event properties, wherein the respective event property is probabilistically dependent on the cluster index variable;

generating two or more different event type clusters for the heterogeneous event types, wherein a respective event type cluster is associated with a plurality of event property clusters, a respective event has an event type, an event type is an event property, and the respective event is represented by one or more event properties; and

assigning events from the heterogeneous event data to the two or more different event type clusters and the event property clusters.

8. The non-transitory computer-readable storage medium of claim 7, wherein a respective event property is one of:

event time, event location, event type, event description, event location properties, or event time properties.

9. The non-transitory computer-readable storage medium of claim 8, wherein the event location properties indicate whether the location is urban, rural, or near or far from a road.

10. The non-transitory computer-readable storage medium of claim 8, wherein the event time properties indicate whether the event time is day, night, weekend, or weekday.

11. The non-transitory computer-readable storage medium of claim 7, wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

analyzing the heterogeneous event data to determine the distribution of event properties associated with clusters using a joint probability distribution that factorizes as follows;

12. The non-transitory computer-readable storage medium of claim 7, wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising applying a Gibbs sampling or variational inference algorithm to determine the distribution of event properties associated with clusters and to assign events to clusters.

13. A computing system for performing a method, the system comprising:

one or more processors,

a non-transitory computer-readable medium coupled to the one or more processors having instructions stored thereon that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

determining a prior distribution of a cluster index variable for event assignments, wherein the prior distribution includes a hyperparameter that describes the mean and variance for the cluster index variable;

determining a property-specific prior distribution for a respective event property, wherein the property-specific prior distribution includes a property-specific hyperparameter that describes the mean and variance for the respective event property;

obtaining heterogeneous event data that corresponds to two or more heterogeneous event types;

generating, based on the property-specific prior distribution for the respective event property and the property-specific hyperparameter, event property clusters for a respective event property of a plurality of event properties, wherein the respective event property is probabilistically dependent on the cluster index variable;

generating two or more different event type clusters for the heterogeneous event types, wherein a respective event type cluster is associated with a plurality of event property clusters, a respective event has an event type, an event type is an event property, and the respective event is represented by one or more event properties; and

assigning events from the heterogeneous event data to the two or more different event type clusters and the event property clusters.

14. The system of claim 13, wherein a respective event property is one of:

event time, event location, event type, event description, event location properties, or event time properties.

15. The system of claim 14, wherein the event location properties indicate whether the location is urban, rural, or near or far from a road.

16. The system of claim 14, wherein the event time properties indicate whether the event time is day, night, weekend, or weekday.

17. The system of claim 13, wherein the non-transitory computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

analyzing the heterogeneous event data to determine the distribution of event properties associated with clusters using a joint probability distribution that factorizes as follows;

18. The system of claim 13, wherein the non-transitory computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

applying a Gibbs sampling or variational inference algorithm to determine the distribution of event properties associated with clusters and to assign events to clusters.