System and method for detecting generalized space-time clusters

• US 20050182502A1
• Filed: 02/12/2004
• Published: 08/18/2005
• Est. Priority Date: 02/12/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyengar, Vijay S.
• Granted Patent: US 7,343,272 B2
• Time in Patent Office: Days
• US Class Current: 700/90
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A system for detecting clusters in space and time using input data on occurrences of a phenomenon and characteristics at a plurality of locations and times comprises an expectation generation module determining expected occurrences of a phenomena, and an occurrence modeling module determining actual occurrences of the phenomena. The system further comprises a search module searching the expected occurrences and the actual occurrences for a plurality of candidate solutions, wherein each solution is represented as a set of points in the three-dimensional space, and wherein each point corresponds to a location at a time. The system comprises a convex container module determining at least one solution corresponding to a selected convex container shape from the plurality of candidate solutions, and a solution evaluation module determining a strength metric for each solution determined by the convex container module, the search module selecting a dominant cluster in the input data.

Claims

1. A system for detecting clusters in space and time using input data on occurrences of a phenomenon and characteristics at a plurality of locations and times comprising:

an expectation generation module determining expected occurrences of a phenomena at a plurality of locations and a plurality of times;

an occurrence modeling module determining actual occurrences of the phenomena at a plurality of locations and a plurality of times;

a search module searching the expected occurrences and the actual occurrences for a plurality of candidate solutions, wherein each solution is represented as a set of points in the three-dimensional space, and wherein each point corresponds to a location at a time;

a convex container module determining at least one solution corresponding to a selected convex container shape from the plurality of candidate solutions; and

a solution evaluation module determining a strength metric for each solution determined by the convex container module, the search module selecting a solution having a desirable strength, wherein the solution having the desirable strength indicates a dominant cluster in the input data.

2. The system of claim 1, wherein the search module selects a strongest solution as determined by the solution evaluation module.

3. The system of claim 1, further comprising a cache module to save the solutions having the desired shape determined by the convex container module for previously examined sets of points.

4. The system of claim 1, wherein the input data on occurrences of a phenomenon comprise counts and times of the occurrences of the phenomenon at the locations in a time period.

5. The system of claim 1, wherein the input data on characteristics of the locations and times comprise of the populations subject to the occurrences of the phenomenon at the locations and times.

6. The system of claim 1, wherein the expectation generation model generates expected counts of occurrences at the locations and times using a Poisson model.

7. The system of claim 1, wherein the occurrence modeling module determines the occurrences as equal to the occurrences in the input data.

8. The system of claim 1, wherein the occurrence modeling module determines the occurrences at the locations and times based on their characteristics and a domain dependent model.

9. The system of claim 8, wherein the occurrences are determined from the population using a Poisson model.

10. The system of claim 1, wherein the search module considers candidate solutions represented as sets of points and utilizes the convex container module to determine solutions having the desired shape from the candidate solutions.

11. The system of claim 10, wherein the candidate solutions are initialized based on the input data.

12. The system of claim 11, wherein each initial candidate solution is singleton point.

13. The system of claim 10, wherein the search module determines candidate solutions from solutions considered using an iterative process.

14. The system of claim 13, wherein candidate solutions are created from solutions considered based on the chosen convex container shape.

15. The system of claim 1, wherein the convex container module determines a solution with minimum volume, given the selected convex container shape, that includes all the points in a given candidate solution.

16. The system of claim 1, wherein the convex container module determines a solution with maximum volume, given the selected convex container shape, that excludes all the points not in the given candidate solution.

17. The system of claim 1, wherein the convex container module determines a solution that maximizes a measure representing the equality between the set of points in the given candidate solution and the set of points included in the solution, given the selected convex container shape.

18. The system of claim 1, wherein the solution evaluation module determines the strength metric based on all the points included in the solution and the expected occurrences determined by the expectation generation module and the occurrences determined by the occurrence modeling module.

19. The system of claim 1, wherein the strength metric is based on the likelihood ratio using the spatial scan statistic.

20. A method for detecting clusters comprising:

receiving input data on occurrences of a phenomenon at locations and times and data on characteristics of the locations and times;

determining actual occurrences of the phenomenon at the three-dimensional space-time points according to the input data;

determining expected occurrences in the absence of any clustering of the phenomenon at the points according to the characteristics of the occurrences using a domain dependent model for the phenomenon;

selecting a convex container shape for determining a cluster in the input data; and

determining a solution represented as a set of points that conforms to the selected convex container shape for a cluster with a desirable strength.

21. The method of claim 20, further comprising caching solutions conforming to the selected convex container shape.

22. The method of claim 20, wherein determining expected occurrences further comprises generating expected counts of occurrences at the locations and times using a model.

23. The method of claim 20, further comprising determining a strength of the cluster based on points included in the cluster, and the expected occurrences and the actual occurrences.

24. A program storage device is provided readable by machine, tangibly embodying a program of instructions automatically executable by the machine to perform method steps for determining a clusters, the method steps comprising:

receiving input data on occurrences of a phenomenon at locations and times and data on characteristics of the locations and times;

determining actual occurrences of the phenomenon at the three-dimensional space-time points according to the input data;

determining expected occurrences in the absence of any clustering of the phenomenon at the points according to the characteristics of the occurrences using a domain dependent model for the phenomenon;

selecting a convex container shape for determining a cluster in the input data; and

determining a solution represented as a set of points that conforms to the selected convex container shape for a cluster with a desirable strength.

25. The method of claim 24, further comprising caching solutions conforming to the selected convex container shape.

26. The method of claim 24, wherein determining expected occurrences further comprises generating expected counts of occurrences at the locations and times using a model.

27. The method of claim 24, further comprising determining a strength of the cluster based on points included in the cluster, and the expected occurrences and the actual occurrences.